ALGO-AGREG

ENS Rennes - Année 2014/2015

Vendredi 25 septembre 2015, 13h30-15h30	Diviser pour régner Théorème fondamental: démonstration Multiplication de nombres : algorithme de Karatsuba Multiplication de polynomes, FFT Pour aller plus loin (vraiment hors programme) : multiplication de nombres avec la FFT
Vendredi 9 octobre 2015, 13h30-15h30	Diviser pour régner (suite et fin) Points les plus rapprochés, fait par un élève démonstration Programmation dynamique Principe : exemple du calcul de la longueur d'une plus longue sous-suite croissante Calcul d'une solution : exemple du calcul d'une plus longue sous-suite croissante Virtuosité pour définir des sous-problèmes : Floyd-Warshall et Bellman-Ford
Vendredi 16 octobre 2015, 13h30-15h30	Programmation dynamique (suite et fin) Sac à dos et mémoïzation (fait par un élève) Bellman-Ford (fin) Parcours en profondeur Rappel sur le parcours en profondeur Exemple pour le tri topologique Exemple pour l'algorithme de Kosaraju Correction de l'algorithme de Kosaraju
Mardi 3 novembre 2015, 13h30-15h30	Parcours en largeur Rappel sur le parcours en largeur Algorithme de Dijstra Démonstrations de correction Algorithme de Kruskal Algorithme : correction Union-find : sans et avec compression de chemins
Vendredi 6 novembre 2015, 13h30-15h30	Analyse de complexité de la compression de chemins présenté par un élève. Document union-find Algorithme de Prim Même squelette que Dijkstra Quelques éléments sur la correction pour Kruskal et Prim (arêtes sûres) Tables de hachage Poly sur les tables de hachage (brouillon) Types abstraits "Ensemble", "Dictionnaire". Vecteurs de bits Fonctions de hachage, Alvéoles, Collisions, Résolution des collisions par chaînage. Hypothèse du hachage uniforme simple. Opérations en O(1+alpha)
Mardi 17 novembre 2015, 13h30-15h30	Tables de hachage (suite) Hypothèse du hachage uniforme simple : nb de collisions Hachage universel Hachage parfait Arbres binaires de recherche Poly sur les ABR (brouillon) Rappel du fonctionnement Equilibrage AVL B-arbres et arbres rouge/noir
Vendredi 24 novembre 2015, 13h30-15h30	Analyse amortie Au choix : Flots dans les graphes ABR (avec équilibrages AVL ? B-arbres ? arbres rouge/noir ? Tables de hachage Complexité en moyenne (tri rapide) Analyse amorti ? Algorithmes d'approximation Algorithmes probabilistes, local search ?

Programme officiel

Programme (p. 11-12)

Références

• Introduction à l’algorithmique, T. H. Cormen, C. E. Leiserson, R. L. Rivest, Dunod. (une référence, couvre beaucoup de choses, un peu lourd et quelques erreurs)
• Algorithms de S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. (couvre l'essentiel, une approche intéressante et concise)
• Algorithms, R. Sedgewick, Addison-Wesley.
• Éléments d’algorithmique, D. Beauquier, J. Berstel, Ph. Chrétienne, Masson. (merci aux auteurs de donner le livre sur Internet)
• Types de données et algorithmes, C. Froidevaux, M.-C. Gaudel, M. Soria, McGraw-Hill-InterEditions. (intéressant pour les structures de données)
• Algorithmics, The Spirit of Computing. David Harel. (une façon originale de présenter le paysage des algorithmes : "les limites", "relâcher les règles (parallélisme, proba)", "algorithme dans la création de logiciels")
• Algorithm design, Jon KIeinberg et Eva Tardos. (ouvrage riche en bons exemples) http://www.aw-bc.com/info/kleinberg/index.html
  

Autre cours sur internet

• http://www.algorist.com/
• Programmation efficace à l'école polytechnique pour le concours ICPC
• http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/
• Un site avec des animations d'algorithmes