Types de données abstraits

Un Type de Données Abstrait (TDA) est une spécification mathématique d'un type de données qui définit les opérations pouvant être effectuées sur ce type de données, sans se soucier de la manière dont ces opérations sont implémentées. En d'autres termes, un TDA décrit le "quoi faire" sans détailler le "comment faire".

Les concepts clés sont :

• Définition TDA : C'est une description logique d'un ensemble de données et des opérations permises sur ces données. L'utilisateur d'un TDA n'a pas besoin de connaître les détails internes de son implémentation.
• Séparation interface/implémentation : L'interface est l'ensemble des opérations (méthodes) disponibles pour manipuler le TDA. L'implémentation est le code interne qui réalise ces opérations. Le TDA garantit que seule l'interface est visible de l'extérieur.
• Encapsulation : C'est le principe qui consiste à regrouper les données et les méthodes qui les manipulent au sein d'une même entité, tout en cachant les détails internes de l'implémentation. Cela protège les données d'un accès direct et non contrôlé. L'encapsulation est fondamentale pour la robustesse du code.

L'utilisation des TDA apporte de nombreux avantages dans le développement logiciel :

• Modularité : Le code est divisé en modules indépendants (les TDA). Chaque module peut être développé et testé séparément, ce qui simplifie la compréhension et la gestion de projets complexes.
• Réutilisabilité : Un TDA bien conçu peut être réutilisé dans différentes parties d'un même projet ou dans d'autres projets. Par exemple, une pile peut être utilisée pour gérer l'historique d'un navigateur web ou pour évaluer des expressions mathématiques.
• Maintenance facilitée : Si l'implémentation interne d'un TDA doit être modifiée (par exemple pour optimiser les performances), cela n'affecte pas le code qui utilise ce TDA, tant que l'interface reste inchangée. Cela réduit considérablement les risques d'introduire des bugs.
• Masquage d'information (ou information hiding) : C'est une conséquence directe de l'encapsulation. Les détails complexes de l'implémentation sont cachés à l'utilisateur du TDA, qui n'a besoin de connaître que l'interface. Cela simplifie l'utilisation du code et réduit la charge cognitive du programmeur.

Vous utilisez probablement déjà des TDA sans le savoir. Voici quelques exemples très courants :

• Listes : Permettent de stocker une collection ordonnée d'éléments. Les opérations typiques incluent l'ajout, la suppression, la recherche ou l'accès à un élément par son index.
• Piles (Stacks) : Gèrent les éléments selon le principe "dernier entré, premier sorti" (LIFO).
• Files d'attente (Queues) : Gèrent les éléments selon le principe "premier entré, premier sorti" (FIFO).
• Dictionnaires (Maps/Hash Tables) : Permettent de stocker des paires clé-valeur et de récupérer rapidement une valeur à partir de sa clé.

Ces structures sont des TDA car leur comportement est défini par les opérations qu'elles offrent, indépendamment de la manière dont ces opérations sont réalisées en interne (par exemple, une liste peut être implémentée avec un tableau dynamique ou une liste chaînée).

Une pile est un TDA qui fonctionne selon le principe LIFO (Last In, First Out), ce qui signifie "dernier entré, premier sorti". Imaginez une pile d'assiettes : vous ajoutez (empilez) une nouvelle assiette sur le dessus, et lorsque vous voulez en prendre une, vous prenez toujours celle du dessus (la dernière que vous avez posée).

• Last In, First Out : Le dernier élément ajouté à la pile est le premier à en être retiré.
• Analogie pile d'assiettes : C'est l'exemple le plus parlant. Les assiettes sont ajoutées et retirées par le haut.
• Ordre d'accès : Seul le sommet de la pile est directement accessible pour l'ajout ou le retrait d'éléments.

Les opérations fondamentales d'une pile sont :

• push(élément) (empiler) : Ajoute un élément au sommet de la pile.
• pop() (dépiler) : Retire et retourne l'élément au sommet de la pile. Si la pile est vide, cette opération doit généralement lever une erreur.
• peek() ou top() (sommet) : Retourne l'élément au sommet de la pile sans le retirer. Si la pile est vide, cela lève aussi une erreur.
• is_empty() (est_vide) : Vérifie si la pile ne contient aucun élément. Retourne True si la pile est vide, False sinon.
• size() (taille) : Retourne le nombre d'éléments dans la pile.

