Automate cellulaire - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Introduction

À gauche, une règle locale simple : une cellule passe d'un état (i) au suivant (i+1) dans le cycle d'états dès que i+1 est présent dans au moins 3 cellules voisines. À droite, le résultat (complexe !) de l'application répétée de cette règle sur une grille ( Un grille-pain est un petit appareil électroménager. Une grille écran est un élément du tube de télévision. Une grille d'arrêt est un élément du tube de télévision. Une grille de contrôle...) de cellules. Ce type d'automates cellulaires a été découvert par D. Griffeath.

Un automate cellulaire consiste en une grille régulière de « cellules » contenant chacune un « état » choisi parmi un ensemble fini (En mathématiques, un ensemble E est dit fini si et seulement si E est vide ou s'il existe un entier n et une bijection de E dans l'ensemble des n premiers entiers...) et qui peut évoluer au cours du temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.). L'état d'une cellule au temps t+1 est fonction de l'état au temps t d'un nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) fini de cellules appelé son « voisinage ». À chaque nouvelle unité de temps, les mêmes règles sont appliquées simultanément à toutes les cellules de la grille, produisant une nouvelle « génération » de cellules dépendant entièrement de la génération précédente.

Étudiés en mathématiques (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que...) et en informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement automatique de l'information par des...) théorique, les automates cellulaires sont à la fois un modèle de système dynamique (En mathématiques, en physique théorique et en ingénierie, un système dynamique est un système classique qui évolue au cours du...) discret et un modèle de calcul. Le modèle des automates cellulaires est remarquable par l'écart entre la simplicité de sa définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) et la complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri Atlan), en sociologie, en informatique ou en sciences de...) que peuvent atteindre certains comportements macroscopiques : l'évolution dans le temps de l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un...) des cellules ne se réduit pas (simplement) à la règle locale qui définit le système. À ce titre il constitue un des modèles standards dans l'étude des systèmes complexes.

Exemples

Les automates cellulaires les plus simples

L'automate (Un automate est un dispositif se comportant de manière automatique, c'est-à-dire sans intervention d'un humain. Ce comportement peut être figé, le système fera...) cellulaire non-trivial le plus simple que l'on puisse concevoir consiste en une grille unidimensionnelle de cellules ne pouvant prendre que deux états (« 0 » ou « 1 »), avec un voisinage (La notion de voisinage correspond à une approche axiomatique équivalente à celle de la topologie. La topologie traite plus naturellement les notions globales comme la continuité qui s'entend ici...) constitué, pour chaque cellule, d'elle-même et des deux cellules qui lui sont adjacentes.

Chacune des cellules pouvant prendre deux états, il existe 23=8 configurations (ou motifs) possibles d'un tel voisinage. Pour que l'automate cellulaire fonctionne, il faut définir quel doit être l'état, à la génération suivante, d'une cellule pour chacun de ces motifs. Il y a 28=256 façons différentes de s'y prendre, soit donc 256 automates cellulaires différents de ce type.

Les automates de cette famille sont dit "élémentaires". On les désigne souvent par un entier entre 0 et 255 dont la représentation binaire est la suite des états pris par l'automate sur les motifs successifs 111, 110, 101, etc.

À titre d'exemple, considérons l'automate cellulaire défini par la table suivante, qui donne la règle d'évolution :

Motif initial 111 110 101 100 011 010 001 000
Valeur suivante de la cellule centrale 0 0 0 1 1 1 1 0

(cela signifie que si par exemple, à un temps t donné, une cellule est à l'état « 1 », sa voisine de gauche à l'état « 1 » et sa voisine de droite à l'état « 0 », au temps t+1 elle sera à l'état « 0 ».)

Si l'on part d'une grille initiale où toutes les cellules sont à l'état « 0 » sauf une, on aboutit à :

Exemple d'automate cellulaire unidimensionnel

où chaque ligne est le résultat de la ligne précédente.

Par convention cette règle est nommée « règle 30 », car 30 s'écrit 00011110 en binaire et 00011110 est la deuxième ligne du tableau (Tableau peut avoir plusieurs sens suivant le contexte employé :) ci-dessus, décrivant la règle d'évolution.

Le jeu de la vie (La vie est le nom donné :)

Quelques étapes d'évolution du jeu de la vie à partir d'une configuration initiale choisie au hasard (Dans le langage ordinaire, le mot hasard est utilisé pour exprimer un manque efficient, sinon de causes, au moins d'une reconnaissance de cause à effet d'un événement.).

Le « jeu de la vie » est un automate cellulaire bidimensionnel où chaque cellule peut prendre deux valeurs (« 0 » ou « 1 », mais on parle plutôt de « vivante » ou « morte ») et où son état futur est déterminé par son état actuel et par le nombre de cellules vivantes parmi les huit qui l'entourent :

  • Si la cellule est vivante et entourée par deux ou trois cellules vivantes, elle reste en vie à la génération suivante, sinon elle meurt.
  • Si la cellule est morte et entourée par exactement trois cellules vivantes, elle naît à la génération suivante.

En apparence simples, ces règles font émerger une forte complexité.

On peut sur le même principe imaginer un grand nombre de règles en faisant varier les seuils de naissance ou de survie, ou en ajoutant des états supplémentaires, etc. Parmi ces variations, on peut citer :

  • Day & Night
  • HighLife
  • Immigration (L'immigration désigne aujourd'hui l'entrée, dans un pays, de personnes étrangères qui y viennent pour y séjourner. Le mot immigration vient du latin migratio qui signifie...)
  • QuadLife

Certains ne prennent en compte pour déterminer les changements d'état d'une cellule que les voisins immédiats de la case considérée, mais d'autres prennent également en compte l'état des cellules voisines dans un rayon de deux cases, voire plus. D'autres attribuent aussi un poids (Le poids est la force de pesanteur, d'origine gravitationnelle et inertielle, exercée par la Terre sur un corps massique en raison uniquement du voisinage de la Terre. Elle est égale à l'opposé de...) plus important à certaines cases du voisinages qu'à d'autres (WeightedLife).

Tous les autres...

Les règles possibles pour définir un automate cellulaires sont très nombreuses, même avec un petit nombre d'états et un petit voisinage :

2 états 3 états 4 états 5 états
2 voisins 16 19 683 4 294 967 296 > 1017
3 voisins 256 7 625 597 484 987 > 1038 > 1087
4 voisins 65 536 > 1038 > 10154 > 10436
5 voisins 4 294 967 296 > 10115 > 10616 > 102184
6 voisins > 1019 > 10347 > 102466 > 1010921

Le modèle des automates cellulaire offre donc un terrain d'exploration (L'exploration est le fait de chercher avec l'intention de découvrir quelque chose d'inconnu.) immense. Il n'est pas difficile de programmer un simulateur d'automates cellulaires et la Toile regorge de réalisations plus ou moins abouties. Le site de Mirek Wojtowicz propose par exemple un logiciel (En informatique, un logiciel est un ensemble d'informations relatives à des traitements effectués automatiquement par un appareil informatique. Y sont inclus les...) de simulation et une galerie d'exemples très riche : Mirek's Cellebration. Un autre exemple de simulateur intéressant est Golly. Il est dédié principalement au Jeu de la vie et optimisé pour cet automate en utilisant notamment des quadtree combinés avec du hachage.

Page générée en 0.095 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique