Iules d'un automate cellulaire sont les cases
d' un résea u rég ulier dans un espace à n
dimensions, le cas le plus co nnu et le
plus étudié étant ce lui d' un qu adrill age
à mailles carrées dans le pl an . On peut
aus i co ncevo ir des automates ce llu -
laires dans un résea u à maill es tri angulaires ou hexagonales ou dans le pavage
régulier d ' un espace à troi s dimensions
ou davantage .
A insi , pour définir un automate cellulaire,
il fa ut un réseau de cases ( les ce llul es)
pouvant prendre un nombre fini d 'états
se lon une règ le préc isa nt le devenir de
chaque état d ' un e ce llul e à l ' in stant
1 + 1 en foncti on de son état et de celui
de ses ce llules vo isines à l ' instant 1. Les
math émati c iens Stephen Wolfram et
Dav id Eppstein ont tenté de proposer
une class ificati on des automates cellulaires.
L'étude d'un automate cellulaire consiste
à pa11ir d' une configuration initi ale donnée et à obser ver son devenir. L a popu -
lation va- t-elle s'éteindre et di sparaître,
s'étendre indéfinim ent , converger vers
une configurati on parti culière constante
ou péri odique, fi xe ou en déplacement ,
ou encore deve nir chaotique? L es automates cellul aires peuvent être considérés co mme des systèmes dynamiques
di screts. L'étude de ces systèmes s'est
co nsidérabl ement déve lo ppée, on le
comprend aisément , avec ! 'avè nement
de l' informatique qui permet une approche
ex périmentale.
Le plu s connu des automates ce llul aires
es t « le j eu de la vie » . John Horto n
Conw ay l 'a introduit dan s les années
1960, en en préc isant les règles de naissance, de survie et de mort.
En oc t o bre 19 7 2, M artin G ardn er
consac re sa rubriqu e du Scie111ijic America11 au j eu de la vi e de Conw ay et
l 'engo uement po ur ce j eu prend un
essor ex trao rdinaire au tout début du
déve loppement de l ' inform atique.
POUR LES MATHS
Quelques exemples d'évolutions
de populations au ieu de la vie
• Dans le premier
exemple, on part d'une
population de trois cellules. Deux de ces cellules ont un seul voisin
et la troisième a deux
voisins. Toutes les trois
vont donc mourir. Mais une cellule vide possède trois voisins (avant leur mort). Cette cellule va donc voir une naissance. À l'instant 2, notre population sera donc éteinte.
• Prenons maintenant l'exemple de trois cellules formant un
rectangle.
On constate que le rectangle va être alternativement horizontal,
puis vertical, et que l'on a affaire à une transformation de période
2 : la population va prendre deux états. On l'appelle parfois
un pulsar.
• Voici maintenant un autre type de population, appelé glisseur, qui revient périodiquement à sa forme initiale mais en
se déplaçant ou en glissant selon un vecteur défini.
• Voici pour finir deux questions faciles
laissées à votre sagacité : comment les
deux configurations ci-dessous vont-elles
évoluer?
Hors-série n° 52. Mathématiques & informatique Tangente
d' un résea u rég ulier dans un espace à n
dimensions, le cas le plus co nnu et le
plus étudié étant ce lui d' un qu adrill age
à mailles carrées dans le pl an . On peut
aus i co ncevo ir des automates ce llu -
laires dans un résea u à maill es tri angulaires ou hexagonales ou dans le pavage
régulier d ' un espace à troi s dimensions
ou davantage .
A insi , pour définir un automate cellulaire,
il fa ut un réseau de cases ( les ce llul es)
pouvant prendre un nombre fini d 'états
se lon une règ le préc isa nt le devenir de
chaque état d ' un e ce llul e à l ' in stant
1 + 1 en foncti on de son état et de celui
de ses ce llules vo isines à l ' instant 1. Les
math émati c iens Stephen Wolfram et
Dav id Eppstein ont tenté de proposer
une class ificati on des automates cellulaires.
L'étude d'un automate cellulaire consiste
à pa11ir d' une configuration initi ale donnée et à obser ver son devenir. L a popu -
lation va- t-elle s'éteindre et di sparaître,
s'étendre indéfinim ent , converger vers
une configurati on parti culière constante
ou péri odique, fi xe ou en déplacement ,
ou encore deve nir chaotique? L es automates cellul aires peuvent être considérés co mme des systèmes dynamiques
di screts. L'étude de ces systèmes s'est
co nsidérabl ement déve lo ppée, on le
comprend aisément , avec ! 'avè nement
de l' informatique qui permet une approche
ex périmentale.
Le plu s connu des automates ce llul aires
es t « le j eu de la vie » . John Horto n
Conw ay l 'a introduit dan s les années
1960, en en préc isant les règles de naissance, de survie et de mort.
En oc t o bre 19 7 2, M artin G ardn er
consac re sa rubriqu e du Scie111ijic America11 au j eu de la vi e de Conw ay et
l 'engo uement po ur ce j eu prend un
essor ex trao rdinaire au tout début du
déve loppement de l ' inform atique.
POUR LES MATHS
Quelques exemples d'évolutions
de populations au ieu de la vie
• Dans le premier
exemple, on part d'une
population de trois cellules. Deux de ces cellules ont un seul voisin
et la troisième a deux
voisins. Toutes les trois
vont donc mourir. Mais une cellule vide possède trois voisins (avant leur mort). Cette cellule va donc voir une naissance. À l'instant 2, notre population sera donc éteinte.
• Prenons maintenant l'exemple de trois cellules formant un
rectangle.
On constate que le rectangle va être alternativement horizontal,
puis vertical, et que l'on a affaire à une transformation de période
2 : la population va prendre deux états. On l'appelle parfois
un pulsar.
• Voici maintenant un autre type de population, appelé glisseur, qui revient périodiquement à sa forme initiale mais en
se déplaçant ou en glissant selon un vecteur défini.
• Voici pour finir deux questions faciles
laissées à votre sagacité : comment les
deux configurations ci-dessous vont-elles
évoluer?
Hors-série n° 52. Mathématiques & informatique Tangente