COURS D’ALGORITHMIQUE ET METHODES DE

PROGRAMMATION II

Promotion : G2 Informatique

Dispensé par : Ass. ALI KOJ

 Cours d’Algorithmique II
G2 Informatique de Gestion 1

TABLE DES MATIERES

TABLE DES MATIERES ................................................................................................................. 1
PLAN DU COURS ......................................................................................................................... 3
BIBLIOGRAPHIE .......................................................................................................................... 3
BUT ET OBJECTIF DU COURS ...................................................................................................... 4
CHAPITRE Ier : DEFINITIONS ....................................................................................................... 5
CHAPITRE II : COMPLEXITE DES ALGORITHMES ......................................................................... 6
II. 1. Définition de la complexité ........................................................................................... 6
II. 2. Taux de croissance......................................................................................................... 6
II. 3. Expression des Algorithmes ........................................................................................... 9
CHAPITRE III. ITERATION RECURSIVITE ET RECURRENCE ......................................................... 11
III.1 Définition des concepts ........................................................................................... 11
III.2 Récursivité et algorithmes récursifs........................................................................ 12
CHAPITRE IV. STRUCTURES PRINCIPALES DES DONNEES ......................................................... 15
A. TABLEAU.......................................................................................................................... 15
A1. Représentation en mémoire ..................................................................................... 15
A 2. Opérations ............................................................................................................... 16
A.3 Tableau multidimensionnel ...................................................................................... 22
A.4 Traits principaux des tableaux et conclusion ........................................................... 25
B. ENREGISTREMENT ........................................................................................................... 29
B.1 Représentation en mémoire ..................................................................................... 30
B.2 Opérations ................................................................................................................ 31
B.3 Enregistrements de longueur variable ..................................................................... 32
C. LISTE ................................................................................................................................ 37
C.1 Représentation en mémoire ..................................................................................... 37
C.2 Opérations ................................................................................................................ 39
C.3 Liste chaînée circulaire à en tête .............................................................................. 42
C.4 Liste bidirectionnelle ................................................................................................. 43
C.5 Liste inversée ............................................................................................................ 44
D. PILE .................................................................................................................................. 48
D.1 Représentation en mémoire ..................................................................................... 48
D.2 Opérations ................................................................................................................ 49
D.3 Exemples .................................................................................................................. 50
E. FILE D’ATTENTE ............................................................................................................... 56
E.1 Représentation en mémoire ..................................................................................... 56
E.2 Opérations ................................................................................................................ 57
E.3 File d’attente à niveau de priorité ............................................................................ 57

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 2

E.4 Deque ........................................................................................................................ 58

F. ARBRE .............................................................................................................................. 59
F.1 Arbre binaire ............................................................................................................. 59
F.2 Arbre binaire complet ............................................................................................... 60
F.3 Arbre binaire étendu (arbre pair) ............................................................................. 61
F.4 Arbre binaire de recherche ....................................................................................... 63
F.5 Représentation en mémoire ..................................................................................... 63
F.6 Opération .................................................................................................................. 64
F.7 Arbre binaire ordonné............................................................................................... 71
F.8 Arbre généralisé ........................................................................................................ 74

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 3

PLAN DU COURS

BUT ET OBJECTIF DU COURS

CHAP Ier : DEFINITIONS

CHAP II : COMPLEXITE DES ALGORITHMES

CHAP III : ITERATION RECURSIVITE ET RECURRENCE
CHAP VI : STRUCTURES PRINCIPALES DES DONNEES EN MEMOIRE
PRIMAIRE

BIBLIOGRAPHIE
1. B. MUYER, Méthodes de programmation, Ed. Eyrolles, Paris, 1978.

2. Chantal RICHARD, Patrice RICHARD, Initiation à l’algorithmique 85 exercices

corrigés, Ed. Belin, Paris, Juin 1981.

3. Charles CORGE, Eléments d’informatique Informatique et démarche de l’esprit,,

Larousse, Paris, 1975.

4. Jean Pierre LAURENT, Jacqueline AYEL, Exercices commentés d’analyse et de

programmation, Ed. Dunod, Paris, 1985.

5. L. ALBERT, P. GASTIN, B. PETAZZONI, A. PETIT, N. PUECH, P. WEIL, Cours et

exercices d’informatique, Ed. Vuibert, Paris, 1998.

6. SEYMOUR LIPSCHUTZ, Les structures de données cours et problèmes, Série

Schaum, Hill inc, Paris, 1987.

7. Yves GRANJON, Informatique Algorithmiques en Pascal et en langage C, Ed.

Dunod, Paris, 1999.

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 4

BUT ET OBJECTIF DU COURS

L’efficacité et la stabilité d’un programme sont principalement

soutenues par :
L’organisation de sa partie active (qu’on appelle généralement
l’ALGORITHMIQUE),
L’organisation de sa partie passive (qu’on appelle généralement
les DONNEES).

Il faudrait que les deux parties soient mutuellement organisées.

L’Algorithme vient de AL KWARIZMI est un ensemble des tâches à
accomplir.
Lorsque la relation qui est entre la nature d’une donnée et sa
structure est la lâche, cela a un impact négatif sur :

 La structure du programme qu’il utilise ;

 La consommation en temps et en espace dans l’exécution de
ce programme.

L’organisation des données et l’étude des Structures de données

sont donc des éléments essentiels en programmation.

Le but de ce cours est de pouvoir examiner quelques structures

de base et les différentes opérations courantes que ces structures admettent
afin d’amener les étudiants futurs analystes programmeurs, à faire un choix
raisonné et adéquat des structures face à un ensemble déterminé des
données.

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 5

CHAPITRE Ier : DEFINITIONS

Les données peuvent être organisées de diverses manières. Le

modèle logique ou mathématique d’une organisation particulière des
données constitue ce que l’on appelle structure de données.

Le choix d’un modèle des données dépend de deux types de

considérations :
 La richesse STRUCTURELLE de ce modèle doit être suffisamment
grande pour refléter les relations effectives qui lient les données
dans le monde réel ;

 La simplicité de ce modèle doit être suffisamment grande pour

permettre une manipulation aisée et rapide des données qu’il
contient.

Une structure de données est donc une représentation

mathématique des données qui :

 Copie plus ou moins fidèlement les relations qui existent entre les
données dans le monde réel ;

 Permet un accès rapide à ces données.

Une structure de données est un paramètre déterminant de la

complexité en temps et en espace des Algorithmes.
D’une manière générale, en informatique nous aurons à faire à :
 Des Structures de données linéaires ;
 Des Structures de données non linéaires.

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 6

CHAPITRE II : COMPLEXITE DES ALGORITHMES

II. 1. Définition de la complexité

L’analyse des Algorithmes constitue un domaine fondamental

dans le cours de structures de données.
Un algorithme est une liste parfaitement définie des étapes
nécessaires à la résolution d’un problème donné.
La taille des données à traiter est le critère le plus important pour
pouvoir mesurer l’efficacité d’un Algorithme.
Le temps et l’espace nécessaire à un Algorithme constituent les
deux objets principaux de la mesure de son efficacité.
La complexité d’un Algorithme M est la fonction f(n) qui donne le
temps d’exécution et/ou l’espace mémoire qui lui est nécessaire étant
donnée la taille n des données à traiter et la nature de ces données.
L’espace mémoire nécessaire est simplement un multiple de la
taille n des données
Un Algorithme qui recherche dans un dictionnaire des mots qui
ont une forte chance d’apparaître en début de ce dictionnaire n’aura pas la
même complexité en temps qu’un deuxième Algorithme qui recherche dans
ce même dictionnaire des mots qui ont une forte chance d’apparaître en fin
de ce dictionnaire.
L’évaluation de la complexité d’un Algorithme se fera
généralement en précisant le cas :
Favorable ;
Courant ;
Défavorable.

II. 2. Taux de croissance

Soit M un algorithme, et soit n la taille des données à traiter, il est

évident que la complexité f(n) doit augmenter avec l’accroissement de n.
ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 7

En général ce sera le taux de croissance f(n) que l’on devra

considérer pour mieux cerner la complexité.
Cela se fait en comparant f(n) (le taux de croissance) à une
fonction de référence. Les fonctions de références les plus utilisées sont les
suivantes :
log2 n, n, n log2 n, n², n3, 2n

En considérant, les fonctions suivantes comme étant des

fonctions de références, nous pouvons donner les taux de croissance avec
des valeurs approximatives dans le tableau ci-après :
g(n) log2 n n n log2 n n² n3 2n
n
2 1 2 2 4 8 4
4 2 4 8 16 64 16
6 2,584962501 6 15,50978 36 216 64
8 3 8 24 64 512 256
9 3,169925001 9 28,52933 81 729 512
10 3,321928095 10 33,21928 100 1000 1024
11 3,459431619 11 38,05375 121 1331 2048
12 3,584962501 12 43,01955 144 1728 4096

On peut remarquer que pour une valeur donnée de n, log2 n

croît beaucoup plus lentement que 2n.
Une manière de comparer f(n) à ces fonctions de référence est
d’utiliser la fonction θ.

Supposons que f(n) et g(n) sont des fonctions définies sur

l’ensemble des entiers positifs avec la propriété que f(n) est bornée par un
multiple quelconque de g(n) pour presque toutes les valeurs de n, c’est-à-
dire qu’il existe un entier positif n0 et un nombre positif m tels que pour tout n >
n0 on a :

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 8

|f(n) | ≤ m.|g(n) |,
Dans ce cas, on peut alors écrire que :
f(n) = θ (g(n))
Ce qui se lit ‘‘ f(n) est de l’ordre de g(n) ’’.

Exemple 1 : Soit un Algorithme qui calcule le polynôme

p(n)= a0 + a1n + a2n2 +a3n3+………+ aknk avec les ai  R
On demande de calculer la complexité de cet Algorithme

Solution : considérons ce qui suit :

Posons b0= a0, b 1 = a1, b2 = a2,..., bk = ak
Alors p(n) ≤ b0 + b1n + b2 n2 +…+ bk nk
P(n) ≤ nk( b0/nk+ b1n/nk + b2 n2/nk +…+ bk nk/nk)
P(n) ≤ nk( b0/nk+ b1/nk-1 + b2 /nk-2 +…+ bk)
Lorsque la valeur de n tend vers l’infini positif, b0/nk+ b1/nk-1 + b2
/nk-2 +…+ bk tend vers une constante

Lim ( b0/nk+ b1/nk-1 + b2 /nk-2 +…+ bk) = m

Si nk se nomme g(n), nous pouvons dire que : p(n) ≤ m. g(n)

Donc, la complexité de cet algorithme est de l’ordre θ (nk)

Exemple 2 : Soit l’algorithme suivant :

ALGORITHME PUIS
VARIABLE j, n, t : Entier
DEBUT
LIRE n, t
j 1
Tantque (j<=n) Faire
Exécuter G
j j*t
FinTantQue
FIN

Déterminer sa complexité.

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 9

