REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE

MINISTERE DE L’ENSEIGNEMENT SUPERIEUR ET DE LA RECHERCHE SCIENTIFIQUE

ECOLE NATIONALE SUPERIEURE D’INFORMATIQUE

CPI 1 Année 2019 / 2020

TP
EN ALGORITHMIQUE ET
STRUCTURES DE DONNEES
STATIQUES (ALSDS)

REALISE PAR :
BENNOUR Salah Eddine Hamza
DJELLAL Meriem

Section : A
Groupe N° : 02

Semestre 1
ESI-CPI-Rapport de TP

SOMMAIRE
1 Introduction ......................................................................................................................................... 4

2 L’énoncé .............................................................................................................................................. 4

3 La solution ........................................................................................................................................... 5

3.1 Le découpage modulaire et la justification .................................................................................... 5

3.1.1 La justification : .................................................................................................................... 5

3.2 Construction de l’algorithme principal et ses modules : ................................................................. 7

3.2.1 Le module Tri_panier ........................................................................................................... 7

3.2.1.1 L’analyse .......................................................................................................................... 7

3.2.1.2 L’algorithme ..................................................................................................................... 7

3.2.1.3 Le déroulement ................................................................................................................. 8

3.2.1.4 Le programme................................................................................................................... 8

3.2.1.5 Le résultat du jeu d’essai ................................................................................................... 9

3.2.2 Le module Panier .................................................................................................................. 9

3.2.2.1 L’analyse .......................................................................................................................... 9

3.2.2.2 L’algorithme ..................................................................................................................... 9

3.2.2.3 Le déroulement ................................................................................................................10

3.2.2.4 Le programme..................................................................................................................10

3.2.2.5 Le résultat du jeu d’essai ..................................................................................................10

3.2.3 Le module Rang_tab ............................................................................................................10

3.2.3.1 L’analyse .........................................................................................................................10

3.2.3.2 L’algorithme ....................................................................................................................11

3.2.3.3 Le déroulement ................................................................................................................12

3.2.3.4 Le programme..................................................................................................................12

3.2.3.5 Le résultat du jeu d’essai ..................................................................................................12

3.2.4 Le module Rechdich ............................................................................................................13

3.2.4.1 L’analyse .........................................................................................................................13

3.2.4.2 L’algorithme ....................................................................................................................13

Réalisé par : BENNOUR-DJELLAL-G02 2
ESI-CPI-Rapport de TP

3.2.4.3 Le déroulement ................................................................................................................14

3.2.4.4 Le programme..................................................................................................................14

3.2.4.5 Le résultat du jeu d’essai ..................................................................................................14

3.2.5 Le module rechseq ...............................................................................................................14

3.2.5.1 L’analyse .........................................................................................................................14

3.2.5.2 L’algorithme ....................................................................................................................15

3.2.5.3 Le Déroulement ...............................................................................................................15

3.2.5.4 Le programme..................................................................................................................16

3.2.5.5 Le résultat du jeu d’essai ..................................................................................................16

3.2.6 L’algorithme principal .........................................................................................................16

3.2.6.1 L’analyse .........................................................................................................................16

3.2.6.2 L’algorithme ....................................................................................................................17

3.2.6.3 Le déroulement ................................................................................................................18

3.2.6.4 Le programme..................................................................................................................18

3.2.6.5 Le jeu d’essai ...................................................................................................................19

4 Conclusion ..........................................................................................................................................20

Réalisé par : BENNOUR-DJELLAL-G02 3

ESI-CPI-Rapport de TP

1 Introduction
L’informatique est un domaine spécialisé dans le traitement automatique de l’information et
l’organisation des bases de données, c’est un domaine où le traitement de l’information est plus important
que l’information elle-même, d’où la nécessité d’un ensemble de moyens pour gérer ces données (tel que les
tableaux) : les algorithmes de tri permettant, comme indique leur nom, de faire un tri d’une collection
d’objets selon une relation prise. On en distingue plusieurs: le tri par bulle, par insertion, par transposition, tri
par comptage (en utilisant trois tables, deux tables et une table) et tri par paniers.

On peut aussi rechercher des valeurs dans une structure statique (tableaux) en utilisant deux types de
recherche : une recherche séquentielle qui s’établit sur un tableau quelconque et une recherche dichotomique
qui s’applique essentiellement sur des tableaux ordonnés (triés déjà auparavant).

