Bernard CHAZELLE, spécialiste de l’algorithmique, est ... · cellulaires, mais aussi la transmission de rumeurs, les nuées d’oiseaux, les colonies de fourmis, les mouvements

Contact presse : Marie Chéron/Cécile Barnier : 01 44 27 12 72 - [email protected] Octobre 2012

1

Communiqué de presse Octobre 2012

L'avenir de l'informatique appartient désormais moins à la puissance brute de calcul des ordinateurs qu'à l'algorithmique qui ouvre pour les sciences des horizons jusqu’ici inimaginables : sans algorithmes, pas de décodage du génome humain.

Bernard CHAZELLE, spécialiste de l’algorithmique, est nommé titulaire de la chaire Informatique et sciences numériques

- Leçon Inaugurale le 18 octobre 2012 -

Moteurs de recherches, cryptage des achats en ligne ou enchères électroniques, les algorithmes sont désormais au cœur d’une multitude d’applications qui font notre quotidien. Leur puissance de modélisation ouvre des champs jusqu’ici inimaginables et bouleverse nombre de domaines scientifiques. Pour Bernard Chazelle, « au-delà de ses applications logicielles, l’algorithme est surtout un outil conceptuel « subversif » qui ouvre la possibilité d’un regard nouveau sur les sciences et les technologies. Développer une théorie mûre des algorithmes est essentiel à la science du 21ème siècle et constitue un des grands enjeux de l’informatique aujourd’hui ». L’Assemblée des professeurs a nommé Bernard Chazelle titulaire de la chaire Informatique et sciences numériques pour l’année académique 2012/2013. Bernard Chazelle, professeur à l’université de Princeton depuis 1986, a apporté à cette science jeune des contributions majeures (notamment sur les algorithmes géométriques ou sur la randomisation des algorithmes). Il s’intéresse tout particulièrement aux applications de l’algorithmique dans les sciences et envisage notamment l’algorithmique comme une nouvelle voie d’approche des phénomènes naturels.

Des algorithmes pour modéliser les circuits cellulaires

mais aussi les épidémies ou les transmissions de rumeurs … « Longtemps simples outils de programmation, les algorithmes sont en passe d’acquérir au sein des sciences et des technologies nouvelles, le rôle qu’ont traditionnellement tenu, dans les sciences physiques, les équations aux dérivées partielles. Un des développements majeurs récents concerne, par exemple, les « algorithmes naturels », c’est-à-dire issus du monde vivant comme les circuits cellulaires, mais aussi la transmission de rumeurs, les nuées d’oiseaux, les colonies de fourmis, les mouvements de foule ou les épidémies. »

Bernard Chazelle donnera sa leçon inaugurale, L’algorithmique et les sciences, le 18 octobre 2012. Ses cours auront lieu, les jeudis à 14h00 à partir du 25 octobre. Ils seront suivis, de 15h00 à 16h00, d’un séminaire en relation avec le cours (voir programme complet ci-joint). L’ensemble du cycle d’enseignement de Bernard Chazelle sera disponible sur le site Internet du Collège de France en version française et anglaise (www.college-de-france.fr).


2

Chaire Informatique et sciences numériques Année académique 2012/2013

Leçon Inaugurale de Bernard Chazelle, le 18 octobre 2012

