Université Paris 7 ECUE LI012

LI 012 : Algorithmes et Structures de données

La conception de programmes informatiques de qualité nécessite aussi bien un travail sur l'organisation des actions, leur contrôle (algorithmique) qu'un travail sur les données : leur mode de codage, de stockage, représentation, etc. (structures de données).

L'objectif du cours est d'aborder ces deux aspects de la conception, en étudiant quelques grandes classes de problèmes identifiés et leurs solutions.

On s'intéressera dans chaque cas aux différentes méthodes de résolution de problème, en évaluant ces méthodes selon différents point de vue : efficacité (coût de stockage et de calcul), lisibilité, généralité, ré-utilisabilité…

Emploi du temps

Horaires :	Mardi, de 12:00 à 14:00
Salle :	305, Barre 24-34, 3e
Rythme :	Semestriel (S2)
Premier cours	Mardi 12 Février

Modalités de contrôle

Contrôle continu
Un DST (30%), un DNS (20%), et un partiel en fin de semestre (50%)
Contrôle terminal
Un examen en fin de semestre (100%)

Plan (sommaire et indicatif) du cours

Les mots : algorithmes de recherche de facteurs.
- Exercices
- Polycopié(s) aux formats PS ou PDF
Les tris : algorithmes standards, en nlogn, récursifs.
- Exercices
- Polycopié(s) : Maximier (PS, PDF) ; Tri rapide (PS, PDF)
Structures linéaires (1) :
- Exercices
- Polycopié(s) : Code complet implémentation chaînée par curseur (PS, PDF, TXT)
Structures linéaires (2) : piles, files, etc.
- Exercices
- Polycopiés : exemples d'utilisation de pile : manipulation d'expressions arithmétiques (PS, PDF) ; code C implémentation pile d'entiers chaînée par tableau (PS, PDF, TXT)
Structures non linéaires (1) : les arbres.

Contrôles

Devoir non surveillé n° 1 : distribué le 12 Mars, pour le 30 avril.
- Sujet au format PostScript ou PDF.
- Notes
Devoir sur table n° 1 : mardi 02 avril, horaire et salle habituels
Sans documents autorisés.
- Sujet au format PostScript ou PDF.
- Corrigé au format PostScript, PDF.
- Exemple en C pour l'exercice 3.
- Notes
Examen final (pour tous les étudiants) : session de juin.
- Sujet au format PostScript ou PDF.
- Corrigé au format PostScript, PDF.
- Notes

Bibliographie

Présents à la bibliothèque de l'UFRL (réserve), le premier est un grand classique

Niklaus Wirth : Algorithmes et Structures de données, Eyrolles, 1987.
Alfred Aho, John Hopcroft, Jeffrey Ullman : Structures de données et algorithmes, InterEditions, 1989.
Ellis Horowitz, Sartag Sahni : Fundamentals of Computer Algorithms, Pitman, 1978.
Un des plus proches du contenu du cours
Jacques Courtin, Irène Kowarski : Initiation à l'algorithmique et aux structures de données (2 volumes), Dunod, 1994-95.
Les ouvrages de référence les plus récents, très complets
Thomas Cormen, Charles Leiserson, Ronald Rivest : Introduction à l'algorithmique, Dunod 1994 (version anglaise 1990).
Danièle Beauquier, Jean Berstel, Philippe Chrétienne : Éléments d'algorithmique, Masson, 1992.
Aho Alfred V. et Jeffrey D. Ullman : Concepts fondamentaux de l'informatique, Dunod, 1992.

http://www.linguist.jussieu.fr/~amsili/Ens/LI012.html lun jui 8, 2002