Unité pédagogique
Théorie de la complexité
Derniere édition le: 17/06/2024
Modifier
Responsable:
GARAIX Thierry
Description générale :
La résolution effective de
problèmes nécessite d'avoir une idée de leurs difficultés algorithmiques,
c'est-à-dire de la possibilité de les résoudre de façon efficace en temps et en
espace via des algorithmes. Dans cette UP l'objectif est de présenter la
classification des problèmes qui est faite actuellement par rapport à ces
questions. Seront donc définies les classes P et NP, ainsi que la fameuse
question "P = NP?" qui est au coeur de la Théorie de la Complexité et
où les problèmes NP - Complets jouent un rôle essentiel. D'autres classes,
comme celle des problèmes NP - Difficiles, seront aussi abordées. Enfin, à
défaut de pouvoir résoudre exactement de façon efficace un problème, pourquoi
de pas tenter une résolution approximative? La dernière partie de l'UP sera
consacrée à cette problématique et fera un tour d'horizon des nombreuses
questions qu'elle pose. L'étude plus spécifique des stratégies possibles pour
l'approximation sera, elle, faite dans l'autre UP du GP.
Mots-clés:
Classification de Problèmes
Classes P et NP
Problèmes NP - Complets
Problèmes NP - Difficiles
Nombre d’heures à l’emploi du temps:
15
Domaine(s) ou champs disciplinaires:
Informatique, Systèmes d'information
Langue d’enseignement:
Français
Objectifs d’apprentissage:
| A la fin de l’unité pédagogique, l’élève sera capable de : |
Niveau de taxonomie |
Priorité |
| Comprendre la nécessité théorique et l'intérêt pratique de l'étude de la "difficulté" de résolution d'un problème et de quelques unes de ses versions particulières |
2. Comprendre |
Essentiel |
| Identifier les problèmes "phares" de ce domaine d'étude et leurs variations, ainsi que certaines de leurs applications |
1. Connaître |
Essentiel |
| Avoir une connaissance rigoureuse des principales classes de problèmes et de leurs relations mutuelles |
1. Connaître |
Essentiel |
| Connaître la problématique de l'approximabilité et ce que l'on peut en attendre |
1. Connaître |
Important |
| Utiliser les notions acquises pour tenter la classification d'un problème et de quelques uns de ses sous problèmes |
3. Appliquer |
Important |
| Utiliser les outils techniques permettant de comparer des problèmes et leurs différentes versions |
3. Appliquer |
Important |
| Appliquer une méthodologie générale de résolution algorithmique d'un problème |
4. Analyser |
Utile |
| Élargir ses connaissances à d'autres questions et classes de problèmes |
2. Comprendre |
Utile |
Modalités d’évaluation des apprentissages:
|
Part de l'évaluation individuelle
|
Part de l'évaluation collective
|
|
Examen sur table :
|
75
|
%
|
Livrable(s) de projet :
|
0
|
%
|
|
Examen oral individuel :
|
0
|
%
|
Exposé collectif :
|
0
|
%
|
|
Exposé individuel :
|
0
|
%
|
Exercice pratique collectif :
|
0
|
%
|
|
Exercice pratique individuel :
|
25
|
%
|
Rapport collectif :
|
0
|
%
|
|
Rapport individuel :
|
0
|
%
|
|
|
|
|
Autre(s) : 0 %
|
Programme et contenus:
| Type d’activité pédagogique : |
Contenu, séquencement et organisation |
| Cours + Travaux Dirigés |
Nature, Type et
Formulation des Problèmes. Classes P et NP
|
| Cours + Travaux Dirigés |
Structure de NP:
Problèmes NP - Complets, Frontière P - NP
|
| Cours + Travaux Dirigés |
Problèmes NP -
Difficiles et autres Classes de Problèmes. Complexité en Espace |
| Cours + Travaux Dirigés |
Problématique de l'Approximabilité |