Dans cet article, on se permettra d’appeler itérateur ce que les pythoniens appellent générateur, parce que leur syntaxe (celle des générateurs, pas celle des pythoniens) est plus courte. Comme les pythoniens sont très sympas, nul doute qu’ils pardonneront ce petit abus de langage.
Exemples
Dans cette partie de l’article on propose de voir certains itérateurs utiles en maths :
- des itérateurs généralisant range modélisant les suites arithmétiques
- suites géométriques
- une suite récurrente historique : table de sinus du 8e siècle
- une autre suite récurrente connue : Les lapins de Fibonacci (début 13e siècle)
- Le jeu de la soustraction, improprement appelé « de Nim »
- La recherche de succès au jeu des petits chevaux (loi géométrique de raison 1/6)
- Un générateur congruentiel linéaire de Lehmer pour simuler une variable aléatoire uniforme sur [0,1] (comme
randomde Python)
Suite arithmétique
Pour créer un itérateur qui modélise une suite arithmétique d’entiers, on peut faire
iter(range(premier_terme,fin_itération,raison))
Voici une manière de l’étendre à un itérateur similaire, parcourant les termes d’une suite arithmétique à termes non nécessairement entiers :
def floatrange(a,b,p=1.0):
x = float(a)
while x<float(b):
yield x
x += pLa fonction floatrange est un générateur : elle crée un itérateur [1], qui se comporte comme le ferait range. Par exemple le script suivant
for x in floatrange(0,1,0.1):
print(x)produit alors l’affichage suivant [2] :
0.0
0.1
0.2
0.30000000000000004
0.4
0.5
0.6
0.7
0.7999999999999999
0.8999999999999999
0.9999999999999999Une suite arithmétique consiste à toujours additionner un même nombre (ici, 0,1)
au terme courant pour avoir le terme suivant. L’arsenal des filtres numériques permet alors de dessiner une telle suite avec un diagramme de flux :
Le symbole dans le cadre est un retardateur, il transforme chaque terme de la suite en le terme précédent.
Suite géométrique
Et si on veut une suite géométrique, on peut faire pareil. Voici par exemple un extrait du sujet de bac ES Polynésie septembre 2018 :
Au 1er janvier 2018, madame DURAND dispose d’un capital de 16 000 €. Le 1er juillet de chaque année, elle prélève 15 % du capital disponible en prévision de ses vacances estivales.
On propose de modéliser le montant du capital non par une suite, mais par un itérateur de suite géométrique, de ce genre :
def geomrange(r,u,s):
while ((r>1 and u<s) or (r<1 and u>s)):
yield u
u *= rLa suite géométrique de l’énoncé a pour raison r=0,15, pour premier terme u=16000 et pour seuil (fin d’itération) s=2000 :
capital = geomrange(0.85,16000,2000)
for n in range(50):
print(n,next(capital))La réponse à l’exercice est donnée par la levée de l’exception « fin d’itération » :
0 16000
1 13600.0
2 11560.0
3 9826.0
4 8352.1
5 7099.285
6 6034.39225
7 5129.2334125
8 4359.848400625
9 3705.87114053125
10 3149.9904694515626
11 2677.4918990338283
12 2275.868114178754
Traceback (most recent call last):
print(n,next(capital))
StopIterationIl faut donc 13 ans pour que Madame Durand soit ruinée.
Il suffit alors de prendre un nombre supérieur à 12 pour que l’itération s’arrête au moment voulu. Ici on a essayé avec 50.
Le diagramme de flux d’une suite géométrique est assez similaire à celui d’une suite arithmétique, en injectant la raison :
Le symbole à gauche représente le premier terme, qu’on injecte une seule fois au début (c’est le rôle joué par le symbole de Kronecker, ici multiplié par 16000).
Noter qu’en omettant le « détail » du premier terme et en utilisant un atténuateur (produit par une constante), la suite géométrique devient l’une des plus faciles à dessiner :
Sinus
Un autre exemple est celui de la plus vieille table de sinus connue, que l’on peut représenter par cet itérateur :
def aryabhata():
n = 0
u = 0.0
S = 0
while n<25:
yield u/3440
n += 1
S += u
u += 225.0-S/225.0Il engendre les sinus (approchés) des multiples de 3°45’. Voici les résultats fournis :
Pour évaluer la précision, on peut représenter (en rouge) les sinus calculés par Python, en plus de ceux d’Aryabhata (en bleu) :
Enfin, voici la suite des erreurs d’approximation de cette table de sinus :
Jusqu’à 45°, l’erreur ne dépasse pas 0,003. Pas mauvais en trigo, les indiens !
La suite d’Aryabhata se dessine ainsi, en diagramme de flux :
Le symbole spécial dans le cadre désigne un filtre intégrateur : à une suite, il associe la somme de ses termes. On peut construire un tel outil avec cette recette :
lapins
Un autre exemple de suite à double récurrence est celle qu’a inventé Fibonacci, à propos de démographie chez les lapins. En représentant chaque lapin adulte par la lettre M (deux grandes oreilles) et chaque lapereau par la lettre m (deux petites oreilles), on peut modéliser la population des lapins par cet itérateur :
def clapier():
adultes = 1
jeunes = 1
while adultes < 1e6:
yield adultes*"M"+jeunes*"m"
adultes,jeunes = adultes+jeunes,adultesLa dernière ligne dit qu’à chaque itération, le nombre d’adultes augmente du nombre de jeunes (ils sont devenus adultes) et le nombre de jeunes est identique au nombre précédent d’adultes (chaque adulte donnant naissance à un jeune).
Pour voir à quoi ressemble, en ascii-art, la population de lapins, ce script suffit :
population = clapier()
for mois in range(8):
print(next(population))L’évolution est conforme à ce qu’on connaît sur la suite de Fibonacci :
Mm
MMm
MMMmm
MMMMMmmm
MMMMMMMMmmmmm
MMMMMMMMMMMMMmmmmmmmm
MMMMMMMMMMMMMMMMMMMMMmmmmmmmmmmmmm
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMmmmmmmmmmmmmmmmmmmmmmRemarque : Ici on a considéré que le modèle cesse d’être valide lorsqu’on dépasse le million d’adultes, mais en remplaçant la condition par True, l’itérateur peut boucler sans fin puisqu’on a une suite numérique (une infinité de nombres). On remarque qu’on n’a pas bouclé sur l’itérateur lui-même, mais sur un range, dans lequel on a appelé la fonction next : Pour chaque mois on a demandé quelle est la prochaine population. Dans le cas d’une suite infinie, écrire
for lapins in clapier():
print(lapins)ferait planter la machine Python. Mais on peut ajouter un test à la boucle pour extraire une sous-suite finie de cette suite infinie ; ainsi en extrayant les termes inférieurs à 20 de la suite de Fibonacci :
[lapins for lapins in population if len(lapins)<20]
on en trouve 5 :
['Mm', 'MMm', 'MMMmm', 'MMMMMmmm', 'MMMMMMMMmmmmm']
C’est ainsi que le langage haskell permet de manipuler des listes infinies (ce qui lui permet d’éviter les itérateurs).
Avez-vous déjà vu un filtre numérique calculant la suite de Fibonacci ? Le voici :
Nim
Un pion se déplaçant sur un graphe est aussi un itérateur. Comme les graphes sont un peu compliqués à représenter en Python, on va prendre le cas du jeu des allumettes (appelé à tort, « de Nim ») auquel le redoutable Père Fourasse soumet les candidats à Fort-Boyard.
L’itérateur suivant permet de jouer au jeu de Fort-Boyard :
def FortBoyard(N):
autre = { "A": "B", "B": "A"}
joueur = "A"
while N>0:
yield joueur + " hérite de " + N*"|"
k=int(input("Combien le joueur " + joueur + " veut-il enlever d'allumettes (1,2 ou 3) ? "))
N -= k
joueur = autre[joueur]Il nomme le joueur [3] (A ou B) qui doit enlever les allumettes, demande à ce joueur combien d’allumettes il veut enlever, et renvoie un dessin des allumettes l’une à côté de l’autre. Du coup pour jouer à Fort-Boyard avec 13 allumettes au départ il suffit de faire
for coup in FortBoyard(13):
print(coup)En regardant le déroulé du jeu, on constate que A a gagné puisque c’est le dernier à avoir joué :
A hérite de |||||||||||||
Combien le joueur A veut-il enlever d'allumettes (1,2 ou 3) ? 2
B hérite de |||||||||||
Combien le joueur B veut-il enlever d'allumettes (1,2 ou 3) ? 3
A hérite de ||||||||
Combien le joueur A veut-il enlever d'allumettes (1,2 ou 3) ? 1
B hérite de |||||||
Combien le joueur B veut-il enlever d'allumettes (1,2 ou 3) ? 2
A hérite de |||||
Combien le joueur A veut-il enlever d'allumettes (1,2 ou 3) ? 3
B hérite de ||
Combien le joueur B veut-il enlever d'allumettes (1,2 ou 3) ? 1
A hérite de |
Combien le joueur A veut-il enlever d'allumettes (1,2 ou 3) ? 1Dada
Blase Pascal a été le premier à s’intéresser au problème suivant : Combien de fois doit-on lancer un dé pour avoir un 6 ? Le nombre de lancers suit une loi géométrique de paramètre 1/6. La suite des résultats peut bien entendu s’obtenir avec un itérateur ad hoc :
def dada():
die = None
while die != 6:
yield die
die = randint(1,6)Le nom de l’itérateur vient de ce que l’obtention d’un 6 est nécessaire pour pouvoir commencer à jouer au jeu de dada. La variable interne de cet itérateur est appelée die qui signifie dé en anglais. On arrête d’itérer lorsque cette variable vaut 6. On continue donc à itérer tant que (« while ») le résultat est différent de 6.
Pour simuler une variable aléatoire géométrique de paramètre 1/6, on peut donc faire
nblancers = 0
for dé in dada():
nblancers += 1Après l’exécution de ce script, la variable nblancers (« nombre de lancers » du dé) contient une réalisation de cette variable aléatoire. Pour répéter plusieurs fois l’expérience et savoir combien de fois on a lancé le dé, on peut faire quelque chose comme ceci :
[len(list(dada())) for k in range(20)]
En effet en convertissant en une liste l’itérateur, la longueur de cette liste est exactement le nombre total de lancers. On obtient ce genre de résultat :
[2, 3, 5, 5, 10, 1, 1, 13, 3, 1, 3, 8, 6, 13, 10, 9, 1, 5, 3, 2]Lehmer
Voici comme Knuth propose de calculer des nombres pseudo-aléatoires entre 0 et 1 (algorithme décrit en Sofus :
On a besoin d’une variable entière appelée graine (seed en anglais) et on itère ainsi :
def alea(graine=1):
while graine>0:
graine *= 1664525
graine += 1013904223
graine %= 2**32
yield graine/2**32Pour simuler une variable aléatoire X suivant une loi uniforme sur [0,1], on peut faire
X = alea(123)
for n in range(8):
print(next(X))qui donne ce genre d’affichage :
0.2837369213812053
0.4351300236303359
0.03865125775337219
0.22087990469299257
0.3594270762987435
0.5902441388461739
0.361280900426209
0.3268499083351344Voici un extrait d’un document préparé pour le stage académique « algorithmique et programmation en 2nde » consacré à Python, où une partie décrit range comme un itérateur :
Ainsi, un itérateur peut être considéré comme une machine ayant plusieurs états possibles, et muni d’une méthode de changement d’état. C’est le cas notamment d’un pion sur un graphe, d’un ordinateur en train d’exécuter un programme, mais aussi d’une chaîne de Markov. Ce qui est l’occasion d’explorer cette notion et ses applications pédagogiques, en l’introduisant par un jeu :
Lièvre et tortue
Voici un célèbre jeu (source : document d’accompagnement de 2000) :
Le document d’accompagnement expliquait déjà, à l’époque, qu’il s’agit d’une chaîne de Markov, que voici dessinée avec Nirina974 :
Pour jouer, charger dans Nirina974 le fichier suivant :
Le sommet 5 correspond à la victoire de la tortue, et le sommet 6 à celle du lièvre.
En fait, les chances de gain de la tortue dépendent du nombre de pas N qu’elle a à effectuer. On propose alors cet itérateur dépendant de N (longueur du trajet) :
from random import *
def lt(N):
lp,tp = 0,0
while lp<N and tp<N:
die = randint(1,6)
if die==6:
lp += 6
else:
tp += 1
yield "Le dé est tombé sur {} ; Le lièvre est en {} et la tortue est en {}.".format(die,lp,tp)Les variables lt et tp désignent respectivement la position du lièvre et celle de la tortue.
Avec
for coup in lt(4):
print(coup)On a des rapports de ce genre :
Le dé est tombé sur 4 ; Le lièvre est en 0 et la tortue est en 1.
Le dé est tombé sur 4 ; Le lièvre est en 0 et la tortue est en 2.
Le dé est tombé sur 5 ; Le lièvre est en 0 et la tortue est en 3.
Le dé est tombé sur 6 ; Le lièvre est en 6 et la tortue est en 3.Genèse
Voici un graphe destiné à jouer à Nim dessus :
Il possède une stratégie gagnante pour le premier joueur (« A ») : Mener le pion à droite. Ensuite le jeu se fait tout seul et A gagne. Mais en constatant que le degré sortant de chaque sommet est un diviseur de 6, on peut en faire un graphe stochastique [4] en attribuant à chaque arête un poids égal à l’inverse du degré sortant de son origine. Puis comme les poids sont égaux à 1, 1/2 ou 1/3, en multipliant chacun d’entre eux par 6, on obtient pour chaque arête le nombre de faces du dé qui fait emprunter cette arête. Ce qui donne cette règle du jeu :
Chaque joueur à son tour lance le dé, puis regarde, parmi les arêtes issues de la position actuelle du pion, laquelle est marquée par le résultat du dé :
• Si le dé donne 1, le pion doit emprunter l’arête à côté de laquelle figure le symbole ⚀ ;
• Si le dé donne 2, le pion doit emprunter l’arête à côté de laquelle figure le symbole ⚁ ;
• Si le dé donne 3, le pion doit emprunter l’arête à côté de laquelle figure le symbole ⚂ ;
• Si le dé donne 4, le pion doit emprunter l’arête à côté de laquelle figure le symbole ⚃ ;
• Si le dé donne 5, le pion doit emprunter l’arête à côté de laquelle figure le symbole ⚄ ;
• Si le dé donne 6, le pion doit emprunter l’arête à côté de laquelle figure le symbole ⚅ ;
• Si l’arête ne comprend aucun symbole, le pion doit l’emprunter quel que soit le résultat du lancer de dé. Autant ne pas lancer le dé dans ce cas.Le joueur qui a lancé le dé (ou avancé automatiquement le pion) au moment où le pion est arrivé, gagne ce jeu.
Ce jeu est-il à l’avantage de A ou de B ?
Pour jouer, il suffit d’un pion (un seul pour les deux joueurs) et un dé, avec ce graphe :
Le logiciel Nirina974 est maintenant doté d’un simulateur de chaînes de Markov. On peut s’en servir pour créer le graphe et le pondérer :
Plus une arête est épaisse, et plus le pion a de chances de passer par cette arête [5].
Pour simuler une partie de ce jeu il suffit de cliquer sur « jouer ». Le pion est alors dessiné en noir sur la case de départ :
Un message apparaît également disant que c’est au joueur A de lancer le dé. En effet, A ne choisit pas si le pion doit aller au sommet 1, 2 ou 5, mais laisse le hasard en décider. En cliquant sur l’icône représentant un dé. Le jeu devient alors quelque chose comme ceci :
Le hasard a donc décidé que le pion aille sur le sommet 2 (au centre). Un message apparaît disant que cet évènement avait une probabilité 1/3 de se réaliser ; un autre message dit que c’est au tour du joueur B de lancer le dé. Et le dé lui est favorable en menant le pion au sommet 5 :
Le joueur A n’a alors pas d’autre choix que d’amener le pion au sommet 4 (quel que soit le résultat du lancer de dé) :
Et ensuite le joueur B lance le dé, et quelle qu’en soit l’issue, le pion va au sommet 3 et fait gagner B :
Décrite par l’itérateur, cette partie ressemble à ceci :
Le joueur A voit le pion sur le sommet 0
Le joueur B voit le pion sur le sommet 2
Le joueur A voit le pion sur le sommet 5
Le joueur B voit le pion sur le sommet 4La version itérateur donne ceci (le graphe est un tableau qui, pour chaque sommet, précise à quoi il est adjacent) :
from random import *
graphe = [[1,2,5],[2,3],[3,4,5],[3],[3],[4]]
autre = {"A": "B", "B": "A"}
def jeu(etat=0):
joueur = "A"
while etat != 3:
yield "Le joueur " + joueur + " voit le pion sur le sommet " + str(etat)
etat = choice(graphe[etat])
joueur = autre[joueur]
for coup in jeu(0):
print(coup)Théorie
Le graphe pondéré peut être décrit par une matrice dite stochastique. Comme le graphe a 6 sommets, cette matrice est de dimensions 6×6 (chaque colonne représente un sommet au départ d’une arête, et chaque ligne le sommet auquel il va). En numérotant les sommets de 0 à 5, on a la matrice suivante :
| 0 | 1/3 | 1/3 | 0 | 0 | 1/3 |
| 0 | 0 | 1/2 | 1/2 | 0 | 0 |
| 0 | 0 | 0 | 1/3 | 1/3 | 1/3 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 |
La situation de départ est décrite par un vecteur où seul le sommet 0 a un poids puisque le pion est alors au départ sur le sommet 0 :
| 1 | 0 | 0 | 0 | 0 | 0 |
En multipliant ce vecteur par la matrice, on obtient la loi de probabilité des positions possibles du pion après un lancer de dé :
| 0 | 1/3 | 1/3 | 0 | 0 | 1/3 |
On pouvait lire cela sur le graphe : Après un lancer du dé (par le joueur A), le pion a une chance sur trois de se trouver au sommet 1, une chance sur trois de se trouver au sommet 2 et une chance sur trois de se trouver au sommet 5.
La probabilité que le pion soit en 3 (4e case) valant 0, on en déduit qu’il est absolument impossible que le joueur A gagne au premier coup.
Par contre en remultipliant par la matrice carrée, on obtient cette distribution de probabilité pour la position du pion après le second lancer de dé (par B) :
| 0 | 0 | 1/6 | 5/18 | 4/9 | 1/9 |
B a donc 5 chances sur 18 de gagner dès le second lancer de dé.
Une fois que le pion est sur le sommet 3, il y reste, donc en remultipliant par la matrice, on a la probabilité 7/9 que le pion soit au sommet 3 au bout de 3 lancers :
| 0 | 0 | 0 | 7/9 | 1/6 | 1/18 |
Parmi ces 7/9, il y a la probabilité que le pion ait déjà été au sommet 3 depuis le coup précédent, soit 5/18.
La probabilité que le joueur A gagne au troisième coup (lorsqu’il relance le dé) est donc 7/9-5/18 = 1/2. En remultipliant par la matrice stochastique, on voit qu’après le 4e lancer de dé, la probabilité que le pion soit sur le sommet 3 est 17 chances sur 18 :
| 0 | 0 | 0 | 17/18 | 1/18 | 0 |
La probabilité que B gagne au bout du 4e lancer de dé est donc 17/18-7/9 = 1/6 : B a une chance sur 6 de gagner au 4e lancer de dé .
En remultipliant par la matrice on trouve que le pion ne peut plus aller qu’au sommet 3 et A gagne à coup sûr dans les rares cas où la partie a duré aussi longtemps :
| 0 | 0 | 0 | 1 | 0 | 0 |
La probabilité que cela arrive (5 lancers de dé) est donc 1-17/18=1/18, soit une chance sur 18.
En résumé, le dé ne peut pas être lancé plus de 5 fois (le trajet le plus long sur le graphe est de longueur 5 arêtes) et B ne peut gagner qu’au bout de 2 lancers (probabilité 5/18) ou au bout de 4 lancers (probabilité 1/6). Par conséquent, la probabilité que ce soit B qui gagne à ce jeu, est 5/18+1/6=4/9 soit environ 0,4444. Le jeu est donc à l’avantage de A qui gagne dans environ 55,55 pourcent des cas.
En général, une chaîne de Markov comprend des cycles, et même il peut arriver que des arêtes aillent d’un sommet à lui-même, ce qui n’a pas été prévu dans l’outil en ligne des chaînes de Markov. On va voir comment circonvenir cette difficulté, sur l’exemple suivant.
Santé
Voici un extrait du sujet de bac S de septembre 2013 :
Dans un village imaginaire isolé, une nouvelle maladie contagieuse mais non mortelle a fait son apparition.
Rapidement les scientifiques ont découvert qu’un individu pouvait être dans l’un des trois états suivants :
S : « l’individu est sain, c’est-à-dire non malade et non infecté »,
I : « l’individu est porteur sain, c’est-à-dire non malade mais infecté »,
M : « l’individu est malade et infecté ».Les scientifiques estiment qu’un seul individu est à l’origine de la maladie sur les 100 personnes que compte la population et que, d’une semaine à la suivante, un individu change d’état suivant le processus suivant :
• parmi les individus sains, la proportion de ceux qui deviennent porteurs sains est égale à 1/3 et la proportion de ceux qui deviennent malades est égale à 1/3,
• parmi les individus porteurs sains, la proportion de ceux qui deviennent malades est égale à 1/2.
Un jeu est facile à fabriquer avec le graphe de ce sujet, que voici :
Comme précédemment en effet, on peut, à partir du constat que toutes les probabilités conditionnelles ont un dénominateur divisant 6, multiplier les probabilités conditionnelles par 6 pour avoir des nombres de faces de dé (cubique) déterminant le trajet choisi. Par exemple :
Pour simuler ceci avec Nirina974, on peut
- diviser le sommet S en deux sommets (le 1 et le 2) avec arête dans les deux sens
- diviser I aussi en deux sommets (le 3 et le 4)
- choisir pour le trajet de S vers I, si l’arête part du sommet 1 ou du sommet 2 (en fait on partage entre les deux)
- faire de l’arrivée (sommet 5 ci-dessous) le sommet M
- ajouter un sommet 0 allant directement, sans autre possibilité, vers le sommet 1 (état initial S)
Voici le graphe obtenu :
Et un exemple de partie du jeu :
Initialement le pion est en 0 ; on lance le dé et le pion va automatiquement en 1 :
Ensuite, on lance le dé et le pion va, par exemple, en 2 (le patient reste en bonne santé mais c’est l’autre bonne santé, pas celle du 1) :
Puis on relance le dé et le pion revient en 1 (le patient est toujours en bonne santé) :
Puis on relance le dé et le patient devient infecté asymptomatique :
Puis on relance le dé et le patient reste infecté (mais au sommet 4, plus 3) :
En relançant le dé, on constate que le patient reste infecté asymptomatique :
Et pas de chance (pour le patient), en relançant le dé, il devient malade, ce qui termine le jeu :
Si on a bien compté, c’est B qui a perdu ce jeu. Quant au patient, c’est la santé qu’il a perdue.
Pour simuler ce modèle, un itérateur sans condition d’arrêt est possible :
from random import *
graphe = {"sain": ["sain","infecté","malade"], "infecté": ["infecté","malade"], "malade": ["malade"]}
def patient(etat="sain"):
while etat != "mort":
yield "Le patient est " + str(etat)
etat = choice(graphe[etat])
santé = patient("sain")
for temps in range(10):
print(next(santé))On peut obtenir ce genre de rapport médical :
Le patient est sain
Le patient est sain
Le patient est sain
Le patient est sain
Le patient est infecté
Le patient est malade
Le patient est malade
Le patient est malade
Le patient est malade
Le patient est maladeBac S
D’autres sujets du bac S se prètent à des réalisations sous forme de jeux de hasard, puisque les dénominateurs sont souvent des diviseurs de 4, 6, 8 ou 20 (à jouer avec des dés respectivement tétraédriques, cubiques, octaédriques ou icosaédriques) :
Arbres pondérés
Un exemple important de chaîne de Markov sans boucle est celui des arbres pondérés, qui peuvent servir à introduire les probabilités conditionnelles et la théorie de Bayes par le jeu :
Ce jeu est à l’évidence à l’avantage de A :
Pour jouer, il faut placer un pion (commun aux deux joueurs) sur la racine de l’arbre, puis lancer le dé deux fois de suite, et déplacer le pion selon les indications données par le dé. Voici le graphe version Nirina974 :
A gagne si la position finale du pion est la feuille 4 ou la feuille 6, B gagne si la position finale du pion est l’une des feuilles 5 et 7. Le débit des trajets du pion étant plus grand vers les feuilles 4 et 6, on voit que A gagnera plus souvent. Mais peut-on quantifier l’avantage de A sur B [6] ?
La version pondérée permet de calculer la probabilité de gain de A : 2/3×5/6+1/3×1/2=10/18+1/6=13/18 soit environ 0,7222 (ou treize chances sur 18, ou treize chances contre cinq [7]).
Voici le plateau de jeu :
Le jeu a été testé en première année de BTS, en deux groupes, ce qui a permis ce relevé statistique par groupe [8] :
| groupes | A gagne | B gagne | total |
| 1 | 73 | 27 | 100 |
| 2 | 66 | 34 | 100 |
Pour noter les résultats des 100 parties, il faut une dizaine de minutes. En effet une fois que le principe du jeu est acquis, les parties s’enchaînent très vite. Par exemple, on comprend vite que rien ne change si la même personne lance le dé deux fois de suite voire ne bouge le pion que mentalement.
Le reste de l’heure est consacré à redessiner l’arbre pondéré, calculer les probabilités (conditionnelles) et compléter l’arbre, puis additionner les probabilités constituant celle de A.
Puis à essayer de relever un défi : Comment équilibrer les chances de gain de A et B, sans aller jusqu’à l’évidence des probabilités (conditionnelles) toutes égales à 1/2 ?
Voici une réponse possible, comme on peut le constater en calculant la probabilité de gain du joueur A :
L’arbre de l’exercice peut être revu d’une manière moins stochastique, en termes de flux dans le réseau. On commence par placer, non un pion, mais 18 graines, au départ :
Puis, comme la probabilité d’emprunter la branche gauche est 2/3, on transfère sur cette branche les deux tiers de ces 18 graines, soit 12 graines, et les 6 graines restantes sur l’autre branche :
Puis on recommence : Les 5/6 des 12 graines tout à gauche, le 6e restant ensuite, et répartition moitié-moitié des 6 graines entre les deux dernières feuilles :
En bref, on a considéré les probabilités (conditionnelles) comme des fractions opérant sur les nombres de graines. Au final, on retrouve les probabilités d’atteinte de ces feuilles, en divisant par le nombre total de graines (18) les numérateurs apparus sur les feuilles de l’arbre ci-dessus : 10, 2, 3 et 3. Et on peut directement, après avoir rassemblé les 13 graines sur les feuilles marquées « A », calculer la probabilité 13/18 de gain de A. Ceci revient à considérer l’arbre pondéré comme un réseau de Petri, que voici :
Une étude de cas : les automates
Kleene
L’automate que voici est capable de reconnaître les multiples de 5, écrits en binaire. On a prévu une version « caméléon » qui montre ses états sous la forme de couleurs. Voici la version html (que l’on peut ouvrir dans un autre onglet pour l’explorer) :
Fonction
Dans ce qui précède, le graphe de transition et l’état initial sont des variables globales. Cela n’est pas nécessaire, on peut les placer dans une fonction :
def est_divisible_par_5(mot):
transition = [(0,1),(2,3),(4,0),(1,2),(3,4)]
state = 0
for lettre in mot:
chiffre = int(lettre)
state = transition[state][chiffre]
return state==0Cette fonction aurait pu afficher les états successifs avec print mais puisque l’état final est le plus important (il détermine à lui seul la divisibilité par 5) on ne renvoie que lui. Ou même sa comparaison avec 0, qui caractérise la divisibilité par 5.
On peut utiliser cette fonction dans une boucle ou une compréhension, par exemple :
for n in range(25):
print(n,est_divisible_par_5(bin(n)[2:]))Mais cela ne modélise pas vraiment l’automate. Un itérateur convient mieux.
Itérateur
Avec un itérateur, l’état est interne à l’automate ce qui correspond mieux à l’image qu’on s’en fait habituellement. L’argument de yield est l’état actuel de l’automate :
def kleene(mot):
transition = [(0,1),(2,3),(4,0),(1,2),(3,4)]
state = 0
for lettre in mot:
chiffre = int(lettre)
state = transition[state][chiffre]
yield stateCommentaires sur les lignes du programme :
- L’automate reçoit un mot en entrée, il sera chargé de le reconnaître (ou non).
- Le graphe des transitions est aussi interne à l’automate. C’est une sorte de câblage de son cerveau, et le cerveau est à l’intérieur...
- Les états, et en particulier l’état initial, sont aussi internes à l’automate.
- En bouclant sur les lettres du mot à lire, l’automate lèvera une exception de fin d’itération quand il arrivera à la fin du mot, pour dire qu’il a fini.
- La lettre lue est « 0 » ou « 1 » (un caractère) donc on le convertit en entier pour pouvoir s’en servir comme index dans la liste.
- L’automate change d’état,
- puis exprime son état actuel.
On peut utiliser cet itérateur en l’initialisant avec le mot à lire puis en bouclant sur ses états successifs :
div5 = kleene("11110101")
for s in div5:
print(s)On peut aussi convertir en liste l’ensemble automate+mot :
for n in range(16):
print(list(kleene(bin(n)[2:])))Coroutine
On peut faire encore mieux, en envoyant une par une les lettres du mot à lire, à l’automate, plutôt que lui donner tout le mot dès sa naissance :
def automate():
transition = [(0,1),(2,3),(4,0),(1,2),(3,4)]
state = 0
lettre = "0"
while 0==0:
lettre = yield state
chiffre = int(lettre)
state = transition[state][chiffre]On retrouve le yield state de l’itérateur précédent, mais cette fois-ci le résultat est affecté à lettre, ce qui permet maintenant de ne pas seulement écouter l’automate, mais aussi lui parler (avec des « 0 » et des « 1 »). Voici un exemple de bavardage :
kleene = automate()
kleene.send(None)
for c in "10100101":
print(kleene.send(c)) Explication du script, ligne par ligne :
- On ne donne plus d’argument à l’automate, sa mémoire est vide à sa naissance, et il apprendra par l’écoute des messages qu’on lui enverra.
- Il faut lancer l’automate en lui envoyant un message vide (la fameuse initialisation ; sinon on aura un message d’erreur, du moins sous Python3.5)
- On boucle sur les lettres du mot, comme précédemment...
- ...mais on les envoie à l’automate et on affiche sa réponse (l’état actuel de l’automate)
Le compte-rendu du bavardage :
1
2
0
0
0
1
2
0L’état final est 0, ce qui confirme que le nombre 165, qui s’écrit 10100101 en binaire, est divisible par 5.
Mealy
Cet automate [9], proposé pour la semaine des maths 2020, permet de décoder des mots binaires. Là encore, on propose une version « caméléon », mais cette-fois ci, outre les changements de couleurs, le caméléon écrit un texte, qui est le mot décodé.
Voici la version html (que l’on peut ouvrir dans un autre onglet pour l’explorer) :
TkInter
from tkinter import *
colors = ["red","magenta","orange","blue","green"]
transition = [[0,1],[0,2],[0,3],[0,4],[0,0]]
code = [["S",""],["A",""],["N",""],["I",""],["T","E"]]
state = 0
letter = ""
word = ""
def affichage(chiffre):
global state,word
word += code[state][chiffre]
state = transition[state][chiffre]
cham.config(background=colors[state])
wlab.config(text=word)
wlab.config(foreground=colors[state])
def r0():
affichage(0)
def r1():
affichage(1)
def rc():
global state,word
state = 0
word = ''
cham.config(background='red')
wlab.config(text='')
machine = Tk()
machine.title("Huffman")
b0=Button(machine,text='0',command=r0)
b0.pack(side=LEFT)
b1=Button(machine,text='1',command=r1)
b1.pack(side=RIGHT)
cham = Canvas(machine,width=160,height=160,bg='red')
cham.pack()
wlab=Label(machine,text='',bg='white',fg='red')
wlab.pack(side=BOTTOM)
c=Button(machine,text='Clear',command=rc)
c.pack(side=BOTTOM)
machine.mainloop()micro:bit
Le code est d’une concision impressionnante :
from microbit import *
transition = [[0,1],[0,2],[0,3],[0,4],[0,0]]
code = [["S",""],["A",""],["N",""],["I",""],["T","E"]]
i = 0
t =""
while 0==0:
n = 2
while n == 2 :
if button_a.was_pressed():
n = 0
elif button_b.was_pressed():
n = 1
t += code[i][n]
i = transition[i][n]
display.scroll(t)Fonction
On peut écrire une fonction de décodage (c’est l’intérêt de cet automate) ayant pour variables locales :
- le graphe (sous forme de liste de couples) des changements d’état ;
- la liste des diagrammes sagittaux (des couples) des suffixes à écrire ;
- l’état de l’automate (un entier servant d’index aux deux listes ci-dessus) ;
- le mot en cours d’écriture.
À la fin de la lecture du mot, l’état final est nul si et seulement si le mot a correctement été codé. Mais c’est le mot lui-même que renverra la fonction :
def decodage(mot_binaire):
transition = [(0,1),(0,2),(0,3),(0,4),(0,0)]
code = [("S",""),("A",""),("N",""),("I",""),("T","E")]
state = 0
word = ""
for lettre in mot_binaire:
chiffre = int(lettre)
word += code[state][chiffre]
state = transition[state][chiffre]
return wordPour décoder le mot binaire 110111011010 c’est aussi simple que
print(decodage("110111011010"))
Itérateur
Pour construire une machine de Mealy comme un itérateur, on fait comme avec l’automate de Kleene, mais au lieu de rendre un rapport sur l’état interne, on en rédige un sur le mot en cours de décodage. Cela permet de mieux voir comment se fait le décodage, étape par étape :
def mealy(mot):
transition = [(0,1),(0,2),(0,3),(0,4),(0,0)]
code = [("S",""),("A",""),("N",""),("I",""),("T","E")]
state = 0
word = ""
for lettre in mot:
chiffre = int(lettre)
word += code[state][chiffre]
state = transition[state][chiffre]
yield wordAvec
secret = mealy("110111011010")
for mot_partiel in secret:
print(mot_partiel)on obtient ce rapport complet sur les étapes du décodage :
NI
NI
NI
NIN
NIN
NINACoroutine
Cette version est une vraie machine séquentielle, à qui on envoie les chiffres binaires l’un après l’autre, et qui renvoie une lettre qu’elle vient de décoder, au fur et à mesure des décodages :
def décodeur():
transition = [(0,1),(0,2),(0,3),(0,4),(0,0)]
code = [("S",""),("A",""),("N",""),("I",""),("T","E")]
state = 0
lettre = ""
lettre_décodée = ""
while 0==0:
lettre = yield lettre_décodée
chiffre = int(lettre)
lettre_décodée = code[state][chiffre]
state = transition[state][chiffre]Comme pour la version automate de Kleene, on doit, après avoir construit la machine, lui envoyer du rien pour la démarrer :
machine = décodeur()
machine.send(None)Après, on crée un mot (décodé) initialisé au mot vide :
mot_décodé = ""puis
- on lit chiffre après chiffre le mot codé en binaire,
- on envoie le chiffre à la machine,
- on lit la lettre qu’elle renvoie,
- et on rajoute cette lettre à la fin du mot en cours de décodage.
for chiffre_binaire in "110111011010":
mot_décodé += machine.send(chiffre_binaire)
print(mot_décodé)En écrivant au fur et à mesure les étapes du mot à décoder (le print ci-dessus), on obtient ceci :
N
N
N
N
NI
NI
NI
NIN
NIN
NINA
Commentaires