Définir une interface, masquer la représentation et raisonner par contrats

Fiche pédagogique du chapitre

Objectifs d’apprentissage

À la fin de ce chapitre, l’étudiant devra être capable de :

• expliquer ce qu’est un type abstrait de données et distinguer données, opérations, interface et implémentation ;
• décrire une structure par son comportement observable plutôt que par son stockage interne ;
• concevoir une interface cohérente pour un nouveau type abstrait ;
• justifier l’encapsulation et l’indépendance de l’implémentation ;
• reconnaître les types abstraits Liste, Pile, File, Ensemble et Dictionnaire ;
• spécifier les préconditions et les postconditions d’une opération ;
• définir les valeurs retournées et les effets de bord d’une opération ;
• choisir une stratégie de gestion des erreurs adaptée ;
• comparer plusieurs implémentations possibles d’une même interface ;
• utiliser les contrats pour tester et documenter une structure de données.

Prérequis

• variables, types simples, tableaux et enregistrements ;
• fonctions, procédures, paramètres et valeurs de retour ;
• notions de portée, modularité et encapsulation élémentaire ;
• listes, piles et files au niveau introductif ;
• notions de complexité temporelle et spatiale.

Plan du chapitre

Organisation pédagogique indicative

Introduction

Dans les premiers programmes, une structure de données est souvent présentée directement par sa représentation : un tableau, une liste chaînée ou un ensemble de variables. Cette manière de procéder devient insuffisante dès que les programmes grandissent. Le code qui utilise une structure finit alors par dépendre de détails internes qui devraient rester modifiables.

Un type abstrait de données, abrégé TAD, décrit une famille de valeurs et les opérations autorisées sur ces valeurs. Il précise ce que la structure doit permettre de faire, mais il ne fixe pas nécessairement la manière dont les données sont stockées. Par exemple, une pile peut être implémentée avec un tableau ou avec une liste chaînée tout en offrant les mêmes opérations Empiler, Dépiler et Sommet.

Cette séparation est essentielle pour concevoir des logiciels modulaires. L’utilisateur d’un TAD se limite à son interface. Le concepteur de l’implémentation peut ensuite améliorer le stockage, la complexité ou la sécurité sans modifier les programmes clients, à condition de respecter le contrat annoncé.

2.1 Définition

Un type abstrait de données est une spécification logique qui regroupe un ensemble de données et les opérations permettant de les créer, de les observer et de les modifier. Le mot abstrait signifie que l’on raisonne d’abord sur le service rendu, sans imposer les détails techniques du stockage.

TAD = domaine de valeurs + opérations + règles de comportement

2.1.1 Données manipulées

La description d’un TAD commence par le domaine des valeurs qu’il peut représenter. Ce domaine ne doit pas être confondu avec la disposition physique en mémoire. Une file représente une séquence ordonnée selon l’ordre d’arrivée, même si elle est stockée dans un tableau circulaire ou dans une liste chaînée.

• la nature des éléments : entiers, chaînes, enregistrements ou objets génériques ;
• l’organisation logique : séquence, ensemble non ordonné, association clé-valeur ou hiérarchie ;
• les états particuliers : structure vide, structure pleine si la capacité est bornée, clé absente ;
• les invariants : propriétés qui doivent rester vraies après chaque opération valide.

2.1.2 Opérations autorisées

Les opérations définissent les seules interactions légitimes avec le TAD. Elles peuvent être classées selon leur rôle. Une interface réduite et cohérente est généralement plus facile à comprendre, à tester et à maintenir qu’une interface contenant de nombreuses opérations redondantes.

Une opération doit avoir un nom précis, des paramètres identifiés, un résultat éventuel et un effet clairement décrit. Il faut également décider si elle modifie la structure ou renvoie une nouvelle valeur sans modifier l’originale.

2.1.3 Interface

L’interface est la partie publique du TAD. Elle contient les signatures des opérations et leur documentation. Une signature indique généralement le nom de l’opération, les paramètres, leurs types, le type du résultat et parfois les erreurs possibles.

Exemple d’interface abstraite

