Automates cellulaires et pavages
Cours de recherche (30h de cours, travail
sur des articles scientifiques)
Cours : Jacques Mazoyer (Jacques.Mazoyer)
Les automates cellulaires ont été introduits dans les
années 1950 pour modéliser la vie artificielle. Depuis lors,
ils ont été utilisés pour modéliser divers
phénomènes en physique, biologie, ...mais aussi en
informatique où ils apparaissent comme un modèle bien formalisé du
parallélisme
massif. Nous les définirons, puis les étudierons comme
effectuant des calculs (algorithmique locale et massivement
parallèle) et donnerons quelques indications sur leur dynamique.
En outre, nous montrerons leurs liens en tant que systèmes de
calculs avec les pavages du plan.
Dans un premier temps, nous définirons les automates cellulaires:
aux sommets d'un graphe régulier sont attachés des automates
finis communiquant entre eux de façon uniforme. Nous
présenterons aussi les graphes d'automates (cas où le graphe
n'est plus “régulier”, mais, seulement de degré borné).
Ensuite, nous montrerons que les plus simples d'entre eux (ceux de
dimension 1) ont la puissance de calcul des machines de Turing et en
déduirons quelques résultats d'indécidabilité.
En utilisant la notion informelle de “signal”, nous
présenterons quelques algorithmes signifiants sur automates
cellulaires de dimension 1. Ces algorithmes correspondent soit à
des calculs usuels: reconnaissance des nombres premiers en temps réel (bien
sûr, en unaire), multiplication de deux entiers...Ils peuvent aussi correspondre à des problèmes sans
équivalents séquentiels: French Flag, Firing Squad (synchronisation
d'une ligne de
fusiliers),...A partir de
là, nous donnerons l'état de l'art sur leur puissance de
calcul lorsqu'on les voit comme reconnaisseurs de langages et
introduirons la question ouverte fondamentale dans ce domaine: tout langage
reconnu en espace linéaire l'est-il en temps réel?
Lorsqu'ils modélisent des phénomènes physiques,...,les propriétés des évolutions des configurations de départ au
cours du temps
sont signifiantes sur le phénomène modélisé. Nous
présenterons les diverses questions qu'on peut se poser:
réversibilité, universalité, classifications des automates
cellulaires ...Nous ferons le point sur ces questions. Savoir si un automate
cellulaire possède une de
ces propriétés peut être indécidable, toutefois dans
le cas particulier d'automates cellulaires, “dits additifs”,
l'étude de leur dynamique se ramène à des questions de
divisibilité de polynômes sur des corps finis. Nous
présenterons en détail cette équivalence.
Finalement, observant que les diagrammes espace-temps d'un automate
cellulaire de dimension un, conduisent à un pavage de Z x N, nous
étudierons les liens entre automates cellulaires et
pavages du plan
Bibliographie