Yann Strozecki (DAVID à l'Université de Versailles Saint-Quentin)

Énumérer des objets est une tâche courante en informatique, que çà soit pour les compter, trouver une solution optimale ou constituer une librairie d’objets intéressants. Pour mesurer la complexité d’un algorithme d’énumération, on borne généralement le délai qui mesure le temps entre la production de deux solutions. Une mesure plus souple est le temps incrémental qui mesure le temps nécessaire à la génération de k solutions.

Il est fréquent de régulariser un processus à temps incrémental linéaire en utilisant un grand “buffer” pour stocker les solutions et les produire régulièrement afin d’obtenir un algorithme à délai polynomial. Malheureusement, cette technique utilise un espace potentiellement exponentiel.

Nous allons présenter une méthode alternative, l’amortissement géométrique, qui permet de régulariser un algorithme en espace polynomial et sans surcoût en temps. Nous montrerons que cette méthode fonctionne même quand on ignore l’espace utilisé et le nombre de solutions générées par l’algorithme qu’on régularise. Par contre, nous allons prouver une borne inférieure pour montrer que la connaissance du temps incrémental est nécessaire.