L'unité d'enseignement « Types et structures de données » est une UE de niveau (200) approfondissement relevant de la licence d'informatique. Elle possède un volume de 6 ECTS et s'étend sur 12 semaines. Elle est placée sous la responsabilité de Gonzales, christophe.

Description

Deuxième étape classique de l'apprentissage du programmeur, ce cours est orienté vers la définition et la manipulation de structures de données.

On s'intéressera aux structures de données devenues classiques en programmation : enregistrements, n-uplets, listes, tables, arbres, tables de hachage.

On étudiera leur mise en oeuvre, dans un langage fortement typé, aussi bien du point de vue fonctionnel qu'impératif, et l'on caractérisera les situations dans lesquelles telle ou telle structure est plus adaptée qu'une autre.

Préalables et buts pédagogiques

Bibliographie

• A. V. Aho, J. E. Hopcroft, J. D. Ullman. "Data Structures and Algorithms". Addison-Wesley, 1985

• C. Froidevaux, M-C. Gaudel, M. Soria. "Types de données et algorithmes". McGraw-Hill Paris, 1990

• C. Cormen, C. Leiserson, R. Rivest, "Introduction à l'algorithmique". Dunod, 1994

• voir aussi la bibliographie de la page Caml de l'INRIA en:

Contenu indicatif par semaine

1. Eléments de langage et types de base. La notion d'environnement en programmation fonctionnelle

2. Les fonctions et les exceptions

3. Les fonctions récursives. Le polymorphisme

4. Types pour la programmation impérative I : les tableaux et les n-uplets

5. Types pour la programmation impérative II : les références et les tableaux

6. Les listes

7. Types somme/union

8. Approfondissements sur les listes

9. Les piles et les files

10. Les arbres binaires et les arbres binaires de recherche

11. Les arbres n-aires, les arbres équilibrés (AVL). Les tas

12. Les tables de hachage