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 24 Avril 2012

Complexité d'énumération : méthodes logiques et algébriques

par Yann Strozecki (LRI)

Je vais présenter dans cet exposé des problèmes d’énumérations, c’est à dire qu’on veut lister toutes les solutions d’un problème. Le but est de réaliser cette tâche avec un algorithme de complexité la plus faible possible. Dans ce cadre on s’intéresse à la fois au temps total de l’algorithme et au délai entre deux solutions.

Dans une première partie je montrerai comment représenter certains problèmes d’énumération par des formules du premier ordre contenant des variables libres du second ordre. On verra que la complexité d’énumération dépend du nombre de quantificateurs ainsi que de la structure sur lequel ces formules sont évaluées (degré bornée, largeur arborescente bornée, ...).

Dans un deuxième temps je présenterai des algorithmes probabilistes qui permettent d’énumérer les monômes d’un polynôme. Je montrerai ensuite comment on peut utiliser ces algorithmes pour résoudre des problèmes sur des graphes, des hypergraphes, des automates probabilistes.

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