011_Kmag

Les types de données abstraits


Version de

Dans cette deuxième partie, nous allons étudier quelques structures de données utilisées de façons intensives en informatique. Il s’agit de gérer des ensembles de données dont le nombre n’est pas fixé a priori. On ne s’intéresse pas aux éléments de l’ensemble considéré mais plutôt aux <em>méthodes</em> de gestion de ces éléments. L'<em>analyse du domaine</em> sert à décomposer les objets réels complexes et leurs interrelations en objets et relations plus simples. Par exemple l’objet « plan d’une maison » se décompose en plans des différents étages et des façades, qui eux-mêmes se décomposent en murs, portes, fenêtres, etc. L’abstraction des données va dans l’autre sens. À partir des objets informatiques de base (types prédéfinis, tableaux, enregistrements, pointeurs) on construit des objets plus abstraits (listes, ensembles, …) qui servent eux-mêmes à construire des objets encore plus abstraits (graphes, dessins, …). Jusqu’à ce qu’on arrive au niveau où il devient simple de représenter les objets du réel que l’on considère.

Définition de types de données

La définition d’un nouveau type de donnée, c.-à-d. d’une nouvelle abstraction, consiste à définir l’ensemble des valeurs possibles pour les objets de ce type et l’ensemble des opérations de traitement de ces valeurs. La gestion des ensembles doit, pour être efficace, respecter au mieux deux critères parfois contradictoires : un minimum de place mémoire utilisée (cf. page Complexite} et un minimum d’instructions pour réaliser une opération. Pour bine faire, la place mémoire utilisée devrait être voisine du nombre d’éléments de l’ensemble multiplié par la taille d’un élément. Pour accueillir les valeurs du type il est nécessaire de définir une structure interne de données construite à partir des types de base du langage et/ou des types déjà définis. Les opérations seront définies par des procédures ou fonctions du langage de programmation.
011_Kmag