Automates cellulaires
Cours de recherche (24h de cours, travail
sur des articles scientifiques),
Cours : Jacques Mazoyer (Jacques.Mazoyer)
Présentation
Les automates cellulaires ont été introduits par J. von
Neumann pour comprendre la logique de l'auto-organisation et
éprouver un concept de complexité. Ils l'ont également
été par K. Zuse pour modéliser des phénomènes
physiques. Ce sont des objets bien formalisés, dont l'étude
théorique, qui nous intéresse ici, les fait apparaître
essentiellement comme modèles de calcul massivement
parallèle ou comme systèmes dynamiques discrets. Ils sont
impliqués dans des problématiques comme celles du chaos, de
l'émergence, de la complexité. L'objectif de ce cours est de
présenter les notions de base, prouver certains résultats
significatifs et formuler divers problèmes ouverts.
Plan du cours
- Introduction.
- Définition algorithmique, caractérisation mathématique (Hedlund, Robertson). Différents types : surjectifs, injectifs, périodiques, nilpotents, additifs ... Théorème de Moore Myhill.
- Point de vue modèle de calcul
-
Algorithmique : Algorithme de Fischer, signaux, Firing Squad.
- Puissance de calcul : universalité Turing et universalité intrinsèque.
- Reconnaissance de langages et classes de complexité (temps réel).
- Systèmes dynamiques
-
Différentes notions de chaos : pourquoi, comment. La classification topologique de Kurka.
- Le groupage comme moyen d'aborder la complexité. Classifications algébriques.