Christiane Frougny

Université Paris 8

Licence d'Informatique - L3 : Algorithmique Avancée

1er semestre 2009-2010

Algorithmes de recherche

Types et structures de données. Complexité. Listes, piles, queues. Arbres. Problèmes de recherche : méthodes élémentaires. Hachage. Arbres binaires de recherche. Méthodes avancées de représentation des ensembles : queues avec priorité, arbres lexicographiques, arbres AVL, arbres a-b, B-arbres. Recherche sur fichiers.

Notes de cours

Listes.

Recherche dichotomique.

Arbres.

Queues avec priorité.

Arbres binaires de recherche.

Hachage ouvert.

Bibliographie

Aho, Hopcroft, Ullman : Structures de données et algorithmes, InterEditions.

Beauquier, Berstel, Chrétienne : Eléments d'algorithmique, Masson. Téléchargeable ici.

Cormen, Leiserson, Rivest : Introduction à l'algorithmique, Dunod.

Froidevaux, Gaudel, Soria : Types de données et algorithmes, Mc Graw-Hill.

Sedgewick : Algorithmes, InterEditions.

Dasgupta, Papadimitriou, and Vazirani : Algorithms. Téléchargeable ici.

Trouvé sur le web

Cours en ligne de l'EnsiCaen : Téléchargeable ici.

Cours Université de Marne-la-Vallée : Arbres. Hachage. Arbres AVL. B-arbres.

Open Course du MIT : Introduction to Algorithms.

Cours de l'Ecole Polytechnique : Téléchargeable ici.

Contrôle des connaissances

Examen écrit dont la note compte pour 60% de la note finale : 26 janvier 2010.

Projet obligatoire. La note compte pour 40% de la note finale. A rendre le 26 janvier 2010. Téléchargeable ici.

RESULTATS 1e session.

Deuxième session le 26 mai de 12h à 14h réservée aux étudiants inscrits au 1er semestre. RESULTATS 2e session.