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. / For some years, living matter modeling has been a major challenge which needs more and more research in the simulation field. Indeed, the use of models of living matter have multiple applications: decision making aid in environment or ecology, teaching tools, decision making aid for physician, research aid for new pharmaceutical treatment and “predictive” biology, etc. But before being able to tackle all these issues, the development of a correct model, able to give answer about specific questions, is needed. Working with complex systems –biologic system being the archetype of them– raises various modeling and simulation issues. It is in this context that the Integrative BioComputing (IBC) company have been elaborating, since the early 2000s, the prototype of a generic platform for modeling and simulation (PGMS). Its goal is to provide a platform used to easily model and simulate biological process of a full organism, including its organs. Since the PGMS was still in its development stage at the start of my PhD, the application performance prevented the modeling and simulation of large biological components in an acceptable time. Therefore, it has been decide to optimize and parallelize its computation to increase significantly the PGMS performances. The goal was to enable the use of the PGMS to model and simulate full organs in acceptable times. During my PhD, I had to work on various aspects of the modeling and simulation of biological systems to increase their process speed. Since the most costly process during the PGMS execution was the computation of chemical fields, I had to study the opportunity of parallelizing this process. Among the various hardware architectures available to parallelize this application, we chose to use graphical processing units for general purpose computation (GPGPUs). This choice was motivated, beside other reasons, by the low cost of the hardware compared to its massive computation power, making it one of the most affordable parallel architecture on the market. Since the results of the initial feasibility study were conclusive, the parallelization of the fields computation has been integrated into the PGMS. In parallel to this work, I also worked on optimizing the sequential performance of the application. All these works lead to an increase of the software performances achieving a speed-up of 18.12x for the longest simulation (from 16 minutes for the non-optimized version with one CPU core to 53 seconds for the optimized version, still using only one core on the CPU but also a GPU GTX500). The other major aspect of my work was to increase the algorithmic performances for the simulation of three-dimensional cellular automata. In fact, these automata allow the simulation of biological behavior as they can be used to implement various mechanisms of a model such as multi-scale interactions. The research work consisted mainly in proposing original algorithms to improve the simulation provided by IBC on the PGMS. The sequential speed increase, thanks to the three-dimensional Hash Life implementation, and the parallelization on GPGPU has been studied together and achieved major computation time improvement.

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. / 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.

Les modèles numériques sont un outil complémentaire pour la prédiction de la corrosion. L'objectif de cette thèse est de développer un modèle de corrosion reposant sur la méthode des automates cellulaires pour l'étude de l'évolution morphologique des surfaces, ainsi que de la cinétique de corrosion. Le modèle développé couple les demi-réactions électrochimiques d'oxydation et de réduction. Au niveau cinétique, la simulation par automates cellulaires peut alors reproduire les courbes intensité-potentiel d'une réaction redox sur électrode inerte. L'échelle spatio-temporelle choisie décrit des phénomènes de corrosion à l'échelle mésoscopique, niveau intermédiaire par rapport aux approches habituelles. Dans notre modèle, les probabilités rendent compte de la nature stochastique des réactions anodiques et cathodiques. Cette étude nous a permis de décrire l'évolution de la morphologie de la corrosion dans différents contextes: corrosion généralisée, corrosion par piqûre et corrosion en milieu confiné. Deux régimes de corrosion ont été observés: un régime de corrosion uniforme dans lequel les demi-réactions sont distribuées de manière homogène suivi par un régime de corrosion localisée, caractérisé par une séparation spatiale des zones cathodiques et anodiques. / Numerical modelling is complementary tool for corrosion prediction. The objective of this work is to develop a corrosion model by means of a probabilistic cellular automata approach at a mesoscopic scale. In this work, we study the morphological evolution and kinetics of corrosion. This model couples electrochemical oxydation and reduction reactions. Regarding kinetics, cellular automata models are able to describe current as a function of the applied potential for a redox reaction on an inert electrode. The inclusion of probabilities allows the description of the stochastic nature of anodic and cathodic reactions. Corrosion morphology has been studied in different context: generalised corrosion, pitting corrosion and corrosion in an occluded environment. A general tendency of two regimes is found. A first regime of uniform corrosion where the anodic and cathodic reactions occur homogeneously over the surface. A second regime of localized corrosion when there is a spatial separation of anodic and cathodic zones, with an increase of anodic reaction rate.

