Publication : t97/184

Systmes dsordonns et frustrs: modles champ moyen et problmes d'optimisation combinatoire

Schreiber G.R. (CEA, DSM, SPhT (Service de Physique Thorique), F-91191 Gif-sur-Yvette, FRANCE)
Abstract:
Dans la prsente thse de doctorat je prsente des rsultats concernant des modles dsordonns et frustrs venant de la physique statistique et de l'optimisation combinatoire. Comme application de la thorie des verres de spins, j'tudie le modle de Blume, Emery et Griffiths dsordonn et frustr. Ce modle est trait dans l'approximation de champ moyen dans le cadre de la mthode des rpliques A l'aide de l'Ansatz symtrique dans les rpliques je prsente une solution numrique complte puis je discute des effets de brisure de cette symtrie La stabilit de la solution symtrique a t Rudik et les rgions instables identifies Le diagramme de phase exhibe des transitions de premier et de second ordre. Le point tricritique persiste dans le modle frustr, Ce qui est en accord avec des travaux antrieurs une version du modle BEG avec un potentiel chimique dsordonn a galement t tudie. les calculs confirment que le point tricritique apparat plus basse temprature quand il y a du dsordre. Ensuite je considre le problme de la bipartition d'un graphe. Ce problme correspond du point de vue de la physique statistique h un verre de spins soumis h une contrainte d'aimantation totale nulle. je considre les proprits statistiques des solutions de faible nergie engendres par des algorithmes heuristiques. de tels algorithme sont en gnral conus pour rsoudre des problmes d'optimisation combinatoire qui sont NP- difficiles. Plusieurs heuristiques ont 60 implmentes pour le problme de la bipartition de graphe. des lois d'chelle ont t obtenues : en particulier la moyenne et la variance du cot obissent A une loi linaire en N. Par consquent le cot obtenu par des heuristiques est une quantit auto-moyennante. je suggre que cette proprit est gnrale valable aussi pour les solutions alatoires pour les solutions quasi-optimales et pour les solutions optimales. En outre je propose une procdure pour comparer des algorithmes heuristiques. Cette procdure tient compte de la qualit de la solution aussi bien que du temps de calcul utilis. Dans la troisime partie de ma thse j'ai tudi en dtail les proprits h temprature nulle des verres de spins sur des graphes alatoires lacunaires avec une coordination fixe. les verres de spins sur de tels graphes peuvent tre considrs comme une approximation aux vrais verres de spins qui est plus raliste que le modle de Sherrington et Kirkpatrick. J'ai conu un nouvel algorithme pour trouver les tats fondamentaux. Aussi je teste numriquement une conjecture de Banavar, Sherrington et Sourlas qui donne la densit d'nergie du fondamental dans la limite de grande taille en fonction de la coordination. La distribution du paramtre d'ordre se rvle tre non triviale et les donnes prsentent une forte indication de la prsence d'ultramtricit pour toutes les valeur de la coordination. Ces rsultats confirment que les proprits particulires des verres de spin, dduites an niveau de l'approximation de champ moyen dans le cadre du modle de Sherrington et Kirkpatrick, sont aussi prsentes pour des modles plus ralistes comme les verres de spins sur des graphes alatoires lacunaires avec une coordination fixe.
Année de publication : 1997
Thse
Soutenance de thse : Universite Paris XI ; 1997-11-13
Lien : http://theses-EN-ligne.in2p3.fr/documents/archives0/00/00/08/25/
Keywords : verre de spins; modele BEG; frustration, systemes complexes; optimisation combinatoire; partition de graphe; algorithme heuristique; auto-moyennage; loi d'echelle spin glasses; BEG model; frustration; complex systems; combinatorial optimization
Langue : Français
Editeurs : Martin O.C.

Fichier(s) à télécharger :
  • publi.pdf

  •  

    Retour en haut