Phenomenes de seuil en optimisation combinatoire:
de la transition a la resolution algorithmique.

par Olivier Dubois et Remi Monasson

On s'est apercu ces dernieres annees que de nombreux
problemes d'optimisation combinatoire ont des comportements
similaire a ceux observes en physique de matiere condensee.
Lorsque l'on varie certains parametres de controle, les
proprietes statistiques de ces problemes changent brutalement.
Ces phenomenes de seuil, ou transitions, ont des consequences
importantes sur la complexite de resolution algorithmique.

Dans ce cours, on se propose de faire un panorama rapide de 
ces problemes, en ce concentrant tout particulierement sur
celui de la Satisfaisabilite aleatoire pour lesquels de nombreuses
etudes ont ete effectuees. On insistera sur la complementarite 
des deux approches disponibles, informatique ou mathematique 
(presentee par O. Dubois) et physique (presentee par R. Monasson), 
en terme d'objectifs et de resultats.