Thèse doct. : mathématiques et informatique fondamentale : Lyon, Ecole normale supérieure (sciences) : 2002. / Bibliogr.p.117-122.Index.

Thèse de doctorat : Chimie : Evry-Val d'Essonne : 2008. / Titre provenant de l'écran-titre.

Thèse de doctorat : Informatique : Nice : 2006. / Bibliogr. p. 87-89. Index. Résumés en français et en anglais.

Les automates cellulaires sont un modèle de calcul massivement parallèle introduit dans les années 50. De nombreuses variantes peuvent être considérées par exemple en faisant varier la dimension de l’espace de calcul, ou les possibilités de communication entre les différentes cellules. En effet, chaque cellule ne peut communiquer qu’avec un nombre fini d’autres cellules que l’on appelle son voisinage. Mes travaux s’intéressent principalement à l’impact du choix du voisinage sur les capacités algorithmiques de ce modèle. Cet impact étant bien compris en une dimension, mes travaux portent majoritairement sur les automates cellulaires bidimensionnels. J’ai tout d’abord essayé de généraliser des propriétés classiques de certaines classes de complexité au plus de voisinages possibles. On arrive notamment à un théorème d’accélération linéaire valable pour tous les voisinages. J’ai ensuite étudié les différences entre les classes de faibles complexités en fonction du voisinage choisi. Ces travaux ont permis d’exhiber des voisinages définissant des classes incomparables, ainsi que des ensembles de voisinages définissant exactement les mêmes classes de complexité. Enfin, je présente aussi des travaux sur les différences de puissance de calcul entre les automates de dimensions différentes. / Cellular automata were introduced in the 50s by J. von Neumann and S. Ulamas an efficient way of modeling massively parallel computation. Many variations of the model can be considered such as varying the dimension of the computation space or the communication capabilities of the computing cells. In a cellular automaton each cell can communicate only with a finite number of other cells called its neighbors. My work focuses on the impact of the choice of the neighbors on the algorithmic properties of the model. My first goal was to generalize some classical properties of computation models to the widest possible class of neighborhoods, in particular I prove a linear speedup theorem for any two dimensional neighborhood. I then study the difference between the complexity classes defined by different neighborhoods, show the existence of neighborhoods defining incomparable classes, and some sets of neighborhoods defining identical classes. Finally, I also discuss the impact of the dimension of the automata on their computational power.

Cette thèse s'articule autour du problème de la synchronisation d'une ligne d'automates. Elle propose une solution économe en nombre d'états en utilisant le schéma de Minsky: temps de synchronisation 3n et nombre d'états 7. Elle s'attache aussi à décrire le comportement de certains automates particuliers découverts lors de la quête automatisée de solutions minimales.

