Notes of Bernard Chazelle’s inaugural lecture

L’Algorithmique et les sciences

Le\c con inaugurale de la Chaire d’informatique et de sciences numériques. Chaire annuelle : c’est un complément au système des titulaires et des cours. Il y a 5 chaires annuelles. Cette année, les titulaires sont

  1. Création artistique : Karol Beffa.
  2. Innovation technologique (Bettencourt) : Yves Bréchet.
  3. Développement durable : Annie Cazenave.
  4. Savoir contre pauvreté : Dominique Kerlédan.
  5. Informatique et sciences numériques (INRIA) : Bernard Chazelle.

1. Introduction, par Gérard Berry

4e édition de la Chaire d’informatique et de sciences numériques.

Parcours de Bernard Chazelle : Ecole des Mines, PhD Yale, puis Brown, puis Princeton.

Il a choisi l’algorithmique, au coeur de l’informatique. Thèse en géométrie algorithmique. Pionnier de l’exploitation de l’alea. Actuellement, algorithmes naturels : aide à comprendre les mécanismes des sciences émergentes.

Chazelle affirme que l’algorithmique va jouer pour la biologie le r\^ole que les équations ont joué pour la physique.

2. Les algorithmes font penser différemment

Niels Bohr avait un fer à cheval au dessus de son bureau : je n’y crois pas, mais on m’a dit que \c ca marche m\^eme si on n’y croit pas. Qu’on croie ou non à la révolution algorithmique, elle est en marche.

2.1. Tout le monde sait ce qu’est un algorithme

On apprend à l’école primaire celui pour multiplier deux entiers. Complexité {n^2}.

On peut faire mieux : {n\log n\log\log n}. Et m\^eme encore mieux.

2.2. Une industrie algorithmique

Google vend des regards. 95% du chiffre d’affaire est fait par deux algorithmes gratuits, PageRank, AdWords. Ils attirent des regards, d’où possibilité de vendre de la pub.

2.3. Convaincre

“Sur internet, personne ne sait que tu es un chien”. Problème métaphysique d’identité. Comme puis-je prouver que je suis moi ? Qu’est ce qu’une preuve ? N’importe quoi qui me convainc. Comment convaincre rapidement ? Faites confiance : renseignez vous auprès d’un expert. Le label confiance fait gagner du temps.

Tout cela n’est qu’une idée re\c cue, comme le montre le théorème PCP.

2.4. L’algorithme PCP

Theorem 1 {NP=PCP(\log n,1)}.

Plut\^ot que d’expliquer, j’illustre. L’hypothèse de Riemann porte sur les nombres premiers. Ils sont déterministes, mais donnent l’impression d’\^etre tirés au hasard. C’est ce que l’hypothèse de Riemann exprime précisément. J’ai trouvé une démonstration, je l’ai rédigée dans un langage formel, PCP, en 500 pages. Comment convaincre les matheux ? Piochez dans la preuve 5 lettres au hasard. Faites une dizaine de tests très simples (est-ce que toutes les lettres sont grecques…). Si tous sont positifs, vous acceptez ma démonstration. Le théorème affirme que vous avez moins d’une chance sur {10^9} de vous tromper. Aucune confiance requise.

C’est choquant. En France, on a la meilleure équipe au monde de vérification automatique de preuve (Gonthier). Le logiciel de Gonthier prend plus de temps, et vous avez besoin d’avoir confiance dans son logiciel.

2.5. Idées re\c cues

Il faut vérifier chaque étape de la preuve : non!

Il faut comprendre la rhétorique compliquée de l’analyse complexe : non!

2.6. Idées de la démonstration du théorème PCP

A chaque énoncé intermédiaire, on ajoute toutes ses conséquences logiques de taille polyn\^omiale. Cela rallonge la preuve, mais pas dramatiquement. S’il y a une erreur, on peut la contourner : elle est diffuse, comme sur les CDRoms codés avec un code correcteur d’erreurs.

2.7. Connaissance

Le théorème PCP ne dit que vrai ou faux, mais il n’explique rien.

Sur la tombe de Hilbert : Wir müssen wissen, wir werden wissen. Le théorème PCP ajoute : mais nous n’y comprendrons rien.

La connaissance, c’est une croyance vraie et justifiée.

Le théorème PCP rend la vérification triviale. C’est l’aléa qui le rend possible.

3. Histoire de l’ingénierie

L’ingénierie, ce sont des pratiques théorisées. On a fait des ponts avant de comprendre la mécanique.

L’informatique, c’est l’inverse, on a fait la théorie avant la pratique.

3.1. Naissance de l’informatique

Fine Hall, Princeton, 1936, le thé à 15h. On y croise Kurt Gödel, Albert Einstein, John von Neumann, Alonso Church, Alan Turing.

