Rapports de stages

J'ai effectué des stages en laboratoire en licence (1993) et en maîtrise (1994) de l'École normale supérieure de Lyon respectivement au LIP et à l'IIT Madras (quand Chennai / சென்னை s'appelait encore Madras).

Stage de licence (juillet 1993)

Le premier rapport de stage sous la direction de ceux qui deviendraient mes directeurs de thèse (Jacques Mazoyer et Bruno Durand) portait sur les automates cellulaires au sens large et s'est décomposé en trois parties :

D'abord, j'ai donné de manière complète un algorithme permettant de résoudre le problème de décision de l'inversibilité ou de la surjectivité d'automates cellulaires de dimension 1, en temps quadratique. Cet algorithme est inspiré d'un article de K. Sutner.
Dans une deuxième partie, je me suis intéressé aux rapports entre automates cellulaires inversibles et universalité, et j'ai construit un automate cellulaire inversible capable de simuler des machines de Turing non réversibles, ce qui prouvait l'universalité de tels automates. K. Morita avait prouvé un résultat similaire, mais ne simulait que des machines de Turing réversibles. Cette partie a par la suite donné lieu à une publication dans une revue.
Enfin, j'ai modifié un programme pré-existant qui permet de simuler des automates cellulaires plans afin d'augmenter ses fonctionnalités, en particulier en lui permettant de d'écrire les automates sous forme de fonction écrites en langage C. Une forme évoluée de ce programme a été refaite depuis zéro en 1998 lors d'un échange au Chili (puis perdue corps et biens).

Une figure insérée initialement a été définitivement perdue (elle ne subsiste que dans les versions papiers du rapport, qui si elles existent encore serviront un jour à allumer un feu de cheminée). Le rapport a été recompilé récemment pour être converti en PDF.

Stage de maîtrise (septembre 1994)

Le deuxième rapport de stage, rendu en septembre 1994, est en deux parties ; un compte-rendu scientifique en anglais et un compte-rendu sur l'apport en français. Je mets ici le deuxième pour mémoire, mais il n'en vaut pas vraiment la peine. Le stage s'est fait sous la direction de Kamala Krithivasan (à l'époque directrice du département, que je n'ai hélas pas beaucoup vue).

J'ai construit pendant ce stage des modèles de calcul dérivés des automates cellulaires : à voisins qui changent en fonction du temps, ou à vol de voisins (on peut changer son voisinage, de façon déterministe toujours, en fonction de son état, en prenant les voisins dans ceux de ses voisins actuels). J'ai démontré quelques résultats d'équivalence, puis que le deuxième modèle était strictement plus puissant que le modèle classique (il permet une synchronisation d'automates en temps logarithmique).

En regardant en arrière, j'ai été bien plus productif et efficace pendant le stage de licence (je trouve les conclusions avancées complètement évidentes). Le fait que je n'ai réussi à dormir que 2 ou 3 heures par nuit au maximum pendant le premier mois de stage a dû jouer dans ma productivité. Le rapport a été recompilé récemment pour être converti en PDF.

Les documents

Citer ce document

N'ayant pas fait l'objet d'une publication à grande échelle, voici l'entrée bibliographique correspondante :

@MastersThesis{dubacq93,
  author =  {Jean-Christophe Dubacq},
  title =   {\'Etude des automates cellulaires inversibles},
  school =  {\'Ecole normale sup\'erieure de Lyon},
  year =    {1993},
  type =    {Licence / Bachelor degree}},
  address = {},
  month =   jul
  note =    {LIP, ENS Lyon}
}
@MastersThesis{dubacq94,
  author =  {Jean-Christophe Dubacq},
  title =   {Different Kinds of Neighborhood-Varying Cellular Automata},
  school =  {\'Ecole normale sup\'erieure de Lyon},
  year =    {1994},
  type =    {Ma{\^{\i}}trise / Honour Bachelor degree}},
  address = {},
  month =   sep,
  note =    {CS dept, IIT Chennai}
}