comment la théorie cellulaire a été construite ?

Description

À gauche, une règle locale simple : une cellule passe d’un état (i) au suivant (i+1) dans le cycle d’états dès que i+1 est présent dans au moins 3 des 8 cellules voisines. À droite, le résultat (complexe) de l’application répétée de cette règle sur une grille de cellules. Ce type d’automates cellulaires a été découvert par D. Griffeath.
Un automate cellulaire consiste en une grille régulière de « cellules » contenant chacune un « état » choisi parmi un ensemble fini et qui peut évoluer au cours du temps. L’état d’une cellule au temps t+1 est fonction de l’état au temps t d’un nombre fini de cellules appelé son « voisinage ». À chaque nouvelle unité de temps, les mêmes règles sont appliquées simultanément à toutes les cellules de la grille, produisant une nouvelle « génération » de cellules dépendant entièrement de la génération précédente.
Étudiés en mathématiques et en informatique théorique, les automates cellulaires sont à la fois un modèle de système dynamique discret et un modèle de calcul. Le modèle des automates cellulaires est remarquable par l’écart entre la simplicité de sa définition et la complexité que peuvent atteindre certains comportements macroscopiques : l’évolution dans le temps de l’ensemble des cellules ne se réduit pas (simplement) à la règle locale qui définit le système. À ce titre il constitue un des modèles standards dans l’étude des systèmes complexes.
Exemples[|]
Les automates cellulaires les plus simples[|]
L’automate cellulaire non trivial le plus simple que l’on puisse concevoir consiste en une grille unidimensionnelle de cellules ne pouvant prendre que deux états (« 0 » ou « 1 »), avec un voisinage constitué, pour chaque cellule, d’elle-même et des deux cellules qui lui sont adjacentes.
Chacune des cellules pouvant prendre deux états, il existe 23 = 8 configurations (ou motifs) possibles d’un tel voisinage. Pour que l’automate cellulaire fonctionne, il faut définir quel doit être l’état, à la génération suivante, d’une cellule pour chacun de ces motifs. Il y a 28 = 256 façons différentes de s’y prendre, soit donc 256 automates cellulaires différents de ce type.
Les automates de cette famille sont dits « élémentaires ». On les désigne souvent par un entier entre 0 et 255 dont la représentation binaire est la suite des états pris par l’automate sur les motifs successifs 111, 110, 101, etc.
À titre d’exemple, considérons l’automate cellulaire défini par la table suivante, qui donne la règle d’évolution :
Motif initial (t) 111 110 101 100 011 010 001 000
Valeur suivante de la cellule centrale (t+1) 0 0 0 1 1 1 1 0
Cela signifie que si par exemple, à un temps t donné, une cellule est à l’état « 1 », sa voisine de gauche à l’état « 1 » et sa voisine de droite à l’état « 0 » (colonne 2 du tableau), au temps t+1 elle sera à l’état « 0 ».
Si l’on part d’une grille initiale où toutes les cellules sont à l’état « 0 » sauf une, on aboutit à :
où chaque ligne est le résultat de la ligne précédente.
Par convention cette règle est nommée « règle 30 », car 30 en décimale s’écrit 00011110 en binaire et 00011110 est la deuxième ligne du tableau ci-dessus, décrivant la règle d’évolution.
Le jeu de la vie[|]
Quelques étapes d’évolution du jeu de la vie à partir d’une configuration initiale choisie au hasard.
Le « jeu de la vie » est un automate cellulaire bidimensionnel où chaque cellule peut prendre deux valeurs (« 0 » ou « 1 », mais on parle plutôt de « vivante » ou « morte ») et où son état futur est déterminé par son état actuel et par le nombre de cellules vivantes parmi les huit qui l’entourent :
Si la cellule est vivante et entourée par deux ou trois cellules vivantes, elle reste en vie à la génération suivante, sinon elle meurt.
Si la cellule est morte et entourée par exactement trois cellules vivantes, elle naît à la génération suivante.
En apparence simples, ces règles font émerger une forte complexité.
On peut sur le même principe imaginer un grand nombre de règles en faisant varier les seuils de naissance ou de survie, ou en ajoutant des états supplémentaires, etc. Parmi ces variations, on peut citer :
Day & Night
HighLife
Immigration
QuadLife
Certains ne prennent en compte pour déterminer les changements d’état d’une cellule que les voisins immédiats de la case considérée, mais d’autres prennent également en compte l’état des cellules voisines dans un rayon de deux cases, voire plus. D’autres attribuent aussi un poids plus important à certaines cases du voisinages qu’à d’autres (WeightedLife).
Tous les autres…[|]
Les règles possibles pour définir un automate cellulaire sont très nombreuses, même avec un petit nombre d’états et un petit voisinage. En effet si le nombre d’états est q et le nombre de voisins est v, il y a
règles. Ceci donne :
2 états 3 états 4 états 5 états
2 voisins 16 19 683 4 294 967 296
3 voisins 256 7 625 597 484 987
4 voisins 65 536
5 voisins 4 294 967 296
6 voisins
Le modèle des automates cellulaire offre donc un terrain d’exploration immense. Il n’est pas difficile de programmer un simulateur d’automates cellulaires et la Toile regorge de réalisations plus ou moins abouties. Le site de Mirek Wojtowicz propose par exemple un logiciel de simulation et une galerie d’exemples très riche : Mirek’s Cellebration []. Un autre exemple de simulateur intéressant est Golly []. Il est dédié principalement au jeu de la vie et optimisé pour cet automate en utilisant notamment des quadtree combinés avec du hachage.
Histoire[|]
Dans les années 1940, Stanislaw Ulam étudiait la croissance des cristaux au laboratoire national de Los Alamos, en la modélisant sur une grille. Dans le même temps, John von Neumann, collègue d’Ulam à Los Alamos, travaillait sur des systèmes auto-réplicatifs et rencontrait des difficultés pour expliciter son modèle initial d’un robot qui se copierait tout seul à partir d’un ensemble de pièces détachées. Ulam lui suggéra de s’inspirer de ses travaux, ce qui conduisit von Neumann à concevoir un modèle mathématique abstrait pour son problème. Le résultat fut le « copieur et constructeur universel » (universal copier and constructor en anglais), le premier automate cellulaire : il était basé sur une grille à deux dimensions où chaque cellule pouvait prendre 29 états. Von Neumann y construisit un motif particulier et démontra qu’il pouvait produire sans fin des copies de lui-même1.
En 1969, Gustav Arnold Hedlund publie Endomorphisms and Automorphisms of the Shift Dynamical System, une monographie de 60 pages environ qui synthétise 10 ans de recherche d’une communauté travaillant dans le domaine de la dynamique symbolique (une branche de l’étude des systèmes dynamiques en mathématiques, fondée notamment par M. Morse et G. A. Hedlund2). C’est cette publication qui pose les bases mathématiques de l’étude des automates cellulaires comme des systèmes dynamiques particuliers.
En 1969 également, Konrad Zuse publia Rechnender Raum (« Quand l’espace calcule »)3 où il émettait l’hypothèse que les lois physiques étaient discrètes et que l’Univers était le résultat d’un gigantesque automate cellulaire.
Dans les années 1970, un automate cellulaire à deux dimensions et deux états nommé le « jeu de la vie », inventé par John Conway, connut un grand succès, particulièrement parmi la communauté informatique naissante. Il fut popularisé par Martin Gardner dans un article du Scientific American4.
En 1983, Stephen Wolfram publia la première d’une série de publications où il analysait de façon systématique un type d’automates cellulaires très simples5. La complexité de leur comportement, induit par des règles élémentaires, le poussa à conjecturer que des mécanismes similaires pourraient expliciter des phénomènes physiques complexes, idées qu’il développa dans son livre A New Kind of Science paru en 20026.
Théorie des automates cellulaires[|]
Si la popularité du modèle des automates cellulaires vient en grande partie d’une approche expérimentale, il fut dès l’origine abordé comme un objet mathématique par Von Neumann1. La plupart des travaux formels sur les automates cellulaires utilisent la définition ci-dessous bien que le modèle admette de nombreuses généralisations et variations intéressantes.
Une définition formelle[|]
Un automate cellulaire est un
-uplet
où :
est la dimension de l’automate, son réseau est alors
, l’espace discret de dimension
;
, un ensemble fini, est son alphabet ;
est son voisinage (un sous-ensemble fini du réseau) ;
est sa règle locale de transition et
est l’arité de l’automate.
On appelle alors configuration l’attribution d’un état à chaque cellule du réseau : une configuration est un élément de
, c’est-à-dire une fonction de
dans
.
À cette description finie et locale, on associe la fonction globale d’évolution de l’automate,
, qui agit sur les configurations et qui est définie par
pour toute configuration
(où
).
Systèmes dynamiques[|]
Les automates cellulaires ont été étudiés comme des systèmes dynamiques dès les années 1960 avec les travaux de G. A. Hedlund. Lorsque la dimension
et l’alphabet
sont fixés, on peut munir l’espace des configurations de la métrique de Cantor par la distance
définie par
L’ensemble des automates cellulaires d’alphabet
et de dimension
est alors caractérisé par le théorème de Curtis-Hedlund-Lyondon7 :
est la fonction globale d’un tel automate cellulaire si et seulement si c’est une fonction continue de
qui commute avec les fonctions de décalage (à toute position
dans le réseau de cellules correspond une fonction de décalage
).
À partir de là, les automates cellulaires peuvent être étudiés avec tout l’outillage de la théorie des systèmes dynamiques classique, de la théorie du chaos et de la théorie ergodique, lorsque l’on munit l’espace des configurations d’une mesure.
Cette branche de la théorie des automates cellulaires reste largement ouverte et fait toujours l’objet de recherches (voir ici [] pour un exemple de question importante non résolue à ce jour).
Modèle de calcul et constructions algorithmiques[|]
Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?
l’algorithme de P. C. Fischer pour reconnaître les nombres premiers
le problème de la ligne de fusiliers : une solution ayant 6 états seulement a été publiée par Jacques Mazoyer, il a également prouvé qu’il n’y avait pas de solution à 4 états.
Automates cellulaires universels[|]
On peut considérer les automates cellulaires aussi bien comme des systèmes dynamiques discrets que comme des systèmes de calcul. Ainsi, chaque automate est capable de réaliser certains calculs ou d’exhiber certains comportements dynamiques. Que l’on adopte l’un ou l’autre des points de vue, on peut se poser une même question : existe-t-il un automate capable de faire tout ce que peuvent faire les automates cellulaires ? Un tel automate est alors dit universel.
La notion d’universalité correspond à une idée très simple et très générale, mais il faut prendre garde au fait que selon le sens que l’on met derrière l’expression « capable de faire » les automates universels ne sont pas les mêmes. On peut distinguer deux types de notions d’universalité pour les automates cellulaires : l’universalité Turing qui est associée à la capacité de calcul et l’universalité intrinsèque qui est associée à la capacité de produire certains comportements dynamiques.
Le fait remarquable est que pour chacune de ces notions il existe des automates universels. Il faut noter également que la notion d’universalité intrinsèque est plus forte que l’universalité Turing : en effet, sans rentrer dans les détails, un automate capable de simuler tous les automates peut en particulier simuler un automate Turing-universel et donc effectuer tous les calculs Turing. En revanche, il existe des automates cellulaires Turing-universels qui ne sont pas intrinsèquement universels.
Universalité Turing[|]
L’universalité Turing est une adaptation aux automates cellulaires de l’universalité pour le calcul. On peut définir cette notion comme la capacité d’un automate à simuler une machine de Turing universelle. Cette possibilité de simulation d’une machine de Turing par un automate cellulaire est très simple et était connue dès les travaux de John von Neumann. Il existe plusieurs manières de la formaliser et ce qui suit est l’une des plus simples. Si
est une machine de Turing fonctionnant avec un alphabet de ruban
et un ensemble d’état
, on peut définir un automate cellulaire
capable de simuler
:
l’alphabet de
est
: ainsi chaque cellule de
possède un état
formé d’une composante
qui correspond au contenu du ruban et d’une composante
qui correspond à l’absence (
) ou la présence (
) d’une tête de Turing à cette position et qui donne le cas échéant son état ;
son voisinage est
le comportement de
consiste à reproduire les mouvements de la tête de Turing sur la première composante et les modifications du ruban sur la deuxième composante exactement comme le ferait
:
On rencontre souvent une acception plus générale (mais plus informelle) de l’universalité Turing : un automate cellulaire est Turing-universel s’il est capable de simuler un système de calcul Turing-complet. Le terme simuler est rarement formalisé dans un cadre général. Le point important est que la transformation des entrées/sorties du système simulé vers des entrées/sorties du simulateur reste simple : sans cette condition, on obtient une notion dénuée d’intérêt car des automates qui ne font rien (l’identité par exemple) deviennent universels grâce à des transformations d’entrées/sorties qui font tout le calcul à leur place.
Universalité intrinsèque[|]
Un automate cellulaire intrinsèquement universel est un automate capable de simuler pas à pas le comportement de n’importe quel automate cellulaire de même dimension. Plus précisément, l’idée de simulation pas à pas repose sur les principes suivants :
dans l’automate simulateur, on forme des groupes de cellules voisines, tous identiques, qui recouvrent régulièrement le réseau de cellules ; chaque groupe dans le simulateur représente une cellule simple de l’automate simulé ;
à chaque état de l’automate simulé correspond une configuration d’états de groupe dans l’automate simulateur ;
l’automate simulateur peut utiliser plusieurs étapes pour simuler une étape de l’automate simulé.
Ainsi, par exemple, le jeu de la vie est capable de simuler pas à pas l’automate
à 2 états (noir et rouge) qui effectue un simple décalage des états vers le sud-est :
les groupes de cellules dans le jeu de la vie sont des carrés de
cellules ;
l’état noir de
correspond à un groupe de cellules toutes mortes et l’état rouge correspond à un planeur entouré de cellules mortes et ajusté dans une certaine position au sein du groupe ;
une étape de
est simulée toutes les 16 étapes du jeu de la vie.
Ainsi, pour simuler le comportement de
à partir d’une certaine configuration initiale, il suffit de fabriquer une configuration du jeu de la vie où chaque groupe est soit rempli de cellules mortes, soit d’un planeur selon l’état de la cellule qui lui correspond dans
.
Il est remarquable qu’avec ce principe de simulation très simple certains automates soient capables de simuler n’importe quel automate cellulaire à partir de n’importe quelle configuration : c’est le cas du jeu de la vie comme expliqué dans la section suivante. Bien entendu, pour simuler des automates avec de plus en plus d’états, un automate intrinsèquement universel utilise des groupes de cellules de plus en plus grands. En effet, avec un type de groupe de cellules fixés, il n’existe qu’un nombre fini de simulations possibles. Ainsi, quand on observe une évolution du jeu de la vie sur un écran (aussi grand soit il), on ne voit pas tous les comportements que le jeu de la vie est capable de simuler ; pourtant cet automate est capable de produire tous les comportements d’automate cellulaire.
Exemples[|]
Un exemple d’évolution de l’automate cellulaire élémentaire 110 utilisé dans la preuve d’universalité de M. Cook (le temps progresse de haut en bas).
Historiquement, le premier automate cellulaire construit ayant une propriété d’universalité (Turing en l’occurrence) est le constructeur universel de John von Neumann : il s’agit d’un automate de dimension 2 à 29 états qui est en outre capable de s’auto-répliquer.
Concernant la notion d’universalité intrinsèque, il faut attendre les années 1970 avec les travaux de E. R. Banks8 qui proposa un automate cellulaire de dimension 2 à 2 états et 5 voisins. Il propose également un automate de dimension 1 intrinsèquement universel avec 5 états mais dont le voisinage est énorme.
L’exemple le plus célèbre d’automate universel est certainement le jeu de la vie. Il fut prouvé Turing-universel dans l’ouvrage Winning Ways for your Mathematical Plays. La preuve consiste à construire des morceaux de configurations qui peuvent être assemblés et qui correspondent à tous les composants nécessaires à la fabrication de circuits logiques (fils, croisements de fils, duplication, portes logiques, etc.). On peut trouver une construction complète d’une machine de Turing dans le jeu de la vie sur le site de Paul Rendell []. À partir des mêmes idées, le jeu de la vie fut plus récemment prouvé intrinsèquement universel9.
Pour la dimension 1, une percée concernant l’universalité Turing a eu lieu récemment : M. Cook a prouvé que l’automate cellulaire élémentaire numéro 110 était Turing-universel. Il a présenté ses idées dès 1998 à la conférence CA98 [], mais ce résultat n’a été (partiellement) diffusé par écrit qu’en 2002 à travers A New Kind of Science6 de S. Wolfram. En effet, M. Cook était employé par Wolfram Research pour travailler sur le livre A New Kind of Science et ses travaux ne furent pas publiés dans les actes de CA98 à la suite d’une action en justice fondée sur un accord de non-divulgation. La preuve complète du résultat de M. Cook a finalement été publiée dans une revue scientifique en 200410.
En revanche, on ne sait toujours pas aujourd’hui si l’automate 110 est intrinsèquement universel ou pas. Le plus petit automate de dimension 1 avec un voisinage de 3 cellules qui ait été prouvé intrinsèquement universel à ce jour comporte 4 états11,12.
Complexité[|]
De façon générale, il est extrêmement difficile de déterminer le comportement global d’un automate cellulaire en examinant sa règle locale de transition. Ceci se traduit par des résultats d’indécidabilité touchant les propriétés les plus simples. Dans ce domaine on peut citer les travaux de Jarkko Kari qui, en utilisant de façon astucieuse les résultats déjà connus sur les pavages, a montré que les problèmes suivants étaient indécidables :
savoir si un automate cellulaire est nilpotent (i.e. toutes les configurations mènent au bout d’un temps fini vers une même configuration uniforme)13,
savoir si un automate cellulaire de dimension
peut atteindre toutes les configurations après une étape (problème de la surjectivité)14,
savoir si un automate cellulaire de dimension
est réversible14.
Le fait que des automates cellulaires puissent simuler n’importe quelle machine de Turing amène aussi des problèmes indécidables d’une autre nature. Par exemple, pour certains automates cellulaires, les problèmes suivants sont également indécidables :
savoir si, étant donné un motif
présent initialement au centre, un motif
va apparaître au centre au bout d’un certain temps,
savoir si un motif
peut apparaître arbitrairement tard dans l’évolution ou, au contraire, s’il existe un temps au-delà duquel
n’apparaît plus quelle que soit la configuration de départ.
Classes remarquables d’automates cellulaires[|]
Comme expliqué plus haut, les règles locales d’automates cellulaires sont trop nombreuses pour une étude exhaustive et la prédiction du comportement en fonction de la règle local est un problème très difficile en général. C’est pourquoi l’étude des automates cellulaires s’est souvent restreinte à des familles particulières, soit parce qu’elles se prêtent plus facilement à l’analyse, soit parce qu’elles correspondent à une propriété intéressante.
Automates réversibles[|]
Un automate cellulaire
est réversible s’il existe un automate cellulaire
tel que les deux fonctions globales d’évolution
et
sont inverses l’une de l’autre :
est la fonction identité. Intuitivement,
« remonte le temps » de l’évolution de
et, inversement,
« remonte le temps » de l’évolution de
. Par le théorème de Hedlund, on peut caractériser les automates cellulaires réversibles comme ceux dont la fonction globale est bijective.
Cette classe a été très étudiée, notamment car elle fournit un modèle qui se rapproche du monde physique réel, supposé réversible à l’échelle microscopique (voir à ce sujet l’article sur la réversibilité et l’irréversibilité en thermodynamique). T. Toffoli et N. Margolus15 sont parmi les premiers à s’être intéressés spécifiquement aux automates cellulaires réversibles. L’intérêt réside aussi dans la recherche de systèmes de calcul réversibles supposés consommer moins d’énergie d’après le principe de Landauer. Il est aujourd’hui établi que certains automates cellulaires réversibles sont Turing universels (travaux de Kenichi Morita).
Reconnaissance[|]
Il est algorithmiquement impossible de distinguer les automates cellulaires réversibles de ceux qui ne le sont pas lorsque la dimension est supérieure à 2. En revanche, en dimension 1, il existe un algorithme très efficace.
Une autre façon de présenter cette différence entre la dimension 1 et les dimensions supérieures est la suivante : la taille du voisinage de l’inverse d’un automate
ne peut pas être borné récursivement en fonction de la taille du voisinage de
lorsque la dimension est 2 ou plus, alors qu’elle est bornée polynomialement en dimension 1 (un résultat récent16 montre même que la borne est linéaire).
Exemples[|]
Technique du « second ordre » appliquée à l’automate cellulaire élémentaire 54 (le temps progresse de bas en haut).
Il est facile de construire des automates cellulaires réversibles. Pour cela, plusieurs formes de constructions existent.
la technique dite « du second ordre » : elle consiste à mélanger par une opération de OU exclusif bit à bit les informations du nouvel état d’une cellule avec son état passé. A priori, un automate cellulaire calcule la génération
en fonction de la génération
uniquement : la technique du second ordre paraît donc être une entorse au modèle. On peut contourner ce problème en fusionnant deux générations en une seule grâce à l’utilisation de plus d’états.
la technique des permutations par blocs alternées : elle a été proposée dans une version simple par Norman Margolus. Elle consiste à découper le réseau de cellules en blocs de cellules, à appliquer une permutation des états des cellules dans chaque bloc indépendamment, puis à décaler ce partitionnement et à appliquer une nouvelle permutation.
la technique du partitionnement : elle a été proposée par K. Morita et M. Harao17. Elle consiste à appliquer une transformation purement locale sur chaque cellule, puis, en utilisant un partitionnement de l’ensemble d’états, à envoyer à chaque cellule voisine une certaine composante de cet état. Avec cette construction, on a la garantie que l’automate cellulaire est réversible si la transformation locale appliquée est elle-même réversible.
Automates linéaires[|]
Les automates cellulaires sont en général des systèmes dynamiques non linéaires, ce qui rend leur étude par des outils classiques difficile. Mais cette vérité générale n’empêche pas certains automates cellulaires de posséder une forme plus ou moins stricte de linéarité.
Définition[|]
Quelques étapes d’évolution sur une configuration périodique d’un automate cellulaire additif à 5 états, en dimension 2, et avec tous les
égaux à 1.
Formellement, un automate d’alphabet
est dit linéaire si l’on peut munir
d’une loi de groupe
telle que :
Dans ce cas, si l’on étend
à une opération agissant cellule à cellule sur l’espace des configurations, la fonction globale
associée à l’automate est bien une fonction linéaire.
La linéarité facilite considérablement l’étude de la dynamique des automates. Ainsi, il suffit de connaître la dynamique d’un automate linéaire sur une « base » de l’espace de ses configurations pour en déduire par linéarité son comportement sur tout l’espace. On peut choisir pour une telle base l’ensemble (fini) des configurations partout égales à
(neutre de
) sauf éventuellement en la cellule centrale.
Automates additifs[|]
L’une des familles les plus étudiées d’automates linéaires est celle des automates dits additifs, introduite par O. Martin, A. Odlyzko et S. Wolfram dans18. Ces automates sont définis de la façon suivante :
,
où les coefficients
sont fixés et caractérisent l’automate.
L’exemple typique est celui où tous les coefficients
sont égaux à 1 : la règle locale consiste alors à faire la somme modulo n de toutes les cellules du voisinage. Ainsi, en dimension 1, l’automate cellulaire élémentaire 90 est additif : sa fonction de transition consiste à faire la somme modulo 2 des états des deux voisines de la cellule. Il suffit de connaître le comportement de cet automate sur la configuration
partout égale à 0 sauf au centre où elle vaut 1 pour en déduire son comportement général par le principe de superposition :
L’automate élémentaire 102 est également additif. Son action sur la configuration
produit un triangle de Pascal modulo 2 (qui donne aussi une approximation du triangle de Sierpinski). Ainsi, partant de
, la cellule
après
étapes se trouve dans l’état :
si
ou
,
dans les autres cas.
Par superposition, on en déduit une expression directe de l’état de la cellule centrale après
étape partant d’une configuration quelconque
:
.
Automates totalistiques[|]
Dans un automate cellulaire totalistique, l’état ultérieur d’une cellule ne dépend que de la somme des états de ses voisines ; c’est le cas du jeu de la vie où une cellule vivante le reste si deux ou trois de ses voisines sont vivantes, et une cellule morte naît si trois de ses voisines sont vivantes. Un automate totalistique ne prend donc pas en compte la position des voisines d’une cellule par rapport à celle-ci.
Automate sommatif (totalistique) tridimensionnel défini sur un réseau dodécaédrique rhombique
Si un automate cellulaire n’est pas totalistique, en plus de leur état propre, la position des voisines d’une cellule influe sur son état ultérieur. Par exemple, pour un automate cellulaire à une dimension, on peut faire une différence entre la cellule voisine de gauche et la voisine de droite.
Automates conservatifs[|]
Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?
Le problème des classifications[|]
Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?
Classification de Wolfram[|]
Cette classification fut introduite par Stephen Wolfram en 1983 dans son article Universality and complexity in cellular automata et représente la première tentative pour classifier les automates cellulaires d’après leur évolution à partir de configurations initiales aléatoires. Il proposa quatre classes de comportement :
Classe I : presque toute configuration initiale conduit à un état homogène. Il est impossible de construire des motifs stables périodiques.
Classe II : des structures stables ou périodiques émergent, mais rien de plus.
Classe III : comportement chaotique avec des motifs apériodiques. À long terme les fréquences d’apparitions des différents motifs se stabilisent.
Classe IV : « émergence » de structures complexes capables d’osciller, de se mouvoir, voire de persévérer plus ou moins dans leur auto-organisation malgré des perturbations structurelles. Le jeu de la Vie en est un parfait exemple.
Classification d’Eppstein[|]
Une des critiques de la classification de Wolfram réside dans son impossibilité à dire si un automate cellulaire donné est Turing-universel ; d’ailleurs, des automates cellulaires universels ont été trouvés pour chacune des classes proposées par Wolfram. Cet état de fait provient de ce que Wolfram n’a considéré que des conditions initiales aléatoires, mais pas des structures particulières créées spécifiquement pour l’occasion. En particulier, la transmission d’information, par exemple par l’intermédiaire de vaisseaux, n’est pas prise en compte.
David Eppstein a proposé une alternative à cette classification :
Expansion obligatoire des motifs : n’importe quel motif initial s’étend indéfiniment dans toutes les directions. Aucun vaisseau ne peut exister.
Expansion impossible : un motif ne peut jamais s’étendre au-delà de ses limites initiales. Aucun vaisseau ne peut exister.
Contraction impossible : un motif ne s’étend pas forcément indéfiniment, mais il ne peut jamais réduire en deçà de ses limites initiales. Aucun vaisseau ne peut exister.
Expansion et contraction possibles : seuls ces cas peuvent contenir des vaisseaux.
A priori, seuls les derniers cas permettent l’universalité, même si tous les automates cellulaires qui y répondent ne le sont pas. En revanche, il n’a pas été non plus démontré qu’il est impossible de construire des structures universelles pour les autres cas, d’autres structures que les vaisseaux pouvant également transmettre des informations.
Généralisation et variations sur le modèle[|]
Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?
Réseau de cellules[|]
Dans la définition formelle ci-dessus, le réseau est systématiquement de la forme
. On peut généraliser sans problème à d’autres graphes infinis réguliers.
Asynchronisme[|]
La première classification d’un automate cellulaire concerne la façon dont les règles sont appliquées sur la grille :
Pour les automates cellulaires à traitement parallèle, l’état de toutes les cellules est mis à jour à chaque tour.
Pour les automates cellulaires à traitement série, seul l’état d’une ou plusieurs cellules est mis à jour.
Autres[|]
Il est possible de généraliser le concept d’automate cellulaire, par exemple :
en modifiant le voisinage au cours du temps
Les automates continus fonctionnent sur le même principe que les automates cellulaires, mais utilisent des grilles ou des états continus (le plus souvent entre 0 et 1). De tels automates peuvent simuler par exemple la diffusion d’un liquide.
Automates cellulaires probabilistes[|]
Un automate cellulaire probabiliste est un automate cellulaire déterministe où la règle locale f est remplacée par une dynamique locale aléatoire, c’est-à-dire une matrice de transition qui indique en fonction de l’état où l’on est avec quelle probabilité on peut se retrouver dans un état suivant.
Il est possible de répéter un automate cellulaire sur l’image trouvée à la suite d’une application du même automate cellulaire probabiliste. On peut itérer cela une infinité de fois. La recherche de loi invariante où de l’ergodicité (convergence) de la loi de départ sont des sujets sur lesquels des recherches sont faites actuellement.
Il est conjecturé (mais pas prouvé) que les automates cellulaires probabilistes sont tous ergodiques si le cardinal de l’alphabet de départ est égale à 2 et il est prouvé que cela est faux pour tous alphabet de très grande taille. Cela a été démontré par Gàcs en 2001 pour les automates cellulaires probabilistes avec un alphabet de cardinal de taille environ
19.
La question reste ouverte et n’est pas conjecturée pour les automates cellulaires probabilistes avec un alphabet de cardinal de taille plus petite.
Dans la recherche mathématique, les automates cellulaires probabilistes sont utilisés aussi pour conjecturer certaines lois sur les percolations de dernier passage généralisées.
Modélisation et applications[|]
On peut considérer le modèle des automates cellulaires comme le pendant discret des équations aux dérivées partielles. Ainsi, à chaque fois qu’un phénomène physique est décrit par des équations aux dérivées partielles, on peut en proposer une (des) discrétisation(s) sous forme d’automate cellulaire20. Il reste à déterminer dans quelle mesure le modèle cellulaire est pertinent pour expliquer et/ou prédire le phénomène étudié. Rien n’est garanti dans le cas général et caractériser la dynamique globale du modèle cellulaire en fonction de sa définition locale peut être au moins aussi difficile que de résoudre le système d’équations aux dérivées partielles.
En revanche, l’automate cellulaire peut être simulé facilement par ordinateur ! Ainsi, en analyse numérique, de nombreuses méthodes consistent à discrétiser certaines grandeurs (espace, temps, valeur) pour effectuer des simulations numériques (voir la méthode des éléments finis, des volumes finis ou des différences finies).
Modélisation en physique[|]
Automate cellulaire appliqué aux feux de forêts : en rouge, les arbres qui brûlent, en vert les arbres intacts et en gris, les cendres. Ce programme utilise le voisinage de von Neumann (les arbres qui se situent à côté d’un arbre en feu brûlent à leur tour).
Parmi les modèles qui ont été très étudiés21, on peut citer les automates de gaz sur réseau (lattice gaz automata en anglais) qui modélisent des particules de gaz régies par une version discrète des équations de Navier Stokes.
La première formulation de ce modèle, connu sous le nom de HPP, (il s’agit d’un automate cellulaire de dimension
) est due à J. Hardy, Y. Pomeau et O. Pazzis dans les années 1970. Une seconde formulation, FHP, a été proposée dans les années 1980 par U. Frisch, B. Hasslacher et Y. Pomeau : elle améliore la précédente en remplaçant le réseau de cellule
par un réseau hexagonal.
Les automates cellulaires trouvent aussi une application dans la modélisation et la simulation des feux de forêts22. La première utilisation est due à Kourtz et O’Regan23 en 1971. Ces modèles permettent facilement d’observer la propagation du feu en fonction de plusieurs paramètres comme la direction et la force du vent ou encore l’humidité.
Phénomènes biologiques[|]
Les motifs de certains coquillages, comme les cônes et les cymbiolae, sont générés par des mécanismes s’apparentant au modèle des automates cellulaires. Les cellules responsables de la pigmentation sont situées sur une bande étroite le long de la bouche du coquillage. Chaque cellule sécrète des pigments selon la sécrétion (ou l’absence de sécrétion) de ses voisines et l’ensemble des cellules produit le motif de la coquille au fur et à mesure de sa croissance. Par exemple, l’espèce Conus textile présente un motif ressemblant à la règle 30 décrite plus haut.
Conus textile présentant sur sa coquille un motif similaire à certains automates cellulaires
Trafic routier[|]
Automate cellulaire élémentaire 184 : en noir les portions d’autoroute vides, en bleu celles où une voiture est présente. Les zones qui semblent être d’un bleu plus foncé sont en fait formées d’une alternance de noir et de bleu et correspondent à une circulation fluide de densité maximale.
K. Nagel et M. Schreckenberg ont proposé dans les années 1990 un modèle de trafic autoroutier basé sur un automate cellulaire de dimension 1 :
les cellules de l’automate représentent différentes portions de l’autoroute ;
une cellule est soit dans l’état vide, soit dans l’un des états
, où
représentent la présence d’un véhicule roulant à la vitesse
(
représente l’arrêt) ;
le fonctionnement est schématiquement le suivant :
chaque véhicule accélère d’un cran (passe de
à
) en limitant sa vitesse afin de ne pas parcourir en 1 unité de temps plus que la distance qui le sépare du véhicule devant lui,
la vitesse obtenue est diminuée d’un cran (passage de
à
) avec une certaine probabilité
,
chaque véhicule avance d’une distance proportionnelle à sa vitesse ainsi déterminée.
Ce modèle correspond à un automate cellulaire si la perturbation aléatoire est absente (
). Si de plus
(un véhicule est soit à l’arrêt, soit à sa vitesse maximum), le modèle se réduit à l’automate cellulaire élémentaire 184 : les cellules peuvent prendre uniquement deux valeurs correspondant à vide ou présence d’un véhicule.
Les automates cellulaires comme des modèles physiques[|]
Plusieurs scientifiques, tels qu’Andrew Ilachinski24, ont émis l’hypothèse selon laquelle l’univers pourrait être considéré comme un automate cellulaire24. Ilachinski la justifie par l’observation suivante : « Considérons l’évolution de la règle 110 : s’il s’agissait d’une sorte de « loi alternative de la physique », quelle serait la description rationnelle des motifs observés ? Un observateur ignorant la règle appliquée pour générer les images pourrait supposer le mouvement d’objets discrets25. » Le physicien James Crutchfield a émis une théorie mathématique rigoureuse basée sur ce principe, prouvant l’émergence statistique de « particules » dans les automates cellulaires26. Par extension, l’univers, qui peut être décrit comme un ensemble de particules, pourrait ainsi être considéré comme un automate cellulaire.
En octobre 2014, une théorie unifiée basée sur cette hypothèse reste encore à être formulée ; néanmoins, les recherches en ce sens ont aidé certains chercheurs à définir l’univers comme un système discret :
Marvin Minsky a étudié les interactions entre particules en se basant sur un automate cellulaire en quatre dimensions27 ;
Konrad Zuse a développé une matrice irrégulière permettant l’étude des informations contenues par les particules28 ;
Edward Fredkin a émis l’« hypothèse de la nature bornée », selon laquelle toute quantité physique, y compris l’espace et le temps, serait discrète et finie29 ;
Stephen Wolfram, dans son livre A New Kind of Science, considère les automates cellulaires comme la clef permettant d’expliquer de nombreux sujets, dont la physique6 ;
Gabriele Rossi, Francesco Berto et Jacopo Tagliabue, présentent dans Mathematics of the Models of Reference un univers, basé sur un « dodécaèdre rhombique » et une règle unique, satisfaisant à l’universalité, parfaitement réversible et permettant la formulation d’affirmations qualitatives quant à l’évolution de l’univers30.
Voir aussi[|]
Sur les autres projets Wikimedia :
Automate cellulaire, sur Wikibooks
Articles connexes[|]
Projet:Automate cellulaire
Stephen Wolfram
Théorème de Liouville (système dynamique)
Domaines apparentés[|]
Systèmes dynamiques
Théorie du chaos
Informatique théorique
Systèmes complexes
Émergence
Calcul parallèle
Règles particulières[|]
Boids
Automate cellulaire de Codd
Boucle de Langton
Constructeur universel
Day & Night
Fourmi de Langton
HighLife
Immigration (automate cellulaire)
Jeu de la vie
QuadLife
vie sans mort
Vers de Paterson
Wireworld
Liens externes[|]
Nazim Fatès – Mémoire de DEA en histoire et philosophie des sciences sur les automates cellulaires. []
une bonne page d’entrée pour le jeu de la vie []
(en) Golly, un programme de simulation du jeu de la vie []
(en) Mirek’s celebration, un automate cellulaire général []

