Algorithmique
Objectifs
Acquis d'apprentissage
- Connaissance des types de données les plus courants.
- Connaissance des techniques de preuve d’un algorithme (arrêt, correction, complexité)
- Connaissance des différents paradigme de programmation (récursif, glouton, programmation dynamique).
Compétences visées
Savoir montrer qu’un algorithme est correcte. Savoir évaluer la complexité algorithmique. Savoir mettre en œuvre le bon paradigme algorithmique pour résoudre un problème donné.
Plan du cours
Chapitre 1 : Niveau de description. On introduit les concepts de langage, de mémoire, de variable et les outils algorithmiques de calcul que sont les structures de contrôle et de réunitarisation.
Chapitre 2 : Type de données abstraits. descriptions des structures de données traditionnelles (pile, file, arbre binaire et tas) et des TDA les plus connus (ensemble dynamique, dictionnaire, file de priorité). Nous introduisons les TDA Famille d'ensembles et Gestion de partition pour lesquels nous proposons plusieurs implémentations.
Chapitre 4 Complexité introduction des concepts de problème algorithmique et de classe de complexité associé. Nous introduisons aussi la complexité algorithmique et les fonction temporelle de complexité dites asymptotiques. Enfin nous démontrons l'influence du codage et du modèle de calcul pour l'analyse formelle de la complexité algorithmique.
Chapitre 6 : Programmation dynamique. Principe d’optimalité de Bellman "toute solution optimale s'appuie elle-même sur des sous-problèmes résolus localement de façon optimale” et nous décrivons un processus en 4 étapes pour la conception d’algorithmes par programmation dynamique: structure d’une solution optimale, définition récursive d’une solution optimale; calcul de la valeur de la solution optimale et calcul effectif de la solution optimale;
Les chapitres 3) sur les Tris et 5) sur l'algorithmique gloutonne sont écartés par manque de temps.
Description des TP
- TD : Inférence inductive
- TD : Preuve d’arrêt d’un algorithme
- TD : Invariant d’algorithme
- TD : Programmation dynamique.
. TP consacrés à la programmtion dynamiqe
Connaissances requises
Pré requis :
- Maitrise des types de données abstraits (définition, implémentation);
- Maitrise des concepts algorithmiques (variable, type, strcuture de contrôles);
- Savoir concevoir un algorithme pour répondre à un problème donné;
- Maitrise de l'algorithmique récursive.
RSE (Responsabilité Sociale et Environnementale)
Bibliographie
-
[HMU] Introduction to Automata Theory, Langage and Computation J.E. Hopcroft, R. Motwani, J.D. Ullman Edition Adison Wesley 2001;
-
[CLM] Introduction à l’algorithmique,
T. Cormen, C. Leiserson, R. Rivest, Edition Dunod 2010;