Tech

Concepts clé

Dossier - Les automates cellulaires
DossierClassé sous :robotique , automates cellulaires , automate cellulaire

-

Développement assez récent de la science initié par les travaux de Von Neumann , et mis à portée d'un public plus large par des réalisations comme le Jeu de la Vie de Conway, les automates cellulaires, jouent leur atout en ingénierie et dans la recherche.

  
DossiersLes automates cellulaires
 

Voici quelques concepts clé que se partagent la plupart des automates cellulaires, et qui permettent de cerner leur mode de fonctionnement.

Notons toutefois qu'on ne peut réduire exclusivement la définition d'automate cellulaire à ces quelques concepts. Si certains d'entre eux comme le parallélisme ou le voisinage semblent être liés intrinsèquement à leur définition, d'autres comme déterminisme ou homogénéité peuvent laisser planer un doute.

En effet, nombreux sont les automates cellulaires non pleinement déterministes. L'intégration d'une once d'aléatoire les ferait-il passer de l'autre côté de la barrière pour autant ? Le choix de les classer ou non comme "automate cellulaire" reste une question de point de vue dont le débat n'est pas une de nos préoccupations premières.

  • Voisinage

Le nouvel état de chaque cellule est déterminé à partir de sa position spatiale dans l'univers de l'automate, en examinant les états des cellules voisines. Les transitions d'un état à l'autre de l'automate se font localement pour chaque cellule (cf. caractéristiques - voisinage).

  • Parallélisme

Toutes les cellules constituant l'univers de l'automate sont mises à jour de manière simultanée et synchrone (recours à un buffer en pratique pour simuler le pseudo-parallélisme / architectures parallèles).

  • Déterminisme

Pour une cellule, la donnée des états des cellules voisines détermine à elle seule le nouvel état. Certains automates cellulaires dits stochastiques introduisent un facteur probabilité dans la transition : une même configuration de voisinage pourra conduire à différentes nouvelles configurations.

  • Homogènéité

Toutes les cellules de l'automate utilisent les même règles de transition pour déterminer leur état suivant.

  • Discrétisation

Un automate cellulaire se déroule dans le temps de manière discrète, génération après génération, en opposition avec la plupart des phénomènes physiques continus.