2 L’énoncé
Tri par paniers et recherche séquentielle et dichotomique dans un tableau à une dimension.

2.1 Données du problème :

 Nous allons réaliser le tri par paniers et calculer le nombre d’itérations en recherchant des éléments
selon la recherche séquentielle et dans un tableau trié selon la recherche dichotomique.

Principe tri par paniers :

 On détermine le minimum et le maximum d’un tableau.

 On crée autant de paniers qu’il y a de nombre entre min et max (max – min +1).

 Construction de la table triée en prenant à chaque fois le nombre des éléments de chaque
panier par ordre.

Principe de la recherche séquentielle : Parcourir séquentiellement le tableau, jusqu’à trouver l’élément

Principe de la recherche dichotomique : (sur des tableaux triés)

 Se positionner sur la moitié du tableau (la case du milieu du tableau), et en

comparant la valeur recherchée avec l’élément du milieu, on peut déduire de quel
côté se trouve la valeur recherchée (à droite, à gauche ou au milieu).

 Et on répète le processus à chaque fois sur le nouveau tableau car on diminue la

taille du tableau initial et soit on trouve la valeur ou on constate qu’elle n’existe
pas.

2.2 Travail demandé :

1. Construction du tri par paniers.

2. Remplissage d’un tableau de 50000 éléments entiers par des valeurs aléatoires comprises entre 1 et
30000.

Réalisé par : BENNOUR-DJELLAL-G02 4

ESI-CPI-Rapport de TP

3. Calcul du nombre d’itérations nécessaires pour le tri par panier

4. Donnons les résultats (positon, nombre d’itérations) selon les deux types de recherche.

5. Conclusion sur les résultats observés.

3 La solution
3.1 Le découpage modulaire et la justification
3.1.1 La justification :
Nous aurons besoin des modules suivants :

 Tri_panier : pour faire le tri d’un tableau à une dimension par la méthode de paniers (construire le tri
par paniers) ce dernier comportera les modules :

 Panier : pour créer un tableau à partir d’un autre et dont chaque élément contient la fréquence
d’apparition de l’indice de cet l’élément dans l’autre tableau.

 Rangtab : qui va construire un tableau T2 à partir de T1 en rangeant chaque indice i de T1 dans

T2 un nombre de fois qui est égal au contenu de T1 à i et cela afin de construire la table triée à
partir de la table de paniers.

 Rechdich : rechercher une valeur dans le tableau trié.

 Rechseq : rechercher une valeur dans le tableau (trié ou non).

Procédure

Var X : tab

Tri_panier

Taille : entier

Rôle : Trier un tableau à une seule dimension

d’entiers par la méthode de paniers.

Procédure

X : TAB VAR P : TAB

Panier

Taille : ENTIER VAR tai : entier

Réalisé par : BENNOUR-DJELLAL-G02 5
ESI-CPI-Rapport de TP

Rôle : Créer des paniers selon les valeurs comprises entre

Petit et grand dans la table X et dont chaque panier N comporte

La fréquence d’apparition de N dans X.

Procédure

P : TAB VAR T : TAB

Rang_tab

Tai : ENTIER VAR taille : ENTIER

Rôle : Construire une table T à partir de P en commençant

par ranger l’élément i (P[i] fois) dans T puis i+1 (p [i+1] fois)

dans T et ainsi de suite.

Procédure

Val : entier VAR existe : Booléen

Taille : entier Rechdich VAR pos : entier

X : TAB VAR iter : entier

Rôle : Rechercher la valeur Val dans le tableau X (trié) par

la méthode dichotomique en se plaçant dans la moitié de X puis

dans la moitié du coté ou se trouve Val et ainsi de suite jusqu’à

trouver (ou pas) Val, dans ce cas elle renvoie vrai, le nombre d’itération, et la

position de la première case trouvée contenant l’élément cherché.

Procédure

Val : ENTIER VAR existe : Booléen

Taille : ENTIER Rechseq VAR pos : ENTIER

X : TAB VAR iter : ENTIER

Réalisé par : BENNOUR-DJELLAL-G02 6

ESI-CPI-Rapport de TP

Rôle : Rechercher la valeur Val dans le tableau X par

la méthode séquentielle qui consiste en parcourant case

par case à partir de la première case jusqu’à trouver (ou pas)

l’élément recherché, dans ce cas elle renvoie vrai, le nombre d’itération, et la

position de la première case trouvée contenant l’élément cherché.,

Sinon trouve prend la valeur faux, pos et iter prennent la valeur 0.