Les systèmes d’information géographique (SIG) sont largement utilisés pour représenter, gérer et analyser les données spatiales dans plusieurs disciplines incluant les géosciences, l’agriculture, la foresterie, la météorologie et l’océanographie. Néanmoins, malgré l’avancement récent des technologies des SIG, ils sont encore limités dans la représentation et la simulation des processus spatiotemporels. Ce travail de recherche définit le cadre théorique, conceptuel et applicatif qui vise à améliorer les méthodes de compréhension, de représentation et de simulation des processus dynamiques continus. Il vise plus précisément à améliorer les structures de données dans les SIG en développant une structure de données hiérarchique qui est la base d’un automate cellulaire capable de répondre aux principales caractéristiques de ces processus. L’exploration du potentiel des automates cellulaires pour simuler et représenter les processus dynamiques continus dans les SIG en respectant leur caractère irrégulier et hiérarchique fait l’objet de ce travail de recherche dans lequel une application dans le contexte hydrologique est mise en place. Nos objectifs spécifiques se résument dans 1) la construction d’une tessellation irrégulière et hiérarchique permettant de représenter les processus spatiotemporels et 2) la simulation de ces processus en utilisant un automate cellulaire opérant sur cette tessellation. Nous étudions la discrétisation de l’espace en tessellation irrégulière basée sur le diagramme de Voronoï et nous proposons une procédure de hiérarchisation de cette tessellation dans un objectif de représentation multi-échelle afin d’offrir une solution d’aide à la décision dans la gestion du territoire. Nous expliquons notre méthodologie et les algorithmes de sélection de données pour la génération de différents niveaux d’échelles spatiales. Un automate cellulaire non traditionnel est mis en place pour lequel nous définissons une grille à géométrie irrégulière de type Voronoï, des règles de transition spécifiques et un type particulier de voisinage orienté. Nous validons le fonctionnement de ce prototype dans le Bassin Expérimental de la Forêt Montmorency à Québec où des comparaisons sont possibles grâce à des données de débits d’eau mesurées in situ. / Geographic information systems (GIS) are widely used to represent, manage and analyse spatial data in many disciplines including geosciences, agriculture, forestry, meteorology and oceanography. However, despite recent advances in GIS technologies, they are still limited when it comes to representation and simulation of spatiotemporal processes. This research work, deals with a theoretical, conceptual and practical framework which aims to improve the representation of dynamic continuous processes. It aims especially to improve GIS capabilities by developing a CA based on a hierarchical irregular tessellation which is able to take into account the main characteristics of these processes. The exploration of the cellular automata potential to simulate and represent dynamic continuous processes regarding their irregular and hierarchic characteristics is the subject of this work where an application in the hydrologic field is established. Our specific objectives are 1) to build an irregular and hierarchic grid that can be used to represent spatiotemporal processes, 2) to simulate those processes with a cellular automata operating on this grid. We give details about the irregular geometric grid based on a Voronoï Diagram, the characteristics of a specific oriented neighbourhood and the transition rules that are governing the cells update. In addition, we discuss the hierarchical perspective of the build lattice that is essential for easy move between different spatial scales. We explain our methodology of data selection in order to generate the spatial levels of representation by demonstrating the used selection algorithms. This facilitates the representation of spatial dynamic phenomena and contributes to the better understanding of the complex behaviour of the whole system at different levels of details. We also present the data structures and general functioning of the whole simulation system. We finally, validate our framework by simulating the water flow process in a specific watershed in the region of Montmorency Forest of Quebec where in situ data are available. To validate our simulation results we compare them with measured data.

Dans un espace discret, comme l'ensemble des points à coordonnées entières, la modélisation de l'isotropie pose des difficultés théoriques notables. À ce jour, aucune théorie géométrique sur $\ZZ^n$ n'est apte à rendre compte de l'isotropie telle qu'elle est décrite par la géométrie euclidienne. Dans l'optique de contribuer à cette problématique, nous nous intéressons à la conception d'algorithmes capables de donner aux rotations discrètes des propriétés proches de celles de la rotation euclidienne. Ces algorithmes doivent de plus fonctionner à base d'arithmétique entière. Après avoir montré la non-existence de rotation discrète transitive sur $\ZZ^n$, nous introduisons un codage de rotations discrètes que nous relions à la fois à la dynamique symbolique et aux automates cellulaires. Il s'agit alors de mener une étude locale des rotations discrètes. Cette étude se situe au carrefour entre géométrie discrète et systèmes dynamiques symboliques. La pertinence des configurations obtenues est justifiée par l'existence de transducteurs planaires capables d'effectuer des rotations à partir des configurations. Ensuite, afin de réinterpréter ces configurations dans le cadre de la théorie des systèmes dynamiques, nous étendons des notions classiques de cette théorie à la dimension 2. Pour la rotation discrétisée, la dynamique symbolique associée est conjuguée avec un jeu de deux translations orthogonales sur un tore bidimensionnel. Après analyse, nous constatons que les configurations obtenues sont des superpositions de configurations de faible complexité. Cela évoque alors les généralisations planaires des mots sturmiens étudiées entre autres par Valérie Berthé et Laurent Vuillon. Des résultats analogues sont aussi obtenus pour les rotations $3$-transvections. L'analyse les rotations discrètes par le biais de systèmes dynamiques a permis de nombreux résultats : mise en évidence de la quasipériodicité des configurations, calcul de la fréquence des symboles, caractérisation des rotations discrétisées bijectives, ce qui est aussi la réciproque du théorème d'Éric Andrès et Marie-Andrée Jacob. Nous avons aussi étudié les discontinuités du processus de rotation. Ces discontinuités ont lieu pour des angles issus d'un sous-ensemble des angles quadratiques (i.e. les angles charnières). En combinant ces remarques, nous aboutissons à deux algorithmes. Le premier algorithme réalise des rotations sans faire aucun calcul à virgule flottante et sans calculer aucun sinus ni aucun cosinus. Il fonctionne de manière incrémentale et en ordre de complexité optimal. Le second algorithme est une implémentation de la rotation $3$-transvections sur automates cellulaires. D'autres pistes pour la conception d'algorithmes sont mentionnées dans la thèse. En outre, nous nous intéressons aussi aux méthodes substitutives qui engendrent les configurations de rotations. Pour les angles quadratiques, nous montrons que les configurations de rotations sont des entrelacements de configurations autosimilaires; et nous présentons le schéma d'une approche basée sur les graphes de Rauzy pour l'inférence de substitutions planaires. En combinant ces deux approches, nous mettons en avant les éléments essentiels de la démonstration de l'autosimilarité de $C_{\pi/4}$. Les applications potentielles de cette thèse concernent à terme l'implémentation d'algorithmes de rotations pour processeurs graphiques. Elle contribue aussi à l'étude des méthodes algorithmiques pour la modélisation physique en milieu discret de phénomènes isotropes.

