Automate cellulaire

Un automate cellulaire à une dimension est constitué de $n$ cellules disposées linéairement. Une cellule donnée est soit dans l'état morte soit dans l'état vivante. L'état d'une cellule à l'instant $t$ est déterminée par son état à l'instant $t-1$ ainsi que l'état de ces deux voisines à ce même instant $t-1$. La figure ci-dessous donne une règle possible de changement d'états.

Règle de changement d'état

Les cellules vivantes sont en noir et les cellules mortes en blanc.

Par convention, la première et la dernière cellule sont considérées comme voisines. Il faut donc plutôt imaginer que les cellules forment un cercle.

Question 1

On choisit de représenter l'état morte par 0 et l'état vivant par 1. La règle de changement d'états ci-dessus peut alors être décrite par la liste [0, 1, 1, 0, 1, 0, 0, 1].

Écrire le code de la fonction new_state.

In [ ]:
def new_state(rule, left, self, right):
    """ Retourne le nouvel état d'une cellule sachant qu'elle
        est dans l'état self et que ses voisines de gauche
        et de droite sont respectivement dans les états
        left et right.
    """
    ### À COMPLÉTER

rule = [0, 1, 1, 0, 1, 0, 0, 1]
new_state(rule, 1, 0, 1)

Question 2

Écrire le code de la fonction next_step.

In [ ]:
def next_step(S, rule):
    """ Applique à l'automate dans l'état S la règle rule
        et retourne le nouvel état de l'automate.
    """
    ### À COMPLÉTER
    
S = [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
rule = [0, 1, 1, 0, 1, 0, 0, 1]
print(S)
S = next_step(S, rule)
print(S)
S = next_step(S, rule)
print(S)

Question 3

Écrire le code de la fonction generate_steps.

In [ ]:
def generate_steps(S, rule, nsteps):
    """ Retourne la liste des états successifs de l'automate
        initialement dans l'état S.
        La règle rule est appliquée nsteps fois.
    """
    ### À COMPLÉTER

S = [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
rule = [0, 1, 1, 0, 1, 0, 0, 1]
evolution = generate_steps(S, rule, 6)
evolution

Question 4

Écrire la fonction save_steps.

In [ ]:
def save_evolution(filename, evolution):
    """ Sauvegarde l'évolution de l'automate dans le fichier
        de texte filename.
        
        * evolution est la liste retournée par la fonction
          generate_steps
        * Le fichier comporte une ligne par état de l'automate
        * Les cellules vivantes sont représentées par 
          le caractère '+' et les cellules mortes par un espace.
    """
    ### À COMPLÉTER

Question 5

On considère un automate de 61 cellules. Seule la cellule centrale est initialement vivante. Simuler 100 étapes en appliquant la règle [0, 1, 1, 0, 1, 0, 0, 1] et sauvegarder l'évolution dans le fichier "automate.txt".

In [ ]:
 

Question 6

Une règle est une liste de huit entiers 0 ou 1. Si on interprète cette liste comme l'écriture en base deux d'un entier on peut désigner une règle par un entier.

(a) Combien existe-t-il de règles possibles ?

(b) Quel est l'entier associé à la règle [0, 1, 1, 0, 1, 0, 0, 1] ?

(c) Quelle est la règle $90$ ?

Question 7

Écrire le code de la fonction rule_from_number.

In [ ]:
def rule_from_number(r):
    """ Retourne la liste qui correspond à la règle numéro r.
    """
    ### À COMPLÉTER

rule_from_number(42)

Question 8

Écrire la fonction automate.

In [ ]:
def automate(n, rule_number, nsteps):
    """ Simule un automate cellulaire.
    
        * n est le nombre de celllules
        * rule_number le numéro de la règle
        * nsteps est le nombre d'étapes
        L'évolution est sauvegardée dans le fichier "automate-<rule_number>.txt"
        où <rule_number> est à remplacer par le numéro de la règle.
    """
    ### À COMPLÉTER

Question 9

On considère un automate de 101 cellules. Seule la cellule centrale est initialement vivante. Simuler 100 étapes en appliquant la règle numéro 90 et sauvegarder l'évolution dans le fichier "automate-90.txt".

In [ ]: