Géométrie et inférence dans l'optimisation et en théorie de l'information

摘要: Les problemes d'optimisation et de satisfaction contraintes sur des ensembles variables discretes sont l'objet principal la complexite algorithmique. Ces ont recemment beneficie outils concepts physique systemes desordonnes, a fois theoriquement algorithmiquement. En particulier, il ete suggere que les difficultes pratiques soulevees par certaines instances dures liees structure fragmentee leur espace solutions, qui rappelle une phase vitreuse. Parallelement, codes correction d'erreur pointe, peuvent etre ramenes d'optimisation, reposent separabilite leurs messages afin d'assurer communication fiable. L'objet cette these est d'explorer, dans un cadre commun, relation entre proprietes d'inference l'organisation geometrique, issus algorithmique theorie l'information. Apres introduction lies aux domaines sus-evoques, methodes passage messages, basees l'approximation Bethe, introduites. utiles d'un point vue physique, car elle permettent d'etudier thermodynamiques d'ensemble d'instances aleatoires. Elles egalement pour l'inference. L'analyse spectres distances ensuite effectuee l'aide combinatoires mises profit prouver l'existence fragmentation contraintes, d'en etudier aspects importants.