Une donnée peut avoir diverses formes et peut provenir d'un large panel d'applications. Habituellement, une donnée possède beaucoup de bruit et peut être soumise aux effets du hasard. Les récents progrès en apprentissage automatique ont relancé les recherches théoriques sur les limites des différentes méthodes probabilistes de traitement du signal. Dans cette thèse, nous nous intéressons aux questions suivantes : quelle est la meilleure performance possible atteignable ? Et comment peut-elle être atteinte, i.e., quelle est la stratégie algorithmique optimale ?La réponse dépend de la forme des données. Les sujets traités dans cette thèse peuvent tous être représentés par des modèles graphiques. Les propriétés des données déterminent la structure intrinsèque du modèle graphique correspondant. Les structures considérées ici sont soit éparses, soit denses. Les questions précédentes peuvent être étudiées dans un cadre probabiliste, qui permet d'apporter des réponses typiques. Un tel cadre est naturel en physique statistique et crée une analogie formelle avec la physique des systèmes désordonnés. En retour, cela permet l'utilisation d'outils spécifiques à ce domaine et de résoudre des problèmes de satisfaction de contraintes et d'inférence statistique. La problématique de performance optimale est directement reliée à la structure des extrema de la fonction d'énergie libre macroscopique, tandis que les aspects algorithmiques proviennent eux de la minimisation de la fonction d'énergie libre microscopique (c'est-à-dire, dans la forme de Bethe).Cette thèse est divisée en quatre parties. Premièrement, nous aborderons par une approche de physique statistique le problème de la coloration de graphes aléatoires et mettrons en évidence un certain nombre de caractéristiques. Dans un second temps, nous calculerons une nouvelle limite supérieure de la taille de l'ensemble contagieux. Troisièmement, nous calculerons le diagramme de phase du modèle de Dawid et Skene dans la région dense en modélisant le problème par une factorisation matricielle de petit rang. Enfin, nous calculerons l'erreur optimale de Bayes pour une classe restreinte de l'estimation matricielle de rang élevé. / Datasets come in a variety of forms and from a broad range of different applications. Typically, the observed data is noisy or in some other way subject to randomness. The recent developments in machine learning have revived the need for exact theoretical limits of probabilistic methods that recover information from noisy data. In this thesis we are concerned with the following two questions: what is the asymptotically best achievable performance? And how can this performance be achieved, i.e., what is the optimal algorithmic strategy? The answer depends on the properties of the data. The problems in this thesis can all be represented as probabilistic graphical models. The generative process of the data determines the structure of the underlying graphical model. The structures considered here are either sparse random graphs or dense (fully connected) models. The above questions can be studied in a probabilistic framework, which leads to an average (or typical) case answer. Such a probabilistic formulation is natural to statistical physics and leads to a formal analogy with problems in disordered systems. In turn, this permits to harvest the methods developed in the study of disordered systems, to attack constraint satisfaction and statistical inference problems. The formal analogy can be exploited as follows. The optimal performance analysis is directly related to the structure of the extrema of the macroscopic free energy. The algorithmic aspects follow from the minimization of the microscopic free energy (that is, the Bethe free energy in this work) which is closely related to message passing algorithms. This thesis is divided into four contributions. First, a statistical physics investigation of the circular coloring problem is carried out that reveals several distinct features. Second, new rigorous upper bounds on the size of minimal contagious sets in random graphs, with bounded maximum degree, are obtained. Third, the phase diagram of the dense Dawid-Skene model is derived by mapping the problem onto low-rank matrix factorization. The associated approximate message passing algorithm is evaluated on real-world data. Finally, the Bayes optimal denoising mean square error is derived for a restricted class of extensive rank matrix estimation problems.

Nous présentons une étude théorique de la dynamique hors équilibre d'une large classe de systèmes microscopiques, dont la caractéristique commune est de présenter, dans certaines conditions expérimentales, une relaxation extrêmement lente (`systèmes vitreux'). Nous abordons tout d'abord le problème du vieillissement de ces systèmes en nous attachant à une comparaison quantitative des deux descriptions théoriques que sont (i) les processus de croissance de domaines, (ii) la solution analytique de modèles désordonnés champ moyen de type verres de spin. Nous abordons ensuite le cas ou la dynamique est forcée par une contrainte extérieure. Cette situation est importante en vue des applications (rhéologie des liquides surfondus et des fluides complexes, compaction lente des matériaux granulaires, etc.), et son étude systématique est un des aspects nouveaux de ce travail. Dans ce cadre, nous étudions tout d'abord numériquement l'influence d'un écoulement sur la séparation de phase d'un mélange binaire. Le diagramme des phases (Température, Forcage) des verres structuraux et des verres de spin est ensuite étudié dans l'approximation de champ moyen. Nous envisageons les deux cas d'un forcage constant non-Hamiltonien, puis Hamiltonien mais dépendant du temps. Ces études fournissent une description à la fois microscopique --forme de la relaxation, température effective définie via le théoreme de fluctuation-dissipation--, et macroscopique --courbes d'écoulement, transitions de phase dynamiques. Les principaux résultats sont testés numériquement sur un liquide surfondu et un verre de spin modéles.

