Tle NSI / Cours

1. Type abstrait de donnée (TAD)

Abstraction

La programmation orientée objet (POO) permet d'implémenter des types abstrait de données (TAD).

En sciences, l'abstraction est l'action de regrouper des caractéristiques et des processus communs à des entités.
Adopter une représentation abstraite commune pour une collection d'objets permet de simplifier et d'unifier leur manipulation.

Par exemple :

Les circuits électriques des appareils électroménagers (programmateurs, etc), autrefois fabriqués à l'aide de composants électroniques divers, sont remplacés par des circuits intégrés (microprocesseurs) du même type. Ainsi, un réfrigérateur et une machine à café peuvent intégrer une même puce assurant une même fonction.
Un langage informatique est une abstraction en lui-même, puisqu'il fait correspondre à une syntaxe qui lui est propre une suite de 0 et de 1 adaptés au matériel sur lequel le programme sera utilisé.

Pour décrire un TAD, nous allons adopter un mode de représentation proche de l'UML (Universal Modeling Language) : il s'agit du diagramme de classe. Une classe décrit les caractéristiques et les opérations communes à une collection d'objets.

Structure d'un diagramme de classe

Diagramme de classe :

Nom du TAD

operateur1(param1, param2, ...) : type_résultat
operateur2(param*, ...) [conditions] : type_résultat

...

Voici le descriptif d'un diagramme de classe :

la première ligne contient le Nom du TAD.
la deuxième partie contient les opérations applicables à ce TAD et forme son interface. Pour chaque opération, on précise :
- ses paramètres ou on laisse des parenthèses vides s'il n'y en a pas,
- des conditions éventuelles entre crochets
- et le type du résultat après « : », ou «vide» si l'opération ne renvoie rien.

Il existe 4 types d'opérations :

les constructeurs (constructor) : qui permettent de créer la structure de donnée,
les mutateurs (setter) : qui permettent de modifier la structure de donnée,
les accesseurs (getter) : qui permettent d'accéder à une information de la structure de donnée,
et les itérateurs (iterator) : qui permettent d'énumérer les éléments de la structure de donnée.

Ce diagramme de classe permet d'exprimer les spécifications d'un TAD, c'est-à-dire définir son interface sans préjuger de la façon dont il sera implémenté. En effet, selon le paradigme de programmation choisi par le développeur, plusieurs implémentations d'un même TAD sont possibles.

Dans la suite de ce chapitre, nous verrons l'implémentation de quatre TAD avec le paradigme de la programmation orientée objet (POO) :

les piles,
les files,
les listes
et les dictionnaires.

Les piles

Spécifications

Une pile (en anglais : stack) est un TAD fonctionnant selon le principe «dernier arrivé, premier sorti» (en anglais : last in, first out ou LIFO). C'est le principe d'une pile d'assiettes : la dernière ajoutée au sommet de la pile sera la première à être prise, donc à sortir de la pile. Dans un ordinateur, un cœur de processeur empile la plupart du temps les processus.

	A
	↓
4
3
2
1
0

	B
	↓
4
3
2
1
0	A

	B
	↑
4
3
2
1	B
0	A

	A
	↑
4
3
2
1
0	A



4
3
2
1
0

Nous allons spécifier le TAD qu'est une pile. Pour cela, il faut définir son interface.

Diagramme de classe :

Pile

créer_pile(taille_pile) : pile vide
empiler(pile, élément) [pile non remplie] : vide
dépiler(pile) [pile non vide] : élément
est_vide(pile) : booléen
est_pleine(pile) : booléen
nbr_éléments_dans(pile) : entier

Interface :

«créer pile» : renvoie une pile vide de la taille demandée
«empiler» : ajoute un élément sur la pile (push en anglais) si elle n'est pas remplie
«dépiler» : enlève un élément de la pile et le renvoie (pop en anglais)
«est_vide» : renvoie vrai si la pile est vide, faux sinon
«est_pleine» : renvoie vrai si la pile est remplie, faux sinon
«nbr_éléments_dans» : renvoie le nombre d'éléments dans la pile

