Complexité : approximation

Code UE : US331Q-PAR01

  • Cours
  • 3 crédits

Responsable(s)

Safia KEDAD SIDHOUM

Compétences visées

Maîtriser l'approximation polynomiale

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
    Intitulé de la formation
    Type
    Modalité(s)
    Lieu(x)
    Lieu(x) À la carte
    Lieu(x) Paris
    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

    Centre(s) d'enseignement proposant cette formation