TNSI : Types Abstraits de Données vs Structures de Données

Introduction

Les algorithmes opèrent sur des données (données en entrée, données auxiliaires), et sont en charge notamment, de manière centrale, de la Représentation des données et de la manipulation des données.

On peut différencier classiquement deux niveaux de représentation :

• niveau Abstrait ou niveau Logique = Type Abstrait de Données ou TAD

  • Ce niveau regroupe tout un ensemble de routines (procédures ou fonctions) abstraites, définissant certaines opérations de manipulation des données.

  • L'ensemble de toutes ces routines est appelée l'INTERFACE (abstraite) de la structure de données abstraites. INTERFACE = Comment on s'en sert?

  • Utiliser un objet ou une fonctionnalité par son interface abstraite permet de raisonner indépendamment des détails de son implémentation, ce qui est une tâche qui revient à la Structure de Données :

• niveau IMPLÉMENTATION = Structure de Données

  • C'est la Structure de données qui est en charge de l'implémentation du type abstrait de données, en particulier :
    • de la Représentation concrète des données en mémoire
    • de l'implémentation des opérations de manipulation de données

  IMPLÉMENTATION = Comment ils fonctionnent ?

INTERFACE vs IMPLÉMENTATION

Interface

Implémentation

On peut choisir comme image une machine à café à capsule, dans laquelle on peut distinguer :

• l' INTERFACE : les boutons, les voyants, le levier…
• l' IMPLÉMENTATION : les électrovannes, la pompe, le bloc de chauffe, voire le déroulement des opérations Utilisateur : Pas besoin de savoir comment fonctionne la machine à l'intérieur (implémentation), pour se faire un café (interface)...

On retient :

Interface vs Implémentation

• Une Interface ou une Spécification de la Structure de Données décrit:
  • Quelles sont les valeurs possibles ? et
  • Quelles sont les opérations avec lesquels on peut la manipuler?, et
  • Quel est le résultat qu'ils produisent?.
• À l'opposé, Une Implémentation ou Réalisation de la Structure de Données :
  • est en charge de la Représentation concrète des données en mémoire
  • contient le code et la manière précis permettant de réaliser l'opération spécifiée par l'interface. Il n'est pas nécessaire de connaître l'implémentation pour manipuler la structure de données.

Types Abstraits de Données (TAD) : niveau Interface / Utilisateur

En algorithmique, les algorithmes opèrent sur des données de natures différentes. Dans un premier niveau, du point de vue Utilisateur, il semble important et intéressant de proposer des algorithmes qui soient :

• indépendants d'un langage de programmation, et même
• indépendants d'une implémentation particulière.

A ce premier niveau, les données sont manipulées de manière abstraite via une interface :

Type Abstrait (de Données)

Un Type Abstrait (de Données) (TAD), ou Structure de Données Abstraite , ou Abstract Data Type (ADT) , est une collection/ensemble d'éléments/données définis par :

• une notation pour les décrire
• des Primitives : des opérations agissant sur ses données/éléments (c'est-à-dire leur interface), indépendamment du langage de programmation.
• une Sémantique : certaines propriétés que doivent vérifier ces opérations, pouvant se subdiviser en:
  • des Pré-conditions : Des conditions/propriétés qui définissent l'existence des opérations (lorsque celles-ci sont partiellement définies).
  • des Axiomes : pour décrire le comportement attendu des opérations.

Un type abstrait de données (TAD) correspond au point de vue de l'Utilisateur, et non pas de l'implémenteur. Il reviendra ensuite à la Structure de Données de les implémenter.

Principaux Types de Données Abstraits

• Structures Linéaires / Séquentielles :
  • Listes
  • Piles
  • Files
  • (Files de Priorité, etc..)
• Structures Récursives / Hiérarchiques / Arborescentes :
  • (Listes)
  • Arbres (généraux)
  • Arbres Binaires, ...
• Structures Relationnelles :
  • Graphes
• Structures à Accès par Clé :
  • Tableaux (Statiques vs Dynamiques)
  • Dictionnaires, ou Tableaux Associatifs, ou Table d'Association

Structures de Données

Définition

Structure de Données

Une Structure de Données est en charge d'organiser, de stocker et de gérer les données. Une Structure de données est une implémentation d'un type de abstrait de données, donc en particulier elle est en charge de :

• la Représentation concrète des données en mémoire
• l'implémentation des opérations/primitives du type abstrait de données

Une structure de données correspond au point de vue de l'implémenteur, et non pas de l'utilisateur (Type Abstrait de Données). Un type de données abstrait peut donc être implémenté de plusieurs manières distinctes en des structures de données abstraites.

en Python

En Python, on pourra penser par exemple aux structures de données (appelés types de données en Python) : list et dict. En Python, la structure de données list est un faux-ami : il implémente le type abstrait de données Tableau Dynamique.

Opérations de base d'une Structure de Données : CRUD

Classiquement, une Structure de Données fournit normalement au minimum les opérations de base suivantes, usuellement notées CRUD (Create, Read, Update, Delete ) :

• Create / Insertion
• Read / Lecture
• Update / Modification
• Delete / Suppression

Complexité des Structures de données

C'est (forcément) la Structure de Données, et non pas le type de Données Abstrait, qui détermine la complexité (en temps mais aussi en espace) de chacune des opérations de la Structure.

PRÉCISION : Complexité d'Accès aux Données

Accéder à / Rechercher une donnée dans la structure de données est un problème totalement indépendant du reste des opérations (e.g. CRUD): C'est pourquoi on étudie / compte séparément ce que l'on appelle la Complexité d'Accès.

Quelques exemples de Complexités des Types de Python

Complexité des Types de Python

\(n\) désigne la taille du conteneur courant. \(k\) désigne soit la taille d'un paramètre, soit le nombre d'éléments dans ce paramètre.

Opérations sur les list	Cas Moyen	Pire des Cas (amorti)
Copy	\(O(n)\)	\(O(n)\)
Append	\(O(1)\)	\(O(1)\)
Pop (le dernier)	\(O(1)\)	\(O(1)\)
Pop (au milieu)	\(O(n)\)	\(O(n)\)
Insert	\(O(n)\)	\(O(n)\)
Lire item	\(O(1)\)	\(O(1)\)
Modifier item	\(O(1)\)	\(O(1)\)
Supprimer item	\(O(n)\)	\(O(n)\)
Itération	\(O(n)\)	\(O(n)\)
Lire Slice/Tranche	\(O(k)\)	\(O(k)\)
Supprimer Slice/Tranche	\(O(n)\)	\(O(n)\)
Modifier Slice/Tranche	\(O(k+n)\)	\(O(k+n)\)
Extend	\(O(k)\)	\(O(k)\)
Sort	\(O(n.log(n))\)	\(O(n.log(n))\)
Multiplication	\(O(nk)\)	\(O(nk)\)
\(x\) in \(lst\)	\(O(n)\)	\(\,\)
min(\(lst\)), max(\(lst\))	\(O(n)\)	\(\,\)
Lire longueur	\(O(1)\)	\(O(1)\)

Opérations sur les dict	Cas Moyen	Pire des Cas (amorti)
\(k\) in \(d\)	\(O(1)\)	\(O(n)\)
Copy	\(O(n)\)	\(O(n)\)
Lire item	\(O(1)\)	\(O(n)\)
Modifier item	\(O(1)\)	\(O(n)\)
Supprimer item	\(O(1)\)	\(O(n)\)
Itération	\(O(n)\)	\(O(n)\)

ALLER PLUS LOIN La page suivante du wiki de Python, liste de manière plus complète, les complexités de certains autres Types de données Python.