Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Ministère de l’Enseignement Supérieur Burkina Faso de la Recherche Scientifique

Ministère de l’Enseignement Supérieur Burkina Faso de la Recherche Scientifique et de l’Innovation Unité-Progrès-Justice ----------------- Université Ouaga I Pr. Joseph KI-ZERBO ----------------- Unité de Formation et de Recherche en Sciences Exactes et Appliquées. (UFR/SEA) MODELISATION Réalisé par : Nom du professeur : M. NEBIE Bayomon Emile M. Frédéric OUEDRAOGO Master1 S2 Informatique/Système d’Information et Réseaux. Année universitaire 2016-2017 THEME : AUTOMATES CELLULAIRES 2 Table des matières INTRODUCTION ...................................................................................................................... 3 I. GENERALITES SUR LES AUTOMATES CELLULAIRES ........................................... 4 1. Historique ........................................................................................................................ 4 2. Définition ........................................................................................................................ 4 3. Autres notions théoriques sur les automates cellulaires .................................................. 5 3.1. Configuration de l’automate cellulaire A .................................................................. 5 3.2. Systèmes dynamiques ............................................................................................... 5 3.3. Algorithmique et modèle de calcul ........................................................................... 5 3.4. Universalités .............................................................................................................. 6 3.5. Indécidabilité et complexité des automates cellulaires ............................................. 7 4. Exemples d’automates cellulaires .................................................................................... 8 II. CLASSIFICATION DES AUTOMATES CELLULAIRES .......................................... 9 1. Familles Classiques .......................................................................................................... 9 2. Autres classifications ...................................................................................................... 10 2.1. Classification de Stephen Wolfram ......................................................................... 10 2.2. Classification d’Eppstein ......................................................................................... 10 III. MODELISATION ET APPLICATIONS ..................................................................... 11 1. Modélisation en physique .............................................................................................. 11 2. Phénomènes biologiques ............................................................................................... 12 CONCLUSION ........................................................................................................................ 13 BIBLIOGRAPHIE ET WEBOGRAPHIE ............................................................................... 14 3 INTRODUCTION La modélisation est une activité consistant à concevoir des représentations d’ objets ou des phénomènes dans un cadre idéalisé par les hypothèses et les règles qui ont servi à sa construction. Une telle représentation est dite modèle. Les automates cellulaires sont perçus comme des modèles. Étudiés en mathématiques et en informatique théorique, les automates cellulaires sont à la fois un modèle de système dynamique discret et un modèle de calcul. Dans une perspective, nous nous posons les questions : qu’est-ce qu’un automate cellulaire ? et quelle est son utilité ? c’est ainsi que le sujet intitulé « automates cellulaires » est soumis à notre étude. Notre travail est structuré en trois parties dont la première sera consacrée à la mise en œuvre d’une étude théorique des automates cellulaires. Quant à la deuxième partie elle portera sur la classification des automates cellulaires et enfin la dernière mettra en exergue leur modélisation et application. 4 I. GENERALITES SUR LES AUTOMATES CELLULAIRES 1. Historique Les automates cellulaires ont débuté dans les années 1940 avec Stanislaw Ulam et John Von Neumann. Ulam étudiait la croissance des cristaux au Laboratoire national de Los Alamos, en la modélisant sur une grille. Dans le même temps, John Von Neumann, collègue d'Ulam à Los Alamos, travaillait sur des systèmes auto-réplicatifs et rencontrait des difficultés pour expliciter son modèle initial d'un robot qui se copierait tout seul à partir d'un ensemble de pièces détachées. Ulam lui suggéra de s'inspirer de ses travaux, ce qui conduisit Von Neumann à concevoir un modèle mathématique abstrait pour son problème. Le résultat fut le système auto-réplicatif, robot qui se copie tout seul ce fut la naissance du premier automate cellulaire. En 1969, Gustav Arnold Hedlund publie Endomorphisms and Automorphisms of the Shift Dynamical System, une monographie de 60 pages environ qui synthétise 10 ans de recherche d'une communauté travaillant dans le domaine de la dynamique symbolique (une branche de l'étude des systèmes dynamiques en mathématiques, fondée notamment par M. Morse et G. A. Hedlund). C'est cette publication qui pose les bases mathématiques de l'étude des automates cellulaires comme des systèmes dynamiques particuliers. En 1969 également, Konrad Zuse publia Rechnender Raum (« Quand l'espace calcule ») où il émettait l'hypothèse que les lois physiques étaient discrètes et que l'Univers était le résultat d'un gigantesque automate cellulaire. Dans les années 1970, un automate cellulaire à deux dimensions et deux états nommé « le jeu de la vie », inventé par John Conway. En 1983, Stephen Wolfram publia la première d'une série de publications où il analysait de façon systématique un type d'automates cellulaires très simples. La complexité de leur comportement, induit par des règles élémentaires, le poussa à conjecturer que des mécanismes similaires pourraient expliciter des phénomènes physiques complexes, idées qu'il développa dans son livre A New Kind of Science paru en 2002. 2. Définition Un automate cellulaire peut être vu comme une infinité de petites machines identiques : les cellules (parallélisme massif), réparties sur un graphe régulier (espace discret). Les cellules n’ont qu’une mémoire finie, c’est-à-dire qu’elles ne peuvent être que dans un nombre fini d’états possibles et qu’elles ne portent pas d’autre information que leur état. À chaque étape de temps (temps discret et synchrone), chaque cellule change son état courant en fonction de son état et de celui de ses voisines uniquement. Plus clairement on définit un automate cellulaire comme suit : Un automate cellulaire est un quadruplet A= (d, Q, V, δ) où :  d ∈ N* est la dimension de l'automate, l'espace discret de dimension d ; 5  Q un ensemble fini d’états, est son alphabet ;  V Son voisinage, V = (v1, v2, ..., vn) ∈ ( )n (un sous-ensemble fini du réseau) ;  δ : Qn → Q est sa règle locale de transition et n = | Q |. Réseau de cellules : le réseau est systématiquement de la forme selon la définition. 3. Autres notions théoriques sur les automates cellulaires 3.1. Configuration de l’automate cellulaire A On appelle une configuration de l’automate A une application : → Q. On associe à chaque cellule de l’automate un état. On note Շ l’ensemble des configurations de A. Avec Շ = Q 3.2. Systèmes dynamiques Un automate cellulaire peut être considéré comme un système dynamique à temps et espace discrets en munissant Շ de la fonction globale de transition de l’automate A, c’est à dire la fonction d’évolution temporelle de la configuration. Cette fonction F : Շ → Շ est la fonction de transition globale : ∀ c ∈ Շ, ∀ γ ∈ , F(c)(γ) = δ(c(γ + v1), ..., c(γ + vn)) Avec V = (v1, v2, ..., vn) voisinage. L’automate cellulaire décrit alors le système dynamique : {∀ c0 ∈ Շ ∀ n ∈ N, Շn+1 = F(Շn) 3.3. Algorithmique et modèle de calcul La forme de changement d’échelle la plus courante dans les constructions algorithmiques sur automates cellulaires est variante. Il existe cependant des algorithmes pour déterminer d’autres calculs, on a : - l'algorithme de P. C. Fischer pour reconnaître les nombres premiers (figure 1). - Le problème de la ligne de fusiliers : une solution ayant 6 états seulement a été publiée par Jacques Mazoyer, il a également prouvé qu'il n'y avait pas de solution à 4 états. Figure 1 : Transformation géométrique de P. C. Fischer 6 3.4. Universalités L’universalité pour un automate cellulaire revient avec la question : existe-t-il un automate capable de faire tout ce que peuvent faire les automates cellulaires ? Un tel automate est alors dit universel. On peut distinguer deux types de notions d'universalité pour les automates cellulaires : l'universalité Turing qui est associée à la capacité de calcul et l'universalité intrinsèque qui est associée à la capacité de produire certains comportements dynamiques. Le fait remarquable est que pour chacune de ces notions il existe des automates universels. Il faut noter également que la notion d'universalité intrinsèque est plus forte que l'universalité Turing : en effet, sans rentrer dans les détails, un automate capable de simuler tous les automates peut en particulier simuler un automate Turing-universel et donc effectuer tous les calculs Turing. En revanche, il existe des automates cellulaires Turing-universels qui ne sont pas intrinsèquement universels.  Universalité Turing L'universalité Turing est une adaptation aux automates cellulaires de l'universalité pour le calcul. On peut définir cette notion comme la capacité d'un automate à simuler une machine de Turing universelle. Cette possibilité de simulation d'une machine de Turing par un automate cellulaire est très simple et était connue dès les travaux de John Von Neumann. Il existe plusieurs manières de la formaliser et ce qui suit est l'une des plus simples. Si M est une machine de Turing fonctionnant avec un alphabet de ruban Ʃ et un ensemble d'état Q, on peut définir un automate cellulaire A capable de simuler M : - L'alphabet de A est Ʃ x(Q U {┴}) : ainsi chaque cellule de A possède un état (σ, q) formé d'une composante σ qui correspond au contenu du ruban et d'une composante q qui correspond à l'absence ( q = ┴) ou la présence (q∈ Q ) d'une tête de Turing à cette position et qui donne le cas échéant son état ; - Son voisinage est {-1, 0, 1} - Le comportement de A consiste à reproduire les mouvements de la tête de Turing sur la première composante et les modifications du ruban sur la deuxième composante exactement comme le ferait M : Figure 2 : Démonstration 7  Universalité intrinsèque Un automate cellulaire intrinsèquement universel est un automate capable de simuler pas à pas le comportement de n'importe quel automate cellulaire de même dimension. Plus précisément, l'idée de simulation pas à pas repose sur les principes suivants :  Dans l'automate simulateur, on forme des groupes de cellules voisines, tous identiques, qui recouvrent régulièrement le réseau de cellules ; uploads/Science et Technologie/ projetdemodelisation-nebie-bayomon-emile.pdf