TP 8 : correction et complexité

Cliquez sur cette invitation pour récupérer le repository du TP.

Multiplication égyptienne

Considérons le code suivant, qui implémente un ancien algorithme égyptien.
a et b sont supposés être des entiers positifs.

def multegy(a, b):
    p = 0
    while a > 0:
        if a%2 == 1:
            p += b
        b *= 2
        a //= 2
    return p

Qui est le variant de boucle permettant de prouver que multegy termine toujours ?

a : a

b : b

c : p

d : autre réponse

Correction (cliquer pour afficher)

a est une suite d'entiers positifs strictement décroissante, c'est donc un variant de boucle.

Détaillez l’éxécution de multegy(23,5) en affectant à a_i, b_i, p_i, les valeurs rencontrées en début de chaque itération.

Correction (cliquer pour afficher)

def multegy(a, b):
    p = 0
    i = 0
    while a > 0:
        print(f"itération {i} : {a = }, {b = }, {p = }")
        if a%2 == 1:
            p += b
        b *= 2
        a //= 2
        i += 1
    print(f"itération {i} : {a = }, {b = }, {p = }")
    return p
multegy(23,5)
Ce code affiche :
itération 0 : a = 23, b = 5, p = 0
itération 1 : a = 11, b = 10, p = 5
itération 2 : a = 5, b = 20, p = 15
itération 3 : a = 2, b = 40, p = 35
itération 4 : a = 1, b = 80, p = 35
itération 5 : a = 0, b = 160, p = 115

Construisons la preuve de l’algorithme :

on va montrer que $a\times b + p$ est un invariant de boucle et l’utiliser pour prouver que l’algorithme retourne bien le produit entre $a$ et $b$.

Notons $a_k$, $b_k$, $p_k$, les valeurs de $a$, $b$ et $p$ après la k^e itération et supposons $a_k\times b_k + p_k = cste$.

initialisation : pour $k=0$, $a_0=a$, $b_0=b$ et $p_0=0$. D’où $a_0\times b_0+p_0=a\times b$
conservation : à la boucle $k+1$, deux cas se présentent :
- si $a$ est impair : $a_{k+1} = X$, $b_{k+1} = Y$ et $p_{k+1}= Z$.
  D’où $a_{k+1}\times b_{k+1} + p_{k+1} = a_k\times b_k - b_k +p_k+ b_k = a_k\times b_k+p_k$
- si $a$ est pair : $a_{k+1} = \frac{a_k}{2}$, $b_{k+1} = b_k\times 2$ et $p_{k+1}=p_k$.
  D’où $a_{k+1}\times b_{k+1} + p_{k+1} = a_k\times b_k + p_k$
  Par conséquent, $a_k\times b_k + p_k$ est bien un invariant pour tout $k$.
terminaison : en sortie de boucle (itération $f$), $a_f = 0$, donc $a_f\times b_f+p_f = p_f$. Or comme l’invariant est… invariant, il garde toujours la valeur qu’il possède en entrée (pour $k=0$) : d’où $p_f = a\times b$. Et comme la fonction retourne $p_f$, cqfd.

Que vallent X,Y et Z ?

a : $a_k$, $b_k$, $p_k+b_k$

b : $\frac{a_k-1}{2}$, $b_k\times 2$, $p_k+b_k$

c : $\frac{a_k+1}{2}$, $b_k\times 2$, $p_k$

Correction (cliquer pour afficher)

$\displaystyle X = \frac{a_k+1}{2}$, $Y = b_k\times 2$, $Z = p_k+b_k$

Quelle est la complexité de multegy (en supposant chacun des calculs comme élémentaire) ?

a : $O(a)$

b : $O(a\times b)$

c : $O(a\log b)$

d : $O(\log a)$

e : $O(b)$

Correction (cliquer pour afficher)

Il y aura autant de tours dans la boucle while que le nombre de fois qu'on peut diviser a par 2 (division euclidienne) avant d'arriver sur 0. Ce nombre est en $O(\log a)$.
Et à chaque tour, il y a soit $c$ étapes, soit $c+1$ où $c$ est une constante.
La complexité globale reste donc en $O(\log a)$.

