v2.11.0 (5687)

Cours scientifiques - APM_5OD23_TA : Théorie de la complexité

Domaine > Applied Maths.

Descriptif

Ce cours s'appuie sur les problèmes de graphes pour présenter la Théorie de la Complexité. La complexité algorithmique étudie la difficulté intrinsèque des problèmes, en particulier vis-à-vis du temps nécessaire à leur résolution.

Nous faisons 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".

Nous ferons 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 contient la classe P et est constituée de problèmes dont la solution est vérifiable en temps polynomial, mais la 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

A la fin du cours les élèves sauront évaluer la difficulté d'un problème de recherche opérationnelle et distinguer les problèmes faciles qu'on peut résoudre en temps polynomial des problèmes NP-difficiles. Cette classification les aide à déterminer l'approche de résolution appropriée : une méthode exacte pour un problème polynomial et, en général, une méthode approchée pour un problème NP-difficile.

21 heures en présentiel (6 blocs ou créneaux)
réparties en:
  • Stage de communication : 23

effectifs minimal / maximal:

8/40

Diplôme(s) concerné(s)

Parcours de rattachement

Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées

de préférence SOD321 - Optimisation Discrète

Format des notes

Numérique sur 20

Littérale/grade européen

Pour les étudiants du diplôme Inside ENSTA Paris

Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)
  • le rattrapage est obligatoire si :
    Note initiale < 6
  • le rattrapage peut être demandé par l'étudiant si :
    6 ≤ note initiale < 10
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 1.5 ECTS

La note obtenue rentre dans le calcul de votre GPA.

L'UE est évaluée par les étudiants.

Pour 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 :

 Examen final. Autorisés: documents distribués et notes personnelles ; les autres documents (livres, polycopiés d'autres cours, documents provenant d'Internet, etc.) sont interdits, de même que les ordinateurs, les téléphones portables et autres objets du même genre.

Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)
  • le rattrapage est obligatoire si :
    Note initiale < 6
  • le rattrapage peut être demandé par l'étudiant si :
    6 ≤ note initiale < 10
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 2 ECTS
  • Scientifique acquis : 2

Le coefficient de l'UE est : 1

La note obtenue rentre dans le calcul de votre GPA.

L'UE est évaluée par les étudiants.

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 écrit

Mots clés

Graphes, complexité, algorithmes, NP-difficulté, polynomial

Méthodes pédagogiques

Cours et Exercices
Veuillez patienter