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'elle 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.

[modifier] Structure

Un type abstrait est composé de cinq champs :

Type Abstrait
Utilise qui contient les types abstraits que l'on va utiliser dans celui que l'on écrit. Par exemple, le type abstrait Pile va utiliser le type abstrait Booléen, on écrira "Utilise : Booléen".
Opérations
Pré-conditions
Axiomes

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

[modifier] Type Abstrait

Le champ Type Abstrait contient le nom du type et précise éventuellement si c'est une extension. Par exemple, on écrira "Type Abstrait : Pile" pour creer un type liste qui décrit la liste et "Extension Type Abstrait : Pile" si on désire l'étendre.

[modifier] Utilise

Ce champs contient les types abstraits que l'on va réutiliser dans celui que l'on décrit.

[modifier] Opérations

Ce champs contient le prototypage de toutes les opérations. Par prototypage, on entend une description des opérations par leur nom, leur arguments et leur retour.

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

les constructeurs (permettent de créer un objet du type)
les transformateurs (permettent de modifier les objets et leur contenu)
les observateurs (fonction donne des informations sur l'état de l'objet)

[modifier] Pré-conditions

Le champs pré-conditions contient, les conditions à respecter sur les arguments d'une fonction pour que celle-ci puisse avoir un comportement normal.

[modifier] Axiomes

Ce champs 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 vrai.

[modifier] Exemple commenté : la Pile

On rappel 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$ $\neg$ estVide(p)

défini(reste(p)) $\Rightarrow$ $\neg$ estVide(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)) = e

(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éfereront mentionner aussi les cas où le booléen sera faux, ce qui ce noterait ici : p $\neq$ creer() $\Rightarrow$ $\neg$ estVide(p).