Les types abstraits de données

Contents

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.

Contents Haut

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.

Contents Haut

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

Contents Haut

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.

Contents Haut

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).

Contents Haut

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

Note

Nous avons utilisé estVide qui est un constructeur de booleen. Il s'agit d'une opération induite (l'opération est intégrée dans la définition).

English translation

You have asked to visit this site in English. For now, only the interface is translated, but not all the content yet.

If you want to help me in translations, your contribution is welcome. All you need to do is register on the site, and send me a message asking me to add you to the group of translators, which will give you the opportunity to translate the pages you want. A link at the bottom of each translated page indicates that you are the translator, and has a link to your profile.

Thank you in advance.

Document created the 11/10/2009, last modified the 26/10/2018
Source of the printed document:https://www.gaudry.be/de/en/programmer-types-abstraits.html

The infobrol is a personal site whose content is my sole responsibility. The text is available under CreativeCommons license (BY-NC-SA). More info on the terms of use and the author.

References

IHDCB331 - Méthodes de Programmation : PY Schobbens, Cours de Méthodes de Programmation (September 2009)

These references and links indicate documents consulted during the writing of this page, or which may provide additional information, but the authors of these sources can not be held responsible for the content of this page.
The author This site is solely responsible for the way in which the various concepts, and the freedoms that are taken with the reference works, are presented here. Remember that you must cross multiple source information to reduce the risk of errors.

Contents Haut