Les algorithmes de recherche

Updated 894 Days AgoPublic

Actions

Instinctivement, lorsqu'on souhaite rechercher quelques choses on utilise des hypothèses pour trouver ce que l'on cherche plus rapidement. Par exemple, lorsqu'on a perdu ses clés, on cherche en premier sur la table, sur le bureau, ... C'est seulement après avoir cherché dans tous les endroits probables, on commence à chercher dans les plus improbables : le frigo. En d'autres termes, vous avez appliqué un algorithme de recherche.

Lorsqu'on effectue une recherche dans un tableau, il faut procéder itérativement sur chacune des valeurs de ce tableau. Ce procédé est appelé la recherche linéaire. Les algorithmes de recherches doivent toujours tenir compte du contexte. Dans un tableau, ce contexte correspond à s'il est trié ou non. C’est-à-dire que si vous recherchez une valeur dans un tableau trié, il est inutile de poursuivre la recherche si les valeurs du tableau sont en dehors du domaine de recherche. Par exemple, lorsqu'on recherche la valeur 5 dans le tableau croisant [1, 4, 7, 9], vous pouvez interrompre prématurément la recherche à la valeur 7, puisqu'elle est plus grande que votre nombre.

Il est possible d'être beaucoup plus efficace lorsqu'on effectue la recherche d'un élément dans un tableau trié. Cet algorithme est celui que l'on emploie naturellement lorsqu'on recherche un mot dans le dictionnaire. On ouvre le dictionnaire au milieu, et on regarde si le mot se situe avant ou après la page que l'on a ouverte. De cette façon, la taille de la recherche dans le dictionnaire est ainsi divisée par deux puisqu'il est possible d'ignorer une partie des mots. On continue notre recherche en ouvrant une page parmi l'ensemble des pages restantes. On répète ainsi l'opération jusqu'à trouver le mot. Cet algorithme est appelé la recherche dichotomique.

Exercices

• Écrivez une fonction qui renvoie la plus petite valeur d'un tableau non trié de N cases. Quelle est la complexité de cet algorithme ?

FONCTION MIN(↕t: TABLEAU ENTIER, N: ENTIER)
VARIABLE i: ENTIER
VARIABLE val <- +∞

POUR i DE 0 À N-1:
    SI val > t[i]:
       val <- t[i]
    FIN SI
FIN POUR

RETOURNER val
FIN FONCTION

• Écrivez une fonction qui renvoie la plus petite valeur d'un tableau croissant de N cases. Quelle est la complexité de cet algorithme ?

FONCTION MIN_TRI(↕t: TABLEAU ENTIER, N: ENTIER)
RETOURNER t[0]
FIN FONCTION

• Écrivez une fonction qui compte le nombre de fois que se trouve une valeur dans un tableau croissant de N cases.

FONCTION COUNT1(↕t: TABLEAU ENTIER, N: ENTIER, val: ENTIER)
VARIABLE i, cpt: ENTIER
cpt <- 0

POUR i DE 0 À N-1:
    SI val = t[i]:
       cpt <- cpt + 1
    FIN SI
FIN POUR

RETOURNER cpt
FIN FONCTION

FONCTION COUNT2(↕t: TABLEAU ENTIER, N: ENTIER, val: ENTIER)
VARIABLE i, cpt: ENTIER
cpt <- 0

TANT QUE t[i] <= val ET i < N:
    SI val = t[i]:
       cpt <- cpt + 1
    FIN SI
    i <- i+1
FIN POUR

RETOURNER cpt
FIN FONCTION

FONCTION COUNT2(↕t: TABLEAU ENTIER, N: ENTIER, val: ENTIER)
VARIABLE i, cpt: ENTIER
cpt <- 0

TANT QUE t[i] <= val ET val <= t[N-1]:
    SI val = t[i]:
       cpt <- cpt + 1
    FIN SI
    i <- i+1
FIN POUR

RETOURNER cpt
FIN FONCTION

• Écrivez une fonction qui renvoie l'indice de la case où se trouve une valeur d'un tableau non trié de N cases. Si la valeur n'est pas présente, renvoyer la valeur -1.

FONCTION FIND(↕t: TABLEAU ENTIER, N: ENTIER, val: ENTIER)
VARIABLE i: ENTIER

POUR i DE 0 À N-1:
    SI val = t[i]:
       RETOURNER i
    FIN SI
FIN POUR

RETOURNER -1
FIN FONCTION

• Écrivez une fonction qui renvoie l'indice de la case où se trouve une valeur dans un tableau croissant de N cases. Si la valeur n'est pas présente, renvoyer la valeur -1. Pour cet exercice, utiliser la recherche linéaire. Quelle est la complexité de cet algorithme ?

FONCTION FIND_LINEAR_ORDERED1(↕t: TABLEAU ENTIER, N: ENTIER, val: ENTIER)
VARIABLE i: ENTIER

POUR i DE 0 À N-1:
    SI val = t[i]:
       RETOURNER i
    SINON SI val < t[i]
       RETOURNER -1
    FIN SI
FIN POUR

RETOURNER -1
FIN FONCTION

FONCTION FIND_LINEAR_ORDERED2(↕t: TABLEAU ENTIER, N: ENTIER, val: ENTIER)
VARIABLE i: ENTIER
i <- 0
TANT QUE t[i] <= val
    SI val = t[i]:
       RETOURNER i
    i <- i + 1
FIN TANT QUE

RETOURNER -1
FIN FONCTION

• Écrivez une fonction qui renvoie l'indice de la case où se trouve une valeur dans un tableau croissant de N cases. Si la valeur n'est pas présente, renvoyer la valeur -1. Pour cet exercice, utiliser la recherche dichotomique. Quelle est la complexité de cet algorithme ?

FONCTION FIND_DICHOTOMIC(↕t: TABLEAU ENTIER, N: ENTIER, val: ENTIER)
VARIABLE g, d, c: ENTIER
g <- 0
d <- N-1

RÉPÉTER
    c = (g+d)/2
    SI t[c] == val:
        RETOURNER c
    SINON SI t[c] < val:
        g = c+1
    SINON SI:
        d = c-1;
    FIN SI
TANT QUE ( g < d )

RETOURNER -1
FIN FONCTION