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 6 Novembre 2007

Temps linéaire et énumération de requêtes à délai constant

par Etienne Grandjean (GREYC)

(travaux communs avec Guillaume Bagan, Arnaud Durand et Frédéric Olive).

La notion de temps linéaire dans le modèle RAM constitue un lien précis entre l'algorithmique et la théorie de la complexité. La complexité en temps linéaire est une notion robuste, naturelle et pratique.

Dans cet exposé, je présenterai d'abord quelques exemples en algorithmique et sur les requêtes en bases de données qui témoignent de l'importance du temps linéaire en pratique. Je décrirai succinctement un ensemble de problèmes de "model-checking" (est-ce qu'une structure S satisfait un certain énoncé logique F?) dont la complexité en temps est linéaire (en la taille de la structure S): il s'agit des formules conjonctives acycliques (formules ACQ de Yannakakis) et leurs extensions, essentielles dans les bases de données.

On peut aller plus loin encore: le calcul de l'ensemble des "tuples" noté F(S) qui satisfont une formule fixée F (conjonctive acyclique) sans quantificateur dans une structure (= base de données) S - est calculable en temps linéaire en la taille de l'entrée (la structure S) + la taille de la sortie (l'ensemble de tuples F(S)). Plus finement encore, il existe, pour chaque requête F, un algorithme qui, après un précalcul linéaire (en la taille de S), énumère les tuples du résultat à délai constant. La classe d'algorithmes d'énumération ainsi mise en évidence, appelée CONSTANT-DELAY(lin), s'avère encore une notion de complexité robuste et, en un certain sens, minimale. De plus, elle s'applique à plusieurs autres classes de requêtes, et en particulier à toutes celles définies sur les logiques et structures suivantes:

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