Nous abordons les automates cellulaires (AC) en cherchant à dégager des informations quantitatives et en particulier à préciser les comportements répandus. Nous étudions en guise de prélude des AC présentant une forte symétrie de la règle locale (AC dits multi-ensemblistes). Les règles locales qui les définissent ont la propriété de pouvoir être utilisées facilement pour différente tailles de voisinage, et nous exhibons des règles, pour chaque dimension, qui sont universelles pour une infinité de tailles. Nous formalisons ensuite la notion de densité d'une propriété parmi l'ensemble des AC. En remarquant que les propriétés répandues sont liées aux propriétés des objets aléatoires au sens de Kolmogorov, et en utilisant divers outils combinatoires nous montrons la négligeabilité (au sens quantitatif) de propriétés non seulement syntaxiques (injectivité, surjectivité, présence d'états persistants ou envahissants), mais aussi dynamiques (nilpotence, certaines contraintes sur l'ensemble limite...). Et nous montrons à l'opposé que l'universalité intrinsèque , propriété qui semble à priori exigeante, est pour de nombreuses sous-familles une propriété très répandue. En ce qui concerne le comportement typique à long terme d'un AC fixé, la mu-nipotence, que nous introduisons à partir de la notion d'ensembles mu-limites, permet de caractériser les AC convergeant presque toujours vers une configuration unique. Nous montrons que celle-ci n'est ni récursivement énumérable ni co-récursivement énumérable. Ceci montre que la difficulté calculatoire de la prédiction du comportement à long terme des AC n'est pas due à des ensembles de configurations négligeables. Nous exhibons aussi des ensembles mu-limites aux langages non récursifs. Enfin nous montrons des résultats d'existence et de non-existence d'AC universels pour la relation de simulation dite surjective parmi certaines sous-familles.

Sont présentés les différents travaux que j'ai pu effectuer: dans le domaine des automates cellulaires et de leur programmation, puis les travaux portant sur les fonctions Booléennes et leur complexité.

Le modèle des automates cellulaires constitue un des modèles le mieux établi de physique discrète sur espace euclidien. Ils implantent trois symétries fondamentales de la physique: la causalité, l'homogénéité et la densité finie de l'information. Bien que l'origine des automates cellulaires provienne de la physique, leur utilisation est très répandue comme modèles de calcul distribué dans l'espace (machines auto-réplicantes, problèmes de synchronisation,...), ou bien comme modèles de systèmes multi-agents (congestion du trafic routier, études démographiques,...). Bien qu'ils soient parmi les modèles de calcul distribué les plus étudiés, la rigidité de leur structure interdit toute extension triviale vers un modèle de topologie variant dans le temps, qui se trouve être un prérequis fondamental à la modélisation de certains phénomènes biologiques, sociaux ou physiques, comme par exemple la discrétisation de la relativité générale. Les dynamiques causales de graphes généralisent les automates cellulaires aux graphes arbitraires de degré borné et pouvant varier dans le temps. Dans cette thèse, nous nous attacherons à généraliser certains des résultats fondamentaux de la théorie des automates cellulaires. En munissant nos graphes d'une métrique compacte, nous présenterons deux approches différentes du modèle. Une première approche axiomatique basée sur les notions de continuité et d'invariance par translation, et une deuxième approche constructive, où une règle locale est appliquée en parallèle et de manière synchrone sur l'ensemble des sommets du graphe. / Cellular Automata constitute one of the most established model of discrete physical transformations that accounts for euclidean space. They implement three fundamental symmetries of physics: causality, homogeneity and finite density of information. Even though their origins lies in physics, they are widely used to model spatially distributed computation (self-replicating machines, synchronization problems,...), as well as a great variety of multi-agents phenomena (traffic jams, demographics,...). While being one of the most studied model of distributed computation, their rigidity forbids any trivial extension toward time-varying topology, which is a fundamental requirement when it comes to modelling phenomena in biology, sociology or physics: for instance when looking for a discrete formulation of general relativity. Causal graph dynamics generalize cellular automata to arbitrary, bounded degree, time-varying graphs. In this work, we generalize the fundamental structure results of cellular automata for this type of transformations. We endow our graphs with a compact metric space structure, and follow two approaches. An axiomatic approach based on the notions of continuity and shift-invariance, and a constructive approach, where a local rule is applied synchronously on every vertex of the graph. Compactness allows us to show the equivalence of these two definitions, extending the famous result of Curtis-Hedlund-Lyndon’s theorem. Another physics-inspired symmetry is then added to the model, namely reversibility.

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. / Heat and mass transfers are two physical phenomena at the base of many thermal systems involved in various fields, such as industries, buildings or renewable energies. The present researches tackle different optimization methodologies of structures subject to heat transfers, coupled with a fluid flow or not, in the topological sense of the term. The partial differential equations describing the physical phenomena are discretized thanks to the finite volume method. The first part of the thesis successively studies three different classes of approaches: constructal theory, cellular automaton, and the solid isotropic material with penalization method. The same academic case, aiming at the optimal cooling of a finite-size volume generating heat, is tackled by means of these three methods, allowing the comparison of the performances of each algorithm. This comparison shows that the method based on the material penalization performs better than the first two approaches, structurally and quantitatively, and also establishes solutions based on a trade-off in the frame multi-objective optimization. Consequently, the second part applies this method to configurations subject to heat and mass transfers with laminar flows. The use of penalization parameters in conjunction with the finite volume method requires a regularization of the viscous dissipation along the solid/fluid interfaces. A bi-objective approach is implemented in order to minimize the total power dissipated by the fluid, while maximizing the thermal energy recovered from the system. The solutions show non-trivial configurations that can be categorized in four different topological classes. The present researches open a new investigation field for fluid flows coupled with the problem of heat transport.