Le but de cette thèse est l'étude des Automates Cellulaires (AC) dans la perspective des fonctions booléennes et des dessins combinatoires. Au-delà de son intérêt théorique, cette recherche est motivée par ses applications à la cryptographie, puisque les fonctions booléennes et les dessins combinatoires sont utilisés pour construire des générateurs de nombres pseudo aléatoires (Pseudorandom Number Generators, PRNG) et des schémas de partage de secret (Secret Sharing Schemes, SSS). Les résultats présentés dans la thèse ont été développés sur trois lignes de recherche, organisées comme suit. La première ligne porte sur l'utilisation des algorithmes d'optimisation heuristique pour chercher des fonctions booléennes ayant des bonnes propriétés cryptographiques, à utiliser comme des règles locales dans des PRNG basés sur les AC. La motivation principale est l'amélioration du générateur de Wolfram basé sur la règle 30, qui a été montré être vulnérable vis à vis de deux attaques cryptanalytiques. La deuxième ligne s'occupe des fonctions booléennes vectorielles engendrées par les règles globales des AC. La première contribution considère la période des pré-images des configurations spatialement périodiques dans les AC surjectifs, et l'analyse des propriétés cryptographiques des règles globales des AC. La troisième ligne se concentre sur les dessins combinatoires engendrés par les AC, en considérant les Carrés Latins Orthogonaux (Orthogonal Latin Squares, OLS), qui sont équivalents aux SSS. En particulier, on donne une caractérisation algébrique des OLS engendrés par les AC linéaires, et on utilise des algorithmes heuristiques pour construire des OLS basés sur des AC non linéaires. / The goal of this thesis is the investigation of Cellular Automata (CA) from the perspective of Boolean functions and combinatorial designs. Beside its theoretical interest, this research finds its motivation in cryptography, since Boolean functions and combinatorial designs are used to construct Pseudorandom Number Generators (PRNG) and Secret Sharing Schemes (SSS). The results presented in the thesis are developed along three research lines, organized as follows. The first line considers the use of heuristic optimization algorithms to search for Boolean functions with good cryptographic properties, to be used as local rules in CA-based PRNG. The main motivation is to improve Wolfram's generator based on rule 30, which has been shown to be vulnerable against two cryptanalytic attacks. The second line deals with vectorial Boolean functions induced by CA global rules. The first contribution considers the period of preimages of spatially periodic configurations in surjective CA, and analyze the cryptographic properties of CA global rules. The third line focuses on the combinatorial designs generated by CA, specifically considering Orthogonal Latin Squares (OLS), which are equivalent to SSS. In particular, an algebraic characterization of OLS generated by linear CA is given, and heuristic algorithms are used to build OLS based on nonlinear CA.

Les automates cellulaires sont à la fois un modèle de calcul parallèle, un système complexe et un système dynamique. Ils fonctionnent de manière synchrone et en temps discret, leur particularité est que les fonctions qu'ils définissent sont issues de l'application simultanée, en tout point de l'espace, d'une règle d'évolution locale. L'ensemble limite est un objet classique des systèmes dynamiques, c'est l'ensemble des états que le système peut atteindre arbitrairement tard. Il a été très étudié dans le cadre des automates cellulaires, et les résultats sont nombreux. Parmi ces résultats, un théorème de Rice démontré par Jarkko Kari dit que toute propriété des ensembles limites est indécidable. Dans ce mémoire, on ne s'intéresse plus à l'ensemble limite traditionnel, mais à une variante pour laquelle on utilise une mesure sur l'espace des entrées, sélectionnant ainsi les comportements susceptibles d'apparaître arbitrairement tard et souvent. Ce nouvel ensemble, que l'on nomme ensemble mu-limite, a été introduit en 2000 par Petr Kurka et Alejandro Maass. La plupart des résultats sur les ensembles limites ne se transposent pas naturellement. On étudie la famille des ensembles mu-limites d'automates cellulaires. On montre que sous certaines contraintes sur la dynamique, l'ensemble mu-limite peut être entièrement décrit. On classe ainsi les automates en fonction de ces contraintes. Dans le cas général, on montre l'existence d'automates cellulaires ayant comme ensembles mu-limites un grand nombre d'ensembles complexes. On finit par montrer un théorème de Rice pour les ensembles mu-limites d'automates cellulaires: tout propriété non triviale de ces ensembles est indécidable. / Cellular automata are simultaneously a model of parallel computation, a complex system and a dynamical system. They are synchronous and time is discrete. The functions defined by their application is the result of the synchronous application of the same local rule everywhere. The limit set is a classical tool of dynamical systems theory, it is the set of states the system can reach arbitrarily late. It has been studied often in the particular case of cellular automata and there are numerous results. Amongst them, a Rice's theorem proved by Jarkko Kari states that any non-trivial property of limit sets of cellular automata is undecidable. In this thesis, we do not consider the classical limit set, as we add a measure on the space of states of the system. Thus, we get a set which contains behaviors that appear arbitrarily far and often. This set is named mu-limit set and was introduced in 2000 by Petr Kurka and Alejandro Maass. Most of the results on limit sets cannot be directly adapted for mu-limit sets. We study the family of all mu-limit sets of cellular automata. We show that under some constraints on the dynamics, the mu-limit set can be entirely described. We then produce a classification of cellular automata according to these constraints. In the general case, we prove the existence of cellular automata whose mu-limit sets are among a large set of complex sets. We finally prove Rice's theorem for mu-limit sets: any non-trivial property is undecidable.

Les automates cellulaires forment une famille bien connue de modèles dynamiques discrets, introduits par S.Ulam et J. von Neumann dans les années 40. Ils ont été étudiés avec succès sous différents points de vue: modélisation, dynamique, ou encore complexité algorithmique. Dans ce travail, nous adoptons ce dernier point de vue pour étudier la famille des automates cellulaires coagulants, ceux dont l’état d’une cellule nepeut évoluer qu’en suivant une relation d’ordre prédéfinie sur l’ensemble de ses états. Nous étudions la complexité algorithmique de ces automates cellulaires de deux points de vue : la capacité de certains automates coagulants à simuler tous les autres automates cellulaires coagulants, appelée universalité intrinsèque, et la complexité temporelle de prédiction de l’évolution d’une cellule à partir d’une configuration finie, appelée complexité de prédiction. Nous montrons que malgré les sévères restrictions apportées par l’ordre sur les états,les automates cellulaires coagulants peuvent toujours exhiber des comportements de grande complexité.D’une part, nous démontrons qu’en dimension deux et supérieure il existe un automate cellulaire coagulants intrinsèquement universel pour les automates cellulaires coagulants en codant leurs états par des blocs de cellules ; cet automate cellulaire effectue au plus deux changements d’états par cellule. Ce résultat est minimal en dimension deux et peut être amélioré en passant à au plus un changement en dimensions supérieures.D’autre part, nous étudions la complexité algorithmique du problème de prédiction pour la famille des automates cellulaires totalistiques à deux états et voisinage de von Neumann en dimension deux. Dans cette famille de 32 automates, nous exhibons deux automates de complexité maximale dans le cas d’une mise à jour synchrone des cellules et nous montrons que dans le cas asynchrone cette complexité n’est atteinte qu’à partir de la dimension trois. Pour presque tous les autres automates de cette famille, nous montrons que leur complexité de prédiction est plus faible (sous l’hypothèse P 6≠NP). / Cellular automata are a well know family of discrete dynamic systems, defined by S. Ulam and J. von Neumannin the 40s. The have been successfully studied from the point of view of modeling, dynamics and computational complexity. In this work, we adopt this last point of view to study the family of freezing cellular automata, those where the state of a cell can only evolve following an order relation on the set of states. We study the complexity of these cellular automata from two points of view, the ability of some freezing cellular automata to simulate every other freezing cellular automata, called intrinsic universality, and the time complexity to predict the evolution of a cell starting from a given finite configuration, called prediction complexity. We show that despite the severe restriction of the ordering of states, freezing cellular automata can still exhibit highly complex behaviors.On the one hand, we show that in two or more dimensions there exists an intrinsically universal freezing cellular automaton, able to simulate any other freezing cellular automaton by encoding its states into blocks of cells, where each cell can change at most twice. This result is minimal in dimension two and can be even simplified to one change per cell in higher dimensions.On the other hand, we extensively study the computational complexity of the prediction problem for totalistic freezing cellular automata with two states and von Neumann neighborhood in dimension two. In this family of 32 cellular automata, we find two automata with the maximum complexity for classical synchronous cellular automata, while in the case of asynchronous evolution, the maximum complexity can only be achived in dimension three. For most of the other automata of this family, we show that they have a lower complexity (assuming P 6≠NP).

