Le sujet global de cette thèse est l'étude d'automates cellulaires probabilistes. Elle est divisée en deux grandes parties.<br /><br />Au cours de la première, nous définissons la notion de chaîne partiellement ordonnée qui généralise celle d'automate cellulaire probabiliste. Cette définition se fait par l'intermédiaire de spécification partiellement ordonnée de la même façon que les mesures de Gibbs sont définies à l'aide de spécifications. Nous obtenons des résultats analogues sur l'espace des phases : caractérisation des mesures extrêmes, construction/reconstruction en partant des noyaux sur un seul site, critères d'unicité. Les résultats sont appliqués tout au long du texte à des automates déjà connus.<br /><br />La deuxième partie est essentiellement vouée à l'étude d'automates cellulaires unidimensionnels à deux voisins et deux états. Nous donnons deux décompositions des configurations spatio-temporelles en flot d'information. Ces flots ont une signification géométrique. De cela nous tirons deux critères d'unicité.<br /><br />En annexe, nous donnons une démonstration de transition de phase d'un automate cellulaire défini par A. Toom, le modèle NEC. Tout au long du texte, des simulations sont présentées.

On s'intéresse à l'analyse et la simulation du comportement itératif de réseaux d'automates et plus particulièrement des réseaux d'automates à seuil (avec éventuellement introduction d'une période de réfraction). On donne, on approfondit des résultats concernant la longueur du cycle limite, le nombre de pas nécessaires pour l'atteindre, ainsi que l'organisation spatiale des cellules dans le cycle.

Ce mémoire de thèse est consacré à l'étude de quelques problèmes de probabilités provenant de l'informatique théorique. Dans une première partie, nous étudions un algorithme probabiliste qui compte le nombre de mots différents dans une liste. Nous montrons que l'étude peut se ramener à un problème d'estimation, et qu'en modifiant légèrement cet algorithme, il est d'une certaine manière optimal. La deuxième partie est consacrée à l'étude de plusieurs problèmes de convergences pour des systèmes finis de particules, nous envisageons différents types de passage à une limite infinie. La première famille de systèmes considérés est une classe particulière d'automates cellulaires. En dimension 1, il apparaît des marches aléatoires dont nous caractérisons de façon complète les comportements limites. En dimension 2, sur une grille carrée, nous étudions quelques-un des cas les plus représentatifs. Nous en déterminons le temps moyen de convergence vers une configuration fixe. Enfin, nous étudions un modèle d'urnes avec des boules à deux états. Dans la troisième partie, nous étudions deux problèmes particuliers de marches aléatoires. Ces deux questions sont initialement motivées par l'étude de certains automates cellulaires, mais nous les présentons de façon indépendante. Le premier de ces deux problèmes est l'étude de marches aléatoires sur un tore discret, réfléchies les unes sur les autres. On montre la convergence de ce processus vers une limite brownienne. Nous étudions enfin de façon entièrement combinatoire une famille de marches aléatoires sur un intervalle, biaisées vers le bas. Nous en déterminons le temps moyen de sortie vers le haut.

Ce mémoire se place dans l'étude des modèles du calcul continus. Nous y montrons que la géométrie plane permet de calculer. Nous définissons un calcul géométrique et utilisons la continuité de l'espace et du temps pour stocker de l'information au point de provoquer des accumulations. Dans le monde des automates cellulaires, on parle souvent de particules ou de signaux (qui forment des lignes discrètes sur les diagrammes espace-temps) tant, pour analyser une dynamique que, pour concevoir des automates cellulaires particuliers. Le point de départ de nos travaux est d'envisager des versions continues de ces signaux. Nous définissons un modèle de calcul continu, les machines à signaux, qui engendre des figures géométriques suivant des règles strictes. Ce modèle peut se comprendre comme une extension continue des automates cellulaires. Le mémoire commence par une présentation des automates cellulaires et des particules. Nous faisons ensuite une classification des différents modèles de calcul existants et mettons en valeur leurs aspects discrets et continus. À notre connaissance, notre modèle est le seul à temps et espace continus mais à valeurs et mises à jour discrètes. Dans la première partie du mémoire, nous présentons ce modèle, les machines à signaux, et montrons comment y mener tout calcul au sens de Turing (par la simulation de tout automate à deux compteurs). Nous montrons comment modifier une machine de manière à réaliser des transformations géométriques (translations, homothéties) sur les diagrammes engendrés. Nous construisons également les itérations automatiques de ces constructions de manière à contracter le calcul à une bande (espace borné) puis, à un triangle (temps également borné). Dans la seconde partie du mémoire, nous cherchons à caractériser les points d'accumulation. Nous reformulons de manière topologique les diagrammes espace-temps: pour chaque position, la valeur doit correspondre au voisinage sur un ouvert suffisamment petit. Muni de cet outil, nous regardons les plus simples accumulations possibles (les singularités isolées) et proposons un critère pour y prolonger le calcul; mais le déterminisme peut être perdu dans le cône d'influence. Enfin, en construisant pour tout automate à deux compteurs une machine à signaux et une configuration initiale simulant l'automate pour toutes les valeurs possibles, nous montrons que le problème de la prévision de l'apparition d'une accumulation est Σ20-complet. Le mémoire se conclut par la présentation de nombreuses perspectives de recherches.

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

Les transferts de chaleur et de masse sont deux phénomènes physiques à la base de nombreux systèmes thermiques employés dans des secteurs variés tels que l'industrie, le bâtiment ou encore les énergies renouvelables. Les présents travaux de recherche envisagent différentes méthodologies d'optimisation de configurations assurant le transfert de flux de chaleur, couplé ou non à un écoulement fluide, au sens topologique du terme. Les équations aux dérivées partielles décrivant les phénomènes physiques sont discrétisées avec la méthode des volumes finis. La première partie du manuscrit examine successivement trois classes différentes de méthodes: la théorie constructale, les automates cellulaires et les méthodes par pénalisation. Le même cas académique, portant sur le refroidissement d'un volume fini générant de la chaleur, est résolu au moyen de ces trois méthodes, ce qui permet ainsi de comparer les performances de chaque algorithme. Cette comparaison démontre l'ascendant des méthodes par pénalisation sur les deux premiers types, tant structurellement que quantitativement, et permet également d'établir des solutions basées sur des compromis dans le cadre d'optimisations multi-objectifs. Par conséquent, la seconde partie envisage l'application de cette approche à des configurations réalisant des transferts de chaleur conducto-convectifs en régime laminaire. L'utilisation de paramètres de pénalisation en conjonction avec les volumes finis requiert une régularisation de la dissipation visqueuse le long de l'interface fluide/solide. Une approche bi-objectif est développée visant à minimiser la puissance dissipée par le fluide, tout en maximisant l'énergie thermique récupérée sur le système. Les solutions obtenues adoptent des configurations non-triviales qui sont divisibles en quatre classes topologiques différentes. La thèse ouvre ainsi un nouveau champ d'investigation pour l'optimisation d'écoulements couplés à la problématique du transport de chaleur.

Les transferts de chaleur et de masse sont deux phénomènes physiques à la base de nombreux systèmes thermiques employés dans des secteurs variés tels que l'industrie, le bâtiment ou encore les énergies renouvelables. Les présents travaux de recherche envisagent différentes méthodologies d'optimisation de configurations assurant le transfert de flux de chaleur, couplé ou non à un écoulement fluide, au sens topologique du terme. Les équations aux dérivées partielles décrivant les phénomènes physiques sont discrétisées avec la méthode des volumes finis. La première partie du manuscrit examine successivement trois classes différentes de méthodes: la théorie constructale, les automates cellulaires et les méthodes par pénalisation. Le même cas académique, portant sur le refroidissement d'un volume fini générant de la chaleur, est résolu au moyen de ces trois méthodes, ce qui permet ainsi de comparer les performances de chaque algorithme. Cette comparaison démontre l'ascendant des méthodes par pénalisation sur les deux premiers types, tant structurellement que quantitativement, et permet également d'établir des solutions basées sur des compromis dans le cadre d'optimisations multi-objectifs. Par conséquent, la seconde partie envisage l'application de cette approche à des configurations réalisant des transferts de chaleur conducto-convectifs en régime laminaire. L'utilisation de paramètres de pénalisation en conjonction avec les volumes finis requiert une régularisation de la dissipation visqueuse le long de l'interface fluide/solide. Une approche bi-objectif est développée visant à minimiser la puissance dissipée par le fluide, tout en maximisant l'énergie thermique récupérée sur le système. Les solutions obtenues adoptent des configurations non-triviales qui sont divisibles en quatre classes topologiques différentes. La thèse ouvre ainsi un nouveau champ d'investigation pour l'optimisation d'écoulements couplés à la problématique du transport de chaleur.

On s'intéresse dans ce travail aux automates cellulaires unidimensionnels qui ont été largement étudiés mais où il reste beaucoup à faire. La théorie spectrale des automates cellulaires a notamment été peu abordée à l'exception de quelques résultats indirects. On cherche a mieux comprendre les cadres topologiques et ergodiques en étudiant l'existence de valeurs propres en particulier celles irrationnelles c'est à dire de la forme e^{2Iπα} où α est un irrationnel et I la racine carrée de l'unité. Cette question ne semble pas avoir été abordée jusqu'à présent. Dans le cadre topologique les résultats sur l'équicontinuité de Kůrka et Blanchard et Tisseur permettent de déduire directement que tout automate cellulaire équicontinu possède des valeurs propres topologiques rationnelles. La densité des points périodiques pour le décalage empêche l'existence de valeurs propres topologiques irrationnelles. La densité des points périodiques pour l'automate cellulaire semble être liée à la question des valeurs propres. Dans le cadre topologique, si l'automate cellulaire possède des points d'équicontinuité sans être équicontinu, la densité des points périodiques a comme conséquence le fait que le spectre représente l'ensemble des racines rationnelles de l'unité c'est à dire tous les nombres de la forme e^{2Iπα} avec α∈Q .Dans le cadre mesuré, la question devient plus difficile, on s'intéresse à la dynamique des automates cellulaires surjectifs pour lesquels la mesure uniforme est invariante en vertu du théorème de Hedlund. La plupart des résultats obtenus demeurent valable dans un cadre plus large. Nous commençons par montrer que les automates cellulaires ayant des points d'équicontinuité ne possèdent pas de valeurs propres mesurables irrationnelles. Ce résultat se généralise aux automates cellulaires possédant des points μ-équicontinu selon la définition de Gilman. Nous démontrons finalement que les automates cellulaires possédant des points μ-équicontinu selon la définition de Gilman possèdent des valeurs propres rationnelles

Reproduction de : Thèse doctorat : Informatique : Reims : 2008. / Titre provenant de l'écran titre. Bibliogr. p. 301-320.

The intended goal of this manuscript is to build bridges between two definitions of complexity. One of them, called the algorithmic complexity is well-known to any computer scientist as the difficulty of performing some task such as sorting or optimizing the outcome of some system. The other one, etymologically closer from the word "complexity" is about what happens when many parts of a system are interacting together. Just as cells in a living body, producers and consumers in some non-planned economies or mathematicians exchanging ideas to prove theorems. On the algorithmic side, the main objects that we are going to use are two models of computations, one called communication protocols, and the other one circuits. Communication protocols are found everywhere in our world, they are the basic stone of almost any human collaboration and achievement. The definition we are going to use of communication reflects exactly this idea of collaboration. Our other model, circuits, are basically combinations of logical gates put together with electrical wires carrying binary values, They are ubiquitous in our everyday life, they are how computers compute, how cell phones make calls, yet the most basic questions about them remain widely open, how to build the most efficient circuits computing a given function, How to prove that some function does not have a circuit of a given size, For all but the most basic computations, the question of whether they can be computed by a very small circuit is still open. On the other hand, our main object of study, cellular automata, is a prototype of our second definition of complexity. What "does" a cellular automaton is exactly this definition, making simple agents evolve with interaction with a small neighborhood. The theory of cellular automata is related to other fields of mathematics, such as dynamical systems, symbolic dynamics, and topology. Several uses of cellular automata have been suggested, ranging from the simple application of them as a model of other biological or physical phenomena, to the more general study in the theory of computation.