Structures de données IFT-10541 Abder Alikacem Semaine 7 Les algorithmes de recherche Département dinformatique et de génie logiciel Édition septembre

Structures de donnéesIFT-10541

Abder AlikacemAbder Alikacem

Semaine 7 Les algorithmes de recherche

Département d’informatique et de génie logiciel

Édition septembre 2009

! +

Plan

• Les algorithmes de recherche• La recherche séquentielle• La recherche dichotomique

• Complexité des algorithmes de recherche• Recherche dichotomique et arborescence

La recherche séquentielle

3 1 4 2 8 14 12 11 6 9 10

• recherche(3) =• recherche(10) =• recherche(12) =• recherche(13) = • meilleur cas =• pire cas =• en moyenne =• absences =

Données pas triées


3 1 4 2 8 14 12 11 6 9 10

• recherche(3) = 1 comparaison• recherche(10) =• recherche(12) =• recherche(13) =• meilleur cas =• pire cas =• en moyenne =• absences =



3 1 4 2 8 14 12 11 6 9 10

• recherche(3) = 1 comparaison• recherche(10) = 11 comparaisons• recherche(12) =• recherche(13) =• meilleur cas =• pire cas =• en moyenne =• absences =



3 1 4 2 8 14 12 11 6 9 10

• recherche(3) = 1 comparaison• recherche(10) = 11 comparaisons• recherche(12) = 7 comparaisons• recherche(13) =• meilleur cas =• pire cas =• en moyenne = • absences =



3 1 4 2 8 14 12 11 6 9 10

• recherche(3) = 1 comparaison• recherche(10) = 11 comparaisons• recherche(12) = 7 comparaisons• recherche(13) = 11 comparaisons• meilleur cas =• pire cas =• en moyenne =• absences =



3 1 4 2 8 14 12 11 6 9 10

• recherche(3) = 1 comparaison• recherche(10) = 11 comparaisons• recherche(12) = 7 comparaisons• recherche(13) = 11 comparaisons• meilleur cas = O(1)• pire cas =• en moyenne =• absences =



3 1 4 2 8 14 12 11 6 9 10

• recherche(3) = 1 comparaison• recherche(10) = 11 comparaisons• recherche(12) = 7 comparaisons• recherche(13) = 11 comparaisons• meilleur cas = O(1)• pire cas = O(n)• en moyenne = • absences =



3 1 4 2 8 14 12 11 6 9 10

• recherche(3) = 1 comparaison• recherche(10) = 11 comparaisons• recherche(12) = 7 comparaisons• recherche(13) = 11 comparaisons• meilleur cas = O(1)• pire cas = O(n)• en moyenne = O(n/2)• absences =



3 1 4 2 8 14 12 11 6 9 10

• recherche(3) = 1 comparaison• recherche(10) = 11 comparaisons• recherche(12) = 7 comparaisons• recherche(13) = 11 comparaisons• meilleur cas = O(1)• pire cas = O(n)• en moyenne = O(n/2)• absences = O(n)



1 2 3 4 6 8 9 10 11 12 14

• recherche(1) =• recherche(14) =• recherche(8) =• recherche(13) =• meilleur cas =• pire cas =• en moyenne = • absences =

Données triées


1 2 3 4 6 8 9 10 11 12 14

• recherche(1) = 1 comparaison• recherche(14) =• recherche(8) =• recherche(13) =• meilleur cas =• pire cas =• en moyenne = • absences =

Données triées


1 2 3 4 6 8 9 10 11 12 14

• recherche(1) = 1 comparaison• recherche(14) = 11 comparaisons• recherche(8) =• recherche(13) =• meilleur cas =• pire cas =• en moyenne = • absences =

Données triées


1 2 3 4 6 8 9 10 11 12 14

• recherche(1) = 1 comparaison• recherche(14) = 11 comparaisons• recherche(8) = 6 comparaisons• recherche(13) =• meilleur cas =• pire cas =• en moyenne = • absences =

Données triées


1 2 3 4 6 8 9 10 11 12 14

• recherche(1) = 1 comparaison• recherche(14) = 11 comparaisons• recherche(8) = 6 comparaisons• recherche(13) = 11 comparaisons• meilleur cas =• pire cas =• en moyenne = • absences =

Données triées


1 2 3 4 6 8 9 10 11 12 14

• recherche(1) = 1 comparaison• recherche(14) = 11 comparaisons• recherche(8) = 6 comparaisons• recherche(13) = 11 comparaisons• meilleur cas = O(1)• pire cas =• en moyenne = • absences =

Données triées


1 2 3 4 6 8 9 10 11 12 14

• recherche(1) = 1 comparaison• recherche(14) = 11 comparaisons• recherche(8) = 6 comparaisons• recherche(13) = 11 comparaisons• meilleur cas = O(1)• pire cas = O(n)• en moyenne = • absences =

Données triées


1 2 3 4 6 8 9 10 11 12 14

• recherche(1) = 1 comparaison• recherche(14) = 11 comparaisons• recherche(8) = 6 comparaisons• recherche(13) = 11 comparaisons• meilleur cas = O(1)• pire cas = O(n)• en moyenne = O(n/2)• absences =

Données triées


1 2 3 4 6 8 9 10 11 12 14

• recherche(1) = 1 comparaison• recherche(14) = 11 comparaisons• recherche(8) = 6 comparaisons• recherche(13) = 11 comparaisons• meilleur cas = O(1)• pire cas = O(n)• en moyenne = O(n/2)• absences = O(n/2)

Données triées


données non triées :• données présentes : O(n/2)• données absentes : O(n)

données triées :• données présentes : O(n/2)• données absentes : O(n/2)

coût pour trier et maintenir triées !

Modèles d’implantation

