Ecole Supérieure d’Economie Numérique
Complexité Algorithmique: Les algorithmes de
recherche
Dr.Chiheb-Eddine Ben N’Cir
2016 − 2017
Outline
1 Recherche simple
2
recherche par dichotomie
3 Recherche par hashage
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de recherche
2016
2 / 12
Algorithme de recherche simple
Recherche simple
public boolean rechercheSimple(int v,int [] T) {
boolean trouve=false;
int i=0;
while ( ( trouve == false ) & &( i < T.length ) ) {
if ( T[i] == v ) {
trouve = true; }
else {
i = i+1; } }
return trouve;
}
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de recherche
2016
3
3 / 12
recherche par dichotomie
Algorithme de recherche par dichotomie
Comparaison de la valeur médiane du tableau et de la valeur recherchée. Trois
alternatives:
Egalité
Infériorité stricte
Supériorité stricte
Si égalité, présence de la valeur recherchée dans le tableau
Inutile de continuer à chercher
Retourner vrai
Si valeur recherchée plus petite
Poursuite de la recherche dans le 1/2 tableau inférieur selon le
Advertisement
même mode opératoire
Si valeur recherchée plus grande
Poursuite de la recherche dans le 1/2 tableau supérieur selon le
même mode opératoire
Quand retourner faux? –>Tableau réduit à zéro élément
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de recherche
2016
4
4 / 12
recherche par dichotomie
Recherche dichotomique
public boolean rechercheDichotomique(int v,int [] T) {
boolean stop=false;
boolean res=false;
int indd=0;
while (stop == false) {
if ( indd > indf ) {
stop = true; }
int indf=T.length;
int indm;
else {
indm = (indd+indf) / 2;
if ( T[indm] == v ) {
stop = true;
res = true; }
else {
if ( v < T[indm] ) {
indf = indm; }
else {
indd = indm+1; } } }
}
return res ;
}
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de recherche
2016
5
5 / 12
Conditions à satisfaire
si deux données sont identiques, leur hash code l’est aussi
les hash codes doivent être différent pour des données différentes.
Recherche par hashage
Principes de Hashage
les données sont stockées dans la table de hashage à un indice calculé en
Advertisement
fonction de leur valeur.
Les indices des données sont déterminés par le hash code, qui est donné par
une fonction de hashage.
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de recherche
2016
6
6 / 12
Recherche par hashage
Principes de Hashage
les données sont stockées dans la table de hashage à un indice calculé en
fonction de leur valeur.
Les indices des données sont déterminés par le hash code, qui est donné par
une fonction de hashage.
Conditions à satisfaire
si deux données sont identiques, leur hash code l’est aussi
les hash codes doivent être différent pour des données différentes.
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de recherche
2016
6
6 / 12
Recherche par hashage
Exemple de Fonction de hashage pour des entiers
h(x) = (3.x + 14)mod10
supposant que nous avons un tableau contenant 0,4,7,42
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de recherche
2016
7
7 / 12
Recherche par hashage
Exemple de Fonction de hashage pour des entiers
h(x) = (3.x + 14)mod10
supposant que nous avons un tableau contenant 0,4,7,42
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de recherche
2016
7
7 / 12
Recherche par hashage
Collision
h(x) = (3.x + 14)mod10
supposant que nous avons un tableau contenant 0,4,7,42
Si le nombre 22 est un element de la table ?
Advertisement
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de recherche
2016
8
8 / 12
Recherche par hashage
Collision
h(x) = (3.x + 14)mod10
supposant que nous avons un tableau contenant 0,4,7,42
Si le nombre 22 est un element de la table ?
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de recherche
2016
8
8 / 12
Recherche par hashage
Gestion des Collisions
les sondages linéaire
le double hachage
le chaînage linéaire.
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de recherche
2016
9
9 / 12
Recherche par hashage
Sondage linéaire
chercher la première case libre
algorithme de recherche: parcourir le tableau du hash code jusqu’a le vide
Supression impossible des cases du tableau
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de recherche
2016
10
10 / 12
Recherche par hashage
Sondage linéaire
chercher la première case libre
algorithme de recherche: parcourir le tableau du hash code jusqu’a le vide
Supression impossible des cases du tableau
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de recherche
2016
10
10 / 12
Advertisement
Recherche par hashage
Hashage double
Hash = (h(x) + i.h2(x))modm
i = l’itération d’insertion qui commence de 0
Algorithme de recherche: parcourir le tableau du hash code jusqu’a le vide
Inconvénient: plus le tableau sera rempli et plus la recherche d’une case vide
risque d’être longue
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de recherche
2016
11
11 / 12
Recherche par hashage
Hashage double
Hash = (h(x) + i.h2(x))modm
i = l’itération d’insertion qui commence de 0
Algorithme de recherche: parcourir le tableau du hash code jusqu’a le vide
Inconvénient: plus le tableau sera rempli et plus la recherche d’une case vide
risque d’être longue
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de recherche
2016
11
11 / 12
Recherche par hashage
Chaînage linéaire
au lieu d’avoir un élément par case, on va avoir une liste chainée
Algorithme de recherche: parcourir la liste correspondant au hash code
Inconvénient: il faut utiliser plus d’espace mémoire supplémentaire
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de recherche
2016
12
12 / 12
Recherche par hashage
Chaînage linéaire
au lieu d’avoir un élément par case, on va avoir une liste chainée
Algorithme de recherche: parcourir la liste correspondant au hash code
Inconvénient: il faut utiliser plus d’espace mémoire supplémentaire
Chiheb-Eddine Ben N’Cir (ESEN)
Complexité Algorithmique: les algorithmes de recherche
2016
12
12 / 12