L’algorithmique et les sciences (présentation) La loi de Moore prévoit le doublement de la puissance des ordinateurs tous les deux ans. Cette progression a été le principal vecteur d’innovation technologique dans le monde depuis plus de quarante ans. Comme toute croissance exponentielle, bien sûr, la Loi de Moore est condamnée à brève échéance. De fait, tout porte à croire qu’elle est déjà lettre morte. C’est en tout cas l’hypothèse de travail qui sous-tend le développement de la prochaine génération de systèmes d’exploitation chez Microsoft. L’avenir de l’informatique, on serait tenté d’en conclure, n’appartient plus à la puissance brute de calcul, mais à l’algorithmique, la discipline qui nous a apporté le décodage du génome humain, les moteurs de recherche, les enchères électroniques, le cryptage des achats en ligne, et la reconnaissance de la parole. Au-delà de ses applications logicielles, toutefois, l’algorithme est surtout un outil conceptuel « subversif » qui ouvre la possibilité d’un regard nouveau sur les sciences et les technologies. Ce cours se propose d’expliquer les éléments constitutifs de cette révolution en marche. Les algorithmes font penser différemment. Saviez-vous, par exemple, qu’il existe un algorithme en mesure de vous convaincre instantanément de la validité d’une preuve comme celle de la redoutable Conjecture de Poincaré en y piochant au plus dix lettres au hasard ? L’intuition qui vous conduit à penser que toute démonstration mathématique est à la merci de la moindre faute est foncièrement trompeuse. Saviez-vous qu’il vous est possible de convaincre un interlocuteur d’une vérité sans en révéler la moindre information sur sa justification. Ces algorithmes à « divulgation nulle » ont radicalement transformé des notions épistémologiques fondamentales comme la vérification de preuve. En cryptographie, leur utilisation permet des transactions entre des entités qui ne se font pas confiance. Par exemple, comment authentifier un document ou prouver la possession d’un mot de passe sans le révéler ? L’efficacité du calcul se mesure en fonction de trois grandes ressources : le temps, la mémoire, et l’aléa. (La vitesse des microprocesseurs est sans grand intérêt théorique.) Des trois, c’est l’aléa qui a le plus transformé le paysage de la théorie informatique ces vingt dernières années. Curieusement, l’aléa est indispensable là où on l’imagine accessoire et inutile là où on le croit nécessaire. Il n’aide sans doute pas à calculer vraiment plus vite mais c’est pourtant un instrument conceptuel dont les chercheurs ne sauraient se passer. Ce paradoxe ne peut être compris qu’algorithmiquement. Un autre grand thème de ce cours concerne l’expressivité du langage algorithmique, qui en fait un outil privilégie pour la modélisation des phénomènes d’interaction et de dynamique sociale. L’apprentissage automatique et la théorie des mécanismes d’incitation (enchères, allocation de ressources, calcul des équilibres de Nash) en sont quelques exemples notoires. Un regard nouveau sur les systèmes dynamiques dans le monde vivant nous a conduit récemment à introduire les « algorithmes naturels » pour étudier les phénomènes émergents à haute complexité descriptive.


3

Ceux-ci s’étendent à toutes les échelles de la dynamique sociale, que ce soient les bactéries, les colonies de fourmis, les nuées d’oiseaux, ou les épidémies. Une approche algorithmique ouvre des horizons naguère inaccessibles. Par exemple, ceci nous a permis de comprendre pourquoi les réseaux sociaux et les blogs tendent à stabiliser les opinions alors que la radio et la télévision sont plus propices aux oscillations périodiques. Le triomphe de la physique du vingtième siècle fut en grande partie celui des mathématiques. Pour des raisons d’expressivité, nul n’entretient l’illusion aujourd’hui que guérir le cancer, élucider le cortex cérébral, ou percer le mystère de l’ontogenèse, puisse se réduire à trouver les « bonnes équations différentielles », comme l’ont fait de leur temps Newton, Maxwell, Boltzmann, Einstein, et Schrödinger. L’univers physique est en effet bâti sur des principes de symétrie et d’invariance largement absents en biologie. L’algorithme offre un langage d’une richesse expressive suffisante pour faire face à la haute complexité descriptive du monde vivant. Les circuits cellulaires, les réseaux protéiques, les bancs de poissons, les insectes sociaux, les transmissions de rumeurs, les mouvements de foule, et la polarisation politique sont autant d’exemples de dynamique sociale qui se prêtent à la modélisation par les algorithmes naturels. Seulement voilà : malgré une pléthore d’applications spectaculaires, l’algorithmique en est encore à ses balbutiements. Développer une théorie mure des algorithmes est essentiel à la science du XXI e siècle et constitue un des grands enjeux de l’informatique d’aujourd’hui.

Bernard Chazelle


4

Chaire Informatique et sciences numériques Année académique 2012/2013