Solution
En considérant pour cet algorithme que les différentes valeurs
que j devra prendre sont les puissances successives de t, nous aurons :
t0, t1, t2, t3, , t4, , t5, ……
En revanche, G sera répété exactement X fois, avec X le premier
exposant tel que :
tx > n
En introduisant de par et d’autre de notre inéquation le
logarithme en base t, nous aurons : logt tx > logt n qui donne :
X . logt t > logt n
X > logt n
Par conséquent X = ( logt n)+1
La complexité de cet algorithme est de l’ordre de logt n, c.à.d. θ (logt n)

II. 3. Expression des Algorithmes

Les Algorithmes qui seront mentionnés dans ce cours pour

exprimer les différentes opérations utiliseront principalement cinq Algorithmes
de mécanismes de contrôle de flux d’action, qui sont :
L’itération,
La sélection,
La séquence,
L’affectation,
L’appel extérieur.
Le langage utilisé pour représenter ces mécanismes est le
pseudo code suivant :
Pour l’itération : Tantque c faire
X
Fintantque

Pour la sélection : Si c alors x

Sinon x
Finsi
Pour la séquence :
x KOJ NGALANDO
ASSISTANT ALI
CONCEPTEUR DES SYSTEMES D’INFORMATION
x
 Cours d’Algorithmique II
G2 Informatique de Gestion 10

Pour l’affectation : Z1 Z2

Pour l’appel extérieur : Nom (A)

Avec C = une forme booléenne

x = mécanisme quelconque de contrôle de flux d’actions
Z1 et Z2 sont des zones quelconques se mémoire
Nom est l’indication de l’objet appelé
A = série des arguments attachés à l’appel extérieur

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 11

CHAPITRE III. ITERATION RECURSIVITE ET RECURRENCE

III.1 Définition des concepts

En informatique, le thème ITERATION se rencontre sous différents

aspects. Les algorithmes et les programmes utilisent l’itération pour accomplir
des tâches répétitives et évitent ainsi d’avoir à spécifier individuellement un
grand nombre d’états similaires. Les langages de programmation utilisent des
constructions des boucles pour cela.

Pour mettre en œuvre des algorithmes itératifs, une notion

proche de la répétition est la RECURSIVITE. Une technique ou un concept est
défini directement ou indirectement en fonction de lui-même.

La récursivité est un outil très important et très utile en

informatique. Des nombreux algorithmes sont en effet décrits de manière plus
descriptive et plus directe en terme de récursivité.
Une procédure est récursive si elle peut faire appel à elle –
même.
Pour qu’une procédure récursive ne continue pas à tourner
indéfiniment, elle doit être bien définie c’est – à – dire qu’elle doit remplir les
deux propriétés suivantes :
1. Elle doit posséder des critères appelés (critères de base)
pour lesquels la procédure ne s’appelle pas elle-même,
2. A chacun de ses appels, elle doit s’approcher de ses
critères.
Une autre notion importante est la RECURRENCE très proche de la
récursivité.
La récurrence, la récursivité et l’itération sont des concepts
fondamentaux qui apparaissent sous des multiples formes dans les modèles
de données, les structures de données et les algorithmes

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 12

III.2 Récursivité et algorithmes récursifs

Une définition récursive met en jeu une base, où un ou plusieurs

objets simples sont définis, et une étape de récurrence où des objets de
complexité supérieure sont définis en fonction des objets de la collection qui
sont de moindre complexité.
Pour transformer une fonction itérative en une fonction récursive,
nous devons définir UN INVARIANT DE BOUCLE, UNE BASE et UNE
RECURRENCE.
Un invariant de boucle est une assertion S qui est VRAIE par
récurrence chaque fois que nous atteignons un endroit particulier dans la
boucle.
L’assertion S est prouvée par récurrence sur un paramètre qui
mesure le nombre de fois que nous avons parcouru la boucle.

Exemple : calcul de la factorielle de n par une fonction non récursive.

Algorithme Factoriel
Variable Fact : entier
n, P : octet
Début
Lire n
Si (n = 0) Alors Fact 1

Sinon P 1
Fact 1
Tantque (P< = n) Faire
Fact Fact * P
P P+1
Fintantque
Finsi
Ecrire Fact
Fin

En considérant, la fonction ci-haut, nous allons nous intéresser à

la partie itérative de l’algorithme, c'est-à-dire aux lignes qui commencent par
Tantque, et qui finissent par Fintantque.

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 13

Tantque (P< = n) Faire

Fact Fact * P
P P+1
Fintantque

Nous pouvons considérer le point d’entrée de la boucle, où nous

avons Tantque (P < = n) Faire dans cette partie de l’algorithme.

La base est considérée comme la première valeur à partir de

laquelle l’invariant de la boucle respecte la condition posée. Dans ce cas,
comme P a été initialisé à 1, alors nous pouvons prendre la base qui vaut 1.
BASE = 1

Chaque fois que nous atteignons le point fixé dans notre

algorithme, la valeur de la Fact vaut toujours la factorielle de P-1 donc :
INVARIANT vaut: S(i) = (i – 1)! pour tout i valeur de P.

Vérifions cette assertion pour toutes les valeurs de P si l’assertion

est correcte.
RECURRENCE

i S(i)
1 0! = 1
2 1!=2
3 2!=4
n-1 (n-2) !
n (n-1) !
Lorsque i aura la valeur de n+1 nous n+1 nou
n+1 n! quitterons la boucle et S(i) vaudra n !

Comme cet algorithme peut vérifier cette assertion on peut le

mettre sous forme de fonction récursive. Pour le faire, il faut :
1. remplacer la ligne d’entrée de la boucle par une

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 14

alternative Si,
2. appeler la fonction en modifiant la valeur qui doit être
passée en paramètre.
3. supprimer la ligne qui permet de changer la valeur qui
était dans la condition de la boucle,
Pour notre cas, nous aurons :
Si (P < = n) alors Fact n* factoriel (Fact, n-1)

Le calcul de la factorielle de n par une fonction

récursive deviendra:
FONCTION Factoriel (Variable Fact, n)
Si (n = 0) Alors Fact 1
Exit
Sinon P 1
Si (P< = n) alors P 1
Fact n * Factoriel(Fact, n- P)
Finsi
Finsi
Finprocedure

EXERCICES

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 15

CHAPITRE IV. STRUCTURES PRINCIPALES DES DONNEES

En mémoire primaire
A. TABLEAU
Un tableau est une structure linaire de n éléments homogènes
des données, dans laquelle la représentation de la relation entre les données
se fait au moyen des positions d’emplacement séquentielles et contiguës.
n est un entier appelé longueur ou taille du tableau.
L’accès aux différents éléments du tableau se fait à l’aide d’un
ensemble d’indices.
Un indice permet à un élément du tableau d’être repéré par sa
position relative dans ce tableau. Le plus petit indice de cet ensemble
d’indices est appelé borne inférieure, le plus grand indice de cet ensemble
d’indices est appelé borne supérieure.
Soit TAB, le nom d’un tableau de n éléments, alors TAB(k) est une
variable indicée et k dont la valeur appartient à l’ensemble des indices de
TAB, est l’indice de cette variable indicée.
Si A et B sont respectivement la borne inférieure et la borne
supérieure du tableau TAB, alors la structure est notée : TAB (A : B).Un tel
tableau est appelé tableau à une dimension.

A1. Représentation en mémoire

Les éléments du tableau étant des mots séquentiels et contigus,

le système d’exploitation n’a pas besoin de garder la trace de chaque
élément du tableau. Pour un tableau donné, il ne garde que sa base.
Exemple : Le tableau E(10 : 14) est représenté comme suit en
mémoire :

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 16

Si l’adresse de E(10) est 317 et que chaque case a 3 bytes alors

E(11) aura l’adresse 320.

Pour chaque tableau on note la seule adresse du premier

élément qui est la BASE.

Si W est considérée comme l’espace occupé par un élément du

tableau TAB en mémoire, et si A représente la borne inférieure du tableau et
B la borne supérieure du tableau, nous aurons :

 La taille du tableau TAB(A : B) vaudra :

TAILLE de TAB(A : B) = B – A +1

 L’espace total occupé par le tableau en mémoire sera égal à :

ESPACE occupé par TAB(A : B) = W * TAILLE

 L’adresse d’un élément d’indice k en mémoire sera trouvée par :

ADRESSE de TAB(k) = BASE + (k – 1)*W

 La position d’un élément se trouvant à l’indice k vaudra :

POSITION de TAB(k) = k – Borne Inférieure + 1

A 2. Opérations

Les opérations possibles sur la structure des tableaux sont :

Accès séquentiel,
Insertion,
Suppression,
Tri,
Recherche,
Fusion.
ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 17

Accès séquentiel

Lorsque l’on doit appliquer un traitement à chaque élément ou

à une grande partie d’éléments du tableau, il est mieux et naturel de
parcourir séquentiellement ce tableau en commençant par l’indice le plus
petit ou le plus grand.
La complexité d’une telle opération est θ(n) si la taille du tableau
est n.

Exemple : Soit le tableau Elie(4) suivant

On demande d’ajouter 2 à chaque élément de ce tableau.

Deux morceaux d’algorithmes possibles seraient :

La complexité serait de l’ordre θ(n) pour un tableau de taille n, Elie(1 : n)

Insertion d’éléments

L’insertion d’un élément autre que le dernier nécessite le

déplacement de la moitié des éléments du tableau, en moyenne vers la fin
de ce tableau. Il est impossible d’éviter ce déplacement, et cela augmente
à coup sûr la complexité de cette opération.

BELIER FOUINE CIVETTE

On demande d’insérer ‘‘TANTALE’’ à la position A(2)

BELIER TANTALE FOUINE CIVETTE

N.B : L’insertion du dernier élément est toujours permise.

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 18

Suppression d’éléments

La suppression d’un élément autre que le dernier nécessite le

déplacement de chaque élément qui suit d’une position vers le début du
tableau de manière à ce que le tableau ne soit pas désarticulé cela risque
d’augmenter la complexité de l’opération.

BLANC ROUGE VERT BLEU

On demande de supprimer ‘‘ROUGE’’ de ce tableau

BLANC VERT BLEU

Pour le déplacement, il faut que :

A(3) occupe la place A(2)
A(4) occupe la place A(3)
Pour éviter ce déplacement, il suffit de marquer par une mention
spéciale l’élément supprimé tout en le laissant en place.

N.B : En principe, on ne peut supprimer que le dernier élément d’un tableau.

Tri d’éléments

L’opération de tri consiste à ordonner les données contenues

dans une structure selon une séquence déterminée.
Exemple : Trier ces boîtes selon l’ordre croissant et décroissant.

L’ordre strictement croissant si l’élément qui vient est strictement supérieur et

non égal ou inférieur.
ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 19

Ce tableau est en ordre décroissant mais pas

en ordre strictement décroissant parce que
l’élément A(3) est égal à l’élément A(4). Il faut
que l’élément d’avant soit inférieur et non
inférieur ou égal.

Ce tableau est en ordre décroissant et aussi en

