Дисертації з теми "Algorithme de passage de message"

Le mode adjoint de la Différentiation Algorithmique (DA) est particulièrement intéressant pour le calcul des gradients. Cependant, ce mode utilise les valeurs intermédiaires de la simulation d'origine dans l'ordre inverse à un coût qui augmente avec la longueur de la simulation. La DA cherche des stratégies pour réduire ce coût, par exemple en profitant de la structure du programme donné. Dans ce travail, nous considérons d'une part le cas des boucles à point-fixe pour lesquels plusieurs auteurs ont proposé des stratégies adjointes adaptées. Parmi ces stratégies, nous choisissons celle de B. Christianson. Nous spécifions la méthode choisie et nous décrivons la manière dont nous l'avons implémentée dans l'outil de DA Tapenade. Les expériences sur une application de taille moyenne montrent une réduction importante de la consommation de mémoire. D'autre part, nous étudions le checkpointing dans le cas de programmes parallèles MPI avec des communications point-à-point. Nous proposons des techniques pour appliquer le checkpointing à ces programmes. Nous fournissons des éléments de preuve de correction de nos techniques et nous les expérimentons sur des codes représentatifs. Ce travail a été effectué dans le cadre du projet européen ``AboutFlow''
The adjoint mode of Algorithmic Differentiation (AD) is particularly attractive for computing gradients. However, this mode needs to use the intermediate values of the original simulation in reverse order at a cost that increases with the length of the simulation. AD research looks for strategies to reduce this cost, for instance by taking advantage of the structure of the given program. In this work, we consider on one hand the frequent case of Fixed-Point loops for which several authors have proposed adapted adjoint strategies. Among these strategies, we select the one introduced by B. Christianson. We specify further the selected method and we describe the way we implemented it inside the AD tool Tapenade. Experiments on a medium-size application shows a major reduction of the memory needed to store trajectories. On the other hand, we study checkpointing in the case of MPI parallel programs with point-to-point communications. We propose techniques to apply checkpointing to these programs. We provide proof of correctness of our techniques and we experiment them on representative CFD codes

Cette thèse s’intéresse à l’application de méthodes de physique statistique des systèmes désordonnés ainsi que de l’inférence à des problèmes issus du traitement du signal et de la théorie du codage, plus précisément, aux problèmes parcimonieux d’estimation linéaire. Les outils utilisés sont essentiellement les modèles graphiques et l’algorithme approximé de passage de messages ainsi que la méthode de la cavité (appelée analyse de l’évolution d’état dans le contexte du traitement de signal) pour son analyse théorique. Nous aurons également recours à la méthode des répliques de la physique des systèmes désordonnées qui permet d’associer aux problèmes rencontrés une fonction de coût appelé potentiel ou entropie libre en physique. Celle-ci permettra de prédire les différentes phases de complexité typique du problème, en fonction de paramètres externes tels que le niveau de bruit ou le nombre de mesures liées au signal auquel l’on a accès : l’inférence pourra être ainsi typiquement simple, possible mais difficile et enfin impossible. Nous verrons que la phase difficile correspond à un régime où coexistent la solution recherchée ainsi qu’une autre solution des équations de passage de messages. Dans cette phase, celle-ci est un état métastable et ne représente donc pas l’équilibre thermodynamique. Ce phénomène peut-être rapproché de la surfusion de l’eau, bloquée dans l’état liquide à une température où elle devrait être solide pour être à l’équilibre. Via cette compréhension du phénomène de blocage de l’algorithme, nous utiliserons une méthode permettant de franchir l’état métastable en imitant la stratégie adoptée par la nature pour la surfusion : la nucléation et le couplage spatial. Dans de l’eau en état métastable liquide, il suffit d’une légère perturbation localisée pour que se créer un noyau de cristal qui va rapidement se propager dans tout le système de proche en proche grâce aux couplages physiques entre atomes. Le même procédé sera utilisé pour aider l’algorithme à retrouver le signal, et ce grâce à l’introduction d’un noyau contenant de l’information locale sur le signal. Celui-ci se propagera ensuite via une "onde de reconstruction" similaire à la propagation de proche en proche du cristal dans l’eau. Après une introduction à l’inférence statistique et aux problèmes d’estimation linéaires, on introduira les outils nécessaires. Seront ensuite présentées des applications de ces notions. Celles-ci seront divisées en deux parties. La partie traitement du signal se concentre essentiellement sur le problème de l’acquisition comprimée où l’on cherche à inférer un signal parcimonieux dont on connaît un nombre restreint de projections linéaires qui peuvent être bruitées. Est étudiée en profondeur l’influence de l’utilisation d’opérateurs structurés à la place des matrices aléatoires utilisées originellement en acquisition comprimée. Ceux-ci permettent un gain substantiel en temps de traitement et en allocation de mémoire, conditions nécessaires pour le traitement algorithmique de très grands signaux. Nous verrons que l’utilisation combinée de tels opérateurs avec la méthode du couplage spatial permet d’obtenir un algorithme de reconstruction extrê- mement optimisé et s’approchant des performances optimales. Nous étudierons également le comportement de l’algorithme confronté à des signaux seulement approximativement parcimonieux, question fondamentale pour l’application concrète de l’acquisition comprimée sur des signaux physiques réels. Une application directe sera étudiée au travers de la reconstruction d’images mesurées par microscopie à fluorescence. La reconstruction d’images dites "naturelles" sera également étudiée. En théorie du codage, seront étudiées les performances du décodeur basé sur le passage de message pour deux modèles distincts de canaux continus. Nous étudierons un schéma où le signal inféré sera en fait le bruit que l’on pourra ainsi soustraire au signal reçu. Le second, les codes de superposition parcimonieuse pour le canal additif Gaussien est le premier exemple de schéma de codes correcteurs d’erreurs pouvant être directement interprété comme un problème d’acquisition comprimée structuré. Dans ce schéma, nous appliquerons une grande partie des techniques étudiée dans cette thèse pour finalement obtenir un décodeur ayant des résultats très prometteurs à des taux d’information transmise extrêmement proches de la limite théorique de transmission du canal
This thesis is interested in the application of statistical physics methods and inference to signal processing and coding theory, more precisely, to sparse linear estimation problems. The main tools are essentially the graphical models and the approximate message-passing algorithm together with the cavity method (referred as the state evolution analysis in the signal processing context) for its theoretical analysis. We will also use the replica method of statistical physics of disordered systems which allows to associate to the studied problems a cost function referred as the potential of free entropy in physics. It allows to predict the different phases of typical complexity of the problem as a function of external parameters such as the noise level or the number of measurements one has about the signal: the inference can be typically easy, hard or impossible. We will see that the hard phase corresponds to a regime of coexistence of the actual solution together with another unwanted solution of the message passing equations. In this phase, it represents a metastable state which is not the true equilibrium solution. This phenomenon can be linked to supercooled water blocked in the liquid state below its freezing critical temperature. Thanks to this understanding of blocking phenomenon of the algorithm, we will use a method that allows to overcome the metastability mimicing the strategy adopted by nature itself for supercooled water: the nucleation and spatial coupling. In supercooled water, a weak localized perturbation is enough to create a crystal nucleus that will propagate in all the medium thanks to the physical couplings between closeby atoms. The same process will help the algorithm to find the signal, thanks to the introduction of a nucleus containing local information about the signal. It will then spread as a "reconstruction wave" similar to the crystal in the water. After an introduction to statistical inference and sparse linear estimation, we will introduce the necessary tools. Then we will move to applications of these notions. They will be divided into two parts. The signal processing part will focus essentially on the compressed sensing problem where we seek to infer a sparse signal from a small number of linear projections of it that can be noisy. We will study in details the influence of structured operators instead of purely random ones used originally in compressed sensing. These allow a substantial gain in computational complexity and necessary memory allocation, which are necessary conditions in order to work with very large signals. We will see that the combined use of such operators with spatial coupling allows the implementation of an highly optimized algorithm able to reach near to optimal performances. We will also study the algorithm behavior for reconstruction of approximately sparse signals, a fundamental question for the application of compressed sensing to real life problems. A direct application will be studied via the reconstruction of images measured by fluorescence microscopy. The reconstruction of "natural" images will be considered as well. In coding theory, we will look at the message-passing decoding performances for two distincts real noisy channel models. A first scheme where the signal to infer will be the noise itself will be presented. The second one, the sparse superposition codes for the additive white Gaussian noise channel is the first example of error correction scheme directly interpreted as a structured compressed sensing problem. Here we will apply all the tools developed in this thesis for finally obtaining a very promising decoder that allows to decode at very high transmission rates, very close of the fundamental channel limit

