Utilisés dans de nombreux domaines scientifiques, les Automates Cellulaires Probabilistes, usuellement abrégés en PCA, de l'anglais "Probabilistic Cellular Automata", constituent, au sein des dynamiques aléatoires à temps discret, une classe de systèmes infinis de particules, c'est à dire de processus stochastiques markoviens à valeurs dans un espace infini S^G où S désigne un ensemble fini et G est un graphe infini. On considère ici toujours le cas où G=Z^d. La particularité de ces dynamiques est l'évolution en parallèle, ou synchrone, de chacune des coordonnées ou composants élémentaires en interaction. Nous nous intéressons dans un premier temps à l'existence et à l'unicité des mesures stationnaires pour les dynamiques PCA non dégénérées i.e. dont le comportement local n'est jamais déterministe, ainsi qu'à la caractérisation de ces états d'équilibre en tant que mesures gibbsiennes. Nous fondant sur les résultats de Dai Pra, Kozlov, Künsch, Lebowitz, Vasilyev et al., nous précisons, pour la classe des dynamiques PCA réversibles, les relations existant entre les mesures stationnaires, les mesures réversibles et les mesures de Gibbs associées à un potentiel dont le lien avec la dynamique est explicité. Pour une famille paramétrée de dynamiques PCA réversibles, nous démontrons l'existence d'un phénomène de transition de phase et explicitons dans ce cas le comportement de différentes mesures de Gibbs sous l'action de ces dynamiques. En particulier, nous exhibons des mesures de Gibbs non-stationnaires. Dans un second temps, nous étudions l'ergodicité, i.e. la convergence vers l'équilibre des dynamiques PCA qui sont de plus attractives. Nous construisons à cet effet un couplage de ces dynamiques préservant l'ordre stochastique. En nous référant aux travaux de Martinelli et Olivieri pour les dynamiques de Glauber, nous établissons qu'en l'absence de transition de phase, dès que l'unique mesure de Gibbs vérifie une condition de faible mélange, il y a ergodicité et convergence à vitesse exponentielle vers cet unique état d'équilibre, améliorant en cela grandement les critères d'ergodicité pour les PCA existant dans la littérature. Enfin, nous illustrons ces résultats par la réalisation de simulations numériques de certaines des dynamiques réversibles précédemment étudiées, et présentons un algorithme parallèle convergeant vers les mesures de Gibbs extrémales du modèle d'Ising.

Ce travail présente deux approches pour la modélisation des structures de grains et de la ségrégation chimique associée à l'état de fonderie après solidification. La première approche est de développer un modèle basé sur une description semi-analytique des couches de diffusion chimique dans la phase solide et à l'extérieur des enveloppes des grains. L'originalité de ce modèle réside dans la prise en compte de la surfusion de germination des structures dendritique et eutectique. Nous avons appliqué le modèle développé aux gouttes solidifiées par lévitation électromagnétique (EML) et dont la germination de la structure primaire s'est produite spontanément. La technique EML est utilisée comme modèle expérimental pour produire des échantillons sphériques d'alliage aluminium–cuivre (Al-Cu) a différentes compositions nominales de cuivre. Pour chaque échantillon, nous avons étudié le cas d'une germination spontanée et le cas d'une germination déclenchée. Plusieurs degrés de surfusion ont été mesurés avant la germination des structures dendritique et eutectique. Des investigations expérimentales ont été menées pour caractériser une section centrale de chaque échantillon. Un microscope électronique à balayage (MEB), équipé d'un capteur rayon X, a été utilise pour l'analyse dispersive en énergie. Un ensemble complet de données a été généré pour chaque échantillon a travers des cartes de distribution du cuivre, de la structure eutectique et de l'espacement interdendritique secondaire. Le modèle permet une prédiction quantitative de la fraction de structure eutectique en accord avec les mesures effectuées et cela grâce à la prise en compte de la surfusion de germination eutectique. L'accord avec les mesures expérimentales est dû à la prise en compte de l'effet de la surfusion et de la recalescence eutectique. Dans la seconde approche, un modèle numérique 2D couplant Automate Cellulaire (CA) – Eléments Finis (FE) est développé pour la prédiction de la variation de la température et des cartes de ségrégation mesurées pour les échantillons Al-Cu. Un modèle de micro-ségrégation a été intégré dans chaque cellule de l'automate. Ce modèle permet de prendre en compte la surfusion de la germination de la phase primaire ainsi que la diffusion du soluté dans la phase solide. Les longueurs caractéristiques de diffusion ont été exprimé en fonction des espacements interdendritiques primaires et secondaires. Les équations de conservation d'énergie, de masse et de quantité de mouvement sont résolues par la méthode des éléments finis. Un nouveau schéma de couplage entre l'automate cellulaire et les éléments finis a été développé pour permettre l'adaptation du maillage. Un estimateur d'erreur géométrique a été intégré pour le contrôle de la taille et l'orientation des mailles afin d'optimiser la résolution par la méthode des éléments finis. L'application du modèle 2D CAFE a permis une compréhension avancée des résultats expérimentaux. Ce modèle a aussi été appliqué à la solidification d'une cavité rectangulaire d'un alliage étain-plomb. Les capacités du modèle pour l étude des transferts d'énergie et de masse aux échelles micro et macro ont été mise en évidence par le bon accord entre ces perditions et les mesures expérimentales (des cartes de température, de la macro–ségrégation et des structures de grains).