ordre strictement décroissant

Ce tableau est trié en ordre croissant et

décroissant.

Généralement, le tableau est une structure efficace pour

l’opération de tri et il existe des très nombreux algorithmes de tri utilisant le
tableau comme structure de base.
Nous illustrons cette opération pour le tri appelé « TRI BULLE ». Ce
tri opère de la manière suivante :
Soit un tableau T(1 : n) qui a n éléments en ordre croissant.

La 1ère étape compare T(1) et T(2), puis

T(2) et T(3), puis
T(3) et T(4), puis
T(4) et T(5)
T(n-2) et T(n-1), puis
Enfin T(n-1) et T(n).

Cette 1ére étape place correctement T(n). Elle nécessité (n-1) comparaisons.

La 2ère étape compare T(1) et T(2), puis

T(2) et T(3), puis
T(3) et T(4), puis
T(4) et T(5)

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 20

Enfin T(n-2) et T(n-1).

Cette 2ème étape place correctement T(n-1). Elle nécessite (n-2)
comparaisons.

La 3ère étape compare T(1) et T(2), puis

T(2) et T(3), puis
T(3) et T(4), puis
T(4) et T(5)
Enfin T(n-3) et T(n-2).
Cette 3ème étape place correctement T(n-2). Elle nécessite (n-3)
comparaisons.
Ainsi de suite jusqu’à la dernière étape qui va comparer T(1) et
T(2). Cette dernière étape place correctement T(2) et elle a nécessité une
seule comparaison.
Calculons la complexité de l’algorithme de tri bulle
Le nombre total des comparaisons égal :
(n-1) + (n-2) + (n-3) + …..+ 2 + 1 = (((n-1)+1)/2)*(n-1))
= n(n-1)/2
= (n2-n)/2

En mettant n2 en évidence, on obtient : = n2(1-1/n)/2

La complexité de cet algorithme est de l’ordre de θ(n2) C
L’algorithme du tri bulle est :

Celle-ci est une structure de deux instructions.

Recherche
ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 21

Lorsque l’on doit chercher un donnée précise X dans un tableau

non trié, la seule possibilité est la recherche séquentielle.
Dans cette recherche l’algorithme doit parcourir tous les
éléments du tableau se trouvant devant pour trouver X.
Si X ne se trouve pas dans le tableau, l’algorithme aura nécessité
(n + 1) comparaisons pour un tableau de taille n.
Si X se trouve dans le tableau on peut s’appuyer sur la notion
probabiliste pour déterminer la complexité de cette opération : Si pk est la
probabilité que X soit dans l’élément T(k). Si q est la probabilité que X ne soit
pas dans le tableau T(1 : n), si l’algorithme utilise m comparaisons lorsque X se
trouve dans l’élément T(n),
Alors le nombre moyen des comparaisons est :

= 1p1 + 2p2 + 3p3 + …+ mpm +…. +npn + (n + 1)q

=1. (1/n) + 2. (1/n) + 3. (1/n) +…+ m. (1/n) +…+n. (1/n) + (n+1). q
= (1+2+3+…+m+…+n). (1/n) + (n+1).q
= (n. (n + 1)/2). (1/n) + (n + 1). q

Lorsque la donnée est là ou si elle n’est pas là, la complexité doit

valoir θ(n).
Lorsque l’on doit chercher une donnée précise x dans un
tableau trie, la recherche séquentielle est toujours possible mais il existe dans
ce cas une recherche plus performante et plus efficace appelée la
recherche binaire.
Dans cette recherche à chaque étape l’algorithme réduit de
moitié la partie du tableau restant à explorer.
Soit le tableau a(1 : n) trié, soit x la donnée à chercher dans ce
tableau, un énoncé formel de l’algorithme de recherche binaire est :

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 22

La recherche binaire et de la complexité de θ(log2n).

10 14 19 20 21 30 40 56 77 79 81 99
1 2 3 4 5 6 7 8 9 10 11 12

Fusion

Cette opération est triviale elle doit allouer un nouveau tableau

dont la taille peut absorber tous les éléments des tableaux à fusionner.

TAB1: A B C D TAB2: E F G H I J TAB3: A B C D E F G H I J

1 2 3 4 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10

A.3 Tableau multidimensionnel

Un tableau multidimensionnel est un tableau TAB(a : b, c :d,

e :f,……) dans lequel chaque élément est repéré par plusieurs indices. La cas
spécifique d’un tableau a (1 : m, 1 : n) à deux dimensions fournit une structure
formée de m lignes et de n colonnes généralement appelé matrice de taille
m x n.
Logiquement on peut représenter un tel tableau, par exemple
de taille 5 x 9 comme suit :

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 23

A (3 , 4) est l’élément situé au croisement de la 3ème ligne et de la

4ème ligne de cette structure.
Physiquement ce sont les lignes ou les colonnes de la matrice qui
sont logés dans les blocs des mémoires successifs. On aura donc (m x n)
position de mémoire successives.
Pour le stockage des colonnes (exemple d’un tableau A (1 :5,
1 :9))

Exemple a :

1 5 9 2 6 10 3 7 11 4 8 12
A(1,1) A(2,1) A(3,1) A(1,2) A(2,2) A(3,2) A(1,3) A(2,3) A(3,3) A(1,4) A(2,4) A(3,4)

Pour le stockage des lignes (exemple d’un tableau A(1 :5, 1 :9))

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 24

Si w est le nombre de bytes (octets) consommés par un élément

du tableau A (1 : m, 1 : n), si Base(A) est l’adresse du début de ce tableau
alors l’adresse de l’élément A (j, k) en mémoire est :
Base (A) + w [m (k-1) + (j-1)] en cas de stockage des colonnes,

Base (A) + w [n (j-1) + (k-1)] en cas de stockage des lignes.

Exemple : A (1:2, 1:4)

1 2 3 4
1 A B C D
2 E F G H

Supposons que chaque élément du tableau consomme 7 bytes.

Calculer l’adresse de l’élément A (2,3) en cas du stockage en
colonne si la base (A) = 0

= Base (A) + 7 [2 (3-1) + (2-1))

= 0+7 (4+1)= 35

Représentation de ces colonnes en mémoire

D’une manière générale si a est un tableau a(d1 :f1,d2 :f2,d3 :f3,…,

dn, fn) ayant n dimensions et de taille m1*m2*m3*….*mn, alors l’adresse de
l’élément a(k1, k2, k3,….kn) en mémoire est :

Pour le stockage des colonnes :

ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 25

Base(A)+[w(((…EnLn-1+En-1)Ln-2+Ln-2)+…+E3)L2+ E2)L1+E1]
Pour le stockage des lignes :
Base(A)+[w (((…E1L2+ E2)L3 + E3)L4+…+ En-1) Ln+ En)]

Avec :
Li = borne supérieure – borne inférieure +1
Ei = ki – borne inférieure
w = nombre de bytes nécessaires pour stocker un élément du tableau a.
Ei représente en fait l’indice effectif qui exprime le déplacement de ki par
rapport à l’indice inférieur et relativement dans l’intervalle (di : fi).

Exemple : Soit un tableau A (2 :8, -4 :1, 6 :10) à trois dimensions rangées par
lignes en mémoire et dont l’adresse de début est 38.

Si chaque élément consomme 2 bytes, trouvez l’adresse de

l’élément A (5 ;-1, 8)

Ecrire les longueurs de chaque indice (3 indices)

L1 = 8 – 2 = 7
L2 = 1 + 4 + 1 = 6
L3 = 10 – 6 + 1 = 5

Calcul des indices effectifs de l’élément A (5, -1, 8)

E1 = 5 – 2 = 3
E2 = -1 + 4 = 3
E3 = 8 – 6 = 2

L’adresse est : Base (A) + w [(E1. L2 + E2) L3 + E3]

= 38 + 2 [(3. 6 + 3) 5 + 2]
= 38 + 214
= 252

b. A (3, -5, 6) impossible parce que -5 n’appartient pas au tableau.

A.4 Traits principaux des tableaux et conclusion

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 26

Les éléments d’un tableau sont reliés par leurs relations physiques
en mémoire et non par une autre quelconque information,
Le tableau est une structure statique. Une fois alloué sa taille ne
peut plus être modifiée,
Il y est généralement malaisé de procéder aux opérations
d’insertion de suppression d’un élément autre que le dernier.

EXERCICES

1. Soit le tableau G(-5 : 9). Il est demandé :

De le représenter
De calculer sa taille

2. Soit le tableau D(-5 :59) dont la taille de chaque élément est de 7 octets. Calculer
l’adresse de l’élément dont l’indice est :
a) i avec i qui respecte la condition (-5 ≤ i ≤ 59)
b) 53
c) 85

3. Soient les données suivantes du tableau TAB(15 : 107) :

Base(TAB)= 91
W= 4
a) Donnez l’adresse de l’élément se trouvant à la position 57
b) Donner l’adresse de l’élément se trouvant à l’indice 57
4. On donne le tableau INFO(4 :23, -7 :12, 4 :10). Si le premier élément de ce tableau
occupe l’adresse 304 dans la mémoire, et si chaque élément occupe 4 bytes,
déterminez :
a) La taille de se tableau si il est disposé par colonne
b) La taille de se tableau si il est disposé par ligne
c) L’espace total occupé par ce tableau en mémoire
d) L’adresse de l’élément INFO(8, 10, 0) si le stockage se fait par ligne
e) L’adresse de l’élément INFO(8, 10, 0) si le stockage se fait par colonne
f) La position de l’élément INFO(11, 9, -1) si le stockage se fait par colonne
g) La position de l’élément INFO(11, 9, -1) si le stockage se fait par ligne

5. Ecrire un algorithme qui divise par 4 tous les éléments contenus dans le tableau
EL(1 :15) de réels.

6. Construire un algorithme qui donne la sommation de toutes les valeurs contenues

dans le tableau SOM(-1 :5, 1 :13).

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 27

7. Soit le tableau S(1 :n) dont les éléments sont des réels. Il vous est demandé :
a) D’écrire un algorithme qui initialise à 0 tous les éléments d’indice PAIR, et à
3 tous les éléments d’indice IMPAIR.
b) D’écrire un algorithme qui divise par 3 tous les multiples de 6 et de 4
contenus dans ce tableau.
c) De calculer la complexité de chacun de ces deux algorithmes

8. On désire suivre l’évolution du nombre d’étudiants à l’Institut Supérieur de

Statistique, en utilisant le modèle tableau. On dispose de deux tableaux de
même taille soit 20. Le premier tableau contient les promotions, le second les
effectifs. La promotion se trouvant à la position k dans le premier tableau a son
effectif se trouvant à la même position dans le second tableau. On vous
demande de :
a) Représenter cette structure.
b) Proposer un algorithme qui remplace le nombre d’étudiants de G2 INFO,
par une valeur qui sera lue.
c) Supprimer la promotion de G3 DEMO.
d) Ajouter une nouvelle promotion de L3 INFO en considérant que les
dernières cases de chaque tableau sont vides.