Les réseaux de communications sans fil, qu’ils soient cellulaires ou ad hoc mobiles (MANETs), doivent permettre des transmissions de données de plus en plus massives en raison de l’augmentation du nombre d’utilisateurs et de l’émergence de nouvelles applications à forte consommation, tout en gérant efficacement les rares ressources radio disponibles. Il est donc crucial d’améliorer l’efficacité spectrale et énergétique de ces systèmes pour répondre à ces besoins croissants. Récemment, des organismes de standardisation (3GPP pour les réseaux cellulaires) ont proposé de nouveaux schémas d’accès dit non orthogonaux aux ressources (NOMA), en combinaison avec des méthodes plus classiques telles que l’utilisation d’antennes multiples en émission et en réception (MIMO). Cependant, ces schémas introduisent également des défis techniques, notamment la génération d’interférences entre utilisateurs, complexifiant le processus de détection du signal au niveau du récepteur. Les fabricants d’équipements radio, tels que Thales, explorent ces solutions NOMA pour les MANETs afin d’accroître leur maturité technique et de relever leurs défis.Des récepteurs numériques itératifs utilisant l’inférence bayésienne approximée, notamment les méthodes de passage de messages qui démontrent leur capacité à surpasser les récepteurs classiques de la littérature, en particulier dans des conditions de propagation avec des niveaux élevés d’interférences. Alors que la propagation de croyance (BP) a été la première méthode utilisée, il semble que la propagation d’espérance (EP) soit capable d’atteindre de meilleurs compromis entre performance et complexité, à la fois dans des scénarios typiques avec peu d’utilisateurs et des débits faibles, et dans des scénarios envisagés pour les réseaux de prochaine génération (Beyond 5G, 6G) avec des dizaines d’utilisateurs partageant les mêmes ressources et des débits élevés.Dans cette thèse, nous proposons des détecteurs doublement itératifs (auto et turbo itérés) capables de conserver les performances de l’état de l’art EP tout en diminuant la complexité sur toute une gamme de configurations, allant de déploiements restreints avec peu d’utilisateurs à des déploiements massifs avec des centaines d’utilisateurs. Nous avons travaillé la représentation graphique de la factorisation de la probabilité a posteriori des symboles à détecter en utilisant des méthodes de décomposition matricielle et/ou d’annulation d’interférences. Nous proposons la dérivation de plusieurs récepteurs basés sur EP et BP répondant aux exigences des nouveaux enjeux de communication. De plus, grâce à un ordonnancement réfléchi des messages internes au détecteur, nous sommes capables d’améliorer les performances sans augmentation significative de la complexité et d’atteindre de meilleurs compromis entre performance/complexité.Nous proposons également une étude des performances asymptotiques de nos récepteurs afin de quantifier leur efficacité spectrale à l’aide d’outils d’analyse issus de la théorie de l’information. L’impact de certains facteurs tels que l’imperfection des connaissances sur le canal de propagation est également étudié, ainsi que des méthodes pour renforcer nos récepteurs, garantissant leur utilisation dans une variété de situations
Wireless communication networks, whether cellular or mobile ad hoc networks (MANETs), must accommodate increasingly massive data transmissions due to the growing number of users and new high-consumption applications, all while efficiently managing the available scarce radio resources. It is therefore crucial to enhance the spectral and energy efficiency of these systems to meet these growing needs.Recently, standardization bodies such as 3GPP for cellular networks proposed new schemes for accessing non-orthogonal resources (NOMA) in combination with more traditional methods, such as the use of multiple-input and multiple-output (MIMO) antennas.However, these schemes also introduce technical challenges, particularly the generation of interference between users, complicating the signal detection process at the receiver. Radio equipment manufacturers, like Thales, are exploring NOMA solutions for MANETs to be able to address their challenges and increase their technical maturity.Iterative digital receivers utilizing approximate Bayesian inference, specifically message-passing methods, demonstrate the ability to outperform conventional receivers of the literature, especially in propagating conditions/setups with high levels of interference. While belief propagation (BP) was the initial method employed, it appears that expectation propagation (EP) is capable of achieving better trade-offs between performance and complexity,both in typical scenarios with few users and low data rates and in scenarios envisioned fornext-generation networks (Beyond 5G, 6G) with dozens of users sharing the same resourcesand high data rates.In this thesis, we propose doubly iterative detectors (auto and turbo iterated) capable of maintaining the performance of state-of-the-art EP while reducing complexity across a range of configurations, from small deployments with few users to massive deployments with hundreds of users. We worked on the graphical representation of the factorization of the posterior probability of the symbols to be detected by using matrix decomposition and/or interference cancellation methods. We propose the derivation of several EP and BP-based receivers meeting the requirements of the new communication challenges. Furthermore, thanks to the thoughtful scheduling of internal messages within the detector, we are able to enhance performance without a significant increase in complexity and achieve better trade-offs between performance and complexity.We also conduct a study of the asymptotic performance of our receivers to quantify their spectral efficiency using analysis tools from the information theory. The impact of factors such as imperfect knowledge of the propagation channel is also investigated, along with methods to reinforce our receivers, ensuring their use in a variety of situations

