ALGO1 : Introduction à l'algorithmique
Licence 3 d'informatique (parcours recherche) et
magistère de Mathématiques de
Rennes - ENS Rennes - Année 2020/2021
Intervenants
Cours :
François
Schwarzentruber
Travaux dirigés :
Léo Henry
Raphaël Truffet
Fiches de cours
Complexité
ALGO1 -- Cours d'introduction -- Problème des mariages stables
Types Abstraits et Structures de Données Basiques
ALGO1 -- File de priorité et tas binaire
ALGO1 -- Tas binomiaux
Arbres binaires de recherche et équilibrage
ALGO1 -- Table de hachage
ALGO1 -- Diviser pour régner
ALGO1 -- Parcours en profondeur
ALGO1 -- Parcours en largeur
ALGO1 -- Tas de Fibonacci
ALGO1 -- Un algorithme glouton : l'algorithme de Kruskal
ALGO1 -- Union-find
ALGO1 -- Programmation dynamique
ALGO1 -- Flots
ALGO1 -- NP-complétude
Examens des années précédentes
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