Théorie de la Complexité
Mis à jour le
Responsable(s) : Mme Safia KEDAD SIDHOUM
- Cours
Envie d'en savoir plus sur cette formation ?
Afin d’obtenir les tarifs, le calendrier de la formation, en distanciel, en présentiel, le lieu de la formation et un contact, remplissez les critères suivants :
Afficher le centre adapté à mes besoins
Afin d’obtenir les tarifs, le calendrier de la formation et le lieu de la formation, remplissez les critères suivants :
-
Durée : 30 heures
-
Package
-
3 crédits
Présentation
Objectifs
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 .
Compétences et débouchés
Informations pratiques
Contact
-
Département : Recherche opérationnelle
-
Tel : 01 40 27 22 67
-
Email : secretariat.ro@cnam.fr
-
Adresse : 2D4P20, 33-1-10, 2 rue Conté - 75003 Paris
Programme
Contenu
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.