Mathématice, intégration des Tice dans l'enseignement des mathématiques  
Sommaire > N°35 - mai 2013 > Un algorithme, un jeu d’enfant !

Un algorithme, un jeu d’enfant !
Moteur de recherche
Mis en ligne le 5 mai 2013, par Florent Girod

Pour rendre possible l’ouverture du fichier CaRMetal en ligne, il faut accepter d’exécuter l’application MAIN (cocher, puis exécuter).

Mots-Clés de l’article : algorithme, accompagnement personnalisé, statistique, histogramme, loi à densité, modélisation, simulation

Cet article résume un travail du groupe Probabilités-Statistiques de l’IREM de Grenoble [1] réalisé pendant l’année scolaire 2012/2013.


Introduction



Présentation de l’activité

Voici le questionnement de départ : lors du jeu du verger (jeu pour enfants édité par Haba dont la règle est détaillée ci-dessous), qui a la situation la plus favorable : les joueurs ou le corbeau ? Par ailleurs, la partie dure-t-elle comme indiqué sur la boîte entre 10 et 15 minutes, durée conseillée pour des enfants de 3 à 6 ans ?

Ce travail a été réalisé sur une période de 6 semaines, pendant l’heure d’APe (Accompagnement Personnalisé) dit "d’approfondissement" en classe de Terminale S, avec un petit groupe d’élèves. Des ordinateurs sont évidemment nécessaires ; l’algorithme a été réalisé sous le logiciel CaRMetal.

CarMetal - 33.7 ko
simulation du jeu sous CaRMetal

règle du jeu

Le jeu du verger est un jeu coopératif (dans la mesure où les joueurs jouent ensemble contre un "ennemi" commun : le corbeau).

Le verger est constitué de 4 arbres (prunier, cerisier, pommier et poirier) qui comptent 10 fruits chacun. La mission des joueurs est de récolter les fruits de ce verger dans leurs paniers.

Mais un corbeau rôde dans les parages. Il lui faut 9 coups pour atteindre le verger et manger les fruits, avant que les joueurs aient pu mettre tous les fruits dans leurs paniers.

Pour réguler le jeu : un dé à 6 faces, composé de la manière suivante :

  • une face bleue pour désigner une prune ;
  • une face rouge pour désigner une paire de cerises ;
  • une face verte pour désigner une pomme ;
  • une face jaune pour désigner une poire ;
  • une face panier : le joueur prend 2 fruits au choix ;
  • une face corbeau : on place une pièce du puzzle du corbeau (ou le corbeau avance d’une case selon la présentation du jeu).

Comment modéliser le jeu et dans quel cadre ?

Modéliser le dé est usuel ; il faut ensuite modéliser la stratégie utilisée par les joueurs lorsque "panier" sort : prendre ses deux fruits préférés (ce que fait un petit enfant), les fruits qui sont en plus grand nombre ? D’autres stratégies ?

Le cadre probabiliste répond à la problématique mais sous quelle forme ? Si on appelle X la variable aléatoire égale au nombre de coups joués en une partie (ce nombre de coups joués donnera la durée de la partie, en supposant par exemple que l’on joue 3 coups par minutes), X peut prendre les valeurs 9, 10, 11, ... jusqu’à l’infini ! Un arbre n’est donc pas envisageable puisqu’il devient vite "très grand", avec certaines branches "infinies".

L’algorithme apparaît comme l’outil adéquat pour simuler le jeu puisqu’il paraît très difficile (voire impossible) de donner la loi de probabilité de X par la théorie.

Reste à mettre en place cet algorithme ! D’une part, il faut l’écrire, et d’autre part, le mettre en œuvre. Le logiciel utilisé est CaRMetal ; c’est à la base un logiciel de géométrie, doublé d’une interface de programmation en JavaScript. Ce choix est guidé par la fait que ce logiciel est utilisé en classe en tant que logiciel de géométrie dynamique : il est donc connu des élèves.

L’activité inscrite dans la progression annuelle

Des algorithmes ont été mis en place depuis la classe de Seconde, mais cette pratique reste délicate - du moins dans cette classe.

