% Rapport de Maths En Jeans % % Pablo Rauzy % % ------------------------- % % Header % ------ \documentclass[a4paper,12pt]{article} \usepackage[french]{babel} \usepackage[utf8]{inputenc} \usepackage{graphicx} \usepackage{wrapfig} \usepackage{color} \definecolor{sattlegray}{rgb}{0.6,0.6,0.6} % Du gris pâââââle \definecolor{emcolor}{rgb}{0,0.5,1} % Aqua is beautiful \newcommand{\emc}[1]{\textcolor{emcolor}{#1}} % EMphase by Color \newcommand{\damn}[1]{\textcolor{red}{#1}} % Tel un taureau... \newcommand{\nmi}[1]{\textcolor{sattlegray}{\small{\textit{#1}}}} \usepackage[colorlinks=false]{hyperref} % Cliquabeule linkz !! \newcommand{\fref}[1]{\footnote{\,Voir section \ref{#1} page \pageref{#1}.}} % HUMAN GOTO NIARK NIARK \newcommand{\refref}[1]{section \ref{section-references}.\ref{#1}, p. \pageref{#1}} % GOTOGOTO \newcommand{\ace}{\textsf{\textsc{a.c.e.}} } % Ça va (plus) vite ! \newcommand{\defin}[2]{\textbf{#1}~#2} % \textbf{bold} is a kind of emphase \newcommand{\demo}[1]{\textbf{Démonstration}~#1} \renewcommand{\familydefault}{\sfdefault} % Sans-serif powaaa \setlength{\parskip}{2mm} \setlength{\parindent}{3mm} % ----- % \title{\vspace*{3cm} \Huge \textbf{Rapport de Maths En Jeans}\\ \Large Groupe 6 : Automates cellulaires, la règle 90.\\ \large avec Yoann Corbasson, François Vaux et Pablo Rauzy. } \author{\vspace*{3cm} \\ \huge Pablo Rauzy\\ \large L1 Math-Info - Faculté des Sciences de Luminy\\ Université de la Méditerranée \vspace*{5cm} \\ } \date{Rendu le \today} % Body % ---- \begin{document} \maketitle \clearpage \tableofcontents \clearpage \section{Introduction} \begin{wrapfigure}{r}{3.2cm} \includegraphics{img/glider.png} \small{\caption{the Glider}} \label{glider} \end{wrapfigure} De part le métier de mon père, il y a toujours eu chez moi au moins un ordinateur. J'ai donc commencé à m'intéresser assez tôt à l'informatique, au début du collège. Depuis je suis passionné et consacre une grande partie de mon temps à apprendre et expérimenter des tas de choses très intéressantes que l'on peut faire avec un ordinateur. Lors d'une de mes nombreuses ballades sur la toile j'ai commencé à m'intéresser à la culture Hacker. En découvrant cet emblème j'ai tout de suite voulu connaître ce qu'elle représentait. Il se trouve que le Glider (planeur en anglais) est le planeur le plus simple du Jeu De La Vie. Ce fût mon premier contact avec les automates cellulaires. Je ne m'y étais plus vraiment intéressé depuis mais cela restait quand même quelque chose d'intéressant dans mon esprit. Et donc quand M. Beddou nous a donné la liste des sujets de Maths En Jeans et que j'ai entendu "automates cellulaires" j'ai tout de suite eu envie de travailler là dessus. \subsection{Automates cellulaires ?} Un automate cellulaire est un \textit{système dynamique} qui \textit{évolue au cours du temps}. Il est composé de \textit{cellules} qui peuvent prendre différents \textit{états}. À chaque \textit{génération}, chaque cellule évolue en fonction de l'état de ses voisines (une cellule peut être une voisine d'elle même) à la génération précédente. Le nouvel état de chaque cellule est déterminé par \textit{la règle} de l'automate cellulaire. % Automates cellulaires ? \clearpage % Introduction \section{Recherches} \subsection{Prise de contact avec le sujet} La particularité de ce projet de recherche est que c'est une des premières fois où l'on a pas de ligne toute tracée ou de questions auxquelles il faut répondre. On est très libre et on peut donner le sens qu'on veux à notre travail. Mais encore faut-il trouver de quoi parler. Pour ça il nous fallait pouvoir observer des automates cellulaires évoluer afin de trouver des pistes intéressantes. Le problème c'est que sur internet nous n'avons trouvé que des choses très spécifiques, comme par exemple une applet Java mais qui ne faisait que le Jeu De La Vie. En faisant nos recherche on se rend compte que le sujet est vraiment très vaste et qu'il y a une infinité de choses à voire ou à faire et qui sont toutes intéressantes ! On se rend compte en même temps que si on veut pouvoir avancer dans nos recherches, il faut qu'on prenne une décision. On décide de commencer par les automates les plus simple : les \ace pour Automates Cellulaires Élémentaires. \defin{Les Automates Cellulaires Élémentaires}{ sont les automates cellulaires les plus simple. Ils sont en une seule dimension; les cellules ont trois voisines : celle de gauche, la cellule elle-même et celle de droite; les cellules n'ont que deux états (vivante ou morte). } % Prise de contact avec le sujet \subsection{Documentation} WIKIPÉDIA POWAAAAAAA !! % Documentation \subsection{Écriture d'un programme pour visualiser des \ace} Le programme \texttt{MEjac}\footnote{\,Ça signifie Maths En Jeans Automates Cellulaires, rien d'autre :-D...} prend en argument la règle qu'il doit utiliser sous forme d'un nombre entier compris entre 0 inclus et 255 inclus puis il lit sur l'entrée standard le nombre de générations qu'il doit générer, ainsi que la grille de départ. Avant de continuer il faut peut-être expliquer la convention de nommage des règles des \ace \defin{Convention de nommage des règles des \ace :}{ \begin{figure} \begin{center} \includegraphics{img/convention.png} \caption{ Exemple de règle d'un \ace : la règle 115.\\ Les cellules grise sont vivantes et les cellules blanche mortes. } \label{convention} \end{center} \end{figure} La convention veut qu'on nomme une règle d'après la valeur en base 10 du nombre formé par la règle en base 2 en l'écrivant dans le sens du bit de poids fort au bit de poids faible. Par exemple la règle 115 que l'on voit sur la figure \ref{convention}. } L'algorithme de passage à la génération suivante n'est pas très compliqué. Dans un tableau de 8 cases numérotés de 0 à 7 représentant la règle, on a stocké les valeurs des bits correspondant. Dans l'exemple de la figure \ref{convention} le tableau contiendrait \texttt{\{1, 1, 0, 1, 1, 1, 0\}}.\\ Ensuite on regarde dans quel cas on est pour chacune des cellules afin de savoir si elle doit être vivante ou morte à la génération que l'on est en train de générer. Par exemple si la cellule est vivante mais que ces deux voisines sont mortes on a : \begin{itemize} \item la voisine de gauche est morte : $0 . 2^2 = 0$ \item la cellule est vivante : $1 . 2^1 = 2$ \item la voisine de droite est morte : $0 . 2^0 = 0$ \end{itemize} Donc ça fait $0 + 2 + 0 = 2$ on utilise la case du tableau qui à l'indice 2. Dans l'exemple la cellule deviendrait donc morte, ce qui correspond bien à la figure \ref{convention}. % Écriture d'un programme pour visualiser des \ace \subsection{Premières observations} \texttt{MEjac} nous a permis d'observer l'évolution de plein d'\ace et de faire plusieurs constatations. Ces constatations ne sont pas toutes aussi intéressantes, mais ce sont ces observations qui ont dirigées nos recherches. Au début on s'est beaucoup amusé à voir les formes que dessinent les \ace quand on les affiches au cours du temps (chaque nouvelle génération sous la précédente). On s'est aperçu que certaines règles avait l'air plus intéressantes que d'autres et même qu'on pouvait certainement regrouper ces règles par familles : celles qui font des triangles, celle qui font des lignes, celles qui "finissent" très vite (comme les règles 0 et 255). On a aussi fait une petite démonstration du nombre d'\ace existant. \demo{ Une règle est en fait une fonction définie sur $[0, 7] \to [0, 1]$. Le nombre de fonctions existantes d'un ensemble de 8 éléments à un ensemble de 2 éléments est $2^8 = 256$.\\ Il y a donc 256 règles possibles, ce qui correspond bien à ce qu'on a dis jusque là : les règles sont numérotés de 0 à 255 inclus. } En fait, il y avait tellement de chose à dire, même sur cette petite partie des automates cellulaires que sont les \ace, que l'on a décidé de se concentrer sur une seule règle qui était à la fois jolie au niveau des formes qu'elle dessine et qui semblait intéressante : la \textbf{règle 90}. % Premières observations \subsection{La règle 90} On a donc décidé de s'intéresser à la règle 90. On a commencé à l'observer plus précisément et on a fait pas mal d'observations.\\ // expliqué avec schema toutes nos observ. % La règle 90 \clearpage % Recherches \section{Résultats} \clearpage % Résultats \end{document}