TypeAbstrait Pile<T>
    Créer() → Pile<T>
    EstVide(P : Pile<T>) → Booléen
    Taille(P : Pile<T>) → Entier
    Empiler(P : Pile<T>, x : T)
    Sommet(P : Pile<T>) → T
    Dépiler(P : Pile<T>) → T
FinTypeAbstrait

Le paramètre T indique que la pile peut contenir différents types d’éléments. Cette généricité évite de définir une nouvelle pile pour chaque type de donnée.

2.1.4 Implémentation

L’implémentation réalise concrètement les opérations promises par l’interface. Plusieurs représentations peuvent convenir au même TAD. Elles diffèrent par leur coût, leur consommation mémoire, leur simplicité et leurs contraintes.

Le choix d’une implémentation ne change pas la signification des opérations. Il peut toutefois modifier leurs performances. L’analyse de complexité aide à choisir la représentation adaptée au contexte.

2.2 Séparation entre interface et représentation

La séparation entre interface et représentation est le principe central des types abstraits. L’interface décrit ce que fait la structure. La représentation décrit comment elle est stockée. Le programme client ne doit dépendre que de la première.

2.2.1 Ce que fait une structure

Le comportement d’une structure est défini par ses opérations et par les propriétés observables qui relient ces opérations. Pour une pile, l’élément renvoyé par Dépiler après Empiler(P, x) doit être x, sauf si une autre modification est intervenue entre les deux appels.

Comportement observable d’une pile

P ← Créer()
Empiler(P, 12)
Empiler(P, 7)
x ← Dépiler(P)
// x doit valoir 7 : le dernier élément ajouté est retiré en premier.

Cette règle exprime le principe LIFO sans préciser si la pile utilise un tableau ou une liste. Elle appartient donc à la spécification abstraite.

2.2.2 Comment elle est stockée

La représentation interne comprend les champs, tableaux, nœuds, liens et indices nécessaires à la réalisation des opérations. Elle peut inclure des informations auxiliaires, comme le nombre d’éléments, afin d’accélérer certaines opérations.

2.2.3 Encapsulation

L’encapsulation consiste à regrouper les données internes et les opérations qui les manipulent, tout en empêchant les modifications directes non contrôlées. Elle protège les invariants de représentation et limite les dépendances entre les modules.

Dans un langage orienté objet, l’encapsulation est souvent assurée par des attributs privés et des méthodes publiques. Dans un langage procédural, elle peut être obtenue avec des modules, des fichiers d’interface et des types opaques.

2.2.4 Indépendance de l’implémentation

L’indépendance de l’implémentation permet de remplacer une représentation par une autre sans changer le code client. Elle facilite l’optimisation, le portage, la correction d’erreurs et l’évolution du logiciel.

Programme client indépendant

// Version cliente : elle ne connaît pas la représentation de la file.
F ← CréerFile()
Enfiler(F, "A")
Enfiler(F, "B")
Afficher(Défiler(F))

// L’implémentation peut utiliser un tableau circulaire aujourd’hui
// et une liste chaînée demain, sans modifier ce code.

• stabilité du code client ;
• possibilité d’optimiser une opération sans changer son usage ;
• réduction des effets en cascade lors d’une modification ;
• tests séparés de l’interface et de l’implémentation ;
• réutilisation d’une même interface dans plusieurs contextes.

2.2.5 Invariant de représentation

L’implémentation possède souvent un invariant de représentation, c’est-à-dire une propriété que les champs internes doivent respecter. Cet invariant n’est pas nécessairement visible dans l’interface, mais chaque opération doit le préserver.

Vérifier l’invariant au début et à la fin des opérations complexes est une technique utile pendant le développement. En production, certaines vérifications peuvent être désactivées pour améliorer les performances, à condition que la structure ait été correctement validée.

2.3 Exemples de types abstraits

Les types abstraits suivants apparaissent fréquemment dans les algorithmes. Ils se distinguent par l’organisation logique des éléments et par les opérations privilégiées. Leur interface peut être enrichie, mais elle doit rester cohérente avec leur sémantique.

2.3.1 Le TAD Liste

