Complexité

Code UE : US331B

  • Cours
  • 2 crédits

Responsable national

Christophe PICOULEAU

Responsable opérationnel

Christophe PICOULEAU

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
Type
Intitulé
Equipe pédagogique
Modalité(s) / Lieu(x)
Code
Equipe pédagogique Informatique
Modalité(s) / Lieu(x)
  • Enseignée en formation présentielle et/ou partiellement à distance : Paris
  • Type Intitulé Equipe pédagogique Modalité(s) / Lieu(x) Code

    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é cette année