Regards croisés sur l'algorithmique et la programmation (4) - [Les nouvelles technologies pour l'enseignement des mathématiques]

Les aventures de Tom le robot

Regards croisés sur l’algorithmique et la programmation (4)

Sur un algorithme du bac S (sujet Antilles-Guyane septembre 2013)

Article mis en ligne le 15 février 2014

dernière modification le 16 décembre 2014

par Alain Busser, Guillaume Connan, Hubert Raymondaud, Pierre-Marc Mazat, Stéphan Manganelli

Cet article peut être librement diffusé et son contenu réutilisé pour une utilisation non commerciale (contacter l’auteur pour une utilisation commerciale) suivant la licence CC-by-nc-sa (http://creativecommons.org/licenses/by-nc-sa/3.0/fr/legalcode)

Le robot Tom doit emprunter un pont sans garde-corps de 10 pas de long et de 2 pas de large. Sa démarche est très particulière :

Soit il avance d’un pas tout droit ;
Soit il se déplace en diagonale vers la gauche (déplacement équivalent à un pas vers la gauche et un pas tout droit) ;
Soit il se déplace en diagonale vers la droite (déplacement équivalent à un pas vers la droite et un pas tout droit).

On suppose que ces trois types de déplacement sont aléatoires et équiprobables.

L’objectif de cet exercice est d’estimer la probabilité p de l’évènement S « Tom traverse le pont » c’est-à-dire « Tom n’est pas tombé dans l’eau et se trouve encore sur le pont au bout de 10 déplacements ».

Préhistoire du sujet

Ce sujet date de 2002, et résulte du travail de l’IREM de Lorraine ; voir la fiche ici. On remarquera le nom du marcheur titubant, et la raison pour laquelle il titubait... On peut donc estimer que les bugs sont pour les robots comme l’alcool pour les humains.

Les titubations tribulations d’Alain Busser

CoffeeScript

CoffeeScript permet de rédiger l’algorithme avec concision, parce que les doubles inégalités (ou encadrements) sont reconnues par ce langage. Comme on peut programmer en CoffeeScript dans CaRMetal, on peut aussi faire une figure animée grâce à celui-ci.

Pour programmer en CoffeeScript au niveau lycée, voici l’outil habituel dans cette rubrique :


alcoffeethmique: outil d’algorithmique niveau lycée, basé sur CoffeeScript

l’article en pdf	son source en odt	la coffeegure

MathsOntologie

l’article en pdf	son source en odt

calcul formel

Puisque la probabilité est calculée dans le sujet par tableur, autant se servir des possibilités de calcul formel que permet CmathOOoCAS, pour avoir les valeurs exactes dans le tableau (fait sous Libre Office avec les mêmes manips que celles de Stephan ci-dessous [1]) :

n	a_n	b_n	c_n
0	0	1	0
1	1/3	1/3	1/3
2	2/9	1/3	2/9
3	5/27	7/27	5/27
4	4/27	17/81	4/27
5	29/243	41/243	29/243
6	70/729	11/81	70/729
7	169/2187	239/2187	169/2187
8	136/2187	577/6561	136/2187
9	985/19683	1393/19683	985/19683
10	2378/59049	1121/19683	2378/59049

On y voit alors que la probabilité cherchée est $\frac{8119}{59049} \approx 0,1374959779$

Plus généralement, on peut trouver l’expression exacte de la probabilité selon n, en diagonalisant la matrice $\left(\begin{array}{rrr} 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \end{array} \right)$. Avec une petite séance Xcas, on trouve alors que

$a_n = \frac{\sqrt{2}\left( (1+\sqrt{2})^n - (1-\sqrt{2})^n \right)}{4 \times 3^n}$
$b_n = \frac{ (1+\sqrt{2})^n - (1-\sqrt{2})^n}{2 \times 3^n}$
$c_n = \frac{\sqrt{2}\left( (1+\sqrt{2})^n - (1-\sqrt{2})^n \right)}{4 \times 3^n}$

D’où on tire la valeur exacte de la probabilité pour Tom, d’être sec au bout de $n$ pas : $p_n = \frac{(1+\sqrt{2})^{n+1}+(1-\sqrt{2})^{n-1}}{2 \times 3^n}$ : On a un peu de mal à voir que ce sont des fractions ! Toujours est-il que $p_n$ étant la somme de deux suites géométriques de raison inférieure à 1, tend vers 0, ce qui veut dire que sur un pont infini, Tom est condamné à rouiller presque sûrement !

La tortue speedée de Guillaume Connan

Le texte est au bout de ce lien

La contribution de Stéphan Manganelli

LARP évidemment, mais aussi un peu de tableur, l’R de rien :

Voir aussi cet atelier en vidéo

La contribution de Pierre-Marc Mazat

l’article en pdf	la figure (+scripts)	les fichiers Maxima

Tom le robot prend l’R avec Hubert Raymondaud

Le fichier au format R

(on peut cliquer sur « télécharger » en bas, mais dans ce cas il faut renommer le résultat avec une extension .R ; il est plus simple de télécharger l’original ci-dessous)

#*****************************************************
# ROBOT TOM
# ANTILLES GUYANE Septembre 2013
# L'algorithme de l'énoncé, exercice 4-1.
robtom1 <- function(){
x <- 0 ; y <- 0 ; urne <- c(-1, 0, 1)
while (y >= -1 & y <= 1 & x <= 9) {
n <- sample(urne, 1)
y <- y + n
x <- x + 1
}
# Affichage des résultats
cat("La dernière position de TOM sur le pont : A(",
x, ",", y, ")\n\n")
}
#-----------------------------
# Exercice 4-2. Qualification de l'arrivée, traversé ou tombé
robtom2 <- function(){
x <- 0 ; y <- 0 ; urne <- c(-1, 0, 1)
while (y >= -1 & y <= 1 & x <= 9) {
n <- sample(urne, 1)
y <- y + n
x <- x + 1
}
# Affichage des résultats
if (y == -2 | y == 2) {
cat("TOM est tombé dans l'eau\n")
cat("La dernière position de TOM est : A(",
x, ",", y, ")\n\n")
} else {
cat("TOM a réussi la traversée du pont\n")
cat("La dernière position de TOM sur le pont : A(",
x, ",", y, ")\n\n")
}
}
#--------------------------------
# REPRÉSENTATION GRAPHIQUE DE LA MARCHE DE TOM
robtom3 <- function(){
x <- 0 ; y <- 0 ; urne <- c(-1, 0, 1)
suiteX <- 0 ; suiteY <- 0
while (y >= -1 & y <= 1 & x <= 9) {
n <- sample(urne, 1)
y <- y + n
x <- x + 1
suiteX <- c(suiteX, x) ; suiteY <- c(suiteY, y)
}
# print(suiteX) ; print(suiteY)
# Représentation graphique du cheminement
plot(c(0, 10), c(1, -1), type = "n",
main = "Cheminement de TOM",
xlab = "", ylab = "",
xaxp = c(0, 10, 10), yaxp = c(-1, 1, 2))
lines(suiteX, suiteY, type = "o", pch = 19, col = "orange", lwd = 2)
abline(h = c(-1, 1), lwd = 2)
grid(col = "grey50")
if (y == 2 | y == -2) {
text(suiteX[x], suiteY[x], pos = 2, labels = "PLOUF",
col = "blue", cex = 2)
} else {
text(suiteX[11], suiteY[11], pos = 2, labels = "TRAVERSE",
col = "orange", cex = 2)
}
}
#---------------------------------
# DE LA SIMULATION D'UNE MARCHE ALÉATOIRE AU CALCUL D'UNE ESTIMATION
# DE LA PROBABILITÉ DE TRAVERSER LE PONT EN SIMULANT nbsim MARCHES ALÉATOIRES
robtom4 <- function(nbsim = 2000){
urne <- c(-1, 0, 1)
statPont <- 0 ; statY <- NULL ; statX <- NULL
for (k in 1:nbsim) {
x <- 0 ; y <- 0
suiteX <- 0 ; suiteY <- 0
while (y >= -1 & y <= 1 & x <= 9) {
n <- sample(urne, 1)
y <- y + n
x <- x + 1
suiteX <- c(suiteX, x) ; suiteY <- c(suiteY, y)
}
# Pont <- ((x == 10 & y == -1) | (x == 10 & y == 1) | (x == 10 & y == 0))
Pont <- (y != -2 & y != 2)
statPont <- statPont + Pont
statX <- c(statX, x) ; statY <- c(statY, y)
}
PCPont <- statPont / nbsim
# Affichage des résultats et des graphiques
cat("Une estimation de la probabilité de passer le pont :", PCPont, "\n\n")
# Représentation graphique des distributions des séries
# simulées des abscisses et des ordonnées des positions
# de la fin de la marche du robot sur le pont.
plot(table(statX) / nbsim,
main = "Distribution des abscisses d'arrivée", lwd = 3)
grid(col = "grey50")
plot(table(statY) / nbsim,
main = "Distribution des ordonnées d'arrivée", lwd = 3)
grid(col = "grey50")
# Représentation graphique du dernier cheminement
plot(c(0, 10), c(1, -1), type = "n",
main = "Dernière simulation du cheminement de TOM",
xlab = "", ylab = "",
xaxp = c(0, 10, 10), yaxp = c(-1, 1, 2))
lines(suiteX, suiteY, type = "o", pch = 19, col = "orange", lwd = 2)
abline(h = c(-1, 1), lwd = 2)
grid(col = "grey50")
if (y == 2 | y == -2) {
text(suiteX[x], suiteY[x], pos = 2, labels = "PLOUF",
col = "blue", cex = 2)
} else {
text(suiteX[11], suiteY[11], pos = 2, labels = "TRAVERSE",
col = "orange", cex = 2)
}
}

Télécharger

L’exercice 4 du sujet 2013 de septembre d’Antilles-Guyane propose un
algorithme de simulation d’une marche aléatoire. Alors que l’énoncé
précise : “L’objectif de cet exercice est d’estimer la probabilité p
de l’événement S [le robot] Tom traverse le pont”, on constate que ni
l’algorithme de la partie A, ni le calcul de la partie B, basé sur des
suites numériques, ne proposent une estimation de cette probabilité. La
partie A propose la simulation d’une marche aléatoire, et la partie B
permet de trouver une valeur approchée de cette probabilité.
Dans ce document, je propose (Tableau 1) la traduction en langage R de
l’algorithme de l’énoncé, et d’un algorithme répondant à la question
A.2. Je propose ensuite (Tableau 2) un prolongement permettant une
représentation graphique du trajet du robot, un prolongement (Tableau 3)
permettant de calculer une estimation de la probabilité de S.
Je présente enfin (tableau 4) un algorithme simulant les résultats des
N élèves d’une classe, et illustrant la loi des grands nombres par une
juxtaposition de diagrammes en boites et un nuage de points.

l’article au format pdf	le source complet en l’R	le source de l’estimation

Dans le même numéro