|
Comment mesurer l'efficacité des algorithmes d'énumération ?| old_uid | 19040 |
|---|
| title | Comment mesurer l'efficacité des algorithmes d'énumération ? |
|---|
| start_date | 2021/05/04 |
|---|
| schedule | 14h |
|---|
| online | no |
|---|
| summary | 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. |
|---|
| responsibles | Laporte |
|---|
| |
|