Détails du cours OROC-RO-CP

Theory of complexity

Cette page est essentiellement destinée aux enseignants et regroupe toutes les informations nécessaires à la gestion d'un cours ENSTA.

Identité du cours

Sigle : OROC-RO-CP
Titre français : Théorie de la complexité (TC)
Titre anglais : Theory of complexity
Méta infos : modifiée le : 09/03/2017   par : mcosta   Nb de visiteurs : 7   annee : 3A      periode : 1      Rattachement/module : A      ECTS : 1.5      type : unknown     
ouvert : Oui     modif. autorisée : Oui     email auto. au responsable : Oui     à évaluer : Oui     en ligne : Non    
domaine ParisTech : 1    

Equipe pédagogique

Responsable (login) :
Professeur principal :
Professeurs participants : Olivier HUDRY,   
Maitres de conférences : Arnaud LAZARE,   

Contenu

Objectifs : 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.

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.
Mots clés : Graphes, complexité, algorithmes, NP-difficulté, polynomial.
Objectives : This course use many problems from graph theory to present the different classes
of computational complexity. We give definitions and present several problems of
graph theory (coloring, covering, time table problems...). Computational
complexity theory studies the intrinsic difficulty of the problems related to
the amounts of resources required for their resolution by an algorithm (in
particular the cpu time). This course is an introduction to the study of
complexity classes and the presentation is mainly based on graph problems.

Knowing the “difficulty” of a problem, one can choose the most suitable
methods to solve it: exact method for "easy" problem, approximate methods for
"difficut" problems..
Keywords : Graphs, complexity, algorithms, NP-hardness, polynomiality.
Supports : Polycopié des vues utilisées en cours.
Biblio : Computers and intractability. A guide to the theory of NP-completeness. G=M. R.
Garey and D. S. Johnson; Freeman & Company (USA). 1979.

Programmation Linéaire, Complexité. Séparation et Optimisation. J.-F.
Maurras. Collection Mathématiques et Applications , Vol. 38. Springer. 2002.
Contrôle : 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.

Besoins particuliers et remarques éventuelles

Moyens :
Commentaires :

Séances

lun. 07 nov. 2016   - 08:30 à 12:15 : Bloc de Module (1/2 journée) (MOD)
programme : 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.
besoin :
Intervenants : Olivier HUDRY,
lun. 14 nov. 2016   - 08:30 à 12:15 : Bloc de Module (1/2 journée) (MOD)
programme : Séance 2 Problèmes d'optimisation combinatoire, problèmes NP-difficiles.
besoin :
Intervenants : Olivier HUDRY,
lun. 21 nov. 2016   - 08:30 à 12:15 : Bloc de Module (1/2 journée) (MOD)
programme : Séance 3 Transformation de problèmes. Preuves de NP-complétude de plusieurs problèmes de RO et de graphes
besoin :
Intervenants : Olivier HUDRY,
lun. 28 nov. 2016   - 08:30 à 12:15 : Bloc de Module (1/2 journée) (MOD)
programme : Séance 4 Suite: Preuves de NP-complétude de plusieurs problèmes de RO et de graphes. Algorithmes pseudo-polynomiaux.
besoin :
Intervenants : Olivier HUDRY,
lun. 12 déc. 2016   - 08:30 à 12:15 : Bloc de Module (1/2 journée) (MOD)
programme : Séance 5 Algorithmes approchés
besoin :
Intervenants : Olivier HUDRY,
lun. 09 janv. 2017   - 09:00 à 11:00 : Bloc de Module (1/2 journée) (MOD)
programme : Examen
besoin :
Intervenants : Olivier HUDRY,
ven. 10 mars 2017   - 14 à 16:30 : Contrôle (CC)
programme : Rattrapage
besoin :
Intervenants : Arnaud LAZARE,