The phase transition in the number partitioning problem (NPP), i.e., the transition from a region in the space of control parameters in which almost all instances have many solutions to a region in which almost all instances have no solution, is investigated by examining the energy landscape of this classic optimization problem. This is achieved by coding the information about the minimum energy paths connecting pairs of minima into a tree structure, termed a barrier tree, the leaves and internal nodes of which represent, respectively, the minima and the lowest energy saddles connecting those minima. Here we apply several measures of shape (balance and symmetry) as well as of branch lengths (barrier heights) to the barrier trees that result from the landscape of the NPP, aiming at identifying traces of the easy-hard transition. We find that it is not possible to tell the easy regime from the hard one by visual inspection of the trees or by measuring the barrier heights. Only the difficulty measure, given by the maximum value of the ratio between the barrier height and the energy surplus of local minima, succeeded in detecting traces of the phase transition in the tree. In addition, we show that the barrier trees associated with the NPP are very similar to random trees, contrasting dramatically with trees associated with the p spin-glass and random energy models. We also examine critically a recent conjecture on the equivalence between the NPP and a truncated random energy model.

Cette thèse aborde des aspects fondamentales et appliquées de la théorie des verres de spin etplus généralement des systèmes complexes. Les premiers modèles théoriques décrivant la transitionvitreuse sont apparues dans les années 1970. Ceux-ci décrivaient les verres à l'aide d'interactionsaléatoires. Il a fallu alors plusieurs années avant qu'une théorie de champs moyen pour ces systèmessoient comprises. De nos jours il existe un grand nombre de modèles tombant dans la classe de« champs moyen » et qui sont bien compris à la fois analytiquement, mais également numériquementgrâce à des outils tels que le monte-carlo ou la méthode de la cavité. Par ailleurs il est bien connu quele groupe de renormalisation a échoué jusque ici à pouvoir prédire le comportement des observablescritiques dans les verres hors champs moyen. Nous avons donc choisi d'étudier des systèmes eninteraction à longue portée dont on ignore encore si la physique est identique à celle du champmoyen. Nous avons montré dans une première partie, la facilité avec laquelle on peut décrire unetransformation du groupe de renormalisation dans les systèmes ferromagnétiques en interaction àlongue portée dé finies sur le réseau hiérarchique de Dyson. Dans un second temps, nous avons portéenotre attention sur des modèles de verre de spin sur ce même réseau. Un début d'analyse sur cestransformations dans l'espace réel est présenté ainsi qu'une comparaison de la mesure de l'exposantcritique nu par différentes méthodes. Si la transformation décrite semble prometteuse il faut cependantnoter que celle-ci doit encore être améliorée afin d'être considérée comme une méthode valide pournotre système. Nous avons continué dans cette même direction en analysant un modèle d'énergiesaléatoires toujours en utilisant la topologie du réseau hiérarchique. Nous avons étudié numériquementce système dans lequel nous avons pu observer l'existence d'une transition de phase de type « criseentropique » tout à fait similaire à celle du REM de Derrida. Toutefois, notre modèle présente desdifférences importantes avec ce dernier telles que le comportement non-analytique de l'entropie à latransition, ainsi que l'émergence de « criticalité » dont la présence serait à confirmer par d'autres études.Nous montrons également à l'aide de notre méthode numérique comment la température critique dece système peut-être estimée de trois façon différentes.Dans une dernière partie nous avons abordé des problèmes liés aux systèmes complexes. Il aété remarqué récemment que les modèles étudiés dans divers domaines, par exemple la physique, labiologie ou l'informatique, étaient très proches les uns des autres. Ceci est particulièrement vrai dansl'optimisation combinatoire qui a en partie été étudiée par des méthodes de physique statistique. Cesméthodes issues de la théories des verres de spin et des verres structuraux ont été très utilisées pourétudier les transitions de phase qui ont lieux dans ces systèmes ainsi que pour inventer de nouveauxalgorithmes pour ces modèles. Nous avons étudié le problème de l'inférence de modules dans lesréseaux à l'aide de ces même méthodes. Nous présentons une analyse sur la détection des modules topologiques dans des réseaux aléatoires et démontrons la présence d'une transition de phase entre une région où ces modules sont indétectables et une région où ils sont détectables. Par ailleurs, nous avons implémenté pour ces problèmes un algorithme utilisant Belief Propagation afin d'inférer les modules ainsi que d'apprendre leurs propriétés en ayant pour unique information la structure du réseau. Finalementnous avons appliqué cet algorithme sur des réseaux construits à partir de données réelles et discutonsles développements à apporter à notre méthode. / This thesis presents fundamental and applied aspects of spin glasses theory and complex systems. The first theoretical models of spin glasses appeared during the 1970. They were modelling glassy systems by using random interactions. It took several years before a mean-field theory of spin glasses was solved and understood. Nowadays there exists many different models falling in the class of mean-field models. They are well-understood analytically but also numerically where many methods exist to analyse them, namely the monte-carlo and the cavity method which are now essential numerical tools to investigate spin glass. At the same time, the renormalisation group technique which has been very useful in the past to analyse second order transition failed in many disordered systems to predict the behaviour of critical observables in non-mean-field spin glasses. We have chosen to study long-range interacting systems in which we don't know if the physics is identical to mean-field models. In a first part, we studied a ferromagnetic model on the Dyson hierarchical lattice. In this system with long-range interaction, we showed that it is easy to find a real-space transformation of the renormalisation group to compute the critical exponents. In a second part we focused on a spin glass model built on the same lattice. We made a first study where a real-space transformation is described for this system and we compare the estimations of the critical exponent nu for this model by different methods. The renormalisation group transformation gives some encouraging results but needs to be improved to become a more reliable method in this system. We have then investigated a model of random energies by using the same hierarchical topology. We studied numerically this system where we observed the existence of a phase transition of the same type as the one present in the REM of Derrida. However our model exhibits many different features compare to the REM. We found a non-analytical behaviour of the entropy at the transition and critical properties such as a diverging length-scale should occur according to our results. This last prediction has to be studied by a more direct measurement. By the numerical method we developed, we estimated the critical temperature using three different observables, all giving the same value. In the last part I turned to problems related to complex systems. It has been noticed recently that models of different fields such as physics, biology or computer science were very close to each other. This is particularly true in combinatorial optimisation problem which has been investigated using method of statistical physics. These techniques coming from the field of spin glasses and structural glasses were used to studied phase transitions in such systems and to invent new algorithms. We studied the problem of inference and learning of modular structure in random graphs by these techniques. We analysed the presence of topological clusters in some particular types of random graphs, and we showed that a phase transition occurred between a region where it is possible to detect clusters and a region where it is impossible. We also implemented a new algorithm using Belief Propagation to learn the properties of these clusters and to infer them in networks. We applied this algorithm to real-graph and discussed further development of this problem.

No description available.