La technique des répliques est une technique formidable prenant ses origines de la physique statistique, comme un moyen de calculer l'espérance du logarithme de la constante de normalisation d'une distribution de probabilité à haute dimension. Dans le jargon de physique, cette quantité est connue sous le nom de l’énergie libre, et toutes sortes de quantités utiles, telle que l’entropie, peuvent être obtenue de là par des dérivées. Cependant, ceci est un problème NP-difficile, qu’une bonne partie de statistique computationelle essaye de résoudre, et qui apparaît partout; de la théorie des codes, à la statistique en hautes dimensions, en passant par les problèmes de satisfaction de contraintes. Dans chaque cas, la méthode des répliques, et son extension par (Parisi et al., 1987), se sont prouvées fortes utiles pour illuminer quelques aspects concernant la corrélation des variables de la distribution de Gibbs et la nature fortement nonconvexe de son logarithme negatif. Algorithmiquement, il existe deux principales méthodologies adressant la difficulté de calcul que pose la constante de normalisation: a). Le point de vue statique: dans cette approche, on reformule le problème en tant que graphe dont les nœuds correspondent aux variables individuelles de la distribution de Gibbs, et dont les arêtes reflètent les dépendances entre celles-ci. Quand le graphe en question est localement un arbre, les procédures de message-passing sont garanties d’approximer arbitrairement bien les probabilités marginales de la distribution de Gibbs et de manière équivalente d'approximer la constante de normalisation. Les prédictions de la physique concernant la disparition des corrélations à longues portées se traduise donc, par le fait que le graphe soit localement un arbre, ainsi permettant l’utilisation des algorithmes locaux de passage de messages. Ceci va être le sujet du chapitre 4. b). Le point de vue dynamique: dans une direction orthogonale, on peut contourner le problème que pose le calcul de la constante de normalisation, en définissant une chaîne de Markov le long de laquelle, l’échantillonnage converge à celui selon la distribution de Gibbs, tel qu’après un certain nombre d’itérations (sous le nom de temps de relaxation), les échantillons sont garanties d’être approximativement générés selon elle. Afin de discuter des conditions dans lesquelles chacune de ces approches échoue, il est très utile d’être familier avec la méthode de replica symmetry breaking de Parisi. Cependant, les calculs nécessaires sont assez compliqués, et requièrent des notions qui sont typiquemment étrangères à ceux sans un entrainement en physique statistique. Ce mémoire a principalement deux objectifs : i) de fournir une introduction a la théorie des répliques, ses prédictions, et ses conséquences algorithmiques pour les problèmes de satisfaction de constraintes, et ii) de donner un survol des méthodes les plus récentes adressant la transition de phase, prédite par la méthode des répliques, dans le cas du problème k−SAT, à partir du point de vu statique et dynamique, et finir en proposant un nouvel algorithme qui prend en considération la transition de phase en question. / The replica trick is a powerful analytic technique originating from statistical physics as an attempt to compute the expectation of the logarithm of the normalization constant of a high dimensional probability distribution known as the Gibbs measure. In physics jargon this quantity is known as the free energy, and all kinds of useful quantities, such as the entropy, can be obtained from it using simple derivatives. The computation of this normalization constant is however an NP-hard problem that a large part of computational statistics attempts to deal with, and which shows up everywhere from coding theory, to high dimensional statistics, compressed sensing, protein folding analysis and constraint satisfaction problems. In each of these cases, the replica trick, and its extension by (Parisi et al., 1987), have proven incredibly successful at shedding light on keys aspects relating to the correlation structure of the Gibbs measure and the highly non-convex nature of − log(the Gibbs measure()). Algorithmic speaking, there exists two main methodologies addressing the intractability of the normalization constant: a) Statics: in this approach, one casts the system as a graphical model whose vertices represent individual variables, and whose edges reflect the dependencies between them. When the underlying graph is locally tree-like, local messagepassing procedures are guaranteed to yield near-exact marginal probabilities or equivalently compute Z. The physics predictions of vanishing long range correlation in the Gibbs measure, then translate into the associated graph being locally tree-like, hence permitting the use message passing procedures. This will be the focus of chapter 4. b) Dynamics: in an orthogonal direction, we can altogether bypass the issue of computing the normalization constant, by defining a Markov chain along which sampling converges to the Gibbs measure, such that after a number of iterations known as the relaxation-time, samples are guaranteed to be approximately sampled according to the Gibbs measure. To get into the conditions in which each of the two approaches is likely to fail (strong long range correlation, high energy barriers, etc..), it is very helpful to be familiar with the so-called replica symmetry breaking picture of Parisi. The computations involved are however quite involved, and come with a number of prescriptions and prerequisite notions (s.a. large deviation principles, saddle-point approximations) that are typically foreign to those without a statistical physics background. The purpose of this thesis is then twofold: i) to provide a self-contained introduction to replica theory, its predictions, and its algorithmic implications for constraint satisfaction problems, and ii) to give an account of state of the art methods in addressing the predicted phase transitions in the case of k−SAT, from both the statics and dynamics points of view, and propose a new algorithm takes takes these into consideration.