9. On demande de construire un algorithme qui fusionne deux tableaux des entiers,

et trie le tableau trouvé en ordre croissant. Sachant que le premier tableau a une
taille de 37, et le second de 21.

10. Soit un modèle qui utilise 4 tableaux comme structure. Dans le premier tableau
nommé ETUDIANT on y stocke les noms de tous les étudiants de G2 INFO/ISS/SHD.
Le second tableau nommé ADRESSE on y stocke les communes de résidence de
chaque étudiant, le troisième tableau nommé ACTIVITE on y stocke l’activité
principale de chaque étudiant, et le dernier tableau nommé ETAT on y
enregistre l’état civil de chaque étudiant.
Il est à signaler que les 4 tableaux ont une même taille qui est de 110, et
toutes les informations à une adresse i quelconque dans tous les tableaux font
références à une même personne.
Ecrire un algorithme complet avec nom et entête qui donne :
a. La liste de tous les étudiants célibataires qui habitent la commune
LUBUMBASHI. (nom, activité, commune.

11. On se décide de gérer les différentes informations concernant les vaccinations

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 28

des enfants dans un service de pédiatrie. Pour y parvenir, le responsable vous

demande de concevoir une structure de données à l’aide des modèles
TABLEAU.
- le premier tableau est à une dimension et contient les noms et les post
noms des enfants
- le deuxième tableau est à deux dimensions (Quatre colonnes)
La première colonne contient les dates de naissance, la deuxième les dates
de l’administration du vaccin BCG, la troisième colonne les dates de
l’administration du vaccin ANTI TETANIC, la dernière les dates de
l’administration de vaccin ROUGEOLE.

Ces deux tableaux ont 143600 lignes.

Ecrire un algorithme qui :
a) affiche la liste de tous les enfants qui ont reçu les trois vaccins
b) affiche la liste des enfants qui sont nés avant le 02/01/2007, et qui ont
reçu au moins deux vaccins
c) affiche la liste du premier enfant trouvé dans les tableaux, qui a été
vacciné de la rougeole à une date qui sera lue

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 29

B. ENREGISTREMENT

Les ensembles d’information sont souvent organisés en une

hiérarchie de champs, d’enregistrements et de fichiers.
Par définition, un enregistrement est un ensemble d’éléments de
données reliés, chacun d’eux étant appelé champ ou attribut.
Un fichier est un ensemble d’enregistrements analogiques.
Chaque élément d’information peut être un item composé de
sous-items, et peut être décomposé en items élémentaires (appelés atomes
ou scalaires). Les noms donnés aux différents éléments d’information sont
appelés identificateurs.
Un enregistrement doit avoir :
 Un ensemble de données hétérogènes, c’est-à-dire qu’il peut
réunir des données de types différents.
 Les éléments de données dans un enregistrement sont indexés par
noms d’attributs, aussi il peut ne pas exister de classement de ces
éléments dans un ordre naturel.
Exemple :
On présente les informations suivantes utilisées dans une école
maternelle concernant un enfant.

La structure de l’enregistrement ci haut peut être décrite comme

suit :

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 30

Le numéro à gauche de
chaque indicateur est appelé numéro de
niveau.

Chaque item composé est

suivi des items élémentaires qui le
constituent, et dont le niveau est d’une
unité inférieure à celui de l’item composé.

Un item est dit composé si et

seulement si il est immédiatement suivi par un item dont le numéro de niveau
lui est supérieur.
Dans une structure d’enregistrement ; certains identificateurs
peuvent désigner des tableaux d’éléments.

Exemple
En remplaçant la première ligne de la structure par : 1 Enfant (134)
Ceci indique un fichier de 134 enregistrements.

Dans cette structure, tous les éléments se trouvant dans une

colonne doivent être nécessairement de même type.

B.1 Représentation en mémoire

Lorsque les données composant les enregistrements sont
homogènes, elles seront rangées dans un tableau, dans le cas ou elles sont
hétérogènes, elles seront représentées par des tableaux parallèles.

Exemple
Soit la liste suivante reprenant les adhérents d’une association, et
comportant le nom, l’âge, le sexe, et le numéro de téléphone de chaque
membre. Nous aurons 4 tableaux parallèles : NOM, AGE, SEXE, PHONE. Par
conséquent pour un indice donné k, les éléments NOM(k), AGE(k), SEXE(k),
ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 31

PHONE(k) appartiennent au même enregistrement

.

B.2 Opérations
Les différentes opérations possibles dans la structure
enregistrement sont :
Parcours séquentiel
Recherche d’un item
Ajout d’un item
Suppression d’un item

Parcours séquentiel
Cette opération permet d’accéder à tous les items de la
structure. Elle permet de parcourir séquentiellement tous les items.

Recherche d’un item

Cette opération permet de rechercher un item de la structure.

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 32

Ajout d’un item

Cette structure permet d’ajouter un nouvel élément à la fin. La
structure prévoit toujours un emplacement BLANK permettant de recevoir un
nouvel item.
Un morceau d’algorithme possible pour effectuer cette
opération serait :

TantQue (Nom_Fichier Not EOF) Faire

Nom_Fichier.suivant
FinTantQue
Nom_Fichier . Nouveau
Colonne1 Valeur1
Colonne2 Valeur2
… …
ColonneN ValeurN

Suppression d’un item

Cette opération permet de supprimer un item de la structure. Il
est commode de supprimer le dernier item.
Pour supprimer un item qui n’est pas le dernier dans un fichier, il
faut d’abord rechercher l’élément à supprimer (La position de l’élément à
supprimer, puis parcourir séquentiellement les autres éléments restant du
fichier.
La suppression dans un fichier est une opération composée.

B.3 Enregistrements de longueur variable

Lorsque certains éléments d’informations d’un enregistrement
peuvent contenir zéro ou plusieurs informations on parle d’un enregistrement
de longueur variable.

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 33

Exemple :
Un parent est identifié au niveau de l’école de ses enfants
par les informations suivantes : son nom, sa profession, son lieu de
service.
Ces informations peuvent être représentées de la manière
suivante :

S’il faut lier chaque parent à son enfant, ceci devient

difficile parce qu’un parent peut avoir plusieurs enfants.

En supposant que KASONGO MWAMBA puisse avoir 2

enfants, ILUNGA SAMBA puisse avoir 3 enfants, TAMBWE
MUTOMBO puisse avoir 1 enfant et TSHIKA KONGOLO puisse avoir
2 enfants, on peut se proposer de représenter ces informations
de la manière suivante :

Nous remarquons que les trois dernières colonnes possèdent les

informations de même nature, par conséquent une solution serait de pouvoir
former un autre modèle qui prendrait la structure de l’enfant. Et nous aurons :

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 34

Ainsi, pour trouver les enfants d’un parent il faut parcourir tous les
enregistrements se trouvant dans l’enregistrement ENFANT ayant le nom du
parent dans la première colonne.

EXERCICES

1) Soit la liste d’entrées suivante correspondant aux enregistrements

d’un fichier d’étudiants :
1 Etudiant, 2 Numéro, 2 Nom, 3 Nom de famille, 3 Prénom,
2 Sexe, 2 Date de naissance, 3 Jour, 3 Mois, 3 Année,
2 Cours, 3 Théorique, 3 Pratique
a) Tracer la structure hiérarchique correspondante
b) Quels sont les items élémentaires ?

2) Trois avocats, PIERRE, CLARISSE et BOB, partagent les mêmes

bureaux. Chacun d’eux possède sa propre clientèle, et les
différentes informations sont enregistrées dans un modèle
enregistrement se nommant CLIENT_AVOCAT, possédant deux
colonnes ; l’une se nommant CLIENT, et l’autre AVOCAT
a) Ecrire un algorithme qui affiche tous les clients de l’avocat se
nommant CLARISSE.
b) Ecrire un algorithme qui nous donne les positions occupées
par les clients de l’avocat PIERRE.
c) Ecrire un algorithme qui nous donne le nombre de tous les
clients de l’avocat BOB.
d) Ecrire un algorithme qui insert le client HUGUES de l’avocat
PIERRE dans cette structure.
e) Ecrire un algorithme qui supprime le client CLASS de l’avocat
BOB.
ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 35

3) Une institution d’enseignement supérieur utilise la structure suivante

d’enregistrement de l’information relative à chaque étudiant.

1) Combien ce fichier contient-il d’items élémentaires ?

2) Ecrire un algorithme qui lit l’IDENTITE d’un étudiant, trouve et
imprime sa position, et sa promotion.
3) Ecrire un algorithme qui recherche et affiche le parcours d’un
étudiant qui sera lu.

4) Une institution d’enseignement universitaire se décide de gérer

les différentes informations à l’aide de 3 fichiers. Le premier se
nomme ETUDIANT et comprend les informations suivantes :
NUMMAT, NOMETU, DATENAIS, ADRESSEET, le deuxième fichier se
nomme ACADEMIQUE comprend les informations suivantes :
ANNEEACAD, PROMOTION, SESSION, POURCENTAGE, DECISION.
Ecrire un algorithme qui :
1) Donne le cursus académique d’un étudiant qui sera lu au
clavier (lire le matricule de l’étudiant)
2) Donne la liste des étudiants ayant fait au moins deux fois une
même promotion
1) Le garage Elouisk se décide de gérer les entretiens de différents
véhicules des abonnés par une structure enregistrement. Elle dispose
trois fichiers différents dans lesquels il stocke ses informations.
Le premier nommée ABONNE contient les informations suivantes sur les
abonnés qui sont :
 Le code de l’abonné
 Le nom de l’abonné
 L’adresse physique de l’abonné
 La profession de l’abonné
ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 36

 Un numéro de contact

Le second nommé VEHICULE contient les informations suivantes sur les

véhicules qui sont :
 La plaque du véhicule
 Le type du véhicule (Voiture, Camion, Camionnette, Jeep,…)
 La marque du véhicule
 L’année de fabrication
 L’année de sa première mise en circulation
 Le code de l’abonné

Le dernier nommé ENTRETIEN contient les informations suivantes sur les

entretiens. Ces informations sont les suivantes :
 La date de l’entretien
 La plaque du véhicule entretenu
 L’observation de l’entretien
 La date du prochain entretien

Ecrire un algorithme qui donne :

a) La liste de tous les véhicules entretenus à une date donnée (la

date sera lue au clavier)
b) La liste de tous les véhicules par propriétaire
c) Pour un véhicule X donné, les identités de son propriétaire ainsi
que tous les entretiens réalisés sur ce véhicule (Observation)
d) La liste de tous les véhicules qui seront entretenus prochainement
à la date du 15 Mai 2009

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 37

C. LISTE
Une liste est une collection linéaire d’éléments d’informations
dont chacun spécifie une information spéciale qui permet de relier ces
éléments entre- eux.

Dans ces conditions, les éléments successifs de la liste n’ont plus

besoin d’occuper des positions adjacentes (contiguës) en mémoire.

Si cette information qui permet de relier les éléments d’une liste

