Algorithms and data structures

Agrégation SCIF - ENS Rennes - Année 2022/2023

Séance 1	Mariages stables Algorithme de Gale-Shapley. Justification du fonctionnement Discussion sur l'implémentation.tableau et liste chaînée.
Séance 2	Initiation à Python, récursivité
Séance 3	Arbres Arbres, algorithme de parcours. Arbres binaires de recherche
Séance 4	Type abstrait "Ensemble" Type abstrait. Exemple d'un ensemble. Motivation : vérifier qu'un tableau contient A et -A. Arbres binaires de recherche, table de hachage. Discussion autour d'une file de priorité.
4 séances	Projet de programmation par groupes de 3

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