Penser, modéliser et maîtriser le calcul informatique

Penser, modéliser et maîtriserle calcul informatique

Gérard Berry

Chaire Informatique et sciences numériques

Collège de France, 19

novembre 2009

19/11/2009 2Collège de France, G. Berry,

Le calcul humain assisté

19/11/2009 3Collège de France, G. Berry,

Curt Herzstark, 1936-1945

19/11/2009 4Collège de France, G. Berry,

La révolution du microprocesseur

Si vous m’instruisez bien, je sais tout faire tout seul,en tournant moi-même la manivelle !

Si vous m’instruisez bien, je sais tout faire tout seul,en tournant moi-même la manivelle !

coeur 1

coeur 2

19/11/2009 5Collège de France, G. Berry,

La révolution du microprocesseur

Rapidité, exactitude, stupidité

coeur 1

coeur 2

Rapidité

Exactitude

Stupidité

Maîtrise ?

Modèles de calcul

19/11/2009 6Collège de France, G. Berry,

Sans la main => sans la pensée !

Intuition

RigueurLenteur

Calculer sur le calcul

19/11/2009 7Collège de France, G. Berry,

Anatomie d’un modèle de calcul

raisonnementsur la correction

penséealgorithmique

conception etprogrammation

implantation optimisation vérification

machines langagesnoyau intuitif etmathématique

19/11/2009 8Collège de France, G. Berry,

Pourquoi plusieurs modèles de calcul,alors que tous les ordinateurs

semblent marcher pareil ?

1. Modèles de la calculabilité

2. Modèles séquentiels

3. Modèles parallèles

4. Modèles diffus

19/11/2009 9Collège de France, G. Berry,

Quatre classes de modèles

19/11/2009 10Collège de France, G. Berry,

La sémantique : concepts ↔ symboles

• Domaine des symboles 34 et 56 sont des symboles en représentation décimale et + le symbole d’un algorithme

4+6 3+5+1 → 1 0

Machine : 34+56

→ 0 9

0 9 0

• Domaine des concepts : la somme du nombre 34 et du nombre 56 est le nombre 90

Il n’y a pas de nombres dans un ordinateurrien que des symboles

19/11/2009 11Collège de France, G. Berry,

Symboles

Conceptssomme du nombre « 34 » et du nombre « 56 »

nombre « 90 »

34+56

notation

090

dénotation

manivelle

Le diagramme sémantique

Pour comprendre l’informatique, il faut arriver àêtre aussi bête qu’un ordinateur

7+57+5

19/11/2009 12Collège de France, G. Berry,

Causalité des calculs

(3+4)+(8-3)(3+4)+(8-3)

7+(8-3) (3+4)+5

12

résidu

création

La causalité détermine la liberté du calcul

• Déterminisme : un seul résultat– calcul mathématique standard– circuits électroniques– pilotage d’avions, conduite de voitures, etc.

19/11/2009 13Collège de France, G. Berry,

Déterminisme / non-déterminisme

• Non-déterminisme : plusieurs résultats– navigateur Internet, moteur de recherches, etc.– incertitude : on ne peut pas connaître en même temps la

position et le contenu d’une page Web– encore quelques voitures (hélas)

2 3 4 5 6 7 8 9 10 1112 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 3132 33 34 35 36 37 38 39 40 4142 43 44 45 46 47 48 49 50 51

Un nombre est premier s’il n’a pas

d’autre diviseur que 1 et lui-même

19/11/2009 14Collège de France, G. Berry,

Le crible d’Eratosthène

2 3 4 5 6 7 8 9 10 1112 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 3132 33 34 35 36 37 38 39 40 4142 43 44 45 46 47 48 49 50 51

19/11/2009 15Collège de France, G. Berry,

Le crible d’Eratosthène

Un nombre est premier s’il n’a pas

d’autre diviseur que 1 et lui-même

2 3 4 5 6 7 8 9 10 1112 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 3132 33 34 35 36 37 38 39 40 4142 43 44 45 46 47 48 49 50 51