En Python, une pile peut être facilement implémentée à l'aide d'une liste standard, car les listes Python sont des tableaux dynamiques qui permettent des ajouts et suppressions rapides en fin de liste.

class Pile:
    def __init__(self):
        self._elements = [] # La liste Python sert de support de stockage

    def is_empty(self):
        return len(self._elements) == 0

    def push(self, element):
        self._elements.append(element) # Ajout en fin de liste

    def pop(self):
        if self.is_empty():
            raise IndexError("pop() sur une pile vide")
        return self._elements.pop() # Suppression en fin de liste

    def peek(self):
        if self.is_empty():
            raise IndexError("peek() sur une pile vide")
        return self._elements[-1] # Accès au dernier élément

    def size(self):
        return len(self._elements)

# Exemple d'utilisation
ma_pile = Pile()
ma_pile.push(10)
ma_pile.push(20)
print(f"Sommet de la pile : {ma_pile.peek()}") # Affiche 20
print(f"Taille de la pile : {ma_pile.size()}") # Affiche 2
print(f"Élément dépilé : {ma_pile.pop()}") # Affiche 20
print(f"Sommet de la pile : {ma_pile.peek()}") # Affiche 10
ma_pile.pop()
print(f"La pile est-elle vide ? {ma_pile.is_empty()}") # Affiche True
# ma_pile.pop() # Cela lèverait une IndexError

• Utilisation des méthodes listes : append() pour push, pop() pour pop. L'accès au sommet (peek) se fait avec l'index [-1].
• Gestion des erreurs (pile vide) : Il est crucial de vérifier si la pile n'est pas vide avant de tenter un pop() ou un peek(). Python lèvera une IndexError si on tente d'accéder à un index inexistant ou de pop sur une liste vide.
• Complexité des opérations : Pour une implémentation basée sur une liste Python, les opérations push, pop, peek, is_empty, et size ont une complexité temporelle constante en moyenne, notée $O(1)$. C'est très efficace.

Les piles sont utilisées dans de nombreux domaines de l'informatique :

• Annuler/Rétablir (undo/redo) : Les actions effectuées par l'utilisateur sont stockées dans une pile "undo". Pour annuler, on dépile l'action précédente. Pour rétablir, on la déplace vers une pile "redo".
• Évaluation d'expressions postfixées (notation polonaise inversée) : Les piles simplifient l'évaluation des expressions arithmétiques sans parenthèses.
• Gestion des appels de fonctions : Le système d'exploitation utilise une "pile d'appels" (call stack) pour gérer les fonctions. Lorsqu'une fonction est appelée, ses informations sont empilées. Lorsqu'elle se termine, elles sont dépilées. C'est ainsi que sont gérées les fonctions récursives.
• Parcours de graphes et d'arbres : Notamment le parcours en profondeur (DFS).
• Rétro-cheminement (backtracking) : Pour explorer toutes les solutions possibles à un problème.

Une file d'attente est un TDA qui fonctionne selon le principe FIFO (First In, First Out), ce qui signifie "premier entré, premier sorti". C'est comme une file d'attente à la caisse d'un supermarché : la première personne qui arrive est la première servie.

• First In, First Out : Le premier élément ajouté à la file est le premier à en être retiré.
• Analogie file d'attente : Les personnes rejoignent la file par l'arrière et en sortent par l'avant.
• Ordre d'accès : Les éléments sont ajoutés à une extrémité (l'arrière ou la queue) et retirés de l'autre extrémité (l'avant ou la tête).

Les opérations fondamentales d'une file sont :

• enqueue(élément) (enfiler) : Ajoute un élément à l'arrière de la file.
• dequeue() (défiler) : Retire et retourne l'élément situé à l'avant de la file. Si la file est vide, cette opération doit lever une erreur.
• front() ou peek() (premier élément) : Retourne l'élément situé à l'avant de la file sans le retirer. Si la file est vide, cela lève aussi une erreur.
• is_empty() (est_vide) : Vérifie si la file ne contient aucun élément. Retourne True si la file est vide, False sinon.
• size() (taille) : Retourne le nombre d'éléments dans la file.