"Dynamics" is very roughly the study of how objects change in time; for instance whether an electrical circuit goes to equilibrium, due to thermal dissipation. By "information", we mean how helpful it is to observe an object in order to know it better, for instance how many binary digits we can acquire on the value of a voltage by an appropriate measure. A "computation" is a physical process, e.g. the flow of current into a complex set of transistors, that after some time eventually gives us the solution of a mathematical problem (such as "Is 13 prime?"). We are interested to various relations between these concepts. In a first chapter, we unify some arguments in the literature to show that a whole class of quantities of dynamical systems are uncomputable. For instance the topological entropy of tilings and Turing machines. Then we propose a precise meaning to the statement "This dynamical system is a computer", at least for symbolic systems, such as cellular automata. We also show, for instance, that a "computer" must be dynamically unstable, and can even be chaotic. In a third chapter, we compare how complicated it is to control a system according whether we can acquire information on it ("feedback") or not ("open loop"). We are specifically interested in finite-state systems. In last chapter we show how to control a scalar linear system when only a finite amount of information can be acquired at every step of time.

Nous étudions le modèle des automates cellulaires en adoptant successivement deux points de vue --celui des représentations syntaxiques locales puis celui des dynamiques globales-- et en cherchant à établir des liens entre eux par différentes approches ou outils --algébrique, combinatoire, et de la théorie de la calculabilité. Au cours de notre étude de la structure des règles de transition locales, nous introduisons une nouvelle classe d'automates (appelés automates cellulaires captifs) définie par une contrainte locale très simple. Nous établissons une loi 0-1 sur cette classe qui a pour corollaire que presque tous les automates cellulaires captifs sont intrinsèquement universels. En revanche, nous montrons qu'il est indécidable de savoir si un automate cellulaire captif est intrinsèquement universel ou pas. Dans une seconde partie, nous poursuivons l'étude des automates cellulaires en cherchant au contraire à nous affranchir le plus possible de leur représentation syntaxique pour insister sur leurs propriétés dynamiques globales. Notre problématique devient celle de la classification et de l'étude de notions de complexité selon ce point de vue global. L'outil fondamental est celui de simulation. Nous étendons les résultats de N. Ollinger sur les structures de pré-ordre (nouvelles relations de simulations et nouvelles propriétés induisant des structures d'idéal ou de filtre) et étudions également l'effet du produit cartésien sur ces structures. Nous établissons une construction qui peut s'interpréter comme un produit cartésien limite et nous permet d'exhiber des chaînes infinies croissantes de longueur omega+omega dans l'un des pré-ordres étudiés. Enfin, nous nous intéressons aux dynamiques séquentielles et aux automates cellulaires universels pour le calcul Turing. Nous construisons un treillis infini d'automates cellulaires Turing-universels qui sont tous à distance infinie de tout automate cellulaire intrinsèquement universel.

