le trésor et la fausse pièce

Dans un épisode de la saison 6 de Columbo, est posé le problème de trouver, parmi des sacs de pièces, celui qui contient des fausses pièces, plus légères, en une seule pesée. Le problème est ici analogue : trouver en un minimum de pesées la seule pièce plus légère, à l’aide d’une balance de Roberval :

Note : l’idée de résoudre ce problème en Python est de Dominique Laporte. Voici son énoncé (pour les deux classes de 1^re et terminale) :

1.

Exemples pour un petit nombre de pièces dans le trésor

Algorithme dans le cas général d’un trésor de n pièces

2. Terme « adapter »

Laquelle (ou lesquelles) des lignes de l’algorithme, doit-elle être modifiée, pour que l’algorithme donne également un résultat lorsque le nombre de pièces n’est pas une puissance de 3, et que le nouvel algorithme donne le même résultat que la version « non adaptée » lorsque le nombre de pièces est une puissance de 3 ?

3. Preuve de correction

Au début de l’algorithme, il n’y a aucune pièce sur la balance et il est donc vrai dès le départ, que s’il y en avait, la plus légère serait sur le plateau le plus élevé en cas d’équilibre et en-dehors de la balance sinon. L’invariant reste donc vrai au cours de l’exécution de l’algorithme, et a fortiori à la fin de celui-ci. Or à la fin, il y a moins de 4 pièces et les 3 (ou moins) tas de pièces sont constitués d’une seule pièce chacun : l’algorithme a isolé la fausse pièce.

Mastermind : le joueur humain devine

Remarque historico-didactique

Le jeu de Mastermind est issu d’un jeu bien plus vieux (il daterait au moins du XIX^e siècle), où Alice essayait de deviner le code (d’un cadenas par exemple) choisi par Bob, selon le protocole suivant :

• Alice essaye un code (suite de 4 chiffres comme 7262 par exemple) ;
• Bob fournit à Alice
  • un taureau (« bull ») pour chaque chiffre correct et bien placé,
  • une vache (« cow ») pour chaque chiffre correct mais au mauvais endroit.
• À partir du nombre de taureaux et du nombre de vaches, Alice fait de nouvelles hypothèses et les fait tester par Bob, jusqu’à la fin du jeu (Alice a trouvé le code ou a effectué un nombre trop grand de tentatives).

Ce jeu s’appelle donc Bulls and Cows. En 1971, Mordecai Meirowitz a eu l’idée de remplacer

• les chiffres par des couleurs,
• les taureaux par des pions noirs,
• et les vaches par des pions blancs.

Le principe du jeu est donc le même pour Bulls and cows et pour Mastermind. Mais le portage numérique de ce dernier ajoute, à la complexité de l’analyse du jeu, celle de la programmation de l’interface (typiquement TkInter). Proposer Bulls and Cows plutôt que Mastermind comme sujet de projet présente donc l’avantage de concentrer les efforts des élèves sur le moteur (par exemple avec une version en console) et de gérer plus efficacement le temps consacré au projet (le sujet parle de 20 heures ce qui, en NSI, représente un mois). D’ailleurs il n’est fait aucune allusion à des couleurs dans la description du projet « mastermind » du manuel d’ISN de Dowek et al (Eyrolles).

Pour se faire une idée, voici des solveurs pour Bulls and Cows et pour Mastermind. Et voici le Mastermind pour daltoniens de l’IREM :

1. Un dictionnaire est une structure de données intéressante lorsqu’il n’y a pas de relation d’ordre sur les clés, or une configuration de Mastermind est constituée de couleurs placées l’une à côté de l’autre comme ceci : □□□□. La ressemblance avec la notation entre crochets de Python est frappante :

□□□□ → [ | | | ] → [ , , , ]

Dans un cas comme celui-ci où les couleurs sont repérées par leurs abscisses, une liste ou un tuple sont mieux adaptés qu’un dictionnaire. Le tuple n’étant pas mutable, on va choisir une liste parce que pour construire une solution, couleur par couleur, on peut ainsi utiliser sa méthode append.

2. Projet de terminale

1. La configuration choisie par le codificateur est générée aléatoirement

Les configurations sont des listes de même taille p, qu’on peut modéliser mathématiquement par des p-uplets. L’ensemble de ces p-uplets est la puissance cartésienne p-ème de range(1,p+1). Pour obtenir une probabilité uniforme sur cet ensemble, on effectue une mesure produit d’intervalles d’entiers :

import random

def genere_configuration(n_couleurs,n_positions):
    return [random.randint(1,n_couleurs) for k in range(n_positions)]

def genere_configuration(n_couleurs,n_positions):
    conf = []
    for k in range(n_positions):
        conf.append(random.randint(1,n_couleurs))
    return conf

def genere_configuration(n_couleurs,n_positions):
    if n_positions==0:
        return []
    else:
        return genere_configuration(n_couleurs,n_positions-1)+[random.randint(1,n_couleurs)]

2. Programmation, en Python, du jeu Mastermind quand le décodeur est le joueur humain

Pour la question (c) on a choisi la structure de multiensemble, modélisée par un dictionnaire de Python, et par la fonction bag qui construit le multiensemble à partir d’une liste d’entiers. La fonction n_pions_communs calcule de fait l’intersection de deux multiensembles

import random


def genere_configuration(n_couleurs,n_positions):
    return [random.randint(1,n_couleurs) for k in range(n_positions)]

def n_bien_places(configuration_1,configuration_2):
    assert len(configuration_1)==len(configuration_2)
    bulls = 0
    for k in range(len(configuration_1)):
        if configuration_1[k]==configuration_2[k]:
            bulls += 1
    return bulls

def bag(liste):
    S = {}
    for elt in liste:
        if elt in S:
            S[elt] += 1
        else:
            S[elt] = 1
    return S

def n_pions_communs(configuration_1,configuration_2):
    assert len(configuration_1)==len(configuration_2)
    sac1 = bag(configuration_1)
    sac2 = bag(configuration_2)
    cows = 0
    for k in sac1:
        if k in sac2:
            cows += min(sac1[k],sac2[k])
    return cows

def n_noirs_blancs(configuration_1,configuration_2):
    bulls = n_bien_places(configuration_1,configuration_2)
    cows = n_pions_communs(configuration_1,configuration_2)
    return bulls,cows-bulls

def joueur_devine(n_couleurs=6,n_positions=4,n_essais=10):
    configuration_cachee = genere_configuration(n_couleurs,n_positions)
    print("Taille de la configuration cachée : ",n_positions)
    i = 0
    trouve = False
    while i<n_essais and not trouve:
        i+= 1
        m = input("Essai "+str(i)+" : ")
        essai = [int(c) for c in list(m)]
        bulls,cows = n_noirs_blancs(configuration_cachee,essai)
        print("    "+str(bulls)+" bien placés - "+str(cows)+" mal placés")
        trouve = (bulls==4)
    if trouve:
        return "Bravo vous avez trouvé en "+str(i)+" essais"
    else:
        return "Perdu vous avez épuisé vos "+str(n_essais)+" tentatives, bonne réponse = "+str(configuration_cachee)






print(joueur_devine())

3. TP en terminale avec n=p=5

4. Remédiation

Proposer de réécrire la fonction verification puis donner au résultat une note égale à la différence entre 45 et le nombre de lignes (hors commentaires) du script. Si la fonction occupe moins de 25 lignes la note est tronquée à 20.

1. Étude de l’ensemble de toutes les configurations

Le nombre de configurations possibles est celui des fonctions d’un ensemble à P éléments (les indices du tableau) vers un ensemble à N éléments (les couleurs associées à ces indices) donc il y en a N^P. Dans le cas « jeunes joueurs » cela fait 1296 configurations possibles et dans le cas « classique » cela en fait 32768. En supposant que chaque entier est codé sur 64 bits (soit 8 octets)

• une configuration pour N=6 occupe 6×8=48 octets,
• une configuration pour N=8 occupe 8×8=64 octets.

Il faut donc plus de 48×1296=62208 octets pour N=4 et plus de 64×32768=2097152 octets pour N=8, soit 2 mégaoctets. Dans ce dernier cas il n’est pas raisonnable de créer et mémoriser toutes les configurations. On peut par exemple estimer le temps que cela prendrait, avec la 3G, pour transmettre ces données.

2. Configurations en Python

La fonction suivante engendre toutes les configurations possibles :

def mystere(n_couleurs=6,n_positions=4):
    if n_positions==0:
        return [[]]
    else:
        l = []
        for element in mystere(n_couleurs,n_positions-1):
            for couleur in range(1,n_couleurs+1):
                l.append(element+[couleur])
        return l

On démontre cela par récurrence sur n_positions :

• Si n_positions = 0, la seule configuration possible est la configuration vide.
• Sinon, on suppose (hypothèse de récurrence) que la boucle sur element parcourt toutes les configurations de n_positions-1. Or toute configuration de n_positions s’obtient en prenant une configuration quelconque de n_positions-1 et en ajoutant une couleur quelconque en position n_positions. C’est précisément ce que fait la boucle sur couleur.

3. Plan de cours

1. Les listes
2. Les piles
3. Les files

4. La machine devine

Une liste est plus appropriée qu’une pile ou une file parce que celles-ci ne permettent pas facilement de choisir un des éléments au hasard (on n’y accède qu’au premier ou au dernier élément). L’ensemble configurations_possibles étant défini par compréhension, tous ses éléments jouent le même rôle l’un que l’autre et le choix de l’un d’entre eux est indifférent. On utilise ici la fonction choice qui effectue ce choix au hasard. On obtient le module suivant :