2 3 4 5 6 7 8 9 10 1112 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 3132 33 34 35 36 37 38 39 40 4142 43 44 45 46 47 48 49 50 51

2 3 4 5 6 7 8 9 10 1112 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 3132 33 34 35 36 37 38 39 40 4142 43 44 45 46 47 48 49 50 51

19/11/2009 16Collège de France, G. Berry,

Le crible d’Eratosthène

Un nombre est premier s’il n’a pas

d’autre diviseur que 1 et lui-même

19/11/2009 17Collège de France, G. Berry,

Le crible de Darwin : p, kp → p

39

7

28

4

7

7

7

2

Banâtre - Le Métayer : GAMMABerry - Boudol : CHAM

19/11/2009 18Collège de France, G. Berry,

Comparaison des cribles

séquentialitécausalité complexe

déterminisme du calculdéterminisme du résultat

terminaison trivialelimité au fini

parallélisme massifcausalité minimale

non-déterminisme du calculdéterminisme du résultatterminaison probabiliste

passe à l’infini

1. Par les machines machines de Turing, de von Neumann,

automates cellulaires, pavages du plan, etc.

2. Par les langages et calculs algébriquesdéfinitions récursives de fonctions

-calcul

3. Par les classes algébriques de fonctions fermetures par opérations appropriées

Toutes ces définitions sont équivalentes

19/11/2009 19Collège de France, G. Berry,

Comment définir la calculabilité ?

Thèse de Church-Turing : Toute nouvelle définition restera équivalente

1 4 95 2 3 • • • • • • 1 4 95 2 3 • • • • • • 1 4 95 2 3 • • • • • • 1 4 95 2 3 • • • • • •

19/11/2009 20Collège de France, G. Berry,

La machine de Turing

1 8 95 2 3 • • • • • •

A : 3 → D, AA : 4 → G, BA : 8 → 3, A

B : 3 → D, C A : 7 → G, BA : 7 → 2, A

DGE

non-déterminisme

arrêt

Théorème : il existe une machine universelle U qui permet de simuler toute machine sur toute donnée

19/11/2009 21Collège de France, G. Berry,

Machine universelle

D o n n é e s

MD o n n é e sD o c M

U

Le programme enregistré est la clef de l’informatique

Théorème : il n’existe pas de machine testant si une machine M s’arrête sur une donnée D

19/11/2009 22Collège de France, G. Berry,

Indécidabilité de l’Arrêt

• A s’arrête toujours• A rend 1 si M s’arrête• A rend 0 si M boucle

A

D o n n é e s

MD o n n é e sD o c M

Toute propriété non-triviale est indécidable

19/11/2009 23Collège de France, G. Berry,

Alan Turing (1912-1954)

1936 : grands théorèmes

1940 : casse le code allemand Enigma

1952 : condamné pour homosexualité castré chimiquement

1954 : suicide (?)

2009 : excuses de Gordon Brown

A Turing qui aimait tant l’argument diagonal,donnons le prix Turing à titre posthume !

• Fact (m) si m1 alors 1 sinon Mult (m, Fact(m1))

Un langage : la récursion générale

19/11/2009 24Collège de France, G. Berry,

• Add (m, n) si m0 alors n sinon si n0 alors m sinon (Add (m1, n1)1)1

• Mult (m, n) si m0 alors 0 sinon si m1 alors n sinon Add (Mult(m1, n), n)

f(2) (x. x+1) (2)

25/11/2009 25G. Berry, Collège de France,

Le -calcul (Church 1936)

•-notation f x. x+1

• Notation classique des fonctions f [ x x+1 ]

g [ y y2 ]

g○f [ z g(f(z)) ] [ z (z+1)2 ]

f(2) (x. x+1) (2)

g(3) (y. y2) (3)32 9g y. y2

Donner un vrai statut à la notation des fonctions

2+1 3

