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 19 Octobre 1999

Automates à groupes aléatoires

par Cyril Nicaud (LIAFA, Jussieu)

En géometrie discrete 2D, un certain nombre de problèmes sont très utilisés, tels que savoir si un objet est connexe, étiqueter les composantes connexes d'un objet, mais aussi d'autres problèmes tels que determiner si deux objets donnés "ont la même topologie".

Après avoir defini précisement un certain nombre de ces problèmes, nous exposerons un algorithme LogSpace pour déterminer si deux pixels d'un objet sont connectés ou non dans cet objet. (LogSpace signifie que l'algorithme ne peut stocker qu'un nombre borné de coordonnées de pixels, independant de la taille de l'image, les entrées étant en "read Only"). Un corollaire est que presque tous les problèmes considérés, et notament l'étiquetage des composantes connexes, sont dans LogSpace.

Ensuite, on s'attache à donner des bornes inferieures pour la complexité de ces problèmes. On montre que le problème de savoir si deux pixels dans un objet sont connectés est NC^1-difficile. Enfin, on montre qu'aucun des problèmes considérés ne peut être résolu en temps constant sur une machine parallèle avec un nombre polynomial de processeurs (plus précisement, on montre qu'aucun de ces problèmes n'est dans AC^0).

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