Chap. 1 : Programmation Orientée Objet / 1 - TAD Mémorisation 0x Réussite 0/0

Démarrer

Classer ces opérations selon leur type :

constructeur

mutateur

accesseur

Placer tous les éléments dans les bons groupes par glisser-déposer ou clics successifs.

Implémentation

Voici l'implémentation du TAD en Python avec le paradigme POO.

# -*- coding: utf-8 -*-

class Pile :
    """Implémentation du TAD «Pile» en Python. """

    def __init__(self, taille) :
        """Instancier un objet de la classe Pile. """
        self.taille = taille
        self.contenu = []

    def empiler(self, element) :
        """Empile un élément au sommet de la pile. """
        if self.est_pleine() :
            print("Impossible, la pile est pleine")
        else :
            self.contenu.append(element)

    def depiler(self) :
        """Extrait et retourne le sommet de la pile. """
        if self.est_vide() :
            print("Impossible, la pile est vide. ")
        else :
            return self.contenu.pop()

    def est_vide(self) :
        """La pile est-elle vide ? """
        if self.contenu == [] :
            return True
        else :
            return False

    def est_pleine(self) :
        """La pile est-elle pleine ? """
        if len(self.contenu) >= self.taille :
            return True
        else :
            return False

    def nbr_elements(self) :
        """Donne le nombre d'éléments dans la pile"""
        return len(self.contenu)


pileA = Pile(6)

for k in range(1,10) :
    print("On empile l'élément ",k)
    pileA.empiler(k)
    print("Nb d'éléments dans la pile : ",pileA.nbr_elements())

print("On dépile 2 éléments : ", pileA.depiler(), pileA.depiler())
print("Nb d'éléments dans la pile : ", pileA.nbr_elements())

Explications :

Le mot clé class en python permet de définir une classe d'objet. Le bloc indenté suivant, contient ses attributs (structure de données) et ses méthodes (interface).
En python, selon la convention PEP8, la première lettre du nom d'une classe est en majuscule, ses attributs et méthodes commencent par une minuscule.
Le mot-clé self (en anglais : soi) fait référence à l'instance de cette classe. Il faut remarquer que self est passé en premier paramètre de chaque méthode, même s'il n'est pas forcément utilisé dans la méthode.
De manière imagée, une classe est comme un moule/un modèle permettant de fabriquer plusieurs objets de cette même classe. Ici, des piles de tailles différentes. Cette fabrication, que l'on appelle instanciation, est réalisée par la méthode constructeur __init__. Celle-ci définit les attributs de l'objet qui part vivre dans la mémoire vive de l'ordinateur. Une instance de l'objet a été créée.

Concrètement :

Une fois le bloc class terminé, on peut instancier une pile de taille 6, en écrivantpileA = Pile(6) . Dans le cas général : mon_objet = Nom_Classe(paramètres). En effet, écrire le nom de la classe appelle son constructeur (méthode __init__). Il faut donc donner les paramètres nécessaires à ce dernier, c'est-à-dire les attributs de l'objet à construire (mais sans le self).
Si l'on souhaite appeler une méthode, par exemple empiler('truc') de l'objet pileA, on écrit :
- soit pileA.empiler('truc') qui signifie j'applique la méthode empiler à l'instance pileA (cas général : mon_objet.ma_méthode(paramètres)).
- soit Pile.empiler(pileA, 'truc') qui signifie j'utilise la méthode empiler de la classe Pile à l'objet pileA avec le paramètre "truc".
et ces deux syntaxes sont équivalentes.
Certaines méthodes dites publiques sont vouées à être appelées par l'utilisateur tandis que d'autres sont dites privées car elles sont appelées uniquement par le développeur ou par d'autres méthodes de l'objet mais en aucun cas par l'utilisateur. Par convention, dans le cas d'une méthode privé, on ajoutera un underscore _ au début de son nom en python.