Une liste représente une séquence finie dans laquelle chaque élément possède une position. Selon l’interface, les positions peuvent être numérotées à partir de 0 ou de 1. La liste abstraite n’impose pas un accès direct en temps constant : cette propriété dépend de l’implémentation.

Interface possible d’une liste

TypeAbstrait Liste<T>
    Créer() → Liste<T>
    Taille(L) → Entier
    EstVide(L) → Booléen
    AjouterFin(L, x)
    Insérer(L, position, x)
    ÉlémentÀ(L, position) → T
    Remplacer(L, position, x)
    SupprimerÀ(L, position) → T
    Rechercher(L, x) → PositionOuAbsent
FinTypeAbstrait

Une liste peut être implémentée par un tableau dynamique, une liste simplement chaînée ou une liste doublement chaînée. Le choix dépend notamment du besoin d’accès par indice et de la fréquence des insertions ou suppressions.

2.3.2 Le TAD Pile

Une pile applique le principe LIFO : le dernier élément ajouté est le premier retiré. L’interface doit empêcher un accès arbitraire qui contredirait cette abstraction. Une opération de parcours peut exister, mais elle ne doit pas autoriser des modifications incohérentes.

Interface de la pile

TypeAbstrait Pile<T>
    Créer() → Pile<T>
    EstVide(P) → Booléen
    Taille(P) → Entier
    Empiler(P, x)
    Sommet(P) → T
    Dépiler(P) → T
    Vider(P)
FinTypeAbstrait

2.3.3 Le TAD File

Une file applique le principe FIFO : le premier élément ajouté est le premier retiré. Les opérations utilisent deux extrémités logiques : la fin pour l’ajout et la tête pour le retrait.

Interface de la file

TypeAbstrait File<T>
    Créer() → File<T>
    EstVide(F) → Booléen
    Taille(F) → Entier
    Enfiler(F, x)
    Tête(F) → T
    Défiler(F) → T
    Vider(F)
FinTypeAbstrait

Le parcours en largeur d’un graphe, l’ordonnancement des tâches et la simulation d’un guichet utilisent naturellement une file.

2.3.4 Le TAD Ensemble

Un ensemble contient des éléments distincts. L’ordre d’énumération n’est généralement pas significatif. Ajouter un élément déjà présent ne crée pas de doublon. Les opérations ensemblistes expriment directement des traitements mathématiques.

Interface de l’ensemble

TypeAbstrait Ensemble<T>
    Créer() → Ensemble<T>
    EstVide(E) → Booléen
    Cardinal(E) → Entier
    Contient(E, x) → Booléen
    Ajouter(E, x)
    Retirer(E, x)
    Union(E1, E2) → Ensemble<T>
    Intersection(E1, E2) → Ensemble<T>
    Différence(E1, E2) → Ensemble<T>
FinTypeAbstrait

2.3.5 Le TAD Dictionnaire

Un dictionnaire associe des clés uniques à des valeurs. La clé permet de retrouver rapidement la valeur correspondante. L’interface doit préciser le comportement en cas d’insertion d’une clé déjà présente ou de recherche d’une clé absente.

Interface du dictionnaire

TypeAbstrait Dictionnaire<Clé, Valeur>
    Créer() → Dictionnaire<Clé, Valeur>
    EstVide(D) → Booléen
    Taille(D) → Entier
    ContientClé(D, clé) → Booléen
    Insérer(D, clé, valeur)
    Obtenir(D, clé) → Valeur
    Modifier(D, clé, valeur)
    Supprimer(D, clé) → Valeur
    Clés(D) → Collection<Clé>
FinTypeAbstrait

Les implémentations usuelles sont la table de hachage et l’arbre de recherche équilibré. La première favorise les opérations moyennes proches de O(1), tandis que la seconde maintient les clés ordonnées et offre généralement O(log n).

2.4 Contrats des opérations

Une signature ne suffit pas à décrire complètement une opération. Le contrat précise les conditions dans lesquelles l’opération peut être appelée, ce qu’elle garantit après son exécution, ce qu’elle retourne et la manière dont les situations anormales sont traitées.

