Shannon, information et Sudoku

Par Vincent Gripon, chercheur à Télécom Bretagne.
Tribune initialement publiée dans The Conversation en collaboration avec le Blog Binaire. 2016 est l’année Shannon – Claude Shannon aurait eu 100 ans cette année. Il est le génial inventeur de la théorie de l’information, qui a des impacts importants en informatique, par exemple pour la compression de données. Binaire a demandé à Vincent Gripon de nous expliquer le concept théorique « d’information » au sens de Shannon. Essayez de sentir le lien avec ce que nous appelons aujourd’hui « information » ou « données ».

[divider style= »normal » top= »5″ bottom= »5″]

[dropcap]S[/dropcap]ignal, données, contenu, sémantique, pas facile de s’y retrouver… Il se cache pourtant une grandeur mesurable parmi ces quatre notions, étudiée depuis le milieu du XX^e siècle par les mathématiciens, les physiciens et les informaticiens. Cette grandeur, c’est l’information. Mais c’est quoi, au juste, un élément d’information ?

Réfléchissez-y. Vous pouvez vous représenter ce qu’est un mètre, un litre, un gramme, mais pouvez- vous déterminer ce qu’est une unité d’information ? Par exemple, si je vous dis que la milliardième décimale de π est un 9, combien vous ai-je transmis d’unités d’information ?

Le comble de cet exemple est que je ne peux moi-même pas vous répondre. Ou plus exactement tout dépend : si vous le saviez déjà alors je ne vous ai transmis aucune information. À l’opposé, si vous n’en aviez pas la moindre idée alors je vous ai transmis suffisamment d’unités d’information pour déterminer lequel des 10 chiffres possibles est le bon.

C’est contre-intuitif, mais la notion d’information est étroitement liée à celle d’événements aléatoires. Pour mieux comprendre, prenons un exemple. Je tire à pile ou face une pièce de monnaie et je vous communique le résultat. A priori, il y a autant de chances pour que je vous dise « pile » ou « face ». Avoir deux possibilités avec la même probabilité correspond exactement à une unité binaire d’information. On l’appelle le Shannon, en hommage au père de la théorie de l’information. Si je lance maintenant deux fois de suite ma pièce et vous communique les deux résultats obtenus, je vous transmettrai donc deux Shannons. Si par contre ma pièce de monnaie est irrégulière et a plus de chances de donner « pile » que « face » (et que vous le savez), alors je ne vous transmettrai plus exactement deux Shannons d’information, mais un peu moins, car vous pouvez prédire partiellement le résultat. Dans le cas extrême où ma pièce de monnaie est truquée et ne peut que donner « face », je ne vous transmets plus aucune information. S’il n’y a plus d’aléatoire, il n’y a plus d’information !

À lire également sur le blog : Théorie de la simplicité : apprendra la pertinence aux IA

En général, la quantité d’unités d’information est relative à celui qui la reçoit. C’est le cas avec l’exemple de la milliardième décimale de Pi. En mathématiques, on est davantage intéressé par une notion universelle d’information, définie indépendamment de celui qui la manipule. C’est le cas avec l’exemple de la pièce de monnaie : tant que la pièce n’a pas été lancée, personne ne peut prédire le résultat.

En théorie de l’information, tout part donc du principe que la réalisation d’un événement aléatoire ayant peu de chances de se produire porte beaucoup d’unités d’information, alors que celle d’un événement aléatoire ayant beaucoup de chances de se produire n’en porte presque pas. C’est logique non ? Si je vous dis que demain le soleil va se lever, je ne vous aurais pas transmis beaucoup de Shannons. Si je vous dis que mon numéro de carte bleue se termine par 142857, je vous en aurais transmis beaucoup.

Information et données

Tous les jours nous échangeons, notamment par le biais de l’Internet, des quantités astronomiques de données, codées sous la forme de valeurs binaires (des « bits »), mais bien moins d’unités d’information.