Deux fonctions de recherche

def cherche(s, m):  
    for k in range(len(s) - len(m) + 1):  
        b = True  
        for i in range(len(m)):  
            if s[k + i] != m[i]:  
                b = False  
        if b:  
            return True  
    return False

def cherche2(s, m):  
    for k in range(len(s) - len(m) + 1):  
        if s[k:k + len(m)] == m:  
            return True  
    return False

Quelle est la complexité de la fonction cherche ? Et celle de cherche2 ?
Appelons len(s) n et len(m) p.

a : les deux en $O(n\times p)$

b : cherche en $O(n\times p)$ et cherche2 en en $O(n)$

c : une autre réponse

Correction (cliquer pour afficher)

Les deux sont en $O(n\times p)$.
Il ne faut pas simplement compter les imbrications de boucles (même si c'est souvent suffisant) ; dans le cas de cherche2, $m$ étapes sont cachées dans la comparaison s[k:k + len(m)] == m puisque l'interprète python ne peut faire autrement que de comparer les caractères un par un pour s'assurer que les deux chaînes sont bien les mêmes.

Exécuter le code suivant peut vous aider à confirmer votre réponse.

import time
from random import randint

abc = 'abcdefghijklmnopqrstuvwxyz'
def motdenlettres(n): 
    mot = ''
    for i in range(n):
        mot += abc[randint(0,25)]
    return mot

print('-'*30)
print('|    n    |    p   | cherche2 |')
print('-'*30)
for j in range(2,6):
    n = 10**5*2**j
    s = motdenlettres(n)
    for k in range(3):
        p = 10**4*2**k
        m = motdenlettres(p)
        
        d = time.time()
        cherche2(s,m)
        f = time.time()
        t = f - d
        
        print(f'|{n:^9d}|{p:^8d}|{t:^10.2E}|')
    print('-'*30)

------------------------------

|    n    |    p   | cherche2 |

------------------------------

| 400000  | 10000  | 2.04E-01 |

| 400000  | 20000  | 4.65E-01 |

| 400000  | 40000  | 9.72E-01 |

------------------------------

| 800000  | 10000  | 4.20E-01 |

| 800000  | 20000  | 8.94E-01 |

| 800000  | 40000  | 2.06E+00 |

------------------------------

| 1600000 | 10000  | 8.25E-01 |

| 1600000 | 20000  | 1.85E+00 |

| 1600000 | 40000  | 4.20E+00 |

------------------------------

| 3200000 | 10000  | 1.66E+00 |

| 3200000 | 20000  | 3.64E+00 |

| 3200000 | 40000  | 8.30E+00 |

------------------------------

Commentaire (cliquer pour afficher)

On constate bien sur le tableau que pour un $n$ fixé, le temps de calcul de cherche2 semble proportionnel à $p$, et que pour un $p$ fixé, il semble proportionnel à $n$...

Quelle est la complexité au meilleur de la fonction cherche ?

a : $O(n)$

b : $O(p)$

c : $O(1)$

Correction (cliquer pour afficher)

Le meilleur des cas possible correspond à un mot à cherché placé au tout début du texte. Il faudra alors $p$ comparaisons (la longueur du mot) avant de sortir de la fonction.
D'où $O(p)$ au meilleur.

On peut déterminer ce que fait la fonction cherche en mettant en lumière deux invariants, un pour chaque boucle.
La boucle interne a pour invariant “b équivaut à s[k:k+i]==m[:i]”.
Et la boucle externe a pour invariant “s[j:j+len(m)] != m pour tout j<k” car s’il y avait égalité, on serait sorti de la boucle avec le return True.
On en conclut que si la boucle n’est jamais interrompue par le return True alors m n’est pas un sous-mot de s.
Si la boucle est interrompue, d’après l’invariant de la boucle intérieure, on a trouvé m dans s.

Commentaire (cliquer pour afficher)

Vous trouverez des exemples de calcul de complexité et une démonstration de correction dans la section recensant les défis algorithmiques ( le défi est souvent de réussir à diminuer la classe de complexité en passant d'un algo naïf à un algo plus malin).