Contrat = préconditions + effets + postconditions + résultat + erreurs

2.4.1 Préconditions

Une précondition est une propriété qui doit être vraie avant l’appel. Elle exprime les obligations du programme client. Si elle n’est pas respectée, le résultat de l’opération n’est pas garanti, sauf si l’interface prévoit explicitement une erreur.

2.4.2 Postconditions

Une postcondition décrit les propriétés garanties après une exécution normale. Elle peut relier l’état après l’opération à l’état précédent. On note parfois ancien(...) pour désigner une valeur avant modification.

Contrat d’Empiler

Opération Empiler(P, x)
Précondition : aucune
Postconditions :
    Taille(P) = ancien(Taille(P)) + 1
    Sommet(P) = x
    Les anciens éléments conservent leur ordre relatif.

Les postconditions constituent une base directe pour les tests. Chaque garantie peut être transformée en une assertion vérifiable.

2.4.3 Valeurs retournées

La documentation doit préciser la signification exacte du résultat. Une opération peut retourner une valeur, une position, un booléen, une structure nouvelle ou un résultat optionnel indiquant l’absence de valeur.

2.4.4 Gestion des erreurs

Une erreur peut provenir d’une précondition violée, d’une ressource insuffisante ou d’une situation normale mais exceptionnelle, comme la recherche d’une clé absente. La stratégie doit être cohérente dans toute l’interface.

2.4.5 Exemple de contrat complet

Contrat de suppression dans une liste

Opération SupprimerÀ(L, i) → T
Préconditions :
    L est une liste valide
    0 ≤ i < Taille(L)
Effets :
    retire l’élément situé à la position i
Résultat :
    retourne l’élément retiré
Postconditions :
    Taille(L) = ancien(Taille(L)) − 1
    pour j < i, ÉlémentÀ(L, j) est inchangé
    pour j ≥ i, ÉlémentÀ(L, j) = ancien(ÉlémentÀ(L, j + 1))
Erreurs :
    IndiceInvalide si i est hors limites

Ce contrat ne précise pas si la liste est représentée par un tableau ou par des nœuds. Il reste donc valable pour plusieurs implémentations.

2.4.6 Conception par contrats

La conception par contrats organise les responsabilités entre le client et le fournisseur d’une opération. Le client garantit les préconditions. L’opération garantit les postconditions et préserve les invariants de la structure.

Applications guidées

Application 1 — Concevoir le TAD Historique

On souhaite gérer l’historique des pages visitées dans un navigateur, avec possibilité de revenir à la page précédente. L’ordre naturel est celui d’une pile.

Interface proposée

TypeAbstrait Historique
    Créer() → Historique
    Enregistrer(H, adresse)
    PeutRevenir(H) → Booléen
    PagePrécédente(H) → Adresse
    Revenir(H) → Adresse
    Effacer(H)
FinTypeAbstrait

Application 2 — Choisir un TAD pour chaque besoin

Application 3 — Remplacer l’implémentation d’une file

Une première version d’un système d’impression utilise un tableau simple et décale les éléments à chaque retrait. Lorsque la charge augmente, Défiler devient coûteux. L’interface étant stable, l’implémentation peut être remplacée par un tableau circulaire.

Utilisation indépendante de la représentation

// Code client inchangé
F ← CréerFile()
Pour chaque document d reçu Faire
    Enfiler(F, d)
FinPour
TantQue NON EstVide(F) Faire
    Imprimer(Défiler(F))
FinTantQue

Application 4 — Spécifier une recherche dans un dictionnaire

Deux interfaces sont possibles pour une clé absente. Le choix doit être explicite.

La version optionnelle convient lorsque l’absence est fréquente et normale. Une exception convient mieux lorsque l’absence révèle une incohérence du programme.

Application 5 — Vérifier un contrat par des tests

Pour Empiler, on peut dériver directement les tests à partir des postconditions.

Travaux dirigés

Les exercices suivants visent à transformer des besoins informels en interfaces abstraites et en contrats vérifiables. Les étudiants doivent justifier chaque opération et éviter d’exposer la représentation.

