Descriptif
La complexité algorithmique étudie la difficulté intrinsèque des problèmes, en particulier vis-à-vis du temps nécessaire à leur résolution.
On donne une introduction à l'étude des classes de complexité, en s'appuyant sur divers problèmes d'optimisation combinatoire, principalement de graphes.
A la fin du cours les élèves sauront évaluer la difficulté d'un problème de recherche opérationnelle et déterminer le type de résolution approprié: une méthode exacte pour un problème "facile" et, en général, une méthode approchée pour un problème "difficile".
On fera une étude détaillée des classes P et NP.
Les problèmes calculables en temps polynomial déterministe forment la classe P. La classe NP est constituée de problèmes dont la solution est vérifiable en temps polynomial, mais les trouver peut demander un temps exponentiel. Ces deux classes contiennent des milliers de problèmes de la
théorie des graphes, de logique, des automates et d'autres domaines.
Objectifs pédagogiques
- Stage de communication : 23
Diplôme(s) concerné(s)
- Master 2 Recherche Opérationnelle
- Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
Parcours de rattachement
Format des notes
Numérique sur 20Littérale/grade européenPour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
Vos modalités d'acquisition :
- le rattrapage est obligatoire si :
- Note initiale < 6
- le rattrapage peut être demandé par l'étudiant si :
- 6 ≤ note initiale < 10
- Crédits ECTS acquis : 1.5 ECTS
- Scientifique acquis : 1.5
Le coefficient de l'UE est : 1.5
La note obtenue rentre dans le calcul de votre GPA.
L'UE est évaluée par les étudiants.
Pour les étudiants du diplôme Master 2 Recherche Opérationnelle
Le rattrapage est autorisé (Note de rattrapage conservée)- le rattrapage est obligatoire si :
- Note initiale < 10
- Crédits ECTS acquis : 2 ECTS
Le coefficient de l'UE est : 2
La note obtenue rentre dans le calcul de votre GPA.
Programme détaillé
1. Bloc de module:
Séance 1
Introduction générale à la complexité des algorithmes. Mesure de l’efficacité d’un algorithme. Problèmes de décision. Transformation polynomiale. Définition des classes P, NP, NP-C, Co-NP. Exemples.
2. Bloc de module:
Séance 2
Problèmes d'optimisation combinatoire, problèmes NP-difficiles.
3. Bloc de module:
Séance 3
Transformation de problèmes.
Preuves de NP-complétude de plusieurs problèmes de RO et de graphes
4. Bloc de module:
Séance 4
Suite: Preuves de NP-complétude de plusieurs problèmes de RO et de graphes.
Algorithmes pseudo-polynomiaux.
5. Bloc de module:
Séance 5
Algorithmes approchés
6. Bloc de module:
Examen