Complexité : approximation

Code UE : US331Q

  • Cours
  • 3 crédits

Responsable(s)

Safia KEDAD SIDHOUM

Safia KEDAD SIDHOUM

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
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).