Tag « journal »

Le problème du compactage de tables consiste à trouver les recoupements maximums dans des tables aléatoires, c'est-à-dire des tables qui permettent en fonction de conditions initiales de donner une liste coefficientée de résultats possibles. Par exemple, dans un jeu qui ressemblerait aux dames avec des pions rouges et bleus et un dé à six faces, il pourrait y avoir une table qui nous dit que sur un jet de dé, si nous avons un pion bleu qui arrive sur un pion rouge, sur un 1, les deux sont éliminés, sur un 2 ou un 3, le pion rouge reste et sinon, le pion bleu prend la place ; alors que si un pion rouge arrive sur un bleu, les résultats 1 à 4 donnent le pion rouge vainqueur et 5 et 6 le pion bleu. Le compactage dans le cas précédent consisterait à dire qu'on lance un dé, qu'on garde la table comme elle est pour le premier cas, que l'on ajoute +2 dans le deuxième cas, et que sur un résultat de 7 ou 8 c'est le pion rouge qui gagne.

Nous avons montré (avec Jean-Yves Moyen que le problème est NP-complet dans le cas général, et étudié certaines des restrictions du problème.

lire la suite

Dans cet article, co-écrit avec Véronique Terrier pour la conférence Latin 2002, nous regardons comment les automates cellulaires de dimension supérieure peuvent aider à tracer des signaux. Nous montrons l'existence d'un « trou » dans l'espace des signaux constructibles en dimension quelconque, Nous montrons à l'aide de deux automates cellulaires de dimension 2 qu'une dimension plus élevée permet de diminuer le nombre d'états nécessaires à certaines constructions.

lire la suite

Cet article, écrit conjointement avec Enrico Formenti et Bruno Durand, présente une approche nouvelle de la classification des automates cellulaires (AC) fondée sur la complexité de Kolmogorov. Nous construisons un paramètre κ qui est basé seulement sur la table de transition des AC et mesure le « caractère aléatoire » des évolutions. κ est meilleur, dans un certain sens, que n'importe quel autre paramètre calculable défini uniquement par la table de transition des AC. Nous avons aussi examiné les relations entre l'approche classique (topologique) et la notre. Notre paramètre a été aussi comparé au paramètre λ de Langton : le notre est plus fondé théoriquement, et s'accorde aussi avec des constatations expérimentales déjà publiées. Finalement, nous proposons aussi un protocole d'approximation de κ et d'expérimentation sur le comportement dynamique des AC.

lire la suite

Il est indécidable de savoir si un automate cellulaire est inversible. L'universalité des automates cellulaires inversibles a été résolue par Toffoli qui a montré qu'un automate cellulaire quelconque peut-être simulé par un automate cellulaire de dimension juste supérieure. Cet article présente une méthode pour prouver le même théorème en dimension 1, accessible à des étudiants de niveau M1 ou M2 pour prouver cela.

lire la suite