8 août 2013

0 commentaire — commenter cet article
Article en partenariat avec

Qui est-ce ?

Le code de Hamming

Xavier Caruso

Chargé de Recherche CNRS, Université de Rennes I (page web)

L’IHP et INRIA ont présenté un stand commun au festival Futur en Seine qui a eu lieu du 13 au 16 juin 2013 à Paris. Cet article détaille une des animations qui a été présentée sur ce stand.

Peut-être connaissez-vous le jeu Qui est-ce ? dont le but est de retrouver, le plus vite possible, la personne que votre adversaire a choisie en lui posant des questions auxquelles il ne peut répondre que par oui ou non.

En voici une variante : choisissez un smiley parmi ceux sur l’image ci-dessous, répondez aux questions qui suivent et cliquez sur Devinez. La nouveauté est que vous avez le droit de mentir au plus une fois (vous n’êtes donc pas obligé de le faire).

Votre smiley est-il jaune  ? Votre smiley porte-t-il un nœud papillon  ?
Votre smiley porte-t-il des lunettes  ? Votre smiley tire-t-il la langue  ?
Votre smiley porte-t-il un chapeau  ? Les mains de votre smiley sont-elles visibles  ?
Votre smiley porte-t-il une moustache  ?

Comment ça marche ?

Sans mentir

Supposons pour commencer que la personne qui joue ne mente à aucune question. Dans ce cas, nous allons voir qu’il est possible de retrouver son smiley à l’aide simplement de quatre des sept questions qui sont :

  • Votre smiley porte-t-il un chapeau ?
  • Votre smiley porte-t-il un nœud papillon ?
  • Votre smiley tire-t-il la langue ?
  • Les mains de votre smiley sont-elles visibles ?

Pour nous en convaincre, disposons les smileys comme le montre la figure ci-contre. Ce faisant, savoir si le smiley porte, oui ou non, un chapeau nous indique si le smiley choisi par le joueur se trouve dans les deux dernières lignes ou dans les deux premières. Savoir ensuite s’il porte un nœud papillon permet de complètement déterminer la ligne dans laquelle se trouve le smiley : en effet, s’il porte un nœud papillon, il se situe sur la ligne du bas (parmi les deux retenues à l’étape précédente) tandis que, sinon, il est sur celle du haut.
De façon analogue, l’information sur la langue permet de déterminer si le smiley choisi est dans les deux premières colonnes ou dans les deux dernières et, en couplant cela avec l’information sur les mains, on arrive enfin à déterminer dans quelle colonne il se trouve exactement.
On a donc réussi à déterminer à la fois dans quelle ligne et dans quelle colonne se trouve le smiley ; on a donc bien retrouvé le smiley lui-même.

Remarque : Dans la pratique, avec un peu d’entraînement, on arrive très facilement à retrouver le smiley sur la figure d’origine sans avoir à raisonner sur les lignes et les colonnes.

Détecter les mensonges

C’est ici qu’interviennent les trois questions supplémentaires que nous n’avons pas encore utilisées ; informellement, leur rôle est de donner plus d’information que nécessaire au « devineur » (on parle souvent de redondance d’information) de façon à permettre à ce dernier de confronter les différentes réponses entre elles pour détecter les mensonges.

Avant d’expliquer précisément comment cela fonctionne sur notre jeu, considérons quelques instants un autre exemple simplifié pour illustrer l’idée de redondance d’information : supposons que le joueur n’ait le choix qu’entre deux smileys — que l’on prénommera Alice et Bob — mais que les règles soient identiques (on a le droit de mentir au plus une fois). Le devineur peut alors poser trois fois de suite la même question : As-tu choisi Alice ? Comme le joueur n’a le droit de mentir qu’une seule fois, il est clair que s’il répond au moins deux fois Oui, c’est qu’il a choisi Alice alors que, sinon, il a choisi Bob. On voit ici clairement, d’une part, qu’en l’absence de mensonge, poser une seule fois la question suffit à déterminer la personne choisie et, d’autre part, que poser la question de façon redondante permet de détecter un éventuel mensonge. En d’autres termes : une information confirmée par plusieurs sources (indépendantes) est plus sûre qu’une information qui provient d’un unique endroit.

Revenons à présent à notre jeu des seize smileys. La stratégie est alors nettement plus subtile. Elle consiste à former les trois groupes de quatre questions que voici :

  • Groupe 1 : couleur, chapeau, nœud papillon, mains
  • Groupe 2 : lunettes, chapeau, langue, mains
  • Groupe 3 : moustache, nœud papillon, langue, mains

Ces groupes vérifient la propriété importante que voici :


Sous l’hypothèse que l’on ne ment pas, pour chacun des seize smileys et pour chaque groupe de questions ci-dessus, il y a toujours un nombre pair de réponses positives (et un nombre pair de réponses négatives).

