L’objectif du TP est de présenter quelques algorithmes dichotomiques, qui font partie des algorithmes basés sur le principe diviser pour régner (ou divide and conquer en anglais). Ces algorithmes ont pour avantage d’être plus performants que les algorithmes naı̈fs. Leur force est de ramener la résolution d’un problème dépendant d’un entier
n
à la résolution d'un ou plusieurs sous-problèmes identiques portant sur des entiersn'
strictement inférieur àn
. Ce TP est composé de 2 parties indépendantes. Dans la première, nous allons travailler sur la recherche dichotomique d’un élément dans une liste triée, alors que dans la deuxième nous calculerons de grandes puissances d’un flottant.
Le but de cette partie est de trouver si un entier
val
est présent dans une liste triéeL
. On considère ici queL
est composée den
entiers inférieurs àM
.
Q1. Implémenter L
pour n=10**3
et M=10**9
comme suit L = [ randint(0, M) for i in range(n) ]
sans oublier
d’importer la fonction randint
via from random import randint
.
Trier ensuite la liste à l’aide de la méthode L.sort()
.
# Cellule à compléter
from random import randint
L = [ randint(0, 10**9) for i in range(10**3) ]
print(L[:10]) # on affiche les 10 premiers éléments
L.sort()
print(L[:10]) # on affiche les 10 premiers éléments
[489667552, 712108270, 336509712, 486065694, 544383934, 950445754, 547044582, 131221649, 989151413, 525327411] [1474169, 3760264, 4033458, 4419673, 4649342, 5439003, 6478294, 6517926, 7178435, 7691567]
Q2. Proposer une fonction recherche_naive(L,val)
prenant en argument une liste triée L
et une valeur val
à rechercher dans celle-ci qui renvoie True
si la valeur est présente et False
sinon.
On commence par réaliser un algorithme naı̈f qui parcourt l’ensemble des valeurs de la liste.
# Cellule à compléter
def recherche_naive(L, val) :
flag = False
for x in L :
if x == val :
flag = True
return flag
# Cellule pour tests unitaires
print(recherche_naive( [1, 2, 3, 4], 3) == True)
print(recherche_naive( [1, 2, 3, 4], 0) == False)
True True
Q3. On peut réaliser une optimisation:
en effet la liste étant triée, on peut sortir de la boucle de recherche dès que la valeur courante de la liste est strictement supérieure à la valeur recherchée.
Mettre en place cette optimisation puis proposer un jeu de tests unitaires pour valider votre algorithme.
# Cellule à compléter
def recherche_naive2(L, val) :
n = len(L)
i = 0
flag = False
while i < n and L[i] <= val :
if L[i] == val :
flag = True
i = i + 1
return flag
# Cellule pour tests unitaires
print(recherche_naive2( [1, 2, 3, 4], 3) == True)
print(recherche_naive2( [1, 2, 3, 4], 0) == False)
True True
Q4. On propose à présent d’étudier la recherche dichotomique.
La liste étant triée, l’idée est de tester si le terme du milieu de la liste est inférieur strictement, supérieur strictement ou égal à la valeur recherchée.
True
,On itère jusqu’à ce que l’intervalle de recherche soit vide.
On peut constater que la taille de ce
dernier est divisée par deux à chaque itération.
Proposer une fonction recherche_dicho(L, val)
basée sur cette méthode en utilisant une boucle while
de condition ind_max-ind_min >= 0
où ind_min
et ind_max
représentent respectivement l’indice minimal et
maximal de l’intervalle de recherche.
# Cellule à compléter
def recherche_dicho(L, val) :
ind_min = 0
ind_max = len(L) - 1
flag = False
while not(flag) and ind_max - ind_min >= 0 :
ind_milieu = (ind_min + ind_max) // 2
if L[ind_milieu] == val: # on a trouvé val dans la liste L
flag = True
elif L[ind_milieu] < val : # val est dans la sous-liste de droite
ind_min = ind_milieu + 1
else : # val est dans la sous-liste de gauche
ind_max = ind_milieu - 1
return flag
Q5. Définir un jeu de tests unitaires utilisant la liste L
de Q1. pour valider votre algorithme.
# Cellule pour tests unitaires
print(recherche_dicho( [1, 2, 3, 4], 3) == True)
print(recherche_dicho( [1, 2, 3, 4], 0) == False)
print("L'algorithme fonctionne si la valeur est avant la borne inférieure : ",\
recherche_dicho(L, -2) == False)
print("L'algorithme fonctionne si la valeur est après le max : ", recherche_dicho(L, L[-1]+1) == False)
print("L'algorithme fonctionne si la valeur est présente : ", recherche_dicho(L, L[1]) == True)
print("L'algorithme fonctionne si la valeur est non présente à l'intérieur : ",\
recherche_dicho(L, L[-1] - 0.5) == False )
True True L'algorithme fonctionne si la valeur est avant la borne inférieure : True L'algorithme fonctionne si la valeur est après le max : True L'algorithme fonctionne si la valeur est présente : True L'algorithme fonctionne si la valeur est non présente à l'intérieur : True
Q6. On considère à présent une liste de taille plus significative, par exemple pour n = 10**6
. On s’intéresse aux
temps de calcul des algorithmes ci-dessus. Le code suivant permet d’afficher le temps de calcul de votre
fonction :
from time import time
start = time() # on sauvegarde le nombre de secondes écoulées depuis le 1er janvier 1970 0h 0mn 0s
fonction(L , val) # on exécute une fonction d'arguments L et val
end = time () # on sauvegarde le nouveau nopmbre de secondes
print(end - start) # on affiche le temps d'exécution de notre fonction
Comparer les temps de calcul des recherches naı̈ve, dichotomique et celle interne de Python ( val in L
).
# Cellule à compléter
from time import time
M = 10**9
n = 10**6
L = [ randint(0, M) for i in range(n) ]
L.sort()
start = time()
recherche_naive(L, L[10**5])
end = time()
print('Temps de recherche pour la méthode naı̈ve : '+ str(end - start))
start = time()
recherche_naive2(L, L[10**5])
end = time()
print('Temps de recherche pour la méthode naı̈ve améliorée : '+ str(end - start))
start = time()
recherche_dicho(L, L[10**5])
end = time()
print('Temps de recherche pour la méthode dichotomique : '+ str(end - start))
start = time()
L[10**5] in L
end = time()
print ('Temps de recherche pour la méthode de Python : '+ str(end - start))
Temps de recherche pour la méthode naı̈ve : 0.11403346061706543 Temps de recherche pour la méthode naı̈ve améliorée : 0.015859127044677734 Temps de recherche pour la méthode dichotomique : 3.314018249511719e-05 Temps de recherche pour la méthode de Python : 0.0023055076599121094
On remarque que la méthode dichotomique est la plus efficace.
Dans le pire des cas (si la valeur n’est pas dans la liste) l’algorithme naïf parcourt la boucle while
entièrement et donc effectue un nombre de comparaisons proportionnel à $n$ où $n$ est la taille de la liste.
Par ailleurs, l’algorithme dichotomique va diviser
la taille de la liste en deux jusqu’à atteindre une liste vide. En notant $k$ le nombre de fois où la boucle
while
est appelée, on a $2k \leq n$ i.e. $k \leq\log_2 (n)$. Le nombre de comparaisons dans le pire des cas est donc
proportionnel à $\log_2 (n)$ dans la méthode dichotomique.
On dit que la complexité de l'algorithme naıïf est linéaire alors que celle de l’algorithme dichotomique est logarithmique.
Q7. Pour les plus rapides. En modifiant les fonctions recherche_naive
et recherche_dicho
à l’aide d’un
compteur, proposer deux nouvelles fonctions complexite_dicho
et complexite_naive
renvoyant le nombre
de comparaisons réalisées lors de ces recherches.
# Cellule à compléter
def complexite_naive(L, val) :
n = len(L)
flag = False
i = 0
compteur = 0
while i < n and L[i] <= val :
if L[i] == val :
flag = True
i = i + 1
compteur = compteur + 2 # on a fait 2 tests
return compteur + 1 # on ajoute le test de sortie de boucle
def complexite_dicho(L, val) :
ind_min = 0
ind_max = len(L) - 1
flag = False
compteur = 0
while not(flag) and ind_max - ind_min >= 0 :
ind_milieu = (ind_min + ind_max) // 2
compteur = compteur + 1
if L[ind_milieu] == val:
flag = True
compteur = compteur + 1
elif L[ind_milieu] < val :
ind_min = ind_milieu + 1
compteur = compteur + 2
else :
ind_max = ind_milieu - 1
compteur = compteur + 2
return compteur + 1
# Cellule pour tester
print( complexite_naive(L, L[10**4]) )
print( complexite_dicho(L, L[10**4]) )
20003 51
Q8. Pour les plus rapides. On souhaite comparer complexite_dicho
et complexite_naive
en fonction de
la taille de la liste en argument. Mettre en place une série d’instructions générant deux listes : C_naive
et
C_dicho
, contenant les nombres de comparaisons dans le pire des cas lors de la recherche dans une liste de
taille $i$ pour $i$ allant de $1$ à $100$.
Représenter ces deux listes à l’aide des instructions suivantes :
import matplotlib.pyplot as plt
plt.figure()
plt.plot([ i for i in range (1 ,10**2)], C_naive)
plt.plot([ i for i in range (1 ,10**2)], C_dicho)
plt.axis('scaled')
plt.show()
# Cellule à compélter
import matplotlib.pyplot as plt
C_naive = []
C_dicho = []
for i in range(1, 10**2) :
C_dicho.append( complexite_dicho(L[:i], L[i]+1) )
C_naive.append( complexite_naive(L[:i ], L[i ]+1) )
plt.figure()
plt.plot([ i for i in range (1 ,10**2) ], C_dicho )
plt.plot([ i for i in range (1 ,10**2) ], C_naive )
plt.xlabel('Taille de la liste')
plt.ylabel('Nombre de comparaisons')
plt.axis('scaled')
plt.show()
Q9. Pour les plus rapides. Mettre en évidence la complexité logarithmique de l’algorithme dichotomique.
On utilise la fonction complexite_dicho
qui donne le nombre de comparaisons (critère qu'on a choisi pour l'étude de complexité).
# Cellule à compléter
import math
C_dicho = []
for i in range (1, 10**4) :
C_dicho.append( complexite_dicho(L[:i], L[i] + 1) )
plt.figure()
plt.plot([ i for i in range (1 ,10**4) ], C_dicho )
plt.plot([ i for i in range (1 ,10**4) ], [3*math.log(i, 2) for i in range(1, 10**4)] )
# le facteur 3 vient du fait que dans le pire des cas on fait 3 comparaisons par tour de boucle
plt.xlabel('Taille de la liste')
plt.ylabel('Nombre de comparaisons')
plt.show()
Le but de cette partie est de calculer de manière efficace $x^y$ où $x$ est un flottant et $y$ un entier naturel.
Q10. Proposer une fonction puissance_naive(x,y)
prenant en argument un flottant x
et un entier positif y
, et
qui renvoie la valeur de $x^y$. On commence par réaliser un algorithme naı̈f sans utiliser **
.
# Cellule à compléter
def puissance_naive(x, y) :
result = 1
for k in range(1, y+1) : # k va de 1 à y
result = result * x
return result
# Cellule pour tests unitaires
print( puissance_naive(2, 3) == 8)
print( puissance_naive(2, 0) == 1)
True True
Q11. On propose à présent d’étudier l'exponentiation rapide.
Notons $(y_0,\dots,y_n)$ les chiffres (0 ou 1) de l’écriture binaire de $y$. Alors $y =\displaystyle\sum_{k=0}^ny_k2^k$ et donc $x^y=\displaystyle\prod_{k=0}^n\left(x^{2^k}\right)^{y_k}$.
En notant $a_k = x^{2^k}$, il se trouve que $a_0 = x$ et que $a_{k+1} = a_k^2.$
Le principe de la méthode de l'exponentiation rapide consiste à calculer pas à pas le produit $x^y =\displaystyle\prod_{k=0}^na_k^{y_k}$
Noter qu'on n'effectue aucune puissance dans ce produit car les $y_k$ sont égaux à $0$ ou $1$.
Illustrons ce produit sur un exemple. Pour $y = 13$, comme $13 = \overline{1101}^2$, on a $y_3 = y_2 = y_0 = 1$ et $y_1 = 0$. D'où
$${\large x^{13} = x^{1\times 2^0 +0\times2^1 +1\times 2^2 +1\times2^3} = (x)^1\times (x^2 )^0 \times (x^4 )^1 \times (x^8 )^1 = a_0^{ y_0} \times a_1^{ y_1} \times a_2^{ y_2} \times a_3^{ y3} = a_0 \times a_2 \times a_3}$$
En vous basant sur cette méthode, proposer une fonction exp_rapide(x,y)
ayant le même objectif que
puissance_naive(x,y)
. On pourra utiliser la fonction bin
de python pour l’écriture binaire de y mais on
s’interdira encore d’utiliser **
.
def exp_rapide(x,y) :
biny = bin(y)
biny = biny[2:] # on enlève le préfixe 0b
biny = biny[::-1]
# on inverse l'ordre des chiffres et on a donc biny[k] qui correponds à y_k de l'énoncé
a = x
if biny[0] == '1' :
result = x
else :
result = 1
for k in range(1, len(biny)) :
a = a*a
if biny[k] == '1':
result = result * a
return result
# Cellule pour tester
print( exp_rapide(2, 3) == 8)
print( exp_rapide(2, 0) == 1)
True True
Q12. Proposer un jeu de tests unitaires pour vos deux fonctions calculant $x^y$. Comparer ensuite les temps de
calcul de vos algorithmes pour $x = 1 + 10^{-7}$ et $y = 10^7$. On pourra également comparer avec x**y
.
# Cellule à compléter
from time import time
x = 1+10**(-7)
y = 10**7
start = time()
puissance_naive(x ,y)
end = time()
print('Temps de calcul pour la méthode naı̈ve : '+str( end - start ) )
start = time()
exp_rapide(x, y)
end = time()
print('Temps de calcul pour l\'exponentiation rapide : '+str( end - start) )
start = time()
x**y
end = time()
print('Temps de calcul pour la méthode de Python : '+str( end - start ) )
Temps de calcul pour la méthode naı̈ve : 0.2531118392944336 Temps de calcul pour l'exponentiation rapide : 3.4332275390625e-05 Temps de calcul pour la méthode de Python : 2.2411346435546875e-05
On remarque que l’exponentiation rapide est plus efficace.
En effet, il y a $y- 1$ produits à effectuer dans la méthode naïve ($x\times\dots\times x$) alors qu’il y a moins de $2n$ produits dans l’exponentiation rapide ($a_{k+1} = a_k\times a_k$ et $x^y = a_0^{y_0}\times\dots\times a_n^{y_n}$). Or $n + 1$ correspond au nombre de chiffres dans l’écriture binaire de $y$, d’où $2n \leq y$ i.e. $n \leq \log_2 (y)$. Ce qui prouve que la complexité de la méthode naïve est linéaire alors que celle de l’exponentiation rapide est logarithmique.
Q13. Pour les plus rapides. En modifiant les fonctions puissance_naive
et exp_rapide
à l’aide d’un compteur, proposer deux nouvelles fonctions puissance_naive_c
et exp_rapide_c
renvoyant le nombre de
produits réalisés lors de ces algorithmes.
# Cellule à compléter
def puissance_naive_c(x, y) :
result = 1
compteur = 0
for k in range(1, y+1) : # k va de 1 à y
result = result * x
compteur = compteur + 1
return compteur
def exp_rapide_c(x,y) :
biny = bin(y)
biny = biny[2:] # on enlève le préfixe 0b
biny = biny[::-1]
# on inverse l'ordre des chiffres et on a donc biny[k] qui correponds à y_k de l'énoncé
a = x
compteur = 0
if biny[0] == '1' :
result = x
else :
result = 1
for k in range(1, len(biny)) :
a = a*a
compteur = compteur + 1
if biny[k] == '1':
result = result * a
compteur = compteur + 1
return compteur
# Cellule pour tester
x = 1+10**(-7)
y = 10**7
print(puissance_naive_c(x, y))
print(exp_rapide_c(x,y))
10000000 31
Q14. Pour les plus rapides. On souhaite comparer puissance_naive_c
et exp_rapide_c
en fonction de la
taille de $y$.
Mettre en place une série d’instructions générant deux listes : L_naive
et L_exp
, contenant les nombres de
produits lors du calcul de $x^y$ pour $y$ allant de $1$ à $100$. On prendra $x = 1 + 10^{-7}$.
Représenter ces deux listes à l’aide d’un graphique puis mettre en évidence la complexité logarithmique de
l’exponentiation rapide.
# Cellule à compléter
L_naive =[]
L_exp = []
x = 1+10**(-7)
for i in range (1, 10**2) :
L_exp.append( exp_rapide_c(x, i) )
L_naive.append( puissance_naive_c(x, i) )
plt.figure()
plt.plot([ i for i in range (1 ,10**2) ], L_exp)
plt.plot([ i for i in range (1 ,10**2) ], L_naive)
plt.xlabel('y')
plt.ylabel('Nombre de produits')
plt.axis('scaled')
plt.show ()