Dans le contexte du calcul géométrique abstrait, les machines à signaux ont été développées comme le pendant continu des automates cellulaires capturant les notions de particules, de signaux et de collisions. Une question importante est la génération automatique d’un automate cellulaire reproduisant la dynamique d’une machine à signaux donnée. D’une part, il existe des conversions ad hoc. D’autre part, ce n’est pas toujours possible car certaines machines à signaux présentent des comportements « continus ». Par conséquent, la discrétisation automatique de telles structures est souvent complexe et pas toujours possible. Cette thèse propose trois manières différentes de discrétiser automatiquement les machines à signaux en automates cellulaires, avec ou sans approximation possible. La première s’intéresse à une sous-catégorie de machines à signaux, qui présente des propriétés permettant d’assurer une discrétisation automatique exacte pour toute machine de ce type. La deuxième est utilisable sur toutes les machines mais ne peut assurer ni l’exactitude ni la correction du résultat. La troisième s’appuie sur une nouvelle expression de la dynamique d’une machine à signaux pour proposer une discrétisation. Cette expression porte le nom de modularité et est décrite avant d’être utilisée pour discrétiser. / In the context of abstract geometrical computation, signal machines have been developed as a continuous counter part of cellular automata capturing the notions of particles, signals and collisions. An important issue is the automatic generation of a cellular automaton mimicking the dynamics of a given signal machine. On the one hand, ad hoc conversions exist.On the other hand, it is not always possible since some signal machines exhibit “purely continuous” behaviors. Therefore, automatically discretizing such structures is often complicated and not always possible. This thesis proposes different ways to automatically discretize signal machines into cellular automata, both with and without handling the possiblity of approximation.The first is concerned with a subcategory of signal machines, which has properties ensuring an exact automatic discretization for any machine of this type. The second is usable on all machines but cannot guarantee the exactness and correction of the result. The third is based on a new expression of the dynamics of a signal machine to propose a discretization.This dynamical expression takes the name of modularity and is described before being used to discretize.

