Ateliers Maths et Informatique, TP3

Introduction

Un automate cellulaire peut être vu comme un univers fictif où l'espace, le temps et les grandeurs physiques prennent des valeurs discrètes. C'est, en quelque sorte, une idéalisation du monde réel, beaucoup plus simple et surtout très bien adapté à une simulation sur un ordinateur car, toutes les variables étant discrètes, aucune erreur numérique d'arrondi n'est à redouter. De plus, les lois qui régissent ce monde virtuel sont simples, et ne nécessitent que des calculs élémentaires pour un ordinateur. Ces lois sont construites par le programmeur selon les besoins du problème, ou selon ses envies. Ainsi, le programmeur se retrouve, l'espace d'un instant, dans la position du Créateur.

Le ``jeu de la vie'' est un exemple fameux d'automate cellulaire qui décrit l'évolution (naissance et mort) d'une population de cellules. Depuis le milieu de année 80, cette technique s'est beaucoup développée comme un outil de modélisation permettant une meilleures compréhension des phénomènes complexes.

Définition

Un automate cellulaire est définit sur un réseau régulier, typiquement un réseau carré de dimension 2, comparable à un échiquier de taille arbitraire. A chaque cellule ou site du réseau (case de l'échiquier) est associé une valeur numérique (par exemple 0 ou 1) appelée l'état du site.

Le système évolue dans le temps en fonction d'une règle choisie. A chaque itération, l'état de chaque site est modifié selon cette règle. Pour chaque site, la {\bf même} règle est appliquée {\bf simultanément}. Par définition, cette règle est une fonction qui ne dépend que de l'état des sites voisins.

Par exemple, si l'état des cellules est soit 0 soit 1, une règle possible serait: (1) on calcul la somme des états dans le voisinage immédiat de chaque site (soit les cellules au nord, nord-est, est, sud-est, sud, sud-ouest, ouest, nord-ouest, ainsi que la cellule elle-même). Pour chaque site cette somme est un nombre compris entre 0 et 9. (2) Si cette somme vaut 0,1,2,3 ou 5, la cellule correspondante prend 0 comme nouvelle valeur de son état. Si, au contraire, la somme vaut 4,6,7,8 ou 9, la cellule prend 1 comme nouvelle valeur. La figure suivante illustre le résultat de cette règle:

Evolution de l'automate cellulaire avec une règle de majorité biaisée, avec une condition initiale aléatoire, avec 50% de site á 1. On observe la croissance de domaines de sites dans le même état.

Problème I

Programmez cet automate cellulaire en matlab (en fait, remplissez les trous du code...)

% Initialisation de la session
clear 
close all

% Taille de l'automate
m=32;

% initialisation aleatoire de l'automate avec des 0 et 1, avec probabilité 0.5
X=rand(m,m)>0.5;


% evolution de la regle de majorite biaisee
% N est la somme des valeurs des etats des voisins
while any(any(X))

  %%%%%%%%%%%%
  %% remplir ici le calcul de N = somme de X plus les 8 voisins
  %%%%%%%%%%%%

  X=(N==4) | (N>5);  % mise a jour selon la regle de l'annealing

% affichage 
  pcolor(X)
  axis off image
  shading flat % removes the lattice
  drawnow
end

corrigé

La fourmi de Langton

C'est un animal hypothétique se déplaçant sur les cases d'un échiquier, selon la règle suivante. Le cases peuvent être soit blanches (0), soit noires (1). Si la case est blanche, la fourmi quitte la case après avoir effectué un quart de tour à droite. Si, au contraire la case est noire, elle quitte la case en effectuant un quart de tour à gauche. Dans tous les cas, après le passage de la fourmi, la case change de couleur: noir->blanc et blanc->noir, de sorte qu'au prochain passage sur la même case, la fourmi aura un comportement différent.

Le comportement de la fourmi de Langton est incroyablement complexe, comme le montre la figure suivante:

Mouvement de la fourmi de Langton. Les pixels blancs ou gris indiquent la couleur de chaque case. La position courante de la fourmi est donnée par le point noir.

Cette observation est intéressante car elle montre que bien qu'on connaisse complètement les règles de déplacement, on ne sait pas dire grand chose sur le comportement global de cette fourmi. En d'autres termes, la connaissance de la loi fondamentale qui régit le monde n'explique pas forcément les phénomènes qui en découlent.

Problème I

Programmez la fourmi.

Le conseil du hacker futé: Pour réaliser un affichage rapide, il faut n'afficher que les cases qui ont été modifiés.

clear all
m=200;                    %taille du domaine
fpos=[m/2 m/2];           %position courante
%%%%%%%%%%%%%%%%%%%
%% peut-etre d'autres declarations
%%%%%%%%%%%%%%%%%%%


X=zeros(m,m);             % remplit X de zeros
figure('Units','points','Position',[20 20 3*m 3*m])
                          %ouvre une figure, unites sont des points,
                          %position sur l'ecran 20, 20;
                          %taille 3*m par 3*m (si on fait m par m, c'est trop petit)
axis([1 3*m 1 3*m])
axis manual               %pour pas qu'il ne se recalcule automatiquement
hold on

while(1);
%%%%%%%%%%%%%%%%%
%% regles d'evolution de la position de la fourmi
%%%%%%%%%%%%%%%%%%%


     %exemple d'affichage d'un carré blanc pour la position fpos(1) fpos(2)
     plot(3*fpos(1),3*fpos(2),'square','Color','w','erasemode','background','markersize',3)
                          %affiche un carre blancde taille 3 par 3 , a la poistion courante

                          %idem en bleu
     plot(3*fpos(1),3*fpos(2),'square','Color','b','erasemode','background','markersize',3)

   drawnow
end

corrigé

Problème III

Peut-on affirmer que, dans un espace infini, la fourmi s'echappera toujours vers l'infini? Ceci est clairement vrai si, initialement, toutes les cases sont blanches puisque la fourmi construira forcément une ``autoroute'' qui l'enmènera au loin. Mais peut-on imaginer une structure particulière de cases blanches et noires qui forcera la fourmi à avoir un mouvement périodique? Tester vos idées par des simulations.

Proposer une démonstration théorique, selon les indications suivantes: remarquez que les cases peuvent être réparties en des cases de type H dans lesquelles la fourmi pénètre horizontalement et des case de type V dans lesquelles la fourmi entre verticalement. Les cases H et V alternent, comme les cases d'un échiquier. Supposez que la fourmi ait un mouvement borné et considérez, par exemple la case en haut à gauche du domaine visité. Que peut-on conclure du mouvement de la fourmi si elle repasse plusieurs fois sur cette case. En déduire la réponse au problème du mouvement borné ou non.

Problème III

Généraliser la règle de mouvement pour permettre à plusieurs fourmis de se déplacer simultanément (au plus quatre fourmis par case, chacune venant d'une direction différente). Faites le choix suivant: si un nombre impair de fourmis traverse la même case, la couleur de la case est changée. S'il y en a un nombre pair, la couleur n'est pas modifiée.

Simuler le comportement de plusieurs fourmis placées aléatoirement dans le région centrale du domaine. Qu'ob\-servez-vous sur le temps de création de la première autoroute?

Est-ce les conclusions du problème III restent valables s'il y a plusieurs fourmis? Que se passe-t-il si, à un moment donné de la simulation, on renvoie toutes les fourmis dans la direction opposées? En déduire que des trajectoires périodiques à deux fourmis peuvent exister.

alexandre masselot

Last modified: Thu Mar 23 15:15:39 CET 2000