Portail nationalFormations hybrides

Théorie de la Complexité

Code UE : US333K

  • Cours
  • 3 crédits

Responsable(s)

Safia KEDAD SIDHOUM

Objectifs pédagogiques

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 .

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.
 

Modalité d'évaluation

  • Examen final

Cette UE apparaît dans les diplômes et certificats suivants

Chargement du résultat...
Patientez
Intitulé de la formation
Type
Modalité(s)
Lieu(x)
Intitulé de la formation Master Sciences, technologies, santé mention Informatique Parcours Recherche opérationnelle
Type Diplôme national (DEUST, licence, master, doctorat, diplôme d'Etat)
Lieu(x) Package
Lieu(x) Paris
Entrée Niveau 6 (Bac+3 et 4)
Intitulé de la formation Type Modalité(s) Lieu(x)

Contact

Recherche opérationnelle
2D4P20, 33-1-10, 2 rue Conté
75003 Paris
Tel :01 40 27 22 67
secretariat.ro@cnam.fr
Voir le site

Voir le calendrier, le tarif, les conditions d'accessibilité et les modalités d'inscription dans le(s) centre(s) d'enseignement qui propose(nt) cette formation.

Enseignement non encore programmé