Nos blogs

Quelle est la quantité minimale d’informations nécessaires pour décrire un oiseau, le roman Les Misérables de Victor Hugo ou tout simplement une suite aléatoire de chiffres ? Tel est le genre de question que se posent les mathématiciens qui explorent la théorie algorithmique de l’information.

Si le terme « information » revêt de nombreux sens dans le langage courant, selon le domaine où il est employé, les mathématiques lui accordent une signification bien précise : il s’agit de la quantité de description nécessaire pour spécifier un objet.

Il existe deux grandes théories de l’information, avec des approches radicalement différentes. D’une part, celle du mathématicien américain Claude Shannon (1916-2001), publiée en 1948, et qui repose sur les probabilités. D’autre part, la théorie algorithmique de l’information, aussi appelée théorie de la complexité de Kolmogorov, du nom du Russe Andreï Kolmogorov (1903-1987), qui en publia l’article fondateur en 19651.

Deux théories différentes…

Pour expliquer ce qui les différencie, recourons à une pièce d’un euro, qui a une chance sur deux de tomber sur face (codé par « 1 »), une chance sur deux de tomber sur pile (codé par « 0 »), et que l’on jetterait 100 fois d’affilée. En théorie, tout résultat d’une série de 100 jets a la même chance de survenir, chacun avec une probabilité de 0,5 à la puissance 100.

La théorie de Shannon est de nature probabiliste : elle repose sur les probabilités, établies a priori (avant même le premier jet), pour quantifier le contenu en information du message constitué par la série de lancers. La théorie de Kolmogorov adopte une approche radicalement différente, a posteriori, explique Laurent Bienvenu, chargé de recherche au Laboratoire Bordelais de Recherche en Informatique2. 

« Dans l’objet que j’ai obtenu, par exemple une suite de 1 et de 0, quelle est la quantité d’information contenue ? Telle est la question que pose cette théorie. A l’inverse de celle de Shannon, qui s’arrête une fois que les pièces ont été lancées ».

La différence est notable : si une suite du type « 1 0 0 1 1 0 1 0 0 0 etc. » a autant de chances de survenir que celle composée de 100 « 0 », elle possède, selon la théorie de Kolmogorov, une quantité d’information plus élevée. En revanche, les chances étant identiques d’obtenir l’une ou l’autre de ces deux suites, la théorie de Shannon ne verra guère de différence entre elles.

… mais liées

Or, malgré leurs approches diamétralement différentes, les deux théories ne sont pas dénuées de liens, comme l’ont montré des travaux menés par le chercheur Andreï Romashchenko, chargé de recherche au Laboratoire d’informatique, de robotique et de microélectronique de Montpellier3, au début des années 2000.

« Les lois qui sont vérifiées par la théorie de l’information de Shannon, en recourant aux probabilités, demeurent inchangées dans la théorie algorithmique  de l’information, lorsqu’on mesure l’information contenue dans l’objet », explique Alexander Shen, directeur de recherche émérite au LIRMM. Fruit d’une collaboration entre le LIRMM, le LaBRI et l’Institut de Recherche en Informatique Fondamentale4, le projet ANR FLITTLA5, coordonné par Andreï Romashchenko, consistait d’ailleurs à mieux comprendre les liens complexes entre la théorie algorithmique de l’information et la théorie de Shannon.

A l’origine de sa théorie algorithmique, il s’agissait pour Andreï Kolmogorov de mieux comprendre ce qui, dans un objet, produit une impression d’aléatoire (comme une série désordonnée de 0 et de 1), ou au contraire de régularité (une suite de 100 « 0 »).. Le mathématicien russe, pourtant l’un des pionniers des probabilités, « n'était pas complètement satisfait par les fondations de la théorie de Shannon », explique Andreï Romashchenko. « Il a continué de réfléchir à cette question, et dans les années 1960, il est parvenu à l'idée que l’idée d'algorithme permettait de mieux expliquer la différence entre les choses aléatoires et celles qui ne le sont pas ».

A cette théorie se rattache la notion de « complexité de Kolmogorov », à savoir la taille du plus court programme permettant de générer l’objet décrit. Exemple, pour des cas simples, de ce type d’instructions : « 100 fois 0 », ou bien « 50 fois ‘1 0’ », etc. Si le concept semble aisé à manier pour un objet peu complexe, il devient plus ardu lorsque son caractère aléatoire prend de l’ampleur.

Une théorie en quête de nouvelles dimensions

Pour les chercheurs, bien d’autres défis se profilent à l’horizon afin d’enrichir la théorie algorithmique de l’information. « En l’état de cette théorie, la question du temps de calcul est complètement balayée », constate Laurent Bienvenu. « On s’intéresse à la plus courte description possible d’un objet, mais ni à la manière de l’obtenir, ni au temps requis pour reconstituer l’objet lui-même. Une compression sera peut-être très courte, mais il faudra un million d’années à un ordinateur classique pour qu’il puisse reconstituer l’objet ! ».

Dans le cadre du projet FLITTLA, les chercheurs ont d’ailleurs tracé de premières pistes de réflexion à ce sujet, en tentant d’établir un lien entre la taille de la compression (complexité de Kolmogorov) et le temps requis pour « reconstituer » l’objet décrit. « C'est un peu comme la notice d’un Titanic de 6.000 pièces de Lego. La notice est courte, mais il faut beaucoup de temps pour construire l’objet », ajoute Laurent Bienvenu.

Jeu de construction, puzzle… l’analogie n’est pas sans évoquer la recherche fondamentale en mathématiques. « Notre travail consiste à lire des articles, à en discuter ensemble, à assister à des séminaires, à passer beaucoup de temps avec un papier et un crayon pour voir si notre raisonnement fonctionne », explique Laurent Bienvenu. « Si ça ne marche pas, on essaie autre chose… parfois, cela ne donne rien, mais d’autres fois si ! ».

-----------------------------------------------------------------------------

Ces recherches ont été financées en tout ou partie, par l’Agence Nationale de la Recherche (ANR) au titre de l'ANR FLITTLA - AAPG2021. Cette communication est réalisée et financée dans le cadre de l’appel à projet Science Avec et Pour la Société - Culture Scientifique Technique et Industrielle pour les projets JCJC et PRC des appels à projets génériques 2021 (SAPS-CSTI JCJC et PRC AAPG 21).