Plan du cours

chap 1: Types de données abstraits élémentaires

(cid:0) Les listes

(cid:0) Les piles

(cid:0) Les files

chap 2: Les arbres

(cid:0) Les arbres binaires

(cid:0) Les arbres bianires de recherche

(cid:0) Les arbres AVL

chap 3: Les Graphes

(cid:0) Les graphes orientés

(cid:0) Les graphes non orientés

chap 4: Complexités des algorithmes et des problèmes

chap 5: L'approche “Diviser pour Régner”

chap 6: Algorithmes de tri interne

chap 7: Algorithmes de tri externe

chap 8: Programmation Dynamique

Algorithmique Avancée

chap1. TYPES DE DONNEES ABSTRAITS ELEMENTAIRES

I. Définitions:

A. LES LISTES

(cid:0) Une liste est une structure particulièrement souple : elle peut grandir ou retrécir à volonté.

Ses éléments, qui sont accessibles à tout moment, peuvent être insérés ou supprimés à tout

moment à n'importe quel endroit.

(cid:0) D'un point de vue mathématique, une liste est une suite, vide ou non, d'éléments d'un type

donné (noté par la suite TypeElement). Il est habituel de représenter une telle suite par: a1,

a2, ...., an où n est un entier positif ou nul et où chaque ai est de type TypeElement.

(cid:0) Une liste peut être concatenée à une autre ou divisée en deux sous-listes.

(cid:0) Le nombre n d'éléments s'appelle la longueur de la liste.

(cid:0) Si n >= 1, on dit que a1 est le premier élément de la liste et an le dernier.

(cid:0) Si n = 0, on parle de liste vide.

(cid:0) On dit que : ai précède ai+1, i = 1, ..., n-1;

ai suit ai-1, i =2, ..., n;

ai se trouve à la position i.

II. Opérations sur les listes :

Notations:

L: liste d'objets de type TypeElément;

x: un objet de type TypeElément;

