AccueilđŸ‡«đŸ‡·Chercher

Type abstrait

En informatique, un type de donnée abstrait (en anglais, abstract data type ou ADT) est une spécification mathématique[1] d'un ensemble de données[2] et de l'ensemble des opérations qu'on peut effectuer sur elles. On qualifie d'abstrait ce type de donnée car il ne spécifie pas comment les données sont représentées ni comment les opérations sont implémentées.

Exemples

Les types abstraits les plus utilisés sont :

Structure

Un type abstrait est composé de cinq champs :

  • Type abstrait ;
  • Utilise ;
  • OpĂ©rations ;
  • PrĂ©-conditions ;
  • Axiomes.

Ces cinq éléments sont souvent réunis sous l'acronyme : TUOPA.

Type abstrait

Le champ « Type abstrait » contient le nom du type que l'on est en train de décrire et précise éventuellement si celui-ci n'est pas une extension d'un autre type abstrait. Par exemple, on écrira « Type abstrait : Pile » pour créer un type nommé Pile qui décrit ce qu'est une pile et « Extension Type abstrait : Pile » si on désire l'étendre (on étend un type abstrait en lui assignant de nouvelles opérations non définies lors de la premiÚre spécification).

Utilise

Le champ « Utilise » contient les types abstraits que l'on va utiliser dans celui que l'on est en train de décrire. Par exemple, le type abstrait Pile que l'on définit va utiliser dans sa spécification le type abstrait Booléen, et on écrira « Utilise : Booléen ».

Opérations

Le champ « Opérations » contient le prototypage de toutes les opérations. Par prototypage, on entend une description des opérations par leur nom, leurs arguments et leur retour.

Les opérations sont divisées en plusieurs types :

  • les constructeurs (permettent de crĂ©er un objet du type que l'on est en train de dĂ©finir) ;
  • les transformateurs (permettent de modifier les objets et leur contenu) ;
  • les observateurs (fonction donnant des informations sur l'Ă©tat de l'objet).

Exemple d'opération pour le type « Type abstrait : Pile » :

             crĂ©er : → Pile

Notez que l'opération « créer » est un constructeur. En effet, cette fonction crée un objet de type pile. De plus, elle n'a pas besoin d'argument pour créer cette pile. Ceci est montré par l'absence d'indication à gauche de la flÚche.

Pré-conditions

Le champ « Pré-conditions » contient les conditions à respecter sur les arguments des opérations pour que celles-ci puissent avoir un comportement normal. On peut parler ici d'ensemble de définition des opérations.

Axiomes

Le champ « Axiomes » contient une série d'axiomes pour décrire le comportement de chaque opération d'un type abstrait. Chaque axiome est une proposition logique vraie.

Exemple commenté : la pile

On rappelle qu'une pile est une structure de donnĂ©es simple, respectant le principe LIFO (« Last In First Out Â»), c'est-Ă -dire que l'on accĂšde toujours au dernier Ă©lĂ©ment que l'on vient d'ajouter Ă  cette structure.

Type abstrait : Pile

Utilise : BoolĂ©en, ÉlĂ©ment

Opérations :

créer : Pile

empiler : Pile ÉlĂ©ment Pile

sommet : Pile ÉlĂ©ment

reste : Pile Pile

estVide : Pile Booléen

insĂ©rerFin : Pile ÉlĂ©ment Pile

On tient compte ici des opérations de base de la pile, ainsi que de l'opération insérerFin permettant d'insérer un élément à la fin de la pile (cette opération permettra de présenter la récursivité en type abstrait). Le symbole « » signifie que l'opération est soumise à des pré-conditions.

On a ici un constructeur : crĂ©er ; trois transformateurs : empiler, reste et insĂ©rerFin ; et deux observateurs : sommet et estVide. L'opĂ©ration empiler est considĂ©rĂ©e par certains comme un constructeur car on constate que toute pile est de la forme « crĂ©er() Â» ou « empiler(p, e) Â».

Pré-conditions : p Pile

défini(sommet(p)) estVide(p)

défini(reste(p)) estVide(p)

Ces pré-conditions correspondent au fait que l'on ne peut pas « voir » le sommet ou prendre le reste d'une pile vide.

Axiomes : p Pile et e, f ÉlĂ©ment

(P1) sommet(empiler(p, e)) = e

(P2) reste(empiler(p, e)) = p

(P3) estVide(créer()) = vrai

(P4) estVide(empiler(p, e)) = faux

(P5) insérerFin(créer(), e) = empiler(créer(), e)

(P6) insérerFin(empiler(p, f), e) = empiler(insérerFin(p, e), f)

Notes et références

  1. Manfred Broy, Martin Wirsing et Claude Pair, « A Systematic Study of Models of Abstract Data Types », Theoretical Computer Science, vol. 33,‎ , p. 139-174
  2. Sébastien Veigneau, Approches impérative et fonctionnelle de l'algorithmique : applications en C et en CAML Light, Springer Science & Business Media, (lire en ligne)
  3. http://pageperso.lif.univ-mrs.fr/~denis.lugiez/Enseignement/L2/Cours/cours4.pdf

Voir aussi


Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.