L'implémentation d'une file avec une liste Python est possible, mais il faut faire attention à la performance.

class File:
    def __init__(self):
        self._elements = []

    def is_empty(self):
        return len(self._elements) == 0

    def enqueue(self, element):
        self._elements.append(element) # Ajout en fin de liste (O(1) en moyenne)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue() sur une file vide")
        return self._elements.pop(0) # Suppression au début de liste (O(n))

    def front(self):
        if self.is_empty():
            raise IndexError("front() sur une file vide")
        return self._elements[0] # Accès au premier élément (O(1))

    def size(self):
        return len(self._elements)

# Exemple d'utilisation
ma_file = File()
ma_file.enqueue("Alice")
ma_file.enqueue("Bob")
print(f"Premier élément de la file : {ma_file.front()}") # Affiche Alice
print(f"Taille de la file : {ma_file.size()}") # Affiche 2
print(f"Élément défilé : {ma_file.dequeue()}") # Affiche Alice
print(f"Premier élément de la file : {ma_file.front()}") # Affiche Bob
ma_file.dequeue()
print(f"La file est-elle vide ? {ma_file.is_empty()}") # Affiche True

• Utilisation des méthodes listes : append() pour enqueue. Cependant, pop(0) pour dequeue est inefficace car il faut décaler tous les autres éléments de la liste, ce qui prend un temps proportionnel à la taille de la liste ($O(n)$).
• Gestion des erreurs (file vide) : Comme pour les piles, des vérifications sont nécessaires.
• Complexité des opérations :
  • enqueue: $O(1)$ en moyenne.
  • dequeue: $O(n)$ (linéaire) car pop(0) décale tous les éléments.
  • front, is_empty, size: $O(1)$. Pour des applications où les files deviennent grandes, l'implémentation avec collections.deque est préférable en Python, car elle offre des opérations $O(1)$ aux deux extrémités.

Les files d'attente sont essentielles dans de nombreux systèmes :

