Algorithms and data structures

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

vendredi 20 septembre 2019	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++.
mardi 24 septembre 2019	Tri fusion. Tri rapide. Fonctions d'ordre supérieures. Rappel sur la récursivité. Code source du projet
lundi 30 septembre 2019	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.
mardi 8 octobre 2019	Implémentation en Python ou C++ : algorithme de Dijkstra et tas.
mardi 15 octobre 2019	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 22 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