Signaux rapides en plusieurs dimensions

Les automates cellulaires ont des propriétés très différentes selon qu'ils soient en dimension 1 ou 2 d'un point de vue de la calculabilité. Après avoir défini une notion de signal, on essaye ici d'analyser la puissance de calcul intrinsèque des automates cellulaires en une ou deux dimensions d'après la forme des signaux qu'il est possible de générer.

Une vision alternative des automates cellulaires est de considérer qu'ils ne sont pas des agents actifs de calcul, mais simplement un milieu discret sur lequel se propagent des signaux (un signal se déplace en ligne droite, et un ou plusieurs signaux ne sont générés — à des angles calculables — uniquement à l'intersection de signaux ; certains « trucs » permettant de faire des « boucles de signaux »).

Les résultats contenus sont intéressants et forment la base de mon travail avec Véronique Terrier. On a notamment construit en dimension 2 un signal qu'il n'est pas possible de construire en dimension 1, à savoir un signal de vitesse \(n+\log^\star(n)\).

À propos de ce rapport

Ce rapport est issu de mon stage de DEA au LIP sous la direction de Jacques Mazoyer et Bruno Durand. Le rapport fourmille de schémas et d'illustrations, et je n'ai pas pu m'empêcher d'inclure ici la vieille version « couleur ». La version PostScript avait la propriété de s'imprimer avec des tâches (de café) à des endroits différents à chaque fois. En 1995, c'était déjà pas mal.

Plutôt que les transparents d'origine, j'ai inclus les transparents refaits à l'occasion des rencontres programmation sur automates cellulaires de Jean-Baptiste Yunès en 2008.

J'ai également recompilé avec une version moderne de LaTeX le rapport. Il semblerait que la gestion des veuves et des orphelines ait changé, et je n'arrive pas à obtenir la même pagination exacte. Mais comme je ne suis pas sûr que le fichier que j'avais était déjà celui d'origine et que ça n'a aucune importance, on se contentera de ce nouveau fichier.

Les documents

• Le transparents de l'exposé RPAC 2008
• Le rapport de stage (recompilé)
• Le rapport original version parchemin sans tâches de café

Citer ce document

@MastersThesis{dubacqdea95,
  author =   {Jean-Christophe Dubacq},
  title =    {Signaux rapides en plusieurs dimensions},
  school =   {\'Ecole normale sup\'erieure de Lyon},
  year =     {1995},
  type =     {DEA / Master degree}},
  month =    sep,
  note =         {LIP, ENS Lyon}
}