Complexité : approximation
3 crédits Safia KEDAD SIDHOUM EPN05 - Informatique Unité spécifique de type cours
Publié Du 01-09-2011 au 31-08-2024
Maîtriser l'approximation polynomiale
L'unité US331Q apparaît dans 1 cursus.
L'objectif de ce cours est de présenter les notions d'algorithmique polynomiale approchée pour les problèmes d'optimisation combinatoire. Cette présentation se fera à partir de la théorie de la complexité Après avoir défini la classe des problèmes de recherche (qui contient en particulier les problèmes d'optimisation), la réduction de Turing est introduite ce qui conduit à la notion de problèmes NP-difficiles. L'Algorithmique polynomiale approché traite de l'approximabilité par des algorithmes polynomiaux de ces derniers problèmes. La qualité d'une solution et la performance d'un algorithme sont définies ainsi que les e-approchés et schémas d'approximation. Les différentes classes d'approximabilité seront introduites.