L'objet de cette recherche porte sur une ligne à grande vitesse appelée à desservir la Région Provence-Alpes-Côte d'Azur à l'horizon 2020. La LGV PACA est une infrastructure programmée mais qui n'en est qu'au stade de projet non encore réalisé, c'est pourquoi notre objectif est de proposer des scénarios visant à mesurer les incidences sur l'évolution du territoire transfrontalier franco-italo-monégasque, à partir de la démarche de géoprospective territoriale. Cette approche méthodologique repose ici sur une modélisation spatiale basée sur un modèle d'automate cellulaire contraint du nom de MOLAND. L'application de MOLAND a permis de procéder à une modélisation intégrant transport et usage des sols, ce qui a pour avantage de faciliter la compréhension de l'évolution actuelle et possible du comportement de l'occupation des sols au sein des espaces limitrophes de la frontière. Trois grandes parties sont proposées dans cette thèse. Il est suggéré dans la première partie un cadrage méthodologique portant sur l'interdépendance existante et pouvant exister entre le système territorial et le sous-système des transports. Dans la deuxième partie, nous abordons la problématique de la modélisation et de la simulation spatiale en insistant sur la difficulté du paramétrage des modèles dynamiques et spatialement explicites et notamment sur le paramétrage des modèles basés sur les automates cellulaires contraints. Dans la troisième et dernière partie de cette thèse, c'est la difficulté de l'exercice géoprospectif encore méconnu qui est mise en avant. À partir de différents scénarios géoprospectifs, cette thèse fournit des éléments de connaissance quant à l'avenir possible d'un espace transfrontalier qui s'apprête à accueillir la grande vitesse ferroviaire. Elle apporte des réponses concrètes aux questions liées à la croissance urbaine et à l'accessibilité des territoires jusque-là isolés des grands couloirs européens de communication. Les résultats de cette recherche sont plus que jamais d'actualité car, dans le cadre de l'aide à la connaissance du territoire et de l'aide à la décision, ils permettent de se pencher sur un volet ignoré jusqu'à présent par les études menées par le maître d'ouvrage RFF (Réseau Ferré de France) : la prise en compte simultanée de l'infrastructure de transport et de l'occupation des sols pour l'appréhension et la compréhension des dynamiques d'un territoire en devenir. La prise en compte de l'occupation des sols dans la modélisation géoprospective par automates cellulaires permet au géographe de poser les bonnes questions à partir d'une entrée territoriale. RFF a récemment lancé de nouvelles études sur l'opportunité qu'offre l'infrastructure grande vitesse ferroviaire pour améliorer la desserte de la Région PACA. En permettant de mesurer les impacts nationaux de cette infrastructure sur ce territoire transfrontalier, les simulations réalisées constituent une aide à la décision utile et indispensable.

