Type abstrait

Un article de Wikipédia, l'encyclopédie libre.

En informatique, 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.

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

Sommaire

[modifier] 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.

[modifier] 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 TA en lui assignant de nouvelles opérations non définit lors de la premiere spécification).

[modifier] Utilise

Ce champ 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, on écrira "Utilise : Booléen".

[modifier] Opérations

Ce champ 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 donne des informations sur l'état de l'objet)
   Exemple d'opération pour le TA : Pile

Opération

             créer : -> Pile

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

[modifier] 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éfinition de la fonction.

[modifier] Axiomes

Ce champ 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.

[modifier] 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 :

creer : \rightarrow Pile

empiler : Pile \times Element \rightarrow Pile

sommet : Pile \rightharpoonup Elément

reste : Pile \rightharpoonup Pile

estVide : Pile \rightarrow Booléen

insererFin : Pile \times Elément \rightarrow Pile

On prend compte ici des opérations de base de la pile, et en plus l'opération insererFin permettant d'insérer un élément à la fin de la pile (cette opération nous permettra de présenter la récursivité en TA). Les \rightharpoonup signifient que l'opération est soumise à des pré-conditions.

On a ici un constructeur : creer, trois transformateurs : empiler, reste et insererFin, et deux observateurs : sommet et estVide. L'opération empiler sera ranger par certain comme un constructeur car on constatera que toute pile sera soit de la forme empiler(p,e) ou creer().

Pré-conditions : p \in Pile

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

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

En effet 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(creer())

(P4) insererFin(creer(),e) = empiler(creer(),e)

(P5) insererFin(empiler(p,f),e) = empiler(insererFin(p,e),f)

Ici estVide(creer()) n'est égal à rien car c'est un booléen et l'on précise donc qu'il renvoie vrai dans ce cas. Certains préfèreront mentionner aussi les cas où le booléen sera faux, ce qui se noterait ici : p\neqcreer() \Rightarrow \negestVide(p).