Unary to binary converter
2019-11-15 17:38:28

Recherche — Automates Cellulaires — La ligne de fusiliers (Mazoyer)

Les productions publiées sur ces différentes pages ont été pensées dans le cadre d'une diffusion de la connaissance, qu'elle soit strictement pédagogique ou dans le cadre plus formel de la recherche scientifique. Ces supports ont été fabriqués par mes soins grâce au soutien de l'Université Paris Diderot et du CNRS, et tout particulièrement de l'IRIF.
Ces documents sont libres de droits et peuvent être réutilisés à toutes fins; mais cela ne signifie pas que vous pouvez vous en attribuer le mérite.

Des vidéos illustrant des solutions au FSSP conçues par le professeur Jacques Mazoyer (IXXI / Ens Lyon, France)

Téléchargez ici et ici les vidéos illustrant la solution de Mazoyer à 6 états.
Cette solution est la première connue à 6 états synchronisant une ligne de longueur n en temps 2n. Le problème reste ouvert de savoir s'il existe une solution à 5 états; il est démontré qu'il n'en existe pas à 4 états. Cette solution possède différentes caractéristiques intéressantes, en particulier elle ne fait pas appel à une symétrie lors des appels récursifs.

Téléchargez ici le petit film illustrant l'extension conservative faite par Yunès à la solution originale de Mazoyer à 6 états.
L'extension consiste à rendre la solution insensible à la position initiale du général. Bien entendu le caractère minimal en temps d'exécution est perdu.