Dans les dernières années, plusieurs problèmes ont été étudiés à l'interface entre la physique statistique et l'informatique. La raison étant que, souvent, ces problèmes peuvent être réinterprétés dans le langage de la physique des systèmes désordonnés, où un grand nombre de variables interagit à travers champs locales qui dépendent de l'état du quartier environnant. Parmi les nombreuses applications de l'optimisation combinatoire le routage optimal sur les réseaux de communication est l'objet de la première partie de la thèse. Nous allons exploiter la méthode de la cavité pour formuler des algorithmes efficaces de type ‘’message-passing’’ et donc résoudre plusieurs variantes du problème grâce à sa mise en œuvre numérique. Dans un deuxième temps, nous allons décrire un modèle pour approcher la version dynamique de la méthode de la cavité, ce qui permet de diminuer la complexité du problème de l'exponentielle de polynôme dans le temps. Ceci sera obtenu en utilisant le formalisme de ‘’Matrix Product State’’ de la mécanique quantique.Un autre sujet qui a suscité beaucoup d'intérêt en physique statistique de processus dynamiques est la marche aléatoire sur les réseaux. La théorie a été développée depuis de nombreuses années dans le cas que la topologie dessous est un réseau de dimension d. Au contraire le cas des réseaux aléatoires a été abordé que dans la dernière décennie, laissant de nombreuses questions encore ouvertes pour obtenir des réponses. Démêler plusieurs aspects de ce thème fera l'objet de la deuxième partie de la thèse. En particulier, nous allons étudier le nombre moyen de sites distincts visités au cours d'une marche aléatoire et caractériser son comportement en fonction de la topologie du graphe. Enfin, nous allons aborder les événements rares statistiques associées aux marches aléatoires sur les réseaux en utilisant le ‘’Large deviations formalism’’. Deux types de transitions de phase dynamiques vont se poser à partir de simulations numériques. Nous allons conclure décrivant les principaux résultats d'une œuvre indépendante développée dans le cadre de la physique hors de l'équilibre. Un système résoluble en deux particules browniens entouré par un bain thermique sera étudiée fournissant des détails sur une interaction à médiation par du bain résultant de la présence du bain
In the last years several problems been studied at the interface between statistical physics and computer science. The reason being that often these problems can be reinterpreted in the language of physics of disordered systems, where a big number of variables interacts through local fields dependent on the state of the surrounding neighborhood. Among the numerous applications of combinatorial optimisation the optimal routing on communication networks is the subject of the first part of the thesis. We will exploit the cavity method to formulate efficient algorithms of type message-passing and thus solve several variants of the problem through its numerical implementation. At a second stage, we will describe a model to approximate the dynamic version of the cavity method, which allows to decrease the complexity of the problem from exponential to polynomial in time. This will be obtained by using the Matrix Product State formalism of quantum mechanics. Another topic that has attracted much interest in statistical physics of dynamic processes is the random walk on networks. The theory has been developed since many years in the case the underneath topology is a d-dimensional lattice. On the contrary the case of random networks has been tackled only in the past decade, leaving many questions still open for answers. Unravelling several aspects of this topic will be the subject of the second part of the thesis. In particular we will study the average number of distinct sites visited during a random walk and characterize its behaviour as a function of the graph topology. Finally, we will address the rare events statistics associated to random walks on networks by using the large-deviations formalism. Two types of dynamic phase transitions will arise from numerical simulations, unveiling important aspects of these problems. We will conclude outlining the main results of an independent work developed in the context of out-of-equilibrium physics. A solvable system made of two Brownian particles surrounded by a thermal bath will be studied providing details about a bath-mediated interaction arising for the presence of the bath

À une époque où l'utilisation des données a atteint un niveau sans précédent, l'apprentissage machine, et plus particulièrement l'apprentissage profond basé sur des réseaux de neurones artificiels, a été responsable de très importants progrès pratiques. Leur utilisation est désormais omniprésente dans de nombreux domaines d'application, de la classification d'images à la reconnaissance vocale en passant par la prédiction de séries temporelles et l'analyse de texte. Pourtant, la compréhension de nombreux algorithmes utilisés en pratique est principalement empirique et leur comportement reste difficile à analyser. Ces lacunes théoriques soulèvent de nombreuses questions sur leur efficacité et leurs potentiels risques. Établir des fondements théoriques sur lesquels asseoir les observations numériques est devenu l'un des défis majeurs de la communauté scientifique.La principale difficulté qui se pose lors de l’analyse de la plupart des algorithmes d'apprentissage automatique est de traiter analytiquement et numériquement un grand nombre de variables aléatoires en interaction. Dans ce manuscrit, nous revisitons une approche basée sur les outils de la physique statistique des systèmes désordonnés. Développés au long d’une riche littérature, ils ont été précisément conçus pour décrire le comportement macroscopique d'un grand nombre de particules, à partir de leurs interactions microscopiques. Au cœur de ce travail, nous mettons fortement à profit le lien profond entre la méthode des répliques et les algorithmes de passage de messages pour mettre en lumière les diagrammes de phase de divers modèles théoriques, en portant l’accent sur les potentiels écarts entre seuils statistiques et algorithmiques. Nous nous concentrons essentiellement sur des tâches et données synthétiques générées dans le paradigme enseignant-élève. En particulier, nous appliquons ces méthodes à champ moyen à l'analyse Bayes-optimale des machines à comité, à l'analyse des bornes de généralisation de Rademacher pour les perceptrons, et à la minimisation du risque empirique dans le contexte des modèles linéaires généralisés. Enfin, nous développons un cadre pour analyser des modèles d'estimation avec des informations à priori structurées, produites par exemple par des réseaux de neurones génératifs avec des poids aléatoires
At a time when the use of data has reached an unprecedented level, machine learning, and more specifically deep learning based on artificial neural networks, has been responsible for very important practical advances. Their use is now ubiquitous in many fields of application, from image classification, text mining to speech recognition, including time series prediction and text analysis. However, the understanding of many algorithms used in practice is mainly empirical and their behavior remains difficult to analyze. These theoretical gaps raise many questions about their effectiveness and potential risks. Establishing theoretical foundations on which to base numerical observations has become one of the fundamental challenges of the scientific community. The main difficulty that arises in the analysis of most machine learning algorithms is to handle, analytically and numerically, a large number of interacting random variables. In this manuscript, we revisit an approach based on the tools of statistical physics of disordered systems. Developed through a rich literature, they have been precisely designed to infer the macroscopic behavior of a large number of particles from their microscopic interactions. At the heart of this work, we strongly capitalize on the deep connection between the replica method and message passing algorithms in order to shed light on the phase diagrams of various theoretical models, with an emphasis on the potential differences between statistical and algorithmic thresholds. We essentially focus on synthetic tasks and data generated in the teacher-student paradigm. In particular, we apply these mean-field methods to the Bayes-optimal analysis of committee machines, to the worst-case analysis of Rademacher generalization bounds for perceptrons, and to empirical risk minimization in the context of generalized linear models. Finally, we develop a framework to analyze estimation models with structured prior informations, produced for instance by deep neural networks based generative models with random weights

