Griffonnages

Là

« L'ordinateur quantique peut-il tout résoudre ? » telle est la question en une du numéro de mai de « Pour la science »

Comme je n'ai pas trop le temps de bloguer, et que le web 2.0, c'est le « user generated content » discussions et questions libres en commentaires. Qu'en avez-vous pensé ? Quelles questions vous restent-ils ? L'ordinateur quantique, qu'en pensez-vous, que voulez-vous savoir sur lui ?

Un billets de commentaires, j'espère.

Paul Erdős (1913-1996) était un mathématicien hongrois aussi prolifique qu'exentrique. Tellement prolifique que presque tous les chercheurs sont reliés à lui, et quelque soit le domaine, c'est assez impressionnant. C'est ce que montre le nombre de Erdős.

Paul Erdős a son nombre à 0.

Le nombre de Erdős de ses coauteurs est 1.

Le nombre de Erdős de la seconde génération de ses coauteurs est 2.

Et ainsi de suite....

Il y a 201 personnes de rang 1 et plus de 8100 personnes de rang 2. Vu le nombre de personnes impliquées et le rythme des publications il est difficile de connaître son nombre de Erdős. Je ne sais pas exactement où je suis. Je connais un chemin de longueur 5, et je sais qu'il n'y en a pas de longueur 3. Bref, je suis 4 ou 5. Pour la petite histoire, je colabore actuellement avec quelqu'un qui colabore avec une personne de rang 1. Si ces deux colaborations sont fertiles, je deviendrais de rang 3, ce qui ma foi n'est pas si mal vu mon âge.

Ce nombre est finalement rarement très grand et il montre le phénomène small-worlds de la recherche mondiale. Le même phénomène que l'on peut observer dans la blogosphère. Tom Roud est arrivé à l'observer en partie en utilisans le mème « 6 choses insignifiantes »

Ronald Munroe d'XKCD, ma "lecture" du lundi, mercredi et vendredi matin dont j'avais déjà dit le plus grand bien, s'est laché aujourd'hui, Convincing Pickup Line :

Tooltip: Check it out; I've sex with someone who's had sex with someone who's written with Paul Erdős

[Image sous Licence CC BY-NC 2.5]

