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

Sommaire

1. Introduction
2. Mise en œuvre en classe
3. Conclusion
Petite bibliographie :
Quelques sites :

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 »