Les itérateurs de Python

vendredi 8 mars 2019
par  Alain BUSSER

Dans les aménagements de programme de 2009 puis dans le programme de 2010 (2nde, rubrique « pour le lycée ») et enfin dans les aménagements de programme de 2de de 2017, figure non pas le mot « itération » mais le mot « itérateur ». Ce mot a disparu dans les programmes de maths applicables à la rentrée 2019. Dans cet article on va donc apporter un regard historique à cette question des itérateurs, et pas seulement ceux de Python.

Un itérateur est un objet possédant un certain nombre (éventuellement infini) d’états discrets, et capable

  • de changer d’état sur commande (avec la fonction next)
  • de faire un rapport introspectif sur son état actuel (avec la fonction yield)

De quoi s’agit-il ?

Mais d’abord, qu’est-ce que c’est qu’un itérateur ? C’est un objet capable d’itérer (si si !), ce qu’il fait à l’aide d’une méthode (une fonction bien à lui) qui, en Python, s’appelle next(). Un exemple a été vu dans cet article où l’on constatait que pour certaines équations de Pell-Fermat, il était possible d’énumerer par algorithme, les points à coordonnées entières sur l’hyperbole : On peut itérer sur ces points. Un itérateur est l’objet qui est capable de parcourir, l’un après l’autre, ces points. Il se comporte un peu comme le petit poucet qui ramasse les cailloux l’un après l’autre, et à chaque ramassage, il sait trouver où est le prochain (next) caillou. On voit fréquemment des itérateurs dans les cours de récréation des écoles : Les enfants qui jouent à la marelle ! Un générateur de nombres pseudo-aléatoires est un autre exemple connu d’itérateur. Mais il en est de même pour le pion qui parcourt un graphe dans les jeux de Nim. Ou une chaîne de Markov comme on le verra plus bas.

Tétratrichotémologie

Le mot itérable est un adjectif, alors que itérateur est un nom. On ne s’attend donc pas à ce qu’ils désignent la même chose. D’après le Gang of Four, un itérateur « est un objet qui permet de parcourir tous les éléments contenus dans un autre objet ».

Ci-dessus on a dit qu’un itérateur est capable d’itérer, pour le GoF c’est un objet qui permet d’itérer.

De même, en Python, range (qui permet bel et bien d’itérer) n’est pas considéré comme un itérateur. En Python, un objet est itérable si on peut lui appliquer la fonction iter. Et cette fonction renvoie justement un ... itérateur !

En fait, on connaît essentiellement 3 moyens de fabriquer un itérateur de Python :

  • Appliquer la fonction iter à un itérable. Par exemple l’objet ci-dessous est un itérable parce qu’il possède une méthode __getitem__ (qui permet de lui appliquer la fonction iter) :
  1. class Cubes():
  2.         def __getitem__(self,n):
  3.                 return n**3

Télécharger

Alors

C = iter(Cubes())

fait que C est un itérateur, parcourant les cubes des entiers l’un après l’autre.

  • Une fonction génératrice, plus simplement un générateur est une fonction fabriquant un itérateur. Un générateur de cubes est
  1. def cubes():
  2.         n = 0
  3.         while 0==0:
  4.                 yield n**3
  5.                 n = n+1

Télécharger

Alors

C = cubes()

fait là encore que C est un itérateur parcourant les cubes des entiers naturels.

  • Une expression génératrice est une compréhension notée entre parenthèses. Elle aussi fabrique un itérateur. Par exemple

C = (n**3 for n in range(5))

fait une fois de plus que C est un itérateur parcourant les cubes des entiers naturels, à ceci près que cette fois-ci l’itérateur a une durée de vie finie.

Dans les trois cas,

  1. for n in range(5):
  2.         print(next(C))

Télécharger

produit le même affichage

0
1
8
27
64

