savoirs

Toute la connaissance humaine sous le sapin

Le président de l'EPFL Martin Vetterli tient désormais une chronique dans «L'Illustré» et sur le site du «Temps». Il se souvient d'un cadeau de Noël, un dictionnaire, qui ouvrait la réflexion sur les boucles

Lorsque j’étais enfant, mes parents m’ont offert un dictionnaire pour Noël. J’ai pensé que c’était le meilleur cadeau possible, car ainsi je pouvais apprendre tout ce qu’il était possible de savoir au moyen d’un seul livre. J’ai donc immédiatement commencé à lire, mais je dois avouer que j’ai rapidement renoncé.

C’est que, quand je me suis mis à lire le premier article sous la lettre A, la définition m’a fait sauter à une autre page (en suivant les mots figurant dans l’article). Par exemple, supposons que vous cherchiez le mot «dictionnaire». La définition est: «Un livre qui recense tous les mots d’une langue» (ou quelque chose du genre). Vous allez donc chercher le mot «livre» et les mots qui le définissent, puis «recenser» et sa description, etc.

Me voici pris dans une boucle

On touche là au nœud du problème: puisqu’il existe un nombre fini de mots, je vais forcément rencontrer, à un moment donné, un mot que j’ai déjà lu avant. Ainsi, je me trouvais indéfiniment pris dans une boucle à l’intérieur du dictionnaire. En d’autres termes, j’étais revenu là où j’avais commencé, mais sans avoir lu tout le livre! Je me suis alors demandé combien il y avait de cycles dans le livre, et quelle était leur taille.

Du point de vue des technologies de l’information, c’est vraiment un problème intéressant. Imaginez un ensemble d’objets, et un ensemble de connexions entre ces objets; ces objets pourraient être par exemple des villes, et les connexions représenteraient une route reliant deux villes. Dans notre dictionnaire, les objets sont des mots, et les connexions, les liens entre les articles du dictionnaire et tous les autres mots utilisés dans sa définition. Les informaticiens aiment appeler un tel arrangement d’objets un «graphe», et le problème qui se pose à nous consiste à trouver un parcours cyclique à l’intérieur du graphe.

Dans un dictionnaire physique, la recherche est laborieuse et il faut souvent tourner de nombreuses pages. Tandis que dans un dictionnaire en ligne, tel que Wikipédia, vous pouvez écrire un algorithme qui suit automatiquement les liens d’une définition, et des définitions successives, pour voir si un cycle existe.

Lire tout Wiki sans tomber dans une boucle

Et voici un point intéressant: il existe de nombreuses manières de programmer un algorithme sur un ordinateur dédié à la recherche de cycles et, même si vous êtes plus ou moins efficace, il est facile de déterminer la longueur du cycle le plus court. Supposons toutefois que je veuille découvrir si je peux lire l’ensemble de Wikipédia dans un très grand cycle, sans me retrouver coincé dans une petite boucle, comme cela m’est arrivé lors de ce fameux Noël. Eh bien, il s’avère que ce problème est d’un tout autre ordre!

Un cycle qui touche tous les objets une seule fois dans un graphe s’appelle un cycle hamiltonien. Et déterminer si un cycle hamiltonien existe ou non est réellement l’un des problèmes les plus ardus en science informatique, pour lequel il n’existe aucune solution efficace connue (voire, selon certains, possible). La seule solution consisterait donc à explorer tous les cycles l’un après l’autre; seulement voilà: si vous deviez compter combien il y a de cycles dans Wikipédia, vous vous retrouveriez avec un nombre de cycles infiniment plus grand que le nombre de particules dans l’univers.


Cette chronique est parue dans L'Illustré.

Précédente chronique: 2017, l’odyssée de la reconnaissance vocale

Publicité