Types abstraits
La résolution d’un problème par un programme nécessite:
- de définir les données du problème
- d’utiliser des instructions du langage sur ces données
Souvent, la résolution du problème demande d’arranger ces données dans un type abstrait, afin d’avoir une résolution plus efficace.
Un type abstrait est défini par son interface, qui est indépendante de son implémentation.
Les types abstraits sont des types structurés. On a déjà vu des types structurés natifs: les types séquences de texte (string), les types séquentiels (listes, tuples), et les mappages (dictionnaires).
Un type abstrait est caractérisé par une interface de programmation qui permet de manipuler les données de ce type. Sans pour autant avoir connaissance du contenu des fonctions proposées par l’interface.
Spécifier un type abstrait, c’est définir son interface, sans prejuger de la façon dont ses opérations sont implémentées.
Implémenter, c’est fournir le code de ces opérations. Plusieurs implémentations peuvent correspondent à la même spécification. On verra dans ce chapitre la programmation dans un style fonctionnel. Il viendra plus tard la programmation par objet.
On verra dans un premier temps, 2 exemples de types abstraits: Les listes chainées et les tableaux. Dans un chapitre ultérieur, nous verrons les types abstraits Piles, Files, et Graphes.
Listes chaînées
Une liste chaînée est une séquence ordonnée d’éléments. L’avantage sur un tableau (la Liste native en Python), c’est qu’en parcourant la Liste chainée, quelle que soit la profondeur de parcours, celle-ci présente la même structure.
On peut donc lui associer des méthodes ou fonctions, qui seront indépendantes de cette profondeur. Que l’on pourra utiliser de la même manière à chaque niveau de la liste chainée.
La liste L précédente représente la chaine: "2nde" -> "1ere" -> "Term" -> "Univ
L = ("Univ",("Term",("1ere",("2nde", ()))))
La liste chainée L contient 2 éléments (tete, queue)
et queue
est elle-même une liste chainée, contenant aussi (tete, queue)
. Le dernier élément: (tete, ())
.
On utilisera par exemple une liste chainée lorsqu’il y a une filiation, une chronologie entre les éléments.
L’interface d’une liste chainée
L'interface fournit certaines fonctions.
fonctions qui implémentent la liste chainée L | nom |
---|---|
créer une liste vide | creer_liste() |
questionner si la liste est vide | liste_vide(L) |
insérer un élément e en tête de liste et retourne une nouvelle liste | inserer(L,e) |
retourne l’élément de tête (premier élément) | tete(L) |
retourne la liste privée de son premier élément (retourne donc le 2e élément) | queue() |
retourne une liste python avec tous les éléments de la liste chainée | elements_liste(L) |
Le contenu de ces fonctions va dépendre de l'implémentation choisie par le programmeur.
Par exemple, si l’on choisit d’implémenter la liste chainée par un tuple, on aura pour la premiere fonction:
def creer_liste():
return ()
Alors que si l’on choisit plutôt une liste:
def creer_liste():
return []
Généralités sur les listes chainées
Une liste chainée est un objet:
-
dynamique: on peut modifier sa taille après création, par exemple en faisant:
inserer(L, e)
-
et mutable: on peut le modifier en partie (ajout/suppression d’un élément), et sa copie se fait par reference.
-
dont les éléments ont une relation d’ordre entre eux.
-
dont on peut atteindre un élément au rang i en temps proportionnel à i, avec une boucle par exemple.
L'interface d’une liste chainée doit aussi proposer l’insertion d’un élément au rang i, en temps constant. (Intercaler cet élément entre 2 éléments de la liste). Ceci ne peut pas être réalisé avec l’implémentation vue plus haut.
Nous verrons d’autres implémentations pour ce type abstrait.
Tableaux
Les tableaux se comportent de manière très similaire aux listes, sauf que les types d’objets qui y sont stockés sont limités. (Array)
C’est un objet qui est:
- statique: sa taille ne varie pas une fois celui-ci créé
- et mutable: on peut le modifier en partie, par exemple avec une instruction du genre:
T[i] = x
. Sa copie se fait par reference.
Un tableau peut être représenté en Python par un tuple contenant 2 éléments:
- la liste des valeurs, de dimension fixe. On mettra
None
pour les valeurs non renseignés. - la valeur de la taille de la liste.
Par exemple:
T = ([6, 7, 8, None, None], 5)
Un tableau peut servir à implémenter une grille de notes par exemple:
Supposons, pour simplifier, que le tableau ne contient que les notes de Kyle:
On peut représenter cet ensemble de notes par le tableau:
T = ([6, 7, 8, None, None], 5)
L’interface d’un tableau
fonctions qui implémentent un tableau T (Array) | nom |
---|---|
taille du tableau | taille(T) |
demander l’élément au rang i | ieme(T,i) |
ajouter à la fin | ajouter(T,e) |
insérer l’élément e au rang i | inserer(T,i,e) |
supprimer l’élément au rang i | supprimer(T,i) |
remplacer l’élément au rang i par e | remplacer(T,i,e) |
Tableaux dynamiques et tableaux statiques
Les tableaux vus ci-dessus sont des tableaux statiques: leur taille ne peut pas être modifiée. Dans le cas où l’on ait besoin d’agrandir le tableau, il faut le copier dans un nouveau tableau, plus grand.
Python implémente naturellement un autre type de tableau, que l’on appelera dynamique: Les Listes Python. Ce problème de dimension n’apparait pas dans les Listes Python, qui apportent de surcroit des méthodes bien pratiques comme append
et pop
.
Attention: les listes chaînées (vues plus haut) et les Listes Python sont différentes, il ne s’agit pas des mêmes objets.
La liste python dynamique (type list)
Le type list
python est dynamique. Il peut lui aussi implémenter une Liste chainée ou bien un Tableau.
Pour un Tableau, si on l’implémente avec le type list
, la taille de celui-ci ne devra pas être modifiée à la fin du traitement.
Editeur Python
- Utiliser un notebook. Saisir une ou plusieurs lignes de code Python, puis appuyer simultanement sur Majuscule(Shift) + Entrée pour executer le code.
Exercices sur les listes
On propose l'implémentation suivante pour les listes chainées:
def creer_liste():
"""exemple:
L = creer_liste()
"""
return []
def liste_vide(L):
"""exemple:
liste_vide(L)
"""
return L == []
def inserer(L,e):
"""exemple:
L = inserer(L,e)
"""
return [e,L]
def tete(L):
"""exemple:
elem = tete(L)
"""
return L[0]
def queue(L):
"""exemple:
L2 = queue(L)
"""
return L[1]
def elements_liste(L):
"""exemple:
L2 = elements_liste(L)
"""
# à completer
#
Exercice sur le parcours scolaire
Le parcours
scolaire est un type abstrait qui s’apparente à une Liste. Les éléments sont disposés dans cette Liste sous la forme:
['Terminale', ['Premiere', ['Seconde', []]]]
L’interface propose les fonctions suivantes:
creer_liste, liste_vide, inserer, tete, queue
.
1. Quelles instructions, utilisant l’interface, vont créer la Liste parcours_lycee
de la manière suivante: ['Terminale', ['Premiere', ['Seconde', []]]]
?
2. Quelle instruction va permettre de connaitre la dernière classe visitée lors du parcours scolaire?
3. Que retourne queue(parcours)
? (choisir)
- la première classe du parcours scolaire
- le parcours scolaire sans la dernière année
4. Que retourne le script suivant?
while not liste_vide(parcours):
print(tete(parcours))
parcours = queue(parcours)
5. On souhaite utiliser ce type abstrait pour décrire le parcours universitaire. Quelles instructions vont créer la structure de données du parcours qui ira de Licence 1
à Master 2
?
Exercice sur l’historique de navigation
On cherche à implémenter l’historique du navigateur pour permettre de revenir en arrière lors de la navigation.
On visite, dans l’ordre les sites suivants:
- site 1
- site 2
- site 3
1. Qu’est ce qui est affiché par le programme suivant?
L1 = creer_liste()
L1 = inserer(L1,'site 1')
print(L1)
L1 = inserer(L1,'site 2')
print(L1)
L1 = inserer(L1,'site 3')
print(L1)
2. Lorsque l’on retourne en arrière, on veut acceder au dernier site visité. Supposons que cela retourne la valeur site 3
. Quelle instruction de l’interface de liste faut-il utiliser?
3. On souhaite alors que cela modifie la liste L1 en supprimant site 3
. Quelle instruction utilisant l’interface de liste va modifier L1 de cette façon?
4. On revient à la liste L1 contenant la navigation sur les 3 sites. Compléter la boucle non bornée pour former la liste python ['site 3', 'site 2', 'site 1']
à partir de la liste chainée L1:
L2 = []
while not liste_vide(L1):
# à completer
#
#
5. Ajouter au script les instructions qui vont déverser la liste python L2 dans une liste python L3. Cette liste L3 devra présenter les sites dans l’ordre de la navigation: ['site 1', 'site 2', 'site 3']
6. Ecrire l’implémentation de la fonction elements_liste
qui va retourner une liste python avec les éléments d’une liste chainée L mise en paramètre. Pour l’exemple précédent, cette fonction retourne la liste python L3 lorsque L est mise en paramètre de la fonction elements_liste
:
elements_liste(L)
# affiche ['site 1', 'site 2', 'site 3']
On utilisera à l’intérieur de la fonction une instruction de copie de la liste L afin de ne pas modifier L lors des traitements:
def elements_liste(L):
L_copie = list(L)
L2 = []
L3 = []
while not liste_vide(L_copie):
# à completer
#
#
#
Exercice sur la separation d’une liste
Compléter la fonction separe
qui sépare les éléments d’une liste en deux listes selon s’ils sont inférieurs (strictement) ou supérieurs (et égal) à une valeur v
:
def separe(L,v):
L_copie = list(L)
L_inf = creer_liste()
L_sup = creer_liste()
while not liste_vide(L_copie):
# à completer
# utilise les fonctions tete, queue et insere
#
#
return L_inf, L_sup
Compléter alors le programme qui affiche les 2 listes une fois celles-ci séparées. La liste L contiendra les valeurs à séparer. Pour utiliser les fonctions de l’interface des listes chainées (voir plus haut), on créé une liste chainée à partir d’un ensemble de valeurs mises entre []
:
L = creer_liste()
for elem in [1,3,20,18,16,11,101,12,15,2,5,4,2,8,1]:
L = inserer(L,elem)
v = 12
# appel de la fonction separe
print(L_inf)
print(L_sup)
# [1, [3, [11, [2, [5, [4, [2, [8, [1, []]]]]]]]]]
# [20, [18, [16, [101, [12, [15, []]]]]]]
Exercices sur les Tableaux statiques
On propose l’implémentation suivante pour les tableaux statiques:
T = (['lundi','mardi','mercredi','jeudi','vendredi'],5)
def taille(T):
"""exemple:
> taille(T)
> 5
"""
return T[1]
def ieme(T,i):
"""exemple:
> ieme(T,3)
> 'jeudi'
"""
return T[0][i]
def remplacer(T,i,e):
"""exemple:
> remplacer(T,2,'jour des enfants')
> T
> (['lundi','mardi','jour des enfants','jeudi','vendredi'],5)
"""
# à completer
Utiliser l’interface du tableau
1. Soit le tableau qui implémente les notes de Kyle dans les matières C1, C2, C3:
T = ([6, 7, 8], 3)
a. Ecrire l’instruction qui retourne la note de Kyle dans la matière C3.
b. Kyle n’a pas eu 8, mais 12/20 dans la matière C3. Ecrire l’instruction qui modifie sa note 8 en 12, à partir d’une fonction de l’interface des tableaux.
c. Compléter le script donné plus haut pour cette fonction.
2. Soit le tableau suivant qui implémente les notes de Kyle, Sean, Quentin et Zinedine dans les matières C1, C2, C3:
T = ([[6, 7, 8],
[10, 0, 10],
['?', '?', '?']
['?', '?', '?']], (4,3))
a. Recopier le tableau T et remplacer les ‘?’ par les bonnes valeurs (utiliser l’image plus haut). Que signifie le tuple (4,3)
placé comme 2e élément du tableau?
b. Utiliser l’instruction taille
de l’interface pour donner le nombre d’élèves dans le tableau? Puis le nombre de colonnes (matières).
c. Modifier la fonction remplacer
pour que celle-ci modifie la note dans la matière voulue pour un élève donné.
Par exemple: Pour modifier la note de la colonne 2 de l’élève au rang 0 (premiere ligne):
Si on veut lui mettre 12, on fera: remplacer(T,0,2,12)
remplacer(T,0,2,12)
T
# affiche
([[6, 7, 12],
[10, 0, 10],
['?', '?', '?']
['?', '?', '?']], ..)
Un nouveau type abstrait
Afin de gérer les notes des élèves de la classe de seconde 209, on veut définir un type abstrait qui permet de calculer sur les notes des élèves.
Ce type abstrait, appelé Classe_209
va utiliser l’interface des tableaux statiques définie plus haut. Mais il va aussi calculer la moyenne des notes grâce à 2 nouvelles fonctions de son interface:
moyenne
:
Fonction qui va calculer la moyenne m
de l’élève au rang eleve_i
(par exemple, pour Kyle, eleve_i
vaut 0) avec l’instruction:
i = 0 # Kyle
m = moyenne(T[0][i])
Pour programmer cette fonction moyenne(L)
, il faudra:
- parcourir toutes les notes de la liste
L
mise en paramètre. - Ajouter la note à une variable
s
, qui vaut 0 au depart. - Puis, à la fin, retourner la moyenne, c’est à dire $s / len(L)$
1. Programmez cette fonction
moyenne_matiere
Fonction qui va calculer la moyenne sur une matière mm
à partir du rang j
. Par exemple, pour C3, j
vaut 2, le rang dans le Tableau de notes):
j = 2 # colonne C3
mm = moyenne_matiere(T[0])
Pour programmer cette fonction moyenne_matiere(M)
, il faudra:
- Faire la somme $M[0][j] + M[1][j] + M[2][j] + M[3][j]$
- Calculer la moyenne
- retourner la valeur
2. Programmez cette fonction
moyenne glissante et tableau statique
Les courbes de données issues du monde réel sont souvent bruitées. Pour simuler ce type de données, nous allons créer une liste de valeurs cumulées aléatoires.
Pour créer et afficher ces valeurs cumulées, nous créons la liste signal2
qui est produite à partir de valeurs aléatoires (signal0
), puis cumulées dans signal2
:
import numpy as np
from numpy.random import randn
import matplotlib.pyplot as plt
plt.clf()
signal0 = (randn(800))*2
plt.plot(signal0,color='silver',label='Signal aleatoire')
plt.grid(True,which='both')
plt.legend(loc='best')
plt.title('Signal avec bruit')
signal2 = np.cumsum(randn(800))
plt.plot(signal2,color='red',label='Signal cumulé')
plt.grid(True,which='both')
plt.legend(loc='best')
plt.show()
Etapes:
- On fait une copie par valeur de
signal2
(liste des valeurs d’origine) danssignal_filtre
(liste dont les termes seront remplacés par la valeur moyenée):
signal_filtre = signal2.copy()
-
On choisit une certaine largeur de liste pour les valeurs dont on fait la moyenne. Par exemple largeur = 10.
-
Au rang i, dans la liste bruitée
signal2
: On prélève les valeurs entre les rangs $i- largeur//2$ et $i + largeur//2$ que l’on stocke dans un tableau STATIQUE appelésignal
. Ce tableau conserve la même taille pendant tout l’exercice. (ici, largeur = 10):
signal = signal2[i-largeur//2:i+largeur//2]
- On calcule la moyenne de valeurs de
signal
avec la fonctionmoyenne
vue dans l’exercice précédent.
signal_filtre[i] = moyenne(signal)
- On place la valeur moyenne dans
signal_filtre[i]
- On répète l’opération pour tous les index
i
compris entrelargeur//2,len(signal2)-largeur//2)
:
for i in range(largeur//2,len(signal2)-largeur//2):
Puis on affiche les graphique de signal2
(inchangé) et signal_filtre
(courbe lissée)
1. Suivre ces étapes pour obtenir les graphiques des courbes de données bruitées et lissées.
2. Créer une fonction lissage
à partir de votre script, qui prend en paramètres une liste L
et une largeur v
, et retourne une liste de valeurs filtrées par une moyenne glissante sur v
valeurs.
Liens et prolongements
- Types séquentiels natifs cours David Latreyte