Remarque :

En python, nous aurions pu aussi implémenter ce TAD avec le paradigme procédural grâce à une liste comme structure de donnée pour stocker les valeurs de la pile et des fonctions pour agir sur la liste.
Ici, il a été choisi que le contenu de la pile soit stockée dans une liste mais d'autres choix sont possibles. Il y a plusieurs implémentations possibles d'un même TAD. Elles dépendent des choix et des compétences du développeurs.

Vocabulaire comparé entre la théorie des TAD et l'implémentation en python POO :

Vocabulaire du TAD	Vocabulaire de l'implémentation en POO	Exemple en python
type abstrait de donnée (TAD)	classe d'objet	`class Nom :`
structure de donnée	attributs	`self.attribut`
opérateurs	méthodes	`def methode(self, ...):`
constructeur	méthode	`def __init__(self, ...):`

Chap. 1 : Programmation Orientée Objet / 3 - POO en python Mémorisation 0x Réussite 0/0

Démarrer

Associer chaque ligne (instruction) à son explication :

pileA = Pile(6) for k in range(1,10) : pileA.empiler(k) print(pileA.depiler(), pileA.depiler())

Ligne 1

Ligne 2

Ligne 3

Ligne 4

Former les bons couples par glisser-déposer ou clics successifs.

Les files

Spécifications

Une file (en anglais : queue) est un TAD fonctionnant selon le principe «premier arrivé, premier sorti» (en anglais : first in, first out : FIFO). C'est le principe d'une file d'attente : la première personne arrivée doit passer en premier, donc sortir de la file en premier. On utilise beaucoup cette structure en gestion des stocks (pour des produits périssables). Dans un ordinateur, la file d'impression fonctionne de cette manière ainsi que certains gestionnaires de téléchargement.

	A
	↓
4
3
2
1
0

	B
	↓
4
3
2
1	B
0	A



4
3
2
1
0	B
	↓
	A



4
3
2
1
0
	↓
	B

Diagramme de classe :

File

créer_file(taille_file) : file vide
enfiler(file, élément) [file non pleine] : vide
défiler(file) [file non vide] : élément
est_vide(file) : booléen
est_pleine(file) : booléen
nbr_éléments_dans(file) : entier

Interface :

«créer_file» : renvoie une file vide de la taille demandée
«enfiler» : ajoute un élément dans la file (enqueue en anglais) si elle n'est pas remplie
«défiler» : retire un élément de la file et le renvoie (dequeue en anglais)
«est_vide» : renvoie vrai si la file est vide, faux sinon
«est_pleine» : renvoie vrai si la file est remplie, faux sinon
«nbr_éléments_dans» : renvoie le nombre d'éléments dans la file

Chap. 1 : Programmation Orientée Objet / 2 - Piles, files, listes et dictionnaires Mémorisation 0x Réussite 0/0/10

Démarrer

Quelle est la valeur de la variable A à la fin de l'exécution de cet algorithme ?

creer_file(file, 6) enfiler(file, 2) enfiler(file, 5) enfiler(file, 2) defiler(file) → B defiler(file) → A enfiler(file, 5)

Implémentation

Chap. 1 : Programmation Orientée Objet / 2 - Piles, files, listes et dictionnaires Mémorisation 0x Réussite 0/0

Démarrer

En s'inspirant de l'implémentation de la classe Pile, implémenter (directement) une classe File en python en POO.

On pourra utiliser les méthodes des listes (voir docs.python.org).

class File : """Implémentation du TAD «File» en Python. """ def __init__(self, taille) : """Ce constructeur sert à instancier un objet de la classe File. """ self.taille = taille self.contenu = [] def enfiler(self, element) : """Enfile un élément dans la file. """ if self.est_pleine() : print("Impossible, la file est pleine") else : self.contenu.append(element) def defiler(self) : """Extrait et retourne l'élément au début de la file. """ if self.est_vide() : print("Impossible, la file est vide. ") else : return self.contenu.pop(0) def est_vide(self) : """La file est-elle vide ? """ return self.contenu == [] def est_pleine(self) : """La file est-elle pleine ? """ return len(self.contenu) >= self.taille def nbr_elements(self) : """Donne le nombre d'éléments dans la file""" return len(self.contenu)