Biographie Professeur à l’université de Princeton depuis 1986, où il occupe la chaire Eugene Higgins d’Informatique, Bernard Chazelle est l’un des pionniers de la géométrie algorithmique. Il a longtemps travaillé sur la conception et l’analyse des algorithmes et des structures de données en géométrie et en optimisation combinatoire. Un des grands thèmes de sa recherche a été le rôle de l’aléa dans la complexité algorithmique, un sujet sur lequel il a écrit un ouvrage The Discrepancy Method: Randomness and Complexity. Depuis plusieurs années, il poursuit un programme de recherche sur les « algorithmes naturels », dans le but de bâtir un pont entre l’algorithmique et les systèmes dynamiques du monde vivant. Il a co-enseigné à Princeton avec des collègues physiciens et biologistes le premier cours de « sciences intégrées ». Directeur du Centre NSF de « Computational Intractability », ses recherches portent sur les algorithmes et la complexité.

Bernard Chazelle est diplômé de l’école des Mines de Paris et titulaire d’un PhD de Yale. Il a été professeur invité à l’ENS Ulm, à l’Ecole Polytechnique, à l’Université Paris-Sud, et à l’INRIA. Il a longtemps été consultant à Xerox PARC, DEC SRC, et NEC Research, ou il fut président du “Board of Fellows”. Il est, ou a été, membre du conseil scientifique de l’ENS Ulm, de l’Ecole Polytechnique, et de l’Institut Henri Poincaré.

Il est membre de l’Académie Américaine des Arts et des Sciences et de l’Académie Européenne des Sciences, Fellow de ACM, Guggenheim Fellow, et lauréat de plusieurs prix de l’association de mathématiques, SIAM.


5

Chaire Informatique et sciences numériques

Année académique 2012/2013

Cycle d’enseignement de Bernard Chazelle

Leçon inaugurale, le 18 octobre 2012, à 18h00 : l’algorithmique et les sciences,

Cours et séminaires les jeudis à 14h00

25 octobre 14h : La complexité de l’aléa 15 h Aléa et Complexité en Cryptographie - Jacques Stern, ENS Ulm 8 novembre 14 h : Les preuves interactives et l’épistémologie algorithmique 15 h : Approximations - Claire Mathieu, ENS Ulm, CNRS 15 novembre 14h : La complexité de la communication 15 h Computational Insights and the Theory of Evolution - Christos Papadimitriou, University of California, Berkeley 22 novembre 14 h La théorie algorithmique des jeux 15 h Quantifying the Inefficiency of Game-Theoretic Equilibria - Tim Roughgarden, Stanford University 29 novembre 14 h L’apprentissage et les algorithmes auto-améliorants 15 h Optimisation et Apprentissage - Alexandre d’Aspremont, École Polytechnique 6 décembre 14 h L’algorithmique des phénomènes émergents 15 h Persistent Homology Applied - Herbert Edelsbrunner, IST Austria 13 décembre 14 h Les systèmes d’influence et la dynamique sociale 15 h Physarum Computations - Kurt Mehlhorn, Max-Planck-Institut 20 décembre 14 h Les algorithmes naturels et les sciences 15 h Algorithmes de Routage et Navigation - François Baccelli, University of Texas, Austin, et ENS Ulm • Cours du Professeur • Séminaire

L’ensemble du cycle d’enseignement de Bernard Chazelle sera disponible sur le site Internet du Collège de France en version française et anglaise (www.college-de-france.fr).


6

Invitation Presse

Leçon inaugurale de Bernard Chazelle Titulaire de la chaire Informatique et sciences numériques

- Jeudi 18 octobre 2012, à 18 heures -

Au Collège de France 11 Place Marcelin Berthelot - Paris 5°

Réponse à retourner par Email ou par fax 01 44 27 11 09

M. ………………………………………………………………………. Media ……………………………………………………………………….. Email ………………………………………………………………………... o � Assistera à la leçon inaugurale de Bernard Chazelle o N’assistera pas à la leçon inaugurale

Documents

Bernard CHAZELLE, spécialiste de l’algorithmique, est ... · cellulaires, mais aussi la transmission de rumeurs, les nuées d’oiseaux, les colonies de fourmis, les mouvements