L'amélioration de la résolution des images satellites optiques permet de distinguer les différents objets qui composent une scène. Néanmoins il reste difficile d'extraire les caractéristiques ou les régions qui sont pertinentes pour la description d'une scène. L'interprétation de ce type de données requiert donc l'introduction d'outils qui permettent de discriminer les objets d'intérêt du reste de l'image. Dans cette thèse nous proposons des outils de raisonnement spatial qui aident à l'interprétation des images satellites. D'abord nous nous intéressons aux relations spatiales qui peuvent être utiles pour l'interprétation des images satellites. Nous nous concentrons sur les relations spatiales suivantes : entourer, alignement, parallélisme et des relations entre lignes et régions. Pour chacune de ces relations nous introduisons des modèles formels, qui considèrent la sémantique des relations et le leur contexte d'utilisation. Ensuite nous proposons une utilisation des modèles de relations spatiales pour des tâches de haut niveau: nous introduisons un système d'interprétation qui est capable de trouver les instanciations d'un modèle structurel dans une image. Le problème d'interprétation d'une image est formulé comme un problème de satisfaction de contraintes floues. Nous proposons des algorithmes de propagation adaptés aux relations complexes telles que l'alignement, et qui prennent en compte les difficultés de détection des objets dans les images. Ce système a été testé sur des scènes contenant des ports et des aéroports et les résultats montrent l'intérêt d'incorporer cette méthodologie dans un système d'interprétation d'image plus complet.

