Les automates cellulaires de S. Wolfram

Dans cet exercice, nous allons nous intéresser à la simulation d'un monde virtuel simple, peuplé de cellules pouvant être vivantes ou mortes. Pour cela, nous disposons d'un monde constitué d'un tableau à une dimension pouvant contenir des cellules vivantes ou mortes. Ensuite, nous définirons des règles d'évolution, qui en fonction du voisinnage d'une case (ie. de l'état des cases qui lui sont adjacentes), nous permettrons de savoir si la cellule courante sera vivante ou morte lors de la prochaine génération.

Une case n'ayant que deux cases voisines, on peut facilement représenter l'ensemble des états que peut prendre cet ensemble de trois cases, cela ne donne que 2³ = 8 cas distincts :

Ce schéma se lit de la manière suivante : les trois cases supérieures permettent d'identifier un état du jeu, tandis que la case inférieure indique l'état que devra prendre la cellule du milieu à la génération suivante. Ainsi, la première règle indique que si l'on se trouve dans la situation où l'on a trois cellules vivantes alors au tour suivant, la case du milieu passera à l'état mort (0).

Cette représentation est intéressante car elle permet de représenter de manière succincte l'ensemble des règles d'évolution possible pour ce monde simplifié. En effet, si l'on met un 0 en dessous d'une case, pour signifier qu'au tour suivant la cellule sera morte, et que l'on met 1 en dessous d'une case, pour signifier cette fois que la cellule sera vivante au tour suivant, on peut représenter une règle (c'est à dire les 8 cas possibles) par un simple décimal compris entre 0 et 255.

Les règles 0 et 255 ne sont pas très intéressantes : elles mènent au vide absolu pour la première et à l'obscurité totale pour la dernière ! Par contre, la règle représentée ci-dessus (quel est le numéro de cette règle ?) génére un motif plus intéressant. En effet, pour visualiser l'évolution de la population, nous allons cette fois-ci afficher chaque génération les unes à la suite des autres, ce qui produira, en fonction de la règle choisie, de surprenants motifs. Voici ce que donne la règle illustrant le codage d'une règle (en commençant avec une seule cellule vivante au milieu du monde) :

Comment pouvons-nous représenter les règles de manière plus utile que sous la forme d'un décimal ? Ou plutôt, comment peut-on transformer le décimal en une représentation plus utile lors du calcul de la génération suivante ? L'idéal serait de disposer d'un tableau nommé regles, composé de huit booléens qui représenteraient le nombre décimal.

a)  Concevez un algorithme qui transforme un entier règle en sa représentation binaire sous la forme d'un tableau de booléen, règles. On pourra supposer que le nombre à convertir appartient à l'intervalle [0, 255].

En supposant que le monde soit défini comme un tableau de booléens (monde), il devient facile de calculer la génération suivante dans le tableau monde2. Il suffit pour cela de balayer les cases du tableau monde de l'indice 1 à l'indice n-1 (si n est le nombre de cases de monde) en appliquant les huit conditionnelles décrites ci-dessus.