Au Joyeux Ragondin

Google a, en son temps, révolutionné le monde des moteurs de recherche: on est passé d'un monde où les créateurs de sites décidaient de comment ils seraient indexés à un monde où ce sont les utilisateurs des sites qui décident cela (en faisant des liens). Depuis, Google a été une entreprise innovante qui a développé ses services de recherches à beaucoup d'autres domaines (dont le très impressionant Google Maps), mais le domaine de la recherche de sites webs semble stagner.

Quelles améliorations serait-il possible d'apporter à court termes à un moteur de recherche ? N'étant pas spécialiste, je ne saurais pas me prononcer sur les changements fondamentaux, mais j'entrevois une possibilité intéressante. Admettons, par exemple, que je cherche le sens mathématique du mot « boule ». Une recherche sur ce simple mot ne sera pas suffisante, car il a beaucoup trop de sens différents. Actuellement, il faut jouer à deviner quels autres mots peuvent être présents sur la page qui m'intéresse. C'est parfois possible (« boule topologie » est plus satisfaisant), mais pas toujours. Ce qui manque, c'est la possibilité de spécifier un contexte sémantique. Malheureusement, pour qu'un moteur de recherche permette de spécifier un contexte sémantique, il faudrait d'abord qu'il comprenne le sens du texte... à moins que...

Google renouvelé le domaine de la recherche en introduisant le concept de PageRank: chaque site se voit attribué un score, et il transmet une partie de son score aux sites vers lesquels il fait des liens. Cela permet au moteur de recherche de juger (approximativement) de la popularité et de la pertinance des sites sans devoir en comprendre le contenu. Il serait tout à fait possible d'étendre ce concept, et d'autoriser en plus du score de transmettre des concepts. Par exemple, le site MathWorld aurait un score élevé pour des concepts comme « mathématiques » ou « glossaire », alors que Libération aurait un score élevé en « actualités » et « vulgarisation ». En transmettant une partie de leurs scores aux sites vers lesquels ils lient, chaque site marqué sémantiquement contribuerait à construire des catégories se superposant. Ainsi, je pourrais rechercher « Fermat » avec le contexte « mathématiques » et tomber sur la définition des théorèmes de fermat sur MathWorld, ou bien avec le contexte « actualités » et tomber sur les annonces concernant la preuve d'Andrew Wiles.

Une des propriétés du réseau Internet fait que ce genre de méthode est réellement applicable: le graphe correspondant aux liens hypertexte entre les sites Web est constitué d'un petit nombre de sommets très connectés (des hubs), et la plupart des autres sommets sont connectés par un court chemin à un de ces hubs. Par conséquent, en isolant les sommets les plus connectés et en leur attribuant des concepts à la main, on peut recouvrir une partie raisonnablement importante du Web.

Les plus outranciers des capitalibéralistes ne se gènent pas pour le dire: si des gens sont pauvres, c'est de leur faute, après tout ils n'avaient qu'à gagner de l'argent. On a donc d'une part les gens qui savent se prendre en main et qui ont une vie décente, et d'autre part des gens improductifs que la société est bien bonne d'entretenir.

Seulement, quand le capitalisme décide de faire dans le social sans verser dans la charité, on obtient des résultats surprenants. Les banques accordants des micro-crédits en sont un bon exemple: il s'agit d'accorder des prets de relativement petites sommes à des gens auxquels jamais une "vraie" banque n'accepterait de prêter quoi que ce soit, afin de leur donner l'élan financier nécessaire pour se sortir de la merde, n'ayons pas peur des mots. C'est ainsi qu'on voit fleurir des mini-entreprises de quelques personnes, et que la quasi-totalité des prêts sont remboursés, ce qui fait de ces banques un service rentable. Les premiers à avoir lancé une banque de ce type (ou les premiers médiatisés, pour ce que j'en sais) sont la Grammeen Bank, au Bangladesh, et on aurait pu croire que ce genre de démarche resterait cantonné aux pays en développement. Pas du tout, ça existe aussi aux États-Unis et en France, et ça marche tout aussi bien, semble-t-il.