Les réseaux ad hoc mobiles (MANETs) sont des systèmes de communication sans fil rapidement déployables et qui fonctionnent avec une coordination minimale, ceci afin d'éviter les pertes d'efficacité spectrale induites par la signalisation. Les stratégies de transmissions coopératives présentent un intérêt pour les MANETs, mais la nature distribuée de tels protocoles peut augmenter le niveau d'interférence avec un impact autant plus sévère que l'on cherche à pousser les limites des efficacités énergétique et spectrale. L'impact de l'interférence doit alors être réduit par l'utilisation d'algorithmes de traitement du signal au niveau de la couche PHY, avec une complexité calculatoire raisonnable. Des avancées récentes sur les techniques de conception de récepteurs numériques itératifs proposent d'exploiter l'inférence bayésienne approximée et des techniques de passage de message associés afin d'améliorer le potentiel des turbo-détecteurs plus classiques. Entre autres, la propagation d'espérance (EP) est une technique flexible, qui offre des compromis attractifs de complexité et de performance dans des situations où la propagation de croyance conventionnel est limité par sa complexité calculatoire. Par ailleurs, grâce à des techniques émergentes de l'apprentissage profond, de telles structures itératives peuvent être projetés vers des réseaux de détection profonds, où l'apprentissage des hyper-paramètres algorithmiques améliore davantage les performances. Dans cette thèse nous proposons des égaliseurs à retour de décision à réponse impulsionnelle finie basée sur la propagation d'espérance (EP) qui apportent des améliorations significatives, en particulier pour des applications à haute efficacité spectrale vis à vis des turbo-détecteurs conventionnels, tout en ayant l'avantage d'être asymptotiquement prédictibles. Nous proposons un cadre générique pour la conception de récepteurs dans le domaine fréquentiel, afin d'obtenir des architectures de détection avec une faible complexité calculatoire. Cette approche est analysée théoriquement et numériquement, avec un accent mis sur l'égalisation des canaux sélectifs en fréquence, et avec des extensions pour de la détection dans des canaux qui varient dans le temps ou pour des systèmes multi-antennes. Nous explorons aussi la conception de détecteurs multi-utilisateurs, ainsi que l'impact de l'estimation du canal, afin de comprendre le potentiel et le limite de cette approche. Pour finir, nous proposons une méthode de prédiction performance à taille finie, afin de réaliser une abstraction de lien pour l'égaliseur domaine fréquentiel à base d'EP. L'impact d'un modélisation plus fine de la couche PHY est évalué dans le contexte de la diffusion coopérative pour des MANETs tactiques, grâce à un simulateur flexible de couche MAC
Mobile ad hoc networks (MANETs) are rapidly deployable wireless communications systems, operating with minimal coordination in order to avoid spectral efficiency losses caused by overhead. Cooperative transmission schemes are attractive for MANETs, but the distributed nature of such protocols comes with an increased level of interference, whose impact is further amplified by the need to push the limits of energy and spectral efficiency. Hence, the impact of interference has to be mitigated through with the use PHY layer signal processing algorithms with reasonable computational complexity. Recent advances in iterative digital receiver design techniques exploit approximate Bayesian inference and derivative message passing techniques to improve the capabilities of well-established turbo detectors. In particular, expectation propagation (EP) is a flexible technique which offers attractive complexity-performance trade-offs in situations where conventional belief propagation is limited by computational complexity. Moreover, thanks to emerging techniques in deep learning, such iterative structures are cast into deep detection networks, where learning the algorithmic hyper-parameters further improves receiver performance. In this thesis, EP-based finite-impulse response decision feedback equalizers are designed, and they achieve significant improvements, especially in high spectral efficiency applications, over more conventional turbo-equalization techniques, while having the advantage of being asymptotically predictable. A framework for designing frequency-domain EP-based receivers is proposed, in order to obtain detection architectures with low computational complexity. This framework is theoretically and numerically analysed with a focus on channel equalization, and then it is also extended to handle detection for time-varying channels and multiple-antenna systems. The design of multiple-user detectors and the impact of channel estimation are also explored to understand the capabilities and limits of this framework. Finally, a finite-length performance prediction method is presented for carrying out link abstraction for the EP-based frequency domain equalizer. The impact of accurate physical layer modelling is evaluated in the context of cooperative broadcasting in tactical MANETs, thanks to a flexible MAC-level simulator

Face au déluge actuel de données principalement non structurées, les graphes ont démontré, dans une variété de domaines scientifiques, leur importance croissante comme language abstrait pour décrire des interactions complexes entre des objets complexes. L’un des principaux défis posés par l’étude de ces réseaux est l’inférence de propriétés macroscopiques à grande échelle, affectant un grand nombre d’objets ou d’agents, sur la seule base des interactions microscopiquesqu’entretiennent leurs constituants élémentaires. La physique statistique, créée précisément dans le but d’obtenir les lois macroscopiques de la thermodynamique à partir d’un modèle idéal de particules en interaction, fournit une intuition décisive dans l’étude des réseaux complexes.Dans cette thèse, nous utilisons des méthodes issues de la physique statistique des systèmes désordonnés pour mettre au point et analyser de nouveaux algorithmes d’inférence sur les graphes. Nous nous concentrons sur les méthodes spectrales, utilisant certains vecteurs propres de matrices bien choisies, et sur les graphes parcimonieux, qui contiennent une faible quantité d’information. Nous développons une théorie originale de l’inférence spectrale, fondée sur une relaxation de l’optimisation de certaines énergies libres en champ moyen. Notre approche est donc entièrement probabiliste, et diffère considérablement des motivations plus classiques fondées sur l’optimisation d’une fonction de coût. Nous illustrons l’efficacité de notre approchesur différents problèmes, dont la détection de communautés, la classification non supervisée à partir de similarités mesurées aléatoirement, et la complétion de matrices
In an era of unprecedented deluge of (mostly unstructured) data, graphs are proving more and more useful, across the sciences, as a flexible abstraction to capture complex relationships between complex objects. One of the main challenges arising in the study of such networks is the inference of macroscopic, large-scale properties affecting a large number of objects, based solely on he microscopic interactions between their elementary constituents. Statistical physics, precisely created to recover the macroscopic laws of thermodynamics from an idealized model of interacting particles, provides significant insight to tackle such complex networks.In this dissertation, we use methods derived from the statistical physics of disordered systems to design and study new algorithms for inference on graphs. Our focus is on spectral methods, based on certain eigenvectors of carefully chosen matrices, and sparse graphs, containing only a small amount of information. We develop an original theory of spectral inference based on a relaxation of various meanfield free energy optimizations. Our approach is therefore fully probabilistic, and contrasts with more traditional motivations based on the optimization of a cost function. We illustrate the efficiency of our approach on various problems, including community detection, randomized similarity-based clustering, and matrix completion

