TP 4 : Recherche par dichotomie

Retour sur la recherche linéaire¶

Exercice

Écrire une fonction appartient telle que appartient(e, L) renvoie un booléen permettant de savoir si e appartient à la liste L.
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]

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 ?
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}$ ?

Solution

In [ ]:

# 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
# 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 ?

Solution

$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.

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) :

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))

Solution

In [7]:

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))
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}$ ?

Solution

$$\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

É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$.
Quel est le nombre de multiplications réalisé par la fonction précédente ?

Solution

In [8]:

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

# 2. n multiplications
# 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 :

In [3]:

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
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

Out[3]:

268435456

Exercice

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.
Comparer le nombre de multiplications dans l'exemple ci-dessus avec le nombre de multiplications réalisé par puissance(2, 12).
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$.
Comment pourrais-t-on utiliser une multiplication de moins dans puissance_rapide. Modifier la fonction pour ce faire.

Solution

| 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}$ | ... | ... |
L'exponentiation rapide a effectué $6$ multiplications, alors que puissance(2, 12) en fait $12$.
On vérifie que $r a^n$ ne change pas dans les deux possibilités suivantes :

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.
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$.

Une fois la dernière valeur de r calculée, il ne sert à rien de mettre à jour a. Donc on pourrait écrire :

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