Type abstrait (Bac 🎯)⚓︎
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.
Sources et crédits pour ce cours
Pour préparer ce cours, j'ai utilisé :
- le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen
- le manuel NSI chez Hachette sous la direction de Michel Beaudouin Lafon
- la ressource Eduscol sur les types de données
- le cours de mon collègue Pierre Duclosson
🔖 Synthèse de ce qu'il faut retenir pour le bac
Interface et implémentation⚓︎
Point de cours 1
Vous avez manipulé en Première des types de données structurées en Python, comme les tableaux/listes ou les dictionnaires. Chacun de ces types de données propose un ensemble d'opérations permettant de manipuler les données qui constitue son interface. L'utilisateur n'a pas besoin de connaître l'implémentation des données et des opérations pour les manipuler.
Exemple 1
Le type list en Python permet d'organiser les données dans une séquence de cases mémoires contigues, appelée tableau. Chaque élément est accessible directement par son indice, ce qui n'est pas le cas pour le type abstrait liste où il faut d'abord parcourir tous les éléments précédents. Il est donc plus correct de qualifier cette structure de tableau que de liste. Néanmoins, la taille de ce tableau peut être redimensionnée, alors que dans le type abstrait tableau la taille est fixée, il est donc finalement plus correct de qualifier cette structure de tableau dynamique que de tableau.
>>> t1 = [] # tableau vide
>>> t1.append(4) # méthode append de tableau dynamique
>>> t1[0] = 5 # opérateur crochet équivalent à t1.__setitem__(0, 5)
>>> t1[0] # opérateur crochet équivalent à t1.__getitem__(0)
5
Plus généralement, un type abstrait de données est une structure qui offre une une interface publique de manipulation des données qui est constituée d'opérations. L'implémentation des données et des opérations peut être dissimulée à l'utilisateur. C'est le principe d'encapsulation.
Exercice 1
💻 Saisir ses réponses sur Capytale
Le type abstrait tableau statique permet de stocker un ensemble de données dans un nombre fixée de cases mémoires contigues en mémoire. Contrairement aux tableaux dynamiques du type
listde Python, les tableaux statiques ne sont pas redimensionnables et ne peuvent donc stocker qu'un nombre maximal de données. Chaque case peut être accessible directement en lecture ou en écriture, comme les cases de la mémoire RAM dans l'architecture de Von Neumann. Voici une interface minimale :
| Opération | Signature | Description |
|---|---|---|
| creer_tableau | creer_tableau(taille) | Renvoie un tableau de taille fixée |
| lire_case | lire_case(tableau, index) | Accès direct en lecture à la valeur de la case du tableau d'index fixé |
| modifier_case | modifier_case(tableau, index, valeur) | Accès direct en écriture à la valeur de la case du tableau d'index fixé |
Question 1
Implémentez le type abstrait tableau statique en utilisant le type list de tableau dynamique de Python dans l'implémentation.
def creer_tableau(taille):
return [None for _ in range(taille)]
def lire_case(tableau, index):
assert isinstance(index, int), "index doit être un entier"
assert 0 <= index < len(tableau), "index en dehors de la plage licite"
return tableau[index]
def modifier_case(tableau, index, valeur):
assert isinstance(index, int), "index doit être un entier"
assert 0 <= index < len(tableau), "index en dehors de la plage licite"
tableau[index] = valeur
def test_tableau():
numeros = creer_tableau(10)
modifier_case(numeros, 2, "0642454712")
assert lire_case(numeros, 2) == "0642454712"
modifier_case(numeros, 0, "0842454912")
assert lire_case(numeros, 0) == "0842454912"
Question 2
Implémentez le type abstrait tableau statique, toujours en utilisant le type list de tableau dynamique de Python, mais cette fois avec un style de programmation objet.
class Tableau:
def __init__(self, taille):
self.taille = taille
self.tab = [None for _ in range(self.taille)]
def lire_case(self, index):
assert isinstance(index, int), "index doit être un entier"
assert 0 <= index < self.taille, "index en dehors de la plage licite"
return self.tab[index]
def modifier_case(self, index, valeur):
assert isinstance(index, int), "index doit être un entier"
assert 0 <= index < self.taille, "index en dehors de la plage licite"
self.tab[index] = valeur
def test_tableau():
numeros = Tableau(10)
numeros.modifier_case(2, "0642454712")
assert numeros.lire_case(2) == "0642454712"
numeros.modifier_case(0, "0842454912")
assert numeros.lire_case(0) == "0842454912"
print("Tests réussis")
Exercice 2
💻 Saisir ses réponses sur Capytale
Un tableau statique ou dynamique permet un accès direct aux données mais par le biais d'un index entier. Le type abstrait dictionnaire permet également un accès direct mais par le biais d'une clef qui n'est pas forcément un entier. Voici une interface minimale :
| Opération | Signature | Description |
|---|---|---|
| creer_dico | creer_dico() | Renvoie un dictionnaire |
| valeur | valeur(dico, clef) | Accès direct en lecture à la valeur associée à la clef fixée |
| ajouter | ajouter(dico, clef, valeur) | Accès direct en écriture à la valeur associée à la clef fixée |
Question 1
Implémentez le type abstrait dictionnaire en utilisant le type dict de Python dans l'implémentation.
def creer_dico():
return dict()
def ajouter(dico, clef, valeur):
dico[clef] = valeur
def valeur(dico, clef):
assert clef in dico, "La clef n'est pas dans le dictionnaire"
return dico[clef]
def test_dico():
annuaire = creer_dico()
ajouter(annuaire, "Eric", "0642454712")
ajouter(annuaire, "Bob", "0908141719")
assert valeur(annuaire, "Eric") == "0642454712"
assert valeur(annuaire, "Bob") == "0908141719"
ajouter(annuaire, "Eva", "0908141719")
assert valeur(annuaire, "Eva") == "0908141719"
print("Tests réussis")
Question 2
On donne ci-dessous une implémentation du type abstrait dictionnaire où les couples (clef, valeur) sont stockés dans un tableau statique pouvant contenir un nombre maximal de clefs. Complétez les tests unitaires en reprenant les mêmes valeurs que pour l'implémentation précédente. On veut une capacité maximale de 10 contacts.
class Dico:
def __init__(self, nb_clefs_max):
self.pos = 0 # position de la prochaine clef
self.nb_clefs_max = nb_clefs_max # nombre maximal de clefs
self.tab = [None for _ in range(nb_clefs_max)] # tableau statique contenant les tuples (clef, valeur)
def ajouter(self, clef, valeur):
assert self.pos < self.nb_clefs_max, "Dictionnaire plein"
self.tab[self.pos] = (clef, valeur)
self.pos = self.pos + 1
def valeur(self, clef):
# à complé
for k in range(self.nb_clefs_max):
c, v = self.tab[k]
if c == clef:
return v
assert False, "clef pas dans le dictionnaire"
def test_dico2():
annuaire = Dico(10)
annuaire.ajouter("Eric", "0642454712")
annuaire.ajouter("Bob", "0908141719")
assert annuaire.valeur("Eric") == "0642454712"
assert annuaire.valeur("Bob") == "0908141719"
annuaire.ajouter("Eva", "0908141719")
assert annuaire.valeur("Eva") == "0908141719"
print("Tests réussis")
Attention
Dans le type abstrait dictionnaire, une clef ne peut être associée qu'à une seule valeur. Cette condition est-elle respectée par cette dernière implémentation ?
solution
Non, on peut insérer un autre numéro pour "Eric" avec annuaire.ajouter("Eric", "0437414172"), du moins tant que la capacité maximale du tableau où sont stockés les couples (clef, valeur) n'est pas dépassée.
Point de cours 2
On a vu dans les exercices précédents qu'il peut exister différentes implémentations d'une même interface de type abstrait de données.
Les performances liées aux complexités temporelle et spatiale peuvent différer selon les implémentations.
Par exemple l'accès à la valeur associée à une clef est de coût constant pour l'implémentation du type abstrait dictionnaire avec le type dict de Python mais dans le pire des cas, le coût peut être égal au nombre de clefs dans le dictionnaire si on stocke les couples (clef, valeur) dans un tableau comme dans la question 2 de l'exercice 2.
Vous étudierez en TP une implémentation efficace du type abstrait dictionnaire.