3.2 Construction de l’algorithme principal et ses modules :

3.2.1 Le module Tri_panier

3.2.1.1 L’analyse
 Construire le tableau de paniers P (en calculant Panier (Taille, X, P, Tai)). //utilisation du
module panier

 Calculer Rang_tab (Tai, P, T, Tail) afin de ranger les numéros de paniers P selon leurs jetons
dans T. //utilisation du module Rang_tab

 Mettre le contenu de T dans X.

3.2.1.2 L’algorithme

PROCEDURE TRI_PANIER (Taille : ENTIER ; VAR X : TAB)

Variables P : TAB

Tai, Tail, i: ENTIER

Réalisé par : BENNOUR-DJELLAL-G02 7

ESI-CPI-Rapport de TP

Procédures Panier, Rang_tab

DEBUT

Panier (Taille, X, P, Tai)

Rang_tab (Tai, P, T, Tail)

Pour i allant de 1 à Tail faire X[i] ← T[i]

FIN

3.2.1.3 Le déroulement
Si on introduit un tableau de taille 10 comme ceci :

I 1 2 3 4 5 6 7 8 9 10

X[i] 55 60 72 85 61 86 55 85 43 63

Le tableau après le tri :

I 1 2 3 4 5 6 7 8 9 10

X[i] 43 55 55 60 61 63 72 85 85 86

3.2.1.4 Le programme

Réalisé par : BENNOUR-DJELLAL-G02 8

ESI-CPI-Rapport de TP

3.2.1.5 Le résultat du jeu d’essai

3.2.2 Le module Panier

3.2.2.1 L’analyse
Pour ce module on aura besoin des modules suivants :

 Max (Tail, X) // Donne le plus grand élément du tableau X à une dimension de taille Tail

 Freqnbt (i, Tail, X) // Calculer la fréquence de l’élément i dans le tableau X à une dimension

- Si le plus grand élément est nul alors le tableau de paniers est nulle (Le tableau ne contient pas d’éléments
nuls dans notre cas).

- On varie i de 1 à max (taille, X) et à chaque itération on met freqnbt (i, Taille, X) dans P[i] (la fréquence
d’apparition de i dans X), la taille de P est la valeur maximum de X (max (Taille, X)).

3.2.2.2 L’algorithme

PROCEDURE PANIER (Taille : ENTIER ; X : TAB ; VAR P : TAB ; VAR tai : ENTIER)

Variables i : ENTIER

Fonctions max, freqnbt

DEBUT

SI max (taille, x)=0 alors tai← 0

SINON

DSI

Pour i allant de de 1 à max (taille, x) faire P[i] ← freqnbt (i, taille, x)

Tai ← max (taille, x)

FSI

FIN

Réalisé par : BENNOUR-DJELLAL-G02 9

ESI-CPI-Rapport de TP

3.2.2.3 Le déroulement
Si on introduit X comme ceci : (taille =20)

I 1 2 3 4 5 6 7 8 9 10

X[i] 11 12 15 17 13 18 11 17 9 13

Le tableau de paniers :

I 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

X[i] 0 0 0 0 0 0 0 0 1 0 2 1 2 0 1 0 2 1

3.2.2.4 Le programme

3.2.2.5 Le résultat du jeu d’essai

3.2.3 Le module Rang_tab

3.2.3.1 L’analyse
Pour ce module on aura besoin des modules suivants :

 Max (Tail, X)// Donne le plus grand élément du tableau X à une dimension de taille Tail

 Frenbt (i, Tail, X)// Calculer la fréquence de l’élément i dans le tableau X à une dimension

Réalisé par : BENNOUR-DJELLAL-G02 10

ESI-CPI-Rapport de TP

- On met 0 dans ind// (c’est l’indice du tableau)

- On varie i de 1 à tai et à chaque itération :

o On met 0 dans K

o Et tant que la condition k < P[i] reste vérifiée on répète le processus suivant :

 On incrémente k

 On incrémente ind

 On met i dans T[i]

(Ce bloc est pour assurer le rangement de i dans un nombre de cases égales à P[i])

o On met ind dans tail (c’est la taille du tableau obtenu)

3.2.3.2 L’algorithme

PROCEDURE Rang_tab (Tai : ENTIER ; P : TAB ; VAR T : TAB ; VAR tail : ENTIER)

Variables i, j, k, Ind: ENTIER

Fonctions max, freqnbt

DEBUT

