LyonHPC LyonHPC

12. Efficacité / complexité

cloud
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np

12.1. Recherche d’un élément dans un tableau trié

Soit X un tableau contenant n valeurs triées, i.e: X[0]<X[1]<…<X[n-1]
on veut déterminer l’indice k d’un élément a, i.e: X[k]=a

12.1.1. algorithme de recherche linéaire

  • on parcours toute la liste en partant du premier élément pour chercher a

  • dans le pire des cas, on fait n itérations

  • un test par itération \(\Rightarrow\) n opérations

algorithme avec une efficacité linéaire: \(O(n)\)

def linsearch(a,X):
    """ recherche de  a dans le tableau X 
        retour: valeur de l'indice k tq X[k]=a, ou -1 si non trouvé 
    """
    n = len(X)
    k = -1
    for i in range(n):
        if X[i]==a :
            k = i
            break
    return k
# application
X=np.arange(10)
print(linsearch(5,X))
print(linsearch(10,X))
5
-1

12.1.3. comparaison de l’efficacité des 2 algorithmes de trie

run courbe1.py
../_images/Efficiency_8_0.png

\(\Rightarrow\) pour n grand l’algorithme de trie par bisection est beaucoup plus efficace

12.2. Complexité et efficacité d’un algorithme

théorie de la complexité: analyse d’un algorithme en vue de déterminer les ressources nécessaire (en temps CPU, en taille mémoire,..) pour l’exécuter en fonction des données (taille des données, paramètre de précision).

efficacité = estimation asymptotique de la complexité en temps sur une machine idéale (machine de Turing) en fonction d’un paramètre n caractérisant les entrées (taille des entrées, nbre de digits pour la précision,..)

attention cette analyse n’est qu’indicative, et peut être remise en question suivant l’architecture des machines (machines parallèles)

12.2.1. Différentes classes de compléxité (classées par efficacité)

type

complexité

example

constante

\(O(1)\)

accés à un tableau: X[i]

logarithmique

\(O(\log{n})\)

trie par dichotomie (binary search)

linéaire

\(O(n)\)

parcours de tableaux

linéarithmique

