Les types abstraits de données

Sommaire du document

Un type abstrait de données(ou ADT pour Abstract Data Type) permet de grouper des éléments qui ont des caractéristiques communes et des comportements identiques. Toutes les opérations définies pour ce type abstrait peuvent s'appliquer à n'importe quel élément de ce type.

Par exemple, nous pouvons définir le type abstrait animal qui spécifierait que chaque animal peut se déplacer. Dans notre ensemble, nous pouvons avoir des chiens, des oiseaux, des poissons, des hommes, etc. Chien, oiseau, etc. sont les types concret des éléments, alors qu'ils correspondent tous au type abstrait animal..

Le type abstrait animal nous assure que nous pouvons demander à chaque élément de se déplacer, mais il est possible que le déplacement dépende du type. En effet, les chiens marchent à quatre pattes, les hommes sur leurs deux pieds (quand ils sont sobres), les oiseaux utilisent leurs ailes et les poissons leurs nageoires.

Avantages des types abstraits

• Abstraction et modifiabilité : l'abstraction masque l'implémentation réelle du type. Ceci permet au programmeur qui utilise le type abstrait de ne pas devoir se préocuper de la complexité mise en œuvre dans l'implémentation, ni de devoir modifier son code en cas de modification de l'implémentation.
• Encapsulation : les données internes nécessaires à la réalisation des opérations sont masquées et ne sont normalement pas accessibles.
• Réutilisation : les types abstraits sont largement utilisés dans un grand nombre de programmes du fait de ces avantages.

Comment définir un type abstrait ?

Nous avons vu dans notre exemple que le type abstrait possédait un nom (animal), qu'il permettait certaines opérations (se déplacer).

Voici la liste complète de ce que nous avons besoin pour définir un type abstrait:

• Le nom du type (Pile, File, Liste, ArbreBinaire)
• Les opérations que nous pouvons effectuer sur ou avec ce type abstrait.
• Les pré-conditions de chaque méthode, opération. Elles déterminent les conditions à respecter pour qu'une opération puisse être effectuée et produise le résultat escompté.
• Les axiomes. Ils décrivent le comportement des opérations du type abstrait.

Nous pouvons déterminer les propriétés d'un type abstrait de différentes manières : par modèles, par axiomes

Donner les propriétés d'un type abstrait par modèles

• Nous devons fournir une "implémentation" abstraite basée sur les ensembles
• Les sous-programmes sont spécifiés par les pré et post-conditions
• Nous devons définir un invariant de représentation R entre le type abstrait et le type concret tel que
  ∀a ∈(type abstrait), ∃c ∈(type concret) : A(a, c)
  L'invariant de représentation peut aussi porter le nom d'invariant d'abstraction ou d'invariant de collage.
  L'invariant de données décrit la partie des données concrètes utilisées

Exemple de type abstrait "Liste"

Notre liste est définie par un ensemble ordonné d'éléments de même type. Chaque élément est défini par une valeur (la donnée, d'un certain type -entier, caractère, etc.) et un indice (la position dans la liste par rapport au premier élément).

Nous spécifions en outre les propriétés suivantes :

• Nous ne pouvons avoir deux valeurs pour un même indice
• Les indices sont numérotés de 1 à n

Par exemple, la liste d'entiers(4, 4, 4, 7, 1, 9) est représentée par l'ensemble {(1,4), (2,4), (3,4), (4,7), (5,1), (6,9)} où (1,4) représente le premier élément avec l'indice 1 et la valeur 4.

Notre définition du type Liste s'appliquera autant à une implémentation de type Tableau (pour lequel nous pouvons directement accéder à l'élément en spécifiant son indice, mais dont le nombre de positions est fixe) qu'à une implémentation de type ListeChaînée (nous devons parcourir tous les éléments qui précèdent avant d'accéder à l'élément, mais la taille de ListeChaînée dépend du nombre d'éléments que nous ajoutons).

Nous pouvons définir une série d'opérations qui seront toujours applicables sur n'importe quelle implémentation de notre Liste :

• listeVide() construit une instance de type Liste qui ne contient aucun élément
• cons(val, list) construit une nouvelle instance de type Liste avec pour premier élément elem (la valeur val au premier indice), suivi des éléments de l'instance liste
• head(liste) nous retourne le premier élément de la liste
• tail(liste) nous retourne tous les éléments de la liste qui suivent le premier
• estVide(liste) nous retourne vrai si la liste ne contient aucun élément, et faux dans le cas contraire.
• concat(liste1, liste2) nous retourne une nouvelle instance de type Liste qui contient tous les éléments de l'instance liste1 suivis de ceux de liste2.

Exemple de définition de notre type abstrait "Liste" par modèles

Type Liste = P(N * elem)
tel que

• val : (0,val) ∈ liste
  = il n'existe pas de valeur à l'indice 0
• i, val₁, val₂ : (i, val₁) ∈ liste et (i, val₁) ∈ liste et val₁ ≠ val₂
  = il ne peut y avoir plus d'une valeur pour un indice
