... | ... | @@ -16,17 +16,51 @@ Cette vision initiera tout un développement encore très actif autour des autom |
|
|
|
|
|
## Description
|
|
|
Les automates cellulaires sont des machines à états finis évoluant sur une grille infinie, le plus souvent, et de dimension `n`. Les dimensions habituelles sont généralement 1 ou 2. La grille définit un espace discret et un voisinage pour chacune des cases de la grille. Cette grille peut être régulière ou non et les cases peuvent prendre différentes formes (rectangulaire, hexagonale ....).
|
|
|
On associe à chaque case de la grille une **cellule**, cette dernière va alors avoir un état, ce dernier est déterminé par l'état de la cellule considérée, le voisinage et une règle de transition. L'automate cellulaire évolue en fonction de ces modifications qui peuvent se faire de façon synchrone ou asynchrone. Dans ce qui suit nous considérerons que le premier cas.
|
|
|
On associe à chaque case de la grille une **cellule**, cette dernière va alors avoir un état, ce dernier est déterminé par l'état de la cellule considérée, le voisinage et une règle de transition. L'automate cellulaire évolue en fonction de ces modifications qui peuvent se faire de façon synchrone ou asynchrone. Dans ce qui suit nous considérerons uniquement le premier cas.
|
|
|
|
|
|
Soit
|
|
|
* $`L`$ un réseau régulier (ses éléments sont des cellules) ;
|
|
|
* $`S`$ un ensemble fini d’états ;
|
|
|
* $`N`$ un ensemble fini d’indices de voisinage (de taille $`n`$ ) tels que
|
|
|
|
|
|
```math
|
|
|
\forall c \in N, \forall r \in L, r + c \in L
|
|
|
```
|
|
|
|
|
|
* Une fonction de transition : $`f : S^n \rightarrow S `$ ;
|
|
|
* Un automate cellulaire est défini par le 4-tuple : $`(L, S, N, f)`$ ;
|
|
|
* Une configuration $`C_1 : L \rightarrow S`$ est une fonction qui associe
|
|
|
un état à chaque cellule du réseau ;
|
|
|
*
|
|
|
|
|
|
|
|
|
## Automates de dimension 1
|
|
|
|
|
|
Considérons un ruban infini des deux cotés, subdivisé en cellules. Chaque cellule pouvant prendre une valeur dans un ensemble fini. Par commodité de représentation on va transcrire ces valeurs en une couleur. Ainsi on va utiliser deux couleurs blanc et bleu :
|
|
|
|
|
|

|
|
|
|
|
|
Chaque cellule va alors changer de couleur en fonction de la couleur de ses voisines.
|
|
|
|
|
|
|
|
|
|
|
|
### Classes d'automate
|
|
|
|
|
|
```mermaid
|
|
|
graph TD;
|
|
|
A-->B;
|
|
|
A-->C;
|
|
|
B-->D;
|
|
|
C-->D;
|
|
|
```
|
|
|
|
|
|
## Automates de dimension 2
|
|
|
|
|
|
### Le jeu de la vie
|
|
|
|
|
|
|
|
|
## Conception
|
|
|
|
|
|
## Automates auto-reproducteurs
|
|
|
|
|
|
|
... | ... | |