Exercice 1 — Identifier les quatre composantes d’un TAD

Pour un système de rendez-vous, on souhaite stocker des créneaux, ajouter une réservation, l’annuler, vérifier la disponibilité et obtenir le nombre de réservations. Identifier les données, les opérations, l’interface et deux implémentations possibles.

Exercice 2 — Interface d’une file de priorité simplifiée

Proposer une interface permettant d’ajouter une tâche avec une priorité entière, de consulter la tâche la plus prioritaire et de la retirer. Préciser les préconditions principales.

Exercice 3 — Détecter les fuites de représentation

Une interface Liste expose une opération ObtenirTableauInterne(L) qui retourne directement le tableau de stockage. Expliquer les risques et proposer une alternative sûre.

Exercice 4 — Contrat de l’opération Retirer

Pour un ensemble E, spécifier deux versions de Retirer(E, x) : une version avec précondition x ∈ E et une version sans précondition retournant un booléen.

Exercice 5 — Comparer deux interfaces de pile

L’interface A propose Dépiler(P) → T avec précondition P non vide. L’interface B propose EssayerDépiler(P) → (Booléen, T). Comparer les avantages et les limites dans un analyseur d’expressions.

Exercice 6 — Choix d’un TAD

Associer un TAD à chacun des besoins suivants : mots déjà vus, dernières commandes annulables, utilisateurs indexés par adresse électronique, messages à traiter dans l’ordre, étapes ordonnées d’un protocole.

Exercice 7 — Invariant d’un tableau circulaire

Une file circulaire est représentée par un tableau de capacité c, un indice tête, un indice fin et une taille. Proposer un invariant de représentation complet.

Exercice 8 — Remplacement d’implémentation

Une liste implémentée par tableau doit être remplacée par une liste chaînée. Indiquer les parties du logiciel qui doivent rester inchangées et les tests à rejouer.

Exercice 9 — Contrat d’une opération de dictionnaire

Spécifier Modifier(D, clé, valeur) dans deux variantes : la clé doit exister, ou l’opération insère si elle est absente.

Exercice 10 — Concevoir un TAD Capteur

Définir un type abstrait pour conserver les dernières mesures d’un capteur, obtenir la dernière mesure, calculer une moyenne et effacer l’historique. La capacité maximale est fixée à k mesures.

Corrigés indicatifs des travaux dirigés

Correction de l’exercice 1

• Données : ensemble de créneaux et état libre ou réservé, éventuellement informations du client ;
• opérations : CréerAgenda, Réserver, Annuler, EstDisponible, NombreRéservations ;
• interface : signatures publiques et contrats de ces opérations ;
• implémentations possibles : tableau indexé par créneau ou dictionnaire créneau → réservation.

Correction de l’exercice 2

TypeAbstrait FilePriorité<T>
    Créer() → FilePriorité<T>
    EstVide(F) → Booléen
    Insérer(F, tâche : T, priorité : Entier)
    PlusPrioritaire(F) → T
    ExtrairePlusPrioritaire(F) → T
    Taille(F) → Entier
FinTypeAbstrait

Précondition de PlusPrioritaire et ExtrairePlusPrioritaire : NON EstVide(F).

Correction de l’exercice 3

Retourner le tableau interne permet au client de modifier les cases sans passer par les opérations du TAD, de changer la taille logique ou de conserver une référence devenue invalide après redimensionnement. Une alternative consiste à retourner une copie, un itérateur en lecture seule ou une opération Parcourir contrôlée.

Correction de l’exercice 4

Version 1 : RetirerPrésent(E, x)
Précondition : Contient(E, x)
Postconditions : NON Contient(E, x) et Cardinal(E)=ancien(Cardinal(E))−1

Version 2 : Retirer(E, x) → Booléen
Précondition : aucune
Si x était présent : le retire et retourne Vrai
Sinon : E reste inchangé et retourne Faux

Correction de l’exercice 5

La version A est concise et convient lorsque l’algorithme peut garantir que la pile n’est jamais vide. La version B rend l’échec explicite et évite une exception lors d’une entrée invalide. Dans un analyseur de texte fourni par un utilisateur, la version B est souvent plus robuste ; dans une fonction interne validée, la version A peut être plus lisible.