Des difficultés techniques, mais aussi des problèmes de "motivation" : à quoi sert un algorithme ?

Des exemples d’algorithmes menés en classe de Terminale au cours du premier trimestre :

  • pour déterminer les valeurs d’une suite numérique ;
  • pour approcher une limite d’une suite numérique ;
  • pour déterminer un intervalle de fluctuation au seuil de 95%.

Dans les manuels

On peut voir différents types de travaux sur les algorithmes dans les manuels :

  • une situation est proposée, puis un algorithme ; on demande alors de faire le lien entre les deux ;
  • une situation est proposée, un algorithme en lien est à compléter ou à modifier ;
  • un algorithme est proposé et on demande son rôle.

Il est souvent demandé de donner les valeurs des variables apparaissant dans l’algorithme (pour un nombre raisonnable d’étapes).

Certains algorithmes ont pour objectif essentiel d’illustrer un aspect technique : condition, boucle ...

On trouve peu de situations donnant une motivation explicite de la mise en place d’un algorithme.


La situation

Questions posées aux élèves, une fois le jeu présenté (et testé !) :

  • qui a la situation la plus favorable : les joueurs ou le corbeau ?
  • quelle est la durée moyenne d’une partie ?
  • l’indication de durée (10-15 minutes) indiquée sur la boîte du jeu est-elle "fiable" ?

Déroulement

Après une discussion avec les élèves sur la méthode à mettre en place (l’algorithme est apparu comme le plus adapté, pour simuler un grand nombre de parties), une fiche guide leur a été distribuée, dans le but de les rendre le plus autonome possible pour la partie "technique" lors de l’écriture de l’algorithme.

PDF - 271.7 ko
fiche élèves

séance n°1 : présentation des deux activités d’APe

pour le jeu du verger, test du jeu en "réel" et en "virtuel" par le fichier CaRMetal présenté plus haut (sous l’image du jeu).


séance n°2 : prise en compte des quatre couleurs du dé

un premier algorithme pour modéliser et simuler le jeu en ne tenant compte que des quatre couleurs du dé sur une partie.


séance n°3 : prise en compte du corbeau

le premier algorithme est enrichi pour modéliser et simuler le jeu en incorporant le corbeau ; il faut désigner le vainqueur.


séance n°4 : prise en compte du panier

un nouvel algorithme est mis en place pour modéliser la face "panier" du jeu ; il faut choisir une stratégie : celle d’un petit enfant qui choisirait son fruit préféré, celui d’un plus grand qui retirerait les fruits les plus nombreux (plus exactement, de manière proportionnel au nombre de fruits restant pour chaque arbre) ; ces deux stratégies - une pour chaque groupe - ont été mises en place.


séance n°5 : algorithme complet pour une partie et plusieurs parties

la partie "panier" est incorporée à l’algorithme précédent. Un autre est construit pour simuler de nombreuses parties.


séance n°6 : exploitation des résultats pour répondre aux questions de départ

utilisation du tableur : un tri à plat des résultats (nombre de coups) est réalisé à l’aide d’un tableau dynamique croisé. On visualise ensuite ces informations par un graphique qui donne la répartition du nombre de coups. On peut répondre ensuite aux questions de départ, et comparer l’influence de chaque stratégie sur le nombre de coups, la probabilité de victoire des joueurs.



Commentaires

Travail des élèves

  • les algorithmes (sous CaRMetal)
CarMetal - 2.8 ko
CarMetal - 1.3 ko
stratégie "petit enfant"
stratégie plus élaborée
  • l’exploitation sur Tableur :
Excel - 3.1 Mo
stratégie "petit enfant" et stratégie plus élaborée

Ici quelques algorithmes évolutifs employant les deux stratégies définies au cours de l’activité :

CarMetal - 8.3 ko
documents "prof"

Intérêt des élèves

Lors de la conception de l’activité, nous avions un doute : les élèves seraient-ils intéressés par un jeu d’enfant ... et bien pas d’inquiétude, les élèves de Terminale ont su garder un certain côté "enfantin" ... et ils se sont pris au jeu sans problème.

Les questions proposées sont venues d’elles-mêmes, et l’utilisation d’un algorithme s’est imposée naturellement.