entre – eux est un lien ou pointeur, on parle alors d’une LISTE CHAINE (ou
LISTE MONODIRECTIONNELLE).

Une liste chaînée est un ensemble des nœuds dans lesquels

chaque nœud est divisé en deux parties :

 La première contient l’information dont l’élément est porteur,

 La seconde contient l’adresse du nœud suivant dans la liste.

Exemple : La structure des mots suivants en mémoire.

Début = Base (L) = 101

Permet de construire la liste chaînée suivante :

C.1 Représentation en mémoire

A moins qu’il ne soit spécifié autrement une liste sera rangée en

mémoire à l’aide de deux tableaux parallèles.

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 38

Le premier qu’on appelle souvent INFO contiendra toutes les

parties « information » des nœuds de cette liste,
Le deuxième que l’on appelle souvent LINK contiendra toutes les
parties « pointeur » des nœuds de cette même liste.

Ainsi INFO(k) et LINK(k) contiennent respectivement la partie

information et la partie pointeur d’un nœud de cette liste situé à l’adresse k.

En plus deux objets seront nécessaires pour la représentation

d’une liste :
- Une variable appelée généralement START qui contient toujours la
position du premier élément de la liste,
- Une valeur généralement appelée NIL qui indique la fin de la liste.

Exemple : Une maison de vente dans laquelle chacun des commis ne

s’occupe que de ses propres clients peut se représenter comme
suit :

Les clients du commis JESUS sont : Luther, Colomban, Irénée, Paul, Wesley,
Martin, Elie.
Les clients du commis ARCHANGE sont : Chérubin, Séraphin, Michael, Gabriel.
Les clients du commis PAPE sont :
PAPE n’a pas de client son pointeur = NIL.
ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 39

Les clients du commis MOISE sont : Josué, Aaron, Caleb.

Matthieu et Marc sont des clients sans commis, ils sont inaccessibles.

N.B. : Les éléments de la liste ne sont pas contigus.

C.2 Opérations

Accès séquentiel : accès aux éléments successifs d’une liste,

Recherche : accès à la position d’un élément de la liste contenant une
donnée déterminée,
Attribution : c’est le fait d’accorder un élément de la liste à une nouvelle
donnée,
Allocation : opération par laquelle le système d’exploitation alloue un nouvel
élément pour la liste,
Insertion : c’est l’ajout d’un élément dans la liste, opération qui allonge
dynamiquement la taille de la liste.
Suppression : destruction d’un élément de la liste, opération qui raccourci
dynamiquement la taille de la liste,
Ramassage des ordures (GARBAGE COLLECTOR) : opération servant à
construire une liste particulière composée des nœuds libres ou
utilise.

Accès séquentiel

Lorsque l’on doit appliquer un traitement donné à chaque nœud

ou à une grande partie des nœuds d’une liste, la seule possibilité est le
parcours séquentiel de tous les nœuds concernés.
Soit une liste :

Le parcours séquentiel est :

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 40

La complexité est θ(n) si il y a n nœuds dans la liste.

Recherche
Lorsque l’on doit chercher une donnée précise X dans une liste
des données non triées, la seule possibilité est la recherche séquentielle

L’algorithme est :

Ramassage des ordures

Il peut s’avérer intéressant, après une longue série de suppression

et d’insertion dans la liste pour des raisons de gestion d’espace de former
une liste particulière de case mémoire non utilisée.
Le début de cette liste particulière sera généralement conservé
dans la variable appelé AVAIL. Dès qu’un nœud devient inutile ou
inaccessible, l’algorithme de ramassage des ordures devra l’insérer dans la
liste issue de AVAIL.

Insérer les nœuds inutiles ou inaccessibles aussitôt qu’il le devient,

risque de consommer trop de temps d’exécution. Pratiquement cette
insertion se fait périodiquement et globalement pour tous les espaces inutiles.
En marquant dans un premier temps les espaces encore utiles de

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 41

toutes les listes,

Dans un second temps en collectant tous les espaces non
marqués pour les insérer dans la liste des cases disponibles.

Attribution et insertion

Lorsqu’une nouvelle donnée arrive l’opération attribution peut

être appliquée pour lui trouver un élément dans la liste des cases disponibles.

Algorithmiquement le cœur de cette opération d’attribution est :

Allocation et insertion

Lorsqu’une nouvelle donnée arrive, cette opération (allocation)

sert à demander un nouvel élément au système d’exploitation.
Schématiquement :

P
P est un nœud situé quelque part en mémoire

Si la donnée X qui réclame cet élément doit être insérée en

début de la liste des éléments valides, un algorithme possible est :

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 42

Suppression et insertion

Cette opération sert à :

- Enlever un nœud B devenu inutile de la liste des éléments utiles, et
- Insérer ce nœud dans la liste des éléments disponibles.

Si on doit insérer le nœud B en début de la liste des cases libres,

un algorithme possible serait :

C.3 Liste chaînée circulaire à en tête

Une liste chaînée circulaire à en-tête est une liste chaînée qui
contient toujours un nœud spécial (le nœud d’en-tête) situé en tête de la
liste et qui est pointé par le dernier nœud.

START

Le nœud A est le nœud d’en-tête.

Un liste chaînée circulaire à en-tête est vide si Link(START) = START

START

Donc la position du 1er nœud d’une liste chaîne circulaire à en-

ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 43

tête est : Link(START) et non START.

Une liste chaînée circulaire à en-tête a surtout l’avantage de rendre
des nombreuses opérations plus faciles à formuler et à implémenter car :
- Le pointeur « Nil » n’est plus utilisé,
- Chaque nœud ordinaire possède un précédent et un suivant, et le
premier nœud ne constitue plus obligatoirement un cas particulier.

C.4 Liste bidirectionnelle

Une liste bidirectionnelle est une liste qui peut être parcourue de
la tête vers la queue et de la queue vers la tête, c’est-à-dire étant donnée la
position n d’un nœud, nous avons immédiatement accès au nœud qui le suit
et à ce lui qui le précède.

Un nœud dans une liste bidirectionnelle est alors divisé en trois

parties :
- Un champ d’information, appelons le toujours « INFO» qui contient les
données de ce nœud,
- Un champ de pointeur, appelons le « FORW» qui contient la position du
nœud suivant,
- Un champ de pointeur, appelons le « BACK» qui contient la position du
nœud précédant.

En plus, une liste « bidirectionnelle » est dotée de deux autres

pointeurs :
« FIRST» qui pointe sur le 1er nœud de la liste, et
« LAST» qui pointe sur le dernier nœud de la liste.
Une liste bidirectionnelle est rangée en mémoire à l’aide de trois tableaux
parallèles :
Un tableau pour « info»
Un tableau pour « back»
Un tableau pour « forw»

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 44

Exemple : On désire parcourir les noms de cinq livres de Moïse tantôt dans
leurs ordres alphabétiques, tantôt dans leurs ordres d’apparition
dans la bible. Cette liste pourra se représenter de la manière
suivante :

« FIRST» et « Forw» concerne l’ordre d’apparition de ces livres dans la bible,

« LAST» et « Back» concerne l’ordre alphabétique.

Soit le nœud X de position P dans une liste bidirectionnelle, on

sait alors que Back(P) est la position du nœud qui précède X, Forw(P) est la
position du nœud qui suit X, c’est-à-dire schématiquement nous avons :

Lorsque l’on souhaite supprimer le nœud x de pointeur p il suffit

de modifier ses voisins de gauche et de droite de la manière suivante :

FORW (Back(p)) FORW(p)

Back(FORW(p)) Back(p)

C.5 Liste inversée

La notion des listes inversées permet de généraliser l’utilisation de

la liste chaînée et de lever certaines restrictions imposées sur les informations
des nœuds d’une liste simple.

Dans l’exemple (commis clients) il serait malsain (malaisé) de

représenter le cas d’un client qui serait géré par plusieurs commis.
Dans une liste inversée, les nœuds sont dépouillés de leurs
ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 45

pointeurs et ces pointeurs sont rangés dans une séquence voulue

(généralement sous forme de tableau) à la suite d’un argument donné.

Sous forme d’une liste inversée, les clients de l’exemple cité ci

haut perdraient leurs parties Link est la représentation deviendrait :

Exercices
2) Une entreprise industrielle qui achète les produits de transformation
désire ranger les différentes informations concernant les produits et les
fournisseurs de ces produits dans une liste mono directionnelle.
Les informations concernant les produits sont :
 Code du produit
 Nom du produit
 Unité de consommation du produit
 Prix unitaire du produit
Les informations concernant les fournisseurs sont :
 Code du fournisseur
 Nom du fournisseur
 Adresse du fournisseur
Pour chaque nœud qui concerne le produit, on y ajoute un code
spécial P et pour chaque nœud qui concerne le fournisseur, le code
spécial est F
Sachant que l’adresse du fournisseur donne le nom du pays
Ecrire un algorithme qui :

a) Donne les produits qui ont un prix unitaire inférieur à 2000 £

b) Donne le fournisseur le moins cher pour un produit X lu
c) Donne la liste de tous les fournisseurs qui livrent au moins 3 produits
d) Donne la liste de tous les produits qui sont livrés par au moins 3
fournisseurs
e) Donne la liste de tous les fournisseurs qui livrent le produit nommé
’’COKE’’
ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 46

f) Modifie de 3% le prix unitaire de tous les produits fournis par le

fournisseur de code FIH-31

3) Le garage Elouisk se décide de gérer les entretiens de différents

véhicules des abonnés par une structure liste. Elle dispose trois listes
différentes dans lesquelles elle stocke ces informations.
La première nommée ABONNE contient les informations suivantes sur
les abonnés qui sont :
 Le code de l’abonné
 Le nom de l’abonné
 L’adresse physique de l’abonné
 La profession de l’abonné
 Un numéro de contact

La seconde nommée VEHICULE contient les informations suivantes sur

les véhicules qui sont :
 La plaque du véhicule
 Le type du véhicule (Voiture, Camion, Camionnette, Jeep,…)
 La marque du véhicule
 L’année de fabrication
 L’année de sa première mise en circulation
 Le code de l’abonné

La dernière nommée ENTRETIEN contient les informations suivantes sur

les entretiens. Ces informations sont les suivantes :
 La date de l’entretien
 La plaque du véhicule entretenu
 L’observation de l’entretien
 La date du prochain entretien

Ecrire un algorithme qui donne :

a) La liste de tous les véhicules entretenus à une date donnée (la
date sera lue au clavier)
b) La liste de tous les véhicules par propriétaire
c) Pour un véhicule X donné, les identités de son propriétaire ainsi
que tous les entretiens réalisés sur ce véhicule (Observation)
d) La liste de tous les véhicules qui seront entretenus prochainement
à la date du 15 Mai 2009

3). Une entreprise industrielle qui achète les produits de transformation

désire ranger les différentes informations concernant les produits et les
fournisseurs de ces produits dans une liste chaînée mono directionnelle
ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 47

composée de deux sortes de nœuds.

Les informations concernant Les informations concernant les