\(O(n\log{n}\)

methode multigrille

quadratique

\(O(n^2)\)

produit matrice x vecteur

cubique

\(O(n^3)\)

produit matrice x matrice

exponentielle

\(O(2^{n^p})\)

factorielle

\(O(n!)\)

calcul déterminant d’une matrice (force brute)

run courbe2.py
../_images/Efficiency_12_0.png

12.3. Exemples

12.3.1. algorithme inefficace: déterminant de Cramer

Calcul du déterminant d’une matrice \(A\) par la méthode de Cramer

  • formule récursive de calcul par développement par rapport à la première colonne

\[ det(A) = \sum_{j=1}^n A_{1,j} (-1)^{1+j} det(A^{1,j}) \]
  • \(A^{1,j}\) matrice d’ordre n-1 obtenue en enlevant la colonne 1 et la ligne i de \(A\)

  • calcul det(A) = somme de n déterminants d’ordre (n-1)

\(\Rightarrow\) algorithme avec une efficacité factorielle: \(O(n!)\)

# nbre d'operations
nops = 0
# algorithme déterminant
def determinant(A):
    """ Calcul du déterminant de A """
    global nops
    n=shape(A)[0]
    if n==1:
        return A[0,0]
    else:
        det =0.0
        coef=1.0
        # developement par rapport a la ligne 0
        for i in range(n):
            A1 = delete(delete(A,0,0),i,1)
            det = det + coef*A[0,i]*determinant(A1)
            coef = -coef
        nops += 3*n
        return det
# test d'utilisation avec timing
from time import process_time
N=range(5,10)
# boucle de timing 
for k,n in enumerate(N):
    A=random.rand(n,n)
    nops = 0
    debut= process_time()
    det1 = determinant(A)
    cpu  = process_time() - debut
    print("n=%d nops=%10d cpu=%12.6g s"%(n,nops,cpu))
n=5 nops=       615 cpu=  0.00821504 s
n=6 nops=      3708 cpu=   0.0771273 s
n=7 nops=     25977 cpu=    0.347297 s
n=8 nops=    207840 cpu=       2.727 s
n=9 nops=   1870587 cpu=     20.0721 s

\(\Rightarrow\) algorithme inutilisable !!!!
\(\Rightarrow\) utiliser l’algorithme de la bibliothéque numpy basé sur une factorisation \(LU\) de \(A\)

print(shape(A))
%timeit linalg.det(A)
(9, 9)
16.3 µs ± 20.4 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

12.3.2. Exemple: recherche de la racine d’une fonction

Calcul d’une valeur approchée \(x^n\) de la racine \(x^*\) d’une fonction \(f(x)\):

\[ \left| x^* - x^n \right| < \epsilon \mbox{ avec } f(x^*)=0 \]

Le nombre de chiffres significatifs \(P\) de \(x^n\) est donnée par \(P= -\log(\epsilon)\)
On compare l’efficacité de 2 algorithmes en fonction de \(P\)
On suppose que l’on a un intervalle \([a,b]\) contenant la racine \(x^*\)

12.3.2.1. Méthode de dichotomie

  • algorithme itératif de dichotomie

  • on choisit comme approximation le milieu de l’intervalle

  • à chaque itération: erreur divisée par 2 , 4 opérations + 1 appel de fonction \(\Rightarrow\) erreur divisée par \(2^n\) au bout de n iterations

efficacité linaire \(O(P)\) car le coût \(\approx C*P + K \)

# Algorithme Dichotomie
def Dichotomie(F,a,b,eps):
    """ calcul la racine de F(x) comprise entre a et b par dichotomie
        F(x) est une fonction , eps = précision """
    nit = 0
    ya = F(a)
    yb = F(b)
    x  = (a+b)/2.0
    while (b-a)>eps :
        x = (a+b)/2.
        y = F(x)
        if y*ya > 0:
            a=x
            ya=y
        else:
            b=x
            yb=y
        nit = nit + 1
    return x,nit
# application
F = cos
xs = pi/2.
x,it = Dichotomie(F,pi/3,3*pi/4,1.e-08)
print("racine %g  nit=%d  err=%g"%(x,it,abs(x-xs)))
racine 1.5708  nit=27  err=1.95056e-09

12.3.2.2. Méthode de Newton

  • à partir de \(x_0\), on approxime la courbe par sa tangente en \(x_0\)

  • nouvelle approximation \(x_1\) = intersection tangente avec l’axe des x

\[ x_1 = x_0 - \frac{F(x_0)}{F'(x_0)}\]
  • l’erreur \(err_1 = x_1 -x^*\) vérifie après D.L. de \(F(x_0)\)

\[ err_1 = err_0 - \frac{F(x_0)}{F'(x_0)} \approx \frac{1}{2}\frac{F''(x_0)}{F'(x_0)}({err_0})^2 + ..\]
  • soit au bout de \(n\) itérations \(err_n \approx (err_0)^{2^n} \)

Efficacité logarithmique \(O(\log P)\) car coût \(\approx C \log P + K\)

run newton.py
../_images/Efficiency_21_0.png
# Algorithme de Newton
def Newton(F,dF,a,b,eps):
    """ calcul la racine de F(x) par la methode de Newton
        F(x) fonction, dF dérivée, a b intervalle d'étude , eps = précision """
    nit = 0
    x   = (a+b)/2.
    err = F(x)/dF(x)
    while abs(err) > eps:
        x   = x - err
        err = F(x)/dF(x)
        nit = nit + 1
    return x,nit
# application
F  = lambda x:  cos(x)
dF = lambda x: -sin(x)
xs = pi/2.
x,it = Newton(F,dF,pi/3,3*pi/4,1.e-08)
print("racine %g  nit=%d  err=%g"%(x,it,abs(x-xs)))
racine 1.5708  nit=2  err=1.42208e-10

12.3.2.3. Conclusion

La méthode de Newton est beaucoup plus efficace que la méthode de dichotomie
Attention cependant, la convergence de la méthode de Newton est uniquement locale !!!

12.4. FIN de la leçon

cloud