p: de type entier (désigne la position d'un élément)

1. FIN(L) : cette fonction retourne la position suivant la nième position d'une liste L de n

éléments. Cette position varie suivant que la liste grandit ou rétricit.

L: 1 2 3 n <-------- vide --------->

////////

.........

an ////////

.........

////////

2. INSERER(x, p, L): insérer l'objet x à la position p dans la liste L, avec déplacement de

l'élément précédemment situé en p et de tous les suivants d'une position vers la fin de la

liste.

⤷ FIN(L) (=n+1)

Exemple:

1<= p <= n

avant l'insert°, L: 1 2 3 4 ⤹FIN(L) (=5)

après l'insert° de x à p =3, L: 1 2 3 4 5 ⤹FIN(L) (=6)

a4 /////////////

/////////////

p= Fin(L)

avant l'insert°, L: 1 2 3 4 ⤹FIN(L) (=5)

après l'insert° de x à p =5, L: 1 2 3 4 5 ⤹FIN(L) (=6)

a4 /////////////

x /////////////

/////////////

3. LOCALISER(x, L): cette fonction retourne la position p de x dans L. si x apparaît

plusieurs fois, c'est la position de la 1ère occurrence qui est retournée. Si x n'est pas dans la

liste, c'est la position FIN(L) qui est renvoyée.

Exemple : L: 1 2 3 4

a2 /////////////

/////////////

LOCALISER(a2, L) ==>

LOCALISER(a6, L) ==>

4. ACCEDER(p, L): cette fonction retourne l'élément se trouvant à la position p de la liste

L. L'opération est impossible si p >= FIN(L) ou si L est vide. Les éléments à extraire doivent

avoir le même type que celui des objets retournés par la fonction ACCEDER.

Exemple:

ACCEDER(3, L) ==>

ACCEDER(5, L) ==>

5. SUPPRIMER(p, L): elle permet de supprimer l'élément se trouvant à la position p de la

liste L. L'opération est impossible si L est vide ou si p >= FIN(L).

Exemple: L : 1 2 3 4

a4 /////////////

/////////////

Suppression de l'élément se trouvant à p =3 (SUPPRIME(3,L))

L: 1 2 3

a4 /////////////

/////////////

6. SUIVANT(p, L) et PRECEDENT(p,L) : ces deux fonctions retournent respecivement la

position suivante et précédente à la position p dans la liste L.

Si p est la dernière position de cette liste, SUIVANT(p, L)=FIN(L);

Si p = FIN(L), SUIVANT() n'est pas définie;

Si p=1, PRECEDENT() n'est pas définie;

Si L est vide, ces deux opérations n'ont pas de sens.

Exemple : L : 1 2 3 4

a4 /////////////

/////////////

SUIVANT(4, L) ==>

SUIVANT(5, L) ==>

PRECEDENT(1, L) ==>

PRECEDENT(3, L) ==>

Exercice 1: écrire une procédure permettant de prendre une liste L en argument et en élimine

toutes les répétitions. Les éléments de la liste sont de type TypeElément et une liste de tels

objets est du type LISTE. On suppose aussi l'existence d'une fonction Identique(x, y) où x et y

sont de type TypeElément, qui retourne la valeur vrai si x et y sont identiques et faux sinon.

III. Mise en oeuvre des listes :

Dans la mise en oeuvre par tableau, le type LISTE consiste en un enregistrement à 2 champs.

Le 1er est un tableau dont la taille est suffisante pour contenir la liste. Le second champ est un

entier “dernier” indiquant la position du dernier élément du tableau.

<---- vide ---->

/////////////

^ ^ ..... ^

1er elet 2nd elet dernier elet

La foncition FIN(L) ne fait que renvoyer la valeur dernier+1

Les déclarations suivantes sont nécessaires:

const LongMax = 100

Type LISTE = enregistrement

Eléments :Tableau [1 .. LongMax] de TypeElement

Dernier :entier

finenregistrement

fonction FIN (L :LISTE) : entier

début

FIN← L.Dernier +1

fin

Exercice 2: Ecrire les sous-programmes suivants : SUIVANT, PRECEDENT, INSERER,

SUPPRIMER et LOCALISER.

I. Définitions

B. LES PILES

(cid:0) Une pile est un type de liste particulier dans lequel toute suppression d'éléments se fait à une

extrimité appelée le dessus ou le sommet de la pile.

(cid:0) Dans une pile, l'élément supprimé est celui de le plus récemment inséré : la pile met en

oeuvre le principe dernier entré, premier sortant, ou LIFO (Last in, first out).

(cid:0) L'opération INSERER dans une pile est souvent appelée EMPILER et l'opération

SUPPRIMER qui ne prend pas d'argument est souvent appelée DEPILER.

(cid:0) Les opérations possibles sur les piles sont souvent les suivants:

RAZ(P): vider le contenu de la pile P;
VIDE(P): cette fonction retourne vrai si P est vide et faux sinon;
SOMMET(P): retourne (sans le dépiler) l'élément au sommet de la pile P;
DEPILER(P): supprime physiquement l'élément au sommet de P;

(cid:0) EMPILER(x, P): insère l'élément x au sommet de P. L'ancien élément le plus haut

devient le 2ème et ainsi de suite...

II. Mise en oeuvre des piles par les tableaux

D'une façon générale, une pile peut être mise en oeuvre par un tableau de taille LongMax,

comme suit:

EMPILER ↴

LongMax ⇨

///////////////////////////

↱

DEPILER

///////////////////////////

Sommet ⇨

⇦ Dernier élément

⇦ 1er 2lément

Exp

//////////

/////////////

⇦ Sommet

////////////

3 ⇦ Sommet

////////////

///////////// ⇦ Sommet

aprés : EMPILER(17, P)

après : DEPILER (P)

SOMMET(P) ==> ?

VIDE(P) ==> ?

EMPILER(3, P)

pour cette mise en oeuvre des piles à partir d'un tableau, il faut définir le type de données

abstrait PILE par:

const LongMax = ....

type PILE = enregistrement

Eléments : tableau[1 .. LongMax] de TypeElément

Sommet : entier

finenreg

Remarque: si le sommet = 0, alors la pile est vide.

Exercice 3: Ecrire les sous-programmes RAZ(P), VIDE(P), SOMMET(P), DEPILER(P) et

EMPILER(x, P).

C. LES FILES

I. Définitions

(cid:0) Une file est un autre type particulier de liste, où les éléments sont insérés en queue et

supprimés de la tête.

(cid:0) Une file met en oeuvre le principe premier entré, premier sorti ou FIFIO (First In, First

Out)

(cid:0) Les opérations sur les files sont analogues à celles définies sur les piles. La principale

différence provenant du fait que les insertions se font en fin de la liste (queue) plutôt qu'en

tête.

RAZ(F): transforme la file en une file vide;

(cid:0) TETE(F): cette fonction retourne l'élément en tête de la file F;

(cid:0) ENFILER(x, F): Insère l'élément x à la fin de la file F;

(cid:0) DEFILER(F): Supprime le 1er élément de a file F;

(cid:0) VIDE(F): cette fonction retourne vrai si la file F est vide et faux sinon.

II. Mise en oeuvre des files par des pointeurs:

Comme pour les piles, toute mise en oeuvre de liste est valable sur les files.

On définit les noeuds de nos files par la déclaration suivante:

type noeud = enregistrement

val : TypeElement

suiv : ^noeud

finenreg

On peut ensuite définir une file comme la donnée de 2 pointeurs : un 1er sur la tête de la file et

un second sur la queue.

On définit alors le type FILE par :

type FILE = enregistrement

tête, queue : ^noeud

finenreg.

Exemple : soit la file F suivante:

Y nil

↑ F.tête ↑ F.queue

F.tête↑val = X

F.queue↑val = Y

F.queue↑suiv = nil

ENFILER(z, F):

Z nil

F.queue↑val = Z

↑ F.tête

↑ F.queue

DEFILER(F):

Z nil

↑ F.tête ↑ F.queue

TETE(F) ==> ?

VIDE (F) ==> ?

RAZ(F) ==> ?

nil

↑ ↑

F.tête F.queue

F.tete = nil

F.queue= nil

VIDE(F) ?

Exercice 4: Ecrire les sous-programmes : RAZ(F), VIDE(F), TETE(F) ENFILER(x, F) et

DEFILER(F)

III. Mise en oeuvre des files par tableaux:

/////// ////////

^F.tête ^F.queue

Suppression ←

... ← Insertion

Il faut noter que la procédure DEFILER, dont l'action est de supprimer le 1er élément,

provoque le déplacement d'une position vers la tête de tous les éléments suivants de la file.

Pour éviter ces décalages successifs, on peut penser à une représentation de la file par un

tableau circulaire où la dernière position est directement suivie par la première.

Sens de déplacement

1er élément : F.tête

Suppression

LongMax

Dernier élément :

F.queue

insertion

Ici la position F.tête du 1er élément est variable das le temps

Quand une insertion insertion est effectuée, la position F.queue est déplacée d’une position

vers l’avant et l’élément est inséré à cette position.

(cid:0) une suppression provoque simplement le déplacement de F.tête d’une position vers l’avant.

Formellement, une fil est définie par:

const LongMax = ....

type FILE = enregistrement

Elément : tableau[1 .. LongMax] de TypeElément

tête, queue : entier

Finenregistrement

Exemple :

tête

VIDE(F) tête

queue

File pleine :

tête =1

queue = 7

File vide :

tête =1

queue = 7

==> Il n'est pas possible de distiguer une file vide de la même file pleine.

Une manière de surmonter ce phénomène est de ne pas permettre le remplissemnet entier de la

file. Autrement dit, la file ne peut pas contenir plus que (LongMax -1) éléments.

Dans ce cas la file est vide si les deux positions F.tête et F.queue sont adjacents.

Exemple.

File pleine :

tête =1

queue = 6

File vide :

tête = 7

queue = 6

Exercice : écrire une fonction AVANCER permettant d'incrémenter une position p dans un

tableau ciculaire de taille LongMax.

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

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