Ind ← 0

Pour i allant de 1 à tai faire

DPOUR

k←0

Tant que k < P[i] faire

DTQ

k ← k+1

ind ← ind +1

T[ind] ← i

FTQ

FPOUR

Tail ← ind

FIN

Réalisé par : BENNOUR-DJELLAL-G02 11

ESI-CPI-Rapport de TP

3.2.3.3 Le déroulement
Le tableau initial :

i 1 2 3 4 5 6 7 8 9 10

T[i] 7 7 8 10 7 10 6 10 5 7

La table des paniers :

i 1 2 3 4 5 6 7 8 9 10

P[i] 0 0 0 0 1 1 4 1 0 3

Le tableau trié :

i 1 2 3 4 5 6 7 8 9 10

T ' [i] 5 6 7 7 7 7 8 10 10 10

3.2.3.4 Le programme

3.2.3.5 Le résultat du jeu d’essai

Réalisé par : BENNOUR-DJELLAL-G02 12

ESI-CPI-Rapport de TP

Le module Rechdich

3.2.3.6 L’analyse
 On met 1 dans j (c’est la plus petite case), taille dans i (c’est la plus grande case).

 On met FAUX dans existe et 0 dans iter

 On se positionne sur la moitié du tableau (la case du milieu du tableau) //on calcule l’indice du
centre du tableau ind= (i+j)/2

 Si X[ind] = Val (la case contient l’élement recherché) on met vrai dans existe ( ind dans pos)

 Sinon si val<T[ind] alors i=ind-1 (Val de se trouve à gauche) sinon val se trouve à droite j=ind+1 on
répète le processus précédent jusqu’à trouver Val ou parcourir tout le tableau(0 dans pos) .

3.2.3.7 L’algorithme

PROCEDURE Rechdich (Val, Taille : ENTIER ; X : TAB ; VAR existe : Booléen ;

VAR pos : ENTIER ; VAR iter : ENTIER)

Variables ind, j, k : ENTIER

DEBUT

j←1

i ← taille

existe ← FAUX

iter ← 0

Répéter

Iter ← iter+1

Ind ← (i+j) div 2

SI Val= X[ind] alors existe ← VRAI

SINON SI Val> X[ind] alors j ← ind +1

SINON i ← ind – 1

Jusqu’à (existe = VRAI) ou (i < j)

SI existe = FAUX alors pos ← 0

SINON pos ← ind

Réalisé par : BENNOUR-DJELLAL-G02 13

ESI-CPI-Rapport de TP

3.2.3.8 Le déroulement
Pour un tableau de taille de 20 cases :

I 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

X[i] 6 28 30 39 39 43 44 48 55 55 60 61 63 65 72 85 85 86 90 97

La variable Taille Val existe pos Iter

La valeur 20 55 VRAI 10 1

3.2.3.9 Le programme

3.2.3.10 Le résultat du jeu d’essai

3.2.4 Le module rechseq

3.2.4.1 L’analyse
 On met faux dans existe

 On met 0 dans dans pos et 0 dans iter

 On repète le processus suivant jusqu’à trouver la valeur Val ou arriver à l’extrémité du tableau
Réalisé par : BENNOUR-DJELLAL-G02 14
ESI-CPI-Rapport de TP

Si X[iter] = Val //la case contient l’élément cherché

- On met iter dans pos, VRAI dans existe

3.2.4.2 L’algorithme

PROCEDURE Rechseq (Val, Taille : ENTIER ; X : TAB ; VAR existe : Booléen ;

VAR pos : ENTIER ; VAR iter : ENTIER)

DEBUT

Existe ← FAUX

Iter ← 0

Pos ← 0

Répéter iter ← iter +1

SI X[iter] = Val alors

DSI

Pos ← iter

Existe ← VRAI

FSI

Jusqu’à (X[iter]=Val) OU (iter = taille)

FIN

3.2.4.3 Le Déroulement
Pour un tableau de taille de 20 cases :

I 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

X[i] 6 6 8 9 7 9 6 9 5 7 7 4 5 3 9 1 10 3 4 5

La variable Taille Val existe pos Iter

La valeur 20 7 VRAI 5 5

Réalisé par : BENNOUR-DJELLAL-G02 15

ESI-CPI-Rapport de TP

3.2.4.4 Le programme

3.2.4.5 Le résultat du jeu d’essai

3.2.5 L’algorithme principal

3.2.5.1 L’analyse
On aura besoin des module suivants :