Comme le sujet de cet article n’est pas la programmation objet, on n’y traitera pas la première méthode (avec iter). La troisième méthode ayant été abordée dans cet article, on utilisera ici exclusivement la deuxième méthode :

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 random de 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 :

  1. def floatrange(a,b,p=1.0):
  2.     x = float(a)
  3.     while x<float(b):
  4.         yield x
  5.         x += p

Télécharger

La 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

  1. for x in floatrange(0,1,0.1):
  2.     print(x)

Télécharger

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

Une 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 :

  1. def geomrange(r,u,s):
  2.     while ((r>1 and u<s) or (r<1 and u>s)):
  3.         yield u
  4.         u *= r

Télécharger

La 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 :

  1. capital = geomrange(0.85,16000,2000)
  2. for n in range(50):
  3.     print(n,next(capital))

Télécharger

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))
StopIteration

Il 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 :

  1. def aryabhata():
  2.     n = 0
  3.     u = 0.0
  4.     S = 0
  5.     while n<25:
  6.         yield u/3440
  7.         n += 1
  8.         S += u
  9.         u += 225.0-S/225.0

Télécharger

Il 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 :

  1. def clapier():
  2.     adultes = 1
  3.     jeunes = 1
  4.     while adultes < 1e6:
  5.         yield adultes*"M"+jeunes*"m"
  6.         adultes,jeunes = adultes+jeunes,adultes

Télécharger

La 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 :

  1. population = clapier()
  2.  
  3. for mois in range(8):
  4.     print(next(population))

Télécharger

L’évolution est conforme à ce qu’on connaît sur la suite de Fibonacci :

Mm
MMm
MMMmm
MMMMMmmm
MMMMMMMMmmmmm
MMMMMMMMMMMMMmmmmmmmm
MMMMMMMMMMMMMMMMMMMMMmmmmmmmmmmmmm
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMmmmmmmmmmmmmmmmmmmmmm

Remarque : 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

  1. for lapins in clapier():
  2.     print(lapins)

Télécharger

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 :

  1. def FortBoyard(N):
  2.     autre = { "A": "B", "B": "A"}
  3.     joueur = "A"
  4.     while N>0:
  5.         yield joueur + " hérite de " + N*"|"
  6.         k=int(input("Combien le joueur " + joueur + " veut-il enlever d'allumettes (1,2 ou 3) ? "))
  7.         N -= k
  8.         joueur = autre[joueur]

Télécharger

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

  1. for coup in FortBoyard(13):
  2.     print(coup)

Télécharger

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) ? 1

Dada

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 :

  1. def dada():
  2.     die = None
  3.     while die != 6:
  4.         yield die
  5.         die = randint(1,6)

Télécharger

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

  1. nblancers = 0
  2. forin dada():
  3.     nblancers += 1

Télécharger

Aprè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 :

  1. def alea(graine=1):
  2.     while graine>0:
  3.         graine *= 1664525
  4.         graine += 1013904223
  5.         graine %= 2**32
  6.         yield graine/2**32

Télécharger

Pour simuler une variable aléatoire X suivant une loi uniforme sur [0,1], on peut faire

  1. X = alea(123)
  2.  
  3. for n in range(8):
  4.     print(next(X))

Télécharger

qui donne ce genre d’affichage :

0.2837369213812053
0.4351300236303359
0.03865125775337219
0.22087990469299257
0.3594270762987435
0.5902441388461739
0.361280900426209
0.3268499083351344

Voici 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) :

  1. from random import *
  2.  
  3. def lt(N):
  4.     lp,tp = 0,0
  5.     while lp<N and tp<N:
  6.         die = randint(1,6)
  7.         if die==6:
  8.             lp += 6
  9.         else:
  10.             tp += 1
  11.         yield "Le dé est tombé sur {} ; Le lièvre est en {} et la tortue est en {}.".format(die,lp,tp)

Télécharger

Les variables lt et tp désignent respectivement la position du lièvre et celle de la tortue.

Avec

  1. for coup in lt(4):
  2.     print(coup)

Télécharger

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 4