from random import choice

def mystere(n_couleurs=6,n_positions=4):
    if n_positions==0:
        return [[]]
    else:
        l = []
        for element in mystere(n_couleurs,n_positions-1):
            for couleur in range(1,n_couleurs+1):
                l.append(element+[couleur])
        return l

def noirs(configuration_1,configuration_2):
    assert len(configuration_1)==len(configuration_2)
    bulls = 0
    for k in range(len(configuration_1)):
        if configuration_1[k]==configuration_2[k]:
            bulls += 1
    return bulls

def bag(liste):
    S = {}
    for elt in liste:
        if elt in S:
            S[elt] += 1
        else:
            S[elt] = 1
    return S

def n_pions_communs(configuration_1,configuration_2):
    assert len(configuration_1)==len(configuration_2)
    sac1 = bag(configuration_1)
    sac2 = bag(configuration_2)
    cows = 0
    for k in sac1:
        if k in sac2:
            cows += min(sac1[k],sac2[k])
    return cows

def n_noirs_blancs(configuration_1,configuration_2):
    bulls = noirs(configuration_1,configuration_2)
    cows = n_pions_communs(configuration_1,configuration_2)
    return bulls,cows-bulls

def reduction_configurations_possibles(tentative,n_bien_places,n_mal_places,S):
    return [x for x in S if n_noirs_blancs(tentative,x)==(n_bien_places,n_mal_places)]

def machine_devine(n_couleurs=6,n_positions=4,n_essais=10):
    configurations_possibles = mystere(n_couleurs,n_positions)
    i = 0
    trouve = False
    while i<n_essais and not trouve:
        i += 1
        if len(configurations_possibles):
            tentative = choice(configurations_possibles)
            print("Je joue",tentative)
            n_bien_places = int(input("Combien ai-je de pions noirs ? "))
            n_mal_places = int(input("Combien ai-je de pions blancs ? "))
            configurations_possibles = reduction_configurations_possibles(tentative,n_bien_places,n_mal_places,configurations_possibles)
            trouve = (n_bien_places==4)
        else:
            return "Tricheur !"
    if trouve:
        return "J'ai gagné en "+str(i)+" tentatives"
    else:
        return "Je me croyais meilleur que ça"

print(machine_devine())

L’algorithme étudié dans cette partie, est à comparer avec celui-ci, de Donald Knuth :

1. La mystérieuse élève était en fait un lycéen suisse, dont voici le projet :

2. Baser une estimation sur le nombre moyen d’essais, c’est estimer une espérance : celle du nombre (aléatoire) d’essais nécessaires pour trouver la combinaison. La moyenne est un estimateur sans biais de l’espérance. Mais cette espérance est conditionnelle puisqu’une limite est fixée à 10 essais. On peut donc dire que la moyenne estime le nombre de tentatives nécessaires pour trouver la combinaison, sachant qu’on l’a effectivement trouvée.

3. Lorsque N ou P est important, le volume de données à traiter est rédhibitoirement important, et pour conserver une durée raisonnable des calculs, il est nécessaire de diminuer la taille de l’échantillon. Cela a pour effet de rendre les résultats moins fiables, selon l’inégalité de Bienaymé-Tchebychev par exemple.

4. La moyenne mesurée pour N=6 et P=4 est largement inférieure à 10 donc au vu de ces résultats statistiques, on peut estimer qu’il est peu probable que plus de 10 essais soient nécessaires en jouant au mieux. Fixer le nombre d’essais à 10 comporte donc a priori peu de risques (qu’il y ait une combinaison impossible à trouver même en jouant au mieux) dans ce cas.

5. Le troisième quartile est plus pertinent que la moyenne pour affiner la limite sur le nombre d’essais.

6. Mesurer la taille moyenne (au cours des essais successifs) de la liste des configurations possibles, est un bon indicateur du coût de l’algorithme, puisque cette liste doit être parcourue pour enlever les configurations impossibles.

7. L’algorithme fonctionne en deux phases :

1. Dans un premier temps, on joue des essais monochromes.Par exemple en ne jouant que des rouges, le nombre de pions noirs obtenus est le nombre de rouges dans la combinaison secrète. On s’arrête lorsque le total de pions noirs obtenus est 4, ce qui permet de connaître la combinaison dans le désordre en un maximum de N étapes.
2. Dans un second temps, on teste des configurations dont une seule couleur fait partie de la combinaison secrète. Par exemple si aucune des couleurs d’icelle n’est verte, on essaye rouge-vert-vert-vert.Cela ne devrait donner qu’un seul pion, et sa couleur permet de savoir où est le rouge.
   1. Pour la première couleur à placer, il suffit de P-1 essais maximum puisque si chaque essai n’a donné qu’un pion blanc, on en déduit que la bonne position est la dernière (non testée).
   2. Une fois connue cette position, on recommence avec les autres couleurs, et il n’y a que P-2 tests à effectuer, au maximum.
   3. Ensuite on teste les P-3 positions restantes pour la troisième couleur, etc.

