Algorithmique Avancée - Types de Données et Algorithmique

Ce document présente un examen d'algorithmique avancée portant sur les types de données abstraits élémentaires, notamment les listes, piles et files. Il teste la compréhension des définitions, opérations, mises en œuvre et la capacité à écrire des sous-programmes manipulant ces structures.

Exercice 1 : Élimination des répétitions dans une liste

La procédure suivante parcourt la liste et élimine les doublons successifs à l'aide de la fonction de comparaison fournie.

Analyse : On travaille sur une liste L d'éléments de type TypeElément. On dispose d'une fonction Identique(x, y) qui retourne vrai si x et y sont identiques.

Solution pas à pas :

1. Parcourir la liste L de la première à la dernière position.
2. Pour chaque élément à la position i, parcourir la liste à partir de la position suivante (i+1) jusqu'à la fin.
3. Comparer chaque élément suivant avec l'élément à la position i en utilisant Identique.
4. Si une égalité est trouvée, supprimer l'élément en position j (avec SUPPRIMER(j, L)) et ne pas avancer j car la liste a été raccourcie.
5. Sinon, avancer j.
6. Continuer jusqu'à la fin de la liste.

Procédure en pseudo-code :

procédure EliminerRepetitions(var L : LISTE)
  pour i de 1 à FIN(L) - 1 faire
    j ← i + 1
    tant que j < FIN(L) faire
      si Identique(ACCEDER(i, L), ACCEDER(j, L)) alors
        SUPPRIMER(j, L)
      sinon
        j ← j + 1
      fin si
    fin tant que
  fin pour
fin procédure

Réponse finale : La procédure ci-dessus élimine toutes les répétitions dans la liste L.

Exercice 2 : Sous-programmes pour listes représentées par tableau

Voici les implémentations des opérations de base sur une liste stockée dans un tableau fixe.

SUIVANT(p, L)

Cette fonction retourne la position suivant p dans la liste L.

Si p est la dernière position (p = L.Dernier), alors SUIVANT(p, L) = FIN(L) = L.Dernier + 1.

fonction SUIVANT(p : entier; L : LISTE) : entier
  si p <= L.Dernier alors
    retourner p + 1
  sinon
    // SUIVANT non défini si p > L.Dernier
    erreur
  fin si
fin fonction

PRECEDENT(p, L)

Cette fonction retourne la position précédente à p dans la liste L.

Si p = 1, PRECEDENT n'est pas défini.

fonction PRECEDENT(p : entier; L : LISTE) : entier
  si p > 1 et p <= FIN(L) alors
    retourner p - 1
  sinon
    // PRECEDENT non défini si p = 1 ou p > FIN(L)
    erreur
  fin si
fin fonction

INSERER(x, p, L)

Cette procédure insère l'objet x à la position p dans la liste L, en décalant les éléments à partir de p vers la fin.

Étapes :

• Vérifier que p est entre 1 et FIN(L) (soit n+1).
• Décaler tous les éléments de la position L.Dernier jusqu'à p vers la droite (position +1).
• Placer x en position p.
• Incrémenter L.Dernier de 1.

procédure INSERER(x : TypeElément; p : entier; var L : LISTE)
  si p <= FIN(L) alors
    pour i de L.Dernier à p faire
      L.Eléments[i + 1] ← L.Eléments[i]
    fin pour
    L.Eléments[p] ← x
    L.Dernier ← L.Dernier + 1
  sinon
    erreur
  fin si
fin procédure

SUPPRIMER(p, L)

Cette procédure supprime l'élément en position p dans la liste L, en décalant les éléments suivants vers la gauche.

Étapes :

• Vérifier que p < FIN(L) et que L n'est pas vide.
• Décaler tous les éléments de p+1 jusqu'à L.Dernier vers la gauche (position -1).
• Décrémenter L.Dernier de 1.

procédure SUPPRIMER(p : entier; var L : LISTE)
  si (L.Dernier >= 1) et (p < FIN(L)) alors
    pour i de p à L.Dernier - 1 faire
      L.Eléments[i] ← L.Eléments[i + 1]
    fin pour
    L.Dernier ← L.Dernier - 1
  sinon
    erreur
  fin si
fin procédure

LOCALISER(x, L)

Cette fonction retourne la position de la première occurrence de x dans L, ou FIN(L) si x n'est pas trouvé.

Étapes :

• Parcourir les positions de 1 à L.Dernier.
• Comparer chaque élément avec x (en utilisant Identique si nécessaire).
• Retourner la position dès la première égalité.
• Si aucune égalité, retourner FIN(L).

fonction LOCALISER(x : TypeElément; L : LISTE) : entier
  pour p de 1 à L.Dernier faire
    si Identique(L.Eléments[p], x) alors
      retourner p
    fin si
  fin pour
  retourner FIN(L)
fin fonction

Exercice 3 : Mises en œuvre des piles par tableau

