BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Département de mathématiques et applications - ECPv6.2.2//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Département de mathématiques et applications
X-ORIGINAL-URL:https://www.math.ens.psl.eu
X-WR-CALDESC:évènements pour Département de mathématiques et applications
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20130331T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20131027T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20130410T140000
DTEND;TZID=Europe/Paris:20130410T150000
DTSTAMP:20260403T223800
CREATED:20130410T120000Z
LAST-MODIFIED:20211104T093039Z
UID:8107-1365602400-1365606000@www.math.ens.psl.eu
SUMMARY:Problèmes aléatoires de satisfaction de contraintes : approches et  résultats de la physique statistique
DESCRIPTION: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.
URL:https://www.math.ens.psl.eu/evenement/problemes-aleatoires-de-satisfaction-de-contraintes-approches-et-resultats-de-la-physique-statistique/
LOCATION:Salle W
CATEGORIES:Séminaire informel de probabilités
END:VEVENT
END:VCALENDAR