○ g f z. (y. y2) ((x. x+1) (z))

25/11/2009 26G. Berry, Collège de France,

○ g f (u. v. z. u(v(z))) (y. y2) (x. x+1)

f x. x+1 g y. y2

○ u. v. z. u(v(z))

○ g f (u. v. z. u(v(z))) (y. y2) (x. x+1)

○ g f z. (y. y2) ((x. x+1) (z))

○ g f z. (y. y2) (z+1)

○ g f z. (z+1)2

○ g f z. (y. y2) (z+1)

g○f : [ z (z+1)2 ]

○ g f

19/11/2009 27Collège de France, G. Berry,

Le -calcul pur

• x, y, z,... : variables • x. M : abstraction fonction de x de corps M• (MN) : application d’une fonction à un argument

• (x. M) N M[N/x] : -réduction

mais ce calcul est vide ! Où sont donc les entiers, la récursion, etc ?

19/11/2009 28Collège de France, G. Berry,

0 f. x. x1 f. x. fx2 f. x. f(fx)...

n f. x. f n(x) = f(f(...f(x)...))

...

+1 n. f. x.f (nfx)

-1 λn.λf.λx. n (λg.λh.h(fg)) (λu.x) (λv.v)

Le nombre n devient l’algorithme qui applique n fois une fonction f à son argument x

19/11/2009 29Collège de France, G. Berry,

Récursion et point fixe

let rec Fact m si m1 alors 1 sinon Mult (m, Fact (m1))

Fact = FACT (Fact) - équation de point fixe

FACT f. m. si m1 alors 1 sinon Mult (m, f (m1))

Fact = Y (FACT) avec Y = (x. y.y(xxy)) (x. y.y(xxy))

Pour comprendre comment un calcul évolue,le mieux est de comprendre ce qu’il laisse fixe !

19/11/2009 30Collège de France, G. Berry,

La carte du -calcul

relations avecla logique formelle

algorithmiquerécursive

programmationfonctionnelle

machines virtuelles

CAM, Krivine

SCHEMECAML Haskell

Javascript

compilation et optimisationdes langages fonctionnels

LCF, HOLIsabelle, CoQ

-calculdomaines de Scott

19/11/2009 31Collège de France, G. Berry,

La carte du -calcul

relations avecla logique formelle

algorithmiquerécursive

programmationfonctionnelle

machines virtuelles

CAM, Krivine

SCHEMECAML Haskell

Javascript

compilation et optimisationdes langages fonctionnels

LCF, HOLIsabelle, CoQ

-calculdomaines de ScottJean-Jacques Lévy

19/11/2009 32Collège de France, G. Berry,

La carte du -calcul

relations avecla logique formelle

algorithmiquerécursive

programmationfonctionnelle

machines virtuelles

CAM, Krivine

SCHEMECAML Haskell

Javascript

compilation et optimisationdes langages fonctionnels

LCF, HOLIsabelle, CoQ

-calculdomaines de Scott

Gérard Huet

-calculdomaines de Scott

=> génie logicien19/11/2009 33Collège de France, G. Berry,

Le théorème des 4 couleurs en CoQ

Preuve omise, évidente mais longue

• 1852 Guthrie

• 1976 Appel – Haken

Georges Gonthier

• 2005 Gonthier (en CoQ)

19/11/2009 34Collège de France, G. Berry,

Systèmes d’états finis

• Expressions régulières : (ab+b)*baba abba bba abbabba ...

• Automates finis

circuits électroniquessystèmes embarqués, réseaux

interfaces homme-machineanalyse des langues, du génome, ...

• Langages évolués (Statecharts, Esterel, SCADE)

19/11/2009 35Collège de France, G. Berry,

La carte des systèmes d’états finis

logiquestemporelles

théorie deslangages

états / transitionsgrammaires

automatescircuits

électroniques

Lex, YaccEsterel

Statecharts

automateslangages réguliers

langages → automateslangages → circuits

model-checking

optimisationbooléenne