Bibliographie[|]
John von Neumann, Arthur W. Burks, Theory of Self-Reproducing Automata, University of Illinois Press (1966)
Konrad Zuse, Rechnender Raum, Schriften zur Datenverarbeitung Band, Friedrich Vieweg & Sohn, Braunschweig (1969)
Martin Gardner, Mathematical Games. The fantastic combinations of John Conway’s new solitaire game « life », Scientific American no 223 (octobre 1970), p. 120-123
Stephen Wolfram, Universality and Complexity in Cellular Automata, Physica D no 10 (janvier 1984), p. 1-35
Stephen Wolfram, A New Kind of Science, Wolfram Media (2002) – (ISBN 1-57955-008-8)
G. A. Hedlund, Endomorphisms and Automorphisms of the Shift Dynamical System (Mathematical Systems Theory, vol. 3, n° 4, 1969)
J. Kari, The Nilpotency Problem of One-dimensional Cellular Automata, SIAM Journal on Computing 21 (1992), pp. 571-586
J. Kari, Reversibility and Surjectivity Problems of Cellular Automata, Journal of Computer and System Sciences 48, 1 (1994), pp. 149-182
T. Toffoli et N. Margolus, Invertible Cellular Automata: a review, Physica D, 45 (1990), pp. 229–253
E. Czeizler et J. Kari, A tight linear bound on the neighborhood of inverse cellular automata, ICALP 2005, Lecture Notes in computer Science 3580, pp. 410–420, Springer-Verlag
O. Martin, A. Odlyzko et S. Wolfram, Algebraic Properties of Cellular Automata, Communications in Mathematical Physics (1984), no 93, p. 219
M. Morse et G. A. Hedlund, Symbolic Dynamics (American journal of Mathematics, vol. 60, 1938)
E. R. Banks, Universality in cellular automata, Eleventh Annual Symposium on Switching and Automata Theory (Santa Monica, California, 1970), IEEE
B. Durand et Z. Róka, The game of life :universality revisited dans Cellular Automata : a Parallel Model, vol. 460 of Mathematics and its Applications. Kluwer Academic Publishers, 1999, pp. 51-74
M. Cook, Universality in Elementary Cellular Automata, Complex Systems, 15(1), 2004, pp. 1–40.
N. Ollinger, The quest for small universal cellular automata, International Colloquium on Automata, Languages and Programming (2002), Lecture Notes in Computer Science, pp. 318-330.
Notes et références[|]
↑
a et b John von Neumann, Arthur W. Burks, Theory of Self-Reproducing Automata, University of Illinois Press (1966).
↑ M. Morse et G. A. Hedlund, Symbolic Dynamics (American journal of Mathematics, vol. 60, 1938).
↑ Konrad Zuse, Rechnender Raum, Schriften zur Datenverarbeitung Band, Friedrich Vieweg & Sohn, Brunswick (1969).
↑ Martin Gardner, Mathematical Games. The fantastic combinations of John Conway’s new solitaire game « life », Scientific American n°223 (Octobre 1970), p. 120-123.
↑ Stephen Wolfram, Universality and Complexity in Cellular Automata, Physica D no 10 (Janvier 1984), p. 1-35.
↑
a b et c Stephen Wolfram, A New Kind of Science, Wolfram Media (2002) – (ISBN 1-57955-008-8).
↑ G. A. Hedlund, Endomorphisms and Automorphisms of the Shift Dynamical System (Mathematical Systems Theory, vol. 3, n° 4, 1969).
↑ E. R. Banks, Universality in cellular automata, Eleventh Annual Symposium on Switching and Automata Theory (Santa Monica, California, 1970), IEEE.
↑ B. Durand et Z. Róka, The game of life :universality revisited dans Cellular Automata : a Parallel Model, vol. 460 of Mathematics and its Applications. Kluwer Academic Publishers, 1999, pp. 51-74.
↑ M. Cook, Universality in Elementary Cellular Automata, Complex Systems, 15(1), 2004, pp. 1-40.
↑ N. Ollinger, G. Richard, A Particular Cellular Automaton [].
↑ N. Ollinger et G. Richard, Four states are enough!, Theoretical Computer Science (2010), DOI:10.1016/j.tcs.2010.08.018.
↑ J. Kari, The Nilpotency Problem of One-dimensional Cellular Automata, SIAM Journal on Computing 21 (1992), pp. 571-586.
↑
a et b J. Kari, Reversibility and Surjectivity Problems of Cellular Automata, Journal of Computer and System Sciences 48, 1 (1994), pp. 149-182.
↑ T. Toffoli et N. Margolus, Invertible Cellular Automata: a review, Physica D, 45 (1990), pp. 229-253.
↑ E. Czeizler et J. Kari, A tight linear bound on the neighborhood of inverse cellular automata, ICALP 2005, Lecture Notes in computer Science 3580, pp. 410-420, Springer-Verlag.
↑ K. Morita and M. Harao. Computation universality of 1 dimensional reversible (injective) cellular automata. Transactions Institute of Electronics, Information and Communication Engineers, E, 72:758762, 1989.
↑ O. Martin, A. Odlyzko et S. Wolfram, Algebraic Properties of Cellular Automata, Communications in Mathematical Physics (1984), n°93, p. 219.
↑ (en) Peter Gács, « Reliable Cellular Automata with Self-Organization », Journal of Statistical Physics, vol. 103, no 1, 1er avril 2001, p. 45–267 (ISSN 1572-9613, DOI 10.1023/A:1004823720305, lire en ligne [], consulté le 26 décembre 2020)
↑ P. Narbel, Qualitative and quantitative cellular automata from differential equations (Proceedings of ACRI 2006, LNCS vol. 4173, pp. 112-121, (ISBN 3-540-40929-7)).
↑ B. Chopard et M. Droz Cellular automata modeling of physical systems (Cambridge University Press Collection Alea, 1998, (ISBN 978-0-521-67345-7)).
↑ Jonathan MARGERIT, « Modélisation et Simulations Numériques de la Propagation de Feux de Forêts » [] [PDF], 7 novembre 2003
↑ (en) Kourtz, A Model a Small Forest Fire . . . to Simulate Burned and Burning Areas for Use in a Detection Model, Society of American Foresters, 1971 (lire en ligne []), pp 163-169
↑
a et b A. Ilachinsky, Cellular Automata, World Scientific Publishing, 2001, pp. 660.
↑ A. Ilachinsky, Cellular Automata, World Scientific Publishing, 2001, pp. 661-662.
↑ J. P. Crutchfield, The Calculi of Emergence: Computation, Dynamics, and Induction, Physica D 75, 11-54, 1994.
↑ M. Minsky, Cellular Vacuum, Int. Jour. of Theo. Phy. 21, 537-551, 1982, DOI:10.1007/BF02650183.
↑ K. Zuse, The Computing Universe, Int. Jour. of Theo. Phy. 21, 589-600, 1982, DOI:10.1007/BF02650187.
↑ E. Fredkin, Digital mechanics: an informational process based on reversible universal cellular automata, Physica D 45, 254-270, 1990.
↑ F. Berto, G. Rossi, J. Tagliabue, The Mathematics of the Models of Reference, College Publications, 2010 [].
[]
v · m
Informatique théorique
Codage
Codage de l’information Compression de données Chiffrement Cryptanalyse Cryptographie Théorie de l’information
Modèles de calcul
Calculabilité Décidabilité et indécidabilité Ensemble récursif Problème de l’arrêt Ensemble récursivement énumérable Machine de Turing Thèse de Church Automate cellulaire Réseau de neurones artificiels Réduction polynomiale Problème NP-complet Principe de Church-Turing-Deutsch
Algorithmique
Algorithmique Algorithme glouton Algorithme probabiliste Algorithme génétique Complexité algorithmique Analyse d’algorithme Diviser pour régner Heuristique Programmation dynamique Géométrie algorithmique Algorithmes de tri Algorithmique du texte Exploration de données Science des données Apprentissage profond Test de primalité Structure de données Arbre enraciné Concurrence Parallélisme
Syntaxe
Réécriture Compilation Expression régulière Grammaire formelle Langage rationnel Ensemble rationnel Théorie des langages Théorie des automates Automate fini Automate sur les mots infinis Automate d’arbres Automate à pile Hiérarchie de Chomsky Linguistique informatique
Sémantique
Interprétation abstraite Méthodes formelles Vérification de modèles Sémantique des langages de programmation Sémantique dénotationnelle Sémantique axiomatique Sémantique opérationnelle
Logique mathématique
Assistant de preuve Calcul des prédicats Correspondance de Curry-Howard Fonction récursive Lambda-calcul Théorèmes d’incomplétude de Gödel Théorie des types
Mathématiques discrètes
Combinatoire Algorithme du simplexe Optimisation combinatoire Théorie des graphes Algorithmes de la théorie des graphes Recherche opérationnelle Théorie de la décision Analyse numérique
Portail de la logique Portail de l’informatique théorique

