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 23 Juin 2015

Un théorème d'accélération linéaire sur tout voisinage pour les automates cellulaires 2D

par Victor Poupet (LIRMM, Montpellier)

Dans cet exposé je présenterai un résultat récent obtenu en collaboration avec Anaël Grandjean qui permet d'obtenir une accélération linéaire de la reconnaissance d'images (motifs rectangulaires) par des automates cellulaires 2D fonctionnant sur des voisinages quelconques. Je présenterai d'abord les automates cellulaires, et la reconnaissance d'images, puis les résultats connus d'accélération linéaire sur les voisinages classiques: von Neumann (4 plus proches voisins) et Moore (8 plus proches voisins).

J'expliquerai les difficultés algorithmiques qui apparaissent lorsque l'on considère des voisinages quelconques, et les idées qui permettent de les résoudre.

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