Le document présente une synthèse de travaux sur le déploiement, l'utilisation et les techniques de mise en oeuvre d'applications développées selon un modèle de programmation à passage de messages sur des grilles de calcul. La première partie décrit les performances observées sur la période 2002-2006 sur une plateforme à l'échelle de la France, ainsi que les gains obtenus par équilibrage de charge. La deuxième partie décrit un intergiciel nouveau baptisé P2P-MPI qui synthétise un ensemble de propositions pour améliorer la prise en charge de tels programmes à passage de messages.

Des antennes multiples du côté de la station de base peuvent être utilisées pour améliorer l'efficacité spectrale et l'efficacité énergétique des technologies sans fil de nouvelle génération. En effet, le multi-entrées et sorties multiples massives (MIMO) est considéré comme une technologie prometteuse pour apporter les avantages susmentionnés pour la norme sans fil de cinquième génération, communément appelée 5G New Radio (5G NR). Dans cette monographie, nous explorerons un large éventail de sujets potentiels dans Multi-userMIMO (MU-MIMO) pertinents pour la 5G NR,• Conception de la formation de faisceaux (BF) maximisant le taux de somme et robustesse à l'état de canal partiel informations à l'émetteur (CSIT)• Analyse asymptotique des différentes techniques BF en MIMO massif et• Méthodes d'estimation de canal bayésien utilisant un apprentissage bayésien clairsemé.L'une des techniques potentielles proposées dans la littérature pour contourner la complexité matérielle et la consommation d'énergie dans le MIMO massif est la formation de faisceaux hybrides. Nous proposons une conception de phaseur analogique globalement optimale utilisant la technique du recuit déterministe, qui nous a valu le prix du meilleur article étudiant. En outre, afin d'analyser le comportement des grands systèmes des systèmes MIMO massifs, nous avons utilisé des techniques de la théorie des matrices aléatoires et obtenu des expressions de taux de somme simplifiées. Enfin, nous avons également examiné le problème de récupération de signal bayésien clairsemé en utilisant la technique appelée apprentissage bayésien clairsemé (SBL)
Multiple antennas at the base station side can be used to enhance the spectral efficiency and energy efficiency of the next generation wireless technologies. Indeed, massive multi-input multi-output (MIMO) is seen as one promising technology to bring the aforementioned benefits for fifth generation wireless standard, commonly known as 5G New Radio (5G NR). In this monograph, we will explore a wide range of potential topics in multi-userMIMO (MU-MIMO) relevant to 5G NR,• Sum rate maximizing beamforming (BF) design and robustness to partial channel stateinformation at the transmitter (CSIT)• Asymptotic analysis of the various BF techniques in massive MIMO and• Bayesian channel estimation methods using sparse Bayesian learning.One of the potential techniques proposed in the literature to circumvent the hardware complexity and power consumption in massive MIMO is hybrid beamforming. We propose a globally optimal analog phasor design using the technique of deterministic annealing, which won us the best student paper award. Further, in order to analyze the large system behaviour of the massive MIMO systems, we utilized techniques from random matrix theory and obtained simplified sum rate expressions. Finally, we also looked at Bayesian sparse signal recovery problem using the technique called sparse Bayesian learning (SBL). We proposed low complexity SBL algorithms using a combination of approximate inference techniques such as belief propagation (BP), expectation propagation and mean field (MF) variational Bayes. We proposed an optimal partitioning of the different parameters (in the factor graph) into either MF or BP nodes based on Fisher information matrix analysis

Les travaux de cette these presente une methode originale pour l'assortiment de structure discretes quand les correspondances sont inconnues. Cette methode evite le traitement point par point base de traitement des methodes existantes avec d'important risques d'explosion combinatoire et considere les structures a comparer dans leur totalite. L'idee de base de cette methode, est la transformation d'une des structures a traiter en une entite continue par des interpolations de ses projections sur les plans d'un repere orthonorme, a l'aide de cubique splines. Une transformation t' composee de rotations et de translations est recherchee. La transformation t' doit pouvoir ramenee les projections de la seconde structure sur la representation continue de la premiere. Suite a cette etape une proposition d'isomorphismes est faite, et la recherche d'une seconde transformation t est operee afin de ramener l'une des structures sur la seconde. Les temps de reponses constates presentent une evolution logarithmique alors que les autres methodes ont une evolution exponentiel. L'interet d'utilisation de cette methode devient evident dans le cas de traitement de structures importantes. Contrairement aux autres methodes, celle presentee dans cette these fait la difference entre un objet et son image miroir d'ou l'idee de son utilisation dans le calcul de la chiralite. Les resultats obtenues ont ete plus que satisfaisants

Les algorithmes d’apprentissage automatique utilisant des réseaux de neurones profonds ont récemment révolutionné l'intelligence artificielle. Malgré l'engouement suscité par leurs diverses applications, les excellentes performances de ces algorithmes demeurent largement inexpliquées sur le plan théorique. Ces problèmes d'apprentissage sont décrits mathématiquement par de très grands ensembles de variables en interaction, difficiles à manipuler aussi bien analytiquement que numériquement. Cette multitude est précisément le champ d'étude de la physique statistique qui s'attelle à comprendre, originellement dans les systèmes naturels, comment rendre compte des comportements macroscopiques à partir de cette complexité microscopique. Dans cette thèse nous nous proposons de mettre à profit les progrès récents des méthodes de champ moyen de la physique statistique des systèmes désordonnés pour dériver des approximations pertinentes dans ce contexte. Nous nous appuyons sur les équivalences et les complémentarités entre les algorithmes de passage de message, les développements haute température et la méthode des répliques. Cette stratégie nous mène d'une part à des contributions pratiques pour l'apprentissage non supervisé des machines de Boltzmann. Elle nous permet d'autre part de contribuer à des réflexions théoriques en considérant le paradigme du professeur-étudiant pour modéliser des situations d'apprentissage. Nous développons une méthode pour caractériser dans ces modèles l'évolution de l'information au cours de l’entraînement, et nous proposons une direction de recherche afin de généraliser l'étude de l'apprentissage bayésien des réseaux de neurones à une couche aux réseaux de neurones profonds
Machine learning algorithms relying on deep new networks recently allowed a great leap forward in artificial intelligence. Despite the popularity of their applications, the efficiency of these algorithms remains largely unexplained from a theoretical point of view. The mathematical descriptions of learning problems involves very large collections of interacting random variables, difficult to handle analytically as well as numerically. This complexity is precisely the object of study of statistical physics. Its mission, originally pointed towards natural systems, is to understand how macroscopic behaviors arise from microscopic laws. In this thesis we propose to take advantage of the recent progress in mean-field methods from statistical physics to derive relevant approximations in this context. We exploit the equivalences and complementarities of message passing algorithms, high-temperature expansions and the replica method. Following this strategy we make practical contributions for the unsupervised learning of Boltzmann machines. We also make theoretical contributions considering the teacher-student paradigm to model supervised learning problems. We develop a framework to characterize the evolution of information during training in these model. Additionally, we propose a research direction to generalize the analysis of Bayesian learning in shallow neural networks to their deep counterparts

