Thèse

École normale Supérieure de Lyon ; soutenue le 10 décembre 2004

• Robustesse de la dynamique des systèmes discrets : le cas de l'asynchronisme dans les automates cellulaires

Résumé:

Les automates cellulaires sont une classe de systèmes dynamiques discrets qui sont fréquemment utilisés pour modéliser des systèmes complexes dans lesquels la dynamique est spécifiée de façon locale. Dans leur acception classique, les automates cellulaires sont simulés sur une grille régulière et avec un synchronisme parfait des transitions. Néanmoins, ces deux hypothèses ont peu de chances de représenter fidèlement ce qui se déroule à une échelle microscopique pour des systèmes physiques, biologiques ou sociaux. Nous nous interrogeons donc sur la capacité des automates cellulaires à garder leur comportement lorsqu'ils sont soumis à de petites pertubrations de synchronisme ou de topologie.

Mon travail s'articule en trois parties : j'expose tout d'abord comment on peut aborder ce problème par des techniques de simulation numérique. Ensuite, je developpe des outils probabilistes (couplages, chaînes de Markov et martingales) qui permettent de traiter le problème dans certains cas particuliers. Dans un troisème temps, je me concentre sur les études "à la physicienne" dans laquelle je cherche à caractériser les transitions de phase observées. Enfin, je conclus sur l'intérêt de ce travail dans le cadre plus général de l'étude des "systèmes complexes" et de la modélisation.

English Abstract

• Robustness of discrete dynamical systems : the case of asynchronism in cellular automata (in French)

The aim of this work is to study what happens when the dynamics of a cellular automaton is perturbed (for example when the transitions are not all made at each time step). We give a formal framework to the informal concept of ``robusteness'' in order to explain why some cellular automata keep their behaviour constant while others change their behaviour, either in a continuous way, or with ``phase transitions''. The main question thus consists in quantifying the phenomena using appropriate measures. We propose a method of classification of cellular automata that use the statistical variations of the density parameter. Starting from these results, the robustnes of various automata is estimated experimentally. Results show that the celular automata studided can indeed be partionned in to various classes. Some of these classes are then studied analytically with probabilistic models such as martingales and Markov chains. Other automata are studied experimentally : we give evidence that some of the transition phases belong to the universality class and we study how the robustness of the Game of Life evolves with topology perturbations.