J'ai été en courte expédition (125h de chez moi à chez moi) à Wǔhàn et
Běijīng (Wuhan et Pékin). Outre ma participation à un colloque ad
hoc (colloque franco-chinois sur les machines virtuelles et
l'informatique dans le nuage le cloud computing),
j'ai surtout participé à des réunions ...
J'ai été faire ce lundi 18 mai un séminaire à Perpignan (Perpinyà en catalan), au laboratoire PROMES.
J'y ai présenté quelques reflexions sur la réalisation d'un programme de simulation d'automates cellulaires généraliste de haute performance et prêt à tourner sur la grille. Ensuite, nous avons commencé ...
lire la suiteÀ l'occasion du départ à la retraite de mon directeur de thèse Jacques Mazoyer a été organisée une conférence très sérieuse sur les thématiques qui lui sont chères, liées en particulier aux automates cellulaires. De nombreux intervenants extérieurs étaient là (venant de France bien sûr, mais aussi de Finlande ...
lire la suiteLe 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 suiteDans 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 suiteLa complexité de Kolmogorov donne une interprétation de la notion d'aléatoire pour les mots sur un alphabet fini. Ces notions ont conduit à l'explicitation de classes de fonctions calculables possédant des caractéristiques provenant de la théorie des codes: la classe des machines préfixes — machines dont le domaine est codé de façon préfixe, c'est-à-dire qu'un mot du domaine n'est jamais le préfixe d'un autre mot du domaine.
Outre la résolution du problème de l'aléatoire dans les mots infinis, cette classe de machine est stable vis-à-vis de la théorie de la calculabilité. On compare ici trois définitions distinctes de la notion de machine préfixe, mais remarquablement similaires. On étend ensuite les notions proposées aux codes comma free (sans facteurs). Certaines propriétés fondamentales sont alors non-vérifiées, comme l'existence d'une machine additivement optimale. Enfin, on étudie la façon dont la notion de préfixe intervient dans la théorie de la calculabilité. On regarde en particulier les machines dont on limite le nombre de caractères (sans caractères blancs) ou encore la modélisation des modèles finis plongés dans des espaces de calcul infinis (ce qui est le cas de la machine de Turing, dotée d'un ruban infini). lire la suite