Une pile P est un enregistrement avec un tableau Eléments[1..LongMax] et un entier Sommet indiquant la position du sommet. Si Sommet = 0, la pile est vide.

RAZ(P)

Cette procédure permet de vider la pile P.

procédure RAZ(var P : PILE)
  P.Sommet ← 0
fin procédure

VIDE(P)

Cette fonction retourne vrai si la pile est vide, faux sinon.

fonction VIDE(P : PILE) : booléen
  retourner (P.Sommet = 0)
fin fonction

SOMMET(P)

Cette fonction retourne l'élément au sommet de la pile sans le dépiler. L'opération est impossible si la pile est vide.

fonction SOMMET(P : PILE) : TypeElément
  si VIDE(P) alors
    erreur
  sinon
    retourner P.Eléments[P.Sommet]
  fin si
fin fonction

DEPILER(P)

Cette procédure supprime l'élément au sommet de la pile. L'opération est impossible si la pile est vide.

procédure DEPILER(var P : PILE)
  si VIDE(P) alors
    erreur
  sinon
    P.Sommet ← P.Sommet - 1
  fin si
fin procédure

EMPILER(x, P)

Cette procédure insère l'élément x au sommet de la pile.

procédure EMPILER(x : TypeElément; var P : PILE)
  si P.Sommet < LongMax alors
    P.Sommet ← P.Sommet + 1
    P.Eléments[P.Sommet] ← x
  sinon
    erreur // pile pleine
  fin si
fin procédure

Exercice 4 : Mises en œuvre des files par pointeurs

Une file F est un enregistrement avec deux pointeurs tête et queue vers des nœuds. Chaque nœud contient val (TypeElément) et suiv (pointeur vers nœud).

RAZ(F)

Cette procédure transforme la file en une file vide.

procédure RAZ(var F : FILE)
  F.tête ← nil
  F.queue ← nil
fin procédure

VIDE(F)

Cette fonction retourne vrai si la file est vide, faux sinon.

fonction VIDE(F : FILE) : booléen
  retourner (F.tête = nil)
fin fonction

TETE(F)

Cette fonction retourne l'élément en tête de la file. L'opération est impossible si la file est vide.

fonction TETE(F : FILE) : TypeElément
  si VIDE(F) alors
    erreur
  sinon
    retourner F.tête↑val
  fin si
fin fonction

ENFILER(x, F)

Cette procédure insère l'élément x à la fin de la file.

procédure ENFILER(x : TypeElément; var F : FILE)
  nouveauNoeud ← allouer noeud
  nouveauNoeud↑val ← x
  nouveauNoeud↑suiv ← nil
  si VIDE(F) alors
    F.tête ← nouveauNoeud
    F.queue ← nouveauNoeud
  sinon
    F.queue↑suiv ← nouveauNoeud
    F.queue ← nouveauNoeud
  fin si
fin procédure

DEFILER(F)

Cette procédure supprime le premier élément de la file. L'opération est impossible si la file est vide.

procédure DEFILER(var F : FILE)
  si VIDE(F) alors
    erreur
  sinon
    temp ← F.tête
    F.tête ← F.tête↑suiv
    libérer temp
    si F.tête = nil alors
      F.queue ← nil
    fin si
  fin si
fin procédure

Exercice supplémentaire : Gestion du tableau circulaire

La fonction AVANCER permet d'incrémenter une position p dans un tableau circulaire de taille LongMax.

Analyse : Dans un tableau circulaire, la position suivante de p est p+1 sauf si p = LongMax, auquel cas la position suivante est 1.

fonction AVANCER(p : entier) : entier
  si p < LongMax alors
    retourner p + 1
  sinon
    retourner 1
  fin si
fin fonction

Méthode générale

Ce devoir récompense la maîtrise des définitions précises des types abstraits de données (listes, piles, files) et de leurs opérations fondamentales. Il est essentiel de :

• Respecter les conventions données, notamment les définitions des fonctions FIN, Identique, et les comportements aux limites (liste vide, pile vide, file vide).
• Montrer clairement les étapes de raisonnement, notamment lors des manipulations d'indices et des décalages dans les tableaux.
• Écrire des algorithmes rigoureux, avec gestion des cas d'erreur (positions invalides, structures vides ou pleines).
• Ne pas inventer de données ou hypothèses non présentes dans l'énoncé.
• Utiliser les notations et noms exacts fournis (INSERER, SUPPRIMER, EMPILER, DEPILER, ENFILER, DEFILER, etc.).

Les erreurs fréquentes à éviter sont :

• Confondre les opérations sur listes, piles et files.
• Oublier de gérer les cas où la structure est vide ou pleine.
• Ne pas respecter la définition de FIN(L) comme L.Dernier + 1.
• Ne pas décaler correctement les éléments lors des insertions ou suppressions dans les tableaux.

Une bonne compréhension des structures abstraites et de leur mise en œuvre est la clé pour réussir ce type d'exercices.