La version itérateur donne ceci (le graphe est un tableau qui, pour chaque sommet, précise à quoi il est adjacent) :

  1. from random import *
  2.  
  3.  
  4. graphe = [[1,2,5],[2,3],[3,4,5],[3],[3],[4]]
  5. autre = {"A": "B", "B": "A"}
  6.  
  7. def jeu(etat=0):
  8.     joueur = "A"
  9.     while etat != 3:
  10.         yield "Le joueur " + joueur + " voit le pion sur le sommet " + str(etat)
  11.         etat = choice(graphe[etat])
  12.         joueur = autre[joueur]
  13.        
  14.  
  15. for coup in jeu(0):
  16.     print(coup)

Télécharger

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

Le joueur B a donc 5 chances sur 18 de gagner au second coup de dé. Et il y a 13 chances sur 18 que le jeu continue. Parmi cela, il y a 7 chances sur 9 que A gagne au troisième coup, comme on le voit en remultipliant par la matrice :

0 0 0 7/9 1/6 1/18

La probabilité que le joueur A gagne au troisième coup (lorsqu’il relance le dé) est donc 13/18×7/9=91/162. Et il y a donc 71 chances sur 162 (1-91/162=71/162) que la partie continue au-delà du troisième lancer de dé. En remultipliant par la matrice stochastique, on voit que lors du 4e lancer de dé, B a 17 chances sur 18 de gagner :

0 0 0 17/18 1/18 0

Mais comme il y avait 71 chances sur 162 que l’évènement de probabilité 17/18 se réalise, la probabilité que B gagne au bout du 4e lancer de dé est 71/162×17/18=1207/2916.

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

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é 1207/2916). Par conséquent, la probabilité que ce soit B qui gagne à ce jeu, est 5/18+1207/2916=2017/2916 soit environ 0,6917. Le jeu est donc à l’avantage de B qui gagne plus de deux fois sur trois.

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 :

  1. from random import *
  2.  
  3.  
  4. graphe = {"sain": ["sain","infecté","malade"], "infecté": ["infecté","malade"], "malade": ["malade"]}
  5.  
  6. def patient(etat="sain"):
  7.     while etat != "mort":
  8.         yield "Le patient est " + str(etat)
  9.         etat = choice(graphe[etat])
  10.        
  11. santé = patient("sain")
  12.  
  13. for temps in range(10):
  14.     print(next(santé))

Télécharger

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 malade

Bac 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) :

Caméléon

Version console

Le premier script permet de faire des tests sans nécessiter l’accès à un appareil connecté comme la micro:bit.

  1. colors = ["rouge","magenta","jaune","bleu","vert"]
  2. transition = [[0,1],[2,3],[4,0],[1,2],[3,4]]
  3. state = 0
  4. lettre = ""
  5. mot = ""
  6. print("La couleur initiale de Bicham est rouge.")
  7. while 0==0:
  8.     lettre = ""
  9.     while lettre not in ["0","1","c"]:
  10.             lettre = input("0, 1 ou c ? ")
  11.     if lettre == "c":
  12.             state,lettre,mot = 0,0,""
  13.             print("Réinitialisation : Bicham est redevenu rouge")
  14.     else:
  15.             chiffre = int(lettre)
  16.             mot += lettre
  17.             state = transition[state][chiffre]
  18.             print("Bicham est devenu",colors[state],"qui est la couleur du mot",mot,"représentant le nombre",str(int(mot,2)))
  19.    

Télécharger