Illustrons cette propriété en regardant l’exemple du smiley en bas à droite, le seul à ne pas sourire. Il est jaune, a des lunettes, un chapeau, mais pas de nœud papillon, ne tire pas la langue et, enfin, on ne voit pas ses mains. Ainsi

  • dans le premier groupe de questions, il y a deux réponses positives (couleur et chapeau)
  • dans le deuxième groupe de questions, il y a aussi deux réponses positives (lunettes et chapeau)
  • dans le troisième groupe de questions, il n’y a aucun réponse positive

Dans tous les cas, le nombre de réponses positives est toujours pair. Vérifiez : cela fonctionne pour tous les smileys ! Il suit de ceci que, sous réserve que l’on ne mente pas, les réponses aux trois questions « secondaires » — portant sur la couleur, les lunettes et les moustaches — sont entièrement déterminées par les réponses aux quatre questions « principales » utilisées dans la partie Sans Mentir, à savoir les questions portant sur le chapeau, le nœud papillon, la langue et les mains. [1] On voit ainsi apparaître la redondance que nous évoquions précédemment sous une forme, certes, nettement plus subtile. De plus, comme nous allons le voir tout de suite, c’est cette redondance qui va permettre de détecter les erreurs grâce à une analyse du « défaut de parité » de réponses positives dans chacun des trois groupes.

Supposons en effet que l’on mente à la première question, c’est-à-dire à la question sur la couleur du smiley. En prenant en compte ce mensonge, on se rend compte qu’il y a maintenant, dans le premier groupe de questions, un nombre impair de réponses positives ; en effet, dans ce groupe, une réponse positive est changée en une réponse négative — ou le contraire — et ceci a pour conséquence d’augmenter ou de diminuer de 1 le nombre de réponses positives, le faisant ainsi passer d’un nombre pair à un nombre impair. Par contre, étant donné que la question sur la couleur n’apparaît ni dans le groupe 2, ni dans le groupe 3, ces deux groupes de questions admettent, eux, toujours un nombre pair de réponses positives.
De façon générale, mentir à une certaine question (et uniquement à celle-ci) a pour conséquence de modifier la parité des réponses positives dans tous les groupes (parmi les trois définis précédemment) où cette question apparaît.

Construisons à présent un tableau où l’on indique, pour chacune des questions, les groupes dans lesquelles elle apparaît :

Question sur Groupe 1 Groupe 2 Groupe 3
la couleur oui non non
les lunettes non oui non
le chapeau oui oui non
la moustache non non oui
le nœud papillon oui non oui
la langue non oui oui
les mains oui oui oui

On remarque que chaque combinaison de oui/non apparaît sur au plus une ligne du tableau [2]. Ainsi, si l’on sait dans quels groupes apparaît une certaine question et dans quels groupes elle n’apparaît pas, on est en mesure — simplement en consultant le tableau — de retrouver la question !

Or, à partir des réponses aux questions, on peut calculer, pour chacun des trois groupes, la parité du nombre de réponses positives et ainsi déterminer dans quels groupes apparaît la question à laquelle le joueur a menti (s’il a menti). D’après ce que nous venons de dire, on peut alors retrouver la question à laquelle le joueur a menti puis, après avoir corrigé cette réponse, retrouver le smiley choisi.

Un exemple

Un exemple étant souvent plus clair qu’une longue explication, voyons comment la méthode fonctionne dans le cas où les réponses aux sept posées sont les suivantes :

Votre smiley est-il jaune ? Votre smiley porte-t-il un nœud papillon ?
Votre smiley porte-t-il des lunettes ? Votre smiley tire-t-il la langue ?
Votre smiley porte-t-il un chapeau ? Les mains de votre smiley sont-elles visibles ?
Votre smiley porte-t-il une moustache ?  

On commence par compter, combien chaque groupe de questions a de réponses positives :

  • le premier (couleur, chapeau, nœud papillon, mains) en a une seule (mains)
  • le deuxième (lunettes, chapeau, langue, mains) en a trois (lunettes, langue, mains)
  • le troisième (moustache, nœud papillon, langue, mains) en a deux (langue, mains)

On est donc dans la situation où la question à laquelle le joueur a menti apparaît dans le groupe 1 (puisque 1 est impair), le groupe 2 (puisque 3 est impair) mais pas dans le groupe 3 (puisque 2 est pair). Un coup d’œil au tableau nous apprend que cela signifie que le joueur a menti à la question du chapeau. Après correction, les réponses aux questions deviennent donc :

Votre smiley est-il jaune ? Votre smiley porte-t-il un nœud papillon ?
Votre smiley porte-t-il des lunettes ? Votre smiley tire-t-il la langue ?
Votre smiley porte-t-il un chapeau ? Les mains de votre smiley sont-elles visibles ?
Votre smiley porte-t-il une moustache ?  

