Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 8 Juin 2004

Les automates cellulaires en dimension 2 et leur voisinage

par Véronique Terrier (GREYC, Université de Caen)

Les automates cellulaires sont un modèle de calcul massivement parallèle. Ce modèle de calcul tout en ayant une description simple et bien formalisée et capable de calcul universel.

En dimension 2, un automate cellulaire est constitué d'un tableau à 2 dimensions de composants élémentaires identiques appelés cellules. A une étape donnée, chaque cellule est dans un état donné. Au cours du temps l'état d'une cellule varie en fonction de son environnement local.

Ces changements d'états se font :

Pour les automates cellulaires vus comme accepteurs de langages, on distingue une cellule du tableau pour récupérer le résultat. Un mot est alors accepté ou rejeté si au cours du calcul cette cellule distinguée entre dans un état d'acceptation ou de rejet.

Je m'intéresserai à la question du voisinage, c'est à dire l'environnement local de chaque cellule. En particulier, j'examinerai en quoi le choix du voisinage peut influer sur les capacités de calcul.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr