Algorithmique
L3 Informatique parcours Math-Info, U. Grenoble Alpes
Cours
Le plan indiqué est prévisionnel et susceptible de modifications.
- Présentation du cours – Quiz d’auto-formation sur les preuves de correction par invariant.
Partie 1. Structures de données
- Types abstraits de données – structures linéaires : tableaux, listes, piles, files, files à priorité
- Arbres binaires et tas
- Tableaux dynamique et arbres binaires de recherche
- Tables de hachage
Partie 2. Techniques algorithmiques
(Les cours de cette partie ne sont pas encore disponibles, mais vous pouvez consulter ceux des années précédentes ci-dessous.)
- Diviser pour régner : principes, exemples du tri fusion et de l’algorithme de Karatsuba
- Recherche exhaustive : principes, exemples de Sat et du voyageur de commerce
- Algorithmes probabilistes : Monte Carlo et Las Vegas, exemples de la coupe minimale et du tri rapide
- Programmation dynamique : principes, exemples de la plus longue sous-suite croissante et de la distance d’édition
- Algorithmes d’approximation : principes, exemples de couverture par sommets, somme partielle, et équilibrage de charges
- Deux techniques avancées : recherche exhaustive rapide (3-Sat), diviser-pour-régner en programmation dynamique (distance d’édition)
Quelques lectures intéressantes
Années précédentes
Sujets de TD et d’examens
- LivretTD1 : partie 1 – structures de données
- LivretTD2 : partie 2 – techniques algorithmiques
- CC : Contrôle continu
- Examen : Examen
-
2025-2026
- LivretTD1 : partie 1 – structures de données
- LivretTD2 : partie 2 – techniques algorithmiques
- CC : Contrôle continu
- Examen : Examen
-
2024-2025
- TD1 : Types abstraits de données
- TD2 : Structures de données linéaires
- TD3 : Tableaux dynamiques et Arbres binaires de recherche
- TD4 : Tables de hachage
- TD5 : Diviser pour régner
- TD6 : Recherche exhaustive
- TD7 : Algorithmes probabilistes
- TD8 : Programmation dynamique
- TD9 : Algorithmes d'approximation
- TD10 : Recherche exhaustive rapide
- CC : Contrôle continu
- DM : Devoir à la maison
- Examen : Examen
-
2023-2024
- TD1 : Types abstraits de données
- TD2 : Structures de données linéaires
- TD3 : Tableaux dynamiques et Arbres binaires de recherche
- TD4 : Tables de hachage
- TD5 : Diviser pour régner
- TD6 : Recherche exhaustive
- TD7 : Algorithmes probabilistes
- TD8 : Programmation dynamique
- TD9 : Algorithmes d'approximation
- TD10 : Recherche exhaustive rapide
- CC : Contrôle continu
- DM : Devoir à la maison
- Examen : Examen
Bibliographie indicative
-
T. H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms. MIT Press, 3rd ed., 2009.
La bible de l’algorithmique, disponible en traduction française. Même si je n’adore pas le style de cet ouvrage, il faut bien reconnaître qu’il y a toute l’algorithmique classique dedans, et bien plus !
Disponible à la BU.
-
R. Sedgewick, K.Wayne. Algorithms. Addison-Wesley, 4th ed., 2011.
La nouvelle bible de l’algorithmique. Une approche beaucoup plus orientée pratique que le précédent.
Des versions précédentes, traduites en français, sont disponibles à la BU.
-
D. Beauquier, J. Berstel, Ph. Chrétienne. Éléments d’algorithmique. Masson, 1992.
Un excellent ouvrage d’algorithmique en français.
Disponible à la BU, et gratuitement sur la page de J. Berstel.
Les deux ouvrages suivants sont mes ouvrages préférés d’algorithmique. Malheureusement, ils ne couvrent pas la partie 1. Structures de données. Ne pas hésiter à les consulter pour la partie 2. Techniques algorithmiques.
-
J. Erickson. Algorithms. Self-published, 2019.
Mon ouvrage préféré d’algorithmique. Consulter également ses autres notes de cours, sur la même page, qui sont toutes excellentes.
Disponible gratuitement en ligne.
-
S. Dasgupta, C.H. Papadimitriou, U. Vazirani. Algorithms. McGraw-Hill Higher Education, 2006.
Mon autre ouvrage préféré d’algorithmique ! Concis et efficace.
Dernière modification : 7 septembre 2026