Ces travaux s'appuient sur le socle formé par les simulations orientées agents (SOA), les simulations par automates cellulaires (AC) et la théorie des fonctions de croyance. Les objectifs sont de proposer des solutions aux problèmes complexes et de développer une architecture de système d'aide à la décision (SAD) organisée autour de ces trois outils. Dans la mesure où ce système fait appel à la théorie des fonctions de croyance (aussi appelée théorie de l'évidence), nous l'avons nommé SEAD, c.-à-d., système évidentiel d'aide à la décision. Le SEAD tente de fournir des explications à une observation effectuée sur un système réel complexe. Il utilise:- les SOA et les AC pour simuler le système complexe d'étude;- les fonctions de croyance pour représenter et manipuler les informations au sein et autour des simulations.L'architecture est validée dans le cadre d'un système d'aide à la décision, nommé ForenSeek, dédié aux experts en entomologie médico-légale. l'entomologie médico-légale est un procédé d'estimation de l'instant de la mort : à partir de la détermination des espèces et âges des insectes prélevés sur un cadavre. Cette technique est confrontée à un ensemble de phénomènes complexes, difficilement perceptibles des experts et ayant des impacts sur leurs décisions finales. Le SEAD forenSeek a recours aux SOA et aux AC pour modéliser la décomposition d'un cadavre. Il intègre un grand nombre de paramètres écosystémiques et teste une quantité importante de modèles biologiques. La théorie des fonctions de croyance est au centre de ce système de fusion. Des premiers résultats à partir de véritables expertises judiciaires sont présentés. / This work is based on the agent simulations (ABS), the cellular automata based simulations (CABS) and the theory of belief functions. The purposes consist in proposing solutions to complex problems and developping a general architecture for decision support system (DSS) organized around these three tools. Because this system resorts to the theory of belief functions (also called the evidence theory), we called it EDSS, i.e., evidential decision support system. The EDSS tries to explain an observation made on a complex real system. It uses:- ABS and CABS to simulate the complex system of study;- the belief function theory to represent and manipulate information within and around the simulations.The architecture is validated through a decision support system, named ForenSeek, dedicated to experts in forensic entomology. Forensic entomology is a method for estimating the time of death from determining the ages and species of insects collected on a cadaver. This technique faces with a set of complex phenomena, not easily discernible by the experts and having an impact on their final decisions. The EDSS ForenSeek uses the ABS and CABS to simulate the corpse decomposition. It incorporates a large number of ecosystem parameters and tests a large quantity of biological models. The theory of belief functions is central to this information fusion system. First results from real forensic expert's reports are presented.

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 / We investigate properties of one-dimensional cellular automata. This category of cellular automata has been widely studied but many questions are still open. Among them the spectral theory of unidimensional cellular automata is an open field with few indirect results. We want a better understanding of both ergodic and topological aspect by investigating the existence of eigenvalues of cellular automata, in particular irrational ones, i.e., those of the form e^{2Iπα} where α is irrationnal and I the complex root of -1. The last question seems not to have been studied yet.In the topological field the results of Kůrka & Blanchard and Tisseur about equicontinuous cellular automata have as direct consequence that any equicontinuous CA has rational eigenvalues. Density of shift periodic points leads to the impossibility for CA to have topological irrational eigenvalues. The density of periodic points of cellular automata seems to be related with the question of eignevalues. If the CA has equicontinuity points without being equicontinuous, the density of periodic points implies the fact that the spectrum contains all rational roots of the unity, i.e., all numbers of the form e^{2Iπα} with α∈Q .In the measurable field the question becomes harder. We assume that the cellular automaton is surjective, which implies that the uniform measure is invariant. Most results are still available in more general conditions. We first prove that cellular automata with equicontinuity points never have irrational measurable eigenvalues. This result is then generalized to cellular automata with μ-equicontinuous points according to Gilman's classification. We also prove that cellular automata with μ-equicontinuous points have rational eigenvalues

Durant cette thèse, nous abordons le problème de la fouille exhaustive de motifs pour un cas particulier de graphes : les grilles. Ces grilles peuvent être utilisées pour modéliser des objets ayant une structure régulière. Ces structures sont naturellement présentes dans de nombreux jeux de plateaux (les dames, les échecs ou le go par exemple) ou encore dans les modélisations d’écosystèmes utilisant des automates cellulaires. On les retrouve également à un plus bas niveau dans les images, qui sont des grilles 2D de pixels ou encore les vidéos, qui sont des grilles spatio-temporelles 2D+t de pixels. Au cours de cette thèse, nous avons proposé un nouvel algorithme de fouille de motifs fréquents dédié aux grilles spatio-temporelles, GriMA. L’usage des grilles régulières permet à notre algorithme de réduire la complexité des tests d’isomorphismes. Ces tests sont souvent utilisés par les algorithmes génériques de fouilles de graphes mais ayant une complexité importante, cela limite leur usage sur des données réelles. Deux applications ont été proposées pour évaluer notre algorithme : la classification d’images pour la fouille de grilles 2D et la prédiction d’automates cellulaires pour la fouille de grilles 2D+t. / During this thesis, we consider the exhaustive graph mining problem for a special kind of graphs : the grids. Theses grids can be used to model objects that present a regular structure. These structures are naturally present in multiple board games (checkers, chess or go for instance) or in ecosystems models using cellular automata. It is also possible to find this structure in a lower level in images, which are 2D grids of pixels, or even in videos, which are 2D+t spatio-temporal grids of pixels. In this thesis, we proposed a new algorithm to find frequent patterns dedicated to spatio-temporal grids, GriMA. Use of regular grids allow our algorithm to reduce the complexity of the isomorphisms test. These tests are often use by generic graph mining algorithm but because of their complexity, they are rarely used on real data. Two applications were proposed to evaluate our algorithm: image classification for 2D grids mining and prediction of cellular automata for 2D+t grids mining.

Dans cette thèse, nous étudions la robustesse dans le contexte de la modélisation de systèmes complexes par les automates cellulaires. En effet, si l'on cherche à reproduire un comportement émergent à partir d'un modèle d'automate cellulaire, il nous semble nécessaire de se demander si les comportements observés sont bien le résultat d'interactions entre entités constituantes, ou bien s'ils dépendent d'une définition particulière du modèle. Nous allons ainsi être amenés à considérer la robustesse du modèle, à savoir la résistance de son comportement à de petites variations sur les attributs de sa définition. Dans un premier temps, nous montrons la pertinence de cette approche en considérant plusieurs définitions possibles d'une perturbation de la mise à jour globale et en les appliquant à une classe simple et représentative de modèles d'automates cellulaires, les Automates Cellulaires Elémentaires. Nous observons que, malgré le fait que nos perturbations soient proches et qu'une majorité des modèles considérés ne change pas de comportement, quelques cas particuliers montrent des changements qualitatifs du comportement que nous étudions plus en détail. Dans un second temps, nous appliquons cette approche en nous penchant sur un modèle particulier d'automate cellulaire, qui simule le phénomène de formation d'essaim à partir d'un modèle évolué d'automate cellulaire, le gaz sur réseau. Nous explorons la robustesse du comportement du modèle en considérant la perturbation de deux attributs du modèle, la forme de la grille cellulaire et la mise à jour globale, et en tirons les conclusions sur la relation entre l'observation du comportement et la définition précise du modèle / In this thesis, we study the role of robustness in the context of the modelling of complex systems by cellular automata. Indeed, if we consider a cellular automaton which aims at reproducing an emergent behaviour from a similar structure, we want to determine whether its observed dynamics are the result of the interaction of entities, or whether it depends a precise definition of the model. We thus consider the model's robustness, that is, the resistance of the behaviour to small perturbations on the model features. First, we show the relevance of this approach by considering several definitions of a perturbation of the global updating and by applying them to a simple and representative class of cellular automata, the Elementary Cellular Automata. We observe that, despite the fact that most models show little or no change between the different perturbations, some particular cases show qualitative changes that we study in detail. Second, we apply this approach to a particular model of cellular automata, which simulates a swarming behaviour based on a lattice-gas model. We then explore the model robustness by considering the pertubations of two of the model's attributes, the lattice shape and the global updating, and discuss the relationship between the observation of the behaviour and the precise definitions of the model

Dans cette thèse nous étudions différents systèmes dynamiques discrets permettant de simuler la formation des piles de sable. Le comportement des modèles de base SPM ou IPM(k) est bien connu dans des conditions initiales spécifiques. Nous étendons ces résultats à des conditions initiales plus générales, et nous introduisons le modèle SSPM qui ajoute de la symétrie à ces modèles et améliore leur réalisme. Dans un second temps, nous étudions un autre système dynamique, les automates de sable. Ils sont définis de manière analogue aux automates cellulaires, avec la contrainte supplémentaire qu'uneconfiguration n'admet pas de « trous ». Ces automates peuvent simuler tous les modèles de piles de sable définis localement, et à l'aide d'un cadre mathématique solide, ils permettent d'obtenir des résultats plus généraux. Nous nous intéressons à la dynamique des automates de sable, plus précisément aux propriétés de réversibilité d'un automate, et nous étudions la décidabilité de propriétés caractérisant les piles de sable classiques : conservation des grains et périodicité ultime.