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.

Cette thèse présente une étude complète des propriétés statiques et dynamiques du modèle à seize vertex en 2D, une version simplifiée de la glace de spin avec interactions dipolaires. Après une discussion générale sur le magnétisme frustré, et la glace de spin en particulier, on justifie l'introduction de notre modèle pour étudier le comportement collectif de la glace de spin. On utilise un algorithme de Monte Carlo à temps continu avec une dynamique locale qui nous permet d'analyser les phases d'équilibre et les propriétés critiques du modèle 2D. On compare nos résutats avec les resultats obtenus dans les cas où le système est intégrable. On définit ensuite le modèle sur des arbres orientés et on applique une approximation du type Bethe-Peierls. Afin de discuter le domaine de validité de cette approche, on compare les résultats ainsi obtenus avec les résultats exacts et numériques obtenus pour le modèle 2D. L'apparition récente des glaces de spin artificielles suggère un certain choix des paramètres du modèle. On montre que le modèle à seize vertex décrit de façon précise la thermodynamique de la glace de spin artificielle. On présente en détail le diagramme de phase et la nature des phases d'équilibre du modèle à seize vertex. Afin d' inclure l'effet des fluctuations thermiques responsables de apparaition de défauts ponc- tuels dans la glace de spin, on construit une extension stochastique du modèle intégrable à six vertex. On étudie, par l'intermédiaire de simulations Monte Carlo, comment le système s'ordonne dans le temps après différentes trempes. On analyse l'évolution de la densité de défauts et on iden- tifie les mécanismes dynamiques qui pilotent la relaxation vers ses différentes phases d'équilibre. On montre ainsi que la dynamique donne lieu à du "coarsening" et qu'elle vérifie l'hypothèse de "scaling" dynamique. On discute le rôle des défauts topologiques étendus et ponctuels présents dans le système au cours de l'évolution. Finalement, on étudie la présence d'un régime dynamique où le système reste gelé pendant de longues périodes de temps, ce qui à été observé dans la glace de spin dipolaire en 3D.

Un grand nombre des problèmes d'optimisation, ainsi que des problèmes inverses, combinatoires ou hors équilibre qui apparaissent en physique statistique des systèmes complexes, peuvent être représentés comme un ensemble des variables en interaction sur un certain réseau. Bien que la recette universelle pour traiter ces problèmes n'existe pas, la compréhension qualitative et quantitative des problèmes complexes sur des graphes a fait des grands progrès au cours de ces dernières années. Un rôle particulier a été joué par des concepts empruntés de la physique des verres de spin et la théorie des champs, qui ont eu beaucoup de succès en ce qui concerne la description des propriétés statistiques des systèmes complexes et le développement d'algorithmes efficaces pour des problèmes concrets.En première partie de cette thèse, nous étudions des problèmes de diffusion sur des réseaux, avec la dynamique hors équilibre. En utilisant la méthode de cavité sur des trajectoires dans le temps, nous montrons comment dériver des équations dynamiques dites "message-passing'' pour une large classe de modèles avec une dynamique unidirectionnelle -- la propriété clef qui permet de résoudre le problème. Ces équations sont asymptotiquement exactes pour des graphes localement en arbre et en général représentent une bonne approximation pour des réseaux réels. Nous illustrons cette approche avec une application des équations dynamiques pour résoudre le problème inverse d'inférence de la source d'épidémie dans le modèle "susceptible-infected-recovered''.Dans la seconde partie du manuscrit, nous considérons un problème d'optimisation d'appariement planaire optimal sur une ligne. En exploitant des techniques de la théorie de champs et des arguments combinatoires, nous caractérisons une transition de phase topologique qui se produit dans un modèle désordonné simple, le modèle de Bernoulli. Visant une application à la physique des structures secondaires de l'ARN, nous discutons la relation entre la transition d'appariement parfait-imparfait et la transition de basse température connue entre les états fondu et vitreux de biopolymère; nous proposons également des modèles généralisés qui suggèrent une correspondance exacte entre la matrice des contacts et la séquence des nucléotides, permettant ainsi de donner un sens à la notion des alphabets effectifs non-entiers. / A large number of optimization, inverse, combinatorial and out-of-equilibrium problems, arising in the statistical physics of complex systems, allow for a convenient representation in terms of disordered interacting variables defined on a certain network. Although a universal recipe for dealing with these problems does not exist, the recent years have seen a serious progress in understanding and quantifying an important number of hard problems on graphs. A particular role has been played by the concepts borrowed from the physics of spin glasses and field theory, that appeared to be extremely successful in the description of the statistical properties of complex systems and in the development of efficient algorithms for concrete problems.In the first part of the thesis, we study the out-of-equilibrium spreading problems on networks. Using dynamic cavity method on time trajectories, we show how to derive dynamic message-passing equations for a large class of models with unidirectional dynamics -- the key property that makes the problem solvable. These equations are asymptotically exact for locally tree-like graphs and generally provide a good approximation for real-world networks. We illustrate the approach by applying the dynamic message-passing equations for susceptible-infected-recovered model to the inverse problem of inference of epidemic origin. In the second part of the manuscript, we address the optimization problem of finding optimal planar matching configurations on a line. Making use of field-theory techniques and combinatorial arguments, we characterize a topological phase transition that occurs in the simple Bernoulli model of disordered matching. As an application to the physics of the RNA secondary structures, we discuss the relation of the perfect-imperfect matching transition to the known molten-glass transition at low temperatures, and suggest generalized models that incorporate a one-to-one correspondence between the contact matrix and the nucleotide sequence, thus giving sense to the notion of effective non-integer alphabets.