Aller au contenu

Recherche séquentielle et dichotomique

Retour sur la recherche linéaire (séquentielle)⚓︎

Exercice
1. Écrire une fonction appartient telle que appartient(e, L) renvoie un booléen permettant de savoir si e appartient à la liste L.
2. Donner le nombre de comparaisons (une comparaison étant une utilisation de == ou <, par exemple) effectuées par appartient pour des valeurs suivantes de e et L : - e = 2 et L = [2, 4, 1, 7] - e = 3 et L = [2, 4, 1, 7] - e = 1 et L = [2, 4, 1, 7] 3. Soit L une liste de taille \(n\). Quel est le nombre minimum de comparaisons réalisées par appartient sur la liste L ? Et le nombre maximum ? Quel est l'indicateur qui vous semble le plus pertinent ?
4. En supposant avoir un ordinateur à 1 GHz (permettant de réaliser \(10^9\) opérations par seconde), et qu'une comparaison demande une opération pour le processeur, combien de temps au plus prendrait l'exécution de appartient sur une liste de taille \(10^{11}\) ?

Python
# 1.
def appartient(e, L):
    for x in L:
        if x == e:
            return True
    return False

# 2. 
# - 1 seule comparaison : appartient(e, L) s'arrête tout de suite
# - 4 comparaisons : appartient(e, L) parcourt toute la liste
# - 3 comparaisons

# 3. Nombre minimum : 1. Nombre maximum : len(L). Le pire cas est plus pertinent car il si on veut éviter d'attendre trop longtemps.

# 4. 10**11 / 10**9 = 100 secondes

Dichotomie⚓︎

Dans la langue française, une dichotomie désigne un choix entre 2 possibilités. En informatique, c'est une technique algorithmique où, à chaque étape, on divise la taille du problème par 2.
L'exemple le plus classique est la recherche par dichotomie dans une liste triée : on souhaite savoir si un élément \(e\) appartient à une liste triée L.

Exercice : Écrire une fonction croissant telle que croissant(L) renvoie un booléen indiquant si L est triée par ordre croissant. Cette fonction ne sera pas utilisée dans la suite (on supposera que la liste est bien triée, sans vérifier).

Considérons par exemple L = \([-2, 1, 2, 4, 6, 7, 8, 9, 11, 12, 14, 15, 18, 22, 54]\) et \(e\) = \(14\).

Au lieu de commencer par regarder le 1er élément de L, on va regarder l'élément du milieu (ici \(9\)): \(\([-2, 1, 2, 4, 6, 7, 8, \underline{\mathbf{9}}, 11, 12, 14, 15, 18, 22, 54]\)\) Comme \(9 < 14\) et que la liste est triée par ordre croissant, on en déduit que \(e\), s'il est dans L, est forcément dans la partie droite : \(\([-2, 1, 2, 4, 6, 7, 8, {9}, \boxed{11, 12, 14, {15}, 18, 22, 54}]\)\) On se restreint donc par la suite à la partie de L qui est encadrée. On compare \(e\) au milieu de cette partie, c'est-à-dire \(15\) : \(\([-2, 1, 2, 4, 6, 7, 8, {9}, \boxed{11, 12, 14, \underline{\textbf{15}}, 18, 22, 54}]\)\) Comme \(e < 15\), on peut cette fois se restreinte à la partie gauche. On cherche donc maintenant \(e\) dans la zone suivante : \(\([-2, 1, 2, 4, 6, 7, 8, {9}, \boxed{11, {12}, 14}, {15}, 18, 22, 54]\)\) On compare encore une fois \(e\) au milieu : \(\([-2, 1, 2, 4, 6, 7, 8, {9}, \boxed{11, \underline{\textbf{12}}, 14}, {15}, 18, 22, 54]\)\) Comme \(e > 12\), on regarde à droite : \(\([-2, 1, 2, 4, 6, 7, 8, {9}, 11, {12}, \boxed{\underline{\textbf{14}}}, {15}, 18, 22, 54]\)\) On a trouvé \(e\) !

Exercice : Quel a été le nombre de comparaisons nécessaires pour la recherche par dichotomie sur cet exemple ? Et si on avait utilisé appartient(e, L) ? Quelle méthode vous semble la plus efficace ?

\(4\) comparaisons pour la recherche dichotomique contre \(11\) (c'est-à-dire l'indice de \(14\)) pour la recherche séquentielle (appartient).

Pour se souvenir de la zone dans laquelle on cherche l'élément \(e\) (encadrée sur l'exemple ci-dessus), on utilise deux indices \(i\) et \(j\).

Exercice : Compléter le code suivant permettant de rechercher un élément dans une liste triée, par dichotomie.

Python
def dichotomie(e, L):
    i, j = 0, len(L) - 1  # i et j sont les indices de L entre lesquels on cherche e
    while ...: # tant qu'il reste au moins 1 élément entre les indices i et j
        m = ... # milieu de i et j
        if e < L[m]:
            ... # regarder dans la partie gauche
        elif e > L[m]:
            ... # regarder dans la partie droite
        else:
            ... # on a trouvé e
    ... # e n'a pas été trouvé