En raison de leur caractère torrentiel, les « crues rapides » qui apparaissent en périodes printanière et estivale dans les régions du nord de la France constituent aujourd'hui la forme la plus originale et la plus dangereuse des inondations rencontrées dans ces régions. Le poids des activités humaines dans le fonctionnement de ces crises hydrologiques est incontestable. Ces crues turbides prennent naissance sur des territoires agricoles où les espaces cultivés ne cessent de se développer. L'urbanisation croissante et la place du réseau routier dans les axes majeurs d'écoulement aggravent la rapidité des flux et la vulnérabilité des biens et des personnes. Afin d'améliorer la connaissance sur ces événements, un inventaire a été réalisé à partir des dossiers « CatNat ». L'approche comparative menée sur les 189 bassins versants recensés (1983-2005) a permis de faire ressortir l'influence de la morphologie à différentes échelles. La vitesse de concentration de l'écoulement rapide est principalement liée à la combinaison entre le système de pentes, l'organisation des réseaux de talwegs et la forme des bassins versants. Il n'existait cependant aucune méthode permettant de mesurer, de manière synthétique et continue, le rôle de cette composante sur la dynamique hydrologique d'un bassin versant. Les approches quantitatives se sont limitées à des mesures séparées des composantes morphologiques (indices de compacité, rapport de confluence d'Horton, courbe hypsométrique...). En s'appuyant sur la théorie des systèmes complexes, et en particulier sur les automates cellulaires, il a été possible de développer des méthodes permettant de quantifier l'efficacité de la structuration en trois dimensions du « bassin versant ». L'adaptation de ces nouvelles méthodes d'analyse spatiale, encore peu employées en géomorphologie, nécessitera une réflexion sur la validité des outils et la pertinence des<br />résultats en réintégrant progressivement les autres variables de l'hydrosystème. Tous ces résultats aboutissent à la réalisation de différentes cartes de sensibilité dans ces régions du nord de la France.

Dans cette thèse, nous proposons successivement deux modèles discrets par réseaux d'automates cellulaires, du processus de subduction-érosion en<br />tectonique des plaques, puis présentons les simulations informatiques parallèles correspondantes.<br /><br />Après une présentation de la tectonique des plaques et des marges convergentes de type II (avec érosion), nous présentons les deux tendances de modélisation existantes, étudions leurs avantages et inconvénients respectifs et montrons l'intérêt de développer une démarche radicalement différente. Nous exposons alors nos hypothèses de travail relativement restrictives et leurs limites, en commençant d'abord par présenter la géométrie d'ensemble du "plan de coupe de modélisation" et sa dynamique, puis en énumérant les phénomènes à reproduire, enfin, en introduisant des échelles de temps et la représentation de l'érosion par une altération (un changement de matière) due au vieillissement.<br /><br />En ce qui concerne les modélisations plus précisément, nous nous inspirons très fortement du "Sand Pile Model" uni-dimensionnel pour développer notre propre modèle uni-dimensionnel et introduire la notion de réseau d'automates cellulaires fini généralisé. Dans le cas du modèle bi-dimensionnel, partant du même principe, nous cherchons à implémenter un modèle d'avalanches dans un tas de sable représenté par un réseau d'automates cellulaires bi-dimensionnel. Constatant que la multiplication des informations stockées dans la structure même du réseau offre un meilleur rendu-visuel, nous choisissons alors de généraliser cette méthode et abordons la description de notre propre réseau d'automates cellulaires.<br /><br />Les temps de calcul respectifs de chacune des simulations séquentielles ainsi que le fait que les réseaux d'automates cellulaires constituent un modèle canonique du calcul parallèle à fine granularité, nous incitent à développer des simulations parallèles et à les porter sur des ordinateurs parallèles tels que le CRAY T3E et l'ORIGIN 2000. Après avoir exposé la stratégie de décomposition de domaine que nous avons employée (avec équi-répartition de la charge des sous-domaines sur l'ensemble des processeurs et minimisation de la taille des problèmes aux interfaces), nous montrons l'intérêt d'utiliser une bibliothèque d'échanges de messages appropriée dans le cadre d'une décomposition de domaine régulière sur une architecture parallèle à mémoire distribuée.<br /><br />Les résultats obtenus sont révélateurs (pour la simulation bi-dimensionnelle du moins) de la très bonne parallélisabilité du problème posé. Ils nous permettent de présenter quelques copies d'écran des animations graphiques<br />obtenues et leur validation d'un point de vue géotectonique. Des développements futurs pourraient être orientés vers la mise au point d'une plate-forme logicielle parallèle adaptée, puis vers une étude de qualification de la concentration des déformations au sein de la plaque chevauchante.

Cette thèse s'intéresse dans un premier temps aux automates cellulaires réversibles, et dans un second temps aux tas de sable linéaires. Nous construisons diverses simulations reliant les automates cellulaires aux automates à partitions, en particulier celle des automates cellulaires réversibles par les automates à partitions réversibles, ce qui était une conjecture depuis 1990. Par des constructions successives, nous montrons que le ``Billiard ball model'' de Toffoli et Margolus est capable de simuler tous les automates à partitions réversibles de dimension 2. En rassemblant ces résultats, nous montrons qu'il existe des automates cellulaires réversibles capables de simuler tous les automates cellulaires réversibles de même dimension. Dans un espace linéaire, ``Tas de sable'' et ``Chip firing game'' sont équivalents. Nous portons notre attention sur le cas où les grains tombent un à un. Des motifs délimités par des signaux apparaissent au sein des configurations engendrées. Nous étudions la dynamique du système et démontrons un équivalent asymptotique. Nous étendons nos méthodes et nos résultats à d'autres types de configurations initiales. Dans chaque cas étudié, le temps parallèle est inférieur au temps séquentiel dans un rapport de l'ordre du nombre de piles mises en œuvre.