https://parlonssciences.ca › ressources-pedagogiques › les-stim-en-contexte › letrange-histoire-de-la-theorie-cellulaire

https://parlonssciences.ca › ressources-pedagogiques › les-stim-en-contexte › letrange-histoire-de-la-theorie-cellulaire
L’étrange histoire de la théorie cellulaire | Parlons sciences
L’histoire de la théorie cellulaire a commencé au 16e siècle aux Pays-Bas, où un fabricant de lunettes du nom de Zacharais Janssen aurait, dit-on, mis au point le premier microscope composé. Un microscope composé est muni de deux lentilles. Une lentille se trouve près de l’objet observé: il s’agit de l’ objectif.

https://fr.wikipedia.org › wiki › Théorie_cellulaire

https://fr.wikipedia.org › wiki › Théorie_cellulaire
Théorie cellulaire — Wikipédia
La théorie cellulaire est la théorie centrale et principale de la biologie cellulaire et le fondement le plus reconnu de la biologie en général. Elle a été alimentée par beaucoup d’expériences réalisées depuis le XVIIe siècle.

https://www.aquaportail.com › definition-3951-theorie-cellulaire.html

https://www.aquaportail.com › definition-3951-theorie-cellulaire.html
Théorie cellulaire : définition, limites, évolution – AquaPortail
Au milieu du 19 e siècle, en 1838, la théorie cellulaire a été formulée. Cela est généralement crédité à Matthias Schleiden et Theodor Schwann. Schwann a également formulé les principes de base de l’ embryologie en observant qu’un oeuf est une cellule unique qui se développe finalement en un organisme complet.

