Structures de données abstraites

I. Définitions

Un type abstrait de donnée est une spécification mathématique d'un ensemble de données et de l'ensemble des opérations que l'on peut effectuer sur ces données.

On parle de type abstrait car il ne définit nullement l'implantation du type, mais seulement les opérations faisables sur ce type.

Une des manières de définir un type abstrait de donnée consiste à utiliser les types abstraits algébriques.

Un type abstrait algébrique est une spécification mathématique d'un ensemble de données caractérisée par :

• Un nom ;
• Des constructeurs ;
• Des opérations, définies par des axiomes.

Une interface d'un type abstrait de données est défini par le nom du type et par l'ensemble des opérations définies sur le type en question.

Il y a de nombreux intérêts à définir des types abtraits de données. En voici quelques-uns :

• Cela permet de définir les besoins sans rentrer dans les détails d'implantation ;
• En donnant un nom universel à une structure, cela permet d'échanger plus facilement (entre humains et entre bibliothèques) ;
• Cela permet de raisonner formellement sur une structure et les manipulauations sur cette structure.

II. Exemple

Une définition des naturels sous la forme d'un type abstrait algébrique est la suivante (entiers de Peano) :

  Nom : Naturel
  

  Constructeurs
    0: Naturel
    s: Naturel → Naturel
  

  Opérateurs
  plus: Naturel x Naturel → Naturel
    plus(x, 0) = x
    plus(x, s(y)) = s(plus(x, y))
  
  fois: Naturel x Naturel → Naturel
    fois(x, 0) = 0
    fois(x, s(y)) = plus(x, fois(x, y))
  

Comme on peut le constater, les constructeurs et opérateurs sont typés par un profil, qui définit les nombres et types des paramètres, ainsi que le type de retour.

En l'occurence, les naturels selon Peano sont définis par 2 constructeurs :

• 0: constructeur sans paramètre, qui est un naturel ;
• s: constructeur qui, appliqué à un naturel, construit un autre naturel : son successeur. Ainsi, le naturel "2" est obtenu en appliquant le constucteur s au successseur de 0 : s(s(0))

Dans les langages orientés objets, la notion de type abstrait de donnée est souvent mise en oeuvre en utilisant les interfaces (ensemble nommé de profils de méthodes) : une inteface ne définit pas les constructeurs et les axiomes, mais donne au moins les opérations disponibles.