TP 9 d’algorithmique avec CaRMetal en Seconde

lundi 10 mai 2010
par  Alain BUSSER

Le héros du jeu est un robot, qui avance après chaque lancer du dé, d’une unité, vers une des 4 directions cardinales. Le dé est en effet tétraédrique. Le but du jeu est de sortir du disque de rayon 4 centré sur sa position de départ.

Deux questions se posent alors :

  1. Est-on certain qu’il finira par gagner, ce pauvre robot ?
  2. Combien de temps la partie durera-t-elle ?

Avant le TP, l’animation en bas de page (lancer le script « jeu » ; on peut annuler les effets et recommencer autant de fois que l’on veut) a été projetée aux élèves, qui se sont immédiatement passionnés pour le sort de ce robot (par « chance », une des parties a été assez longue). Des explications ont été données sur

  • le tétraèdre, forme peu connue des élèves (la plupart ne savait pas combien de faces le dé possède), et des questions intéressantes ont été posées sur la lecture du résultat du lancer, le dé n’ayant pas de face de dessus ;
  • Le « switch..case » de JavaScript qui simplifie l’écriture du code (même avec seulement 4 faces) ;
  • les tableaux de JavaScript, sous la forme du corrigé d’un exercice sur les diagrammes en bâtons.
  • La définition du disque et le rappel des TPs sur les distances.

L’objet de ce TP est juste d’introduire l’autre sorte de boucle à condition de sortie :

  1. La boucle $while(b)$ tourne tant que $b$ est vraie. Donc si $b$ est fausse la boucle ne tourne jamais.
  2. Parfois on a besoin que la boucle soit effectuée au moins une fois, même si $b$ est fausse ; c’est l’analogue des boucles $until(\neg b)$ de Pascal (langage). En JavaScript, une telle boucle se rédige $do ... while(b)$. Dans le cas présent, on est certain que la boucle sera effectuée au moins 4 fois donc la distinction entre ces deux sortes de boucle ne présente pas d’intérêt pour cet exercice.

Le sujet du TP, au format pdf, est téléchargeable ici :

le sujet au format pdf

Une fois encore, les élèves se sont précipités pour copier le script au clavier, sans faire suffisamment attention à la syntaxe (oubli fréquent de points-virgule) et parfois sans lire le début de l’énoncé, qui demandait la construction du cercle !

Une fois le script entré, le spectacle de ce robot tentant parfois péniblement de sortir du cercle a été visiblement captivant pour les élèves [1] :

Lo tipwin y bouz...

Lo tipwin lé là...

Là n’a ganié !

erreurs de syntaxe

  • En écrivant « case3 » et « case4 » sans espace entre « case » et le chiffre, le robot ne se déplace que sur l’axe des abscisses (parfois pas du tout). Bien que l’erreur de syntaxe soit difficile à corriger (on ne voit pas bien l’espace manquant), la présence d’une erreur a été immédiatement perçue par l’élève.
  • Le remplacement du point-virgule par un double-point est une erreur de syntaxe signalée comme telle mais difficile à détecter, même en connaissant le numéro de la ligne.

erreurs d’algorithmique

  • Les x=0 et y=0 sont souvent restés au début, ce qui a donné des tableaux visiblement faux (le robot ne repart pas de l’origine au début de la partie)
  • r2[i]=x*x+y*y;

Ici, c’est le carré de la distance qui est stocké dans le tableau et non la durée de la partie.

animisme javascriptien

  • « C’est bien Pause(100) pour faire 100 parties ? » (en fait c’est une boucle « for » qu’il faut utiliser).
  • var n = nombre de lancers

(classique : JavaScript est si puissant qu’il doit bien y avoir une instruction donnant directement le nombre de lancers sans avoir à créer un algorithme pour cela)

Au bilan, il a fallu moins d’une demi-heure, débogage compris [2] pour entrer le script, mais la demi-heure suivante n’a pas été fructueuse. Cela s’explique par les points suivants :

  1. Le TP est difficile et long : Seules deux connaissances sont réinvesties, les tableaux et le comptage (vu dans le TP sur la méthode de Monte-Carlo)
  2. Le TP fait appel à l’usage de tableaux, hors programme et à juste titre. Il eût mieux valu ne demander que la liste des 100 parties avec leurs durées, sans regrouper ces durées dans le tableau. Cette liste a été fournie par deux élèves.
  3. La création d’une variable de comptage, initialisée à 0, puis incrémentée au fur et à mesure, n’est pas encore maîtrisée par les élèves de fin de Seconde.

