Complexité

Code UE : US331B

  • Cours
  • 2 crédits

Responsable(s)

Safia KEDAD SIDHOUM

Compétences visées

Maîtriser les preuves de NP-complétude

Contenu

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.

Cette UE apparaît dans les diplômes et certificats suivants

Chargement du résultat...
Patientez
Intitulé de la formation
Type
Modalité(s)
Lieu(x)
Lieu(x)
Lieu(x)
Intitulé de la formation Type Modalité(s) Lieu(x)

Contact

Recherche opérationnelle
2D4P20, 33-1-10, 2 rue Conté
75003 Paris
Tel :01 40 27 22 67
secretariat.ro@cnam.fr

Voir les dates et horaires, les lieux d'enseignement et les modes d'inscription sur les sites internet des centres régionaux qui proposent cette formation

Enseignement non programmé s'il s'agit d'un diplôme, d'un certificat ou d'une UE ou enseignement qui ne fait jamais l'objet d'une programmation s'il s'agit d'une UA ou d'une US (le code formation commence alors par UA ou US).