Introduction à l'algorithmique (année 2018-2019)
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. Les travaux dirigés sont assurés par Antoine Chatalic. Ce cours est très fortement coordonné avec le cours d'algorithmique enseigné aux étudiants de L3 Mathématiques, par Francois Schwarzentruber.
Vous pouvez accéder au cours de l'année précédente.
Bibliographie
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2001). Introduction à l’algorithmique, deuxième édition edn.
- Dasgupta, S., Papadimitriou, C. H., & Vazirani, U. V. Algorithms. 2007.
- Sedgewick, R. Algorithms in C. 1990.
Cours 1 : Introducion, Analyse des algorithmes
- Type abstrait et structure de données
- File de priorité et tas binaire
- Étude de cas : le tri par tas
- Optimalité (nombre de comparaisons) du tri par tas
Cours 2 : Recherche dans une collection
- Structure de données linéaire
- Table de hachage (fonction de hachage, gestion des collisions)
- Arbre binaire de recherche (rappels, complexité dans le cas moyen)
- B-arbres
Cours 3 : Diviser pour régner
- Théorème principal pour le calcul des récurrences
- Algorithme de Karatsuba pour la multiplication de grands nombres
- Multiplication de matrices (algorithme de Strassen)
- Transformée de Fourier rapide pour la multiplication de polynômes
Cours 4 : Parcours de graphes — applications du parcours en profondeur
- Parcours en profondeur
- Détection de cycles
- Tri topologique
- Composantes fortement connexes
Cours 5 : Plus courts chemins dans un graphe
- Parcours en largeur
- Algorithme de Dijkstra
Cours 6 : Algorithmes gloutons
- Calcul d'un arbre couvrant de poids minimal (algorithmes de Kruskal et de Prim)
- Satisfiabilité des clauses de Horn
- Couverture minimale d'ensemble
Cours 7 : Programmation dynamique
- Parenthésage optimal pour la multiplication d'une séquence de matrices
- Plus longue sous-séquence croissante
- Plus courts chemins dans un graphe orienté (algorithmes de Floyd-Warshall et de Bellman-Ford)
Cours 8 : Réseaux de flots
- Théorème de flot maximal - coupe minimale
- Algorithme de Ford-Fulkerson
- Réduction du couplage parfait au problème de flot maximum
Cours 9 : Programmation linéaire
- Forme standard et forme canonique
- Algorithme du simplexe
- Réduction du problème du plus court chemin dans un graphe à la programmation linéaire
Cours 10 : Problèmes « de recherche »
- Recherche exhaustive maligne (backgtracking et branch-and-bound)
- Recherche locale (recuit simulé)
Devoir maison
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.
