Problèmes de satisfaction de contraintes
Cours de recherche (30h de cours, travail
sur des articles scientifiques)
Cours : Pascal Koiran (Pascal.Koiran)
Le formalisme des problèmes de satisfaction de contraintes (CSP en anglais) est flexible et général. Il peut s’appliquer à des problèmes variés
qui apparaissent dans diverses disciplines, avec de nombreuses applications allant du routage au test des microprocesseurs, des verres de spin aux réseaux d’expression de gènes.
Mais il y a un prix à payer pour cette généralité :
la complexité algorithmique de leur résolution peut être élevée.
Par exemple, l’un de ces problèmes, la satisfaisabilité
des formules booléennes sous forme normale conjonctive, est
un problème NP-complet bien connu.
Ce cours abordera ces problèmes de satisfaction de contraintes sous trois aspects.
-
La complexité algorithmique : on verra quels CSP peuvent etre
résolus efficacement,
et lesquels sont algorithmiquement difficiles.
- L’étude générale des modèles graphiques par des méthodes probabilistes issues
de la physique statistique: notion de graphe factoriel,
algorithmes de passage de message comme la propagation des convictions,
transitions de phases. On développera pour ce faire un langage commun illustré
par des applications à la satisfaisabilité de formules aléatoires et à
certains problèmes de théorie de l’information.
- Aspects logiciels:
on verra quelles heuristiques permettent de résoudre en pratique
des problèmes de taille significative.
Les intervenants sont:
-
Pascal Koiran (informatique, ENS Lyon) : complexité dans le pire cas.
- Marc Mézard (physique, Orsay) : analyse probabiliste, modèles graphiques,
liens avec la physique statistique.
- Laurent Simon (informatique, Orsay) : heuristiques, aspects logiciels.
Bibliographie