Les algorithmes diviser pour régner

Exercice 1 : tests d'efficacité

Nous allons comparer l'efficacité des 3 programmes suivants :

avec l'approche naïve

def recherche_naive(val, tab):
    for i in range(len(tab)):
        if tab[i] == val:
            return True
    return False

avec l'approche dichotomique et liste

def recherche_dicho_liste(val, tab):
    while len(tab) > 0:
        c=(len(tab)-1)//2
        if tab[c] == val:
            return True
        elif tab[c] > val:
            tab = [tab[i] for i in range(c)]
        else:
            tab = [tab[i] for i in range(c+1,len(tab))]
    return False

avec l'approche dichotomique

def recherche_dichotomique(val, tab):
    index_debut = 0
    index_fin = len(tab)-1
    while (index_fin - index_debut) >= 0:
        centre = (index_debut + index_fin)// 2
        if tab[centre] == val:
            return True
        elif tab[centre] > val:
            index_fin = centre - 1
        else:
            index_debut = centre + 1
    return False

Nombre de boucles

Nous allons compter le nombre de boucles dans le pire des cas pour un tableau contenant un million de valeurs.

Copiez et collez les 3 programmes et la ligne suivante :
```
tab=list(range(1000000))
```
Combien y aura-t-il de boucles dans l'approche naïve ?

Dans les approches dichotomiques introduisez une variable etape qui permet de décompter le nombre de boucles.

Voir une solution

Testez ces fonctions avec les paramètres val = -1 et tab = tab.

Temps d'exécution

Nous alons utiliser le module timeit. Ce module fournit une façon simple de mesurer le temps d'exécution de fragments de code Python. Il expose une Interface en ligne de commande ainsi qu'une interface Python. Ce module permet d'éviter un certain nombre de problèmes classiques liés à la mesure des temps d'exécution.

Copiez, puis collez les lignes suivantes à la suite des 3 fonctions.

import timeit
liste=list(range(100))  #tester pour 200, 500
print(timeit.timeit('recherche_dichotomique(-1,liste)', globals=globals()))
print(timeit.timeit('recherche_dicho_liste(-1,liste)', globals=globals()))
print(timeit.timeit('recherche_naive(-1,liste)', globals=globals()))

Testez avec les valeurs 100, 200 et 500.
Analysez et commentez ces résultats.

Exercice 2 : Calcul de puissance

Approche naïve

L'écriture a**n permet de calculer des puissances. Naturellement cette écriture sera interdite dans cet exercice.

Ecrire une fonction puissance de paramètres deux entiers naturels a et n et qui renvoie le nombre aⁿ.
Voir une solution
Voir le code :
```
def puissance(a,n):
    resultat = 1
    for i in range(n):
        resultat = resultat * a
    return resultat
```
Masquer
Combien de boucles sont nécessaire pour calculer puissance(2, 100) ?

Approche diviser pour régner

Voici un programme calculant la puissance utilisant la méthode diviser pour régner :

def exponentiationRapide(nombre,exposant):
    N = exposant
    A = nombre
    resultat = 1
    while N > 0 :
        if N % 2 == 0:
            A = A * A
            N = N // 2
        else :
            resultat = resultat * A
            N = N - 1
    return resultat

Testez cette fonction avec différentes valeurs donnant des résultats connus.
Faites tourner ce programme à la main pour nombre = 2 et exposant = 20.

Introduisez une variable etape qui permet de décompter le nombre de boucles.

Voir une solution

Tests d'efficacité

Copiez, puis collez les lignes suivantes à la suite des 2 fonctions.

import timeit
print(timeit.timeit('puissance(2,100)', globals=globals()))
print(timeit.timeit('exponentiationRapide(2,100)', globals=globals()))

Analysez et commentez ces résultats.

Pour aller plus loin

Monrez la terminaison de la fonction exponentiationRapide en trouvant un variant de boucle.
Voir une solution
Voir le code :
Le variant de boucle est N.
- N est un entier positif
- N est strictement décroisant à chaque itération (on divise par 2 ou on retire 1)
Masquer
Montrez la correction de la fonction exponentiationRapide en utilisant l'invariant de boucle de « nombre^exposant = resultat × A^N ».
Voir une solution
Voir le code :
Correction du programme

Pour prouver la correction du programme, nous allons utiliser un invariant de boucle. Nous allons utiliser l’invariant de boucle suivant: Inv: « nombre^exposant = resultat × A^N »

INITIALISATION : on doit montrer que l'invariant de boucle est vrai avant la première itération de la boucle.
Avant de rentrer dans la boucle, N = exposant, A = nombre, resultat = 1, donc Inv est vérifié.

CONSERVATION : on doit montrer que si l'invariant de boucle est vrai avant une itération de la boucle, il le reste à la fin de l'itération.
On a : nombre^exposant = resultat × A^N à l'entrée de la boucle.
Deux cas sont à examiner:
On note A avant l'itération, A_i, N avant l'itération, N_i et resultat avant l'itération, resultat_i
- Si N_i est pair, alors A = A_i × A_i et N = N_i / 2 et resultat_i = resultat , donc :
  nombre^exposant = resultat_i × A_i^N_i = resultat_i × A_i^2.N_i/2 = resultat_i × (A_i²)^N_i/2 = resultat_i × (A_i × A_i)^N_i/2 = resultat × A^N
- Si N_i est impair, alors A = A_i, resultat = resultat_i * A_i et N = N_i - 1, donc :
  nombre^exposant = resultat_i × A_i^N_i = resultat_i × A_i × A_i^N_i-1 = resultat × A^N
Donc Inv est encore vrai à la sortie de la boucle.

TERMINAISON : A la sortie de la boucle, on a nombre^exposant = resultat × A^N avec N = 0, soit nombre^exposant = resultat.

Masquer