Informatique-réseaux : algorithmique
|
Marie-Pierre.Beal@univ-mlv.fr
Université de Marne-la-Vallée, septembre 2004
|
Présentation
L'objectif de ce cours est présenter les méthodes de base de la
programmation et les algorithmes élémentaires sur les
structures de données classiques.
Le cours commence par une introduction à l'algorithmique et contient une
revue des algorithmes de recherche et de classements.
Les têtes de chapitre sont : complexité asymptotique,
récursivité, classements (tri rapide),
types abstraits (liste, pile, file), hachage, arbres,
codage de Huffman, arbres binaires de recherche,
files de priorité (tri par tas), tri lexicographique.
|
Organisation
Première année : structures de données
- Dix cours de deux heures
Polycopié de Maxime
Crochemore
- Algorithmique (conception, preuve, complexité)
- Récurrence et récursivité
(aux formats pdf ou
ppt)
- Classements internes (tri rapide)
(aux formats pdf ou
ppt)
- Types abstraits de données (listes) (deux cours)
(aux formats pdf ou
ppt)
- Hachage
(aux formats pdf ou
ppt)
- Arbres (compression de texte) (deux
cours)
(aux formats pdf ou
ppt)
- Ensembles (arbres binaires de recherche) et files de priorités
(aux formats pdf ou
ppt)
- B-arbres
(aux formats pdf ou
ppt)
ou arbres AVL
(aux formats pdf ou
ppt)
- Tri lexicographique
(aux formats pdf ou
ppt)
- Tris externes
(aux formats pdf ou
ppt)
- Dix séances de Travaux Dirigés avec
Francesca Fiorenzi et Cyril Nicaud.
- Contrôle
- un examen ecrit (plus éventuellement
contrôles en cours) qui compte 1/2.
-
sujet du
contrôle 2, groupe 1,
corrigé.
-
sujet du
contrôle 2, groupe 2,
corrigé.
-
sujet de
l'examen,
corrigé
des exercices 2,3,4,5,
corrigé
des exercices 6,7.
- une note de contrôle continu en TD-TP (devoirs, projets, tps) qui compte 1/2.
|
Références principales
- H. Cormen, Charles E. Leiserson, Ronald L. Rivest,
Introduction à l'Algorithmique, Paris : Dunod, 1994.
-
S. Veigneau,
Approches impérative et fonctionnelle de l'algorithmique,
Springer-Verlag France, 1999.
-
D. Beauquier, J. Berstel et Ph. Chrétienne,
Éléments d'algorithmique,
Masson, 1992, 463 pages.
-
A.V. Aho, J.E. Hopcroft et J.D. Ullman,
Structures de données et algorithmes,
InterEditions, 1988.
|
|
Institut Gaspard-Monge,
Laboratoire d'informatique,
le 30 septembre 2002,
Marie-Pierre Béal
|