https://www.lelivrescolaire.fr › page › 6659198

https://www.lelivrescolaire.fr › page › 6659198
De l’invention du microscope à la théorie cellulaire
De l’invention du microscope à la théorie cellulaire Si l’étude des astres lointains remonte à l’Antiquité, l’observation d’éléments très petits n’a été possible qu’avec l’invention du microscope par Janssen en 1595. Quelles sont les étapes de la construction de la théorie cellulaire ?

https://fr.khanacademy.org › science › biologie-a-l-ecole › x5047ff3843d876a6:bio-4e-annee-sciences-de-base › x5047ff3843d876a6:bio-4-1h-introduction-aux-cellules › v › cell-theory

https://fr.khanacademy.org › science › biologie-a-l-ecole › x5047ff3843d876a6:bio-4e-annee-sciences-de-base › x5047ff3843d876a6:bio-4-1h-introduction-aux-cellules › v › cell-theory
Théorie cellulaire (vidéo) | Khan Academy
Introduction à la théorie cellulaire et découverte des rôles de Hooke, de Leeuwenhoek et des autres dans son développement. Introduction à la théorie cellulaire et découverte des rôles de Hooke, de Leeuwenhoek et des autres dans son développement. If you’re seeing this message, it means we’re having trouble loading external resources on our website. Si vous avez un filtre web …

