Type abstrait


Type abstrait

En génie logiciel, un type abstrait est une spécification mathématique d'un ensemble de données et de l'ensemble des opérations qu'elles peuvent effectuer. On qualifie d'abstrait ce type de données car il correspond à un cahier des charges qu'une structure de données doit ensuite implémenter. Notons que la plupart des types abstraits décrivent généralement des structures récursives.

Les types abstraits les plus utilisés sont : pile, file, liste et arbre binaire.

Sommaire

Structure

Un type abstrait est composé de cinq champs :

  • TA (Type Abstrait)
  • Utilise
  • Opérations
  • Pré-conditions
  • Axiomes

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

Type Abstrait

Le champ « TA » (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 « TA : Pile » pour créer un type nommé Pile qui décrit ce qu'est une pile et « Extension TA : 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 « TA : 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 d'une fonction pour que celle-ci puisse avoir un comportement normal. On peut parler ici d'ensemble de définitions de la fonction.

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, Elément

Opérations :

créer : \rightarrow Pile

empiler : Pile \times
Elément \rightarrow Pile

sommet : Pile \rightharpoonup Elément

reste : Pile \rightharpoonup Pile

estVide : Pile \rightarrow Booléen

insérerFin : Pile \times Elément \rightarrow 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 nous permettra de présenter la récursivité en type abstrait). Le symbole « \rightharpoonup » 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 « empiler(p,e) » ou « créer() ».

Pré-conditions : p \in Pile

défini(sommet(p)) \Rightarrow \negestVide(p)

défini(reste(p)) \Rightarrow \negestVide(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 \in Pile e, f \in Elément

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

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

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

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

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

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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Type abstrait de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • type abstrait — ● loc. m. ►TYPE Voir abstrait …   Dictionnaire d'informatique francophone

  • Trait (type abstrait) — Pour les articles homonymes, voir Trait. Un Trait est un type abstrait, simple modèle conceptuel pour structurer des programmes orientés objets . [1]. Les traits sont similaires aux mixins, mais peuvent inclure des définitions pour des méthodes… …   Wikipédia en Français

  • TYPE — Modèle qui détermine la forme d’une série d’êtres, lui même étant l’un de ces êtres (prototype, archétype); être qui présente la forme la plus caractéristique ou la plus parfaite d’une série (être «typique», «typé»; «typifier»: exagérer les… …   Encyclopédie Universelle

  • Type algebrique de donnees — Type algébrique de données Un type algébrique de données est un type de données dont chacune des valeurs est une donnée d un autre type enveloppée dans un des constructeurs du type. Toutes les données enveloppées sont des arguments du… …   Wikipédia en Français

  • Type algébrique — de données Un type algébrique de données est un type de données dont chacune des valeurs est une donnée d un autre type enveloppée dans un des constructeurs du type. Toutes les données enveloppées sont des arguments du constructeur. Par contraste …   Wikipédia en Français

  • Type recursif — Type récursif Dans un langage de programmation, un type récursif ou type inductif est un type de données pour des valeurs qui contiennent d autres valeurs du même type. Un exemple est le type liste en Haskell : data List a = Nil | Cons a… …   Wikipédia en Français

  • Type — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Type », sur le Wiktionnaire (dictionnaire universel) Le mot « type » (du grec tupos,… …   Wikipédia en Français

  • Type statique — Typage statique Sommaire 1 Définition 2 Langages à objets et typage statique 3 Problèmes 4 Résolution, autres difficultés …   Wikipédia en Français

  • Type algébrique de données — Un type algébrique de données est un type de données dont chacune des valeurs est une donnée d un autre type enveloppée dans un des constructeurs du type. Toutes les données enveloppées sont des arguments du constructeur. Par contraste aux autres …   Wikipédia en Français

  • Type récursif — Dans un langage de programmation, un type récursif ou type inductif est un type de données pour des valeurs qui contiennent d autres valeurs du même type. Cette notion s applique naturellement dans l étude des listes et des arbres. Sommaire 1… …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.