| | | | | | | webmail : intra-extra| Accès VPN| Accès IST| Contact | Français
La transition vitreuse en physique et en informatique
Marc Mezard
Laboratoire de Physique Théorique et Modèles Statistiques, CNRS et Université Paris Sud
Thu, Jan. 20th 2011, 11:00
CEA Bât 774, Amphi Claude Bloch, Orme des Merisiers

Lorsqu’on pense aux liens entre physique et informatique, les développements du "hardware" et la loi de Moore viennent immédiatement à l’esprit. Depuis quelques années, un rapprochement très important mais beaucoup moins connu émerge en ce qui concerne la théorie du calcul et la complexité des algorithmes.

Les problèmes de satisfaction de contraintes, qui forment le coeur de la classe des problèmes de décision les plus difficiles en informatique, présentent bien des similitudes avec les phases vitreuses en physique, au niveau structurel -existence de contraintes antagonistes-, comme au niveau dynamique : relaxations très lentes et ralentissement des algorithmes.

L’exposé montrera comment les développements récents dans la théorie des verres structuraux permettent d’aborder et de comprendre certains éléments essentiels qui sont à l’origine de la complexité algorithmique. L'existence d'une transition vitreuse fournit une explication de la difficulté des problèmes de satisfaction de contraintes aléatoires et c'est à partir de cette analyse qu’ont été trouvés les algorithmes les plus puissants connus à ce jour pour résoudre ces problèmes.

 

Lien vers les colloques de l'Orme (depuis 2007).


http://lptms.u-psud.fr/membres/mezard/
Contact : Luc BARBIER

 

Retour en haut