Cette page accompagne la premiè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 2026
- 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
15 septembre 2026
- 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)
17 septembre 2026
- construction d'un tas binaire en O(n)
- tas binomiaux
- complexité amortie
- exemple de la file avec deux piles
24 septembre 2026
- insertion dans un tas binomial en temps amorti O(1)
- tas de Fibonacci
1er octobre 2026
- rappel tri fusion
- tri rapide
- complexité en moyenne dans le cas du pivot aléatoire
- quick select
8 octobre 2026
Cours annulé pour cause deblocage de l'ENS Paris-Saclay. Voir la feuille type TD sur les arbres a-b