Cette page accompagne la prmière partie du cours d'alorithmique 1 en L3 à l'ENS Paris-Saclay.
Évaluation
Le cours d'algorithmique 1 est en deux parties. La note finale est la moyenne des notes des deux parties. Pour la première partie, la note est obtenue en combinant
- la note du partiel: 60%
- les notes de contrôle continu (petits exercices à rendre en TD et cours): 40%.
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
10 septembre 2025
- Organisation d'informations données sous forme d'ensembles de couples (clé, valeur)
- Pourquoi trier?
- tri par comptage
- tri par base, bit de poids fort en premier (récursif)
- correction
- invariants de boucles
- pré/post conditions
16 septembre 2025
- tri par base, bit de poids faible en premier (itératif)
- tri par insertion
- tri par sélection
- tri par tas (vu comme implémentation efficace du tri par sélection)
- construction du tas binaire en O(n)
17 septembre 2025
- tas binomiaux
- complexité amortie
- exemple de la file avec deux piles
- insertion dans un tas binomial en temps amorti O(1)
24 septembre 2025
- tas de Fibonacci
- rappel tri fusion
1er octobre 2025
- tri rapide
- complexité en moyenne dans le cas du pivot aléatoire
- borne de complexité Omega(n log n) pour les tris par comparaisons
- quick select
8 octobre 2025
- B-arbres / arbres a-b