Séminaires généraux
Transitions de phases : de la physique à l'informatique
par
→
US/Central
Amphi Pierre Lehmann (LAL)
Amphi Pierre Lehmann
LAL
Description
Les problèmes de satisfaction de contraintes (coloriage de graphes, routage, 'clustering' de données, reconnaissance de trajectoires...) font des apparitions fréquentes
dans l'activité scientifique. Ils sont aussi au coeur de la
théorie de la complexité en informatique : ils ont servi
à définir la classe des problèmes dits “NP-complet”, pour
lesquels on pense que les algorithmes de résolution nécessiteront toujours un temps de calcul qui augmente plus vite que toute puissance du nombre de variables.
Pourtant certains de ces problèmes ont une formulation très simple. Le “problème SAT”, par exemple, revient à trouver s'il existe une configuration d'un système de spins d'Ising qui satisfait un certain ensemble de contraintes locales. Des travaux récents ont en fait montré que la vraie difficulté de ce problème est liée à l'existence d'une transition de phase qui apparaît pour une valeur précise de la densité de contraintes.
En prenant ce problème SAT comme exemple, cet exposé propose une introduction à la physique statistique des problèmes d'optimisation. Il analysera en particulier l'apparition de phases vitreuses dans ces problèmes, et le ralentissement dramatique des algorithmes qu'elles induisent. Ces travaux théoriques, qui s'inscrivent dans la lignée d'études fondamentales sur les verres de spin, ont également trouvé des applications inattendues, à savoir le développement de nouveaux types d'algorithmes très performants pour toute une classe de problèmes de satisfaction de contraintes.
Pourtant certains de ces problèmes ont une formulation très simple. Le “problème SAT”, par exemple, revient à trouver s'il existe une configuration d'un système de spins d'Ising qui satisfait un certain ensemble de contraintes locales. Des travaux récents ont en fait montré que la vraie difficulté de ce problème est liée à l'existence d'une transition de phase qui apparaît pour une valeur précise de la densité de contraintes.
En prenant ce problème SAT comme exemple, cet exposé propose une introduction à la physique statistique des problèmes d'optimisation. Il analysera en particulier l'apparition de phases vitreuses dans ces problèmes, et le ralentissement dramatique des algorithmes qu'elles induisent. Ces travaux théoriques, qui s'inscrivent dans la lignée d'études fondamentales sur les verres de spin, ont également trouvé des applications inattendues, à savoir le développement de nouveaux types d'algorithmes très performants pour toute une classe de problèmes de satisfaction de contraintes.