Énumérer des objets est une tâche courante en informatique, que ça 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. Cette méthode est optimale, au sens ou nous donnons des bornes inférieures qui montre qu’il est impossible de faire de l’amortissement quand on ne connaît pas le délai ou qu’on veut respecter l’ordre des solutions.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne