Algorithmes et Structures de Données

Ce document présente les concepts fondamentaux des types abstraits de données (TAD) liés aux listes, piles, files et arbres binaires, ainsi que leurs opérations principales. Il s'adresse aux étudiants en informatique souhaitant maîtriser les bases des structures de données et leur manipulation algorithmique.

Type Abstrait de Données (TAD) Liste Itérative

Le TAD Liste Itérative est défini avec les types Entier, Élément et Place. Il propose plusieurs opérations essentielles :

• Liste_vide : crée une liste vide.
• ième(l, k) : retourne l’élément à la position k dans la liste l.
• longueur(l) : retourne la longueur de la liste l.
• supprimer(l, k) : supprime l’élément à la position k dans la liste l.
• insérer(l, k, e) : insère l’élément e à la position k dans la liste l.
• accès(l, k) : retourne la place (référence) de l’élément à la position k.
• succ(p) : retourne la place suivante après p.
• contenu(p) : retourne l’élément contenu à la place p.

Préconditions :

• ième(l, k) est défini si et seulement si 1 ≤ k ≤ longueur(l).
• supprimer(l, k) est défini si 1 ≤ k ≤ longueur(l).
• insérer(l, k, e) est défini si 1 ≤ k ≤ longueur(l) + 1.

Axiomes importants :

longueur(liste_vide) = 0

longueur(insérer(l, i, e)) = longueur(l) + 1

ième(insérer(l, i, e), i) = e

longueur(supprimer(l, k)) = longueur(l) - 1

Pour i < k : ième(supprimer(l, k), i) = ième(l, i)

Pour i ≥ k : ième(supprimer(l, k), i) = ième(l, i + 1)

Pour i < k : ième(insérer(l, k, e), i) = ième(l, i)

Pour i = k : ième(insérer(l, k, e), i) = e

Pour i > k : ième(insérer(l, k, e), i) = ième(l, i - 1)

Exemple d’utilisation

Soit une liste l = [a, b, c], longueur(l) = 3.

Insérer un élément e à la position 2 :

insérer(l, 2, e) donne la liste [a, e, b, c] avec longueur 4.

Supprimer l’élément à la position 3 :

supprimer([a, e, b, c], 3) donne [a, e, c] avec longueur 3.

Type Abstrait de Données Liste Récursive

Le TAD Liste Récursive utilise les mêmes types Entier, Élément et Place, mais est défini récursivement :

• Liste_vide : liste vide.
• fin(l) : retourne la liste sans son premier élément.
• cons(e, l) : construit une liste en ajoutant l’élément e en tête de la liste l.
• premier(l) : retourne le premier élément de la liste.
• tête(l) : retourne la place du premier élément.
• succ(p) : place suivante.
• contenu(p) : élément à la place p.

Préconditions :

• tête(l), fin(l), premier(l) sont définis si et seulement si l ≠ Liste_vide()

Axiomes :

premier(cons(e, l)) = e

fin(cons(e, l)) = l

longueur(Liste_vide()) = 0

longueur(cons(e, l)) = longueur(l) + 1

Exemple d’utilisation

Soit l = cons(a, cons(b, Liste_vide())) = [a, b]

premier(l) = a

fin(l) = cons(b, Liste_vide()) = [b]

longueur(l) = 2

Type Abstrait de Données Pile

Le TAD Pile est défini avec les types Entier et Élément et propose :

• Pile_vide : crée une pile vide.
• Est_vide(p) : indique si la pile p est vide (booléen).
• empiler(p, e) : empile l’élément e sur la pile p.
• dépiler(p) : dépile la pile p (retire le sommet).
• sommet(p) : retourne l’élément au sommet de la pile p.

Préconditions :

• dépiler(p) et sommet(p) sont définis si Est_vide(p) = faux.

Axiomes :

dépiler(empiler(p, e)) = p

sommet(empiler(p, e)) = e

Est_vide(Pile_vide()) = vrai

Est_vide(empiler(p, e)) = faux

Exemple d’utilisation

Soit p = Pile_vide()

empiler(p, a) donne une pile avec sommet a

sommet(empiler(p, a)) = a

dépiler(empiler(p, a)) = p (pile vide)

Type Abstrait de Données File

Le TAD File est défini avec les types Entier et Élément :

• File_vide : crée une file vide.
• Est_vide(f) : indique si la file f est vide.
• enfiler(f, e) : ajoute l’élément e à la fin de la file f.
• défiler(f) : retire l’élément en tête de la file f.
• sommet(f) : retourne l’élément en tête de la file f.

Préconditions :

