Les nouvelles technologies pour l’enseignement des mathématiques
Intégration des TICE dans l’enseignement des mathématiques

MathémaTICE, première revue en ligne destinée à promouvoir les TICE à travers 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 an bn cn
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)

  1. #*****************************************************
  2. # ROBOT TOM
  3. # ANTILLES GUYANE Septembre 2013
  4. # L'algorithme de l'énoncé, exercice 4-1.
  5. robtom1 <- function(){
  6.         x <- 0 ; y <- 0 ; urne <- c(-1, 0, 1)
  7.         while (y >= -1 & y <= 1 & x <= 9) {
  8.                 n <- sample(urne, 1)
  9.                 y <- y + n
  10.                 x <- x + 1
  11.         }
  12. # Affichage des résultats
  13.         cat("La dernière position de TOM sur le pont : A(",
  14.                  x, ",", y, ")\n\n")
  15. }
  16.  
  17. #-----------------------------
  18. # Exercice 4-2. Qualification de l'arrivée, traversé ou tombé
  19. robtom2 <- function(){
  20.         x <- 0 ; y <- 0 ; urne <- c(-1, 0, 1)
  21.         while (y >= -1 & y <= 1 & x <= 9) {
  22.                 n <- sample(urne, 1)
  23.                 y <- y + n
  24.                 x <- x + 1
  25.         }
  26.         # Affichage des résultats
  27.         if (y == -2 | y == 2) {
  28.                 cat("TOM est tombé dans l'eau\n")
  29.                 cat("La dernière position de TOM est : A(",
  30.                          x, ",", y, ")\n\n")
  31.         } else {
  32.                 cat("TOM a réussi la traversée du pont\n")
  33.                 cat("La dernière position de TOM sur le pont : A(",
  34.                          x, ",", y, ")\n\n")
  35.         }
  36. }
  37.  
  38. #--------------------------------
  39. # REPRÉSENTATION GRAPHIQUE DE LA MARCHE DE TOM
  40. robtom3 <- function(){
  41.         x <- 0 ; y <- 0 ; urne <- c(-1, 0, 1)
  42.         suiteX <- 0 ; suiteY <- 0
  43.         while (y >= -1 & y <= 1 & x <= 9) {
  44.                 n <- sample(urne, 1)
  45.                 y <- y + n
  46.                 x <- x + 1
  47.                 suiteX <- c(suiteX, x) ; suiteY <- c(suiteY, y)
  48.         }
  49. # print(suiteX) ; print(suiteY)
  50. # Représentation graphique du cheminement
  51.         plot(c(0, 10), c(1, -1), type = "n",
  52.                    main = "Cheminement de TOM",
  53.                    xlab = "", ylab = "",
  54.                    xaxp = c(0, 10, 10), yaxp = c(-1, 1, 2))
  55.            lines(suiteX, suiteY, type = "o", pch = 19, col = "orange", lwd = 2)
  56.            abline(h = c(-1, 1), lwd = 2)
  57.            grid(col = "grey50")
  58.            if (y == 2 | y == -2) {
  59.                    text(suiteX[x], suiteY[x], pos = 2, labels = "PLOUF",
  60.                            col = "blue", cex = 2)
  61.            } else {
  62.                    text(suiteX[11], suiteY[11], pos = 2, labels = "TRAVERSE",
  63.                            col = "orange", cex = 2)
  64.            }
  65. }
  66.  
  67. #---------------------------------
  68. # DE LA SIMULATION D'UNE MARCHE ALÉATOIRE AU CALCUL D'UNE ESTIMATION
  69. # DE LA PROBABILITÉ DE TRAVERSER LE PONT EN SIMULANT nbsim MARCHES ALÉATOIRES
  70. robtom4 <- function(nbsim = 2000){
  71.         urne <- c(-1, 0, 1)
  72.         statPont <- 0 ; statY <- NULL ; statX <- NULL
  73.         for (k in 1:nbsim) {
  74.                 x <- 0 ; y <- 0
  75.                 suiteX <- 0 ; suiteY <- 0
  76.                 while (y >= -1 & y <= 1 & x <= 9) {
  77.                         n <- sample(urne, 1)
  78.                         y <- y + n
  79.                         x <- x + 1
  80.                         suiteX <- c(suiteX, x) ; suiteY <- c(suiteY, y)
  81.                 }
  82.                 # Pont <- ((x == 10 & y == -1) | (x == 10 & y == 1) | (x == 10 & y == 0))
  83.                 Pont <- (y != -2 & y != 2)
  84.                 statPont <- statPont + Pont
  85.                 statX <- c(statX, x) ; statY <- c(statY, y)
  86.         }
  87.         PCPont <- statPont / nbsim
  88. # Affichage des résultats et des graphiques
  89.    cat("Une estimation de la probabilité de passer le pont :", PCPont, "\n\n")
  90. # Représentation graphique des distributions des séries
  91. # simulées des abscisses et des ordonnées des positions
  92. # de la fin de la marche du robot sur le pont.
  93.         plot(table(statX) / nbsim,
  94.                    main = "Distribution des abscisses d'arrivée", lwd = 3)
  95.            grid(col = "grey50")
  96.         plot(table(statY) / nbsim,
  97.                    main = "Distribution des ordonnées d'arrivée", lwd = 3)
  98.            grid(col = "grey50")
  99. # Représentation graphique du dernier cheminement
  100.         plot(c(0, 10), c(1, -1), type = "n",
  101.                    main = "Dernière simulation du cheminement de TOM",
  102.                    xlab = "", ylab = "",
  103.                    xaxp = c(0, 10, 10), yaxp = c(-1, 1, 2))
  104.            lines(suiteX, suiteY, type = "o", pch = 19, col = "orange", lwd = 2)
  105.            abline(h = c(-1, 1), lwd = 2)
  106.            grid(col = "grey50")
  107.            if (y == 2 | y == -2) {
  108.                    text(suiteX[x], suiteY[x], pos = 2, labels = "PLOUF",
  109.                            col = "blue", cex = 2)
  110.            } else {
  111.                    text(suiteX[11], suiteY[11], pos = 2, labels = "TRAVERSE",
  112.                            col = "orange", cex = 2)
  113.            }
  114. }

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

Innumérisme et chômage sont-ils liés ? (1/2)
le 10 mars 2014
par Michel Vigier
L’explosion continue… en classe
le 4 mars 2014
par Claudie Asselain-Missenard ,
Pierre Pansu
Approche d’une homothétie à l’aide de Geogebra
le 19 février 2014
par Hédi Abderrahim
Prise en main de CaRMetal (1/2)
le 13 février 2014
par Alain Busser ,
Patrice Debrabant
Géométrie algébrique plane avec GeoGebra
le 12 février 2014
par Alain Busser