EnglishFrançais

Site Web DMA

Bannière DMA Site de l'ENS Site Paris Sciences et Lettres Site du CNRS Accueil

Séminaire informel de Probabilités et Statistiques

Horaires : Le mercredi 10 avril 2013, 14h-15h

Lieu : Salle W

Problèmes aléatoires de satisfaction de contraintes : approches et résultats de la physique statistique

Guilhem Semerjian (ENS - page personnelle)

Dans les années 90 des simulations numériques ont révélées des propriétés intéressantes dans les ensembles aléatoires d'instances de problèmes de satisfaction de contraintes (satisfiabilité, coloriage de graphes notamment). Quand un paramètre définissant l'ensemble aléatoire (le nombre de clauses par variables) augmente la probabilité de trouver une formule satisfiable chute abruptement de 1 à 0 dans la limite des grandes tailles de formule. Ce phénomène de seuil a été l'objet d'actives recherches en informatique et en probabilités. Par ailleurs des outils (non-rigoureux) de physique statistique ont pu être appliqués à ces problèmes. Un certain nombre de résultats ont émergé de ces études, par exemple des conjectures quantitatives sur la valeur du seuil de satisfiabilité, et une image plus précise de la structure de l'ensemble des solutions des formules satisfiables. D'autres résultats de physique statistique ont un aspect plus algorithmique, que ce soit l'analyse d'algorithmes déjà existants ou la suggestion de nouvelles stratégies pour résoudre ces formules aléatoires. Dans ce séminaire j'essaierai de présenter, sans rentrer dans les détails techniques, le cadre général de ces études et certains de ces résultats.

 

Autres séances du séminaire


45 rue d'Ulm - F 75230 PARIS cedex 05 | phone : (33) 1 44 32 20 49 | fax : (33) 1 44 32 20 69

Plan du site | Mentions légales | | Edition du site | Web site designed under SPIP