Pour comprendre la notion d’information, il est essentiel de la différencier de celle de donnée. Prenons un exemple. J’ai une amie qui vient d’accoucher. Je lui envoie un SMS pour lui demander le sexe du nouveau-né. Dans ma vision des choses, il y a autant de chances pour qu’il s’agisse d’un garçon ou d’une fille. Sa réponse me transmettra donc exactement un Shannon. Pour me répondre, elle m’enverra probablement une phrase constituée de plusieurs caractères, chacun étant représenté par plusieurs bits. Je vais donc recevoir plusieurs dizaines de bits de données pour un seul Shannon.

Notre cerveau est coutumier du fait. On estime à cent millions de bits par seconde la quantité de données transmises depuis le cortex visuel vers les aires profondes de notre néocortex. La plupart de ces données nous sont complètement inutiles, et portent par ailleurs bien peu d’éléments d’information.

Faire en sorte qu’un bit de donnée corresponde exactement à un Shannon, c’est le rêve des spécialistes de la compression. En effet, compresser, c’est réduire la taille des données en maintenant exactement la même quantité d’information. C’est par exemple ce que vous faites quand vous compressez un fichier informatique. Un résultat fondamental de la théorie de l’information est qu’un bit de donnée ne peut pas correspondre à plus d’un Shannon. Par exemple, si je crée un fichier informatique en y inscrivant des valeurs 0 ou 1 et en tirant chaque bit à pile ou face, je ne pourrai pas le compresser : il contiendra déjà autant de bits que de Shannons.

À lire également sur le blog : Claude Shannon, un héritage au-delà du numérique

La redondance

Une information n’est utile que si elle est manipulée. En pratique il s’agit souvent de la transmettre ou de la stocker. Et ce n’est pas si simple !

Quand on discute dans un endroit bruyant, on est coutumier du fait de manquer des bouts de conversation. Il en va de même pour les systèmes numériques. Toute transmission d’un message est sujette à altérations. La cause ? Les interférences, les atténuations, les erreurs dans les systèmes traitant l’information… Il est alors nécessaire de la protéger.

Du fait de la miniaturisation des composants et de leur multiplication, les systèmes de stockage ont perdu en fiabilité. Il ne s’agit pas uniquement de pertes de données, mais aussi de corruption de leur contenu. Ils requièrent donc des mécanismes de protection de l’information. C’est en particulier le cas des circuits électroniques que nous utilisons au quotidien.

Pour protéger l’information vis-à-vis des perturbations, on utilise de la « redondance ». C’est une forme subtile de répétition. Les théoriciens de la redondance ont imaginé plein de stratégies efficaces pour créer de la redondance. Aujourd’hui la plupart des systèmes utilisés s’appuient sur le principe du codage distribué, un principe qui vous est bien plus familier que vous ne l’imaginez…

Le meilleur exemple de codage distribué, c’est la grille de Sudoku. Le principe du Sudoku est une façon efficace de protection de l’information. En effet, le but du jeu consiste à retrouver le contenu des cases effacées à partir de celui des cases restantes : c’est exactement la robustesse que l’on recherche dans les systèmes numériques. La grille de Sudoku n’est pas définie par une seule règle très compliquée, mais plutôt en combinant 27 règles simples : 9 pour les lignes, 9 pour les colonnes, et 9 pour les petits carrés.

Chacune de ces règles prise indépendamment des autres n’est pas très robuste. Prenez par exemple une ligne d’une grille de Sudoku sur laquelle manquent deux chiffres. Vous pouvez déduire des chiffres restants quels sont les chiffres manquants, mais vous ne pouvez pas retrouver leurs emplacements. Par contre, quand vous mettez ensemble les 27 règles, vous parvenez à retrouver les chiffres manquants de la grille, même dans certaines situations où ils représentent plus de la moitié des 81 cases.

Où sont le 2 et le 6 ?

Si vous avez tout compris à cet article, la prochaine fois que vous résoudrez un Sudoku vous saurez que vous ne cherchez pas de l’information manquante, mais des données manquantes, et la prochaine fois que vous ferez répéter au téléphone, vous ne ferez qu’augmenter le taux de redondance !