Un algorithme "élaboré"

Au final, l’algorithme est relativement complexe. Il a été amené en plusieurs étapes, avec une méthode bien établie :

  1. réflexion sur papier ;
  2. écriture de l’algorithme ;
  3. test étape par étape par visualisation des valeurs des variables ;
  4. réaction : validation ou ajustement suivant le résultat du test ;
  5. passage à la suite.

Le passage « de l’écrit au langage » s’est fait de plus en plus rapidement et efficacement au fur et à mesure des séances. Les élèves n’avaient au départ aucune expérience avec le langage JavaScript.


Utilisation des données

L’exploitation des données n’a posé aucune difficulté : une fois le tri à plat réalisé, des réponses satisfaisantes ont été données.

Des comparaisons entre les deux stratégies ont été faites et commentées : la stratégie du petit enfant diminue la probabilité de victoire des joueurs et allonge la partie, ce qui paraît bien normal. Les simulations ont pu chiffrer ces différences.

Des prolongements qualitatifs ont été faits :

  • augmentation de la probabilité de victoire du corbeau en diminuant le nombre de pièces du puzzle le constituant ;
  • augmentation du nombre de fruits dans chaque arbre pour rendre le jeu plus équitable ;
  • changement de la règle : un seul fruit pris au choix lors du panier.

Les élèves ont remarqué un intérêt de l’algorithme, à savoir la possibilité de modifier des paramètres assez rapidement pour voir les effets de ces modifications. Ces modifications sont d’autant plus faciles à faire si elles ont été anticipées et prises en compte dès l’élaboration de l’algorithme.

Un commentaire d’élève

“J’ai bien apprécié cette approche un peu moins scolaire et intéressante avec le point de vue de l’algorithme et du logiciel. Le passage de l’écrit au langage était bien aussi. Personnellement, je pense que ce type d’activité est à poursuivre.”


Prolongement par des étudiants de STID Grenoble

Deux membres du groupe IREM à la base de cette activité enseignent à l’IUT STID à Grenoble (STID pour STatisitique et Informatique Décisionnelle).

Ils ont proposé à des étudiants de 2ème année cette activité comme support d’un projet tutoré. Ces étudiants sont allés évidemment plus loin que les élèves de Terminale, modélisant plusieurs stratégies et exploitant de manière plus poussée les résultats statistiques obtenus par les algorithmes. Ils ont notamment mis en évidence que pour chaque stratégie, 4000 simulations étaient suffisantes pour avoir une bonne approximation de la probabilité de victoire des joueurs.

Pour plus d’informations, voici le lien sur les affiches des projets tutorés des étudiants de STID, où vous trouverez prochainement le poster concernant ce projet "jeu du corbeau" : posters


Présentation de l’activité à d’autres élèves

Les élèves de Terminale et les étudiants de STID ont présenté ensemble leur travail à des lycéens dans le cadre de la "semaine des mathématiques".

D’une part, cela a permis à des élèves de 1ère S de voir "vivre" un algorithme mis en place par des élèves de Terminale, cela pouvant éventuellement donner du sens à des algorithmes qu’ils rencontreront par ailleurs. D’autre part, ils ont pu observer l’évolution de la qualité du travail entre des élèves de Terminale et des étudiants "post-bac" spécialisés en informatique et en statistiques.


Exploitation des résultats

Présentation de l’activité à la classe

Les élèves de Terminale ont également présenté leurs résultats au reste de la classe, ces données ayant servi de support comme introduction aux lois de probabilité à densité.

Comment présenter les résultats ?

On s’intéresse ici à la répartition du nombre de coups des parties simulées.

Les résultats (tri à plat) donnés, l’histogramme est apparu comme le graphique le plus adapté pour les représenter. Mais au cours de leur scolarité, les élèves ont rarement été confrontés à la mise en place d’un histogramme, sans qu’on leur donne les classes !

Il a fallu rappeler que c’est l’unité d’aire qui est proportionnelle à l’effectif représenté, et non l’ordonnée, à partir du moment où l’on choisit des classes de tailles différentes.

