Algorithmique
Objectifs
- Découverte de l'analyse de complexité des algorithmes
- Structures de données usuelles, via l'étude d'algorithmes et de structures de données classiques
- Focus particulier sur les tas binaires et leurs applications
Plan du cours
- Complexité en temps : analyse d'algorithmes itératifs et récursifs classiques (algorithmes de recherche, algorithmes de tris quadratiques)
- Notations de complexité asymptotiques : grand O, Omega, Theta
- Principe algorithmique "diviser pour régner" : analyse récursive d'algorithmes (étude d'exemples : recherche dichotomique, tri par fusion, etc)
- Algorithmes de programmation dynamique : formulation inductive de problèmes d'optimisation, principes de la programation dynamique (étude d'exemples : calcul des nombres de Fibonacci, rendu de monnaie, sac à dos, etc)
- Structures de données usuelles et complexité de leurs opérations : tableaux, listes chaînées et leurs variantes
- Tas binaires, implémentation, complexité, HeapSort, Utilisation dans Dijkstra.
Description des TP
TP de découverte de la programmation dynamique (problèmes de rendu de monnaie et du sac à dos)
Connaissances requises
Programmation impérative.
RSE (Responsabilité Sociale et Environnementale)
Bibliographie
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms. MIT press.