Complexité : approximation

Code UE : US331Q

  • Cours
  • 3 crédits

Responsable national

Christophe PICOULEAU

Responsable opérationnel

Christophe PICOULEAU

Compétences visées

Maîtriser l'approximation polynomiale

Contenu

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.

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é en 2017/2018