Un élève a proposé de faire des classes qui contiendraient le même nombre (de manière approximative) de données.

Les élèves ont construit " à la main" un histogramme ; ceux qui ont fait le choix évoqué précédemment on obtenu ceci :

Les deux histogrammes suivants ont été obtenus grâce au logiciel R [2] et ont été présentés aux élèves :

Du discret au continu

Si le problème posé est sur le principe "discret" (on cherche le nombre de coups joués pour une partie), on peut l’assimiler à un problème continu. En effet, la probabilité que deux parties aient le même nombre de coups est faible.

Il est d’ailleurs intéressant de se poser la question du type de problématique : est-ce un problème discret ou continu ? Une étude sur la taille d’un individu par exemple est par définition un problème continu, mais en ne gardant que des tailles arrondies au cm près, devient-il discret ?

En partant de l’histogramme, les élèves ont aisément admis que la probabilité d’appartenir à un intervalle était donné par l’aire des barres correspondantes. En augmentant le nombre de classes et en reliant les sommets des barres de l’histogramme, on forme une "courbe", et l’aire recherchée est assimilée à une aire sous la courbe.

Cette activité, par l’exploitation de ses résultats par le biais de l’histogramme et d’un "passage au continu" a donc permis d’introduire la notion de probabilité vue comme une aire sous la courbe, dans le cas d’une situation décrite par une fonction densité de probabilité.


Quelques dernières réflexions

Le principe utilisé pour déterminer des probabilités, la démarche fréquentiste prend vie au cours de cette activité. Cette démarche a été motivée par le fait qu’une approche "théorique" était impossible à mettre en œuvre. Le grand nombre de répétitions, même s’il n’est pas "proprement" défini, apporte une sorte de garantie aux résultats.

Par ailleurs, existe-t-il une loi "sous-jacente" à la règle du jeu ? Si c’est le cas, quelles en sont les caractéristiques ? Cette question pourra être posée lors de l’étude des lois de probabilités continues.

Enfin, des intervalles de fluctuation à des seuils inhabituels sont exploités : environ 80% des parties durent entre 10 et 15 minutes pour la stratégie n°2. Là encore, des notions vues de manière un peu "théoriques" prennent un sens concret car elles permettent de répondre à l’une des questions de départ : est-il raisonnable d’indiquer une durée de jeu de 10-15 mn sur la boîte du jeu ? On a grâce à cette étude une réponse chiffrée par les 80% cités précédemment, qui permet de donner une réponse objective.

Annexe : Un courrier d’Hubert Raymondaud

"J’ai trouvé très intéressante cette activité de modélisation et de simulation.

Je vais la proposer pour mes séances avec les terminales S.

Malgré une période assez chargée, je n’ai pas pu résister à la tentation de passer le jeu du Verger à la moulinette du logiciel R. On peut ainsi toucher du doigt les qualités de cet outil, que je trouve dommage de limiter à la simple réalisation des "histogrammes" pour une variable discrète.

L’exploitation graphique des résultats permet de bien mettre en évidence les différences entre les 3 protocoles : distributions simulées de la variable nombre de coups d’une partie (diagrammes en barres), et évolution du nombre des différents fruits et de l’avancée du corbeau.

PDF - 241.3 ko
Trois simulations avec R
R - 8.5 ko
Corbeau.R

Les deux premiers protocoles sont simples à mettre en oeuvre.

Par contre le panier complique sensiblement l’affaire, j’ai donc fait quelques hypothèses simplificatrices (dont un seul joueur, parmi d’autres plus discrètes)."


notes

[1ce groupe est composé de :

  • Alain Birebent, enseignant à l’Université Pierre Mendès France de Grenoble
  • Nathalie Catinot, professeur au Lycée de l’Albanais à Rumilly
  • Philippe Garat de l’IUT STID de Grenoble
  • Florent Girod, professeur à l’Externat Notre Dame à Grenoble
  • Damien Jacquemoud, professeur au Collège de Cluses
  • Frédérique Letué de l’IUT STID de Grenoble

[2R est un logiciel libre et gratuit avec de très nombreuses applications liées aux probabilité-statistiques

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...
À 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