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.

Exemples

Dans cette partie de l’article on propose de voir certains itérateurs utiles en maths :

  • range et sa généralisation à d’autres 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

L’itérateur le plus connu de Python est range [1]. 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 += p

La fonction floatrange est un générateur : elle crée un itérateur [2], 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 [3] :

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 :

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

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 :

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

def aryabhata():
    n = 0
    u = 0.0
    S = 0
    while n<25:
        yield u/3440
        n += 1
        S += u
        u += 225.0-S/225.0

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 :

def clapier():
    adultes = 1
    jeunes = 1
    while adultes < 1e6:
        yield adultes*"M"+jeunes*"m"
        adultes,jeunes = adultes+jeunes,adultes

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 :

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

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 [4] (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) ? 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 :

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
forin dada():
    nblancers += 1

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 :

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

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

PDF - 1.7 Mo

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 :

 - 5.2 ko

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 [5] 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 :

PDF - 76.6 ko

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 [6].

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

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

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 :

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

PDF - 160 ko

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 :

PDF - 45.5 ko

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 [7] ?

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 [8]).

Voici le plateau de jeu :

PDF - 110.5 ko

Le jeu a été testé en première année de BTS, en deux groupes, ce qui a permis ce relevé statistique par groupe [9] :

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 :

PDF - 107.5 ko

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 :


[1Même que c’est même pas vrai : Si on écrit

R = range(3)
print(next(R))

alors on a un message d’erreur :

  • En Python 2 : la liste n’est pas un itérateur
  • En Python 3 : range n’est pas un itérateur.

On peut dire que range est un itérateur spécial, considéré comme une catégorie à part ; de la même façon que les lambda-fonctions ne sont pas du même type que les fonctions, alors que ce sont des fonctions ! De fait, Python possède une fonction appelée iter qui peut créer un itérateur sur un itérable. Par exemple iter([2,3,5,7]) crée un itérateur sur les nombres premiers inférieurs à 10. On n’a donc pas d’erreur avec ce script :

R = iter(range(3))
print(next(R))

[2le 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

[3L’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

[4Pour 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

[5L’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é.

[6Pour 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.

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

[8il 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 !

[9Les é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.


Documents joints

LaTeX - 2 ko
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.

Annonces

Prochains rendez-vous de l’IREM

Assemblée générale de l’APMEP-Réunion

- Mercredi 21 aout à 14h, lycée Évariste-de-Parny, saint-Paul.

Réunion de rentrée de l’IREM

- Mercredi 11 septembre 2019, 14h-18h, salle S23.6, PTU, Saint-Denis.


Brèves

Python au bac 2019

vendredi 31 mai

C’est une brève de MathemaTICE

La question 4b de l’exercice 3 du bac S Amérique du Nord ne pouvait être résolue sans utiliser Python.

Elwyn Berlekamp

jeudi 18 avril

Elwyn Berlekamp, connu des lecteurs de ce site pour son jeu des interrupteurs, était un spécialiste du jeu de Go ainsi que de la Pipopipette, d’Édouard Lucas que Berlekamp admirait énormément.

Notation au bac

lundi 11 décembre 2017

Une nouvelle notation sera pratiquée à partir de la session 2018 pour les algorithmes au bac. Elle est décrite avec de nombreux exemples, ici.

Décès de Roger Mohr

mardi 27 juin 2017

On sait bien que Nicolas Bourbaki n’était pas le nom d’une personne mais le pseudonyme d’un groupe. L’équivalent en informatique théorique est Claude Livercy, auteur de la théorie des programmes. Roger Mohr était un des membres de Claude Livercy.

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Statistiques

Dernière mise à jour

dimanche 14 juillet 2019

Publication

844 Articles
Aucun album photo
140 Brèves
11 Sites Web
145 Auteurs

Visites

476 aujourd'hui
451 hier
2894294 depuis le début
23 visiteurs actuellement connectés