Introduction à l'algorithmique (année 2017-2018)
Vous trouverez sur cette page quelques ressources pédagogiques liées à l'enseignement de l'algorithmique. Ces ressources sont utilisées dans le cadre du cours d'algorithmique que j'enseigne à l'ENS Rennes pour les étudiants de L3 Informatique et L3 Mathématiques (option).
Cours 1 : Analyse des algorithmes - terminaison et preuve
- Définitions
- Problème de la connectivité dynamique
Cours 2 : Analyse des algorithmes - complexité
- Problème de la connectivité dynamique (suite)
- Algorithmes de tri
Cours 3 : Recherche dans une collection (1/2)
- Solutions simples en temps linéaire
- Arbres binaires de recherche
Expérience illustrant le fait qu'en moyenne, la hauteur d'un arbre binaire de recherche généré aléatoirement a une croissance logarithmique en fonction du nombre d'éléments qui le composent (preuve en TD). Chaque réalisation de l'expérience a été obtenue en tirant aléatoirement un entier \(n\) uniformément entre 1 et 100, puis en tirant aléatoirement une permutation de \(\{1,\ldots, n\}\) ; les éléments de la suite ainsi générée ont été ajoutés séquentiellement à l'arbre vide en utilisant la procédure d'ajout aux feuilles vue en cours. On montre dans cette animation 1000 réalisations de cette expérience, et pour chaque réalisation on reporte sur un graphe la taille de l'arbre en abscisse, et sa hauteur en ordonnée.
Cours 4 : Recherche dans une collection (2/2)
- Arbres binaires de recherche équilibrés (arbres AVL)
- Tables de hachage
Cours 5 : Parcours de graphes et applications (1/3)
- Définitions et implémentations
- Parcours en profondeur, parcours en largeur
Cours 6 : Parcours de graphes et applications (2/3)
- Propriétés du parcours en profondeur
- Détection des cycles dans un graphe
- Tri topologique
- Calcul des composantes fortement connexes
Cours 7 : Parcours de graphes et applications (3/3)
- Propriétés du parcours en largeur
- Plus courts chemins à origine unique
Cours 8 : Problème du flot maximum
- Définitions : Réseau, flot et coupure
- Algorithme de Ford-Fulkerson
- Problème dual : coupure minimum
Test de la stratégie gloutonne (solution non optimale)
Transparents de cours
Sujet du TD8
Cours 9 : Algorithmes gloutons
- Étude d'exemples
- Algorithmes de Prim et de Kruskal pour le calcul d'abre couvrant de poids minimal
Cours 10 : Programmation dynamique
- Approche ascendante
- Approche descendante (récursive) avec recensement
- Application 1 : parenthésage optimal du produit en cascade de matrices
- Application 2 : plus longue sous-séquence commune de chaînes de caractères
- Application 3 : plus courts chemins dans un graphe orienté pondéré (algorithme de Floyd-Warshall)
Sujet du TD10
Sujet du TD11 (sujet « bonus »)
Révisions
Ce cours et le matériel proposé sur cette page est le fruit du travail de nombreuses personnes, que je tiens à remercier. J'y apporte ma modeste contribution.
