* * * Forum OXMO Message * * * -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- Titre : [SCIENCE] Les Automates Cellulaires Lancé le 30-01-2005 14:41 par Zakath Téléchargé de https://www.forum.oxmo.org/showthread.php?threadid=32586 -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 1] Auteur : Zakath Date : 30-01-2005 14:41 Titre : [SCIENCE] Les Automates Cellulaires Je sais qu'Oxmo est surtout un forum technique, mais je me suis dit que le sujet vous intéresserait peut-être. Il s'agit en effet d'informatique théorique, et accessoirement de mon futur thème de recherche. Comme je passe pas mal de temps dessus, je me suis dit que ça pourrait être rigolo de vous exposer ça, histoire de faire un peu partager ce sujet passionant et aussi de voir si je suis capable de bien vulgariser la chose. En très bref, les automates cellulaires sont surtout connus par l'intermédiaire du Jeu de la Vie de John Conway. On peut les voir comme un modèle de calcul (à la manière des machines de Turing, pour ceux qui connaissent) ou simplement comme des choses qui font des jolis dessins. L'idée est la suivante : on se donne un grille (infinie ou juste torique) de dimension d et un ensemble d'états Q = {q1, q2,... qn}. Chaque élément de la grille est une "cellule" qui peut se trouver dans un des états de Q. A chaque instant t, on applique un jeu de règles pour déterminer le nouvel état de chaque cellule. Ces règles dépendent de l'état des voisins de la cellule considérée. Le jeu de la vie, par exemple, utilise une grille torique de dimension 2 (donc un plan) et deux états. Le voisinage considéré est celui des 8 cases voisines. Si une cellule dans l'état 1 a deux ou trois voisins dans l'état 1, elle reste dans cet état, sinon elle passe à l'état 0. Si elle est dans l'état 0 et a exactement 3 voisins, elle passe dans l'état 1, sinon reste dans l'état 0. Il y a de nombreuses pages sur le jeu de la vie, [url=http://t0m.free.fr/jdlv/jdlv.htm]en voici une[/url] en français. Un autre exemple, plus intéressant, est celui de l'automate 110 (selon la numérotation de Wolfram). Cette fois en dimension1, donc une ligne, ce qui permet de placer son évolution temporelle sur le diagramme. On a toujours 2 états, 0 et 1, et le voisinage est simplement : {cellule à ma gauche, moi-même, cellule à ma droite}. Si on écrit 110 en binaire et qu'on trie lexicographiquement les voisinages, cela nous donne le jeu de règles, soit : 000 -> 0 001 -> 1 010 -> 1 011 -> 1 100 -> 0 101 -> 1 110 -> 1 111 -> 0 Ce qui est proprement surprenant, c'est qu'on arrive à générer des comportement extrêmement complexes avec ces règles aussi simples et des conditions initiales qui le sont tout autant. Un exemple d'évolution de 110 : [img]http://www.rule110.org/amhso/results/rule110-intro/img2.gif[/img] et [img]http://www.rule110.org/amhso/results/rule110-intro/img26.gif[/img] Il a été démontré très récemment que 110 était intrinsèquement universel, ce qui veut dire qu'il peut simuler n'importe quel autre automate cellulaire unidimensionnel. Selon les intérêts soulevés, je peux développer beaucoup sur les différents détails ou clarifier tout ce qui n'est pas clair dans la courtissime présentation ci-dessus (mais dites-moi si vous ne comprenez pas, et ce que vous ne comprenez pas !). Un jeu de transparents est également à l'étude. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 2] Auteur : fleming Date : 30-01-2005 19:53 Moi j'ai à peu près compris et j'ai trouvé ça intéressant... §dacdac§ ... mais c'est peut-être parce que mon mémoire de maîtrise de maths avait pour sujet les codes lexicographiques et les graphes de Lenstra en petites dimensions. :D j'avais même avec ma binôme démontré un théorème à l'époque, mon plus haut fait d'armes (et je serais bien incapable de m'y remettre maintenant 8 ans plus tard), la preuve, je l'ai retrouvé par hasard il y a quelques semaines, j'ai voulu jeter un coup d'oeil... et j'ai rien compris ! :D -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 3] Auteur : KissTheFuture Date : 30-01-2005 21:59 moi je cherchais un thread pour m'aider à m'endormir et je dois te remerci........ -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 4] Auteur : shakes808080 Date : 31-01-2005 10:10 Très intéressant... maintenant, faudrait montrer ce que ça donne concrètement par exemple : on a tous des PC capables de faire des simulations de ce genre, il faudrait juste un petit programme . -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 5] Auteur : Alexiel Date : 31-01-2005 11:06 [color=deeppink]tu dois pas être mauvais en vulgarisation puisque j'ai presque tout compris!! Sauf quelques termes, mais j'ai compris le but général...[/color]§bienjoué§ -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 6] Auteur : Zakath Date : 31-01-2005 16:35 [QUOTE][i]Message écrit par shakes808080, le 31-01-2005 à 10:10 [/i] [B]Très intéressant... maintenant, faudrait montrer ce que ça donne concrètement par exemple : on a tous des PC capables de faire des simulations de ce genre, il faudrait juste un petit programme . [/B][/QUOTE] Oui, ce n'est vraiment pas difficile, surtout pour les unidimensionnels. Si tu veux, je peux te passer mes sources C (avec le Makefile qui va bien) pour gcc sous Linux (il te faut la SDL pour le graphisme) qui font ces zolis dessins. Edit: voila la chose, recopie dans les fichiers qui vont bien puis fais un make. Il te faut gcc et SDL. Il y a deux règles, 54 et 110, renomme celle de ton choix en rules.c puis recompile. Le lancement se fait avec [CODE]./cells largeur etapes random seed[/CODE] Makefile: [CODE]CC = gcc CFLAGS = -Wall SRC = rules.c graph.c sim.c PROG = cells INC = -I /usr/include/SDL INCLIBS = -lSDL all: $(PROG) $(PROG): $(CC) $(CFLAGS) $(INC) $(SRC) -o $@ $(INCLIBS) clean: rm cells [/CODE] sim.c : [CODE]/* you must rename the rules files you intend to use in rules.c/rules.h */ #include #include #include #include "rules.h" #include "graph.h" int* conf; int size; int voisin[VECTS]; void compute (void) { int i, j, k; int valide; int* tmp; tmp = calloc (size, sizeof(int)); for (i = 0; i < size; i++) { valide = 1; for (j = 0; j < VECTS; j++) { k = i + vects[j][0]; if (k >= 0 && k < size) voisin[j] = conf[k]; else { valide = 0; break; } } if (valide) tmp[i] = delta(voisin); else /* On choisit de remplir les bords extérieurs avec des 0 */ tmp[i] = 0; } free (conf); conf = tmp; return; } int main (int argc, char* argv[]) { int i; SDL_Surface* screen; int steps, is_random, seed; if (argc != 5) { printf ("Bad number of arguments. Expected 4 and received %d\n", argc-1); exit (0); } if (DIM != 1) { fprintf (stderr, "As for now, only unidimensionnal automata are supported, sorry\n"); exit (0); } screen = SDL_Initialisation(); size = atoi(argv[1]); steps = atoi(argv[2]); is_random = atoi(argv[3]); seed = atoi(argv[4]); srand(seed); conf = calloc (size, sizeof(int)); if (is_random) { for (i = 0; i < size; i++) { conf[i] = rand()%STATES; } } else { for (i = 0; i < size; i++) { if (i == size/2) conf[i] = 1; else conf[i] = 0; } } for (i = 0; i < steps && i < HEIGHT/2; i++) { compute(); paint_line (conf, i, size, screen); } getc(stdin); free (conf); return 0; }[/CODE] graph.c : [CODE]#include #include #include #include #include "graph.h" int color_r[2] = {0xff, 0x00}; int color_g[2] = {0xff, 0x00}; int color_b[2] = {0xff, 0x00}; SDL_Surface* SDL_Initialisation (void) { SDL_Surface *screen; SDL_Init(SDL_INIT_VIDEO); atexit(SDL_Quit); screen = SDL_SetVideoMode(WIDTH, HEIGHT, 8, SDL_SWSURFACE); return (screen); } void putpixel(SDL_Surface *surface, int x, int y, Uint32 pixel) { int bpp = surface->format->BytesPerPixel; /* Here p is the address to the pixel we want to set */ Uint8 *p = (Uint8 *)surface->pixels + y * surface->pitch + x * bpp; switch(bpp) { case 1: *p = pixel; break; case 2: *(Uint16 *)p = pixel; break; case 3: if(SDL_BYTEORDER == SDL_BIG_ENDIAN) { p[0] = (pixel >> 16) & 0xff; p[1] = (pixel >> 8) & 0xff; p[2] = pixel & 0xff; } else { p[0] = pixel & 0xff; p[1] = (pixel >> 8) & 0xff; p[2] = (pixel >> 16) & 0xff; } break; case 4: *(Uint32 *)p = pixel; break; } } void paint_pixel (SDL_Surface* screen, int y, int x, int r, int g, int b) { Uint32 yellow; yellow = SDL_MapRGB(screen->format, r, g, b); if ( SDL_MUSTLOCK(screen) ) { if ( SDL_LockSurface(screen) < 0 ) { fprintf(stderr, "Can't lock screen: %s\n", SDL_GetError()); return; } } putpixel(screen, x, y, yellow); if ( SDL_MUSTLOCK(screen) ) { SDL_UnlockSurface(screen); } return; } void paint_line (int* bin, int line, int size, SDL_Surface* screen) { int i, r, g, b; int col; for (col = 0; col < WIDTH/2 && col < size; col++) { i = bin[col]; r = color_r[i]; g = color_g[i]; b = color_b[i]; paint_pixel (screen, 2*line, 2*col, r, g, b); paint_pixel (screen, 2*line+1, 2*col, r, g, b); paint_pixel (screen, 2*line, 2*col+1, r, g, b); paint_pixel (screen, 2*line+1, 2*col+1, r, g, b); } SDL_UpdateRect(screen, 0, 2*line, WIDTH, 2); return; } [/CODE] graph.h : [CODE]#include #define WIDTH 1024 #define HEIGHT 768 SDL_Surface* SDL_Initialisation (void); void paint_line (int*, int, int, SDL_Surface*);[/CODE] rules.h : [CODE]/* dimension de l'automate */ #define DIM 1 /* Nombre d'états */ #define STATES 2 /* Nombre de vecteurs de voisinage */ #define VECTS 3 int vects[VECTS][DIM]; int delta (int*);[/CODE] r54.c : [CODE]/* Rule 54 */ #include "sample.h" int vects[VECTS][DIM] = {{-1}, {0}, {1}}; int delta (int* v) { if (v[1] == 0) { if (v[0] == 0 && v[2] == 0) return 0; else return 1; } if (v[0] == 0 && v[2] == 0) return 1; return 0; }[/CODE] r1110.c : [CODE]/* Rule 110 */ #include "sample.h" int vects[VECTS][DIM] = {{-1}, {0}, {1}}; int delta (int* v) { if (v[0] == 1) { if (v[1] == v[2]) return 0; else return 1; } else { if (v[1] == 0 && v[2] == 0) return 0; } return 1; }[/CODE] -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 7] Auteur : Alexiel Date : 01-02-2005 00:20 [color=deeppink]Bon...... là, je suis larguée........[/color]§mondieu§ -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 8] Auteur : Pateretou[2] Date : 01-02-2005 01:40 Bah heu je suis pas sur que tout le monde puisse compiler sous linux la ... -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 9] Auteur : Pateretou[2] Date : 01-02-2005 01:45 blou blou, il gere pas les <> vbulletin, il cherche des balises la :D bloublou y a un include sample.h qui est foireux -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 10] Auteur : Pateretou[2] Date : 01-02-2005 01:52 Allez hop, j'ai "adapté" sous windows, mais j'ai eu la flemme de faire un truc graphique pour changer les options et tout et tout(et oh, z'avez vu l'heure j'ai une femme qui m'attend au lit moi!) Donc les sources sont la (VC7) : [url]http://www.crapules.com/~pateretou/zakath/zak.rar[/url] et l'executable (pour ceux qui veulent pas s'embeter a recompiler tout ca tout ca) : [url]http://www.crapules.com/~pateretou/zakath/zak_exe.rar[/url] Pour l'executer, il faut ouvrir une fenetre ms-dos et taper un truc du genre : [code] C:\Documents and Settings\pateretou\My Documents\Visual Studio Projects\zak\Debug>zak.exe 500 500 400 4000[/code] pour quitter, un ctrl-C dans la fenetre ms-dos J'ai pas eu le temps de m'y pencher mais j'ai pas reussi a trouver de "jolies trucs". Heu c'est tout ? oui je crois, si tu as des choses a rajouter zak, moi je t'avoue que j'ai pas trop le tps la mais ca a l'air interessant je checkerais ca a l'occas :D Ah vi, j'ai compilé avec le rul110 mais libre a vous de remplacer le contenu de rules.cpp par le contenur de rul54.c de zakath au dessus! Bonne nuit -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 11] Auteur : Zakath Date : 01-02-2005 07:09 Erf oui, IL ne faut pas lire #include "sample.h" mais #include "rules.h", désolé. Merci beaucoup d'avoir converti pour windows, je n'ai aucune idée de comment ça marche... Si tu ne veux pas commencer avec un truc aléatoire, il faut lui donner un 0 en 3ème option. Je ne sais pas ce que tu appelles de "jolis trucs", mais ce qu'il y a à voir, ce sont des structures (d'après Ollinger, des particules) qui se déplacent sur un fond régulier et qui vont aller s'entrechoquer pour fusionner et potentiellement donner d'autres structures. C'est grâce à ça qu'on peut simuler une machine de Turing (moyennant un codage ignoble, mais bon). Dès que j'ai un peu de temps dans la semaine, je pense rajouter la possibilité de continuer à regarder ce qui se passe "plus bas" (enfin plus haut, parce que les diagrammes espace-temps vont de bas en haut, dans l'école française). -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- [Post 12] Auteur : Pateretou[2] Date : 01-02-2005 11:16 zak : oui je parlais de "jolies structures" :D Pour le portage, c'est du copiez collez et de l'include de lib sdl la ou il faut dans VC, c'est tout et ca va pas chercher plus loin ... (et qq modif au code : tu definis deux fois la meme global) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-