Depuis plusieurs dizaines d'années, la modélisation du vivant est un enjeu majeur qui nécessite de plus en plus de travaux dans le domaine de la simulation. En effet, elle ouvre la porte à toute une palette d'applications : l'aide à la décision en environnement et en écologie, l'aide à l'enseignement, l'aide à la décision pour les médecins, l'aide à la recherche de nouveaux traitements pharmaceutiques et la biologie dite " prédictive ", etc. Avant de pouvoir aborder un problème, il est nécessaire de pouvoir modéliser de façon précise le système biologique concerné en précisant bien les questions auxquelles devra répondre le modèle. La manipulation et l'étude de systèmes complexes, les systèmes biologiques en étant l'archétype, pose, de façon générale, des problèmes de modélisation et de simulation. C'est dans ce contexte que la société Integrative BioComputing (IBC) développe depuis le début des années 2000 un prototype d'une Plateforme Générique de Modélisation et de Simulation (la PGMS) dont le but est de fournir un environnement pour modéliser et simuler plus simplement les processus et les fonctions biologiques d'un organisme complet avec les organes le composant. La PGMS étant une plateforme générique encore en phase de développement, elle ne possédait pas les performances nécessaires pour permettre de réaliser la modélisation et la simulation d'éléments importants dans des temps suffisamment courts. Il a donc été décidé, afin d'améliorer drastiquement les performances de la PGMS, de paralléliser et d'optimiser l'implémentation de celle-ci ; le but étant de permettre la modélisation et la simulation d'organes complets dans des temps acceptables. Le travail réalisé au cours de cette thèse a donc consisté à traiter différents aspects de la modélisation et de la simulation de systèmes biologiques afin d'accélérer les traitements de ceux-ci. Le traitement le plus gourmand en termes de temps de calcul lors de l'exécution de la PGMS, le calcul des champs physicochimiques, a ainsi fait l'objet d'une étude de faisabilité de sa parallélisation. Parmi les différentes architectures disponibles pour paralléliser une telle application, notre choix s'est porté sur l'utilisation de GPU (Graphical Processing Unit) à des fins de calculs généralistes aussi couramment appelé GPGPU (General-Purpose computation on Graphics Processing Units). Ce choix a été réalisé du fait, entre autres, du coût réduit du matériel et de sa très grande puissance de calcul brute qui en fait une des architectures de parallélisation les plus accessibles du marché. Les résultats de l'étude de faisabilité étant particulièrement concluant, la parallélisation du calcul des champs a ensuite été intégrée à la PGMS. En parallèle, nous avons également mené des travaux d'optimisations pour améliorer les performances séquentielles de la PGMS. Le résultat de ces travaux est une augmentation de la vitesse d'exécution d'un facteur 18,12x sur les simulations les plus longues (passant de 16 minutes pour la simulation non optimisée utilisant un seul cœur CPU à 53 secondes pour la version optimisée utilisant toujours un seul cœur CPU mais aussi un GPU GTX500). L'autre aspect majeur traité dans ces travaux a été d'améliorer les performances algorithmiques pour la simulation d'automates cellulaires en trois dimensions. En effet, ces derniers permettent aussi bien de simuler des comportements biologiques que d'implémenter des mécanismes de modélisation tels que les interactions multi-échelles. Le travail de recherche s'est essentiellement effectué sur des propositions algorithmiques originales afin d'améliorer les simulations réalisées par IBC sur la PGMS. L'accélération logicielle, à travers l'implémentation de l'algorithme Hash‑Life en trois dimensions, et la parallélisation à l'aide de GPGPU ont été étudiées de façon concomitante et ont abouti à des gains très significatifs en temps de calcul.