version TkInter

  1. from tkinter import *
  2.  
  3. colors = ["red","magenta","orange","blue","green"]
  4. transition = [[0,1],[2,3],[4,0],[1,2],[3,4]]
  5. state = 0
  6. letter = ""
  7. word = ""
  8.  
  9. def affichage(chiffre):
  10.     global state,word
  11.     state = transition[state][chiffre]
  12.     word += str(chiffre)
  13.     cham.config(background=colors[state])
  14.     wlab.config(text=word+' ('+str(int(word,2))+')')
  15.     wlab.config(foreground=colors[state])
  16.  
  17.  
  18. def r0():
  19.     affichage(0)
  20.  
  21. def r1():
  22.     affichage(1)
  23.  
  24. def rc():
  25.     global state,word
  26.     state = 0
  27.     word = ''
  28.     cham.config(background='red')
  29.     wlab.config(text='')
  30.  
  31. machine = Tk()
  32. machine.title("bicham")
  33. b0=Button(machine,text='0',command=r0)
  34. b0.pack(side=LEFT)
  35. b1=Button(machine,text='1',command=r1)
  36. b1.pack(side=RIGHT)
  37. cham = Canvas(machine,width=160,height=160,bg='red')
  38. cham.pack()
  39. wlab=Label(machine,text='',bg='white',fg='red')
  40. wlab.pack(side=BOTTOM)
  41. c=Button(machine,text='Clear',command=rc)
  42. c.pack(side=BOTTOM)
  43. machine.mainloop()

Télécharger

version Sense Hat :

L’entrée d’un « 0 » se fait en déplaçant le joystick vers la gauche, l’entrée d’un « 1 » se fait en déplaçant le joystick vers la droite.

  1. from sense_hat import *
  2.  
  3. couleur = [(120,0,0),(120,0,120),(160,40,0),(0,0,120),(0,120,0)]
  4. transition = [[0,1],[2,3],[4,0],[1,2],[3,4]]
  5.  
  6.  
  7. hat = SenseHat()
  8. hat.low_light = True
  9. etat = 0
  10.  
  11. hat.clear(couleur[etat])
  12. goon = True
  13. while goon:
  14.         event = hat.stick.wait_for_event()
  15.         if event.action == "released":
  16.                 if event.direction == "left":
  17.                         etat = transition[etat][0]
  18.                         hat.clear(couleur[etat])
  19.                 elif event.direction == "right":
  20.                         etat = transition[etat][1]
  21.                         hat.clear(couleur[etat])
  22.                 elif event.direction == "middle":
  23.                         goon = False

Télécharger

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 :

  1. def est_divisible_par_5(mot):
  2.         transition = [(0,1),(2,3),(4,0),(1,2),(3,4)]
  3.         state = 0
  4.         for lettre in mot:
  5.                 chiffre = int(lettre)
  6.                 state = transition[state][chiffre]
  7.         return state==0

Télécharger

Cette 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 :

  1. for n in range(25):
  2.         print(n,est_divisible_par_5(bin(n)[2:]))

Télécharger

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 :

  1. def kleene(mot):
  2.         transition = [(0,1),(2,3),(4,0),(1,2),(3,4)]
  3.         state = 0
  4.         for lettre in mot:
  5.                 chiffre = int(lettre)
  6.                 state = transition[state][chiffre]
  7.                 yield state

Télécharger

Commentaires sur les lignes du programme :

  1. L’automate reçoit un mot en entrée, il sera chargé de le reconnaître (ou non).
  2. 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...
  3. Les états, et en particulier l’état initial, sont aussi internes à l’automate.
  4. 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.
  5. 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.
  6. L’automate change d’état,
  7. 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 :

  1. div5 = kleene("11110101")
  2. for s in div5:
  3.         print(s)

Télécharger

On peut aussi convertir en liste l’ensemble automate+mot :

  1. for n in range(16):
  2.         print(list(kleene(bin(n)[2:])))

Télécharger

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 :

  1. def automate():
  2.         transition = [(0,1),(2,3),(4,0),(1,2),(3,4)]
  3.         state = 0
  4.         lettre = "0"
  5.         while 0==0:
  6.                 lettre = yield state
  7.                 chiffre = int(lettre)
  8.                 state = transition[state][chiffre]

Télécharger

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 :

  1. kleene = automate()
  2. kleene.send(None)
  3. for c in "10100101":
  4.         print(kleene.send(c))  

Télécharger

Explication du script, ligne par ligne :

  1. 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.
  2. 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)
  3. On boucle sur les lettres du mot, comme précédemment...
  4. ...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
