71 |
Laplaciens des graphes sur les surfaces et applications à la physique statistique / Laplacians on graphs on surfaces and applications to statistical physicsKassel, Adrien 24 June 2013 (has links)
Nous étudions le déterminant du laplacien sur les fibrés vectoriels sur les graphes et l'utilisons, en lien avec des techniques d'analyse complexe discrète, pour comprendre des modèles de physique statistique. Nous calculons certaines constantes de réseaux, construisons des limites d'échelles d'excursions de la marche aléatoire à boucles effacées sur les surfaces, et étudions certains champs gaussiens et processus déterminantaux. / We study the determinant of the Laplacian on vector bundles on graphs and use it, combined with discrete complex analysis, to study models of statistical physics. We compute exact lattice constants, construct scaling limits for excursions of the loop-erased random walk on surfaces, and study some Gaussian fields and determinantal processes.
|
72 |
Inference and modeling of biological networks : a statistical-physics approach to neural attractors and protein fitness landscapes / Inférence et modélisation de réseaux biologiques par la physique statistique : des attracteurs neuronaux au paysage de fitness des protéinesPosani, Lorenzo 07 December 2018 (has links)
L'avènement récent des procédures expérimentales à haut débit a ouvert une nouvelle ère pour l'étude quantitative des systèmes biologiques. De nos jours, les enregistrements d'électrophysiologie et l'imagerie du calcium permettent l'enregistrement simultané in vivo de centaines à des milliers de neurones. Parallèlement, grâce à des procédures de séquençage automatisées, les bibliothèques de protéines fonctionnelles connues ont été étendues de milliers à des millions en quelques années seulement. L'abondance actuelle de données biologiques ouvre une nouvelle série de défis aux théoriciens. Des méthodes d’analyse précises et transparentes sont nécessaires pour traiter cette quantité massive de données brutes en observables significatifs. Parallèlement, l'observation simultanée d'un grand nombre d'unités en interaction permet de développer et de valider des modèles théoriques visant à la compréhension mécanistique du comportement collectif des systèmes biologiques. Dans ce manuscrit, nous proposons une approche de ces défis basée sur des méthodes et des modèles issus de la physique statistique, en développent et appliquant ces méthodes au problèmes issu de la neuroscience et de la bio-informatique : l’étude de la mémoire spatiale dans le réseau hippocampique, et la reconstruction du paysage adaptatif local d'une protéine. / The recent advent of high-throughput experimental procedures has opened a new era for the quantitative study of biological systems. Today, electrophysiology recordings and calcium imaging allow for the in vivo simultaneous recording of hundreds to thousands of neurons. In parallel, thanks to automated sequencing procedures, the libraries of known functional proteins expanded from thousands to millions in just a few years. This current abundance of biological data opens a new series of challenges for theoreticians. Accurate and transparent analysis methods are needed to process this massive amount of raw data into meaningful observables. Concurrently, the simultaneous observation of a large number of interacting units enables the development and validation of theoretical models aimed at the mechanistic understanding of the collective behavior of biological systems. In this manuscript, we propose an approach to both these challenges based on methods and models from statistical physics. We present an application of these methods to problems from neuroscience and bioinformatics, focusing on (1) the spatial memory and navigation task in the hippocampal loop and (2) the reconstruction of the fitness landscape of proteins from homologous sequence data.
|
73 |
Simulation numérique de l'initiation de la rupture à l'échelle atomique / Atomistic simulation of brittle failure initiationSouguir, Sabri 28 November 2018 (has links)
En ingénierie mécanique, la rupture des matériaux est un risque qu'il convient d'anticiper et qui reste aujourd'hui une menace pour les structures. La rupture des systèmes pré-fissurés a lieu quand l'énergie libérée par la propagation de la fissure préexistante excède un seuil critique (taux de restitution d'énergie) qui représente une propriété du matériau. Au contraire, la rupture de systèmes sans défauts préexistants survient lorsque la contrainte appliquée atteint la résistance, également propriété du matériau. L'existence de deux critères pour la rupture semble indiquer des mécanismes d'amorçage différents, ce qui soulève la question des cas réels intermédiaires qui présentent des concentrations de contrainte modérées. Différentes approches existantes sont cohérentes avec les deux situations limites mais il n'y a pas de consensus clair dans la communauté scientifique. Dans cette thèse, nous étudions les mécanismes de la rupture fragile à l'échelle atomique afin d'en comprendre l'origine physique pour différentes concentrations de contraintes. La rupture provient de la rupture des liaisons à l'échelle atomique. Nous utilisons donc des techniques de simulation moléculaire pour étudier la physique élémentaire de l'initiation de la rupture fragile. Dans ce but, on étudie deux types de structure atomique. Le premier est un matériau modèle à maille triangulaire, dont le potentiel permet d'interpréter analytiquement, et avec précision, les résultats des simulations moléculaires. L'étude est étendue à un système plus réel : le graphène. Ce matériau, qui présente une résistance élevée au regard de sa faible ténacité, a l'une des plus petites tailles de zone d'élaboration par rapport aux autres matériaux fragiles, ce qui permet d'appliquer numériquement les concepts de la rupture fragile jusqu'à l'échelle nanométrique de la simulation moléculaire. On s'intéresse dans un premier temps à la rupture des matériaux à 0K. À cette température, un système atomique est en équilibre statique. La rupture peut donc être traitée comme une instabilité. L'analyse du profil énergétique du système atomique fournit un moyen d'identifier les mécanismes de rupture. Nous montrons qu'on peut identifier la rupture en cherchant les valeurs propres nulles ou négative de la matrice hessienne. Les vecteurs propres correspondants indiquent les modes de rupture et montrent l'apparition de bandes de transition entre mouvements de groupes d'atomes pour des systèmes intacts, dont la largeur rappelle la longueur d'élaboration, généralement introduite dans des théories macroscopiques d'initiation de la rupture. On étudie aussi l'effet de la présence de défauts sur les modes d'instabilité et leur dégénérescence. Cette étude fournit une technique générale pour identifier les mécanismes d'initiation de rupture quelle que soit la concentration de contrainte dans la structure. On s'intéresse ensuite aux températures non nulles. On étudie les effets combinés de la température, de la taille du système et du taux de chargement. En partant de la théorie cinétique, nous montrons qu'il existe des lois d'échelle générales fournissant une équivalence taille-vitesse de chargement-température et permettant de relier résistance et ténacité à la limite à 0K. La différence entre la loi d'échelle en résistance et celle en ténacité réside dans le fait que la rupture ne soit pas sensible à la taille du système pré-fissuré mais au nombre de pointes de fissure. Cela indique une différence statistique essentielle entre la rupture en résistance et la fracture ce qui permet de mieux comprendre la transition de l'une à l'autre. Dans l'esprit de mieux comprendre la transition entre les deux types de rupture, on traite le cas de trous elliptiques à différents rapports d'aspects et on analyse en même temps l'effet de cette transition sur les modes d'instabilité. On étudie en dernière partie, l'effet des surfaces libres et les différents paramètres caractérisant cette situation / In mechanical engineering, failure is a risk that must be anticipated and is still a threat for structures. The failure of pre-cracked systems occurs when the energy released by the propagation of the pre-existing crack exceeds a critical threshold (Griffith's energy release rate) which represents a property of the material. On the contrary, the failure of systems without pre-existing defects occurs when the applied stress reaches the strength, also property of the material. The existence of two criteria for failure suggests different driving mechanisms, which raises the question of intermediate cases with moderate stress concentrations. Different existing approaches are consistent with the two limit cases but there is no clear consensus in the scientific community.In this work, we study the mechanisms of brittle failure on the atomic scale in order to understand the underlying physical mechanisms. Macroscopic failure comes from the breaking of bonds at the atomic scale. We therefore use molecular simulation techniques to study the elementary physics of brittle failure initiation. Two types of atomic structure are studied. The first one is a triangular lattice toy model whose simplicity allows precise analytical interpretation of the molecular simulation results. The study is extended to a more realistic system: graphene. This material, which has a high strength and a rather low toughness in comparison, has one of the smallest process zones compared to other brittle materials, which makes it possible to apply the concepts of brittle failure up to the nanometric scale of molecular simulation. We first investigate the failure of materials at 0K. At this temperature, an atomic system is in static equilibrium. The breaking of bonds can be treated as instability. The analysis of the energy profile of the atomic system provides a means of identifying the mechanisms of failure. We show that we can identify failure initiation by looking for negative or zero eigenvalues of the Hessian matrix. The corresponding eigenvectors indicate the modes of failure and show the appearance of transition bands between motions of groups of atoms for intact systems, whose width recalls the size of the process zone, generally introduced in macroscopic theories of failure initiation. We also study the effect of defects on the instability modes and their degeneracy. This study provides a general technique to capture fracture initiation mechanisms irrespective of the stress concentration in the structure. We focus afterwards on finite temperatures. We study the combined effects of temperature, system size and loading rate. Starting from the kinetic theory, we identify general scaling laws providing a size-loading rate-temperature equivalence and relating the strength and toughness to the limit at 0K. The difference between the scaling law of strength and that of toughness lies in the fact that failure is not sensitive to the size of the pre-cracked system but to the number of crack tips. This indicates an essential statistical difference between strength and fracture failures which makes it possible to better understand the transition from one to the other.In order to better understand the transition between the two types of failure, we treat the case of elliptic holes with different aspect ratios and we focus at the same time on the effect of this transition on instability modes. We study in the last part the case of non-periodic structures with free surfaces. We determine the various parameters characterizing this situation and the effect of the presence of surface phenomena on instability modes
|
74 |
Restricted Boltzmann machines : from compositional representations to protein sequence analysis / Machines de Boltzmann restreintes : des représentations compositionnelles à l'analyse des séquences de protéinesTubiana, Jérôme 29 November 2018 (has links)
Les Machines de Boltzmann restreintes (RBM) sont des modèles graphiques capables d’apprendre simultanément une distribution de probabilité et une représentation des données. Malgré leur architecture relativement simple, les RBM peuvent reproduire très fidèlement des données complexes telles que la base de données de chiffres écrits à la main MNIST. Il a par ailleurs été montré empiriquement qu’elles peuvent produire des représentations compositionnelles des données, i.e. qui décomposent les configurations en leurs différentes parties constitutives. Cependant, toutes les variantes de ce modèle ne sont pas aussi performantes les unes que les autres, et il n’y a pas d’explication théorique justifiant ces observations empiriques. Dans la première partie de ma thèse, nous avons cherché à comprendre comment un modèle si simple peut produire des distributions de probabilité si complexes. Pour cela, nous avons analysé un modèle simplifié de RBM à poids aléatoires à l’aide de la méthode des répliques. Nous avons pu caractériser théoriquement un régime compositionnel pour les RBM, et montré sous quelles conditions (statistique des poids, choix de la fonction de transfert) ce régime peut ou ne peut pas émerger. Les prédictions qualitatives et quantitatives de cette analyse théorique sont en accord avec les observations réalisées sur des RBM entraînées sur des données réelles. Nous avons ensuite appliqué les RBM à l’analyse et à la conception de séquences de protéines. De part leur grande taille, il est en effet très difficile de simuler physiquement les protéines, et donc de prédire leur structure et leur fonction. Il est cependant possible d’obtenir des informations sur la structure d’une protéine en étudiant la façon dont sa séquence varie selon les organismes. Par exemple, deux sites présentant des corrélations de mutations importantes sont souvent physiquement proches sur la structure. A l’aide de modèles graphiques tels que les Machine de Boltzmann, on peut exploiter ces signaux pour prédire la proximité spatiale des acides-aminés d’une séquence. Dans le même esprit, nous avons montré sur plusieurs familles de protéines que les RBM peuvent aller au-delà de la structure, et extraire des motifs étendus d’acides aminés en coévolution qui reflètent les contraintes phylogénétiques, structurelles et fonctionnelles des protéines. De plus, on peut utiliser les RBM pour concevoir de nouvelles séquences avec des propriétés fonctionnelles putatives par recombinaison de ces motifs. Enfin, nous avons développé de nouveaux algorithmes d’entraînement et des nouvelles formes paramétriques qui améliorent significativement la performance générative des RBM. Ces améliorations les rendent compétitives avec l’état de l’art des modèles génératifs tels que les réseaux génératifs adversariaux ou les auto-encodeurs variationnels pour des données de taille intermédiaires. / Restricted Boltzmann machines (RBM) are graphical models that learn jointly a probability distribution and a representation of data. Despite their simple architecture, they can learn very well complex data distributions such the handwritten digits data base MNIST. Moreover, they are empirically known to learn compositional representations of data, i.e. representations that effectively decompose configurations into their constitutive parts. However, not all variants of RBM perform equally well, and little theoretical arguments exist for these empirical observations. In the first part of this thesis, we ask how come such a simple model can learn such complex probability distributions and representations. By analyzing an ensemble of RBM with random weights using the replica method, we have characterised a compositional regime for RBM, and shown under which conditions (statistics of weights, choice of transfer function) it can and cannot arise. Both qualitative and quantitative predictions obtained with our theoretical analysis are in agreement with observations from RBM trained on real data. In a second part, we present an application of RBM to protein sequence analysis and design. Owe to their large size, it is very difficult to run physical simulations of proteins, and to predict their structure and function. It is however possible to infer information about a protein structure from the way its sequence varies across organisms. For instance, Boltzmann Machines can leverage correlations of mutations to predict spatial proximity of the sequence amino-acids. Here, we have shown on several synthetic and real protein families that provided a compositional regime is enforced, RBM can go beyond structure and extract extended motifs of coevolving amino-acids that reflect phylogenic, structural and functional constraints within proteins. Moreover, RBM can be used to design new protein sequences with putative functional properties by recombining these motifs at will. Lastly, we have designed new training algorithms and model parametrizations that significantly improve RBM generative performance, to the point where it can compete with state-of-the-art generative models such as Generative Adversarial Networks or Variational Autoencoders on medium-scale data.
|
75 |
Self-assembly of dipolar particles / Auto-assemblage de particules dipolairesSpiteri, Ludovic 21 December 2018 (has links)
Cette thèse couvre l'auto-assemblage de particules dipolaires (magnétiques/électriques). Ces systèmes sont abondants en physique de la matière condensée (molécules et nanoparticules magnétiques, particules colloïdales magnétiques, bactérie magnétotactique, etc.). Sur un plan fondamental, ils représentent un défi important en raison de l'anisotropie et de la longue portée de l'interaction de paire. Le principal objectif de ce travail de recherche est de prédire les microstructures de ces systèmes en tenant compte de façon adéquate de l'interaction complexe dipôle-dipôle ainsi que des effets stériques et ceux dus à un éventuel confinement. Comprendre et revisiter les interactions de filaments dipolaires tels que des aiguilles et des chaînes faites de billes dipolaires est une première étape importante de cette thèse. En effet, les chaînes sont les constituants élémentaires de nombreux systèmes dipolaires, notamment sous l'effet d'un champ magnétique extérieur appliqué. Ensuite, l'agrégation colonnaire des chaînes dipolaires est examinée, ce qui conduit aussi naturellement à l'étude des cristaux dipolaires massifs où une nouvelle phase est découverte. Le cas plus générique des chaînes hélicoïdales est discuté en considérant les situations limites que sont les chaînes linéaires droites et en zigzag. L'association des chaînes dipolaires, dans le cas bidimensionnel, forme des rubans, puis une monocouche avec un réseau hexagonal. La réponse non triviale d'un tel réseau à un champ magnétique perpendiculaire imposé est aussi étudiée. Il est démontré qu'un réseau rhombique peut être induit de cette façon. Finalement, la sédimentation de particules paramagnétiques dans une monocouche inclinée en présence d'un champ magnétique est explorée via une étude mêlant expériences, théorie et simulations. L'ordre induit par gravité s'avère être une voie prometteuse pour l'élaboration contrôlée de réseaux bidimensionnels / This thesis covers the self-assembly of dipolar (magnetic/dielectric) particles. These systems are abundant in condensed matter physics (magnetic molecules and nanoparticles, magnetic colloidal particles, magnetotactic bacteria, etc). They also represent a fundamental challenge owing to the both long range and anisotropic nature of the pair interaction. The main objective of this research work is to predict the microstructures of these systems by properly handling the intricate dipole-dipole interaction combined with steric and possibly confinement effects. Understanding and revisiting the interaction of dipolar filaments such as needles or chains made up of dipolar beads is a first important achievement in this thesis. Indeed, the chains are the fundamental building blocks of many dipolar systems especially under applied external magnetic field. Then, the columnar aggregation of dipolar chains is investigated which naturally leads to the study of the bulk dipolar crystals. A new phase is discovered there. The more generic case of helical chains is discussed by considering limiting situations such as straight linear chains and zigzag chains. The association of dipolar chains in two-dimensions forms ribbons then a monolayer with triangular lattice symmetry. The interesting response of such a layer to an imposed perpendicular magnetic is addressed as well. It is demonstrated that rhombicity can be induced that way. Finally, sedimenting paramagnetic particles in a tilted monolayer in presence of a magnetic field are investigated by experiments, theory and simulations. The gravity-mediated ordering is found to be a promising route to elaborate tailored two-dimensional patterns
|
76 |
Collective Behavior of active colloids / Comportements collectifs de colloïdes autopropulsésTheurkauff, Isaac 29 November 2013 (has links)
Nous étudions le comportement collectif d'une assemblée de colloïdes Janus, des sphères d'or de 1µm dont une moitié est recouverte de platine. Lorsqu'ils sont immergés dans une solution d'eau oxygénée, ils se déplacent à des vitesses de l'ordre de 5µm/s, contrôlable par la concentration en peroxyde. Individuellement, ces colloïdes suivent une marche aléatoire persistante ; Ils interagissent par effets phorétiques, formant des clusters dynamiques de quelques dizaines de colloïdes. Ces clusters, mobiles, échangent continuellement des colloïdes, se divisent et se fusionnent, formant une phase stationnaire. Nous avons développés ces colloïdes, ainsi qu'un système d'acquisition pour détecter et reconstituer les trajectoires des colloïdes. La taille moyenne des clusters augmente linéairement avec l'activité, définie comme la vitesse moyenne des colloïdes en dehors des clusters. La fonction densité de probabilité de la taille des clusters est une loi de puissance d'exposant -2. Nous quantifions les vitesses de translation et de rotation des clusters. Pour réaliser une étude thermodynamique, nous réalisons des expériences de sédimentation. Une transition est observée, entre une phase peu dense, un gaz parfait, dans lequel on mesure une température effective, et une phase dense à la dynamique hétérogène. L'équation d'état du système est mesurée, et une forme analytique heuristique est proposée / We study the collective behavior of an assembly of Janus Colloids. These are 1µm gold colloids with one half coated in platinum. When immersed in a peroxide bath, they self-propel, owing to diffusiophoresis and electrophoresis, moving at velocities of order 5µm/s. The velocity can be tune by adjusting the amount of peroxide in the bath. At the single particle level, the colloids undergo a persistent random walk. When in denser groups, the colloids interact through chemical and steric effects. The combination of these interactions, with the colloids activity, leads to collective effects. A dynamic cluster phase is observed, the formation of motile clusters of colloids, formed of up to 100 colloids. The clusters are in a stationary state, constantly moving, and exchanging colloids, they are also colliding, merging and breaking apart. We developed both the colloids, whose synthesis is described, and a high-throughput acquisition and analysis system. We measure the positions, and reconstruct the trajectories of thousands of colloids for a few minutes. From the trajectories, we extract statistical observables. We show that the sizes of clusters increases linearly as a function of the activity of the colloids. The probability distribution functions of sizes are power laws. As the density increases, a jamming transition is observed. The dense phase heterogeneous dynamics is characterized. We study the transition from the dense phase to a low density assembly with sedimentation experiments. The low density phase behaves as an ideal gas, allowing the definition of an effective temperature. We measure an equation of state for the system, and propose a heuristic collapse
|
77 |
Étude des systèmes critiques bidimensionnels possédant des symetries discrètes : les th\éories conformes parafermioniques, et leurs applications.Estienne, Benoit 30 September 2009 (has links) (PDF)
Cette thèse est consacrée à l'étude des systèmes critiques possédant des symétries discrètes, en deux dimensions. Les théories conformes jouent un rôle central dans la compréhension des phénomènes critiques des systèmes bidimensionnels, et la symétrie discrète additionnelle donne lieu aux théories dites parafermioniques. Dans une première partie, nous étudions les flots du groupe de renormalisation sous l'effet de perturbations faiblement pertinentes pour ces théories parafermioniques . En utilisant les techniques issues du Gaz de Coulomb et de la représentation coset de ces théories conformes, nous avons obtenu perturbativement les équations du groupe de renormalisation. Nous avons ainsi mis en évidence des flots non massifs entre différentes théories parafermioniques. Dans une deuxiéme partie, nous étudions les applications des théories conformes parafermioniques à l'effet Hall quantique fractionnaire. Nous montrons, en calculant les fonctions de corrélation correspondantes, que les théories parafermioniques unitaires fournissent des candidats interessants pour décrire certains états non-abéliens, en particulier elles permettent de corriger les problèmes de non-unitarité. Enfin nous prouvons une conjecture reliant les polynômes de Jack aux théories W.
|
78 |
Applications exploratoires des modèles de spins au Traitement Automatique de la LangueFernandez Sabido, Silvia 22 May 2009 (has links) (PDF)
Dans cette thèse nous avons exploré la capacité des modèles magnétiques de la physique statistique à extraire l'information essentielle contenue dans les textes. Les documents ont été représentés comme des ensembles d'unités en interaction magnétique, l'intensité de telles interactions a été mesurée et utilisée pour calculer de quantités qui sont des indices de l'importance de l'information portée. Nous proposons deux nouvelles méthodes. Premièrement, nous avons étudié un modèle de spins qui nous a permis d'introduire l'énergie textuelle d'un document. Cette quantité a été utilisée comme indicatrice de pertinence et appliquée à une vaste palette de tâches telles que le résumé automatique, la recherche d'information, la classification de documents et la segmentation thématique. Par ailleurs, et de façon encore exploratoire, nous proposons un deuxième algorithme qui définie un couplage grammatical pour conserver les termes importants et produire des contractions. De cette façon, la compression d'une phrase est l'état fondamental de la chaîne de termes. Comme cette compression n'est pas forcement bonne, il a été intéressant de produire des variantes en permettant des fluctuations thermiques. Nous avons fait des simulations Métropolis Monte-Carlo avec le but de trouver l'état fondamental de ce système qui est analogue au verre de spin. Les deux systèmes, utilisant des méthodes numériques, restent indépendants de la langue.
|
79 |
Quelques aspects de physique statistique des systèmes corrélésClusel, Maxime 22 July 2005 (has links) (PDF)
Les travaux regroupés dans cette th`ese traitent de différents aspects de la physique statistique dessystèmes corrélés. Dans la première partie de cette thèse on s'intéresse aux fluctuations de grandeurs globalesdans les systèmes corrélés, dont de nombreux travaux sur des systèmes variés proposent qu'elles soientbien d´ecrites par la distribution BHP issue du modèle XY 2d. Le modèle d'Ising 2d est utilisé pour tester cette proposition et laquantifier. En utilisant des observations issues de simulations Monte Carlo, une étude analytique montre quel'apparente universalité de BHP est reliée au modèle gaussien obtenu par perturbation. et que des écarts àBHP d'importance variable existe, provenant de la contribution d'un terme non-gaussien. Dans la secondepartie, on s'intéresse à l'étude de la décohérence d'un système quantique à deux niveaux, induite par unbruit intermittent présentant un spectre en 1/f et du vieillissement. Un tel bruit peut schématiser l'effet d'unenvironnement corrélé sur un Qbit. En utilisant des résultats de probabilité, on peut calculer le facteur dedécohérence dans de nombreux régimes. On obtient alors des scénarios de décohérence anormaux, présentantune décroissance en loi de puissance aux temps longs, ainsi que de la non-stationnarité. Enfin la dernièrepartie est dédiée `a l'étude des solutions exactes du modèle d'Ising 2d classique, avec un champ magnétiquesur un bord. En généralisant une méthode due à Plechko, on obtient la fonction de partition de ce systèmeau moyen d'une action gaussienne fermionique unidimensionnelle. Dans le cas d'un champ homogène, onretrouve les résultats précédents de McCoy et Wu. On peut aller au-delà en considérant le cas où le champmagnétique change de direction une fois au bord. Cette méthode permet alors de décrire une transition detype mouillage, induite par ce défaut d'orientation. Il est en particulier possible d'obtenir analytiquement lediagramme de phase de ce système.
|
80 |
Phases vitreuses, optimisation et grandes déviationsRivoire, Olivier 11 July 2005 (has links) (PDF)
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.
|
Page generated in 0.0395 seconds