Turing a inventé l’ordinateur. Un ordinateur, c’est un train, à plusieurs états. La voie ferrée a des symboles sur les traverses. Il y a un automate (une série d’instructions) qui dit au train quoi faire, dans tous les cas de figure. Turing à l’idée d’écrire la liste d’instructions sur la voie ferrée. Le train devient universel : il est capable d’exécuter n’importe qu’elle série d’instructions.

Thèse de Church-Turing : ils démontrent que le train est capable de calculer tout ce qu’on peut calculer.

3.2. Indécidabilité

Theorem 2 (Gödel) Toute axiomatique calculable qui permet de définir les entiers contient des vérités indémontrables.

Les machines de Turing (invention d’ingénieur) permettent d’en donner une preuve bien plus courte que la preuve originale de Gödel (logicien).

3.3. Dualité

Concept clé : la dualité. Programme et données ne sont que des interprétations différentes de la m\^eme chose. On les lit différemment, le programme par ce qu’il fait, et les données par ce qu’elles sont.

En bio, protéines et ADN présentent la m\^eme dualité.

En physique, équations différentielles et mesures expérimentales.

3.4. Invariance

L’univers est fait d’invariance. Les mathématiques sont la science de la symétrie. Emmy Noether : invariance et symétrie, c’est la m\^eme chose.

Eugene Wigner : efficacité déraisonnable des maths en physique.

(C’est Wigner qui a signé mon contrat d’embauche à Princeton, et Serge Haroche mon contrat au Collège de France. Sans les prix Nobel de physique, je ne pourrais pas gagner ma vie).

Israel Gelfand : encore plus déraisonnable, leur inefficacité en biologie.

Pourquoi ? Dans le monde vivant, au fil des milliards d’années, la symétrie s’est perdue, d’où une grande complexité descriptive.

3.5. Complexité

Le terme a de multiples significations.

  1. Pour tout un chacun, est complexe ce qui est difficile à comprendre.
  2. Complexité de phénomènes physiques imbriqués : la météo.
  3. Complexité algorithmique.
  4. Complexité descriptive : elle est très basse en physique. Des milliards de molécules, mais une seule équation permet de comprendre la chaleur.

4. Le monde vivant parle le langage des algorithmes naturels

11ème Commandement : “De m\^eme que tu étudies les équations avec des équations, tu étudieras les algorithmes avec des algorithmes”.

4.1. Systèmes d’influence

Je me concentre sur le cas diffusif.

Huygens 1665 : 3 métronomes de m\^eme fréquence et de phases distinctes, posés sur une planche posée sur 2 canettes, finissent par rapprocher leurs phases. Aisé à expliquer par des équations. Essentiel au fonctionnement du coeur. (Gyorgy Ligeti : morceau de musique à 100 métronomes).

Autre point de vue : 3 agents qui se parlent. Un algorithme qui dit qui communique avec qui à quel moment (chaque agent peut avoir le sien), très général (théorie du premier ordre des réels). Chaque agent évolue en se rapprochant du centre de gravité de ses proches (ceux à qui il parle). Expérimentalement, on constate que le graphe devient progressivement périodique.

Autrement dit, quelle que soit la sophistication du cerveau, on finit par tourner en rond. Nous recyclons nos idées à perpétuité…

Theorem 3 (Chazelle 2012) Le systèmes d’influence diffusifs, avec forte probabilité, convergent vers la périodicité. Pourtant, il y en a qui sont Turing complets, mais ceux-ci sont rares.

Criticalité (comme dans les systèmes de spin) : entropie contre énergie. La région frontière (critique) est fractale. Presque s\^urement, l’entropie perd la partie.

4.2. Preuve

Analyse de bifurcation, et renormalisation, les deux de nature algorithmique.

Un algorithme, c’est un arbre infini, avec des branchements. On a besoin de comprendre la statistique du nombre de branches (entropie). Les branches ont un volume, on a besoin de comprendre à quelle vitesse ce volume décro\^\i t (dissipation de l’énergie). Pour cela, on a des opérations de chirurgie, de renormalisation, un langage arborateur. On étudie une décomposition récursive de l’arbre, algorithmique et non équationnelle (elle ne se fait pas indépendamment du système).

Le compilateur repose sur deux algorithmes,

  1. Un algorithme financier : les agents échangent de l’argent (se substitue à une fonction de Lyapunov).
  2. Un algorithme de flots : les agents mesurent où va leur influence.

4.3. Vol d’oiseau

Modèle de Vicsek-Cucker-Smale. Utilise un algorithme de passage de témoin.

Theorem 4 (Chazelle 2009)

About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See http://www.math.ens.fr/metric2011/
This entry was posted in Course. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s