Joseph SifakisAmir Pnueli

19/11/2009 36Collège de France, G. Berry,

La carte des systèmes d’états finis

logiquestemporelles

théorie deslangages

états / transitionsgrammaires

automatescircuits

électroniques

Lex, YaccEsterel

Statecharts

automateslangages réguliers

langages → automateslangages → circuits

model-checking

optimisationbooléenne

Dominique Perrin

• Communication entre machines distantes– unité centrale et périphériques (PC → imprimante)– émetteurs et receveurs multiples : réseaux

19/11/2009 37Collège de France, G. Berry,

Pourquoi le parallélisme

• Partage de ressources– PC: plusieurs tâches partagent le CPU, les disques, etc.– stockage d’information dans les grands réseaux.

• Amélioration de performances– machines parallèles, grilles, nuages– circuits : caches, spéculation, multicœurs, SoCs, etc.

19/11/2009 38Collège de France, G. Berry,

Pourquoi le parallélisme

• Contrôle d’objets avec parallélisme physique– avion : ~10 gouvernes, 2 réacteurs, 3 trains, etc.

• Contrôle de grands systèmes– contrôle aérien– signalisation ferroviaire, aiguillages– contrôle de la circulation en ville

• Redondance pour la sécurité et la disponibilité

communication, coopération, compétitionsécurité des données et communications

19/11/2009 39Collège de France, G. Berry,

Interblocage (deadlock)

19/11/2009 40Collège de France, G. Berry,

Famine (starvation)

13:0613:0312:57

19/11/2009 41Collège de France, G. Berry,

Le ski au 20 e siècle

13:00

19/11/2009 42Collège de France, G. Berry,

Le ski au 20 e siècle, avec protocole

13:0613:0312:5713:00

Le drapeau ajoute le lien de causalité manquant

19/11/2009 43Collège de France, G. Berry,

Le ski au 21 e siècle

On peut même prévenir d’avance qu’on sera en retard !

13:0613:0312:5713:00

19/11/2009 44Collège de France, G. Berry,

Processus et communication

P Q

R S

• Réseaux de processus statiques ou dynamiques• Trois types de communication

– asynchrone : temps quelconque– synchrone : temps conceptuellement nul– vibratoire : temps non nul prévisible

19/11/2009 45Collège de France, G. Berry,

Parallélismes synchrone et vibratoire

SynchroneMusiciens et spectateurs négligent la vitesse du son

VibratoireMais les acousticiens règlent sa propagation

19/11/2009 46Collège de France, G. Berry,

Applications : embarqué et circuits

SCADE

circuits électroniques

Nicolas Halbwachs

modèle / langage Lustre

Jean Vuillemin

nombres 2-adiques

19/11/2009 47Collège de France, G. Berry,

Mémoire partagée

P Q

R S

Mémoire

19/11/2009 48Collège de France, G. Berry,

P QP

P

P

Q

Q

Q

P

P

Michel Raynal

Brisure decausalité

• P and Q sont asynchrone, mais communiquent de façon localement synchrone

• A ce moment, chacun sait ce que sait l’autre

• Les rendezvous sont ordonnancés de manière non-déterministe

19/11/2009 49Collège de France, G. Berry,

Rendezvous = information partagée

P Q

19/11/2009 50Collège de France, G. Berry,

CSP = séquentiel + rendez-vous

P Q

R S

Bien contrôlable, mais souvent trop lourd

• Découplage de l’émetteur et du récepteur– plus de parallélisme– mais introduction de latence imprévisible– et comportement total plus complexe

19/11/2009 51Collège de France, G. Berry,

Communication par files d’attente

P Q

• Applications– transmission dans les réseaux– traitement du signal – interfaces homme / machine, Web

• nœuds déterministes, files non bornées

• ordonnancement non-déterministe arbitraire

• Mais résultat déterministe !Magnifique

sémantique mathématique

19/11/2009 52Collège de France, G. Berry,

