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é


Curt Herzstark, 1936-1945


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


La révolution du microprocesseur

Rapidité, exactitude, stupidité

coeur 1

coeur 2

Rapidité

Exactitude

Stupidité

Maîtrise ?

Modèles de calcul


Sans la main => sans la pensée !

Intuition

RigueurLenteur

Calculer sur le calcul


Anatomie d’un modèle de calcul

raisonnementsur la correction

penséealgorithmique

conception etprogrammation

implantation optimisation vérification

machines langagesnoyau intuitif etmathématique


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


Quatre classes de modèles


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


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


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.


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


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





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






Le crible de Darwin : p, kp → p

39

7

28

4

7

7

7

2

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


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


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 • • • • • •


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


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


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


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


• 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


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 ?


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


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 !


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


La carte du -calcul




machines virtuelles

CAM, Krivine

SCHEMECAML Haskell

Javascript



-calculdomaines de ScottJean-Jacques Lévy


La carte du -calcul




machines virtuelles

CAM, Krivine

SCHEMECAML Haskell

Javascript




Gérard Huet


=> 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)


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)


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


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


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.


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


Interblocage (deadlock)


Famine (starvation)

13:0613:0312:57


Le ski au 20 e siècle

13:00


Le ski au 20 e siècle, avec protocole

13:0613:0312:5713:00

Le drapeau ajoute le lien de causalité manquant


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


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


Parallélismes synchrone et vibratoire

SynchroneMusiciens et spectateurs négligent la vitesse du son

VibratoireMais les acousticiens règlent sa propagation


Applications : embarqué et circuits

SCADE

circuits électroniques

Nicolas Halbwachs

modèle / langage Lustre

Jean Vuillemin

nombres 2-adiques


Mémoire partagée

P Q

R S

Mémoire


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


Rendezvous = information partagée

P Q


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


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


Réseaux de Kahn

P

Q

R


Réseaux graphiques

Réseaux de Petri

Source Univ. Stuttgart

Réseaux d’automates


Le -calcul de Milner : chimie + calcul

[email protected]<“vous habitez chez vos parents?”>

[email protected]

[email protected]

Annuaireadr<Alice> rep<[email protected]>[email protected]<[email protected]>[email protected]<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



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

Anne-Marie Kermarrec


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


Comment calcule notre cerveau ?


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

=> couplages circuits / neurones


• 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– …


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

Documents

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