[PDF] Les matériaux pour l'habitat citadin URGENT!!!
[PDF] les materiaux usuels
[PDF] Les matériaux utilisés dans la fabrication d'un convecteur
[PDF] les math et l'SVT
[PDF] les math suite et limite
[PDF] les mathematique silvouplait besoin d'aide
[PDF] les mathématiques , s'il vous plait
[PDF] Les mathématiques acariens
[PDF] les mathématiques dans l'art
[PDF] les mathématiques devoir maison sur les fonctions
[PDF] les mathematiques ma bète noir :'(
[PDF] les mathématiques un peu beaucoup ? la folie 2e année
[PDF] les mathématiques un peu beaucoup ? la folie 3e année
[PDF] les mathématiques un peu beaucoup ? la folie 4e année
[PDF] les mathématiques un peu beaucoup ? la folie 5e année
1
Automates cellulaires
Guillaume Hutzler
LaMI (Laboratoire de Méthodes Informatiques)
SyDRA (Systèmes Distribués, Réactifs et Adaptatifs) hutzler@lami.univ-evry.fr http://www.lami.univ-evry.fr/~hutzler
Plan du cours
yIntroduction Exemples simples Petit historique yDétail des choix de conception possibles yConsidérations théoriques yApplication à la modélisation et à la simulation de systèmes biologiques yConclusion
Introduction
Un exemple simple pour commencer
yL'automate élémentaire à 1 dimension Modèle à 1 dimension -Tableau de cellules à une dimension Espace d'états limité -Chaque cellule prend ses valeurs dans l'ensemble {0, 1} Voisinage réduit -Le voisinage d'une cellule se réduit aux deux cellules adjacentes Règles de transition simples -L'automate progresse par générations successives -L'état d'une cellule à la génération suivante est fonction de son état et de l'état de ses voisines à la génération courante -Toutes les cellules changent d'état de manière synchrone Etudié de manière systématique par S. Wolfram
Introduction - Un exemple simple pour commencer
Les règles de transition
yPrincipe de base yPour une cellule donnée 8 configurations possibles (2 3 2 nouveaux états possibles pour chaque configuration Au total 256 automates possibles (2 8 ex. : règle 18 -f(111)=0 - f(110)=0 -f(101)=0 - f(100)=1 -f(011)=0 - f(010)=0 -f(001)=1 - f(000)=0 n° règle = f(111)f(110)f(101)f(100)f(011)f(010)f(001)f(000)
Diagramme espace-temps
Introduction - Un exemple simple pour commencer
Un modèle de morphogénèse?
yObservation Les patterns obtenus par certains automates ressemblent aux motifs exhibés par certains coquillages Peut modéliser un processus de diffusion simple [Meinhardt &
Klingler 1987]
" Shell patterns are time records of a one-dimensional pattern forming process along the growing edge. Oblique lines result from travelling waves of activation (pigment production). Branches and crossing result from a temporary shift from an oscillatory into a steady mode of pigment production... »
Introduction - Un exemple simple pour commencer
Considérations générales
yDomaine très expérimental un automate est entièrement décrit par sa spécification Mais : impossible de prédire a priori l'état d'un automate sans l'exécuter yMais également des résultats théoriques Classes de complexité Réversibilité Jardins d'Eden et ensembles limites Lois de conservation Universalité yApplications simulation de phénomènes spatio-temporels (physique, chimie, biologie mais aussi ingénierie, trafic, sociologie, etc.) traitement d'image et classification 2
Introduction
Petit retour historique (1)
yStanislaw M. Ulam S'intéressait à l'évolution de constructions graphiques engendrées à partir de règles simples Principe -Espace à deux dimensions divisé en " cellules » (sorte de feuille quadrillée) -Chacune des cellules pouvait avoir deux états : allumé ou éteint -Partant d'une configuration donnée, la génération suivante était déterminée en fonction de règles de voisinage -Ex. si une cellule donnée était en contact avec deux cellules allumées elle s'allumait sinon elle s'éteignait Résultats -génération de figures complexes et esthétiques -dans certains cas, ces figures pouvaient se répliquer Questionnements -ces mécanismes récursifs peuvent-ils expliquer la complexité du réel? -Cette complexité n'est elle qu'apparente, les lois fondamentales étant elles- mêmes simples?
Introduction - S. Ulam
La croix de Malte (1)
Introduction - S. Ulam
La croix de Malte (2)
[Greene 1991]
Introduction
Petit retour historique (2)
yJohn von Neumann Travaillait à la conception d'une machine auto-réplicatrice, le kinématon -Capable de produire n'importe quelle machine décrite dans son programme, y compris une copie d'elle-même, à partir de matériaux trouvés dans l'environnement Problèmes - autoréférence de la description -La machine doit avoir une description d'elle-même, donc également une description de la description... -La description est considérée à la fois comme un programme et un composant -La description est interprétée pour construire la nouvelle machine -Elle est ensuite copiée -Similaire au fonctionnement de l'ADN (découvert plus tard) -Conditions physiques de réalisation de la machine
Introduction
Petit retour historique (3)
yLes automates auto-reproducteurs Ulam a suggéré à von Neumann d'utiliser ce qu'il appelait les " espaces cellulaires » (cellular spaces) pour construire sa machine -" En axiomatisant les automates [autoréplicateurs] de cette manière, on (...) s'est résigné à ne pas expliquer comment ces éléments sont constitués de choses réelles, particulièrement comment ces éléments sont constitués de particules élémentaires ou même de molécules (...) on considérera simplement que des particules élémentaires dotées de certaines propriétés existent. La question à laquelle on espère répondre, ou au moins examiner, est : quels principes sont mis en oeuvre dans l'organisation de ces molécules dans les êtres vivants fonctionnels (...) » chaque cellule est un automate à états finis -AC à 2 dimensions avec 200 000 cellules et 29 états -Transport de signal -Opérations logiques -Architecture logique -Un constructeur universel -Une bande de cellules
Introduction - Petit retour historique
Les développements ultérieurs
yDéveloppements dans différentes directions Complément des travaux de Von Neumann sur les automates cellulaires [Burks 70] Extension des travaux de Von Neumann sur les machines auto- reproductrices [Codd 68, Langton 84] Jeux basés sur les automates cellulaires -Jeu de la vie [Conway 70] -Brian's brain [Silverman 84] Etude théorique des propriétés des automates cellulaires Extension du modèle originel (coupled map lattices) Application à la modélisation de systèmes complexes (biologie, physique, sociologie, etc.) 3
Introduction - automates auto-reproducteurs
Automates auto-reproducteurs
yEdgar Codd (1968) Version simplifiée de l'automate de Von Neumann -Seulement 8 états -Toujours un constructeur universel yChristopher Langton (1984) abandonne l'idée d'universalité du réplicateur concevoir un automate cellulaire supportant une structure dont les composants constituent l'information nécessaire à sa propre réplication -structure à la fois elle-même et représentation d'elle-même -utilise huit états et vingt-neuf règles -boucle constituée d'une " membrane » au sein de laquelle circule l'information nécessaire à la réplication.
Introduction - automates auto-reproducteurs
La boucle de Langton
les cellules à l'état 2 forment la membrane les cellules internes contiennent l'information de réplication (sorte d'ADN) Les séquences 7-0 et 4-0 se propagent vers la queue -les séquences 7-0 prolongent la queue -les séquences 7-0 construisent un angle droit vers la gauche une règle de " stérilisation » bloque l'évolution au bout d'un certain nombre de générations et permet la cristallisation des boucles les plus anciennes
Introduction - automates auto-reproducteurs
Un automate robotisé
Introduction - Jeux basés sur les automates cellulaires
Le jeu de la vie [Conway 1970]
yPrésenté à l'origine comme un jeu mathématique grille carrée de cellules chaque cellule est dans l'état " vivante » ou " morte » l'état des cellules est initialisé de manière aléatoire à l'instant t+1, l'état de chaque cellule dépend de son propre état et de l'état de ses 8 voisines à l'instant t -une cellule naît si elle possède trois cellules voisines vivantes (reproduction) -une cellule meurt si elle possède -moins de deux cellules voisines vivantes (mort par isolement) -plus de trois cellules voisines vivantes (mort par sur-population) yRésultat apparition de structures dynamiques émergentes variantes : différentes règles pour l'évolution des cellules
Introduction - Le jeu de la vie
Un exemple simple
Cellules numérotées
(vivantes en jaune, mortes en rouge)
Voisinage de la cellule 12
Nombre de voisins par celluleEtat de l'automate à la génération suivante
Introduction - Le jeu de la vie
Exemple de dynamique
4
Introduction - Le jeu de la vie
Structures particulières
yStructures stables (1-périodiques) yStructures 2-périodiques yPlaneur Introduction - Jeux basés sur les automates cellulaires
Brian's brain [Silverman 84]
3 états au lieu de 2 -excité (blanc) -réfractaire (rouge) -mort (noir) Règles de transition -Les cellules excitées deviennent toujours réfractaires au pas de temps suivant -Les cellules réfractaires meurent toujours au pas de temps suivant -Une cellule morte devient excitée si elle a exactement 2 voisines excitées (parmi ses 8 voisines)
Caractérisation des automates cellulaires
Description informelle
yFramework pour une large classe de modèles discrets à interactions homogènes yCes modèles ont les propriétés suivantes: Discrétisation -spatiale : espace décomposé en une grille de cellules -temporelle : évolution par pas de temps discrets Parallélisme -les cellules évoluent simultanément et de manière indépendante Localité -chaque cellule évolue en fonction de son propre état et de celui d'un ensemble fini de cellules voisines Homogénéité -la topologie des cellules est régulière -la relation de voisinage est uniforme -les règles de transition sont identiques pour toutes les cellules
Caractérisation des automates cellulaires
Exemple simple : Greenberg-Hastings
yModèle de milieu excitable état de repos (0) état d'excitation (2) état réfractaire (ou de rémission) yParamètres de l'automate réseau carré voisinage 4 voisins règles - si pas de voisin - si au - 1 voisin
Caractérisation des automates cellulaires
Evolution avec 1 cellule excitée
Caractérisation des automates cellulaires
Définition formelle
ySoit 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 une fonction de transition : yUn automate cellulaire est défini par le 4-tuple yUne configuration est une fonction qui associe un état à chaque cellule du réseau yLe rôle de la fonction de transition f est de changer en selon la relation : où désigne l'ensemble des voisins de la cellule r 5
Caractérisation des automates cellulaires
Choix de conception
yGéométrie du réseau yVoisinage yConditions aux bords yConditions initiales yEnsemble d'états yRègles de transition Caractérisation des automates cellulaires - Choix de conception
Géométrie du réseau
yréseau régulier = pavage périodique d'un espace
à d dimensions
les cellules remplissent entièrement l'espace à d dimensions le réseau se reproduit à l'identique par des translations dans d directions indépendantes ysolutions à 1, 2, 3 dimensions Caractérisation des automates cellulaires - Choix de conception
Espace à 1 dimension
yUne seule possibilité tableau linéaire de cellules Caractérisation des automates cellulaires - Choix de conception
Espace à 2 dimensions (1)
y3 réseaux réguliers triangulaire carré hexagonal Caractérisation des automates cellulaires - Choix de conception
Espace à 2 dimensions (2)
yréseau triangulaire avantage = petit nombre de voisins (3) désavantage = difficile à représenter et à visualiser yréseau carré avantage = représentation et visualisation simple désavantage = anisotropie yréseau hexagonal avantage = plus faible anisotropie des trois désavantage = difficile à représenter et à visualiser Caractérisation des automates cellulaires - Choix de conception
Mappings réseaux hexagonaux -> carrés (1)
yCisaillement la cellule (i,j) a son centre en -origine dans le coin en haut à gauche -unité = distance entre les cellules la cellule (i,j) est mappée en la relation de voisinage devient : 6 Caractérisation des automates cellulaires - Choix de conception
Mappings réseaux hexagonaux -> carrés (2)
yDécalage des lignes successives en sens opposé la cellule (i,j) est mappée en la relation de voisinage devient : Caractérisation des automates cellulaires - Choix de conception
Mappings réseaux hexagonaux -> carrés (3)
yCisaillement avantage = la relation de voisinage local reste uniforme désavantages = -conditions aux limites plus difficiles à implanter -nécessaire de retransformer la représentation pour la visualisation yDécalage avantages = -conditions aux limites aussi faciles à implanter qu'avec la représentation carrée -visualisation simple désavantage = le voisinage dépend de la parité de j -voisinage et règles inhomogènes Caractérisation des automates cellulaires - Choix de conception Mappings réseaux triangulaires -> carrés (1) ySimilaire au mapping par décalage la cellule (i,j) est mappée en la relation de voisinage devient : Caractérisation des automates cellulaires - Choix de conception Mappings réseaux triangulaires -> carrés (2) yAutre solution : espace d'états étendu pour chaque cellule carrée voisinage de 2 cellules triangulaires = voisinage d'une cellule carrée avantage = voisinage et règles de transition uniformes désavantage = -plus grand espace d'états -plus grande table de transition pour les cellules Caractérisation des automates cellulaires - Choix de conception
Espace à 3 dimensions
yBeaucoup de réseaux possibles plus simple = réseau cubique pas de réseaux suffisamment symétriques pour les pbs d'hydrodynamique yProblèmes spécifiques de visualisation représentation 3D représentation par tranches 2D Caractérisation des automates cellulaires - Choix de conception
Taille et forme du voisinage (1)
yvoisinage = ensemble des cellules avec lesquelles une cellule donnée pourra interagir ydescription du voisinage = ensemble des cellules qui font partie du voisinage de la cellule (i,j) 7 Caractérisation des automates cellulaires - Choix de conception
Taille et forme du voisinage (2)
yvoisinage de von Neumann yvoisinage de Moore yvoisinage de von Neumann généralisé (rayon r) yvoisinage de Moore généralisé (rayon r) Caractérisation des automates cellulaires - Choix de conception
Conditions aux limites
yDéfinition formelle donnée dans le cadre de réseaux de dimensions infinies raisonnable et nécessaire du point de vue théorique inapplicable en pratique certains problèmes ont des frontières naturelles y3 types de frontières périodique réfléchissante à valeur fixe Caractérisation des automates cellulaires - Choix de conception
Frontière périoique
yExtension périodique du réseau yversion à 1 dimension souvent utilisé car se rapproche le plus d'un réseau de taille infinie yversion à 2 dimensions : tore pas possible d'obtenir une sphère Caractérisation des automates cellulaires - Choix de conception
Frontière réflechissante
yRépétition du réseau à la frontière yversion à 1 dimension adapté lorsque le système à simuler a des frontières yversion à 2 dimensions Caractérisation des automates cellulaires - Choix de conception
Conditions fixes
yValeur fixe donnée aux cellules qui constituent la frontière Caractérisation des automates cellulaires - Choix de conception
Conditions mixtes
yles 3 types de conditions peuvent être combinées les différentes frontières ont des conditions différentes si une frontière a un bord périodique, le bord opposé aura
également les mêmes conditions
une tube long peut être simulé en imposant des conditions périodiques dans une dimension et des conditions réfléchissantes dans l'autre yAutres solutions étendre le réseau quand les structures dans l'AC touchent les bords -pb = certaines structures se développent très rapidement adopter des règles de transition spéciales pour les frontières -pb = potentiellement beaucoup de cas particuliers 8 Caractérisation des automates cellulaires - Choix de conception
Conditions initiales
yLes conditions initiales déterminent souvent l'évolution future de l'automate construction génération aléatoire yConsidérations importantes beaucoup d'automates conservent certaines quantités -propres au modèle : nb de particules, énergie, etc. -particulières au réseau : nb de particules dans une ligne ou une colonne choix de manière à ce que -les 1ères soient vérifiées -les secondes ne soient pas gênantes Caractérisation des automates cellulaires - Choix de conception
Exemple : greenberg-hastings
ysi que des cellules rouges vague qui se propage et disparaît ysi barre rouge au-dessus d'une barre jaune spirale sans fin à chaque extrémité de la barre cas particulier = une cellule rouge à côté d'une cellule jaune -> centre d'émission de vagues périodiques le nombre de spirales est conservé! Caractérisation des automates cellulaires - Choix de conception
Espace d'états
yAC = automate à états finis nb d'état fini en général petit -pour pouvoir explorer systématiquement tous les ACs -pour s états et n voisins, le nb d'ACs est -pour pouvoir spécifier les règles de transition explicitement et les stocker dans une table (de taille ) grand nombre d'état intéressant pour augmenter la précision -mais on pourra préférer une modélisation par équations aux dérivées partielles si grande précision souhaitée -ACs adaptés pour systèmes avec fluctuations, où les interactions locales sont importantes Caractérisation des automates cellulaires - Choix de conception
Généralisation de greenberg-hastings
yn états différents possibles yrègle de transition: yPériode réfractaire plus grande Caractérisation des automates cellulaires - Choix de conception
Extension = Coupled-map lattices
yEspace d'états continu au lieu d'être discret Caractérisation des automates cellulaires - Choix de conception
Etats à plusieurs variables
yl'espace d'état S est le produit en croix des espaces de chacune des variables ymédium excitable caractérisé par variable d'excitation u -u=1 -> excité -u=0 -> au repos variable de phase v -u=1 -> v est le temps pendant lequel la cellule est excitée -u=0 -> v est le temps avant que la cellule soit à nouveau excitable 9 Caractérisation des automates cellulaires - Choix de conception
Règles de transition
yl'aspect le plus important des ACs yconditionné par la géométriequotesdbs_dbs46.pdfusesText_46
[PDF] Comment construire un automate ? - Aix - Marseille