Adhérer ou faire un don

L’algorithmique en seconde : un exemple de mise en oeuvre dans la classe.

Daniel Vagost

Daniel Vagost [1]

1. Introduction

En 1980, au début de ma carrière, j’ai fait l’acquisition d’un livre édité chez CEDIC : « Mathématique élémentaire d’un point de vue algorithmique » de A. Engel (adapté en français par D. Reisz). Dans la préface datant de janvier 1977, l’auteur écrit : « Les développements récents des ordinateurs et des calculatrices électroniques de poche amèneront, à brève échéance, une nouvelle évolution dont l’idée directrice consistera à souligner le caractère algorithmique des mathématiques. La notion d’algorithmique deviendra fondamentale dans l’enseignement et il nous faut repenser l’ensemble des mathématiques scolaires d’un point de vue algorithmique ».

Plus de trente ans plus tard nous trouvons (enfin ?) dans les nouveaux programmes de seconde qui font une place à un enseignement de l’algorithmique ces quelques phrases : « La démarche algorithmique est, depuis les origines, une composante essentielle de l’activité mathématique. […] Ce qui est proposé dans le programme est une formalisation en langage naturel propre à donner lieu à traduction sur une calculatrice ou à l’aide d’un logiciel. […] Les élèves, dans le cadre d’une résolution de problèmes, seront entraînés à en réaliser quelques-uns à l’aide d’un tableur ou d’un petit programme réalisé sur une calculatrice ou avec un logiciel adapté. »

Voilà trente ans que l’enseignant que je suis, que ce soit au lycée, à l’IUT, ou en formation initiale ou continue, essaye d’être un vecteur de cette idée exprimée par D. Reisz, dans l’introduction de l’édition française du livre cité précédemment : « … donner la priorité aux processus algorithmiques et à travers eux à une mathématique plus active, plus vécue : faire des mathématiques et non en contempler ».

L’objet de cet article est de vous présenter un exercice illustrant, dans le cadre des programmes de seconde, cette démarche et vous donner envie d’y plonger, vous aussi, pour le plus grand profit de la formation mathématique de nos élèves.

L’exercice : n chasseurs d’élite (ils ne ratent jamais leur cible) tirent « au hasard » simultanément sur n canards. Combien de canards sont-ils survivants après ces tirs ?

Il est bien sûr possible d’écrire cet exercice sous sa forme mathématique : « Soient $X_{1}$, $X_{2}$, …, $X_{n}$ n variables aléatoires indépendantes identiquement distribuées selon la loi uniforme sur $\{1,2,3, ...,n\}$.

On définit alors la variable aléatoire X, qui à chaque réalisation ($x_{1}$, $x_{2}$, …, $x_{n}$) de ($X_{1}$, $X_{2}$, …, $X_{n}$) associe le nombre d’entiers de $\{1,2,3, ...,n\}$. non présents dans ($x_{1}$, $x_{2}$, …, $x_{n}$). Quelle est l’espérance de X ? … et pourquoi pas « Donner la distribution de X. »

Nous laissons le soin au lecteur intéressé de vérifier qu’il n’est pas aisé de trouver la loi de X, mais que calculer E(X) n’est pas vraiment difficile.

Calcul de E(X) :
- le canard n° i est survivant si chacun des n chasseurs choisit un autre que lui ;
- la probabilité que le chasseur numéro 1 choisisse un autre canard que le numéro i est p avec p = (n − 1)/n ;
- les choix des n chasseurs sont indépendants les uns des autres, la probabilité que le canard numéro i soit vivant après les tirs est donc : $p^{n}$ ;
- or il y a n canards, E(X) est donc égal à :$ {n} p^{n}$ , soit $\frac{(n -1)^{n}}{n^{n-1}}$.

Ce que nous proposons de mettre en œuvre, ici, est la résolution de cet exercice par simulation. Simuler c’est « faire comme si »… La simulation est un outil puissant pour résoudre des problèmes que nous ne savons pas résoudre analytiquement.

Personnellement j’aime bien présenter aux élèves des exercices qu’ils ne savent pas résoudre autrement, peu importe la raison : il est possible qu’il leur manque encore des connaissances qu’ils vont acquérir plus tard, il est possible que le problème requiert des compétences qu’ils n’auront jamais, il est possible que personne ne sache encore résoudre le problème autrement que par simulation, …

Il est bien évident que la simulation ne doit pas paraître comme un outil magique ; il est nécessaire, pour cela, de proposer aux élèves la résolution par simulation de quelques problèmes qu’ils savent aussi résoudre autrement, afin de confronter les solutions obtenues.

2. Mise en œuvre en classe

Alors comment peut-on aborder cet exercice en classe de seconde ? Ce que nous proposons ici peut aisément se dérouler en une séance d’une heure. L’énoncé donné aux élèves est exactement celui qui est dans l’introduction : n chasseurs d’élite (ils ne ratent jamais leur cible) tirent « au hasard » simultanément sur n canards. Combien de canards sont-ils survivants après ces tirs ?

2.1. Mise en œuvre « manuelle »

Pour des raisons pratiques il peut être intéressant d’utiliser n = 4.
- Mettre les élèves par quatre (c’est pratique et dans une classe de trente-deux cela fait huit groupes !) ; chaque élève a devant lui quatre papiers numérotés 1, 2, 3, 4, numéros invisibles.
- Au signal chaque élève retourne un des papiers « au hasard » : on a alors la liste des canards tués, il suffit de noter le nombre de canards survivants.
- Recommencer une vingtaine de fois : on obtient ainsi une liste de plus de cent nombres représentant le nombre de canards survivants à une centaine de campagnes de tirs ; on peut alors étudier cette série et en particulier le nombre moyen … et comparer alors cette moyenne à 1,266 (valeur approchée de 34/43).