Dans cette thèse nous étudions l’isolation mémoire et les mesures de communications efficaces par passage de message dans le contexte des environnements à mémoire partagée et la programmation orientée-objets. L’état de l’art en la matière se base presque exclusivement sur deux techniques complémentaires dites de propriété des objets (ownership) et d’unicité de références (reference uniqueness) afin d’adresser les problèmes de sécurité dans les programmes concurrents. Il est frappant de constater que la grande majorité des travaux existants emploient des méthodes de vérification statique des programmes, qui requirent soit un effort d’annotations soit l’introduction de fortes contraintes sur la forme et les références vers messages échangés. Notre contribution avec SIAAM est la démonstration d’une solution d’isolation réalisée uniquement à l’exécution et basée sur le modèle de programmation par acteurs. Cette solution purement dynamique ne nécessite ni annotations ni vérification statique des programmes. SIAAM permet la communication sans copie de messages de forme arbitraire. Nous présentons la sémantique formelle de SIAAM ainsi qu’une preuve d’isolation vérifiée avec l’assistant COQ. L’implantation du modèle de programmation pour le langage Java est réalisé dans la machine virtuelle JikesRVM. Enfin nous décrivons un ensemble d’analyses statiques qui réduit automatiquement le cout à l’exécution de notre approche
In this thesis we study state isolation and efficient message-passing in the context of concurrent object-oriented programming. The ’ownership’ and ’reference uniqueness’ techniques have been extensively employed to address concurrency safety in the past. Strikingly the vast majority of the previous works rely on a set of statically checkable typing rules, either requiring an annotation overhead or introducing strong restrictions on the shape and the aliasing of the exchanged messages.Our contribution with SIAAM is the demonstration of a purely runtime, actor-based, annotation-free, aliasing-proof approach to concurrent state isolation allowing efficient communication of arbitrary objects graphs. We present the formal semantic of SIAAM, along with a machine-checked proof of isolation. An implementation of the model has been realized in a state-of-the-art Java virtual-machine and a set of custom static analyses automatically reduce the runtime overhead

Ces dernières années, la virtualisation a connu un important regain d'intérêt dans les centres de traitement de données. Elle séduit par la grande flexibilité qu'elle apporte, par ses propriétés d'isolation et de tolérance aux pannes ainsi que par sa capacité à tirer partie des processeurs multicoeurs. Toutes ces caractéristiques en font une solution intéressante pour répondre aux problèmes liés aux évolutions matérielles des grappes de calcul. Cependant, la virtualisation est encore peu mise en oeuvre dans ce cadre, notamment car son impact sur les performances des applications parallèles est considéré comme prohibitif. Pour pallier ce problème, nous avons conçu un périphérique virtuel de communication permettant l'exécution efficace d'applications parallèles dans une grappe de machines virtuelles. Nous proposons en outre un ensemble de techniques permettant de faciliter le déploiement d'applications virtualisées. Ces fonctionnalités ont été regroupées au sein d'un support exécutif permettant de bénéficier des avantages de la virtualisation de la manière la plus transparente possible pour l'utilisateur, et ce en minimisant l'impact sur les performances.

Dans cette thèse nous proposons de nouveaux algorithmes d'analyse vidéo. La première contribution de cette thèse concerne le domaine de la segmentation de vidéos avec pour objectif d'obtenir une segmentation dense et spatio-temporellement cohérente. Nous proposons de combiner les aspects spatiaux et temporels d'une vidéo en une seule notion, celle de Fibre. Une fibre est un ensemble de trajectoires qui sont spatialement connectées par un maillage. Les fibres sont construites en évaluant simultanément les aspects spatiaux et temporels. Par rapport a l’état de l'art une segmentation de vidéo a base de fibres présente comme avantages d’accéder naturellement au voisinage grâce au maillage et aux correspondances temporelles pour la plupart des pixels de la vidéo. De plus, cette segmentation à base de fibres a une complexité quasi linéaire par rapport au nombre de pixels. La deuxième contribution de cette thèse concerne le suivi d'objets multiples. Nous proposons une approche de suivi qui utilise des caractéristiques des points suivis, la cinématique des objets suivis et l'apparence globale des détections. L'unification de toutes ces caractéristiques est effectuée avec un champ conditionnel aléatoire. Ensuite ce modèle est optimisé en combinant les techniques de passage de message et une variante de processus ICM (Iterated Conditional Modes) pour inférer les trajectoires d'objet. Une troisième contribution mineure consiste dans le développement d'un descripteur pour la mise en correspondance d'apparences de personne. Toutes les approches proposées obtiennent des résultats compétitifs ou meilleurs (qualitativement et quantitativement) que l’état de l'art sur des base de données
In this thesis we propose novel algorithms for video analysis. The first contribution of this thesis is in the domain of video segmentation wherein the objective is to obtain a dense and coherent spatio-temporal segmentation. We propose joining both spatial and temporal aspects of a video into a single notion Fiber. A fiber is a set of trajectories which are spatially connected by a mesh. Fibers are built by jointly assessing spatial and temporal aspects of the video. Compared to the state-of-the-art, a fiber based video segmentation presents advantages such as a natural spatio-temporal neighborhood accessor by a mesh, and temporal correspondences for most pixels in the video. Furthermore, this fiber-based segmentation is of quasi-linear complexity w.r.t. the number of pixels. The second contribution is in the realm of multiple object tracking. We proposed a tracking approach which utilizes cues from point tracks, kinematics of moving objects and global appearance of detections. Unification of all these cues is performed on a Conditional Random Field. Subsequently this model is optimized by a combination of message passing and an Iterated Conditional Modes (ICM) variant to infer object-trajectories. A third, minor, contribution relates to the development of suitable feature descriptor for appearance matching of persons. All of our proposed approaches achieve competitive and better results (both qualitatively and quantitatively) than state-of-the-art on open source datasets

