Les problèmes d'optimisation combinatoires définis sur graphes aléatoires sont au coeur de la théorie de la complexité algorithmique. Ils sont également étroitement liés à une formulation champ moyen, dite approximation de Bethe, de modèles sur réseau de verres de spins et verres structuraux. Cette thèse s'appuie sur ce parallèle pour appliquer à des problèmes d'optimisation une approche issue de la physique statistique des systèmes désordonnés, la méthode de la cavité. Etant donné un ensemble d'entrées (instances) d'un problème d'optimisation, cette méthode permet de déterminer les propriétés des solutions des instances typiques, ainsi que celles des instances atypiques, dont les probabilités sont exponentiellement petites (grandes déviations sur la structure externe). Pour une instance donnée, la méthode de la cavité donne également accès à la thermodynamique des différentes solutions admissibles (grandes déviations sur la structure interne). D'un point de vue physique, de nombreux problèmes algorithmiquement difficiles se révèlent ainsi posséder une phase de type verre. Cette thèse est composée de trois parties destinées à exposer les principes, applications et limitations de la méthode de la cavité. La première partie rappelle, dans la perspective des grandes déviations, les liens entre physique statistique et optimisation combinatoire. La deuxième partie aborde les modèles définis sur graphes aléatoires et, pour différents ensembles de graphes, analyse les propriétés typiques et atypiques de ces modèles. La troisième partie est consacrée aux grandes déviations sur le "désordre interne", constitué par les solutions et quasi-solutions d'une instance donnée. Une attention particulière est dévolue au traitement des phases vitreuses où l'ensemble des solutions est fragmenté en un nombre exponentiel d'amas disjoints (structure dite à un pas de brisure de symétrie des répliques); il est montré comment la méthode de la cavité fournit dans de tels cas une description fine des propriétés géométriques de l'espace des solutions.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00009956 |
| Date | 11 July 2005 |
| Creators | Rivoire, Olivier |
| Publisher | Université Paris Sud - Paris XI |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0019 seconds