Il nous faut à présent trouver un smiley correspond à tous ces critères et, comme nous l’avons expliqué au début, on peut se concentrer uniquement sur la présence d’un chapeau, l’absence d’un nœud papillon, le fait que le smiley tire la langue et que l’on voit ses mains. Rapidement, on trouve :

L’astuce du 4, 2, 1

Pour terminer, je vous livre une petite astuce pour retrouver la question à laquelle le joueur a menti (s’il y en a une) sans passer par le tableau ci-dessus.

  • Retenez le nombre 1 si le premier groupe a un nombre impair de réponses positives.
  • Retenez le nombre 2 si le deuxième groupe a un nombre impair de réponses positives.
  • Retenez le nombre 4 si le troisième groupe a un nombre impair de réponses positives.
  • Additionnez les nombres retenus : le joueur a menti à la question dont le numéro [3] est le résultat de votre addition (si le résultat est 0, le joueur n’a pas menti).

Dans l’exemple que nous avons traité précédemment, les deux groupes incriminés étaient le premier et le deuxième. Il faut donc ajouter 1 et 2. On trouve 3 et c’est bien à la troisième question que le joueur avait menti.

À quoi ça sert ?

Le « tour de magie » que nous venons de présenter illustre ce que l’on appelle le code de Hamming dont l’utilité va bien au-delà de la recherche du smiley perdu. En réalité, il — ou, pour être plus précis, certaines de ses variantes, portant le nom générique de code correcteur d’erreurs — est utilisé dès lors que l’on souhaite soit enregistrer une information sur un support susceptible d’être altéré au cours du temps, soit transmettre une information à travers un canal pouvant subir des altérations. Pour des exemples concrets, pensez à :

  • un CD : une poussière ou une micro-rayure sur un CD sont susceptibles d’altérer les informations qui y sont gravées ;
  • un disque dur : un champ magnétique (produit par exemple par un aimant) passant à proximité est susceptible de corrompre certaines données ;
  • un téléphone portable ou le wifi : les communications par ondes peuvent — plus encore que les autres — subir des interférences dues par exemple aux intempéries.

Dans tous ces cas, on utilise donc un code correcteur d’erreurs pour protéger l’information que l’on souhaite transmettre. Pour expliquer de quoi il s’agit de façon plus précise, revenons à l’exemple des smileys. Supposons que l’information que l’on souhaite transmettre soit justement le smiley que l’on a choisi. Nous avons vu, dans la partie Sans mentir, que celui-ci peut être codé par une suite de quatre bits [4], à savoir les réponses aux questions portant sur le chapeau, le nœud papillon, la langue et, enfin, les mains.
Toutefois, si l’on transmet uniquement ces quatre bits, une erreur sur un bit corrompt le message (c’est-à-dire le smiley) de façon irréversible. Par contre si, au contraire, on transmet les sept bits correspondant aux réponses aux sept questions, une erreur — qui correspond à un mensonge — peut être détectée et même corrigée. Ainsi, si le canal que l’on utilise ne produit pas plus d’une erreur tous les sept bits (ce qui est très raisonnable), on peut reconstruire la totalité du message d’origine quand bien même il y aurait des altérations.

Notes

Cet article est très fortement inspiré de ce texte d’agrégation.

P.S. :

La rédaction d’Images des Mathématiques ainsi que l’auteur tiennent à remercier pour leur travail de relecture de ce texte, les personnes dont voici les pseudonymes : alchymic666, Pierre Monmarché, Walter, Xanthopoulos.

Notes

[1En effet, comme il doit y avoir un nombre pair de réponses positives dans le groupe 1, s’il y a un nombre pair (respectivement impair) de réponses positives aux trois questions sur le chapeau, le nœud papillon et les mains, la réponse à la question sur la couleur devra être Non (respectivement Oui). Un raisonnement identique avec les groupes 2 et 3 indique que les réponses aux questions sur les lunettes et les moustaches sont également déterminées.

[2Ceux qui connaissent la base 2 ne seront probablement pas étonnés, pas plus d’ailleurs que lorsque nous présenterons l’astuce 4, 2, 1 plus tard.

[3Les questions étant numérotées par colonne : de 1 à 4 pour les questions de la première colonne et de 5 à 7 pour les questions de la deuxième colonne.

[4Un bit désigne un chiffre valant soit 0, soit 1 ou, ce qui revient au même, un mot pouvant être soit oui, soit non.

Affiliation de l'auteur

Soyez le premier à déposer un commentaire

Pour citer cet article : Xavier Caruso, « Qui est-ce ? »Images des Mathématiques, CNRS, 2013.

En ligne, URL : http://images.math.cnrs.fr/Qui-est-ce.html