moteur de recherche

Séminaire Algo - Yann Strozecki
Séminaire Algo - Yann Strozecki
4-May-2021 14:00
Age: 43 days





Yann Strozecki (DAVID, Université de Versailles Saint-Quentin)

Comment mesurer l'efficacité des algorithmes d'énumération ?

Zoom (if you want to participate, please request the meeting password. If your interest in the seminar is more general, you can request to be added to the announcement mailing list which will contain the password for each meeting)

Résumé: Un problèmes d'énumération demande de lister un ensemble de solutions, généralement très grand. Par exemple il est facile de produire tous les arbres couvrants d'un graphe mais l'ensemble des arbres couvrants est exponentiel en la taille du graphe d'entrée.

Il faut donc introduire des mesures de complexité adaptées pour caractériser la complexité des problèmes d'énumération. Les plus classiques sont :
- le temps incrémental, c'est à dire le temps qu'il faut pour générer t solutions (fonction de t et de la taille de l'entrée)
- le délai entre deux solutions (fonction de la taille de l'entrée ou d'une solution)

Nous donnerons des exemples de méthodes pour résoudre un problème d'énumération en délai polynomial (en l'entrée ou la solution) ou en délai constant, en étudiant le problème de générer les modèles d'une formule DNF. Puis nous montrerons comment on peut se passer de la notion de délai polynomial pour la remplacer par le temps incrémental linéaire, en introduisant une méthode qui garantit la régularité des solutions énumérées tout en utilisant peu d'espace.








<- Back to: Accueil