Le verre de spin est une phase de la matière dans laquelle le désordre magnétique est gelé. Étant considéré comme un système modèle des verres en général, il a fait l'objet de nombreux travaux théoriques et expérimentaux. Les recherches ont convergé vers deux principales descriptions de l'état fondamental du système diamétralement opposées. D'une part, la solution " champ-moyen " nécessite une brisure de symétrie non triviale, et l'état fondamental est composé de multiples états organisés en une structure hiérarchique. D'autre part, une approche de " gouttelettes ", fondée sur la dynamique hors-équilibre d'un état fondamental unique. La validation expérimentale d'une de ces deux théories nécessite une observation détaillée de l'échantillon au niveau microscopique. La physique mésoscopique, basée sur les effets d'interférences électroniques, propose un outil unique pour accéder à cette configuration microscopique des impuretés: les fluctuations universelles de conductance. En effet, ces fluctuations représentent une empreinte unique du désordre dans l'échantillon. Ce travail présente la mise en œuvre de mesures de fluctuations de conductance universelles dans les verres de spin. Les effets d'interférences électroniques étant sensibles aux processus de décohérence du verre de spin, ils donnent accès expérimentalement à de nouvelles quantités concernant les excitations du système. La mesure des corrélations entre les empreintes du désordre permet quant à elle d'explorer sous un angle nouveau l'ordre non conventionnel de cet état vitreux.

Des techniques expérimentales récentes ont donné la possibilité d'acquérir un très grand nombre de données concernant des réseaux biologiques complexes, comme des réseaux de neurones, des réseaux de gènes et des réseaux d'interactions de protéines. Ces techniques sont capables d'enregistrer les états des composantes individuelles de ces réseaux (neurones, gènes, protéines) pour un grand nombre de configurations. Cependant, l'information la plus pertinente biologiquement se trouve dans la connectivité de ces systèmes et dans la façon précise avec laquelle ces composantes interagissent, information que les techniques expérimentales ne sont pas au point d'observer directement. Le bût de cette thèse est d'étudier les méthodes statistiques nécessaires pour inférer de l'information sur la connectivité des réseaux complexes en partant des données expérimentales. Ce sujet est traité par le point de vue de la physique statistique, en puisant de l'arsenal de méthodes théoriques qui ont été développées pour l'étude des verres de spins. Les verres de spins sont des exemples de réseaux à variables discrètes qui interagissent de façon complexe et sont souvent utilisés pour modéliser des réseaux biologiques. Après une introduction sur les modèles utilisés ainsi qu'une discussion sur la motivation biologique de cette thèse, toutes les méthodes d'inférence de réseaux connues sont présentées et analysées du point de vue de leur performance. Par la suite, dans la troisième partie de la thèse, un nouvelle méthode est proposée qui s'appuie sur la remarque que les interactions en biologie ne sont pas nécessairement symétriques (c'est-à-dire l'interaction entre les noeuds A et B n'est pas la même dans les deux directions). Il est démontré que cette assomption conduit à des méthodes qui sont capables de prédire les interactions de façon exacte, étant donné un nombre suffisant de données, tout en utilisant un temps de calcul polynomial. Ceci est un résultat original important car toutes les autres méthodes connues sont soit exactes et non-polynomiales soit inexactes et polynomiales. / Recent experimental techniques in biology made possible the acquisition of overwhelming amounts of data concerning complex biological networks, such as neural networks, gene regulation networks and protein-protein interaction networks. These techniques are able to record states of individual components of such networks (neurons, genes, proteins) for a large number of configurations. However, the most biologically relevantinformation lies in their connectivity and in the way their components interact, information that these techniques aren't able to record directly. The aim of this thesis is to study statistical methods for inferring information about the connectivity of complex networks starting from experimental data. The subject is approached from a statistical physics point of view drawing from the arsenal of methods developed in the study of spin glasses. Spin-glasses are prototypes of networks of discrete variables interacting in a complex way and are widely used to model biological networks. After an introduction of the models used and a discussion on the biological motivation of the thesis, all known methods of network inference are introduced and analysed from the point of view of their performance. Then, in the third part of the thesis, a new method is proposed which relies in the remark that the interactions in biology are not necessarily symmetric (i.e. the interaction from node A to node B is not the same as the one from B to A). It is shown that this assumption leads to methods that are both exact and efficient. This means that the interactions can be computed exactly, given a sufficient amount of data, and in a reasonable amount of time. This is an important original contribution since no other method is known to be both exact and efficient.