• ∀(i, val) ∈ liste, i > 1 ⇒ ∃val₂ : (i-1, val₂) ∈ liste
  = pour tout couple (d'indice i et de valeur val) appartenant à l'ensemble liste, avec i supérieur à 1, il existe un couple à l'indice i-1 appartenant à liste et comporant une autre valeur (qui peut être identique car nous travaillons avec des ensembles). Ceci revient à déclarer que les indices sont numérotés de 1 à maximum le nombre d'éléments de la liste.

fonction listeVide : Liste
post-condition : listeVide = {}

fonction cons(val : T, liste Liste<T>) : Liste<T>
la valeur de l'élément est de type T car tous les éléments de la liste sont de même type
post-condition : cons(val : T, liste Liste<T>) = {(1, val)}∪{i + 1, val₂) | (i, val₂) ∈ liste }
= la nouvelle liste correspond au couple représenté par l'indice 1 et l'élément elem de type T, uni au reste de la liste passée en argument. Ce qui revient à dire que notre nouvelle liste contient elem en première position, suivi par les éléments de la liste de départ.

fonction head(liste : Liste) : T
pré-condition : liste ≠{}
= la liste n'est pas vide, ce qui peut aussi s'écrire ∃val : (1, val) ∈ liste
post-condition : head = val ⇐ (1, val) ∈ liste
= la fonction head retourne la valeur pour autant que cette valeur se trouve à la première position de la liste

fonction tail(liste : Liste) : Liste
pré-condition : liste ≠{}
post-condition : tail = {(i, val) | (i + 1,val) ∈ liste et i ≥ 1}
= la nouvelle liste retournée est l'ensemble des éléments (couples indice/valeur de la liste passée en argument) sauf le premier élément.

fonction estVide(liste : Liste) : boolean
post-condition : estVide = (liste = {})

fonction concat(liste1, liste2 : Liste) : Liste
post-condition : concat = liste1 ∪{maxL1 + i, val) | (i, val) ∈liste2, maxL1 = #liste1
= la nouvelle liste retournée est l'union des éléments de liste1 et de liste2, avec une correction des indices des éléments de liste2 pour lesquels on ajoute le nombre d'éléments de liste1 (ce qui correspond dans notre cas à l'indice du dernier élément de liste1 => les éléments de liste2 se trouvent après ceux de liste1 dans la nouvelle liste).

Définir un type abstrait par axiomes

Les axiomes sont en quelque sorte des vérités sur lesquelles nous pouvons nous baser pour définir et prouver les différentes fonctions et procédures de notre type abstrait.

Pour les fonctions (en partant du principe qu'elles n'induisent pas d'effet de bord, c'est à dire qu'elle ne modifient pas les variables extérieures), nous pouvons employer la logique de premier ordre.

Pour les procédures, nous devons ajouter la logique dynamique suivante : [Prog] Formule qui signifie "après toute exécution de Prog, Formule est vraie".

Afin de nous assurer d'avoir suffisament d'axiomes pour définir un type abstrait (complétude), nous pouvons procéder de deux manières : en employant la méthode des constructeurs, ou la méthode des observateurs. Dans un cas comme dans l'autre, nous allons associer des opérations, et nous devrons vérifier que leur combinaison est possible du point de vue des types, et qu'elle ait un sens.

Méthode des constructeurs

Nous devons choisir un sous-ensemble "Constructeurs" constitué par les opérations qui permettent de construire toutes les valeurs du type abstrait.
Par exemple Constructeurs : {listeVide, cons}

Nous pouvons utiliser une fonction qui prend en argument le(s) constructeur(s) que nous désirons définir, selon la formule suivante :
n(c₁(...), c₂(...)) = e
pour laquelle
- n est une fonction non constructeur
- c₁ et c₂ sont des constructeurs
- e est une expression plus simple
Par exemple head(cons(val, liste)) = val

Nous pouvons ensuite utiliser les relations qui existent entre les constructeurs selon la formule suivante :
c₁(c₂(...)) = e
Par exemple cons(val, listeVide())) = {val}

Exemple d'axiomes du type abstrait "Liste" par la méthode des constructeurs

Constructeurs : {listeVide, cons}


head(listeVide()) = indéfini (de plus, ne remplit pas les pré-conditionsde head)

head(cons(val, liste) = val

tail(listeVide()) = indéfini (de plus, ne remplit pas les pré-conditionsde tail)

tail(cons(val, liste)) = liste

estVide(listeVide()) = true

estVide(cons(val, liste)) = false

concat(listeVide(), liste) = liste

concat(liste, listeVide()) = liste

concat(cons(val, liste), liste2) = cons(val, concat(liste, liste2)

Méthode des observateurs

Nous allons procéder de la même manière que pour les constructeurs, mais avec d'autres opérations. Nous pouvons donc commencer en sélectionnant d'abord un ensemble d'opérations qui nous permettront d'observer les différences entre 2 valeurs.
Par exemple Observateurs : {head, tail,estVide}

Nous allons ensuite écrire les différents axiomes, selon la formule suivante :
o(n(x)) = e...o(x)
pour laquelle
- n est une fonction non observateur
- o est un observateur
- e est une expression qui ne contient pas o(x)

Exemple d'axiomes du type abstrait "Liste" par la méthode des observateurs

Observateurs : {listeVide, cons}


head(listeVide()) = indéfini

head(cons(val, liste) = val

tail(listeVide()) = indéfini

tail(cons(val, liste)) = liste

estVide(listeVide()) = true

estVide(cons(val, liste)) = false

estVide(concat(liste1, liste2)) = estVide(liste1) et estVide(liste2)

head(concat(liste1, liste2)) =
    head(liste2) si estVide(liste1) = true,
    head(liste1)si estVide(liste1) = false

tail(concat(liste1, liste2)) =
    tail(liste2) si estVide(liste1) = true,
    concat(tail(liste1), liste2) si estVide(liste1) = false

Références

1. IHDCB331 - Méthodes de Programmation : PY Schobbens, Cours de Méthodes de Programmation (Septembre 2009)

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

Structure du document