Les problèmes d'optimisation et de satisfaction de contraintes sur des ensembles de variables discrètes sont l'objet principal de la complexité algorithmique. Ces problèmes ont récemment bénéficié des outils et des concepts de la physique des systèmes désordonnés, à la fois théoriquement et algorithmiquement. En particulier, il a été suggéré que les difficultés pratiques soulevées par certaines instances dures de problèmes d'optimisation sont liées à la structure fragmentée de leur espace de solutions, qui rappelle une phase vitreuse. Parallèlement, les codes de correction d'erreur de pointe, qui peuvent être ramenés à des problèmes d'optimisation, reposent sur la séparabilité de leurs messages afin d'assurer une communication fiable. L'objet de cette thèse est d'explorer, dans un cadre commun, cette relation entre les propriétés d'inférence et l'organisation géométrique, dans les problèmes issus de la complexité algorithmique et de la théorie de l'information.<br /><br />Après une introduction physique des problèmes et des concepts liés aux domaines sus-évoqués, les méthodes de passage de messages, basées sur l'approximation de Bethe, sont introduites. Ces méthodes sont utiles d'un point de vue physique, car elle permettent d'étudier les propriétés thermodynamiques d'ensemble d'instances aléatoires. Elles sont également utiles pour l'inférence. L'analyse de spectres de distances est ensuite effectuée à l'aide de méthodes combinatoires et de passage de messages, et mises à profit afin de prouver et l'existence de la fragmentation dans les problèmes de satisfaction de contraintes, et d'en étudier les aspects importants.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00175221 |
| Date | 24 September 2007 |
| Creators | Mora, T. |
| 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.0021 seconds