v2.11.0 (5776)

Enseignement scientifique & technique - CSC_4MI03_TP : Complexité

Domaine > Mathématiques.

Descriptif

Ce cours propose une introduction à la théorie de la complexité des problèmes d'’optimisation combinatoire (théorie de la NP-complétude).
L'’objectif est de donner un sens et des éléments de réponse à la question suivante : dans quelle mesure peut-on dire qu'’un problème est intrinsèquement difficile à résoudre d’'un point de vue algorithmique ?
Les concepts abordés sont les suivants : machines de Turing (déterministes ou non déterministes), problèmes de décision, liens entre problèmes d’'optimisation et problèmes de décision, classes P et NP, transformations polynomiales, transformations de Turing, problèmes polynomiaux, NP-complets, NP-difficiles, hiérarchie polynomiale.

Format des notes

Numérique sur 20

Littérale/grade européen

Pour les étudiants du diplôme Diplôme d'ingénieur

L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 2.5 ECTS
  • Crédit d'UE électives acquis : 2.5

La note obtenue rentre dans le calcul de votre GPA.

Pour les étudiants du diplôme Echange international non diplomant

La note obtenue rentre dans le calcul de votre GPA.

Programme détaillé

 

Veuillez patienter