Comme P-1+P-2+P-3+... = P(P-1)/2, la seconde phase de l’algorithme nécessite au maximum P(P-1)/2 essais et l’algorithme complet nécessite N+P(P-1)/2 essais au maximum.

Pour N=6 et P=4 l’algorithme effectue 12 essais maximum. Pour N=8 et P=5 l’algorithme effectue 18 essais maximum. Ces nombres étant supérieurs à 10 (maximum autorisé) l’algorithme ne permet pas toujours de trouver la bonne combinaison.

8. Le problème de recherche d’une configuration cachée est donc de complexité linéaire par rapport au nombre de couleurs et quadratique par rapport au nombre de positions.

1. Les problèmes soulevés dans cette partie sont similaires au jeu de Mastermind parce que, dans les deux cas, on extrait une information exhaustive que l’on croyait cachée. En fait, à chaque tour du jeu de Mastermind, de nouvelles informations permettent de réduire le champ des possibilités au point de finalement n’en avoir qu’une seule.

Mastermind est un jeu, et la meilleure façon d’utiliser un jeu est d’y jouer. Une fois que les élèves sont familiarisés avec le fonctionnement et le principe de ce jeu, on peut proposer cette comparaison :

2. Pour montrer en quoi des données personnelles permettent la réidentification, on peut voir par exemple

• Cette présentation de la QDN sur les réseaux sociaux (entre autres),
• l’examen de données Exif d’une photo, permettant de savoir à quel endroit précis se trouvait le photographe, et à quel instant précis aussi,
• le traçage par téléphone,
• L’achat de marchandises sur les sites de vente en ligne et leur AI suggérant des achats,
• l’application stopcovid,
• la notion de cookie (informatique)

3. Le partage de données anonymisées est d’intérêt public dans des cas comme :

• le calcul de données comme le seuil de pauvreté ou le salaire médian, qui nécessite de connaître la répartition des revenus,
• les données épidémiologiques des agences régionales de santé (qui ont récemment permis de classer les régions par couleur de déconfinement),
• la répartition des véhicules et leur vitesse, permettant de signaler les embouteillages aux usagers de la route se dirigeant vers ceux-ci (diminue le risque de carambolage en cas d’accident),
• le vote électronique...

4. La réidentification peut poser problème

• lorsqu’elle permet de connaître le dossier médical d’un.e citoyen.ne (non respect de la vie privée),
• lorsqu’elle permet de connaître les intentions de vote d’un.e citoyen.ne (non respect du secret de l’isoloir et de la démocratie),
• lorsqu’elle permet de classer une personne dans une catégorie ethnique menacée (par l’homophobie, l’antisémitisme etc),
• lorsqu’elle permet à des cambrioleurs de savoir ce qu’a acheté une personne,
• lorsqu’elle permet de localiser une célébrité (risque de harcèlement)...

5. Pour permettre aux élèves de voir les données personnelles stockées, on peut

• effectuer une navigation Internet à l’aide du navigateur intégré à CookieViz,
• visualiser les requêtes http à l’aide des outils de développement du navigateur (catégorie « réseau »),
• vider le cache du navigateur puis, au cours de la navigation, examiner son contenu à l’aide du système d’exploitation et d’un éditeur de texte

6. Cours d’1h30

Avant le cours, lecture de cet article à propos des dangers du jeu Pokémon Go et choix d’un groupe d’élèves volontaires pour un exposé résumant l’article.

En TD (avant ou peu après le cours), les élèves expérimentent cette activité en ligne. Et des parties de Mastermind les ont sensibilisés aux principes de la k-anonymisation sur la base du jeu sérieux : découverte spontanée des concepts par la simple pratique du jeu.

Le cours proprement dit commence par l’exposé sur Pokémon Go, puis aborde les notions suivantes :

• Cookies
• dialogue entre client et serveur (requêtes http permettant de transmettre des données)
• données Exif d’une photo
• géolocalisation et traçage
• avantages et inconvénients sociaux du traçage
• principe de la k-anonymisation
• Exemples :
  • le RGPD
  • la CNIL
  • l’initiative de Framasoft
  • l’application Stop covid
• Recommandations et bonnes pratiques (https, navigation anonyme, vidage régulier du cache, tor (réseau), blocage de cookies tiers etc)

7. QCM

Voici le QCM à faire en ligne ou en version papier :