Les transmissions radio à longue portée et basse énergie ouvrent de nouveaux champs d'application pour les capteurs, en particulier pour la surveillance de l'environnement. Le protocole radio LoRa permet, par exemple, de connecter des capteurs à une distance pouvant aller jusqu'à dix kilomètres en ligne de visée. Cependant, la grande surface couverte amène plusieurs difficultés, telles que le placement spatial en regard de la topologie géographique, ou la variabilité de la latence des communications. Le positionnement dans I'environnement comporte également des contraintes liées à I'intérêt des points de mesure du phénomène physique. Les critères de conception de ces réseaux tranchent donc avec les méthodes existantes (disques) quand on s'attaque aux terrains complexes. Cette thèse décrit des techniques de simulation basées sur I'analyse géographique cellulaire pour calculer les couvertures radio à longue portée et déduire les caractéristiques radios dans ces situations. Comme la propagation radio n'est qu'un cas particulier de phénomènes physiques, on montre qu'une approche unifiée cellulaire permet de caractériser beaucoup de comportements physiques potentiels. Le cas des fortes pluies et des inondations est étudié. L'analyse de la géographie est réalisée en utilisant des outils de segmentation pour produire des systèmes cellulaires qui sont à leur tour traduits en code pour des calculs de haute performance. La thèse fournit des résultats d'expériences de terrain complexes pratiques en utilisant LoRa, permettant de qualifier l'exactitude de la simulation des couvertures, et les caractéristiques d'ordonnancement des communications. Nous produisons des tables de performance pour les simulations sur les unités de traitement graphique (GPUs) qui montrent que le choix d'une algorithmique parallèle est pertinent sur ces problèmes. / Long-range radio transmissions open new sensor application fields, in particular for environment monitoring. For example, the LoRa radio protocol enables to connect remote sensors at distance as long as ten kilometers in a line-of-sight. However, the large area covered also brings several difficulties, such as the placement of sensing devices in regard to topology in geography, or the variability of communication latency. Sensing the environment also carries constraints related to the inlerest of sensing points in relation with a physical phenomenon. Thus criteria for designs are evolving a lot from the existing methods, especially in complex terrains. This thesis describes simulation techniques based on geography analysis to compute long-range radio coverages and radio characteristics in these situations. As radio propagation is just a particular case of physical phenomena, it is shown how a unified approach also allows to characterize the behavior of potential physical risks. The case of heavy rainfall and flooding is investigated. Geography analysis is achieved using segmentation tools to produce cellular systems which are in turn translated into code for high-þerformance computations. The thesis provides results from practical complex terrain experiments using LoRa which confirm the accuracy of the simulation, and scheduling characteristics for sample networks. Performance tables are produced for these simulations on current Graphics Processing Units (GPUs).

Le sujet abordé dans cette thèse concerne la contrôlabilité d’une classe de systèmes spatio-temporels, entièrement discrets de type automates cellulaires (AC). Le but de cette étude est de mettre en lumière de nouvelles pistes pour prouver la contrôlabilité des systèmes complexes. Plus spécifiquement, cette thèse se focalise sur la contrôlabilité régionale qui consiste à se restreindre à une région du domaine où le système devra atteindre un objectif donné à travers des actions ciblées. Le cas d’AC Booléens a été particulièrement examiné tout au long de cette thèse. La première partie est consacrée à l’étude du problème de la contrôlabilité régionale des AC déterministes lorsque les actions sont exercées sur la frontière de la régioncontrôlée. Une première démarche que nous avons utilisée s’appuie sur les chaines de Markov et la contrôlabilité est caractérisée en établissant une matrice similaire à leur matrice de transition en utilisant les définitions d’une chaîne ergodique et régulière. Cette étude a été étendue au cas des AC probabilistes qui sont largement utilisés pour modéliser de nombreux phénomènes réels. Le même problème a été appréhendé en utilisant des outils de la théorie des graphes. Nous proposons des conditions nécessaires et suffisantes pour la contrôlabilité régionale des AC déterministes en utilisant les notions de circuit hamiltonien et de composante fortement connexe. Le contrôle qui assure la contrôlabilité régionale est défini à travers un algorithme préimages. La deuxième partie est dédiée au problème de la contrôlabilité régionale frontière des AC Booléens qui consiste à agir sur la frontière du domaine pour atteindre un objectif sur une région cible. Nous considérons d’abord des AC linéaires pour lesquels nousdonnons un résultat de caractérisation grâce à la condition de Kalman. Nous proposons un algorithme pour déterminer le contrôle qui permet de forcer l’apparition d’une configuration désirée dans la région d’étude. Le cas des AC non linéaires a été également considéré en utilisant un algorithme de recherche des préimages. / The issue addressed in this thesis concerns the controllability of a class of discrete spatio-temporal systems named cellular automata (CA). The purpose of this study is to highlight new ways to prove the controllability of complex systems. Morespecifically, this thesis focuses on regional controllability which consists in restricting the study to a subregion of the domain where the system will have to achieve a given objective through targeted actions. The case of Boolean CA have been particularly examined throughout this thesis. The first part is devoted to the study of the problem of the regional controllability of deterministic CAs when the actions are exerted on the boundaries of the controlled region. A first approach that we used relies on Markov chains and controllability is characterized by establishing a matrix similar to their transition matrix using the definitions of a regular and ergodic chain. This study has been extended to the case of probabilistic CAs that are widely used tomodel many real phenomena. The same problem has been apprehended using tools of graph theory. We proposenecessary and sufficient conditions for the regional controllability of deterministic CAs using the notions of Hamiltonian circuit and strongly connected component. The control that ensures regional controllability is defined through a preimage algorithm.The second part is devoted to the problem of the boundary regional controllability of Boolean CAs, which consists of acting on the boundary of the domain in order to reach a desired goal in a target region. We first consider linear CAs for which we givea characterization result using the Kalman condition. We propose an algorithm to determine the control that allows to force the appearance of a desired configuration in the study area. The case of nonlinear CAs was also considered using a preimagesearch algorithm.

La prévention du risque volcanique est un enjeu majeur, notamment pour l'Etna, dont les éruptions fréquentes menacent la province de Catane. Sont exposés les éléments physiques nécessaires à la compréhension des mécanismes intervenant dans un écoulement de lave basaltique. Un système d'information intégrant les principaux aspects du risque volcanique et permettant la création de cartes de risques est alors proposé. Ce système comprend un modèle, basé sur les automates cellulaires et intégrant le traitement d’images satellitaires. Il permet de simuler l'évolution d'une coulée ainsi que son débit. Ce système est alors intégré dans un Système d'Information Géographique. Il est validé sur les éruptions 2001, 2006 et 2007. Enfin, nous développons, pour l’enrichir, un modèle numérique pour le refroidissement d'une coulée de lave à l'aide des Smoothed Particle Hydrodynamics. Ce modèle, validé sur différents cas test, est appliqué au refroidissement d'un lac et d’une coulée de lave. Keywords : risque volcanique, automates cellulaires, système de veille, information élaborée, système d'information géographique, Smoothed Particle Hydrodynamics / Preventing volcanic risk is a major challenge, in particular when dealing with Mt Etna whose frequent eruptions regularly threaten Catane province. First, the physical elements necessary to understand the mechanism intervening in basaltic lava flow are exposed. Then, we develop an information system which deals with the main aspects of volcanic risk : lava flow evolution foresight and risk map design. This system is integrated in a geographical information system and is composed of both a model based on cellular automata permitting to simulate the evolution of a lava flow, and an infrared satellite image treatment module permitting to evaluate the lava flux rate. All the models and procedures developed were validated with the 2001, 2006 and 2007 eruptions. Lastly, to enhance the information system, we develop a digital model for lava flow cooling by means of Smoothed Particles Hydrodynamics. This model is validated by different case tests before being applied to the cooling of a lava lake