Ce mémoire est composé de deux grandes parties. Dans la première, nous simulons le fonctionnement d'automates cellulaires par différents modèles de calcul parallèle comme les PRAM, les XPRAM et les machines spatiales. Nous obtenons ainsi différentes preuves de l'universalité de ces modèles. Nous tirons quelques conséquences de ces résultats du point de vue de la calculabilité et de la complexité. Dans la seconde partie, nous considérons les automates cellulaires définis sur des graphes de Cayley finis. Nous rappelons la simulation de Róka qui permet de mimer le fonctionnement d'un tore hexagonal d'automates par un tore d'automates de dimension deux. Nous décrivons ensuite différentes manières de plonger un tore d'automates de dimension deux dans un anneau d'automates. Nous déduisons de ces résultats la simulation de tores de dimension finie par un anneau d'automates et celle d'un tore hexagonal d'automates par un anneau d'automates.

Cette thèse a pour objet l'étude des systèmes de particules et collisions dans les automates cellulaires. En se basant sur des observations expérimentales, nous proposons des définitions formelles de ces objets et montrons qu'ils peuvent être mis en relation avec des coloriages réguliers du plan. À l'aide d'une représentation sous forme syntaxique de ces objets, nous introduisons une opération syntaxique d'assemblage: les schémas de ligature. Cette opération peut être interprétée en termes de coloriage et correspond à une opération intuitive utilisée dans l'étude algorithmique des automates cellulaires. Nous prouvons que, dans le cas d'assemblages finis, le lien entre l'opération syntaxique et l'interprétation peut être complètement caractérisé de façon algorithmique. Nous explorons ensuite des pistes d'extension de ces systèmes facilitant l'encodage et permettant de dépasser le cas fini. Enfin, nous étudions les applications de tels systèmes en lien avec l'universalité dans les automates cellulaires. En particulier, nous donnons une nouvelle preuve de l'universalité de l'automate cellulaire 110 et présentons la construction d'un automate cellulaire intrinsèquement universel de rayon 1 et à 4 états.

Nous mettons en évidence un certain nombre de liens entre la théorie des nombres et celle des automates :<br>- étude de sous-suites de la suite "somme des chiffres", étude des itérées de cette suite ;<br>- utilisation de suites automatiques particulières (baptisées q-miroirs) dans le problème de l'itération des fonctions continues unimodales réelles ;<br>- étude d'un curieux ensemble de répartition modulo 1 de nombres réels ; <br>- propriétés arithmétiques d'un automate cellulaire ;<br>- répartition modulo 1 des puissances de séries formelles à coefficients automatiques (donc algébrique sur le corps des fractions rationnelles sur un corps fini).