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.
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.
24 heures en présentiel
Diplôme(s) concerné(s)
Parcours de rattachement
Format des notes
Numérique sur 20Littérale/grade européenPour 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é