Mathématice, intégration des Tice dans l'enseignement des mathématiques  
Sommaire > N°39 - mars 2014 > Regards croisés sur l’algorithmique et la (...)
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)
Moteur de recherche
Mis en ligne le 15 février 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 ».

Retour au sommaire

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

Alain Busser, Guillaume Connan, Hubert Raymondaud, Pierre-Marc Mazat, Stéphan Manganelli Haut de page
notes

[1] sauf que les opérations de CmathOOoCAS sont préfixées et non infixées : Par exemple, au lieu de a+b, on fait csomme(a,b) ; ce qui mène à des parenthèses imbriquées.

Documents associés à l'article
     |   (PDF - 169.8 ko)
Télécharger le fichier
Réagir à cet article
Vous souhaitez compléter cet article pour un numéro futur, réagir à son contenu, demander des précisions à l'auteur ou au comité de rédaction...
Poster un message
À lire aussi ici
MathémaTICE est un projet
en collaboration avec
Suivre la vie du site Flux RSS 2.0  |  Espace de rédaction  |  Nous contacter  |  Site réalisé avec: SPIP  |  N° ISSN 2109-9197