Réseaux de Kahn

P

Q

R

19/11/2009 53Collège de France, G. Berry,

Réseaux graphiques

Réseaux de Petri

Source Univ. Stuttgart

Réseaux d’automates

19/11/2009 54Collège de France, G. Berry,

Le -calcul de Milner : chimie + calcul

Bob@cdf.fr<“vous habitez chez vos parents?”>

Alice@cdf.fr

Bob@cdf.fr

Annuaireadr<Alice> rep<alice@cdf.fr>alice@cdf.fr<Bob@cdf.fr>alice@cdf.fr<Bonjour>

Cedric Fournet

D’un ordinateur, on ne sort jamais que ce qu’on y a misD’un ordinateur, on ne sort jamais que ce qu’on y a mis

D’Internet, je sors ce que le reste du monde y a mis

Homo bureaucratus

Homo Internetus

5519/11/2009 55Collège de France, G. Berry,

19/11/2009 56Collège de France, G. Berry,

Communautés, pair-à-pair et réseaux virtuels

Anne-Marie Kermarrec

19/11/2009 57Collège de France, G. Berry,

Calcul diffus : alerte aux pucerons !

• infestation massive par pucerons enfouis partout• qui peuvent communiquer entre eux• Comment les programmer et les coordonner ?

Manuel Serrano

• De nombreux principes de calcul parallèle– trains de spikes (vibratoires)– évaluations probabilistes– discussions asynchrones– synchronisation d’horloges

• Un mélange synchrone / asynchrone– conscient séquentiel, inconscient parallèle

• Une robustesse fondamentale– apprentissage (semi-) spontané– beaucoup de pièces en panne– plasticité cérébrale

19/11/2009 58Collège de France, G. Berry,

Comment calcule notre cerveau ?

19/11/2009 59Collège de France, G. Berry,

Neurosciences computationnelles=> nouveaux principes de calcul informatique=> commande d’actions par l’activité cérébrale

=> couplages circuits / neurones

19/11/2009 60Collège de France, G. Berry,

• Le 20e siècle a été celui de l’énergie et du moteur

• Le 21e sera celui de l’information et du calcul– qu’il faut donc étudier à fond

• L’épidémie numériques gagne les sciences– mathématiques numériques G. Gonthier, E. Ghys, …– Physique numérique, cf L.I. Antoine Georges, 2009– Bioinformatique, informatique médicale– …

19/11/2009 61Collège de France, G. Berry,

Conclusion

Faire ce qu’ on veut en étant aussi bête qu’un ordinateur demande beaucoup d’intelligence

A mon directeur de thèse

Maurice Nivat

A mes thésards préférés

Pierre-Louis CurienLaurent CosseratGeorges Gonthier

Olivier Tardieu

A la bande du bâtiment 8 de l’INRIA Rocquencourt

Bruno CourcellePhilippe Flajolet

Gérard HuetGilles Kahn

GustaveJean-Jacques Lévy

Ron RivestJean-Marc Steyaert

Jean Vuillemin

A la bande de l’Ecole des Mines / INRIA Sophia-Antipolis

Yves BertotGérard Boudol

Frédéric BoussinotIlaria Castellani

Jean-Paul MarmoratJean-Paul RigaultDavide SangiorgiRobert de Simone

Valérie Roy

A la bande de Digital Equipment

Patrice BertinFrançois Bourdoncle

Olivier CoudertJean-Christophe Madre

Mark ShandHervé Touati

Jean Vuillemin

A la bande de Grenoble

Paul CaspiNicolas Halbwachs

Florence MaraninchiPascal Raymond

Joseph Sifakis

A la bande d’Esterel Technologies

Amar BoualiXavier FornariBruno PaganoMarc Perreaut

... et tous les autres

Et à mes collègues étrangers

Mike KishinevskyEdward Lee

David McQueenRobin MilnerDana Scott

Gordon PlotkinEllen Sentovich

Ravi Sethi

Remerciements spéciaux