On assiste depuis quelques années à l’émergence d’un nouveau domaine de recherche autour du point triple théorie de l’information – physique statistique – optimisation combinatoire. Un des fils qui relie ces sujets est la question de satisfaction de contraintes dans des systèmes comportant beaucoup de variables discrètes en interactions. Ce type de problème est en effet central pour les codes de correction d’erreur en théorie de l’information, ainsi que pour les systèmes frustrés en physique statistique, et certains des problèmes les plus importants en optimisation combinatoire et en théorie de la complexité algorithmique sont naturellement formulés en terme de satisfaction de contraintes.
Cet exposé propose une introduction à ce vaste sujet, qui s’attachera à mettre en valeur l’apport conceptuel de la physique statistique, le rôle des transitions de phases et des phases vitreuses, et les conséquences que l’on peut en déduire pour la conception de nouveaux types d’algorithmes.

Laboratoire de Physique Théorique et Modèles Statistiques Université Paris Sud, Orsay