Et si vous vous demandez à quoi ressemble un graphe des relations dans la vraie vie (parce que vous vous dites que c'est un excélent moyen de comprendre les dynamiques de propagation des MST, je ne peux pas imaginer une autre raison) une enquête a été faite dans un lycée américain.

(Cliquez sur l'image pour agrandir)

J'espère que vous avez aimé ce petit parcours des mathématiques à la biologie en passant par moi et la typologie de la blogosphère. Les sciences, c'est bien !

Sur twitter, lieu de plaintes mutuelles entre BeRewt et moi^[1]

<celui> Vous devrez notamment joindre l'avis d'un industriel montrant son intérêt dans le projet Je fais de la recherche fondamentale, pauv'con
<BeRewt> File moi pas ton projet, tu m'salis

Le Turing Award, c'est notre prix Nobel à nous, les informaticiens. Ça ne nous va pas si mal, dans le domaine, c'est vraiment la classe d'en avoir un. C'est pareil pour les matheux, chez eux la récompense suprême, c'est la médaille Fields. Comme ici ce n'est pas le Nouvel Obs, je ne vous dirai pas pourquoi il n'y aurait pas de prix Nobel en math.

Seulement voilà, sorti de la communauté, personne ne sait ce que c'est que le Turing Award, et ce n'est même pas médiatisé : pas un article dans le Monde, ni dans Libération, ni dans le Figaro.^[1] Et pourtant, le Turing Award 2007 a été décerné ce 4 février à Joseph Sifakis, un chercheur (franco)-hellénique, fondateur de verimag, un des laboratoires de recherche en informatique de Grenoble.

Il partage ce prix avec deux américains, E. Clarke et E. Emerson, pour leurs travaux sur le model checking.

Voici la vérité, je vous aurais bien entretenu du model checking, mais je n'y connais presque rien. J'ai fait un peu de googlage et tout, et quand j'ai vu qu'il y avait des modèles de Kripke, j'ai abandonné. Je garde des mes cours de logique (en licence) un souvenir confus : je ne me suis jamais bien entendu avec cette branche de l'informatique théorique. Et pourtant j'apprends que ça fait parti des cours de bases. Là, je m'étouffe.

Nous mettons là le doigt sur une spécificité de l'informatique théorique française, il y a une forte communauté de (pour faire simple) logiciens, et tous les dérivés : λ-μ-π-calculeurs, logisticiens exotiques (systèmes temporels, logique épistémique, etc...) et même des catégoriciens.

Leur graal, c'est d'arriver à comprendre ce qu'est un programme. Non, ne rigolez pas, ce n'est pas facile. Il faut dire que le passage de messieurs Curry et Howard a été déterminant : ils ont montré qu'un programme, c'est une preuve. Et de là découlent tout un tas de problématiques : un programme qui ne plante pas, c'est un démonstration juste. Et une démonstration juste, ce n'est rien d'autre que de la logique. Et les applications sont nombreuses : développement de nouveaux langages de programmation pour lesquels il est possible de certifier des propriétés de justesse sur le programme,^[2] assistants de preuves automatiques^[3], toute une panoplie de méthodes de vérification (dont le model checking fait parti). Ce sont ces gens là qu'il faut remercier pour avoir montré comment vérifier que les métros sans conducteurs ne font pas n'importe quoi.

Mais quand on lit ce qu'ils produisent, tout de suite, cela devient très abscons.

Cela donne un peu une vision à deux têtes à la recherche française en informatique théorique, groso modo, les logiciens d'un côté, les algorithmiciens de l'autre. Avec une douce guéguerre entre les deux. Par exemple, l'Université Paris 7 se retrouve avec deux labos : le LIAFA (Algo) et le PPS (Logique) et ceux qui passent par le MPRI (Master Parisien de Recherche en Informatique), master de recherche de Polytechnique, ÉNS Ulm & Cachan, P7) expliquent qu'ils ne connaissent qu'une seule moitié de la promo tellement le cloisonnement existe.

Donc, je suis heureux que cette prestigieuse récompense soit enfin décernée à un chercheur qui travaille dans un laboratoire français, je fais remarquer que c'est un chercheur au CNRS, ce qui montre combien cette institution est obsolète, et espère qu'un prochain Turing Award sera rapidement décerné à un algorithmicien français. Évidement, cela ne remet pas en question l'adage qui veut que les logiciens sombrent inéluctablement dans la folie.

Je vais finir par penser que le Turing Award, n'est pas l'agenda des medias. Si seulement il y avait un prix Nobel d'informatique ! Mais moi, à faire de l'informatique quantique, je pourrais toujours avoir un Nobel de physique en sus de mon Turing Award.

Comme funnyface, je trouve qu'énoncer le sujet de ma thèse en société, ça ne se fait pas. Ça relève de la vulgarité et de la prétention. (et en plus, il n'y a pas Foucault dedans). Mais les gens sont curieux, ils insistent Allez, Celui, dis-moi le sujet de ta thèse, alors je suis obligé d'assurer mes arrières Es-tu bien sûr que tu veux le savoir ?. Là j'espère voir poindre une lueur de doute, mais ma question a toujours l'effet inverse : Bien sûr que je veux savoir !

Erreur fatale, blue screen of the death, Et c'est sur moi que ça retombe, les gens attendent des explications, de la vulgarisation, comme si je n'avais pas dit assez de gros mots comme ça.

Dorénavant, j'ai la solution, je répondrai va voir sur mon blog, y a la réponse C'est le niveau 1 de la pédagogie, mais ma vie sociale est à ce prix-là.

Je fais de la cryptographie, c'est-à-dire coder des messages, les envoyer, les décoder. Le truc important, c'est qu'un espion, s'il a le message codé ne puisse pas le décoder. C'est pour ça que vous pouvez commander mes cadeaux de noël sur Internet sans (trop de) risque.

Mais voilà, il y a une saloperie, il y a un théorème d'impossibilité. C'est un théorème qui commence par Il est impossible de ; et dans mon cas c'est Il est impossible de faire un protocole de cryptographie inconditionnellement sûr. Au jeu du chat et de la souris, il est impossible à la souris de trouver un endroit sûr. Ça m'emmerde pour mes cadeaux.

Donc ce qu'on cherche, c'est un protocole où pour l'espion (que l'on appelle Ève entre nous) il soit très difficile de décoder le message. C'est à dire que le problème décoder le message soit compliqué. Ça un vrai truc d'informaticien, on a des milliers de problèmes qu'on passe notre temps à trier, à ranger, à classer. Et des classes de problèmes, nous en avons à revendre. Il y a en tellement, un bestiaire impressionnant, qu'il existe même un zoo. Il y en a pour tous les goûts : des classes de problèmes extrêmement simples aux plus ardus.

