Descriptif
Définition d'un problème NP-difficile. Définition d'un algorithme approché. Les différentes mesures d'approximabilité. Les réductions préservant les rapports d'approximation. Les schémas d'approximation. L'obtention de solution approchées par techniques locales, d'arrondis,...L'algorithmique 'on-line'.
Objectifs pédagogiques
Etre capable de classifier les problèmes NP-difficiles en fonction de la difficulté de leur approximabilité.
30 heures en présentiel
Diplôme(s) concerné(s)
Domaine Université Paris Saclay
Mention Informatique.Pour les étudiants du diplôme Master 2 Recherche Opérationnelle
Cours de théorie de la complexité.
Format des notes
Numérique sur 20Littérale/grade européenPour les étudiants du diplôme Master 2 Recherche Opérationnelle
Vos modalités d'acquisition :
Examen
Rattrapage en 2ème session note plafonnée à 12
- le rattrapage est obligatoire si :
- Note initiale < 8
- le rattrapage peut être demandé par l'étudiant si :
- 8 ≤ note initiale < 10
- Crédits ECTS acquis : 3 ECTS
Le coefficient de l'UE est : 3
La note obtenue rentre dans le calcul de votre GPA.