les produits sont : fournisseurs sont :
 Code du produit  Code du fournisseur
 Nom du produit  Nom du fournisseur
 Unité de consommation  Adresse du fournisseur
 Prix unitaire du produit fourni

Pour chaque nœud qui concerne le PRODUIT, on y ajoute un code spécial

P et pour chaque nœud qui concerne le FOURNISSEUR, le code spécial
est F.

L’adresse du fournisseur donne le nom du pays, et un nœud du produit est

suivi par tous les nœuds des fournisseurs qui livrent ce produit.

P CodeProduit NomProduit UniteCons Link

Nœud PRODUIT

F CodeFour NomFour Adresse PrixUnit Link

Nœud FOURNISSEUR
Ecrire un algorithme qui donne :
1) Le(s) produit(s) qui ont un prix unitaire inférieur à 2000$ (le nom du
produit, le prix de l’unité de consommation, le nom du fournisseur)

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 48

D. PILE

Une pile est une structure linéaire en laquelle il n’est possible

d’ajouter ou de retirer les éléments qui a une seule extrémité appelé sommet.
Donc le dernier élément ajouté à une telle structure sera le 1er à
en être retiré.

Les éléments sont ainsi retirés de la pile dans l’ordre inverse dans
lequel ils y ont été ajoutés.

La pile est qualifiée de « Liste LIFO » = Last In First Out.

Il existe des situations fréquentes en informatique dans lesquelles

il est souhaitable de restreindre les insertions et les suppressions d’informations
à un seul bout de la structure, pas à l’intérieur.

D.1 Représentation en mémoire

Le plus souvent une pile est représentée au moyen d’une liste

monodirectionnelle ou d’un tableau linéaire. Dans le deuxième cas :

Le tableau sera appelé « STACK », par exemple « Top » sera la

variable qui contiendra l’adresse de l’élément au sommet de la pile,
« MAXSTK » donnera le nombre maximum d’éléments qui
peuvent être accommodés par la pile.

Exemple :

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 49

D.2 Opérations

Les deux opérations fondamentales sont :

PUSH : Opération d’adjonction (d’ajout) d’un élément au sommet de la pile,

Pop : Opération de suppression de l’élément se trouvant au sommet de la
pile.

1. Push

Un algorithme possible pour le push de la donnée x est :

Pour réduire la fréquence de dépassement de capacité, on

peut procéder à une réservation initiale d’un espace de mémoire assez
grand pour chaque pile, mais cette façon de procéder peut se révéler
coûteuse si cet espace n’est pas souvent utilisé.

Lorsque cet espace est insuffisant, la fréquence de dépassement

de capacité augmente et le temps consacré au traitement de ce
dépassement de capacité peut de révéler encore plus coûteux.

Diverses techniques ont été développées dans le seul but de

mieux utiliser l’espace réservé dans une pile ou de diminuer la fréquence de
dépassement de capacité.
Une de ces techniques est « l’allocation commune » qui procède
à une allocation d’une seule structure de taille n pour deux piles A et B, dans
laquelle la pile A croit dans un sens et la pile B croit dans l’autre sens de la
manière suivante :

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 50

Evolution de la pile A Evolution de la pile B

(de gauche vers la droite) (de droite vers la gauche)

Ainsi un dépassement de capacité ne peut arriver que si la taille

de la pile A et celle de la pile B dépasse n.

2. Pop

Un algorithme possible pour désempiler l’élément du sommet :

D.3 Exemples

L’exemple le plus souvent donné pour monter l’utilité d’une pile

est le cas de la notion polonaise.

La notion polonaise préfixe désigne une notion d’expression

arithmétique dans laquelle l’opérateur est placé devant ses opérandes.

Exemple : l’expression arithmétique a + b = (notation infixée)

En notation polonaise préfixée les expressions suivantes
seront :
a + b = + ab
(a + b)* c = *+abc
a + (b * c) = a + [b * c] = +a*bc
(a + b) / (c – d) = [+ab] / [-cd] =/+ab – cd

N.B. : Dans cette notation, on n’a pas besoin des parenthèses.

La notation polonaise suffixée (inversée) désigne une notation

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 51

d’expression arithmétique dans laquelle l’opérateur est placé derrière ses

opérandes.
a+b = ab+
(a + b) * c = ab+c*
a + (b * c) = abc*+
(a + b) / (c – d) = (ab+)/(cd)- = ab+cd-/

On voit que les différentes expressions obtenues en notation

polonaise préfixées ou suffixées n’ont mutuellement besoin des parenthèses
car l’ordre dans lequel les opérations doivent être effectuées est
essentiellement déterminé par l’emplacement des opérateurs et des
opérandes dans l’expression.

La notation polonaise préfixée ou suffixée est une notation plus

commode à manipuler, pour un automate, que la notion infixée des
expressions.

Ainsi par exemple l’expression infixée suivante : 3^4-5*2^3–30/6

ou l’on tient compte des niveaux d’évaluation suivant :
Exponentiation, multiplication et division, addition et soustraction.
Nécessite 3 parcours :
Evaluation des exponentiation 81-5*8–30/6,
Evaluation de multiplication et division 81- 40- 5
Evaluation d’addition et de soustraction 36.

La même expression en notation polonaise suffixée s’écrit comme suite :

3 4^5 2 3^*- 30 6 /- ,
et ne nécessite qu’un seul parcours (au lieu de 3).

Un algorithme possible pour évaluer une expression P en notation

polonaise préfixée est :
Soit Q une expression en notation infixée à transformer en un
ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 52

expression P en notation polonaise suffixée. Si on utilise un pile pour ranger

temporairement les opérateurs et les parenthèses de gauche de l’expression
Q.
Si l’expression en notation suffixée (P) est construite en allant de
la gauche vers la droite, en utilisant les opérandes de l’expression infixée (Q)
et les opérations désempilées de la pile.

Si avant toute chose, on empile d’abord une opération

parenthèse ouvrante dans la pile et une parenthèse fermante à la fin de
l’expression Q, alors un algorithme possible est le suivant :

Exemple Q = (a - b) / (c + d * f)
= ab – cdf * + - / (notation suffixée)

1. Tri rapide (quicksort)

Le quicksort est un tri basé sur le principe « diviser pour régner »

par la réduction de la taille de l’ensemble de n éléments à trier en deux
ensembles plus petits sur base d’un élément appelé élément pivot.

Soit A, la liste des nombres à trier suivante :

44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88, 66

Considérons le 1er élément, 44 comme élément pivot, il faut alors :

Parcourir la liste A par la droite en comparant 44 avec chacun des
éléments et permuter 44 avec le 1er qui lui est inférieur, ce qui donne :

22, 33, 11, 55, 77, 90, 40, 59, 44, 88, 66

Parcourir la liste A par la gauche en comparant 44 avec le 1er qui lui

est supérieur, qui donne :

22, 33, 11, 44, 77, 90, 40, 60, 99, 55, 88, 66

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 53

Parcourir la liste A, par la droite en commençant par 55 et en

comparant 44 avec chacun des éléments et permuter 44 avec le 1er qui lui
est inférieur ce qui donne :

22, 33, 11, 40, 77, 90, 44, 60, 90, 55, 88, 66

Parcourir la liste A par la gauche en commençant par 40 et en

comparant 44 avec chacun des éléments et permuter 44 avec le 1er qui lui
est supérieur ce qui donne :

22, 33, 11, 40, 44, 90, 77, 60, 99, 55, 88, 66

La première phase de diviser pour régner se termine : tous les

chiffres à gauche de 44 lui sont inférieurs et tous les nombres à droite se 44 lui
sont supérieurs, donc cette première phase à placer correctement l’élément
pivot c’est-à-dire 44 dans la liste triée : la tâche de triage de la liste A a été
réduite au tri de deux listes plus petites A1 et A2.

La phase de diviser pour régner devra alors être appliquée sur les
listes A1 et A2. Une seule partie de la liste A sera traitée à la fois. Il faut donc
garder la trace de toutes les autres parties en vue de traitement ultérieur.

Cela est accompli en utilisant deux piles, appelons les « BAS » et

« HAUT » pour ranger temporairement et respectivement la borne inférieure et
la borne supérieure de la partie de la liste A que l’on traite.
Cet algorithme se conçoit mieux en deux procédures :

1. PlacePivot (A, N, Bi, Bs, P) : procédure qui trouve la place pour l’élément pivot.
A : liste à trier,
N : taille de la liste A,
Bi : borne inférieure de la partie de « A » à trier,
Bs : borne supérieure de la partie de « A » à trier,
P : adresse de l’élément pivot (par exemple : l’adresse de A(Bi)).

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 54

2. TRI : procédure qui étend le principe de place pivot sur toute la liste
(QUICKSORT).

