Algorithms and data structures

Agrégation SCIF - ENS Rennes - Année 2018/2019

mardi 18 septembre 2018	Algorithme de Graham pour calculer l'enveloppe convexe Type abstrait VS implémentation. Pile. Implémentation avec un tableau, une liste chaînée. Tri insertion et sélection. Implémentation en Python et/ou C++.
mercredi 26 septembre 2018	Tri fusion. Tri rapide. Fonctions d'ordre supérieures. Rappel sur la récursivité. Code source du projet
vendredi 5 octobre 2018	Plus court chemin Graphe comme type abstrait. Implémentation : matrices d'adjacence et liste d'adjacence. Algorithme de Dijkstra File de priorité. Implémentations : tas.
jeudi 11 octobre 2018	Implémentation en Python ou C++ : algorithme de Dijkstra et tas.
vendredi 19 octobre 2018	Implémentation de Dijkstra en C++ Tas mémoire. Mutable et immutable. Rappels sur les pointeurs. Représentation des nombres entiers (mots sur 32, 64 bits, grands entiers). Représentation des flottants. Discussion sur compilation et interprétation. Génération de labyrinthes Algorithme randomisé (variante de l'algorithme de Kruskal). Type abstrait "relation d'équivalence". Structure de données union-find.
vendredi 26 octobre 2018	Implémentation en Python ou C++.

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