https://www.pimido.com › matieres-scientifiques-et-technologiques › biologie › cours-de-professeur › histoire-theorie-cellulaire-597015.html

https://www.pimido.com › matieres-scientifiques-et-technologiques › biologie › cours-de-professeur › histoire-theorie-cellulaire-597015.html
L’histoire de la théorie cellulaire – Pimido
La cellule est la plus petite unité de vie. Toutes les cellules se forment par division d’une cellule préexistante. La construction de cette théorie est un processus rendu possible par l’invention du microscope et les apports de plusieurs scientifiques : L’invention des microscopes au 17e siècle permet l’observation des premières cellules.

https://www.insee.fr › fr › information › 1300628

renaudhths.wikidot.com › l-evolution-de-la-theorie-cellulaire
L’évolution de la théorie cellulaire – Renaudhths
La théorie cellulaire s’est développée comme résultat du travail de plusieurs scientifiques importants, les suivants y inclus : Anton von Leeuwenhoek (1632 – 1723) Leeuwenhoek a beaucoup amélioré le microscope et, donc, a ouvert tout un nouveau monde observable aux biologistes.

https://linternaute.com › science › divers › dossiers › 06 › revolutions-scientifiques › 12.shtml

https://linternaute.com › science › divers › dossiers › 06 › revolutions-scientifiques › 12.shtml
Révolution scientifique : découverte de la cellule
Mais la véritable théorie cellulaire voit le jour en 1839. Le botaniste Schleiden et le zoologiste Schwann, s’appuyant sur les nombreuses observations de leurs collègues et prédécesseurs,…