Les supercalculateurs deviennent de plus en plus complexes à utiliser. C’est pourquoi l’utilisation de modèle de programmation dit hybride, MPI + X, sont mis en place dans les applications. Ces nouveaux types de modèle permettent une utilisation plus efficace d’un supercalculateur, mais créent aussi de nouveaux problèmes lors de l’exécution des applications. Ces problèmes sont de différents types.Nous étudierons plus précisément trois problèmes liés aux programmations MPI + X. La progression des communications non bloquante de MPI au sein de l’environnement X. Puis deux types de déséquilibre possible dans les applications MPI+X. Le premier étant entre les processus MPI et le second au sein d’un processus MPI, c’est-à-dire le déséquilibre en sein de X.Une solution dans le cas d’un environnement X en tâches récursives sera tout d’abord présentée pour le problème de progression de communication MPI à l’aide d’insertion de tâche de progression dans l’environnement X. Lors du déséquilibre entre processus MPI, une solution de rééquilibrage de ressources au sein d’un nœud sera présentée. Enfin, pour le déséquilibre dans l’environnement X, une solution permettant d’utiliser le déséquilibre pour exécuter une seconde application sera également présentée
Supercomputers are becoming more and more complex to use. This is why the use of so-called hybrid programming models, MPI + X, are being implemented in applications. These new types of models allow a more efficient use of a supercomputer, but also create new problems during the execution of applications. These problems are of different types.More specifically, we will study three problems related to MPI + X programming. The progression of non-blocking MPI communications within the X environment. Then two types of possible imbalance in MPI+X applications. The first being between MPI processes and the second within an MPI process, i.e., imbalance within X.A solution in the case of an X environment in recursive tasks will first be presented for the MPI communication progress problem using progress task insertion in the X environment. For the imbalance between MPI processes, a solution for resource rebalancing within a node will be presented. Finally, for the imbalance in the X environment, a solution to use the imbalance to run a second application will also be presented

Une multitude d'algorithmes d'exclusion mutuelle ont été conçus au cours des vingt cinq dernières années, dans le but d'améliorer les performances liées à l'exécution de sections critiques et aux verrous.Malheureusement, il n'existe actuellement pas d'étude générale et complète au sujet du comportement de ces algorithmes d'exclusion mutuelle sur des applications réalistes (par opposition à des applications synthétiques) qui considère plusieurs métriques de performances, telles que l'efficacité énergétique ou la latence.Dans cette thèse, nous effectuons une analyse pragmatique des mécanismes d'exclusion mutuelle, dans le but de proposer aux développeurs logiciels assez d'informations pour leur permettre de concevoir et/ou d'utiliser des mécanismes rapides, qui passent à l'échelle et efficaces énergétiquement.Premièrement, nous effectuons une étude de performances de 28 algorithmes d'exclusion mutuelle faisant partie de l'état de l'art, en considérant 40 applications et quatre machines multicœurs différentes.Nous considérons non seulement le débit (la métrique de performance traditionnellement considérée), mais aussi l'efficacité énergétique et la latence, deux facteurs qui deviennent de plus en plus importants.Deuxièmement, nous présentons une analyse en profondeur de nos résultats.Plus particulièrement, nous décrivons neufs problèmes de performance liés aux verrous et proposons six recommandations aidant les développeurs logiciels dans le choix d'un algorithme d'exclusion mutuelle, se basant sur les caractéristiques de leur application ainsi que les propriétés des différents algorithmes.A partir de notre analyse détaillée, nous faisons plusieurs observations relatives à l'interaction des verrous et des applications, dont plusieurs d'entre elles sont à notre connaissance originales:(i) les applications sollicitent fortement les primitives lock/unlock mais aussi l'ensemble des primitives de synchronisation liées à l'exclusion mutuelle (ex. trylocks, variables de conditions),(ii) l'empreinte mémoire d'un verrou peut directement impacter les performances de l'application,(iii) pour beaucoup d'applications, l'interaction entre les verrous et l'ordonnanceur du système d'exploitation est un facteur primordial de performance,(iv) la latence d'acquisition d'un verrou a un impact très variable sur la latence d'une application,(v) aucun verrou n'est systématiquement le meilleur,(vi) choisir le meilleur verrou est difficile, et(vii) l'efficacité énergétique et le débit vont de pair dans le contexte des algorithmes d'exclusion mutuelle.Ces découvertes mettent en avant le fait que la synchronisation à base de verrou ne se résume pas seulement à la simple interface "lock - unlock".En conséquence, ces résultats appellent à plus de recherche dans le but de concevoir des algorithmes d'exclusion mutuelle avec une empreinte mémoire faible, adaptatifs et qui implémentent l'ensemble des primitives de synchronisation liées à l'exclusion mutuelle.De plus, ces algorithmes ne doivent pas seulement avoir de bonnes performances d'un point de vue du débit, mais aussi considérer la latence ainsi que l'efficacité énergétique
A plethora of optimized mutual exclusion lock algorithms have been designed over the past 25 years to mitigate performance bottlenecks related to critical sections and synchronization.Unfortunately, there is currently no broad study of the behavior of these optimized lock algorithms on realistic applications that consider different performance metrics, such as energy efficiency and tail latency.In this thesis, we perform a thorough and practical analysis, with the goal of providing software developers with enough information to achieve fast, scalable and energy-efficient synchronization in their systems.First, we provide a performance study of 28 state-of-the-art mutex lock algorithms, on 40 applications, and four different multicore machines.We not only consider throughput (traditionally the main performance metric), but also energy efficiency and tail latency, which are becoming increasingly important.Second, we present an in-depth analysis in which we summarize our findings for all the studied applications.In particular, we describe nine different lock-related performance bottlenecks, and propose six guidelines helping software developers with their choice of a lock algorithm according to the different lock properties and the application characteristics.From our detailed analysis, we make a number of observations regarding locking algorithms and application behaviors, several of which have not been previously discovered:(i) applications not only stress the lock/unlock interface, but also the full locking API (e.g., trylocks, condition variables),(ii) the memory footprint of a lock can directly affect the application performance,(iii) for many applications, the interaction between locks and scheduling is an important application performance factor,(iv) lock tail latencies may or may not affect application tail latency,(v) no single lock is systematically the best,(vi) choosing the best lock is difficult (as it depends on many factors such as the workload and the machine), and(vii) energy efficiency and throughput go hand in hand in the context of lock algorithms.These findings highlight that locking involves more considerations than the simple "lock - unlock" interface and call for further research on designing low-memory footprint adaptive locks that fully and efficiently support the full lock interface, and consider all performance metrics

Le but de cette these est d'etudier et developper des methodes pour la parallelisation efficace des applications scientifiques sur machines paralleles a memoire distribuee. Dans une premiere partie nous presentons deux bibliotheques de fonctions de communication PVM ((\it Parallel Virtual Machine)) et MPI ((\it Message Passing Interface)). Ces dernieres fournissent une portabilite des programmes sur la grande majorite des machines paralleles, mais aussi sur des reseaux d'ordinateurs heterogenes. Cette partie illustre le probleme de la mesure des performances pour des reseaux de processeurs heterogenes. Ceci nous a amene a adapter le calcul du facteur d'acceleration et de l'efficacite afin de pouvoir evaluer les performances d'un algorithme sur un reseau de processeurs heterogenes. La deuxieme partie est consacree a l'etude de bibliotheques numeriques paralleles, comme ScaLAPACK, et au developpement d'une methode etudiee de maniere theorique, mais peu utilisee en pratique pour augmenter les performances des fonctions de ces bibliotheques : le recouvrement calcul/communication. L'idee generale consiste a anticiper les communications, notamment en pipelinant l'envoi des messages. Des resultats experimentaux sur machines Cray T3D et IBM SP1, permettent de valider les etudes theoriques effectuees sur des algorithmes de base de ces bibliotheques
The aim of this thesis is to study and develop efficient methods for parallelization of scientific applications on parallel computers with distributed memory. In the first part we present two libraries of PVM((\it Parallel Virtual Machine)) and MPI ((\it Message Passing Interface)) communication tools. They allow implementation of programs on most parallel machines, but also on heterogeneous computer networks. This chapter illustrates the problems faced when trying to evaluate performances of networks with heterogeneous processors. To evaluate such performances we modified and adapted the concepts of speed-up and efficiency to account for heterogeneity. The second part deals with a study of parallel application libraries such as ScaLAPACK and with the development of communication masking techniques. The general concept is based on communication anticipation, in particular by pipelining message sending operations. Experimental results on Cray T3D and IBM SP1 machines validates the theoretical studies performed on basic algorithms of the libraries discussed above