Correction de l’exercice 6

Correction de l’exercice 7

• c > 0 ;
• 0 ≤ taille ≤ c ;
• 0 ≤ tête < c et 0 ≤ fin < c ;
• si taille = 0, aucune case n’est logiquement occupée ;
• si taille = c, la file est pleine ;
• les éléments occupés sont les taille cases obtenues à partir de tête modulo c ;
• fin désigne la prochaine case d’insertion, selon la convention choisie.

Correction de l’exercice 8

Le code client, les signatures publiques, les contrats et les tests fonctionnels doivent rester inchangés. Seul le module d’implémentation et éventuellement les tests structurels internes changent. Il faut rejouer les tests de création, accès, ajout, insertion, suppression, recherche, cas limites et erreurs, puis mesurer les performances attendues.

Correction de l’exercice 9

Variante stricte : Modifier(D, clé, valeur)
Précondition : ContientClé(D, clé)
Postcondition : Obtenir(D, clé)=valeur et Taille(D) inchangée

Variante fusionnée : Définir(D, clé, valeur)
Précondition : aucune
Si clé présente, remplace la valeur et conserve la taille
Sinon, ajoute l’association et augmente la taille de 1

Correction de l’exercice 10

TypeAbstrait HistoriqueCapteur
    Créer(k : EntierPositif) → HistoriqueCapteur
    EstVide(H) → Booléen
    NombreMesures(H) → Entier
    AjouterMesure(H, valeur : Réel)
    DernièreMesure(H) → Réel
    Moyenne(H) → Réel
    Effacer(H)
FinTypeAbstrait

Règle : lorsque k mesures sont déjà présentes, AjouterMesure retire

la plus ancienne avant d’ajouter la nouvelle.

Précondition de DernièreMesure et Moyenne : l’historique n’est pas vide. Une file circulaire de capacité k constitue une implémentation adaptée.

Travail pratique — Deux implémentations d’une même pile

Objectif

Montrer expérimentalement que l’interface d’un TAD peut rester identique lorsque sa représentation change. Les étudiants implémentent une pile d’entiers avec un tableau dynamique, puis avec une liste chaînée.

Travail demandé

1. Définir l’interface commune : Créer, EstVide, Taille, Empiler, Sommet, Dépiler et Vider.

2. Écrire les contrats de Sommet, Empiler et Dépiler.

3. Réaliser une première implémentation avec un tableau dynamique.

4. Réaliser une seconde implémentation avec une liste simplement chaînée.

5. Écrire un programme client unique qui exécute une suite d’opérations sur les deux versions.

6. Vérifier que les résultats observables sont identiques.

7. Mesurer le temps d’un million d’opérations Empiler/Dépiler et commenter les écarts.

8. Comparer la mémoire utilisée et rédiger une conclusion sur les compromis.

Jeux d’essai minimaux

Architecture de correction

Module InterfacePile
    // signatures et contrats, sans représentation
FinModule

Module PileTableau implémente InterfacePile
    données privées : tableau, taille
FinModule

Module PileChaînée implémente InterfacePile
    données privées : sommet, taille
FinModule

Programme TestPile(constructeurPile)
    P ← constructeurPile()
    // même scénario pour les deux implémentations
FinProgramme

Grille d’évaluation indicative

Synthèse du chapitre

Méthode pour concevoir un type abstrait

1. Décrire le besoin sans choisir immédiatement une structure de stockage.

2. Identifier les valeurs représentées et les propriétés logiques attendues.

3. Lister les opérations indispensables et supprimer les opérations redondantes.

4. Définir les signatures, paramètres et résultats.

5. Écrire les préconditions, postconditions, effets et erreurs.

6. Choisir une ou plusieurs représentations possibles.

7. Définir les invariants de représentation.

8. Implémenter les opérations en préservant les invariants.

9. Tester le comportement public indépendamment des détails internes.

10. Comparer les performances et faire évoluer l’implémentation si nécessaire.

Glossaire

Auto-évaluation