2.2. Mise en œuvre sur une calculatrice

Ici il n’est plus utile de prendre n = 4 ; on peut commencer avec n = 10, puis modifier éventuellement l’algorithme en ajoutant la possibilité de choisir le nombre de canards au départ. L’algorithme Cet algorithme nécessite deux itérations à nombre d’itérations donné, imbriquées. On obtient ainsi une série de N nombres que l’on peut étudier pour avoir une idée de la distribution ; on peut, en particulier, calculer le nombre moyen de canards survivants par partie et le comparer à 3,487 (valeur approchée de 10 × $0,9^{10}$).
Remarque : avec les élèves il peut être intéressant de dérouler cet algorithme « à la main » avant de l’exécuter sur une calculatrice (ou sur un logiciel).
Traduction sur TI 84
L’auteur a utilisé une TI 84, mais il est bien évidemment possible de le traduire sur toute autre calculatrice.
Les deux premiers écrans donnent le programme, traduction de l’algorithme précédent : le seul ajout est la deuxième ligne du programme (ClrList L1, L2) qui réinitialise les deux listes utilisées pour stocker les résultats : L1 est l’ensemble des 10 canards (il était possible de ne pas l’initialiser ici, vu qu’à chaque campagne de tirs on « lâche » dix nouveaux canards vivants) et L2 est la liste dans laquelle on range le nombre de canards survivants (L2(I) est le nombre de canards survivants après la Ième campagne de tirs).
Commentaire : le fait de mettre les canards à 1 avant les tirs et de mettre à 0 les canards tués fait que le nombre de canards survivants s’obtient simplement avec la somme de L1.
Il ne reste plus qu’à exécuter ce programme : ce que nous avons fait deux fois (écran 3) ; nous avons obtenu 3,65 et 3,47. Dans une classe de trente-deux élèves on obtient ainsi trente-deux valeurs… Il est facile de les comparer entre elles et aussi à 3,487...
L’auteur a analysé la série obtenue lors de la dernière exécution du programme (celle ayant abouti à la moyenne 3,47) ; cette étude est illustrée par les deux écrans 4 et 5 : on peut voir que le mode est 4 cibles intactes avec une fréquence de 0,36... Les résultats sont donnés dans le tableau suivant (le lecteur curieux pourra vérifier que ces valeurs observées ne sont pas trop éloignées des valeurs théoriques !).

Nombre de cibles intactes 0 1 2 3 4 5 6 7 8 9
effectif 0 1 17 32 36 12 6 0 0 0 100
Remarque : il est possible de modifier l’algorithme, puis le programme, en demandant, outre le nombre de parties, le nombre de canards … et du coup voir l’évolution de E(X) selon le nombre de canards.

2.3. Et sur tableur ?

Il est possible, pour aller plus loin (ou pour inciter les élèves à utiliser un tableur) de proposer la simulation en utilisant un tableur (en devoir maison par exemple ?) : la traduction « littérale » est plus difficile mais la mise en œuvre ne l’est pas.
Les deux tableaux ci-dessous montrent un exemple de mise en œuvre effectuée par l’auteur lors d’un TP avec des étudiants de première année de DUT. Commentaires :
- il est possible d’utiliser ALEA.ENTRE.BORNES(1 ; N) à la place de ENT (N*ALEA()) ;
- dans la colonne C, NB.SI (plage ; Ai) permet de dénombrer le nombre de fois où le canard dont le numéro est dans la cellule Ai, est touché ;
- la formule de la cellule C11 permet de dénombrer le nombre de canards survivants (ceux qui ne sont touchés par aucun chasseur) : il y a dans notre simulation quatre canards survivants...
- Il ne reste plus qu’à répéter de « nombreuses » fois...

3. Conclusion

Utilisé dans différentes conditions cet exemple a toujours suscité beaucoup d’intérêt : la possibilité de mixer les mises en œuvre accentue la motivation. De plus la possibilité de traduire simplement cet algorithme sur une calculatrice (et donc de n’avoir pas à utiliser un déplacement en salle informatique) permet la mise en œuvre dans des délais permettant de résoudre un exercice de bout en bout lors d’une seule séance. La possibilité d’obtenir un résultat à partir d’une simulation, somme toute assez simple, permet d’en montrer l’intérêt. De plus, conformément au programme de seconde voilà un bon point de départ pour étudier une série statistique, et donc d’avoir, au final, fait des mathématiques.

Petite bibliographie :

Histoire d’algorithmes, Collectif, Belin.
"Mathématique élémentaire d’un point de vue algorithmique" (Collection Formation des maîtres en mathématiques Éditions Cédic) de Arthur Engel et Daniel Reisz
et dans la même collection et du même auteur : «  L’enseignement des probabilités et de la statistique » réédité chez ALEAS Éditeur sous le titre « Les certitudes du hasard »

Quelques sites :

Il y a bien sûr de nombreuses choses sur les sites des IREM et de nombreux liens vers des sites intéressants sur le site de l’APMEP

- un site intéressant pour la mise en œuvre d’algorithmes sur calculatrices

- un cours d’algorithmique tout à fait intéressant

- la revue Mathematice, bien connue des lecteurs du bulletin, dont un numéroest entièrement consacré à l’algorithmique.

- nombreux exemples d’activités faites par des collègues dans leurs classes.


[1] IUT de Metz, département STID. vagost@univ-metz.fr