La conception de prototypes de systèmes de vision en temps réel embarqué est sujet à de multiples contraintes sévères et fortement contradictoires. Dans le cas de capteurs dits "intelligents", il est nécessaire de fournir une puissance de traitement suffisante pour exécuter les algorithmes à la cadence des capteurs d'images avec un dispositif de taille minimale et consommant peu d'énergie. La conception d'un système monopuce (ou SoC) et l'implantation d'algorithmes de plus en plus complexes pose problème si on veut l'associer avec une approche de prototypage rapide d'applications scientifiques. Afin de réduire de manière significative le temps et les différents coûts de conception, le procédé de conception est fortement automatisé. La conception matérielle est basée sur la dérivation d'un modèle d'architecture multiprocesseur générique de manière à répondre aux besoins de capacité de traitement et de communication spécifiques à l'application visée. Les principales étapes manuelles se réduisent au choix et au paramétrage des différents composants matériels synthétisables disponibles. La conception logicielle consiste en la parallélisation des algorithmes, qui est facilitée par l'homogénéité et la régularité de l'architecture de traitement parallèle et la possibilité d'employer des outils d'aide à la parallélisation. Avec l'approche de conception sont présentés les premiers éléments constitutifs qui permettent de la mettre en oeuvre.Ceux ci portent essentiellement sur les aspects de conception matérielle. L'approche proposée est illustrée par l'implantation d'un traitement de stabilisation temps réel vidéo sur technologie SoPC

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 dissémination d'informations (broadcast) est essentielle pour de nombreuses applications réparties. Celle-ci doit être efficace, c'est à dire limiter la redondance des messages, et assurer forte fiabilité et faible latence. Nous considérons ici les algorithmes répartis profitant des propriétés des topologies sous-jacentes. Cependant, ces propriétés et les paramètres dans les algorithmes sont hétérogènes. Ainsi, nous devons trouver une manière pour les comparer équitablement. D'abord, nous étudions les protocoles probabilistes de dissémination d'informations (gossip) exécutées sur trois graphes aléatoires. Les trois graphes représentent les topologies typiques des réseaux à grande-échelle : le graphe de Bernoulli, le graphe géométrique aléatoire et le graphe scale-free. Afin de comparer équitablement leurs performances, nous proposons un nouveau paramètre générique : le fanout effectif. Pour une topologie et un algorithme donnés, le fanout effectif caractérise la puissance moyenne de la dissémination des sites infectés. De plus, il simplifie la comparaison théorique des différents algorithmes sur une topologie. Après avoir compris l'impact des topologies et les algorithmes sur les performances , nous proposons un algorithme fiable et efficace pour la topologie scale-free.

Dans ce mémoire nous abordons de prime abord la reconstruction d'arbres et de réseaux phylogénétiques, à travers deux méthodes d'inférence. Les arbres et les réseaux sont deux supports pour la représentation de l'évolution d'un groupe d'espèces étudiées. Les modèles d'évolution d'espèces qui seront traités sont les suivants : 1) Le modèle arborescent classique qui a longtemps été le seul support formel pour la représentation des relations génétiques entre les espèces. 2) Le modèle en réseau qui permet de représenter des mécanismes phylogénétiques importants pouvant jouer un rôle clé dans l'évolution et pouvant s'expliquer par le phénomène de l'évolution réticulée. Nous nous sommes particulièrement intéressés aux algorithmes d'inférence de réseaux de transferts horizontaux de gènes. Un transfert horizontal de gènes permet à deux espèces de s'échanger, partiellement ou totalement, différents gènes au cours de l'évolution. Le travail effectué sur la reconstruction d'arbres et de réseaux phylogénétiques a mené à la publication de trois articles. Ensuite, nous abordons le problème de réduction du temps d'exécution de différents programmes bioinformatiques. Ce problème a pris de l'ampleur à cause de la croissance du volume de données biologiques et du blocage de la puissance des ordinateurs autour de 3,4GHZ depuis environ deux ans. Nous décrivons un procédé d'accélération des calculs effectués par différents algorithmes d'inférence et de représentation de l'évolution des espèces, en utilisant le parallélisme. Le parallélisme mis en place a été réalisé à travers une librairie standard de passage de messages (Message Passing Interface). Nous montrons les différentes formes de parallélisme, les architectures de systèmes parallèles, quelques environnements qui permettent de supporter l'exécution des applications de façon à exprimer le parallélisme, ainsi que les approches utilisées pour paralléliser différents modèles d'évolution. Les versions parallèles des algorithmes d'évolution ont été développées et installées sur une « grappe » (i.e. cluster) Linux ayant 16 lames possédant chacune deux processeurs et sa propre mémoire. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : algorithmes d'évolution, arbre phylogénétique, réseau phylogénétique, transferts horizontaux de gènes, programmation parallèle, Message Passing Interface (MPI).

Ce travail de thèse a porté sur la détection et localisation de défauts dans les réseaux de distribution HTA par les
indicateurs de passage de défaut (IPD). Les études ont été effectuées dans le cadre du développement attendu et
croissant des GED (sources de Génération d'Energie Décentralisées).
La première partie du mémoire est consacrée à l'analyse du comportement des IPD. En ce qui concerne
l'influence du contexte de fonctionnement sur la réponse des IPD, une partie est destinée à vérifier le
fonctionnement des modèles IPD développés et les règles d'utilisation des IPD prévus. Une autre analyse
l'influence des GED sur l'utilisation des IPD sur la détection et localisation de défauts. Pour l'amélioration de la
robustesse du diagnostic avec IPD en présence de fausses indications, une méthode de détermination de la
section en défaut (limitée par des IPD) est proposée.
La deuxième partie du mémoire est consacrée à une méthode d'optimisation du placement des IPD dans les
réseaux HTA sur la base d'algorithmes génétiques. Nous avons défini différents critères pour l'optimisation ; ils
sont validés par un programme de calcul des indices de fiabilité. L'influence de la GED dans le départ HTA sur
le placement optimal des IPD est analysée en tenant compte du coût de l'énergie non fournie par la GED et du
fonctionnement envisageable comme un secours de la GED.