Corrige TD03
Corrige TD03
Corrige TD03
Pb n2 c Pn−1−b n c
On pose alors B[X] = i=0 pi X i et A[X] = i=0 2 pi+1+b n2 c X i . A[X] et B[X] sont alors
n
deux polynômes de degré au plus b n2 c et P [X] = A[X]X 1+b 2 c + B[X]. On définit de même les
n
polynômes C et D pour Q : Q[X] = C[X]X 1+b 2 c + D[X].
Avec les notations précédemment définies, on a :
n
P [X]Q[X] = A[X]C[X]X 2+2b 2 c
n
+((A[X] + B[X])(C[X] + D[X]) − A[X]C[X] − B[X]D[X])X 1+b 2 c
+C[X]D[X].
Par conséquent, le produit de deux polynômes de degré au plus n peut se ramener au calcul de
trois produits de polynômes de degré au plus b n2 c (A[X]C[X], B[X]D[X] et (A[X]+B[X])(C[X]+
D[X])), à des additions de polynômes de degré au plus n —ce qui coûte Θ(n)— et à des multipli-
cations par un monôme X j —ce qui est un simple décalage des indices et coûte également Θ(n).
L’équation de récurrence définissant la complexité de notre algorithme est alors :
n
T (n) = 3T + Θ(n).
2
Nous appliquons alors le théorème vu en cours :
1
Théorème 1 (Résolution des récurrences « diviser pour régner »).
Soient a ≥ 1 et b > 1 deux constantes, soit f (n) une fonction et soit T (n) une fonction définie
pour les entiers positifs par la récurrence :
T (n) = aT (n/b) + f (n),
où l’on interprète n/b soit comme bn/bc, soit comme dn/be.
T (n) peut alors être bornée asymptotiquement comme suit :
i. Si f (n) = O(n(logb a)− ) pour une certaine constante > 0, alors T (n) = Θ(nlogb a ).
ii. Si f (n) = Θ(nlogb a ), alors T (n) = Θ(nlogb a log n).
iii. Si f (n) = Ω(n(logb a)+ ) pour une certaine constante > 0, et si af (n/b) ≤ cf (n) pour une
constante c < 1 et n suffisamment grand, alors T (n) = Θ(f (n)).
Ici a = 3, b = 2 et f (n) = Θ(n). Comme log2 3 > 1, nous nous trouvons dans le cas i) du théorème
et donc
T (n) = Θ nlog2 3 .
Pour fixer les idées, log2 3 ≈ 1, 58 et l’algorithme naı̈f de multiplications de polynômes est en
Θ(n2 ).
(b) Le second algorithme devra séparer les coefficients du polynôme d’entrée selon la parité de leur
indice.
n
X
P [X] = pi X i
i=0
X X
= pi X i + pi X i
i pair i impair
bn
2c b n−1
2 c
X X
2i
= p2i X + p2i+1 X 2i+1
i=0 i=0
bn
2c b n−1
2 c
X X
2i
= p2i X +X p2i+1 X 2i
i=0 i=0
Pb n−1
2 c
Pb n2 c
On pose alors A[X] = i=1 p2i+1 X i et B[X] = i=0 p2i X i . A[X] et B[X] sont alors deux
polynômes de degré au plus b n2 c et P [X] = A[X 2 ]X + B[X 2 ]. On définit de même les polynômes
C et D pour Q : Q[X] = C[X 2 ]X + D[X 2 ].
Avec les notations précédemment définies on a :
P [X]Q[X] = A[X 2 ]C[X 2 ]X 2
+((A[X 2 ] + B[X 2 ])(C[X 2 ] + D[X 2 ]) − A[X 2 ]C[X 2 ] − B[X 2 ]D[X 2 ])X
+B[X 2 ]D[X 2 ]
Par conséquent, le produit de deux polynômes de degré au plus n peut se ramener au calcul de
trois produits de polynômes de degré au plus b n2 c (A[X]C[X], B[X]D[X] et (A[X]+B[X])(C[X]+
D[X])), à des additions de polynômes de degré au plus n —ce qui coûte Θ(n)— à des multiplica-
tions par un monôme X j —ce qui est un simple décalage des indices et coûte également Θ(n)— et
à des transpositions du polynôme R[X] au polynôme R[X 2 ] —ce qui est encore un simple décalage
des indices et coûte également Θ(n). L’équation de récurrence définissant la complexité de notre
algorithme est donc comme précédemment :
n
T (n) = 3T + Θ(n),
2
et la complexité est la même :
T (n) = Θ nlog2 3 .
2
3. Montrez que deux entiers à n bits peuvent être multipliés en Θ(nlog2 3 ) étapes.
L’entier m = i=0 mi 2i peut être vu comme un polynôme : il nous suffit de réappliquer un des algo-
P
rithmes vu à la question précédente pour obtenir le résultat escompté.
Trigo(n, a, b)
Si n = 0 alors renvoyer (1, 0)
sinon c, d = Trigo(n − 1, a, b)
renvoyer (ac − bd, ad + bc)