Cette séance présente quelques techniques ou algorithmes fondamentaux, dont il est bon de connaître l’existence, la complexité ainsi que quelques applications.
Note
Complexité des opérations élémentaires
Note
Le calcul naïf de \(a^n\) fait intervenir \(n\) multiplications. En écrivant
on remarque que l’on peut économiser environ la moitié des multiplications pour le prix d’une mise au carré. On peut appliquer cette idée récursivement.
Pour développer cette idée, décomposons \(n\) en base deux
on peut écrire
ou bien
Dans un cas comme dans l’autre, l’expression ne fait plus intervenir que \(k\) multiplications au plus et \(k\) carrés, avec \(k=\ceil{\log_2(n)}\).
Écrire la fonction pow_naif(a,n) qui calcule \(a^n\) de manière
récursive.
pow_naif(a,n):={
if(n==0) return(1);
return( a*pow_naif(n-1) );
}
Écrire une fonction pow_rec(a,n) qui calcule \(a^n\)
par exponentiation rapide de manière récursive.
La tester en calculant pow_rec(a,19).
Il y a deux solutions à ce problème, selon l’endroit où l’on prend le carré:
pow_rec(a,n):= {
if(n==0) return 1;
if(irem(n,2)) return a*pow_rec(a,iquo(n,2))^2;
return pow_rec(a,n/2)^2;
}
ou bien:
pow_rec(a,n):= {
if(n==0) return 1;
if(irem(n,2)) return a*pow_rec(a^2,iquo(n,2));
return pow_rec(a^2,n/2);
}
Il y a deux solutions à ce problème, selon l’endroit où l’on prend le carré:
def pow_rec(a,n):
if n==0: return 1
r = pow_rec(a^2,n//2)
if n%2:
return r*a
else:
return r
ou bien:
def pow_rec(a,n):
if n==0: return 1
r = pow_rec(a,n//2)^2
if n%2:
return r*a
else:
return r
Écrire la fonction pow_iter(a,n) qui effectue le même calcul
de manière itérative.
pow_iter(a,n):= {
local(r:=1);
while(n>0) {
if (n%2==1) {r := r*a};
a := a^2;
n := iquo(n,2);
};
return(r);
}
Si l’on ne veut pas calculer a priori la décomposition binaire de \(n\), la solution la plus simple correspond au premier algorithme récursif.
def pow_iter(a,n):
r = 1
while n>0:
if n%2:
r *= a
a = a^2
n = n//2
return r
Exemple à retenir : quel est le coût du calcul des trois derniers chiffres de \(3^{123456789}\) ?
Pour obtenir les trois derniers chiffres, il faut prendre le reste modulo 1000. Et puisque la projection \(\Z\to \Z/1000\Z\) est un morphisme d’anneaux, il faut surtout effectuer tout le calcul modulo 1000 en écrivant:
pow_rec(3%1000,123456789)
et non pas prendre le reste à la fin, ce qui demande de calculer un nombre gigantesque (ce que Xcas ne peut pas faire):
pow_rec(3,123456789) % 1000
En faisant bien les choses, la complexité du calcul est réduite à une exponentiation rapide de
On considère la suite classique \(f_0=f_1=1\), \(f_{n+1}=f_n+f_{n-1}\).
Programmer le calcul récursif naïf de la suite. Quelle est sa complexité ? Calculer \(f_{34}\).
def fib_naif(n):
if n<2: return 1
return fib_naif(n-1)+fib_naif(n-2)
La complexité du calcul obéit à la même récurrence, si bien que le calcul de \(f_n\) est de complexité \(O(f_n)\), donc exponentielle en \(n\).
Programmer le calcul des \(f_n\) à l’aide d’une fenêtre glissante. Quelle est la complexité ? Calculer \(f_{10^5}\).
Il s’agit de conserver à chaque étape les deux dernières valeurs pour ne pas les recalculer.
def fib_glis(n): ff = (1,1) for i in xrange(n-1): ff = (sum(ff),ff[0]) return ff[0] fib_glis(10^5)
À présent la complexité fait intervenir \(n\) additions de taille croissant linéairement vers \(n\), ce qui fait une complexité quadratique \(O(n^2)\).
En écrivant la récurrence linéaire
et l’expression de \(F_n=A^nF_0\), calculer à nouveau \(f_{10^5}\). Quelle est la complexité du calcul, pourquoi ?
def fib_mat(n):
A = matrix(2,2,[1,1,1,0])
F0 = vector([1,1])
return (A^n*F0)[0]
fib_mat(10^4)
fib_mat(n):={ local(A); A := matrix(2,2,[1,1,1,0]); return( (A^n)[0,0] ); };
La complexité est à présent de \(O(\log(n))\) multiplications matricielles \(2\times 2\), d’entiers dont la taille croît en \(O(n)\), d’où une complexité dominée par les derniers produits en \(O(n\log(n)\log\log n)\)
Comparer les temps de calcul de \(f_{2^{25}-1}\) et \(f_{2^{25}}\), commenter.
Rappeler comment on obtient l’expression algébrique exacte
et utilisez-la pour calculer \(f_n\).
phi := (1+sqrt(5))/2;
fib_alg(n) := simplify( (phi^(n+1)-(1-phi)^(n+1))/sqrt(5) );
Pour le logiciel, cela revient à effectuer les mêmes calculs qu’avec la matrice.
Quel est le nombre de chiffres de \(f_{f_{f_{f_{f_4}}}}\) ?
Cette technique reprend aussi le principe diviser pour régner : il s’agit de résoudre un problème en le décomposant en deux sous-problèmes de complexité inférieure et comparable.
Écrire une fonction fact(n) qui calcule la factorielle de \(n\). Quelle est sa
complexité binaire ?
def fact(n):
if n<=1: return 1
return n*fact(n-1)
def fact(n):
return prod( k for k in xrange(1,n) )
Avec une solution récursive
fact(n):= {
if(n==0) return(1);
return(n*fact(n-1));
}
ou bien de manière itérative:
fact(n):= {
local(r:=1);
for(k:=2;k<=n;k++) { r:= r*k; }
return(r);
}
Implanter la variante de binary splitting, qui consiste à faire uniquement des multiplication entre opérandes de même taille en écrivant
Quelle est la complexité ? Comparer les temps d’exécution pour \(200000!\).
def fact_bin(n2,n1=1):
""" computes recursively n2!/n1! """
if n1 == n2: return n1
mid = (n2+n1)>>1
if mid == n1: return n1*n2
return fact_bin(n2,mid)*fact_bin(mid-1,n1)
On écrit une fonction qui calcule récursivement \(\frac{n_2!}{n_1!}\)
fact_split(n2,n1):= {
if(n2==n1) return(1);
if(n2==n1+1) return(n2);
local(mid:=iquo(n1+n2,2));
return( fact_split(n2,mid)*fact_split(mid,n1) );
}
Vérifier l’identité de Karatsuba
et compter le nombre de multiplications et d’additions qu’elle fait intervenir par rapport au développement usuel du membre de gauche.
Au lieu de 4 multiplications et 1 addition dans le produit classique, cette identité fait intervenir 3 multiplications et 4 additions.
Soient \(P\) et \(Q\) deux polynômes de \(\K[x]\) de degré \(d=2^n\). La multiplication de Karatsuba consiste à écrire l’identité ci-dessus en posant d’abord \(X=x^{d/2}\), puis à réappliquer récursivement la même méthode pour chacun des produits de taille \(d/2=2^{n-1}\).
Écrire une fonction karatsuba(n) qui compte le nombre de multiplications
de \(\K\) nécessaires pour effectuer le produit de \(P\) et \(Q\).
karatsuba(n):= {
if(n==0) return(3);
return(3*karatsuba(n-1));
};
Quelle est la complexité de la multiplication de Karatsuba ?
Pour des entiers de \(n\) bits, on effectue une descente récursive de longueur \(\log_2{n}\), soit \(3^{\log_2 n}\) multiplications élémentaires (et de l’ordre de \(7^{\log_2n}\) additions que l’on négligera), donc la complexité est de \(O(n^{\log_2(3)})=O(n^{1.59})\).
Note
Le schéma d’évaluation de Hörner consiste à écrire
ce qui permet de calculer la valeur \(P(x)\) à l’aide de \(n\) multiplications et additions.
Remarquer la similitude avec l’exponentiation rapide.
horner(P,a) qui évalue le polynôme \(P\) en \(a\). La tester.Pour calculer numériquement la racine carrée de \(a\), on définit la suite
Écrire une procédure Newton(a) qui effectue dix itérations de cette suite, et
affiche à chaque étape \(n\) les décimales communes à \(x_n\) et
\(x_{n-1}\). On fera le calcul en précision 200.
Le nombre de décimales communes à deux nombres est le log en base 10 de leur différence relative.
1 2 3 4 5 6 7 8 9 10 11 12 13 | Digits:=200;
Newton(a) := {
local(b:=1);
local(c:=0);
local(k);
local(n);
for(k:=0;k<5;k++) {
c := b;
b := evalf((b+a/b)/2);
n := floor(1-logb(abs((c-b)/c),10));
if(n>0) print( left(string(c),n) );
};
};
|
Quelle est la vitesse de convergence de la suite ? Combien d’itérations faut-il pour obtenir un million de chiffres de \(\sqrt{5}\) ?
La précision double à chaque itération, la suite converge exponentiellement vite en nombre de chiffres corrects.
Il faut seulement \(\log_2(10^6)\approx20\) itérations pour obtenir un million de décimales de \(\sqrt{5}\).