Algorithmes et structures de données avancées

Ce cours approfondit l’algorithmique pour des ingénieurs appelés à concevoir des systèmes qui doivent tenir la charge : un opérateur de mobile money qui traite des millions de transactions par jour, une plateforme d’e-gouvernement qui indexe l’état civil de tout un pays, une application logistique qui optimise des tournées entre Niamey, Dosso, Tahoua et Maradi. Il s’agit de savoir analyser rigoureusement le coût d’un algorithme, de choisir la structure de données adaptée (tas, table de hachage, arbre équilibré, B-arbre, graphe) et de concevoir des solutions efficaces à l’aide des grands paradigmes (diviser pour régner, glouton, programmation dynamique). Les TP se font en Python (ou Java) avec mesures expérimentales de performances.

Objectifs d’apprentissage

• Évaluer la complexité temporelle et spatiale d’un algorithme (notations O, Ω, Θ, analyse amortie) et résoudre des récurrences par le théorème maître.
• Choisir et justifier un algorithme de tri ou de recherche selon les données et contraintes.
• Implémenter et analyser tas, tables de hachage, arbres AVL, rouge-noir et B-arbres.
• Appliquer les algorithmes de graphes (BFS, DFS, tri topologique, Dijkstra, Bellman-Ford, Prim, Kruskal) à des problèmes réels.
• Concevoir des solutions par diviser pour régner, stratégie gloutonne et programmation dynamique, et prouver leur correction.
• Valider expérimentalement les analyses théoriques par des mesures.

Prérequis

Algorithmique et structures de données de licence (tableaux, listes, piles, files, arbres binaires, récursivité), mathématiques discrètes (logarithmes, sommes, raisonnement par récurrence), un langage de programmation.

Plan du cours

1. Leçon 1 — Complexité, récurrences, tri et recherche
2. Leçon 2 — Structures de données avancées : tas, hachage, arbres équilibrés et B-arbres
3. Leçon 3 — Algorithmes de graphes : parcours, plus courts chemins et arbres couvrants
4. Leçon 4 — Paradigmes de conception : diviser pour régner, glouton et programmation dynamique

Modalités d’évaluation

Volume horaire : 20 h de cours (CM), 10 h de TD, 10 h de TP, 40 h de TPE ; 4 crédits. Évaluation : contrôle continu (40 % : TP avec rapport de mesures, quiz, devoir) et examen terminal écrit (60 %).

Bibliographie

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, MIT Press (trad. française : Algorithmique, Dunod).
• Robert Sedgewick, Kevin Wayne, Algorithms, Addison-Wesley.
• Jon Kleinberg, Éva Tardos, Algorithm Design, Pearson.
• Donald E. Knuth, The Art of Computer Programming, vol. 1 et 3, Addison-Wesley.
• Steven S. Skiena, The Algorithm Design Manual, Springer.