v2.11.0 (5679)

Enseignement scientifique & technique - MITRO203 : 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

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

La note obtenue rentre dans le calcul de votre GPA.

Pour les étudiants du diplôme Data & Artificial Intelligence

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

Programme détaillé

 

Veuillez patienter