Un automate cellulaire probabiliste (ACP) est une chaîne de Markov sur un espace symbolique. Le temps est discret, les cellules évoluent de manière synchrone, et le nouvel état de chaque cellule est choisi de manière aléatoire, indépendamment des autres cellules, selon une distribution déterminée par les états d'un nombre fini de cellules situées dans le voisinage. Les ACP sont utilisés en informatique comme modèle de calcul, ainsi qu'en biologie et en physique. Ils interviennent aussi dans différents contextes en probabilités et en combinatoire. Un ACP est ergodique s'il a une unique mesure invariante qui est attractive. Nous prouvons que pour les AC déterministes, l'ergodicité est équivalente à la nilpotence, ce qui fournit une nouvelle preuve de l'indécidabilité de l'ergodicité pour les ACP. Alors que la mesure invariante d'un AC ergodique est triviale, la mesure invariante d'un ACP ergodique peut être très complexe. Nous proposons un algorithme pour échantillonner parfaitement cette mesure. Nous nous intéressons à des familles spécifiques d'ACP, ayant des mesures de Bernoulli ou des mesures markoviennes invariantes, et étudions les propriétés de leurs diagrammes espace-temps. Nous résolvons le problème de classification de la densité sur les grilles de dimension supérieure ou égale à 2 et sur les arbres. Enfin, nous nous intéressons à d'autres types de problèmes. Nous donnons une caractérisation combinatoire des mesures limites pour des marches aléatoires sur des produits libres de groupes. Nous étudions les mesures d'entropie maximale de sous-décalages de type fini sur les réseaux et sur les arbres. Les ACP interviennent à nouveau dans ce dernier travail.

Ce projet de thèse, dans le cadre d’une collaboration entre le LIMOS et le LPC, s’inscrit dans une démarche de recherche permettant la mise en synergie des domaines de la biologie, de la physique et de l’informatique par la proposition d’une démarche de simulation permettant la réalisation d’expériences in silico. Pour cela, nous nous proposons de développer une plateforme logicielle dédiée à la modélisation multiéchelle des systèmes biologiques qui pourra par la suite être interfacée avec les outils de simulation de physique des particules. Nous proposons également un modèle individu-centré de cellule biologique paramétrable à l’aide de données obtenues d’expériences in vitro. Nous présentons l’élaboration de cette plateforme et une démarche de validation de ses fonctionnalités à travers l’implémentation de modèles d’automates cellulaires de la littérature. Nous présentons ensuite la construction du modèle de cellule biologique en prenant le temps d’expliquer comment est pris en compte le système biologique, comment nous le modélisons puis comment nous paramétrons le modèle. Nous modélisons les processus internes de la cellule, dont les caractéristiques sont liées à l’information génétique qu’elle porte. Ce modèle de cellule permet de reproduire le comportement d’une cellule isolée, et à partir de là, d’un ensemble de cellules via l'automate. Le modèle est ensuite utilisé pour retrouver les courbes de croissance d'une population de bactéries Escherichia coli. Des valeurs de données de fluxomique ont été exploitées et ont permis la reproduction in silico des expériences in vitro dont elles étaient issues. / This PhD thesis project is part of a research program in the fields of biology, physics and computer science aiming to propose a simulation approach for performing experiments in silico. For this, we propose to develop a software platform dedicated to multi-scale modeling of biological systems that can be combined with particle physics simulation tools. We also propose a general individual-based model of biological cell in which data obtained from in vitro experiments can be used. We present the development of this platform and the validation process of its functionalities through the implementation of cellular automata from the literature. We then present the design of the biological cell model by giving the hypothesis we made, how we model and how we parameterize the model. Starting from a simple biological system, bacteria, observed in liquid culture, our model uses a multi-scale middle-out approach. We focus on the cell and we model internal processes, assuming that all their properties come from genetic information carried out by the cell’s genome. This model allows to consider the cell behavior, and then to obtain the behavior of a cell population. Data from fluxomic experiments have been used in this model to parameterize the biochemical processes. The results we obtain allow us to consider the model as validated as simulation results match the experimental data.