Dans le cas défavorable (quand la liste A à trier est déjà triée

cette algorithme a une complexité de l’ordre de numéro (n2)
Le 1er élément, pour qu’il soit placé nécessite n comparaisons (la
ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 55

1ère sous liste comporte alors un seul élément, la 2ème sous liste comporte alors
(n – 1) éléments).

Le 2ème élément, pour qu’il soit placé nécessite (n–1)

comparaison (la 1ère sous liste comporte alors un seul élément, la 2ème sous
liste comporte alors (n – 2) éléments), etc.

Au total cet algorithme aura dans ce cas consommé :

n + (n – 1) + (n – 2) + …+ 2 + 1 = θ (n2)
Dans le cas favorable (quand la liste A à trier est vraiment
désordonnée), cet algorithme a une complexité de θ (n log n) :

La réduction de la liste initiale place un élément et produit deux

listes partielles.
La réduction de ces deux listes partielles place deux éléments et
produit quatre listes partielles.
La réduction de ces quatre listes partielles place quatre éléments
et produit huit listes partielles.
La réduction de ces huit listes partielles place huit éléments et
produit seize listes partielles.

Le niveau K permet de placer donc 2K – 1 éléments ;

Il y aura donc environs (log n) niveaux. Comme chaque niveau
utilise au plus n comparaisons, la complexité dans ce cas est de l’ordre de
θ(nlog n)

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 56

E. FILE D’ATTENTE

Une file d’attente est une structure linéaire à laquelle des

éléments ne peuvent être ajoutés qu’à une extrémité (la queue) et être retiré
qu’à l’autre (la tête). Le 1er élément ajouté à une telle structure sera le 1er à
en être retiré. La file d’attente est appelée aussi liste à FIFO.

E.1 Représentation en mémoire

Le plus souvent une file d’attente est représentée au moyen

d’une liste mono directionnelle ou d’un tableau linéaire.

Dans le deuxième cas : Le tableau de taille n sera appelé QUEUE,

« FRONT » sera la variable qui contiendra l’adresse de son premier

élément,
« REAR » sera la variable qui contiendra l’adresse de son dernier
élément.

Chaque fois qu’un élément est supprimé, FRONT s’incrémente de

1, et chaque fois qu’un élément est ajouté REAR s’incrémente de 1.

Après n insertions le dernier élément occupera la case mémoire

QUEUE (n) même si toutes les cases se trouvant devant ce dernier élément
sont VIDES.

Si donc l’on désire insérer un élément dans une file d’attente

pour laquelle REAR = N, il suffit alors de déplacer toute la file d’attente vers le
début de tableau en modifiant de façon correcte le continu de FRONT et de
REAR et d’insérer ce nouvel élément. Cette façon de faire coûte trop chère,
ce pour cela en pratique on considère que le tableau QUEUE est CIRCULAIRE.

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 57

E.2 Opérations

Les deux opérations fondamentales sur la file d’attente sont :

Insertion : Ajout d’un élément dans la file d’attente
Retrait : Suppression d’un élément se trouvant dans la file d’attente.

Un algorithme possible pour l’insertion d’un élément X dans une

file d’attente est :

Si ((Rear = n) et (Front = 1)) ou (Rear = Front – 1)

Alors ECRIRE ‘’ File pleine impossible d’insérer’’
Sinon Si (Rear < > n) Alors Rear Rear + 1
Sinon Rear 1
Finsi
Queue(Rear) X
Finsi

Un algorithme possible de retrait d’un élément X dans une file

d’attente est :

Si ((Rear = null) et (Front = null))

Alors ECRIRE ‘’ File vide impossible de retirer’’
Sinon X Queue(Front)
Si (Front = Rear) Alors Rear null
Front null
Sinon Si (Front = n) Alors Front 1
Sinon Front Front + 1
Finsi
Finsi
Finsi

E.3 File d’attente à niveau de priorité

Une file d’attente à niveau de priorité est un ensemble

d’éléments tel qu’un niveau de priorité a été affecté chacun d’entre eux est
dont l’ordre dans lequel ils sont traits et traités obéit aux règles suivant :

Un élément de priorité supérieure est traité avant élément de

ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 58

priorité inférieure.

Deux éléments de même priorité sont traités selon l’un dans

lequel ils sont la insérés dans la file.

E.4 Deque

Une deque est une liste linéaire où les éléments peuvent être
ajoutés ou supprimés à l’un ou l’autre extrémité mais pas au milieu, c’est
donc une file d’attente à deux queues.

Une deque est généralement représentée en mémoire à l’aide

d’un tableau circulaire appelons le deque, muni des pointeurs « LEFT » et
« RIGHT » et « RIGHT » pointant sur Bs deux extrémités.

Il existe deux variantes des deques :

Deque à entrée restreinte : Qui n’accepte les entrées qu’à une seule de ses
extrémités (et les sorties) mais permet des
suppressions à ses deux extrémités.
Deque à sortie restreinte : Qui n’accepte des suppressions qu’a une seule des
ses extrémités mais permet des entrées à ses deux
extrémités.

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 59

F. ARBRE

Un arbre est une structure de données non linéaire qui est surtout
appliquée à des informations dont les éléments sont liés par des relations
hiérarchiques : ensemble des valeurs des champs relatives à une entité
donnée, table des matrices, index, etc.

F.1 Arbre binaire

Un arbre binaire T est un ensemble d’éléments appelés nœuds
tels que :
 T est vide, (dans ce cas il est appelé arbre nul ou arbre vide) ou
 T comporte un nœud particulier R appelé racine de T, et les autres
nœuds de T forment une paire ordonnée T1 et T2 d’arbres binaires
disjoints.

Dans le deuxième cas, T1 est appelé sous-arbre de gauche de R

et T2 est appelé sous-arbre de droite de R.

La racine de T1, si elle existe est appelée successeur gauche de

R, la racine de T2, si elle existe est appelée successeur droit de R.

Tout nœud d’un arbre binaire T possède deux successeurs au

maximum Tout nœud sans successeur est appelé nœud terminal ou feuille.

Soit X, un nœud, soient S1 et S2, successeurs de X, alors X est

appelé « parent » de S1 et S2,

 S1 est appelé «enfant gauche» de X,

 S2 est appelé «enfant droit» de X,
 S1 et S2 sont «des frères».
 Le segment de droite qui relie deux nœuds est appelé « arête ».
 Une séquence d’arêtes consécutives constitue un chemin.
 Un chemin qui se termine par une feuille (nœud terminal) est une
branche.

La profondeur (hauteur) d’un arbre T est le nombre maximum des

ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 60

nœuds dans une branche de T.

Deux arbres binaires T est V sont dits « similaires» s’ils ont la même
structure (la même forme).
Exemple l’Arbre START et l’Arbre START1

Deux arbres binaires T et V sont dits « copiés l’un de l’autre », s’ils

présentent le même contenu aux nœuds correspondants. C'est-à-dire s’ils
sont similaires et si les différents nœuds possèdent les mêmes valeurs.

F.2 Arbre binaire complet

Un arbre binaire est complet :

ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 61

 Si tous les niveaux, sauf éventuellement le dernier comportent le

nombre maximum des nœuds,
 Si tous les nœuds terminaux qui apparaissent au dernier niveau et qui
sont seuls sont à gauche.

START n’est pas un arbre binaire complet parce que le nœud se

trouvant à l’adresse 15 (P) a un seul enfant à droite au lieu qu’il soit à
gauche.

START1 n’est pas un arbre binaire complet parce que le nœud se

trouvant à l’adresse 9 (M) a un seul enfant à gauche alors que son frère se
trouvant à l’adresse 32 n’a pas encore d’enfant.

START2 est un arbre binaire complet.

F.3 Arbre binaire étendu (arbre pair)

Un arbre binaire est dit étendu ou pair si chaque nœud possède

ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 62

0 ou deux enfants, les nœuds dotés de deux enfants sont des nœuds internes
et ceux qui n’en possèdent pas sont des nœuds externes.

START2 n’est pas un arbre binaire complet parce que le nœud F

possède un seul enfant qui est N.

START est pas un arbre binaire complet parce que les nœuds A,
B, P et K possèdent deux enfants, tandis que les nœuds F, M, N, H, Q ne
possèdent aucun enfant.

Tout arbre binaire peut être transformé en arbre binaire étendu :

 En remplaçant chaque sous arbre vide par un nœud nouveau,
 En ajoutant deux nœuds externes aux nœuds terminaux.

Exemple : soit l’arbre binaire suivant

On demande de le rendre binaire étendu.

Les nœuds A et B possèdent chacun deux enfants. Le nœud P
possède une seul enfant à droite, il faut lui donne un deuxième enfant à
gauche. Les nœuds F, M, et H ne possèdent aucun enfant, par conséquent il

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 63

faut leurs donner chacun deux enfants l’un à gauche et l’autre à droite.

REMARQUE : Le nombre des nœuds nouveaux à ajouter correspond au

nombre des nœuds de l’arbre binaire plus un nœud.

F.4 Arbre binaire de recherche

Un arbre binaire est dit « arbre de recherche binaire » si chaque

nœud X est tel que :
1. La valeur du nœud X est supérieure à toute valeur
contenue dans le sous-arbre gauche de X,
2. La valeur du nœud X est inférieure à toute valeur contenue
dans le sous-arbre droit de X.
Exemple

F.5 Représentation en mémoire

1. Représentation chaînée d’un arbre binaire A. B

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 64

Cette représentation utilise trois tableaux parallèles appelons – les

« infos », « left », et « right » et un pointeur appelons – le « root ».

Ainsi chaque nœud n de l’arbre binaire T correspondra à une

adresse k telle que :
Info (k) contient l’information du nœud n,
Left (k) contient l’adresse de l’enfant gauche de n,
Right (k) contient l’adresse de l’enfant droit de n,
Root contient toujours l’adresse de la racine de T.

2. Représentation séquentielle d’un arbre binaire

Cette représentation utilise un tableau linéaire unique appelons

le « tree » dans lequel :
La racine R de l’arbre est rangée en tree (1),
Si un nœud occupe la place tree (k), alors son enfant gauche
est rangé en tree (2k) et son enfant droit est rangé en tree (2k + 1).

La profondeur d’un arbre binaire range de cette façon est :

(log2 n) + 1 (Avec n qui équivaut au nombre de nœuds)
La représentation séquentielle d’un arbre binaire de profondeur
d nécessite un tableau unique dont la taille 2d-1.

F.6 Opération

Parcours séquentiel
Recherche dans un arbre binaire
Recherche et insertion dans un arbre binaire
Suppression dans arbre binaire

Parcours séquentiel

Il existe trois parcours standardisés pour accéder

séquentiellement à un arbre binaire T de racine R.

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 65

PRE – ORDRE : Parcours où l’on exécute successivement les

opérations suivantes :
Traiter la racine R
Parcourir le sous- arbre gauche de R
Parcourir le sous– arbre droit de R

IN – ORDRE : Parcours où l’on exécute successivement les

opérations suivantes :
Parcourir le sous- arbre gauche de R
Traiter la racine R
Parcourir le sous- arbre droit de R

POST – ORDRE : Parcours où l’on exécute successivement les

opérations suivantes :
Parcourir le sous- arbre gauche de R
Parcourir le sous- arbre droit de R
Traiter la racine R

Les trois parcours sont essentiellement récursifs : Il faut donc

mettre en œuvre des piles pour leurs implémentations en mémoire.

Quel que soit le parcours, il est important de remarquer les

nœuds terminaux (feuilles) défilent dans le même ordre.

Algorithme de parcours « pré- ordre »

L’arbre est rangé en mémoire et une pile (STACK) est utilisée pour
stocker temporairement les adresses des nœuds.
PREORD (Info, Left, Right, Root)
Pile STACK(1 : n)
Top 1
STACK(Top) ASSISTANTNil ALI KOJ NGALANDO
P CONCEPTEUR DES SYSTEMES D’INFORMATION
Root
Tantque (P < > Nil) Faire
Traiter Info(P)
Si (Right(P) < > Nil) Alors Top Top + 1
 Cours d’Algorithmique II
G2 Informatique de Gestion 66

Algorithme de parcours “in- ordre”

L’arbre est rangé en mémoire et une pile (STACK) est utilisée pour
stocker temporairement les adresses des nœuds.

INORD (Info, Left, Right, Root)

Pile STACK(1 : n)
Top 1
STACK(Top) Nil
P Root
Tantque (P < > Nil) Faire
Top Top + 1
STACK(Top) P
P Left(P)
Fintantque
** P STACK(Top)
Top Top – 1
Tantque (P < > Nil) Faire
Traiter Info(P)
Si (Right(P) < > Nil) Alors P Right(P)
Aller à **
Finsi
P STACK(Top)
Top Top – 1
Fintantque
Algorithme de
Exitparcours post- ordre
L’arbre est rangé en mémoire et une pile (STACK) est utilisée pour
stocker temporairement les adresses des nœuds.

POSTORD (Info, Left, Right, Root)

Pile STACK(1 : n)
Top 1
STACK(Top) Nil
P Root ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
**Tantque (P < > Nil) Faire
Top Top + 1
STACK(Top) P
Si (Right(P) < > Nil) Alors Top Top + 1
 Cours d’Algorithmique II
G2 Informatique de Gestion 67

Exemple
Un arbre binaire T comporte neuf nœuds. Les parcours in- ordre et pré- ordre
sont :
In- ordre E A C K F H D B G
Pré- ordre F A E K C D H G B

Résolution

L’arbre T sera tracé de la manière suivante :

La racine de T est le premier nœud du parcours pré- ordonné, F.
Le parcours on- ordonné de T, fournit les nœuds du sous- arbre
gauche de F, c’est-à-dire EACK l’enfant gauche de F est alors déterminé en
choisissant le 1er nœud (parmi EACK) qui apparaît dans le parcours pré-
ordonné, c’est-à-dire A.
Le parcours in- ordonné de T, fournit les nœuds du sous- arbre
droit de F, c’est-à-dire HDBG l’enfant droit de F est alors déterminé en
choisissant le 1er nœud (parmi HDBG) qui apparaît dans le parcours pré-
ordonné, c’est-à-dire D.

Recherche dans un arbre de recherche binaire

ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 68

Soit x, une information.

Il s’agit de déterminer l’adresse loc. de x et l’adresse par du

parent de x.

FIND(Info,Left,
FIND(Info, Left,Right,
Right,Root,
Root,X,X,Loc,
Loc,Par)
Par)
Si(Root=Nil) Alors Loc Nil
Par Nil
Exit
Finsi
Si(X=Info(Root)) Alors Loc Nil
Par Nil
Exit
Finsi
Si(X<Info(Root)) Alors P Left(Root)
Left(Root)
Save Root
Root
Exit
Sinon P Right(Root)
Right(Root)
Save Root
Root
Finsi
Tantque(P< >Nil) Faire
Si(X=Info(P)) Alors Loc P
Par Save
Exit
Finsi
Si(X < Info(P)) Alors Save PP
P Left(P)
Left(P)
Sinon Save PP
P Right(P)
Right(P)
Finsi
Fintantque
Loc Nil Nil
Par SaveSave
Exit
Exit

Recherche et insertion dans un arbre binaire de recherche

Soit x, une information.
Il s’agit de trouver l’adresse de x ou de l’insérer en tant que
nœud nouveau dans cet arbre

INSBST(Info, Left, Right, Root, Avail, X, Loc)

FIND(Info, Left, Right, Root, X, Loc, Par)
Si(Loc < >ASSISTANT
Nil) Alors Exit
ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
Finsi
Si(Avail = Nil) Alors Ecrire ‘’Overflow’’
Exit
Finsi
 Cours d’Algorithmique II
G2 Informatique de Gestion 69

Suppression dans un arbre de recherche binaire

Soit x, une information.
La manière dont le nœud x est supprimé dépend du nombre
d’enfant de ce nœud x.

Trois cas possibles :

Cas 1 X n’a pas d’enfants

X est supprimé de l’arbre binaire T et l’adresse de X est remplacée par Nil
(dans le nœud parent de ce x).

Cas 2 X a un seul enfant

X est supprimé de l’arbre binaire T et l’adresse de X est remplacée par celle
de son enfant unique (dans le nœud de ce x).
Cas 3 X a deux enfants
Soit S(x) le successeur in- ordonné de X (ce qui signifie que S(x) n’a pas
d’enfant gauche), il faut alors :
Ecarter temporairement S(X)
Remplacer le nœud x par S(x)

Exemple :
In- ordonné 15 25 33 44 50 60 66 75

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 70

Pour supprimer 25, il faut supprimer temporairement 33 ; 44

devient le fils droit de S
Remplacer ensuite 25 par 33

Algorithme de suppression d’un nœud X à l’adresse Loc. Lorsque

X n’a pas deux enfants.
Par donne l’adresse du parent de X, si Par vaut Nil donc X est la racine

Child donne l’adresse de l’enfant unique de X, Child vaut Nil donc N n’a
pas d’enfant

CASE1(Info, Left, Right, Root, Loc, Par)

Si((Left(Loc) ==Nil)
Si(((Left(Loc) Nil)et
et(Right(Loc)
(Right(Loc)=Nil))
=Nil)))Alors
AlorsChild
Child NilNil
Sinon
Sinon
Si(Left(Loc)
Si(Left(Loc)
< ><Nil)
> Nil)
Alors
Alors
Child
Child Left(Loc)
Left(Loc)
Sinon Child Right(Loc)
FinsiFinsi
Finsi
Si(Par < > Nil) Alors
Si(Loc = Left(Par)) Alors Left(Par) ChildChild
Sinon Right(Par) Child
Finsi
Sinon
SinonRoot
Root Child
Child
Finsi
Return

Algorithme de suppression d’un nœud X à l’adresse loc. Lorsque

X possède deux enfants
Par donne l’adresse du parent de X
Suc donne l’adresse du successeur « in- ordonné » de X
Parsuc donne l’adresse du parent de ce successeur.

Algorithme formel de suppression de X :

CASE2(Info, Left, Right, Root, X, Loc, Par)

P Right(Loc)
Save Loc
Tantque(Left(P) < > Nil) Faire
Save PP
Left(P)
P Left(P)
Fintantque
CASE1(Info, Left, Right, Root, Suc, Parsuc)
Si(Par < >Nil) Alors
ASSISTANT
Si(Loc ALI KOJ
= Left(Par)) NGALANDO
Alors Left(Par) Suc
Suc
CONCEPTEUR DES SYSTEMES D’INFORMATION
Sinon Right(Par) Suc
Suc
Finsi
SinonRoot
Root SucSuc
Finsi
 Cours d’Algorithmique II
G2 Informatique de Gestion 71

Formellement l’algorithme de suppression de l’élément X en

intégrant les deux procédures CASE1 et CASE2 est le suivant :

DEL(Info, Left, Right, Root, Avail, X)

FIND(Info, Left, Right, Root, X, Loc, Par)
Si(Loc = Nil) Alors Ecrire X,‘’n’est pas sur l’arbre’’
Exit
Finsi
Si((Right(Loc) < > Nil) et (Left(Loc) < > Nil)) Alors CASE2(Info, Left, Right, Root, Loc, Par)
Sinon CASE2(Info, Left, Right, Root, Loc, Par)
Finsi
Left(Loc) Avail
Avail Loc
Exit

F.7 Arbre binaire ordonné

Soit H, un arbre complet à n éléments est dit arbre binaire

ordonné si tout nœud X de H possède une des propriétés suivantes :

La valeur de X est supérieur ou égale à celle de chacun de ses

enfants et par conséquent à celle de tous ses descendants (cas où l’arbre
binaire ordonné est appelé maxipile).

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 72

La valeur de X est inférieure ou égale à celle de chacun de ses

enfants et par conséquent à celle de tous ses descendants (cas où l’arbre
binaire est appelé minipile)

L’élément le plus grand d’une maxipile se trouve à la racine

Opération d’insertion dans une maxipile

Algorithme d’insertion
Soit X à insérer dans l’arbre ordonné T de n éléments rangé dans un tableau
TREE. P donne l’adresse Loc de X à mesure qu’il migre dans l’arbre et par
indique l’adresse du parent de X. nous aurons l’algorithme sera :

INSHEAP(TREE, n, X)
n n+1
P n
Tantque(P < 1) Faire
Par P\2
Si(X < =TREE(Par)) Alors TREE(Par) X
Return
ASSISTANT
Finsi ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
TREE(P) TREE(Par)
P Par
Fintantque
TREE(1) X
 Cours d’Algorithmique II
G2 Informatique de Gestion 73

Opération de suppression dans une maxipile

Algorithme de suppression. Soit X à supprimer dans l’arbre ordonné T de n
éléments rangé dans un tableau TREE. La
variable LAST sauvegarde la valeur du nœud L
originellement dernier nœud de T.
P donne l’adresse de LAST, Left l’adresse de son enfant gauche et Right celui
de son enfant droit.
Il faut : Affecter la racine X à Y
Remplacer X par le dernier nœud L de T
Réordonner T
DELHEAP(TREE, n, X)
X TREE(1)
LAST TREE(n)
n n–1
P 1
Left 2
Right 3
Tantque(Right < = n) Faire
Si(LAST > = TREE(Left)) et (LAST > = TREE(Right)) Alors TREE(P) LAST
Return
Finsi
Si(TREE(Right) < = TREE(Left)) Alors TREE(P) TREE(Left)
P Left
Sinon TREE(P) TREE(Right)
P Right
Finsi
Left 2*P
Right Left + 1
Fintantque
Si(Left=n) et (LAST < TREE(Left)) Alors P Left
Finsi
TREE(P) LAST
Return

Tri vertical (HEAPSORT) HEAP = TAS

Soit un tableau A à n éléments. Pour procéder au tri, il faut :
Bâtir un arbre ordonné avec les éléments de A, et
Supprimer la racine de A de manière répétitive

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 74

HEAPSORT(A, n)
J 1
Tantque( J< = n-1) Faire
INSHEAP(A, J, A(J+1))
J J+1
Fintantque
Tantque(n > 1) Faire
DELHEAP(A, n, X)
A(n+1) X
Fintantque
Exit

Pour la construction de l’arbre ordonné remarquons que le

nombre des comparaisons nécessaire pour déterminer une place appropriée
pour un élément nouveau ne peut excéder la profondeur de l’arbre qui est
de (log n).
Le temps pour insérer n éléments est donc de l’ordre de θ (n log n).

Pour la suppression répétitive de la racine, remarquons que c’est

l’opération de réarrangement de l’arbre qui est essentielle : cette opération
fait appelle à quatre comparaisons pour déplacer le nœud qui a remplacé
la racine le long de l’arbre.

Pour déplacer les n éléments le temps maximal est proportionnel

à θ 4nlog n.
La complexité du tri vertical (HEAPSORT) est donc de l’ordre de θ
(n log n).

F.8 Arbre généralisé

Un arbre généralisé (ou arbre tout court) est un ensemble non

vide des nœuds ayant :
 un nœud particulier appelé racine et
 des sous arbres disjoints T1, T2, … Tn
ASSISTANT ALI KOJ NGALANDO
CONCEPTEUR DES SYSTEMES D’INFORMATION
 Cours d’Algorithmique II
G2 Informatique de Gestion 75

Dans un arbre généralisé il n’y a ni enfant gauche ni enfant droit.

Ainsi les arbres T1 et T2 :

T1 T2
A A

B B

C D C D

Considérés comme des arbres binaires ces deux arbres sont

différents mais considérés comme des arbres généralisés les deux arbres sont
identiques.
Généralement un arbre généralisé T sera représenté en mémoire
sous forme d’une représentation chaînée à trois tableaux parallèles « Info »,
« Child », et « Sibl ».

Chaque nœud X de T correspond à une adresse k telle que :

Info (k) contient l’information du nœud X,
Child (k) contient la position du 1er enfant de X et
Sibl (k) contient l’adresse du prochain frère de X.

ASSISTANT ALI KOJ NGALANDO

CONCEPTEUR DES SYSTEMES D’INFORMATION