UNIVERSITE IBN ZOHR
FACULTE DES SCIENCES APPLIQUEES
COMPUS UNIVERSITAIRE AIT MELLOUL
Informatique
FILIÈRE : IA - S2
ALGORITHMIQUE 2
ANNÉE U N I V ERSI TA IRE : 2 0 2 3- 2024
Pr. oulad sayad younes [Link]@[Link]
PLAN
Chapitre 1 : Notions de base en Algorithmique
Chapitre 2 : Les instructions itératives
Chapitre 3 : La Récursivité
Chapitre 4 : La Recherche dans un tableau
Chapitre 5 : Tri des éléments d’un tableau
Chapitre 6 : La complexité
Pr. oulad sayad younes 2
CHAPITRE 4 :
La Recherche dans un
tableau
Pr. oulad sayad younes 3
Rappel sur Les Tableaux
Pr. oulad sayad younes 4
Définition
• Un TABLEAU (ou VECTEUR) est une
juxtaposition, sous un NOM UNIQUE, d’un certain
nombre de VARIABLES DE MEME TYPE.
Chaque variable porte le même nom mais est unique
grâce à son rang.
Pr. oulad sayad younes
5
Déclaration
• En pseudo code :
variable tableau identificateur[dimension] : type
identificateur : nom donné au tableau (= à chacune des variables qui le
composent)
dimension : nombre de variables du tableau (l’indice est alors compris entre 1
et nbre_elements)
type : type de données des variables composant le tableau
liste_de_valeurs : valeurs données à chacun des éléments du tableau
Pr. oulad sayad younes
6
Déclaration
• Exemples : déclaration
- VARIABLE TABLEAU note[6] : ENTIER
Pr. oulad sayad younes
7
Accès aux éléments d’un tableau
Exemple :
VARIABLE TABLEAU temperature[12] : ENTIER
Ecrire(temperature[8])
Pr. oulad sayad younes 8
Saisie et affichage d’un tableau
Algorithme qui permet de saisir et d'afficher les éléments d'un tableau de 30
notes:
Pr. oulad sayad younes 9
Dimensions, tableaux multi
dimensionnels
• La DIMENSION correspond à un nombre d’imbrications de
tableaux, chaque élément d’un tableau pouvant être composé d’un
autre tableau, etc.
• On parle de « tableau MULTI-DIMENSIONNEL » (à plusieurs
dimensions).
Pr. oulad sayad younes
10
Dimensions, tableaux multi
dimensionnels
Syntaxe tableau à 2 dimensions :
variable tableau identificateur[dimension1] [dimension2] : type
• Exemple : une matrice A de 3 lignes et 4 colonnes dont les
éléments sont réels
variable tableau A[3][4] : Réel
• A[i][j] permet d'accéder à l’élément de la matrice qui se trouve
à l’intersection de la ligne i et de la colonne j
Pr. oulad sayad younes
11
Dimensions, tableaux multi
dimensionnels
Exemple : tableau de températures de 2 ans, 12 mois par an
variable tableau temperature[2][12] : Entier
Dans un tableau à 2 dimensions, on pourra mémoriser
« elem1 » X « elem2 » valeurs.
Pr. oulad sayad younes
12
Accès aux tableaux multi
dimensionnels
L’ACCES A UN ELEMENT D’UN TABLEAU A PLUSIEURS DIMENSIONS
NECESSITE AUTANT D’INDICES QUE DE DIMENSIONS.
Pr. oulad sayad younes
13
Exemple : lecture d’une matrice
Algorithme qui permet de saisir les éléments d'une matrice de vingt lignes et
cinquante colonnes:
Pr. oulad sayad younes 14
Exemple : affichage d’une matrice
Algorithme qui permet d'afficher les éléments d'une matrice de vingt lignes et
cinquante colonnes:
Pr. oulad sayad younes 15
Tableaux Accès Parcours Recherche Tri
Problème de la recherche
Données : un tableau de n entiers naturels distincts, et une valeur v à trouver.
Résultat : si le tableau contient un élément de valeur v , alors afficher l’index de cet
élément ; sinon afficher "échec".
Algorithme de recherche
Le problème est de trouver un élément dans une structure linéaire (tableau).
- l'élément peut ne pas être présent
- l'élément peut être présent à plusieurs endroits
- si la structure a plusieurs dimensions, il faut fouiller chaque dimension
Technique intuitive : la recherche séquentielle
- on parcourt la structure dans l'ordre « naturel »
- on s'arrête au bout, ou quand on trouve l'élément
- parfois on peut s'arrêter plus tôt
Algorithmique et Programmation 2
Tableaux Accès Parcours Recherche Tri
Recherche séquentielle
Rechercher dans un tableau non trié
variables
entier notes[5] ← {18, 15, 10, 12, 14}
entier i, valeur
booléen trouvé
début
lire valeur
i ←0
répéter
trouvé ← notes[i] = valeur
i ← i +1
jusqu’à trouvé ou i = 5
si trouvé alors
afficher i − 1
sinon
afficher "échec"
fin
fin
Tableaux Accès Parcours Recherche Tri
Recherche séquentielle
Rechercher dans un tableau non trié
variables
entier notes[5] ← {18, 15, 10, 12, 14}
entier i, valeur
booléen trouvé notes
18 15 10 12 14
début 0 1 2 3 4
lire valeur
i ←0
répéter
trouvé ← notes[i] = valeur ? ? ?
i ← i +1 i valeur trouvé
jusqu’à trouvé ou i = 5
si trouvé alors
afficher i − 1
sinon Déclaration des variables
afficher "échec"
fin
fin
Tableaux Accès Parcours Recherche Tri
Recherche séquentielle
Rechercher dans un tableau non trié
variables
entier notes[5] ← {18, 15, 10, 12, 14}
entier i, valeur
booléen trouvé notes
18 15 10 12 14
début 0 1 2 3 4
lire valeur
i ←0
répéter
trouvé ← notes[i] = valeur 0 10 ?
i ← i +1 i valeur trouvé
jusqu’à trouvé ou i = 5
si trouvé alors
afficher i − 1
sinon Initialisation des variables
afficher "échec"
fin
fin
Tableaux Accès Parcours Recherche Tri
Recherche séquentielle
Rechercher dans un tableau non trié
variables
entier notes[5] ← {18, 15, 10, 12, 14}
entier i, valeur
booléen trouvé notes
18 15 10 12 14
début 0 1 2 3 4
lire valeur
i ←0
répéter
trouvé ← notes[i] = valeur 1 10 faux
i ← i +1 i valeur trouvé
jusqu’à trouvé ou i = 5
si trouvé alors
afficher i − 1
sinon Fin de la 1ère itération
afficher "échec"
fin
fin
Tableaux Accès Parcours Recherche Tri
Recherche séquentielle
Rechercher dans un tableau non trié
variables
entier notes[5] ← {18, 15, 10, 12, 14}
entier i, valeur
booléen trouvé notes
18 15 10 12 14
début 0 1 2 3 4
lire valeur
i ←0
répéter
trouvé ← notes[i] = valeur 2 10 faux
i ← i +1 i valeur trouvé
jusqu’à trouvé ou i = 5
si trouvé alors
afficher i − 1
sinon Fin de la 2ème itération
afficher "échec"
fin
fin
Tableaux Accès Parcours Recherche Tri
Recherche séquentielle
Rechercher dans un tableau non trié
variables
entier notes[5] ← {18, 15, 10, 12, 14}
entier i, valeur
booléen trouvé notes
18 15 10 12 14
début 0 1 2 3 4
lire valeur
i ←0
répéter
trouvé ← notes[i] = valeur 3 10 vrai
i ← i +1 i valeur trouvé
jusqu’à trouvé ou i = 5
si trouvé alors
afficher i − 1
sinon Fin de la 3ème itération
afficher "échec"
fin
fin
Tableaux Accès Parcours Recherche Tri
Recherche séquentielle
Rechercher dans un tableau non trié
variables
entier notes[5] ← {18, 15, 10, 12, 14}
entier i, valeur
booléen trouvé notes
18 15 10 12 14
début 0 1 2 3 4
lire valeur
i ←0
répéter
trouvé ← notes[i] = valeur 3 10 vrai
i ← i +1 i valeur trouvé
jusqu’à trouvé ou i = 5
si trouvé alors
afficher i − 1
sinon i < 5 donc le programme retourne 2
afficher "échec"
fin
fin
Divide ut imperes
Principe diviser pour régner : on découpe les données en différentes parties qu'on
traite séparément.
Exemple : pour rechercher un élément dans un tableau, on le coupe en deux et
on chercher dans chaque partie.
'a' 'c' 'c' 'd' 'f' 'm' 'n' 'p' 'v' 'x'
'a' 'c' 'c' 'd' 'f' 'm' 'n' 'p' 'v' 'x'
Ce principe est utile :
- si on peut lancer des programmes en parallèle, on mettra environ deux fois
moins de temps pour rechercher l'élément.
- si le tableau est trié, on peut ne chercher l'élément que dans une seule des
parties.
Algorithmique et Programmation 6
Recherche dichotomique
Recherche par dichotomie : le tableau est supposé trié par ordre croissant et on
cherche un élément e dans un tableau t
Principe de l'algorithme :
0- on regarde l'élément situé au milieu de t :
1- s'il s'agit de e c'est gagné.
2- s'il est plus grand que e, on cherche dans la moitié gauche
3- s'il est plus petit que e, on cherche dans la moitié droite
Remarques :
- ça ne peut marcher que si le tableau est trié
- on coupe le tableau en deux parties pas forcément égales en taille
Algorithmique et Programmation 7
Recherche dichotomique
Exemple : rechercher 490 dans le tableau d'entiers suivant.
121 568 569 701
4 17 25 26 45 45 87 102 234 237 490
3 1 0 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
121 568 569 701
4 17 25 26 45 45 87 102 234 237 490
3 1 0 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
121 568 569 701
4 17 25 26 45 45 87 102 234 237 490
3 1 0 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
121 568 569 701
4 17 25 26 45 45 87 102 234 237 490
3 1 0 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Remarque : on trouve 490 en 4 itérations, une recherche séquentielle aurait
demandé 11 itérations
Algorithmique et Programmation 8
Tableaux Accès Parcours Recherche Tri
Recherche dichotomique
60
Supposons que l’on ait un grand tableau d’éléments triés du plus
petit au plus grand. On cherche la valeur 60 dans le tableau.
Tableaux Accès Parcours Recherche Tri
Recherche dichotomique
60
81
On commence par regarder le milieu du tableau.
Tableaux Accès Parcours Recherche Tri
Recherche dichotomique
60
81
Comme la valeur recherchée est plus petite que 81 on re-
lance la recherche dans la moitié gauche du tableau.
Tableaux Accès Parcours Recherche Tri
Recherche dichotomique
60
55 81
On regarde le milieu de cette portion.
Tableaux Accès Parcours Recherche Tri
Recherche dichotomique
60
55 81
Comme la valeur recherchée est plus grande que 55 on re-
lance la recherche dans la moitié droite de la portion.
Tableaux Accès Parcours Recherche Tri
Recherche dichotomique
60
55 62 81
Et ainsi de suite . . .
Tableaux Accès Parcours Recherche Tri
Recherche dichotomique
60
55 60 62 81
. . . jusqu’à tomber sur la valeur recherchée, ou jusqu’à obtenir une portion vide.
Tableaux Accès Parcours Recherche Tri
Recherche dichotomique
Rechercher dans un tableau trié
variables
entier tableau[n] ← {· · · }
entier i, gauche, droite, valeur
début
lire valeur
gauche ← 0
droite ← n − 1
répéter
i ← (gauche + droite) / 2
si valeur < tableau[i] alors
droite ← i − 1
sinon
gauche ← i + 1
fin
jusqu’à (valeur = tableau[i]) ou (gauche > droite)
si valeur = tableau[i] alors
afficher i
sinon
afficher "échec"
fin
fin
Tableaux Accès Parcours Recherche Tri
Recherche dichotomique
Rechercher dans un tableau trié
variables
entier tableau[n] ← {· · · }
entier i, gauche, droite, valeur
Bornes de la portion à rechercher
début
lire valeur
gauche ← 0
droite ← n − 1
répéter
i ← (gauche + droite) / 2
si valeur < tableau[i] alors
droite ← i − 1
sinon
gauche ← i + 1
fin
jusqu’à (valeur = tableau[i]) ou (gauche > droite)
si valeur = tableau[i] alors
afficher i
sinon
afficher "échec"
fin
fin
Tableaux Accès Parcours Recherche Tri
Recherche dichotomique
Rechercher dans un tableau trié
variables
entier tableau[n] ← {· · · }
entier i, gauche, droite, valeur
Bornes de la portion à rechercher
début
lire valeur Milieu de la portion
gauche ← 0
droite ← n − 1
répéter
i ← (gauche + droite) / 2
si valeur < tableau[i] alors
droite ← i − 1
sinon
gauche ← i + 1
fin
jusqu’à (valeur = tableau[i]) ou (gauche > droite)
si valeur = tableau[i] alors
afficher i
sinon
afficher "échec"
fin
fin
Tableaux Accès Parcours Recherche Tri
Recherche dichotomique
Rechercher dans un tableau trié
variables
entier tableau[n] ← {· · · }
entier i, gauche, droite, valeur
Bornes de la portion à rechercher
début
lire valeur Milieu de la portion
gauche ← 0
droite ← n − 1
répéter Si la valeur est plus petite que le milieu
i ← (gauche + droite) / 2
si valeur < tableau[i] alors
droite ← i − 1
sinon
gauche ← i + 1
fin
jusqu’à (valeur = tableau[i]) ou (gauche > droite)
si valeur = tableau[i] alors
afficher i
sinon
afficher "échec"
fin
fin
Tableaux Accès Parcours Recherche Tri
Recherche dichotomique
Rechercher dans un tableau trié
variables
entier tableau[n] ← {· · · }
entier i, gauche, droite, valeur
Bornes de la portion à rechercher
début
lire valeur Milieu de la portion
gauche ← 0
droite ← n − 1
répéter Si la valeur est plus petite que le milieu
i ← (gauche + droite) / 2
si valeur < tableau[i] alors
droite ← i − 1 alors rechercher dans la moitié gauche
sinon
gauche ← i + 1
fin
jusqu’à (valeur = tableau[i]) ou (gauche > droite)
si valeur = tableau[i] alors
afficher i
sinon
afficher "échec"
fin
fin
Tableaux Accès Parcours Recherche Tri
Recherche dichotomique
Rechercher dans un tableau trié
variables
entier tableau[n] ← {· · · }
entier i, gauche, droite, valeur
Bornes de la portion à rechercher
début
lire valeur Milieu de la portion
gauche ← 0
droite ← n − 1
répéter Si la valeur est plus petite que le milieu
i ← (gauche + droite) / 2
si valeur < tableau[i] alors
droite ← i − 1 alors rechercher dans la moitié gauche
sinon
gauche ← i + 1
fin sinon rechercher dans la moitié droite
jusqu’à (valeur = tableau[i]) ou (gauche > droite)
si valeur = tableau[i] alors
afficher i
sinon
afficher "échec"
fin
fin
Tableaux Accès Parcours Recherche Tri
Recherche dichotomique
Rechercher dans un tableau trié
variables
entier tableau[n] ← {· · · }
entier i, gauche, droite, valeur
Bornes de la portion à rechercher
début
lire valeur Milieu de la portion
gauche ← 0
droite ← n − 1
répéter Si la valeur est plus petite que le milieu
i ← (gauche + droite) / 2
si valeur < tableau[i] alors
droite ← i − 1 alors rechercher dans la moitié gauche
sinon
gauche ← i + 1
fin sinon rechercher dans la moitié droite
jusqu’à (valeur = tableau[i]) ou (gauche > droite)
si valeur = tableau[i] alors continuer jusqu’à ce que la portion soit
afficher i vide
sinon
afficher "échec"
fin
fin
Tableaux Accès Parcours Recherche Tri
Recherche dichotomique
Rechercher dans un tableau trié
variables
entier tableau[n] ← {· · · }
entier i, gauche, droite, valeur
Bornes de la portion à rechercher
début
lire valeur Milieu de la portion
gauche ← 0
droite ← n − 1
répéter Si la valeur est plus petite que le milieu
i ← (gauche + droite) / 2
si valeur < tableau[i] alors
droite ← i − 1 alors rechercher dans la moitié gauche
sinon
gauche ← i + 1
fin sinon rechercher dans la moitié droite
jusqu’à (valeur = tableau[i]) ou (gauche > droite)
si valeur = tableau[i] alors continuer jusqu’à ce que la portion soit
afficher i vide
sinon
afficher "échec"
fin ou jusqu’à trouver l’index de la valeur
fin
Algorithme de recherche dichotomique
// cette fonction renvoie vrai si e est présente dans tab, faux sinon
// le tableau tab est supposé trié par ordre croissant
fonction avec retour booléen rechercheElement3(chaine tab[], chaine e)
entier i, j;
booléen trouve;
début
trouve <- false;
i <- 0;
j <- [Link]-1;
tantque (i <= j et non trouve) faire
si (tab[(j+i)/2] = e) alors
trouve <- vrai;
sinon
si (tab[(j+i)/2] > e) alors
j <- (j+i)/2 - 1;
sinon
i <- (j+i)/2 + 1;
finsi
finsi
fintantque
retourne trouve;
fin
Algorithmique et Programmation 9