Puis tester votre fonction avec le jeu de tests suivant (assert déclenche une erreur si son argument est False) :
Python
L1, L2, L3 = [0, 2], [0, 2, 5], [-2, 1, 2, 4, 6, 7, 8, 9, 11, 12, 14, 15, 18, 22, 54]
assert (dichotomie(0, L1) and not dichotomie(1, L1))
assert (dichotomie(5, L2) and not dichotomie(7, L2))
assert (dichotomie(14, L3) and not dichotomie(-4, L3))

Python
def dichotomie(e, L):
    i, j = 0, len(L) - 1  # i et j sont les indices de L entre lesquels on cherche e
    while i <= j: # tant qu'il reste au moins 1 élément entre les indices i et j
        m = (i + j)//2 # milieu de i et j
        if e < L[m]:
            j = m - 1 # regarder dans la partie gauche
        elif e > L[m]:
            i = m + 1 # regarder dans la partie droite
        else:
            return True # on a trouvé e
    return False # e n'a pas été trouvé

L1, L2, L3 = [0, 2], [0, 2, 5], [-2, 1, 2, 4, 6, 7, 8, 9, 11, 12, 14, 15, 18, 22, 54]
assert (dichotomie(0, L1) and not dichotomie(1, L1))
assert (dichotomie(5, L2) and not dichotomie(7, L2))
assert (dichotomie(14, L3) and not dichotomie(-4, L3))

Exercice : On admet que dichotomie(e, L) réalise au plus environ \(\log(n)\) opérations si L est de taille \(n\). Sur un ordinateur à 1 GHz, combien de temps au plus prendrait l'exécution de dichotomie pour une liste de taille \(10^{11}\) ?

\(\(\frac{\log(10^{11})}{10^9} = \frac{11}{10^9} = 1.1 \times 10^{-8} \text{ secondes}\)\) dichotomie est donc beaucoup plus rapide que appartient.

Exponentiation rapide⚓︎

Exercice
1. Écrire une fonction puissance telle que puissance(a, n) renvoie a puissance n (la même chose que a**n). On utilisera \(a^n = a\times a \times... \times a\).
2. Quel est le nombre de multiplications réalisé par la fonction précédente ?

Python
# 1.
def puissance(a, n):
    r = 1
    for i in range(n):
        r = r * a
    return r

# 2. n multiplications

L'algorithme ci-dessus n'est pas optimal. On peut faire mieux en utilisant le fait que, si on connaît \(b = a^{\frac{n}{2}}\), il suffit de calculer \(b^2\) pour avoir la valeur de \(a^n\), ce qui demande \(1\) multiplication au lieu de \(\frac{n}{2}\). L'idée de l'exponentiation rapide est de partir de \(r = a\) et de mettre \(r\) au carré un certain nombre de fois jusqu'à obtenir \(a^n\). Cependant, si \(n\) est impair, on ne peut pas diviser \(n\) par \(2\) et il faut à la place multiplier \(r\) par \(a\).
On met en oeuvre cette idée avec l'algorithme suivant :

Python
def puissance_rapide(a, n):
    r = 1
    while n != 0:
        if n % 2 == 1:
            r = r * a
        a = a * a
        n = n // 2
    return r
Text Only
268435456

Exercice
1. Exécuter à la main puissance_rapide(2, 12). On donnera la valeur de r, a et n à la fin de chaque passage dans la boucle while. 2. Comparer le nombre de multiplications dans l'exemple ci-dessus avec le nombre de multiplications réalisé par puissance(2, 12). 3. Montrer que la valeur de \(r a^n\) reste identique à chaque passage dans le while. En déduire que puissance_rapide(a, n) renvoie bien \(a^n\).
4. Comment pourrais-t-on utiliser une multiplication de moins dans puissance_rapide. Modifier la fonction pour ce faire.

  1. Nombre de passages dans le while r a n
    1 \(1\) \(2\) \(12\)
    2 \(1\) \(4\) \(6\)
    3 \(1\) \(4^2 = 16\) \(3\)
    4 \(16\) \(16^2 = 256\) \(1\)
    5 \(16\times 256 = \boxed{4096}\) ... ...
  2. L'exponentiation rapide a effectué \(6\) multiplications, alors que puissance(2, 12) en fait \(12\).
  3. On vérifie que \(r a^n\) ne change pas dans les deux possibilités suivantes :
  4. Si n est pair, on remplace \(a^n\) par \((a^2)^\frac{n}{2}\) et \(r\) ne change pas, donc \(ra^n\) ne change pas.
  5. Si n est impair, on remplace \(n\) par \(\frac{n - 1}{2}\) (car n \\ 2 effectue la division entière) donc \(ra^n\) est remplacé par \((r\times a)(a^2)^{\frac{n - 1}{2}} = r \times a^n\).
  6. Une fois la dernière valeur de r calculée, il ne sert à rien de mettre à jour a. Donc on pourrait écrire :
    Python
    def puissance_rapide(a, n):
    r = 1
    while n > 1:
        if n % 2 == 1:
            r = r * a
        a = a * a
        n = n // 2
    return r * a  # dernière modification de r, quand n == 1