0

L’é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

  1. from tkinter import *
  2.  
  3. colors = ["red","magenta","orange","blue","green"]
  4. transition = [[0,1],[0,2],[0,3],[0,4],[0,0]]
  5. code = [["S",""],["A",""],["N",""],["I",""],["T","E"]]
  6. state = 0
  7. letter = ""
  8. word = ""
  9.  
  10. def affichage(chiffre):
  11.     global state,word
  12.     word += code[state][chiffre]
  13.     state = transition[state][chiffre]
  14.     cham.config(background=colors[state])
  15.     wlab.config(text=word)
  16.     wlab.config(foreground=colors[state])
  17.  
  18.  
  19. def r0():
  20.     affichage(0)
  21.  
  22. def r1():
  23.     affichage(1)
  24.  
  25. def rc():
  26.     global state,word
  27.     state = 0
  28.     word = ''
  29.     cham.config(background='red')
  30.     wlab.config(text='')
  31.  
  32.  
  33.  
  34.  
  35.  
  36.  
  37. machine = Tk()
  38. machine.title("Huffman")
  39. b0=Button(machine,text='0',command=r0)
  40. b0.pack(side=LEFT)
  41. b1=Button(machine,text='1',command=r1)
  42. b1.pack(side=RIGHT)
  43. cham = Canvas(machine,width=160,height=160,bg='red')
  44. cham.pack()
  45. wlab=Label(machine,text='',bg='white',fg='red')
  46. wlab.pack(side=BOTTOM)
  47. c=Button(machine,text='Clear',command=rc)
  48. c.pack(side=BOTTOM)
  49. machine.mainloop()

Télécharger

micro:bit

Le code est d’une concision impressionnante :

  1. from microbit import *
  2.  
  3. transition = [[0,1],[0,2],[0,3],[0,4],[0,0]]
  4. code = [["S",""],["A",""],["N",""],["I",""],["T","E"]]
  5. i = 0
  6. t =""
  7.  
  8. while 0==0:
  9.         n = 2
  10.         while n == 2 :
  11.             if button_a.was_pressed():
  12.                 n = 0
  13.             elif button_b.was_pressed():
  14.                 n = 1
  15.         t += code[i][n]
  16.         i = transition[i][n]
  17.         display.scroll(t)

Télécharger

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 :

  1. def decodage(mot_binaire):
  2.         transition = [(0,1),(0,2),(0,3),(0,4),(0,0)]
  3.         code = [("S",""),("A",""),("N",""),("I",""),("T","E")]
  4.         state = 0
  5.         word = ""
  6.         for lettre in mot_binaire:
  7.                 chiffre = int(lettre)
  8.                 word += code[state][chiffre]
  9.                 state = transition[state][chiffre]
  10.         return word

Télécharger

Pour 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 :

  1. def mealy(mot):
  2.         transition = [(0,1),(0,2),(0,3),(0,4),(0,0)]
  3.         code = [("S",""),("A",""),("N",""),("I",""),("T","E")]
  4.         state = 0
  5.         word = ""
  6.         for lettre in mot:
  7.                 chiffre = int(lettre)
  8.                 word += code[state][chiffre]
  9.                 state = transition[state][chiffre]
  10.                 yield word

Télécharger

Avec

  1. secret = mealy("110111011010")
  2.  
  3. for mot_partiel in secret:
  4.         print(mot_partiel)

Télécharger

on obtient ce rapport complet sur les étapes du décodage :

NI
NI
NI
NIN
NIN
NINA

Coroutine

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 :

  1. def décodeur():
  2.         transition = [(0,1),(0,2),(0,3),(0,4),(0,0)]
  3.         code = [("S",""),("A",""),("N",""),("I",""),("T","E")]
  4.         state = 0
  5.         lettre = ""
  6.         lettre_décodée = ""
  7.         while 0==0:
  8.                 lettre = yield lettre_décodée
  9.                 chiffre = int(lettre)
  10.                 lettre_décodée = code[state][chiffre]
  11.                 state = transition[state][chiffre]

