Thomas Chatain Algorithmique 1
(L3 ENS Paris-Saclay)
Références
- Thomas Cormen, Charles Leiserson, Ronald Rivest. Introduction à l'algorithmique. Dunod (Il existe plusieurs éditions, en anglais et en français)
- Danièle Beauquier, Jean Berstel, Philippe Chrétienne. Eléments d'algorithmique. Masson, 1992.
- Christoph Dürr, Jill-Jênn Vie. Programmation efficace - 128 algorithmes qu’il faut avoir compris et codés en Python au cours de sa vie. Ellipses. ISBN : 9782340010055
9 septembre 2024
- Organisation d'informations données sous forme d'ensembles de couples (clé, valeur)
- Pourquoi trier?
- tri par comptage
- tri par base
- bit de poids faible en premier (itératif)
- bit de poids fort en premier (récursif)
- correction
- invariants de boucles
- pré/post conditions
11 septembre 2024
- tri par insertion
- tri par sélection
- tri par tas (vu comme implémentation efficace du tri par sélection)
18 septembre 2024
- construction du tas binaire en O(n)
- tas binomiaux
25 septembre 2024
- complexité amortie
- exemple de la file avec deux piles
- tas de Fibonacci
2 octobre 2024
- tris basés sur le paradigme diviser pour régner
- tri fusion
- tri rapide
- complexité en moyenne dans le cas du pivot aléatoire
- borne de complexité O(n log n) pour les tris par comparaisons
9 octobre 2024
- quick select
- arbres binaires de recherche
- B-arbres / arbres a-b
16 octobre 2024
- union-find
- tables de hachage
