La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Partagez cette publication

1-1
Cours 9:
Algorithmes et physique statistique
Mod`eledIsingetcoupemaximale,NP-comple´tude
Fonction de partition, polynome de Tutte
Mode`leinhomog`ene,calculsdanslecasplanaire
Recuitsimul´e,uneheuristiqueinspire´eparlaphysique
Gilles Schaeffer
INF-551-9: Algorithmes et physique statistique
2-1
Mod`le d’Ising et coupe maximale e Donnees:Un grapheG= (X, E), une applicationJdeEdansR, ´ de´crivantl´energiedinteractionentresitesvoisins. Uneconfiguration de spinsest une applicationσdeXdans{−1,+1} L’greie´enice´saose`aσreepaonn´estd H(σ) =MXσ(x)XJ(e)σ(x)σ(y) xXe={x,y}∈E Probl`emes:gonaturndioen´igrenimelami.erTuoevlrca Calculer la fonction de partitionZG(β) =PσeβH(σ).
Gilles S
chaeffer
INF-551-9: Algorithmes et physique statistique
2-2
Mode`ledIsingetcoupemaximale Donne´es:Un grapheG= (X, E), une applicationJdeEdansR, de´crivantle´nergiedinteractionentresitesvoisins. Uneconfiguration de spinsest une applicationσdeXdans{−1,+1} L’egieren´ocssaa`ee´iσest d ´e par onne H(σ) =MXσ(x)XJ(e)σ(x)σ(y) xXe={x,y}∈E Proble`mes:orTrevu.iminamele´engreirationdlacongu Calculer la fonction de partitionZG(β) =PσeβH(σ). UnecoupeesetrˆsnenutseadelbmeCtelles qu’il existe une partition X=X+X,X+X=pour laquelleC=C(X+, X), lensembledesareˆtesayantleursextre´mit´esdans2partsdi´erentes.
Gilles Schaeffer
INF-551-9: Algorithmes et physique statistique
2-3
Mode`ledIsingetcoupemaximale Donn´ees:Un grapheG= (X, E), une applicationJdeEdansR, d´ecrivantle´nergiedinteractionentresitesvoisins. Uneconfiguration de spinsest une applicationσdeXdans{−1,+1} L’ne´eierge´ica`esoasσeepardtse´nno H(σ) =MXσ(x)XJ(e)σ(x)σ(y) xeX={x,y}∈E Proble`mes:ouev.eTraliminemgieren´dnoitarugnocalr Calculer la fonction de partitionZG(β) =PσeβH(σ). UnecoupebmesdeltsenenuˆearsteCtelles qu’il existe une partition X=X+X,X+X=pour laquelleC=C(X+, X), lembledesareˆtesayantleursextr´emit´esdans2partsdie´rentes. ens Chaqueσ:enied´upconetuCσ=C(X+, X)u`oX+=σ1(1).
Gilles Schaeffer
INF-551-9: Algorithmes et physique statistique
2-4
Mode`ledIsingetcoupemaximale Donne´es:Un grapheG= (X, E), une applicationJdeEdansR, d´ecrivantle´nergiedinteractionentresitesvoisins. Uneconfiguration de spinsest une applicationσdeXdans{−1,+1} L’engreie´asae`´ecisoσontdesrapee´n H(σ) =MXσ(x)XJ(e)σ(x)σ(y) xeX={x,y}∈E Proble`mes:ouTrrugoitalrevnocagieminimnd´enerla.e Calculer la fonction de partitionZG(β) =PσeβH(σ). UnecoupeeteˆradsestunensembleCtelles qu’il existe une partition X=X+X,X+X=pour laquelleC=C(X+, X), lensembledesareˆtesayantleursextre´mite´sdans2partsdi´erentes. Chaqueσinutenoc´dee:upCσ=C(X+, X)ou`X+=σ1(1). PourM= 0etJ <0constant,H(σ) =−|E| ∙J+ 2|Cσ| ∙J.
Gilles Schaeffer
INF-551-9: Algorithmes et physique statistique
2-5
Mode`ledIsingetcoupemaximale Donn´ees:Un grapheG= (X, E), une applicationJdeEdansR, de´crivantl´energiedinteractionentresitesvoisins. Uneconfiguration de spinsest une applicationσdeXdans{−1,+1} L’eigrene´icossaa´ee`σest donnee par ´ H(σ) =MXσ(x)XJ(e)σ(x)σ(y) xXe={x,y}∈E Probl`emes:taoidn´canogruTrouverle.aliminemgieren Calculer la fonction de partitionZG(β) =PσeβH(σ). UnecoupeeteˆsestunensembledarCtelles qu’il existe une partition X=X+X,X+X=pour laquelleC=C(X+, X), lensembledesareˆtesayantleursextr´emite´sdans2partsdi´erentes. Chaqueσocen:epue´dutinCσ=C(X+, X)u`oX+=σ1(1). PourM= 0etJ <0constant,H(σ) =−|E| ∙J+ 2|Cσ| ∙J. Trouver la configuration d’Ising d’energie minimaleMaxCut.
Gilles Schaeffer
INF-551-9: Algorithmes et physique statistique
3-1
NP-comple´tudedeMaxCut
Onr´eduit3-SATa`MaxCutepem-o3rilvblea`NAESAT´:tetan donn´eunensembledeclausesa`3litte´raux,trouveruneaectation o`uchaqueclausecontientaumoinsunlitt´eralvraietunlitt´eralfaux.
Gilles Schaeffer
INF-551-9: Algorithmes et physique statistique
3-2
NP-compl´etudedeMaxCut
Onr´eduit3-SAT`aMaxCuteme3obl`leprvia-NAESATate´tn: donn´eunensembledeclausesa`3litte´raux,trouveruneaectation o`uchaqueclausecontientaumoinsunlitt´eralvraietunlitte´ralfaux. 3-SATude´a`tiers3-NAESAT:soit(Ci=xiyizi)i=1,...,mune instance de3-SAT; on poseCi0=xiyitietCi00=zit¯iu`uo uet lestisont de nouvelles variables.
Gilles Schaeffer
INF-551-9: Algorithmes et physique statistique
3-3
NP-comple´tudedeMaxCut
Onre´duit3-SATa`MaxCutbl`eme3-vialeproNAESATtenat´: donne´unensembledeclausesa`3litte´raux,trouveruneaectation o`uchaqueclausecontientaumoinsunlitt´eralvraietunlitte´ralfaux. 3-SATdeiu`tar´se3-NAESAT:soit(Ci=xiyizi)i=1,...,mune instance de3-SAT; on poseCi0=xiyitie00¯u tCi=zitiuo` uet lestisont de nouvelles variables. Il faut voir que(Ci)admet une affectation ssi(Ci0, Ci00)admet une bi-affectation (ielaeuqahcauseauclert´itnlVraiet unFaux):
Gilles Schaeffer
INF-551-9: Algorithmes et physique statistique
3-4
NP-comple´tudedeMaxCut
Onre´duit3-SAT`aMaxCutem-3lbe`eprovialNAESATtanet´: donne´unensembledeclausesa`3litte´raux,trouveruneaectation o`uchaqueclausecontientaumoinsunlitte´ralvraietunlitte´ralfaux. 3-SAT`tadeiues´r3-NAESAT:soit(Ci=xiyizi)i=1,...,mune instance de30iyitietCi00=zi¯ o -SAT; on poseCi=xtiu`u uet lestisont de nouvelles variables. Il faut voir que(Ci)admet une affectation ssi(Ci0, Ci00)admet une bi-affectation (ieauseauclueaqchlalnti´treVraiet unFaux): s’il existe une affectation telle que tous lesCisoient vraies, on la compl`eteparti=xiyietu=Faux: c’est une bi-affectation.
Gilles Schaeffer
INF-551-9: Algorithmes et physique statistique
3-5
NP-comple´tudedeMaxCut
Onre´duit3-SAT`aMaxCut3e-rpbo`lmevleiaNAESAT:´etant donn´eunensembledeclausesa`3litt´eraux,trouveruneaectation o`uchaqueclausecontientaumoinsunlitt´eralvraietunlitt´eralfaux. 3-SAT`sae´retiud3-NAESAT:soit(Ci=xiyizi)i=1,...,mune instance de3-SAT; on poseCi0=xiyitietCi00=zit¯iuo`u uet lestisont de nouvelles variables. Il faut voir que(Ci)admet une affectation ssi(Ci0, Ci00)admet une bi-affectation (iehacuslaecquttilnuaelare´Vraiet unFaux): s’il existe une affectation telle que tous lesCisoient vraies, on la compl`eteparti=xiyietu=Faux une bi-affectation.: c’est s’il existe une bi-affectation de(Ci0, Ci00): ¯ – soitu=Faux, alorszitest vraie doncxiyiziest vraie. – soitu=Vrai, alors nier toutes les valeurs des variables...
Gilles Schaeffer
INF-551-9: Algorithmes et physique statistique