Types et abstraction

Notions	Commentaires
Type prédéfini (booléen, entier, flottant). Pointeur. Type paramétré (tableau). Type composé. Tableaux statiques. Allocation (malloc) et désallocation (free) dynamique.	On se limite à une présentation pratique des types, en les illustrant avec les langages du programme. Un étudiant est capable d’inférer un type à la lecture d’un fragment de code, cependant toute théorie du typage est hors programme.
Définition d’une structure de données abstraite comme un type muni d’opérations.	On parle de constructeur pour l’initialisation d’une structure, d’accesseur pour récupérer une valeur et de transformateur pour modifier l’état de la structure. On montre l’intérêt d’une structure de données abstraite en terme de modularité. On distingue la notion de structure de données abstraite de son implémentation. Plusieurs implémentations concrètes sont interchangeables. La notion de classe et la programmation orientée objet sont hors programme.
Distinction entre structure de données mutable et immuable.	Illustrée en langage OCaml.

Il s’agit de montrer l’intérêt et l’influence des structures de données sur les algorithmes et les méthodes de programmation.
On insiste sur la distinction entre une structure de données abstraite (un type muni d’opérations ou encore une interface) et son implémentation concrète. On montre l’intérêt d’une structure de données abstraite en terme de modularité. Grâce aux bibliothèques, on peut utiliser des structures de données avant d’avoir programmé leur réalisation concrète.