Résolution exacte de problèmes NP-complets et difficiles

Crédit : 3 ECTS
Langue du cours : anglais

Description du contenu de l'enseignement

Objectifs : Enseigner les techniques de la résolution exacte des problèmes NP-difficiles par des algorithmes à complexité non-triviale (dits algorithmes modérément exponentiels) et par des algorithmes paramétrés. Pour chacune de ces techniques, des exemples de problèmes sur lesquels elles sont appliquées seront présentés et discutés. Complexité au pire des cas
Techniques de résolution exacte (Programmation dynamique, Arbres de recherche, Enumération, Inclusion – exclusion, Recherche locale)
Application à la résolution exacte de problèmes NP-difficiles (Coloration, Voyageur de commerce, Stable, Coupe maximum, Stable maximum, Couverture d'ensembles)
Techniques de l’algorithmique paramétrée (Kernelisation, Arbres de recherche, …)
Application à la résolution paramétrée de problèmes NP-difficiles (Couverture de sommets minimum, Feedback vertex set, k-Couverture de sommets)

Bibliographie, lectures recommandées

Bibliographie
R. G. Downey, M. R. Fellows, Parameterized Complexity, Springer-Verlag, 1999.
F. V. Fomin, D. Kratsch, Exact Exponential Algorithms, Springer-Verlag, 2010.


Année universitaire 2019 - 2020 - Fiche modifiée le : 20-12-2018 (11H37) - Sous réserve de modification.