• Gestion des tâches (Systèmes d'exploitation) : Les processus en attente d'exécution ou les tâches à traiter sont souvent stockés dans des files d'attente.
• Impression : Les documents à imprimer sont placés dans une file d'attente d'impression.
• Simulation d'événements : Pour modéliser des systèmes où des événements se produisent dans un ordre chronologique (par exemple, des clients arrivant à un guichet).
• Parcours de graphes : Notamment le parcours en largeur (BFS).
• Communication inter-processus : Les messages entre différents programmes sont souvent échangés via des files.

Une liste chaînée est un TDA qui représente une séquence d'éléments, où chaque élément (appelé nœud) contient non seulement la donnée mais aussi une référence (un pointeur) vers le nœud suivant dans la séquence.

• Nœud (valeur, suivant) : Chaque nœud est un objet composé de deux parties :
  • La valeur (ou donnée) qu'il stocke.
  • Un pointeur (ou référence) vers le prochain nœud de la liste. Le dernier nœud pointe généralement vers None (ou null).
• Tête de liste : C'est la référence au tout premier nœud de la liste. Si la liste est vide, la tête de liste pointe vers None. La tête de liste est le seul point d'entrée pour accéder à tous les éléments.
• Chaînage des éléments : Les nœuds sont liés entre eux par leurs pointeurs, formant une chaîne.

Il existe plusieurs variantes de listes chaînées :

• Simple (singly linked list) : Chaque nœud pointe uniquement vers le nœud suivant. C'est le type le plus basique.
• Double (doubly linked list) : Chaque nœud contient un pointeur vers le nœud suivant ET un pointeur vers le nœud précédent. Cela permet un parcours dans les deux sens et facilite certaines opérations (comme la suppression).
• Circulaire (circular linked list) : Le dernier nœud de la liste pointe vers le premier nœud, formant une boucle. Cela permet de parcourir la liste indéfiniment.

Les opérations courantes sur les listes chaînées incluent :

• Ajout :
  • Début de liste : Créer un nouveau nœud, le faire pointer vers l'ancienne tête, puis mettre à jour la tête de liste vers le nouveau nœud. $O(1)$.
  • Fin de liste : Parcourir la liste jusqu'au dernier nœud, puis faire pointer ce dernier vers le nouveau nœud. $O(n)$ pour une liste simple.
  • Milieu de liste : Trouver le nœud précédant la position d'insertion, modifier les pointeurs pour insérer le nouveau nœud. $O(n)$ pour trouver la position.
• Suppression :
  • Début de liste : Faire pointer la tête de liste vers le deuxième nœud. $O(1)$.
  • Fin de liste : Parcourir la liste jusqu'à l'avant-dernier nœud, puis faire pointer ce nœud vers None. $O(n)$.
  • Milieu de liste : Trouver le nœud précédant celui à supprimer, puis le faire pointer vers le nœud qui suit celui à supprimer. $O(n)$.
• Recherche d'un élément : Parcourir la liste depuis la tête jusqu'à trouver l'élément ou atteindre la fin. $O(n)$.
• Parcours : Parcourir tous les éléments de la liste un par un, en suivant les pointeurs, depuis la tête jusqu'à ce que le pointeur soit None. $O(n)$.

class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.suivant = None # Pointeur vers le nœud suivant

class ListeChaineeSimple:
    def __init__(self):
        self.tete = None # La tête de liste, initialement vide

    def est_vide(self):
        return self.tete is None

    def ajouter_debut(self, valeur):
        nouveau_noeud = Noeud(valeur)
        nouveau_noeud.suivant = self.tete
        self.tete = nouveau_noeud

    def parcours(self):
        courant = self.tete
        elements = []
        while courant:
            elements.append(courant.valeur)
            courant = courant.suivant
        return elements

# Exemple
ma_liste = ListeChaineeSimple()
ma_liste.ajouter_debut(3)
ma_liste.ajouter_debut(2)
ma_liste.ajouter_debut(1)
print(f"Liste chaînée: {ma_liste.parcours()}") # Affiche [1, 2, 3]

Avantages des listes chaînées :

• Insertion et suppression d'éléments très efficaces si l'on a déjà un pointeur vers le nœud précédent ou le nœud lui-même.
• La taille est flexible et n'a pas besoin d'être prédéfinie.
• Pas de gaspillage de mémoire (sauf pour les pointeurs) car elle alloue de la mémoire au fur et à mesure des besoins.

Inconvénients des listes chaînées :

• Accès séquentiel : L'accès à un élément par son index est lent. Impossible d'accéder directement au 5ème élément sans parcourir les 4 premiers.
• Consommation mémoire plus élevée due aux pointeurs.
• Plus complexe à implémenter et à manipuler que les tableaux.

Un arbre est une structure de données hiérarchique composée de nœuds reliés par des arêtes. Un arbre binaire est un type spécifique d'arbre où chaque nœud a au plus deux enfants (un enfant gauche et un enfant droit).

Voici la terminologie clé :

• Nœud : Élément de base de l'arbre, contenant une valeur et des références vers ses enfants.
• Racine : Le nœud supérieur de l'arbre. C'est le seul nœud qui n'a pas de parent.
• Feuille : Un nœud qui n'a aucun enfant.
• Parent : Un nœud qui a un ou plusieurs enfants.
• Enfant : Un nœud directement connecté en dessous d'un autre nœud (son parent).
• Frère : Des nœuds qui partagent le même parent.
• Sous-arbre : Un nœud et tous ses descendants forment un sous-arbre.
• Profondeur d'un nœud : Le nombre d'arêtes du chemin de la racine à ce nœud. La racine a une profondeur de 0.
• Hauteur d'un arbre : La profondeur maximale de tous les nœuds de l'arbre. C'est la longueur du plus long chemin de la racine à une feuille. Un arbre vide a une hauteur de -1, un arbre avec juste la racine a une hauteur de 0.

Un Arbre Binaire de Recherche (ABR) est un arbre binaire dont les nœuds sont ordonnés selon une propriété spécifique :

• Pour chaque nœud, toutes les valeurs de son sous-arbre gauche sont inférieures à la valeur du nœud.
• Pour chaque nœud, toutes les valeurs de son sous-arbre droit sont supérieures à la valeur du nœud.

Cette propriété permet une recherche efficace :

• Recherche : Pour trouver une valeur, on compare la valeur recherchée avec le nœud courant. Si elle est égale, on a trouvé. Si elle est inférieure, on cherche dans le sous-arbre gauche. Si elle est supérieure, on cherche dans le sous-arbre droit. Cela réduit l'espace de recherche de moitié à chaque étape (comme la dichotomie).
  • Complexité de recherche : $O(h)$ où $h$ est la hauteur de l'arbre. Dans le meilleur des cas (arbre équilibré), $O(\log n)$. Dans le pire des cas (arbre dégénéré, ressemble à une liste chaînée), $O(n)$.
• Insertion : Similaire à la recherche. On trouve la position où la valeur devrait se trouver (en respectant la propriété d'ordonnancement) et on l'insère comme une nouvelle feuille.
• Suppression : Plus complexe, car il faut maintenir la propriété d'ordonnancement. Il existe trois cas : suppression d'une feuille, suppression d'un nœud avec un seul enfant, suppression d'un nœud avec deux enfants.

Le parcours d'un arbre consiste à visiter tous ses nœuds. Il existe différentes stratégies :

• Parcours en profondeur (Depth-First Search - DFS) :
  • Préfixe (préordre) : Visiter le nœud courant, puis parcourir récursivement le sous-arbre gauche, puis le sous-arbre droit. (Racine, Gauche, Droite)
    • Exemple : pour un arbre d'expression, cela donne l'expression polonaise.
  • Infixe (interordre) : Parcourir récursivement le sous-arbre gauche, puis visiter le nœud courant, puis parcourir récursivement le sous-arbre droit. (Gauche, Racine, Droite)
    • Exemple : pour un ABR, cela permet de récupérer les éléments triés par ordre croissant. Très utile pour les ABR.
  • Suffixe (postordre) : Parcourir récursivement le sous-arbre gauche, puis le sous-arbre droit, puis visiter le nœud courant. (Gauche, Droite, Racine)
    • Exemple : pour un arbre d'expression, cela donne l'expression polonaise inversée.
• Parcours en largeur (Breadth-First Search - BFS) : Visiter les nœuds niveau par niveau, de gauche à droite. Utilise généralement une file d'attente.

class NoeudArbre:
    def __init__(self, valeur):
        self.valeur = valeur
        self.gauche = None
        self.droite = None

def parcours_infixe(noeud):
    if noeud:
        parcours_infixe(noeud.gauche)
        print(noeud.valeur, end=" ")
        parcours_infixe(noeud.droite)

# Exemple d'ABR
#        8
#       / \
#      3   10
#     / \   \
#    1   6   14
#       /
#      4
racine = NoeudArbre(8)
racine.gauche = NoeudArbre(3)
racine.droite = NoeudArbre(10)
racine.gauche.gauche = NoeudArbre(1)
racine.gauche.droite = NoeudArbre(6)
racine.gauche.droite.gauche = NoeudArbre(4)
racine.droite.droite = NoeudArbre(14)

print("Parcours infixe (trié):")
parcours_infixe(racine) # Affiche 1 3 4 6 8 10 14

Les arbres binaires et autres types d'arbres sont omniprésents en informatique :

• Indexation de bases de données : Les ABR, et plus spécifiquement les arbres B et B+, sont utilisés pour organiser les données et permettre une recherche rapide.
• Représentation d'expressions arithmétiques : Les arbres d'expression permettent de représenter des formules mathématiques et de les évaluer.
• Algorithmes de tri : Le tri par arbre (Tree Sort) utilise un ABR.
• Compression de données : Les arbres de Huffman sont utilisés pour la compression.
• Systèmes de fichiers : La structure des répertoires et fichiers sur un ordinateur est un arbre.
• Intelligence artificielle : Les arbres de décision sont utilisés pour la classification et la prédiction.

Un graphe est un TDA non linéaire composé d'un ensemble de sommets (ou nœuds) et d'un ensemble d'arêtes (ou arcs) qui relient ces sommets. Les graphes sont des outils puissants pour modéliser des relations entre des entités.

• Sommets (nœuds) : Les entités que le graphe représente. Par exemple, des villes, des personnes, des pages web.
• Arêtes (arcs) : Les liens ou relations entre les sommets. Par exemple, une route entre deux villes, une amitié entre deux personnes, un lien hypertexte.
• Orienté/non orienté :
  • Graphe non orienté : Les arêtes n'ont pas de direction. Si A est relié à B, B est aussi relié à A (ex: amitié). Une arête {A, B} est une paire non ordonnée.
  • Graphe orienté (digraphe) : Les arêtes ont une direction. Si A est relié à B, cela n'implique pas que B est relié à A (ex: routes à sens unique). Une arête (A, B) est une paire ordonnée.
• Pondéré/non pondéré :
  • Graphe non pondéré : Les arêtes n'ont pas de valeur associée.
  • Graphe pondéré : Chaque arête a un poids (ou coût) associé. Par exemple, la distance d'une route, le temps de parcours, le coût d'une connexion. Les poids sont cruciaux pour les algorithmes de plus court chemin.

Comment stocker un graphe en mémoire ? Deux représentations principales :

1. Matrice d'adjacence :

   • C'est une matrice carrée de taille $N \times N$, où $N$ est le nombre de sommets.
   • M[i][j] vaut 1 (ou True) si une arête existe du sommet i au sommet j, et 0 (ou False) sinon.
   • Pour un graphe pondéré, M[i][j] contient le poids de l'arête.
   • Avantages : Vérifier l'existence d'une arête est $O(1)$. Facile à implémenter.
   • Inconvénients : Consomme beaucoup de mémoire ($O(N^2)$) même pour les graphes creux (peu d'arêtes). Parcourir les voisins d'un sommet prend $O(N)$.

2. Liste d'adjacence :

   • C'est un tableau (ou dictionnaire en Python) où chaque entrée i contient une liste des sommets adjacents au sommet i.
   • Pour un graphe pondéré, la liste contient des paires (voisin, poids).
   • Avantages : Consomme moins de mémoire pour les graphes creux ($O(N+E)$ où $E$ est le nombre d'arêtes). Parcourir les voisins d'un sommet est efficace ($O(deg(v))$ où $deg(v)$ est le degré du sommet).
   • Inconvénients : Vérifier l'existence d'une arête peut prendre $O(deg(v))$ dans le pire des cas.

Le parcours permet de visiter systématiquement tous les sommets d'un graphe.

• Parcours en largeur (Breadth-First Search - BFS) :
  • Explore le graphe niveau par niveau. Il visite d'abord tous les voisins d'un sommet, puis tous les voisins de ces voisins, etc.
  • Utilise une file d'attente pour stocker les sommets à visiter.
  • Applications : Trouver le plus court chemin en nombre d'arêtes dans un graphe non pondéré, trouver les composants connexes.
• Parcours en profondeur (Depth-First Search - DFS) :
  • Explore le graphe en allant aussi loin que possible le long de chaque branche avant de revenir en arrière (backtracking).
  • Utilise une pile (implicitement par la récursion ou explicitement).
  • Applications : Détection de cycles, tri topologique, trouver les composants fortement connexes.

Les graphes sont incroyablement polyvalents :

• Réseaux sociaux : Modéliser les amitiés, les connexions. Les algorithmes de graphes peuvent trouver des communautés, des influenceurs.
• GPS (plus court chemin) : Algorithmes comme Dijkstra ou Bellman-Ford trouvent le chemin le plus rapide ou le plus court entre deux points sur une carte (les villes sont des sommets, les routes des arêtes pondérées par la distance/temps).
• Ordonnancement de tâches : Représenter les dépendances entre les tâches d'un projet.
• Réseaux informatiques : Modéliser les routeurs et les connexions.
• Moteurs de recherche : Le PageRank de Google est basé sur une analyse de graphes du web.
• Biologie moléculaire : Représenter les interactions entre protéines ou gènes.
• Logistique : Optimisation des tournées de livraison.