Dans les disciplines de l'intelligence artificielle et de la recherche opérationnelle, on rencontre de nombreux problèmes comme l'allocation de ressources, l'ordonnancement, la, conception, le diagnostic automatisé. Ces problèmes se formulent aisément comme des problèmes de satisfaction de contraintes (CSP). Un CSP est défini comme étant un ensemble de contraintes impliquant un certain nombre de variables. L'objectif consiste simplement à trouver un ensemble de valeurs à affecter aux variables, de sorte que toutes les contraintes soient satisfaites. Dans le cas le plus général, les problèmes de satisfaction de contraintes ont un aspect fortement combinatoire qui leur confère une grande complexité. Nous nous intéressons dans le cadre de cette thèse aux problèmes de satisfaction de contraintes binaires en domaines finis. Les méthodes auxquelles nous nous intéressons pour résoudre un CSP sont, les méthodes dites incomplètes : elles font une réparation d'une configuration en parcourant de manière non systématique l'espace des configurations. Dans cette catégorie de méthodes, notre intérêt s'est plus particulièrement tourné vers les Algorithmes Evolutionnistes. Ce sont des méthodes générales d'optimisation combinatoire qui sont inspirées de la théorie de l'évolution. Dans un CSP classique, on recherche une solution, sans avoir à optimiser de fonction. Pour entrer dans le cadre des Algorithmes Évolutionnistes, on se doit de définir une fonction d'évaluation pour les CSP qui prend ses valeurs minimales sur les solutions du problème. Cette fonction pourrait être utilisée par toutes méthodes incomplètes, telles que les techniques min-conflits, GSAT et leurs variantes. Nous montrons dans cette thèse l'application de notre fonction d'évaluation pour la méthode min-conflits ainsi que pour un algorithme évolutionniste. D'un autre côté, dans le contexte plus spécifique des algorithmes génétiques, nous souhaitons guider l'évolution (i.e. recherche d'une solution), en faisant des transformations sur la population plus orientées vers le problème de satisfaction de contraintes. Nous définissons ainsi des opérateurs de mutation et de croisement spécialisés pour les CSP qui sont basés sur la structure du graphe de contraintes. Ensuite, nous incorporons le concept d'adaptation dans l'opérateur de croisement, afin d'améliorer la recherche de l'algorithme. Dans ce mémoire, nous décrivons et justifions les algorithmes mis en oeuvre, en illustrant les techniques implémentées par la résolution de problèmes de coloriage de graphe avec trois couleurs, et de CSP générés aléatoirement.

Les problèmes de satisfaction de contraintes distribués (DisCSP) permettent de formaliser divers problèmes qui se situent dans l'intelligence artificielle distribuée. Ces problèmes consistent à trouver une combinaison cohérente des actions de plusieurs agents. Durant cette thèse nous avons apporté plusieurs contributions dans le cadre des DisCSPs. Premièrement, nous avons proposé le Nogood-Based Asynchronous Forward-Checking (AFC-ng). Dans AFC-ng, les agents utilisent les nogoods pour justifier chaque suppression d'une valeur du domaine de chaque variable. Outre l'utilisation des nogoods, plusieurs backtracks simultanés venant de différents agents vers différentes destinations sont autorisés. En deuxième lieu, nous exploitons les caractéristiques intrinsèques du réseau de contraintes pour exécuter plusieurs processus de recherche AFC-ng d'une manière asynchrone à travers chaque branche du pseudo-arborescence obtenu à partir du graphe de contraintes dans l'algorithme Asynchronous Forward-Checking Tree (AFC-tree). Puis, nous proposons deux nouveaux algorithmes de recherche synchrones basés sur le même mécanisme que notre AFC-ng. Cependant, au lieu de maintenir le forward checking sur les agents non encore instanciés, nous proposons de maintenir la consistance d'arc. Ensuite, nous proposons Agile Asynchronous Backtracking (Agile-ABT), un algorithme de changement d'ordre asynchrone qui s'affranchit des restrictions habituelles des algorithmes de backtracking asynchrone. Puis, nous avons proposé une nouvelle méthode correcte pour comparer les ordres dans ABT_DO-Retro. Cette méthode détermine l'ordre le plus pertinent en comparant les indices des agents dès que les compteurs d'une position donnée dans le timestamp sont égaux. Finalement, nous présentons une nouvelle version entièrement restructurée de la plateforme DisChoco pour résoudre les problèmes de satisfaction et d'optimisation de contraintes distribués.

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.

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.

La description détaillée des systèmes désordonnés et vitreux représente un défi central en physique statistique et de la matière condensée, puisqu'à ce jour il n'existe pas de théorie unique et établie permettant de comprendre ces systèmes, pourtant omniprésents.Ce travail de recherche est lié en particulier à l'étude des matériaux vitreux à basse température. Plus précisément, si l'on considère des systèmes formés par un ensemble de particules athermiques avec des interactions répulsives de portée finie, en augmentant la densité, on peut observer une transition dite d'encombrement ("jamming"). Celle-ci consiste en un blocage des degrés de liberté accompagné par une augmentation spectaculaire de la rigidité du matériau.Nous étudierons ce problème à l’aide d’une analogie formelle entre des modèles de sphères et le perceptron, un modèle théorique qui développe une transition d'encombrement et des phénomènes de frustration typiques des systèmes désordonnés.En tant que modèle en champ moyen, il permet d'obtenir des résultats analytiques précis et généralisables à des systèmes à haute dimension.L'enjeu majeur de cette étude est de reconstruire le spectre des modes de vibration et toutes les propriétés pertinentes d'une phase spécifique (correspondant au régime dit des sphères dures).Dans ce cadre, nous dériverons le potentiel effectif en fonction des paramètres d'ordre du modèle et nous montrerons qu'il est dominé à proximité du point de jamming par une interaction logarithmique non triviale, qui clarifiera le lien entre les forces de contact et les distances moyennes entre les particules, dans la région critique et au-delà.Comprendre pleinement la transition d'encombrement et les propriétés du perceptron nous permettra de faire des progrès dans plusieurs domaines reliés. En premier lieu, cela peut conduire à une théorie complète des systèmes amorphes, à la fois en dimension infinie et en dimension finie.De plus, le modèle du perceptron semble avoir un lien étroit avec des problèmes dits de Von Neumann. En effet, les systèmes biologiques et écologiques développent souvent des propriétés liées à une condition pseudo-critique en mettant en oeuvre des mécanismes d'optimisation de ressource-consommation.Est-il possible d'identifier un régime caractérisé par une brisure de symétrie? Quel serait le spectre de fluctuations d'énergie dans ces systèmes?Ce ne sont que quelques-unes des questions auxquelles nous essayerons de répondre dans cette thèse.Cependant, l'approximation de champ moyen peut parfois fournir des informationsincorrectes ou trompeuses, en particulier dans l'étude de certaines transitions de phase et la détermination des dimensions critiques inférieure et supérieure.Afin d'avoir une vue d'ensemble et pouvoir manipuler correctement des systèmes en dimension finie, dans la suite de la thèse nous discuterons comment obtenir un développement perturbatif systématique, applicable à tout modèle, à condition que ce dernier soit défini sur un réseau ou un graphe biparti.Notre motivation est en particulier liée à la possibilité d'étudier certaines transitions de phase du second ordre qui existent sur le réseau de Bethe - c'est-à-dire un réseau en arbre sans boucles dont chaque noeud a une connectivité fixe - mais qui sont qualitativement différentes ou absentes dans le modèle entièrement connecté correspondant. / The detailed description of disordered and glassy systems represents an open problem in statistical physics and condensed matter. As yet, there is no single, well-established theory allowing to understand such systems. The research presented in this thesis is related in particular to the study of glassy materials in the low-temperature regime. More precisely, considering systems formed by athermal particles subject to repulsive short-range interactions, upon progressively increasing the density, a so-called jamming transition can be detected. It entails a freezing of the degrees of freedom and hence a huge increase of the material rigidity.We shall study this problem in view of a formal analogy between sphere models and the perceptron, a theoretical model undergoing a jamming transition and frustration phenomena typical of disordered systems. Being a mean-field model, it allows to obtain exact analytical results, which are generalizable to more complex high-dimensional settings.The main aim is to reconstruct the vibrational spectrum and all the relevant properties of a specific phase of the perceptron, corresponding to the hard-sphere regime.In this framework, we will derive the effective potential as a function of the gaps between and forces among the particles, and we will show that it is dominated by a non-trivial logarithmic interaction near the jamming point. This interaction in turn will clarify the relations existing between the relevant variables of the system, in the critical jamming region and beyond.Understanding the jamming transition and the perceptron properties will allow us to make progress in several related fields. First, this study could lay part of the groundwork towards a complete theory of amorphous systems, in both infinite and finite dimensions. Furthermore, the perceptron model seems to a have a close connection with the so-called Von Neumann problems. Indeed, biological and ecological systems often develop pseudo-critical properties and give rise to general mechanisms of resource-consumption optimisation.Is the identification of a broken symmetry regime possible? What would it yield in terms of the spectrum of the energy fluctuations?These are just a few questions we shall attempt to answer in this context.However, the mean-field approximation can sometimes provide wrong or misleading information, especially in studying certain phase transitions and determining the exact lower and upper critical dimensions. To have a broad perspective and correctly deal with finite-dimensional systems, in the second part of the thesis we will discuss obtaining a systematic perturbative expansion which can be applied to any model, as long as defined on a lattice or a bipartite graph.Our motivation is in particular due to the possibility of studying relevant second-order phase transitions which exist on the Bethe lattice — a lattice with a locally tree-like structure and fixed connectivity for each node — but which are qualitatively different or absent in the corresponding fully-connected version.

Le test à base de modèles des systèmes réactifs est le processus de vérifier si un système sous test (SUT) est conforme à sa spécification. Il consiste à gérer à la fois la génération des données de test et le calcul de verdicts en utilisant des modèles. Nous spécifions le comportement des systèmes réactifs à l'aide des systèmes de transitions symboliques temporisées à entrée-sortie (TIOSTS). Quand les TIOSTSs sont utilisés pour tester des systèmes avec une interface centralisée, l'utilisateur peut ordonner complètement les événements (i.e., les entrées envoyées au système et les sorties produites). Les interactions entre le testeur et le SUT consistent en des séquences d'entrées et de sortie nommées traces, pouvant être séparées par des durées dans le cadre du test temporisé, pour former ce que l'on appelle des traces temporisées. Les systèmes distribués sont des collections de composants locaux communiquant entre eux et interagissant avec leur environnement via des interfaces physiquement distribuées. Différents événements survenant à ces différentes interfaces ne peuvent plus être ordonnés. Cette thèse concerne le test de conformité des systèmes distribués où un testeur est placé à chaque interface localisée et peut observer ce qui se passe à cette interface. Nous supposons qu'il n'y a pas d’horloge commune mais seulement des horloges locales pour chaque interface. La sémantique de tels systèmes est définie comme des tuples de traces temporisées. Nous considérons une approche du test dans le contexte de la relation de conformité distribuée dtioco. La conformité globale peut être testée dans une architecture de test en utilisant des testeurs locaux sans communication entre eux. Nous proposons un algorithme pour vérifier la communication pour un tuple de traces temporisées en formulant le problème de message-passing en un problème de satisfaction de contraintes (CSP). Nous avons mis en œuvre le calcul des verdicts de test en orchestrant à la fois les algorithmes du test centralisé off-line de chacun des composants et la vérification des communications par le biais d'un solveur de contraintes. Nous avons validé notre approche sur un cas étude de taille significative. / Model-based testing of reactive systems is the process of checking if a System Under Test (SUT) conforms to its model. It consists of handling both test data generation and verdict computation by using models. We specify the behaviour of reactive systems using Timed Input Output Symbolic Transition Systems (TIOSTS) that are timed automata enriched with symbolic mechanisms to handle data. When TIOSTSs are used to test systems with a centralized interface, the user may completely order events occurring at this interface (i.e., inputs sent to the system and outputs produced from it). Interactions between the tester and the SUT are sequences of inputs and outputs named traces, separated by delays in the timed framework, to form so-called timed traces. Distributed systems are collections of communicating local components which interact with their environment at physically distributed interfaces. Interacting with such a distributed system requires exchanging values with it by means of several interfaces in the same testing process. Different events occurring at different interfaces cannot be ordered any more. This thesis focuses on conformance testing for distributed systems where a separate tester is placed at each localized interface and may only observe what happens at this interface. We assume that there is no global clock but only local clocks for each localized interface. The semantics of such systems can be seen as tuples of timed traces. We consider a framework for distributed testing from TIOSTS along with corresponding test hypotheses and a distributed conformance relation called dtioco. Global conformance can be tested in a distributed testing architecture using only local testers without any communication between them. We propose an algorithm to check communication policy for a tuple of timed traces by formulating the verification of message passing in terms of Constraint Satisfaction Problem (CSP). Hence, we were able to implement the computation of test verdicts by orchestrating both localised off-line testing algorithms and the verification of constraints defined by message passing that can be supported by a constraint solver. Lastly, we validated our approach on a real case study of a telecommunications distributed system.