Les listes

Spécifications

Une liste (en anglais : list) permet de regrouper des données de manière à pouvoir y accéder directement par le biais de leur indice (en anglais : index). On parle aussi de position, de rang ou de place.

Valeur	45	154	58	78	31	5	74
Indice	0	1	2	3	4	5	6

Diagramme de classe :

Liste

créer_liste(liste, taille_liste) : liste vide
insérer(liste, el, i) [liste non pleine] : vide
supprimer(liste, i) : vide
rechercher(liste, el) : entier
lire(liste, i) : élément
modifier(liste, i, el) : vide
longueur(liste) : entier
est_vide(liste) : booléen
est_pleine(liste) : booléen

Interface :

«créer_liste» : renvoie une liste vide de la taille demandée
«insérer» : ajoute un élément el dans la liste, à la place i, si elle n'est pas remplie
«supprimer» : retire de la liste l'élément qui occupe l'indice i
«rechercher» : renvoie l'indice de l'élément el
«lire» : renvoie l'élément correspondant à l'indice donné
«modifier» : remplace l'élément correspondant à l'indice donné par l'élément donné
«longueur» : renvoie le nombre d'éléments dans la liste
«est_pleine» : renvoie vrai si la liste est pleine, faux sinon.

Chap. 1 : Programmation Orientée Objet / 2 - Piles, files, listes et dictionnaires Mémorisation 0x Réussite 0/0

Démarrer

Que fait cet algorithme ? Donner sa complexité en fonction de la taille de la liste notée `n`.

Fonction INSERER(liste, x, i) : Si (i >= longueur(liste)) : Retourner Faux Sinon : Créée un emplacement vide dans la liste Pour k allant de longueur(liste)-1 à i avec un pas de -1 : L(k) = L(k-1) L(i) = x Retourner Vrai

Cet algorithme permet d'insérer un élément dans une liste. Pour cela il vérifie que l'emplacement d'insertion n'est pas en dehors de la liste. Sinon, il décale tous les éléments au-delà de l'emplacement d'insertion et inscrit la valeur x à insérer à son emplacement i. On constate que cet algorithme parcours une fois la liste (même moins que la liste). Il s'agit donc d'une complexité linéaire en `O(n)`.

Implémentations

La plupart des langages de programmation implémentent ce TAD sous la forme d'un tableau (en anglais : array) à une dimension. La plupart du temps, ces tableaux utilisent des adresses contiguës en mémoire : de fait, leur taille dépend de la place disponible à côté en mémoire.
Python implémentent les listes sous forme de tableaux à taille dynamique, qui utilisent le principe des listes chaînées où chaque élément contient l'adresse en mémoire du suivant. Il est ainsi très facile d'insérer ou de supprimer des éléments.