No description available.

Les symétries géométriques jouent un rôle important dans la compréhension de la stabilité de tout système physique. En structure nucléaire, elles sont reliées à la forme du champ moyen utilisé pour décrire les propriétés des noyaux atomiques. Dans le cadre de cette thèse, nous avons utilisé les prédictions obtenues avec l'aide du Hamiltonien du champ moyen nucléaire avec le potentiel de Woods-Saxon Universel pour étudier les effets des symétries dites de « Haut-Rang ». Ces symétries ponctuelles mènent à des dégénérescences des états nucléaires d’ordre 4. Il est prédit que la symétrie tétraédrique influence la stabilité des noyaux proches des nombres magiques tétraédriques [Z,N]=[32,40,56,64,70,90-94,136]. Nous avons sélectionné la région des Terres-Rares proche du noyau doublement magique tétraédrique 154Gd pour notre étude. Dans cette région, il existe des structures de parité négative qui sont mal comprises. Or la symétrie tétraédrique, en tant que déformation octupolaire non-axiale, brise la symétrie par réflexion et doit produire des états de parité négative. Après une étude systématique des propriétés expérimentales des noyaux de la région, nous avons sélectionné le 156Gd comme objet de notre étude des modes d’excitation octupolaire. Nous avons utilisé les probabilités réduites de transition gamma pour discerner ces différents modes. Pour atteindre cet objectif, nous avons réalisé trois expériences de spectroscopie gamma à l’ILL de Grenoble avec les détecteurs EXILL et GAMS afin de mesurer les durées de vie et les intensités des transitions gamma des états candidats. L'analyse de nos résultats montre que notamment la forme tétraédrique aide à comprendre les probabilités des transitions dipolaires. Ce résultat ouvre de nouvelles perspectives expérimentales et théoriques. / Geometrical symmetries play an important role in the understanding of all physical systems. In nuclear structure they are linked to the shape of the mean-field used to describe the atomic nuclei properties. In the framework of this thesis, we have used the predictions obtained with the help of the nuclear mean-field Hamiltonian with the Universal Woods-Saxon potential to study the effects of the so-called “High-Rank” symmetries. These point-group symmetries lead to a nuclear state degeneracy of the order of 4. It is predicted that the tetrahedral symmetry affects the stability of nuclei close to the tetrahedral magic numbers [Z,N]=[32,40,56,64,70,90-94,136]. We have selected the Rare-Earth region close to the tetrahedral doubly magic nucleus 154Gd for our study. In this region, there exists negative parity structures poorly understood. Yet the tetrahedral symmetry, as related to a non-axial octupole deformation, breaks the reflection symmetry and leads to the negative parity states. Following a systematics of experimental properties of the nuclei in this region, we have selected 156Gd as the object of our study for the octupole excitation modes. We have used the reduced transitions probabilities to discriminate between these modes. To achieve this goal, we have performed three gamma spectroscopy experiments at the ILL in Grenoble with the EXILL and GAMS detectors to measure the lifetimes and the gamma transition intensities from the candidate states. The analysis of our results shows that including the tetrahedral shape helps to understand the dipole transition probabilities. This result will open new experimental and theoretical perspectives.