Complexité
2 crédits Safia KEDAD SIDHOUM EPN05 - Informatique Unité spécifique de type cours
Publié Du 01-09-2011 au 31-08-2024
Maîtriser les preuves de NP-complétude
L'unité US331B apparaît dans 1 cursus.
Présentation des différentes classes de problèmes combinatoires tant au point de vue de leur complexité Cette présentation est faite via l'introduction des notions de réduction polynomiale. La classe NP des problèmes de décision est définie à partir de la notion d'algorithme non déterministe polynomial puis est donnée la définition des problèmes NP-complets. Le théorème de Cook qui établit que le problème de satisfiabilité (SAT) est NP-complet est démontré. A partir de ce résultat, d'autres problèmes sont montrés NP-complets. La notion d'algorithmes pseudo-polynomial permet ensuite d'établir une distinction entre les problèmes NP-complets.