Il est aussi possible de rencontrer des listes doublement chaînées (chaque élément est attaché à l'adresse de son successeur et de son prédécesseur), ou bien de former des cycles (au lieu de pointer sur une fin de liste, on pointe sur le premier élément créant ainsi une boucle.

Le type list en python va beaucoup plus loin que la structure abstraite commune «liste» dont nous venons de parler. Il faut garder à l'esprit que même s'il est possible de l'ignorer en utilisant python, on a bien affaire à des listes chaînées en mémoire. Le type list python est donc assez «lourd» mais très complet et flexible, donc il ne faut pas hésiter à l'utiliser.
Voici un rappel des méthodes communes sur les listes, ci-dessous. Voir aussi la documentation officielle.

ls = [14, 9, 8, 8]
print(ls)
print("Longueur de la liste :", len(ls))
print("Somme des valeurs de la liste :", sum(ls))
print("Ajouter un élément à la fin (ici 1000) :", end=" ")
ls.append(1000)
print(ls)
print("Enlever un élément à une certaine place (ici place 1):", end=" ")
ls.pop(1)
print(ls)
print("Vérifier la présence d'une valeur dans la liste (ici 12) :", 12 in ls)
print("Compter le nombre d'occurence d'une valeur (ici 8) :", ls.count(8))
print("Trouver la première place d'une valeur (ici 8) :", ls.index(8))
print("Enlever une valeur (ici 8) :", end=" ")
ls.remove(8)
print(ls, end=" ")
print("C'est la première apparition qui est enlevée !")
print("Concaténer deux listes :", ls+[4, 6])
print("Concaténer plusieurs fois une liste avec elle-même :", 3*ls)
print("Trier une liste :", end=" ")
ls.sort()
print(ls)
print("8nverser une liste :", end=" ")
ls.reverse()
print(ls)
print("Créer une sous-listes : ", ls[:2])

Les dictionnaires

À la différence des listes, qui sont indexées par des nombres, les dictionnaires sont indexés par des clés, qui, au lieu d'être uniquement des nombres entiers (comme pour les listes), peuvent être n'importe quel objet dans le cadre abstrait, et dans le cadre de leur implémentation en python, n'importe quel objet immuable (non «modifiable» dans le sens ou pour obtenir une copie de l'objet, il suffit de copier sa référence en mémoire).
En langage python, les types bool, tuple, str, bytes, frozenset et range sont immuables, ainsi que les types numériques int, float et complex. Les objets tuple sont des listes immuables d'objets hétérogènes en python. On peut voir le type tuple comme le pendant immuable de list, et frozenset comme le pendant immuable de set.

Diagramme de classe :

Dictionnaire

créer_dico_vide() : Dictionnaire
insérer(dico, clé, valeur) : vide
supprimer(dico, clé) [si la clé existe] : vide
lire(dico, clé) [si la clé existe] : type T
rechercher(dico, clé) : booléen

Interface du TAD Dictionnaire :

«insérer» : insère une entrée clé-valeur dans le dictionnaire ;
«supprimer» : supprimer l'entrée correspondant à la clé donnée ;
«lire» : renvoie l'entrée correspondant à la clé donnée ;
«rechercher» : retourne vrai ou faux selon que la clé est dans le dictionnaire ou non.

Chap. 1 : Programmation Orientée Objet / 2 - Piles, files, listes et dictionnaires Mémorisation 0x Réussite 0/0

Démarrer

Associer chaque situation au TAD le plus pertinent ?

une liste

une pile

une file

un dictionnaire

Placer tous les éléments dans les bons groupes par glisser-déposer ou clics successifs.

Application : TAD «Vecteur»

Spécifications

Diagramme de classe :

Vecteur

créer_vecteur(x, y) : vecteur
afficher(vecteur) : vide
modifier(vecteur, x, y) : vide
est_nul(vecteur) : booléen
det(vecteur1, vecteur2) : nombre

Interface du TAD Vecteur :

«créer_vecteur» : renvoie un vecteur avec les coordonnées demandées
«afficher» : affiche dans la console les coordonnées du vecteur (cette méthode ne retourne rien)
«modifier» : permet de modifier l'objet vecteur à partir de nouvelles coordonnées données
«est_nul» : vérifie si un vecteur a ses coordonnées égales à zéro en renvoyant vrai ou faux
«det» : vérifie si deux vecteurs sont colinéaires (même direction)

Implémentation

1446

Aide :

La classe d'objet vecteur pourra avoir comme attributs : 𝑥 et 𝑦 deux nombres (int ou float) correspondant aux coordonnées du vecteur
La norme d'un vecteur se calcule par la formule de Pythagore 𝑛 = √
𝑥² + 𝑦²
et pourra être calculée directement dans le constructeur __init__ (lors de l'instanciation d'un vecteur).
Pour vérifier la colinéarité entre deux vecteur, écrire def det(self, other) : avec other désignant le deuxième vecteur. La formule de calcul sera ainsi self.x*other.y-self.y*other.x.