Min (tai : entier, T : tab) : entier//donne le plus petit élément du tableau T à une dimension de taille tai

Max (tai : entier, T : tab) : entier//donne le plus grand élément du tableau T à une dimension de taille tai

Remp_alea (tai : entier, val_max : entier, var T : tab)//remplir un tableau par des valeurs aléatoires
comprises entre [0, val_max] à partir de la fonction standard random
 On remplit un tableau T par des valeurs aléatoires //en utilisant le module Remp_alea

 Puis on tri le tableau T//en utilisant le module Tri_panier

 Puis on calcule le nombre d’itérations nécessaires pour trier le tableau T en utilisant le tri par
paniers // utilisation des modules min et max //par la formule suivante : max(T)-min(T) +1

 On fait varier i //l’indice du tableau T de 1 à 6//

o En utilisant la fonction standard on donne à val (valeur recherchée) des valeurs aléatoires
//RANDOM

o On cherche val en utilisant les modules Rechdich et Rechseq

Réalisé par : BENNOUR-DJELLAL-G02 16

ESI-CPI-Rapport de TP

3.2.5.2 L’algorithme
ALGORITHME TP2

TYPE TAB= TABLEAU [1..60000] d’entiers

VARIABLES X: TAB; i, j, nb, pos, iter: ENTIERS; Trouve : Booléen

Remp_alea, Tri_panier, Max, Min, Rechdich, Rechseq

DEBUT

Remp_alea (30000, 50000, X)

Tri_panier (50000, X)

Nb ← max (50000, X) – min (50000, X) +1

ECRIRE (‘Le d’itérations pour faire le tri est’, Nb)

ECRIRE (‘Par recherche dichotomique : ’)

Pour i allant de 1 à 6 faire

DPOUR

j ← Random (30000)

Rechdich (j, 50000, X, Trouve, pos, iter)

SI Trouve alors ECRIRE ( ‘Le nombre : ’, j,’, La position : ’, pos,’, Le nombre

D’itérations : ’, iter)

SINON ECRIRE (‘ Le nombre ’,j,’ est introuvable’)

FPOUR

ECRIRE (‘Par recherche séquentielle’)

Pour i allant de 1 à 6 faire

DPOUR

j ← Random (30000)

Rechseq (j, 50000, X, Trouve, pos, iter)

SI Trouve alors ECRIRE ( ‘Le nombre : ’, j,’, La position : ’, pos,’, Le nombre

d’itérations : ’, iter)

SINON ECRIRE(‘ Le nombre ’,j,’ est introuvable’)

FPOUR

FIN

Réalisé par : BENNOUR-DJELLAL-G02 17

ESI-CPI-Rapport de TP

3.2.5.3 Le déroulement
Par la recherche dichotomique :

Le nombre 26436 14177 15936 25724 26041 1646

Pos, iter 44023, 13 / 26598, 12 / 43368, 14 /

Par la recherche séquentielle :

Le nombre 23326 5676 29079 3676 27771 27963

Pos (= iter) 38866 9590 48508 6257 46316

3.2.5.4 Le programme

Réalisé par : BENNOUR-DJELLAL-G02 18

ESI-CPI-Rapport de TP

3.2.5.5 Le jeu d’essai

Réalisé par : BENNOUR-DJELLAL-G02 19

ESI-CPI-Rapport de TP

4 Conclusion
 Sur l’échelle pédagogique, psychologique :

Le travail en binôme, nous développe l’esprit de la coopération, du dialogue et de la discussion et nous

enseigne comment exprimer notre opinion et même à se mettre d’accord sur une solution en acceptant l’avis
d’autrui.

Il nous enseigne aussi comment contrôler le temps (La gestion de temps) et comment se partager les tâches.

 Sur l’échelle éducative :

L’algorithme tri par paniers est simple ainsi qu’il est peu efficace à cause de sa complexité, notamment le
coût d’opérations (nombre d’itérations).

D’autre part, on constate que l’algorithme de la recherche dichotomique est beaucoup plus important que
celui de la recherche séquentielle par la mesure de la complexité des algorithmes d’où l’efficacité.

Egalement une propriété importante de la recherche dichotomique car ne s’applique que sur une collection
d’objets (tableau) triés vu la cohérence et l’enchainement de son principe en effet on procède par élimination
contrairement à la recherche séquentielle qui s’applique sur un tableau quelconque.

Réalisé par : BENNOUR-DJELLAL-G02 20