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.
Objectifs pédagogiques
Acquis d'apprentissageÀ l'issue de l'UE, l'élève sera capable de:
- Analyser la complexité d'un problème en distinguant les problèmes ""faciles à résoudre"" (c'est-à-dire polynomiaux) des problèmes ""difficiles à résoudre"" (typiquement, les problèmes NP-difficiles).
- Etablir la NP-complétude ou la NP-difficulté d'un problème.
- Etablir des liens entre différents problèmes (de décision ou d'optimisation) à l'aide de transformations polynomiales ou de transformations de Turing.
- Choisir une méthode appropriée (exacte ou approchée, polynomiale ou exponentielle) pour résoudre un problème donné selon la complexité de celui-ci.
- Adapter des algorithmes conçus pour certains problèmes à d'autres problèmes à l'aide de transformations de Turing.
Compétences de rattachement (et justification)
- BC10.3 – Analyser une résolution par des approches formelles ou mathématiques; Justification : L'UE MITRO203 fournit à ses élèves les outils permettant d'établir la classe de complexité algorithmique à laquelle appartiennent les problèmes qu'ils considèrent. Cette classe conditionnera le choix ultérieur des méthodes de résolution qui seront mises en oeuvre.
- BC10.2 – Analyser et résoudre des problèmes mathématiques et algorithmiques nécessaires dans des étapes de réalisation d’un projet en s’appuyant, si besoin est, sur des simulations et dans l’objectif d’implémenter des solutions compétitives; Justification : La résolution pratique d'un projet à l'aide d'outils algorithmiques nécessite préalablement l'identification de la difficulté intrinsèque du problème à résoudre (classe de complexité).
- BC1.3 – Elaborer une ou plusieurs solutions technologiques, en s’appuyant sur la modélisation théorique et la méthode scientifique de manière à faire ressortir la pertinence desdites solutions permettant une prise de décision; Justification : Le choix d'une méthode plutôt qu'une autre dans une solution algorithmique se justifie par l'adaptation des performances de la méthode retenue par rapport à la nature du problème à résoudre. Les modélisations théoriques abordées en MITRO203 permettent de faire ressortir la pertinence de ces méthodes par rapport au problème fondamental qu'est la croissance (polynomiale ou exponentielle) du temps de calcul nécessaire pour traiter les instances du problème considéré.
24 heures en présentiel
20 heures de travail personnel estimé pour l’étudiant.
Diplôme(s) concerné(s)
Parcours de rattachement
Format des notes
Numérique sur 20Littérale/grade européenPour les étudiants du diplôme Echange international non diplomant
Vos modalités d'acquisition :
Contrôle de connaissance écrit de trois heures.
La note obtenue rentre dans le calcul de votre GPA.
Pour les étudiants du diplôme Diplôme d'ingénieur
Vos modalités d'acquisition :
Contrôle de connaissance écrit de trois heures.
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.
Programme détaillé
Mots clés
informatique théorique, complexité algorithmique des problèmes, classes P et NP, NP-complétude, NP-difficulté, tranformations polynomiales, transformations de TuringMéthodes pédagogiques
Les séances programmées à l'emploi du temps intègrent cours magistral et partie s'apparentant à des TD dans la mesure où les élèves sont invités à proposer leurs réflexions pour définir les démonstrations faisant l'objet du cours (essentiellement en ce qui concerne la conception des transformations polynomiales, spécifiques à chaque problème abordé et conduisant à la NP-complétude de celui-ci). L'ensemble est complété par des exercices à faire à la maison et dont la correction peut être développée lors de la séance suivante.Ressources : document synthétique présentant les lignes essentielles du cours + bibliographie + annales corrigées.