Guide

Créer un vecteur u(2, 4) et l'afficher pour tester.
Modifier u en u(0.2, 1) et l'afficher. La norme a-t-elle correctement été modifiée, pourquoi ? Sinon, corriger la méthode modifier en conséquence.
Créer v(1.4, 7) et tester la méthode det sur u et v. Comparer ce résultat à 0 avec ==. Verdict : se méfier des tests d'égalité sur les flottants...
Faire w = v, puis del v ; que devient w ? Et en faisant del w ensuite ?

Remarques :

Python ne dispose pas de variables ou méthodes réellement privées contrairement au C++ et à Java par exemple. Si l'on veut préciser qu'un attribut ou une méthode est privé c'est-à-dire que l'utilisateur ne devrait pas y avoir accès, on ajoute, par convention, un underscore _ devant son nom. Cette pratique est répendue mais sans effet (cf. doc Python).

Surcharge d'opérateur en python

La surcharge permet de redéfinir les symboles opératoires courants pour les adapter à un comportement voulu pour une classe donnée. En voilà un bon résumé (d'après les cours en ligne de l'Université Paris-Sud) :

Méthodes d'affichage :

utilisation	nom
conversion en string pour la fonction `print`	`__str__(self)`
affichage lors d'un appel en console	`__repr__(self)`

Opérations mathématiques : Définir ou redéfinir les opérateurs standards permet d'utiliser les symboles mathématiques pour de nouvelles classes d'objets :

opération	symbole	méthode	symbole unaire	méthode
addition	+	`__add__(self,other)`	+=	`__iadd__(self,other)`
soustraction	-	`__sub__(self,other)`	-=	`__isub__(self,other)`
multiplication	*	`__mul__(self,other)`	*=	`__imul__(self,other)`
division	/	`__truediv__(self,other)`	/=	`__itruediv__(self,other)`
élévation à la puissance	**	`__pow__(self,other)`	**=	`__ipow__(self,other)`
division entière	//	`__floordiv__(self,other)`	//=	`__ifloordiv__(self,other)`
reste de la division entière (modulo)	%	`__mod__(self,other)`	%=	`__imod__(self,other)`

opération	symbole	méthode
opposé	-	`__neg__(self)`
positif	+	`__pos__(self)`
valeur absolue	abs()	`__abs__(self)`

Opérateurs de comparaison :

opération	symbole	méthode
égal	==	`__eq__(self,other)`
non égal	!= ou <>	`__ne__(self,other)`
strictement inférieur	<	`__lt__(self,other)`
strictement supérieur	>	`__gt__(self,other)`
inférieur ou égal	<=	`__le__(self,other)`
supérieur ou égal	>=	`__ge__(self,other)`

Opérateurs de conteneurs : destinés à des objets pouvant être des conteneurs.

opération	syntaxe	méthode
dimension	`len(objet)`	`__len__(self)`
accès aux éléments en lecture	`objet[key]`	`__getitem__(self,key)`
accès aux éléments en écriture	`objet[key] = ...`	`__setitem__(self,key,value)`

Chap. 1 : Programmation Orientée Objet / 2 - Piles, files, listes et dictionnaires Mémorisation 0x Réussite 0/0

Démarrer

En modifiant la classe Vecteur précédente, permettre une addition de deux vecteurs par la surcharge de l'opérateur +

Il faut définir une méthode supplémentaire avec def __add__(self,other):.

En anglais :

programmation orientée objet (POO) : oriented object programming (OOP)
pile : stack
dernier arrivé, premier sorti : last in, first out (LIFO)
empiler : push
dépiler : pop
file : queue
premier arrivé, premier sorti : first in, first out (FIFO)
enfiler : enqueue
défile : dequeue
liste : list
indice : index
tableau : array