tableau :

liste chaînée :

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

La recherche binaire

• implantation en tableau = accès direct à n’importe quel élément

• en regardant tout de suite au milieu, on peut éliminer la moitié des données

1 2 3 4 6 8 9 10 11 12 14


1 2 3 4 6 8 9 10 11 12 14

100


1 2 3 4 6 8 9 10 11 12 14

100 5


1 2 3 4 6 8 9 10 11 12 14

100 5


1 2 3 4 6 8 9 10 11 12 14

100 5

La recherche binaire : 10 ?

1 2 3 4 6 8 9 10 11 12 14

100 5


1 2 3 4 6 8 9 10 11 12 14

100 5


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 10


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108

6 7


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108

6 7


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108

6 7


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108

6 7

1 2 3 4 6 8 9 10 11 12 14

7


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108

6 7

1 2 3 4 6 8 9 10 11 12 14

7

La recherche binaire : 9.5 ?

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108

6 7

1 2 3 4 6 8 9 10 11 12 14

7


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108

6 7

1 2 3 4 6 8 9 10 11 12 14

7

11

5

2

1


1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108

6 7

1 2 3 4 6 8 9 10 11 12 14

7

11

5

2

1

n

n/2

n/4

n/8

Algorithme récursif

• récursion ?

• conditions d’arrêt ?

• convergence ?

1 2 3 4 6 8 9 10 11 12 14

100 5

Récursion

x tab[debut..fin]

si x = tab[milieu] (condition d’arrêt)si x < tab[milieu] et x tab[debut..milieu-1]si x > tab[milieu] et x tab[milieu+1..fin]

1 2 3 4 6 8 9 10 11 12 14

100 5

Conditions d’arrêt

x tab[debut..fin] si debut > fin

x tab[debut..fin] si x = tab[milieu]

1 2 3 4 6 8 9 10 11 12 14

100 5

Convergence

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100 5

6 108

6 7

1 2 3 4 6 8 9 10 11 12 14

7

Template <typename T>

int rechercheBinRec(T * tab, T val, int debut, int fin)

{ int milieu;

/*A: tab est correctement initialisé*/

if (debut > fin) return -1;

else

{ milieu= (debut + fin)/2;

if( val == tab[milieu]) return milieu;

else

{

if( val < tab[milieu]) return(rechercheBinRec(tab,val,debut, milieu-

1));

else return(rechercheBinRec(tab,val,milieu+1,fin));

}

}

}

Il vaut bien mieux implanter cet algorithme de manière itérative, car la fonction se rappelle jusqu'à trouver la position désirée, puis seulement on effectue les dépilages, alors que l'on n'a plus besoin des états intermédiaires qui ont été mémorisés par la récursivité puisque le problème est résolu.

Remarque sur les algorithmes récursifs

Tableau comparatif

recherche séquentielle : (données triées)• données présentes : O(n/2)• données absentes : O(n/2)

recherche binaire : (données triées)• données présentes : O(log n)• données absentes : O(log n)

Modèles d’implantation

tableau :

liste chaînée ?

1 2 3 4 6 8 9 10 11 12 14

1 2 3 4 6 8 9 10 11 12 14

100

Structures pointées

1 2 3 4 6 8 9 10 11 12 14

0 1 2 3 4 5 6 7 8 9 10


1 2 3 4 6 8 9 10 11 12 14

0 1 2 3 4 5 6 7 8 9 10


1 2 3 4 6 8 9 10 11 12 14

0 1 2 3 4 5 6 7 8 9 10


1 2 3 4 6

8

9 10 11 12 14

0 1 2 3 4 6 7 8 9 10


1 2 3 4 6

8

9 10 11 12 14

0 1 2 3 4 6 7 8 9 10


1 2 3 4 6

8

9 10 11 12 14

0 1 2 3 4 6 7 8 9 10


1 2

3

4 6

8

9 10

11

12 14

0 1 3 4 6 7 9 10


1 2

3

4 6

8

9 10

11

12 14

0 1 3 4 6 7 9 10


1 2

3

4 6

8

9 10

11

12 14

0 1 3 4 6 7 9 10


1

2

3

4

6

8

9

10

11

12

14


1

2

3

4

6

8

9

10

11

12

14


1

2

3

4

6

8

9

10

11

12

14


1

2

3

4

6

8

9

10

11

12

14

Arbre binaire !

1

2

3

4

6

8

9

10

11

12

14

Arbre binaire !

1

2

3

4

6

8

9

10

11

12

14

≤≤

≤≤

≤

≤≤

≤ ≤ ≤

Arbre binaire

racine

sous-arbre de gauchesous-arbre de droite

nœuds internes

feuilles

Arbre = graphe

1

2

3

4

6

8

9

10

11

12

14

Arbre = graphe

1

2

3

4

6

8

9

10

11

12

14

Arbre = graphe

1

2

3

4

6

8

9

10

11

12

14

Arbre = graphe

• graphe connexe, orienté, acyclique• 1 seul nœud source = racine• nœuds puits = feuilles• ordre d ’entrée de tout nœud = 1, sauf racine• un chemin de la racine à tout autre nœud

Arbre = index

1

2

3

4

6

8

9

10

11

12

14

Arbre = index

1

2

3

4

6

8

9

10

11

12

14

Index sur sommet d’un graphe

4

25

3

1

1

2

3

4

5

1 2 3 4 5

1

1 1

1 1

1

...

Index sur sommet d’un graphe

4

25

3

1

1

2

3

4

5

1 2 3 4 5

1

1 1

1 1

1

...

3

5

4

2

1

Documents

Structures de données IFT-10541 Abder Alikacem Semaine 7 Les algorithmes de recherche Département dinformatique et de génie logiciel Édition septembre