(Une particularité intéressante de la Grameen Bank était de ne prêter qu'aux femmes, je vous laisse réfléchir là dessus).

Concernant le projet de constitution européenne, on a d'abord entendu que voter "non" freinerait le développement de l'Europe. C'est un argument pertinent car les opposants au traité viennent d'horizons parfois éloignés: le "non" risque de l'emporter en France parce que le traité n'est pas assez "social", alors que l'Angleterre est globalement contre parce que le traité est trop "social". La renégociation en cas de rejet peut donc sembler difficile (j'y reviendrai).

Seulement, il est vite apparu que même si la France et d'autres pays rejetaient le traité, l'Europe pourrait bien continuer sans nous. Alors le nouvel argument à la mode, c'est de défendre la Puissance de la France. Pour paraphraser notre président, on a le choix entre voter "oui" et être des leaders de l'Europe, ou voter "non" et être laissés de côté.

Tout d'abord, j'ai du mal à comprendre comment on peut être leaders si notre avis nous est dicté par les autres pays. En toute logique, l'avis d'un pays puissant et important est écouté et apprécié, or on nous dit que si notre avis n'est pas celui des autres pays, nous serons ignorés. Ce n'est pas très caractéristique d'un leader. Mais admettons.

Quand bien même nous pourrions être des leaders, est-ce opportun ? Je suppose que chaque état de l'Union aimerait bien faire partie des leaders, et je ne vois pas trop quels critères devraient nous permettre de décider qui le peut. La France fait historiquement partie des pays qui ont contribué à la formation de l'UE, mais doit-on en espérer une reconnaissance particulière ? J'ai du mal à comprendre pour quelle raison nous devrions défendre la puissance de notre nation au lieu de tenter une répartition équitable du pouvoir entre tous les états membres.

Selon moi, le problème n'est pas que la France perde de l'influence en cas de rejet du traité, mais que la majorité des états membres puissent décider de se passer de l'avis de quelques états et de continuer sans eux. Qu'il s'agisse d'ignorer l'avis de la France ou de la Pologne, peu importe, dans les deux cas c'est aussi dérangeant. Voulons-nous d'une Europe où le choix des pays à écouter évolue en fonction des décisions à prendre ? Il me semble que voter oui par peur que cela n'arrive, c'est avouer que l'on ne croit pas en une Europe démocratique. L'avenir nous dira peut-être si cette peur est justifiée, mais je ne considère pas que cet argument là justifie un "oui, mais" au référendum.

Le problème de coloration de graphe (peut-on colorier les sommets d'un graphe avec k couleurs sans que deux sommets voisins aient la même couleur) est un des problèmes classiques d'algorithmique qui sont connus pour être NP-complets. La célèbre conjecture (P != NP) postule que pour certains problèmes, dont les problèmes NP-complets, il n'existe pas d'algorithme les résolvant en temps polynomial. La preuve de cette conjecture permettrait de répondre, enfin, à la question "existe-t-il des problèmes difficiles". Bien entendu, cette preuve a toujours défié mathématiciens et informaticiens.

Jusqu'à recemment en tout cas. Le mois dernier, le mathématicien Edwin Eutch, se basant sur des travaux d'Alfred Tarski, a proposé un algorithme polynomial permettant de décider la k-colorabilité. Dans ce genre de cas, il ne faut pas se précipiter: de nombreuses preuves ont été avancées, et rejetées. Mais après de nombreuses relectures, l'article a été accepté et publié, ce qui est déjà beaucoup. Inutile de préciser que la communauté est en émoi.

L'article est bien entendu très technique, et je vous invite à le lire pour vous faire une opinion, mais je vais quand même en esquisser l'idée générale. L'obstacle dans tous les problèmes NP-complets est l'explosion combinatoire qui fait que l'on ne peut pas (dans un temps raisonnable) explorer tous les cas possibles. Par exemple dans le cas de la k-coloration, il est possible de vérifier toutes les colorations possibles pour un graphe donné, mais leur nombre est trop élevé pour que cela soit une technique raisonnable. Tarski et Eutch se basent sur un résultat de théorie de l'information formulé par J.P. Pernod et F. Nyues qui prétend qu'il est possible de ne considérer qu'une partie très réduite de l'information sans diminuer la qualité du résultat. L'algorithme effectue une décomposition du graphe d'entrée en un nombre réduit de sous-graphes appelés motifs, et dont on connaît le nombre chromatique. Ces motifs (dont la figure ci-dessous donne des exemples) sont ensuite recomposés sans que la coloration soit rendue impropre, et ce en temps polynomial.