Cours 9: Algorithmes et physique statistique

Cours 9: Algorithmes et physique statistique
• Mod`ele d’Ising et coupe maximale, NP-compl´etude
• Fonction de partition, polynome de Tutte
• Mod`ele inhomog`ene, calculs dans le cas planaire
• Recuit simul´e, une heuristique inspir´ee par la physique
Gilles Schaeffer INF-551-9: Algorithmes et physique statistique
1-1Mod`ele d’Ising et coupe maximale
Donn´ees: Un graphe G = (X,E), une application J de E dans R,
d´ecrivant l’´energie d’interaction entre sites voisins.
Une configuration de spins est une applicationσ deX dans{−1,+1}
L’´energie associ´ee `a σ est donn´ee par
X X
H(σ) =−M σ(x)− J(e)σ(x)σ(y)
x∈X e={x,y}∈E
Probl`emes: • Trouver la configuration d’´energie minimale.
P
−βH(σ)• Calculer la fonction de partition Z (β) = e .G σ
Gilles Schaeffer INF-551-9: Algorithmes et physique statistique
2-1Mod`ele d’Ising et coupe maximale
Donn´ees: Un graphe G = (X,E), une application J de E dans R,
d´ecrivant l’´energie d’interaction entre sites voisins.
Une configuration de spins est une applicationσ deX dans{−1,+1}
L’´energie associ´ee `a σ est donn´ee par
X X
H(σ) =−M σ(x)− J(e)σ(x)σ(y)
x∈X e={x,y}∈E
Probl`emes: • Trouver la configuration d’´energie minimale.
P
−βH(σ)• Calculer la fonction de partition Z (β) = e .G σ
Une coupe est un ensemble d’arˆetesC telles qu’il existe une partition
X = X ∪ X , X ∩ X = ∅ pour laquelle C = C(X ,X ),+ − + − + −
l’ensemble des arˆetes ayant leurs extr´emit´es dans 2 parts diff´erentes.
Gilles Schaeffer INF-551-9: Algorithmes et physique ...