Les deux classes les plus connues répondent incontestablement aux doux noms de P et de NP. Dans P il y a les problèmes pas trop durs, dans NP des problèmes (que l'on croit) difficiles. La question la plus fondamentale aujourd'hui en informatique, c'est de démontrer que P≠NP.

Une immense partie de la cryptographie actuelle est basée sur un algorithme qui s'appelle RSA (trouvé par Rivest, Shamir et Adleman). Le problème qu'Ève doit résoudre pour espionner la conversation est dans NP. C'est sacrément compliqué pour elle de le faire, même si ce n'est pas impossible.

Un exemple ? Si je vous dit que 159623548 x 5597469526 = 893487945561998248, vous prenez votre calculatrice pour vérifier, c'est facile, la multiplication est dans P. Maintenant, je vous demande de trouver deux nombres à 10 chiffres tels qu'en les multipliant vous obtenez 893487945561998248, c'est une autre histoire, c'est compliqué, c'est dans NP. C'est sur principe que reposent les algorithmes modernes. (À la différence près qu'au lieu d'utiliser des nombres de 10 chiffres, on utilise des nombres de plusieurs centaines de chiffres)

Mais voilà, en 1994, Peter Shor a montré que si Ève avait un ordinateur quantique, alors elle peut facilement écouter les conversations. Un chat avec un ordinateur quantique, c'est un chat qui coure plus vite. Il ne fait rien de magique, rien de plus que ce qu'il pouvait faire avant, il le fait juste plus vite. Donc ce que j'essaye de faire, c'est de trouver un protocole, mieux qu'RSA (en tout cas sur le papier) où Ève, même avec un ordinateur quantique, ne puisse pas écouter la conversation.

Dit comme ça, on dirait que je ne sais pas trop où je vais. C'est faux. Il y a rarement quelque chose de fondamentalement nouveau en recherche. Je joue au Légo, j'assemble des briques qui existent déjà, mais à la Celui, j'utilise de vieux outils, même si personne ne les utilise de cette manière. C'est ce qui continue de m'émerveiller, chaque fois que j'ajoute un élément, çà me donne une idée de comment continuer. De temps en temps, il faut casser un bout pour le reconstruire différemment, mais la maison immanquablement prend forme.

Quand on y réfléchis bien, je ne suis qu'un gamin qui continue de jouer au Légo, pour que vous puissiez continuer vos activités d'adultes qui nécessitent le secret. À chacun sa place, et j'aime la mienne.

Ça fait une bonne introduction pour ma thèse, non ?

J'en ai marre qu'on me demande s'il y a encore quelque chose à trouver en informatique. Les âmes plus prudentes me demande s'il y a encore quelque chose de fondamental à trouver.

Je pourrais parler de P et d'NP, mais à quoi bon rentrer dans la théorie alors qu'il y a un exemple que tout le monde comprend : la multiplication. Parce que, accrochez-vous, on ne connaît pas l'algorithme le plus rapide^[1] pour faire une multiplication.^[2], ça va, c'est assez fondamental ?

Le meilleur algorithme connu, celui de Martin Fürer, date de février 2007. Il améliore l'algorithme de Schönage et Strassen de 1971. C'est vous dire si c'est compliqué. Puisqu'on y est, c'est pareil pour la division : on ne connaît pas non plus l'algorithme le plus rapide (mais sait comment le fabriquer à partir de celui de la multiplication).