• défiler(f) et sommet(f) sont définis si Est_vide(f) = faux.

Axiomes :

défiler(enfiler(f, e)) = f

sommet(enfiler(f, e)) = e

Est_vide(File_vide()) = vrai

Est_vide(enfiler(f, e)) = faux

Exemple d’utilisation

Soit f = File_vide()

enfiler(f, a) donne une file avec a en tête

sommet(enfiler(f, a)) = a

défiler(enfiler(f, a)) = f (file vide)

Type Abstrait de Données Arbre Binaire

Le TAD Arbre Binaire utilise les types Élément et Noeud :

• Arbre_vide : crée un arbre vide.
• Est_vide(a) : indique si l’arbre a est vide.
• <racine, gauche, droit> : construit un arbre binaire à partir d’un nœud racine et de deux sous-arbres gauche et droit.
• racine(a) : retourne le nœud racine de l’arbre a.
• gauche(a) : retourne le sous-arbre gauche.
• droit(a) : retourne le sous-arbre droit.
• contenu(n) : retourne l’élément contenu dans le nœud n.

Exercices proposés

Listes

1. Montrer l’équivalence entre Liste Itérative et Liste Récursive en exprimant :
   • premier, fin, cons en fonction de ième, insérer et supprimer
   • ième, insérer, supprimer, longueur en fonction de premier, fin et cons
2. Écrire des algorithmes récursifs pour les opérations longueur, ième, insérer et supprimer sur Liste Itérative.
3. Implémenter les opérations suivantes pour Liste Itérative en représentation chaînée :
   • concaténation de deux listes l1 et l2 en une nouvelle liste l3 (concat : Liste x Liste → Liste)
   • recherche de la dernière occurrence d’un élément et retour de sa position (0 si absent) (rechercher : Liste x Élément → Entier)
   • inversion d’une liste (inverser : Liste → Liste)
   • tri des éléments selon un champ key de type réel dans Élément
4. Modifier la représentation contiguë de Liste Itérative en utilisant un tableau dynamique et implémenter les opérations.
5. Modifier la représentation chaînée en chaîne double et implémenter les opérations.
6. Modifier la représentation chaînée en chaîne circulaire et implémenter les opérations.

Piles

1. Écrire une procédure Enlever(p : Pile, i : Entier → p : Pile) qui enlève le ième élément d’une pile sans modifier les autres.
2. Écrire un algorithme utilisant une pile pour simuler la saisie d’une ligne de texte avec les caractères spéciaux :
   • # pour effacer le dernier caractère
   • % pour effacer toute la ligne
   • $ pour fin de ligne
   Le texte "Jem# m'euh%Je m'#euh## suit#s trop#mp&#é$" doit être lu comme "Je me suis trompé". Deux procédures sont à écrire : LireLigne(P) et EcrireLigne(P).

Files

1. Fusionner deux files ordonnées d’entiers en une file ordonnée.
2. Écrire un algorithme Evaluer_polynome pour évaluer un polynôme stocké dans une file f (coefficients et exposants), pour une valeur x réelle. Le degré maximal est supposé ≤ 10.

Remarque : Toute manipulation d’une file doit passer par les opérations définies dans le TAD File.

Glossaire des termes clés

• Liste Itérative : structure de données linéaire où les éléments sont accessibles par un indice entier.
• Liste Récursive : structure de données définie récursivement, avec un élément en tête et une sous-liste.
• Pile : structure de données LIFO (Last In First Out) où les éléments sont empilés et dépilés.
• File : structure de données FIFO (First In First Out) où les éléments sont enfilés et défilés.
• Place : référence ou position d’un élément dans une structure.
• Empiler : ajouter un élément au sommet d’une pile.
• Dépiler : retirer l’élément au sommet d’une pile.
• Enfiler : ajouter un élément à la fin d’une file.
• Défiler : retirer l’élément en tête d’une file.
• Arbre Binaire : structure arborescente où chaque nœud a au plus deux sous-arbres (gauche et droit).
• Cons : opération qui construit une liste en ajoutant un élément en tête.

Points clés à retenir

• Les listes peuvent être définies de manière itérative ou récursive, avec des opérations équivalentes.
• Les piles et files sont des structures linéaires avec des règles d’accès différentes (LIFO vs FIFO).
• Les opérations sur ces structures doivent respecter les préconditions pour garantir leur validité.
• Les axiomes définissent le comportement attendu des opérations, assurant la cohérence des structures.
• Les arbres binaires permettent de modéliser des données hiérarchiques avec un accès récursif aux sous-arbres.
• Les exercices proposés permettent de pratiquer la manipulation et l’implémentation de ces structures.