Algorithmique Avancée

Ce laboratoire porte sur les types de données abstraits élémentaires en algorithmique avancée, notamment les listes, piles et files. Il permet de comprendre leurs définitions, opérations fondamentales, et différentes mises en œuvre, tant par tableaux que par pointeurs. Pour réaliser ce TP, il est nécessaire de maîtriser les concepts de base des structures de données et de savoir programmer des sous-programmes simples.

Objectifs

• Comprendre la définition et les propriétés des listes, piles et files.
• Apprendre à manipuler les opérations fondamentales sur ces structures (insertion, suppression, localisation, accès).
• Mettre en œuvre ces structures par tableaux ou pointeurs.
• Écrire des sous-programmes pour gérer ces structures (ex. INSERER, SUPPRIMER, EMPILER, DEPILER, ENFILER, DEFILER).
• Appliquer les notions de liste circulaire pour la gestion efficace des files.

Prérequis et installation

• Connaissances de base en algorithmique et programmation (types, tableaux, pointeurs).
• Environnement de programmation permettant la définition de types et l’écriture de sous-programmes (ex. Pascal, C, ou pseudocode).
• Compréhension des notions mathématiques simples (indices, positions, suites).

Types de données abstraits élémentaires : Les listes

Une liste est une structure dynamique pouvant grandir ou rétrécir. Ses éléments sont accessibles à tout moment et peuvent être insérés ou supprimés en n'importe quelle position.

Mathématiquement, une liste est une suite d'éléments a1, a2, ..., an où n est la longueur de la liste (n ≥ 0). Si n = 0, la liste est vide. Le premier élément est a1, le dernier est an.

Les opérations principales sont :

• FIN(L) : retourne la position suivant la dernière position de la liste L (c'est-à-dire n+1 si la liste a n éléments).
• INSERER(x, p, L) : insère l'élément x à la position p dans L, décalant les éléments à partir de p vers la fin.
• LOCALISER(x, L) : retourne la position de la première occurrence de x dans L, ou FIN(L) si x n'est pas présent.
• ACCEDER(p, L) : retourne l'élément en position p de L (impossible si p ≥ FIN(L) ou si L est vide).
• SUPPRIMER(p, L) : supprime l'élément en position p de L (impossible si L est vide ou p ≥ FIN(L)).
• SUIVANT(p, L) et PRECEDENT(p, L) : retournent respectivement la position suivante et précédente à p dans L, avec des cas particuliers si p est en bordure.

Exemple d'insertion :

Avant insertion à p=3 : L = a1, a2, a3, a4, FIN(L)=5
Après insertion de x à p=3 : L = a1, a2, x, a3, a4, FIN(L)=6

Dans la mise en œuvre par tableau, une liste est un enregistrement avec :

• Un tableau d'éléments de taille maximale LongMax.
• Un entier "dernier" indiquant la position du dernier élément.

La fonction FIN(L) se définit alors par :

fonction FIN(L : LISTE) : entier
début
  FIN ← L.Dernier + 1
fin

Exercices proposés :

• Écrire une procédure pour éliminer toutes les répétitions dans une liste L.
• Écrire les sous-programmes SUIVANT, PRECEDENT, INSERER, SUPPRIMER et LOCALISER.

Les piles

Une pile est une liste particulière où les suppressions se font uniquement au sommet (dernier élément inséré). Elle suit le principe LIFO (Last In, First Out).

Les opérations principales sont :

• RAZ(P) : vider la pile P.
• VIDE(P) : retourne vrai si la pile est vide, sinon faux.
• SOMMET(P) : retourne l'élément au sommet sans le dépiler.
• DEPILER(P) : supprime l'élément au sommet.
• EMPILER(x, P) : insère l'élément x au sommet.

La mise en œuvre par tableau utilise un tableau de taille LongMax et un entier Sommet indiquant la position du sommet. Si Sommet = 0, la pile est vide.

Déclaration type :

const LongMax = ...
type PILE = enregistrement
  Eléments : tableau[1 .. LongMax] de TypeElément
  Sommet : entier
finenreg

Exercice : écrire les sous-programmes RAZ, VIDE, SOMMET, DEPILER et EMPILER.

Les files

Une file est une liste particulière où les éléments sont insérés en queue et supprimés en tête, suivant le principe FIFO (First In, First Out).

Les opérations principales sont :

• RAZ(F) : vide la file.
• TETE(F) : retourne l'élément en tête.
• ENFILER(x, F) : insère l'élément x en queue.
• DEFILER(F) : supprime l'élément en tête.
• VIDE(F) : retourne vrai si la file est vide, sinon faux.

Mise en œuvre par pointeurs

Les noeuds sont définis par :

type noeud = enregistrement
  val : TypeElement
  suiv : ^noeud
finenreg

La file est définie par deux pointeurs :

type FILE = enregistrement
  tête, queue : ^noeud
finenreg

Exemple d'état d'une file :

F.tête↑val = X
F.queue↑val = Y
F.queue↑suiv = nil

Exercice : écrire les sous-programmes RAZ, VIDE, TETE, ENFILER et DEFILER.

Mise en œuvre par tableaux circulaires

Pour éviter le déplacement coûteux des éléments lors de DEFILER, on utilise un tableau circulaire où la dernière position est suivie de la première.

La file est définie par :

const LongMax = ...
type FILE = enregistrement
  Elément : tableau[1 .. LongMax] de TypeElément
  tête, queue : entier
finenreg

Insertion (ENFILER) déplace la position queue d’une unité vers l’avant et insère l’élément à cette position.

Suppression (DEFILER) déplace la position tête d’une unité vers l’avant.

Problème : il est impossible de distinguer une file vide d’une file pleine si tête = queue.

Solution : ne jamais remplir complètement la file, la capacité maximale est LongMax - 1 éléments. La file est vide si tête et queue sont adjacents.

Exercice : écrire une fonction AVANCER permettant d'incrémenter une position p dans un tableau circulaire de taille LongMax.

Résultats attendus

• Compréhension claire des opérations sur listes, piles et files.
• Fonctions et procédures correctement écrites pour manipuler ces structures.
• Gestion efficace des files circulaires sans décalage excessif.
• Capacité à éliminer les répétitions dans une liste.
• Reconnaissance correcte des états vides et pleins des piles et files.

Pièges courants

• Ne pas vérifier les conditions limites (ex. p ≥ FIN(L), pile ou file vide) avant d’accéder ou supprimer un élément.
• Confondre les opérations sur piles (LIFO) et files (FIFO).
• Oublier que dans une file circulaire, la file pleine et la file vide peuvent avoir tête = queue, nécessitant une gestion spécifique.
• Lors de l’insertion dans une liste, ne pas décaler correctement les éléments suivants.
• Dans les piles, ne pas mettre à jour correctement l’indice Sommet.
• Dans la suppression d’éléments, ne pas gérer le cas où la liste ou la pile est vide.