Unité pédagogique
Paradigmes de résolution de problèmes
Derniere édition le: 17/06/2024
Modifier
Responsable:
JUGANARU-MATHIEU Mihaela
Description générale :
L'objectif de ce cours est
de faire un tour d'horizon d'un certain nombre de méthodes générales de
résolution algorithmique de problèmes, baptisées Paradigmes Algorithmiques.
Chacune de ces stratègies sera illustrée par de nombreux exemples où les élèves
pourront en mesurer à la fois leurs pertinences, leurs adaptabilités à la
spécificité du problème étudié, et leurs efficacités en terme de complexités
(temps et espace). Les problèmes étudiés sont de nature discrète, c'est à dire
représentables exactement par des structures finies, et admettent tous une
réponse exacte calculable en un temps fini. Certains d'entre eux, qualifiés de
"difficiles", en raison du temps de calcul prohibitif nécessaire à
leur résolution exacte (leur étude fait l'objet d'une deuxième UP), nous
obligent à développer des techniques d'approximation. De telles stratégies
seront abordées en dernière partie.
Mots-clés:
Résolution de Problèmes
Stratégies Algorithmiques
Complexité
Optimisation discrète
Parcours de Graphes
Nombre d’heures à l’emploi du temps:
24
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é |
| Envisager et de décrire précisément plusieurs plusieurs stratégies de résolution exactes pour un problème donné |
4. Analyser |
Essentiel |
| Mettre en oeuvre effectivement ces méthodes, au niveau algorithmique et pratique |
3. Appliquer |
Essentiel |
| Déterminer la pertinence et les complexités de chacune de ces méthodes pour un problème donné |
4. Analyser |
Essentiel |
| Utiliser des outils de mathématiques discrètes |
4. Analyser |
Important |
| Mettre en oeuvre des méthodes d'approximation classiques et plus récentes sur un problème difficile |
3. Appliquer |
Important |
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 + TD |
Méthodes Incrémentales,
Prétraitement, Algorithmes Gloutons
Cours + Travaux Dirigés |
| Cours + TD |
Divide and Conquer,
Récursivité, Équations de Récurrence
Cours + Travaux Dirigés |
| Cours + TD |
Parcours de Graphes et
Applications
Cours + Travaux Dirigés |
| Cours + TD |
Méthodes Approximatives:
Recherches Locales, Recuit Simulé, Recherche Tabou, Algorithmes Génétiques et
Bio Inspirés
Cours + Travaux Dirigés |