https://www.maxicours.com › se › cours › une-structure-complexe-la-cellule-vivante

https://www.maxicours.com › se › cours › une-structure-complexe-la-cellule-vivante
Une structure complexe : la cellule vivante – Maxicours
Savoir comment s’est construite la théorie cellulaire. Être capable de situer des ordres de grandeur : atome, molécule, organite, cellule, tissu et organisme. À l’aide de l’exemple de la membrane plasmique, faire le lien entre échelle cellulaire et échelle moléculaire.

https://tribu.phm.education.gouv.fr › toutatice-portail-cms-nuxeo › binary › deroule_TP1_theo_cell.pdf?type=FILE&path= › default-domain › workspaces › preparation-des-nouveaux-programmes-de-svt-en-lycee › enseignement-scientifique-premiere › theorie-cellulaire › deroule-tp1-theo-cell-pd&portalName=foad&liveState=true&fieldName=file:content&t=1566982584

https://tribu.phm.education.gouv.fr › toutatice-portail-cms-nuxeo › binary › deroule_TP1_theo_cell.pdf?type=FILE&path= › default-domain › workspaces › preparation-des-nouveaux-programmes-de-svt-en-lycee › enseignement-scientifique-premiere › theorie-cellulaire › deroule-tp1-theo-cell-pd&portalName=foad&liveState=true&fieldName=file:content&t=1566982584
PDF Chapitre 1 Une structure complexe : la cellule – Education
I) La construction de la théorie cellulaire Les trois principes de la théorie cellulaire sont : – Tout organisme vivant est onstitué dune ou plusieurs ellules – La ellule est lunité de ase de la vie – Toute ellule provient dune autre ellule.

https://www.youtube.com/watch?v=DaVPX8sX008