Télécharger

Comme pour la version automate de Kleene, on doit, après avoir construit la machine, lui envoyer du rien pour la démarrer :

  1. machine = décodeur()
  2. machine.send(None)

Télécharger

Après, on crée un mot (décodé) initialisé au mot vide :

  1. 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.
  1. for chiffre_binaire in "110111011010":
  2.         mot_décodé += machine.send(chiffre_binaire)
  3.         print(mot_décodé)

Télécharger

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


[1le module numpy possède un outil similaire, qui s’appelle linspace, mais dont l’ordre des arguments n’est pas le même, et qui renvoie une liste et non un itérateur

[2L’exemple est intéressant parce que contrairement au comportement attendu, il y a une itération de trop, dûe au fait que les erreurs d’arrondi aboutissent à une valeur approchée par défaut de 1

[3Pour changer de joueur, on utilise un dictionnaire de Python, qui représente une application qui, à un joueur, associe son adversaire, et permet de changer de joueur

[4L’attention de l’auteur de cet article sur ce sujet lui a été suggérée lors d’une discussion avec un passionné des graphes ; qu’il en soit ici remercié.

[5Pour modifier le poids d’une arête, commencer par effectuer un Control-click dessus (elle apparaît alors en pointillés) puis appuyer sur la lettre M (« Moins ») pour diminuer sa largeur, sur la lettre P (« Plus ») pour augmenter celle-ci. Si on veut attribuer un poids nul à une arête, appuyer sur Suppr ce qui a pour effet de la supprimer.

[6En fait le jeu est un pari sur la position finale du pion, estimer ou calculer la probabilité de A permet d’équilibrer le pari.

[7il faut donc parier à 5 contre 13 pour équilibrer le jeu, c’est-à-dire que A met 13 € dans la cagnotte et B met 5 € dans la cagnotte, le gagnant remportant la cagnotte. Sans évoquer la complication supplémentaire occasionnée par les impôts prélevés depuis le 18e siècle sur tous les jeux de hasard !

[8Les étudiants sont assis par deux, avec une feuille A3 entre eux, laquelle feuille représente l’arbre pondéré ; ils ont un pion par couple de joueurs, et un dé. Le pion est initialement placé à la racine de l’arbre. Chaque joueur lance le dé à son tour ou le joueur le plus rapide lance le dé pour les deux joueurs, on comprend vite que cela n’a pas d’importance.

[9Qui n’est pas vraiment un automate de Mealy : si c’était le cas il écrirait une lettre à la fois, ici il n’écrit souvent rien du tout. C’est un automate transducteur plus général qu’un automate de Mealy.


Documents joints

LaTeX - 2 ko

Commentaires

Logo de Sébastien HOARAU
dimanche 10 mars 2019 à 05h31 - par  Sébastien HOARAU

Rappelons aussi que le principal intérêt des itérateurs est de ne rien créer de lourd en mémoire. Et pour cela le meilleur exemple est le fichier. Quand on fait :

f_in = open(mon_fichier)

on ne veut surtout pas charger en mémoire l’ensemble du contenu de mon_fichier. f_in est donc un itérateur sur les lignes de mon_fichier

Logo de seb
samedi 9 mars 2019 à 18h10 - par  seb

Très sympa cet article merci Alain. Si on veut chipoter : la fonction lt n’est pas un itérateur mais une fonction génératrice... l’itérateur est le résultat de cette fonction (par exemple dans for i in lt(4), le lt(4) est un itérateur). Cette notion de fonction génératrice étend la notion d’expression génératrice :

par exemple : sum(x ** 2 for x in range(1000)) permet de calculer la somme des carrés des entiers de 0 à 999, sans créer de structure pour stocker ces carrés.

Pour savoir si un objet est un iterateur il suffit de tester : obj == iter(obj) si la réponse est True alors obj est un itérateur.