Bribes de théorie

Le code Euler Math Toolbox ci-dessous

affiche la distribution des temps d’échappement sur 10 000 parties allant jusqu’à 1000 lancers de dés chacune (la 4ème valeur de « extrema(x) » est la première valeur de i pour laquelle x[i] est maximale, c’est-à-dire égale à 1). Voici la distribution affichée :

Une approximation infinitésimale de la marche aléatoire étant un mouvement brownien, la distance parcourue est modélisée par une loi de Rayleigh dont l’écart-type est fonction croissante du temps (proportionnel à sa racine carrée). Cela ne permet pas aisément de trouver la loi du temps mis à quitter le disque. Mais si le mouvement du robot est un processus de Poisson, la loi est exponentielle, ce qui est parfaitement compatible avec le graphique ci-dessus. Pour vérifier, on a superposé la loi exponentielle de paramètre 0,08 (donc d’espérance 12,5) à l’histogramme :

La moyenne donnée par Euler Math Toolbox est de 18,3 et la médiane 25,5 :

  • Il ne faut pratiquement jamais plus de 100 lancers de dés pour que le robot sorte du disque ;
  • Dans la moitié des cas, il faut moins de 36 lancers de dés ;
  • En moyenne, on doit lancer le dé environ 18 fois pour que le robot sorte du disque.

La répétition de l’expérience sur 10 000 échantillons confirme la stabilité de la moyenne, 18,2 ou 18,3 ; par contre la médiane fluctue beaucoup, parfois inférieure à la moyenne comme le prévoit le modèle exponentiel, parfois au contraire supérieure à celle-ci.

La démo en ligne :


[1On constate le pléonasme « le petit point » peut-être lié à la représentation circulaire des points sous CaRMetal, ou au fait que le fichier d’exemple a été projeté avec l’image d’un robot « réaliste » fait avec PovRay

[2et test compris, parfois on a du mal à croire que le robot sortira un jour, au point qu’une élève s’est mise à douter de son script, pensant qu’un bogue ramenait systématiquement le robot vers le centre


Commentaires

Logo de Alain BUSSER
dimanche 28 novembre 2010 à 11h24 - par  Alain BUSSER

Bien que le programme de Seconde parle d’algorithmique et pas de programmation, on y lit parmi les « objectifs pour le lycée » ces deux points (page 10) :

  • programmer un calcul itératif, le nombre d’itérations étant donné ;
  • programmer une instruction conditionnelle, un calcul itératif, avec une fin de boucle
    conditionnelle.

Qu’on veuille appeler la réalisation et le test de boucles à sortie conditionnelle, un algorithme ou un programme, ce genre de débat sur le vocabulaire ne change rien au fait que c’est au programme (actuellement de Seconde et Premières ES et S, sans oublier la présence de ce genre de boucles dans les sujets du Bac L), et que s’interdire de les traiter juste parce qu’on a vu le mot « algorithme », revient à s’interdire de traiter dans son intégralité le programme de Seconde...

L’idée de fabriquer un robot en cours de maths de Seconde me semble témoigner d’une ignorance des contenus horaires de la classe de Seconde. Même des patrons, activité enrichissante s’il en est, ne sont plus faits au collège, faute de temps, et ne le seront sans doute pas plus au lycée, pour la même raison.

Logo de marc Jambon
mercredi 24 novembre 2010 à 07h53 - par  marc Jambon

Il serait intéressant de fabriquer effectivement le dé tétraédrique dans le cadre de l’apprentissage de la géométrie dans l’espace et ensuite le robot. On sera alors en mesure de faire l’expérience sur le terrain. Clairement, il faudra au moins quatre coups de dé pour atteindre le bord du cercle mais, il se peut aussi qu’on ne l’atteigne jamais. Le programme que vous proposez est bien un programme, on pourrait même le qualifier de programme aléatoire ou plutôt pseudo-aléatoire, ce n’est pas un algorithme, voir « algorithmique et algorithme » sur Wikipédia par exemple.

http://fr.wikipedia.org/wiki/Algori...