Type abstrait Sommaire Exemples | Structure | Exemple commenté : la pile | Notes et références | Voir aussi | Menu de navigationlire en lignemm
Structure de donnéesThéorie des typesMéthode formelle
informatiquecahier des chargesstructure de donnéesimplémenterBooléenBooléenprototypageprototypageconstructeurpilepileaxiomespilestructure de donnéesLIFOpilepileconstructeurpilepile
Type abstrait
Sauter à la navigation
Sauter à la recherche
Pour les articles homonymes, voir ADT.En informatique, un type 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ées car il correspond à un cahier des charges qu'une structure de données doit ensuite implémenter.
Sommaire
1 Exemples
2 Structure
2.1 Type abstrait
2.2 Utilise
2.3 Opérations
2.4 Pré-conditions
2.5 Axiomes
3 Exemple commenté : la pile
4 Notes et références
5 Voir aussi
Exemples |
Les types abstraits les plus utilisés sont :
arbre binaire[3]- conteneur
- dictionnaire ou tableau associatif
- ensemble
- file
- file de priorité
- Graphe
- liste
- multiensemble
- pile
- Union-find
Structure |
 | Cette section ne cite pas suffisamment ses sources (décembre 2017). Pour l'améliorer, ajoutez des références vérifiables [comment faire ?] ou le modèle Référence nécessaire sur les passages nécessitant une source. |
Un type abstrait est composé de cinq champs[réf. nécessaire] :
- 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 : →displaystyle rightarrow Pile empiler : Pile ×displaystyle times "/> Élément →displaystyle rightarrow Pile sommet : Pile ⇀displaystyle rightharpoonup Élément reste : Pile ⇀displaystyle rightharpoonup Pile estVide : Pile →displaystyle rightarrow Booléen insérerFin : Pile ×displaystyle times Élément →displaystyle 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 « ⇀displaystyle 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 « créer() » ou « empiler(p, e) ».
Pré-conditions : p ∈displaystyle in Pile défini(sommet(p)) ⇒displaystyle Rightarrow ¬displaystyle neg estVide(p) défini(reste(p)) ⇒displaystyle Rightarrow ¬displaystyle neg 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 ∈displaystyle in Pile et e, f ∈displaystyle in É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 |
Manfred Broy, Martin Wirsing et Claude Pair, « A Systematic Study of Models of Abstract Data Types », Theoretical Computer Science, vol. 33, 1984, p. 139-174
Sébastien Veigneau, Approches impérative et fonctionnelle de l'algorithmique: applications en C et en CAML Light, Springer Science & Business Media, 1999(lire en ligne)
http://pageperso.lif.univ-mrs.fr/~denis.lugiez/Enseignement/L2/Cours/cours4.pdf
Voir aussi |
.mw-parser-output .autres-projets ulmargin:0;padding:0.mw-parser-output .autres-projets lilist-style-type:none;list-style-image:none;margin:0.2em 0;text-indent:0;padding-left:24px;min-height:20px;text-align:left.mw-parser-output .autres-projets .titretext-align:center;margin:0.2em 0.mw-parser-output .autres-projets li afont-style:italic
- Ensemble (informatique)
- File (structure de données)
- File de priorité
- Liste (informatique)
- Vecteur (structure de données)
- Graphe (type abstrait)
Portail de la programmation informatique 
Portail de l'informatique théorique
Catégories :
- Structure de données
- Théorie des types
- Méthode formelle
(window.RLQ=window.RLQ||[]).push(function()mw.config.set("wgPageParseReport":"limitreport":"cputime":"0.368","walltime":"0.601","ppvisitednodes":"value":4622,"limit":1000000,"ppgeneratednodes":"value":0,"limit":1500000,"postexpandincludesize":"value":157415,"limit":2097152,"templateargumentsize":"value":55534,"limit":2097152,"expansiondepth":"value":23,"limit":40,"expensivefunctioncount":"value":21,"limit":500,"unstrip-depth":"value":0,"limit":20,"unstrip-size":"value":4629,"limit":5000000,"entityaccesscount":"value":1,"limit":400,"timingprofile":["100.00% 351.548 1 -total"," 37.84% 133.018 1 Modèle:Palette"," 30.93% 108.724 2 Modèle:Méta_palette_de_navigation"," 27.78% 97.663 1 Modèle:Palette_Types_de_données"," 22.54% 79.227 1 Modèle:Références"," 19.14% 67.270 18 Modèle:Liste_horizontale"," 17.80% 62.592 1 Modèle:Article"," 17.41% 61.200 18 Modèle:Trim"," 16.51% 58.030 20 Modèle:Lien"," 14.40% 50.637 1 Modèle:Portail"],"scribunto":"limitreport-timeusage":"value":"0.064","limit":"10.000","limitreport-memusage":"value":3003306,"limit":52428800,"cachereport":"origin":"mw1269","timestamp":"20190326085007","ttl":2592000,"transientcontent":false);mw.config.set("wgBackendResponseTime":118,"wgHostname":"mw1268"););
