Page MenuHomePhabricator

Les algorithmes de recherche
Updated 36 Days AgoPublic

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 ?
Minimum dun tableau
FONCTION MIN(t: TABLEAU ENTIER, N: ENTIER)
VARIABLE i: ENTIER
VARIABLE val <- +

POUR i DE 0 À N:
    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 ?
Minimum dun tableau trié
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.
Nombre de valeur
FONCTION COUNT(t: TABLEAU ENTIER, N: ENTIER, val: ENTIER)
VARIABLE i, cpt: ENTIER
cpt <- 0

POUR i DE 0 À N:
    SI val = t[i]:
       cpt <- cpt + 1
    FIN SI
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.
Recherche linéaire
FONCTION FIND(t: TABLEAU ENTIER, N: ENTIER, val: ENTIER)
VARIABLE i: ENTIER

POUR i DE 0 À N:
    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 ?
Recherche linéaire dans un tableau croissant
FONCTION FIND_LINEAR_ORDERED(t: TABLEAU ENTIER, N: ENTIER, val: ENTIER)
VARIABLE i: ENTIER

POUR i DE 0 À N:
    SI val = t[i]:
       RETOURNER i
    SINON SI val < t[i]
       RETOURNER -1
    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 dichotomique. Quelle est la complexité de cet algorithme ?
Recherche dicothomique
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
Last Author
Steve
Last Edited
Sep 13 2020, 2:04 PM

Event Timeline

Steve edited the content of this document. (Show Details)Sep 10 2020, 4:34 PM
Steve edited the content of this document. (Show Details)
Steve created this object.
Steve changed the title from Search to La complexité d'un algorithme.Sep 12 2020, 1:43 PM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)
Steve changed the title from La complexité d'un algorithme to Les algorithmes de recherche.Sep 13 2020, 10:36 AM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Sep 13 2020, 12:05 PM
Steve edited the content of this document. (Show Details)Sep 13 2020, 2:04 PM
Steve edited the content of this document. (Show Details)