Fractions rationnelles

DEA algorithmique






Attention
Pour visualiser convenablement les formules mathématiques sous netscape, il faut ajouter la ligne suivante à votre fichier .Xdefaults: 
Netscape*documentFonts.charset*adobe-fontspecific: iso-8859-1
et redémarrer netscape.



1  Programmation et polynômes

1.1  Finir la feuille précédente

1.2  Un peu d'arithmétique des polynômes

Écrire une procédure qui calcule simplement le produit de deux polynômes.

Voici maintenant un algorithme pour calculer cette quantité plus rapidement :

On considère les polynômes
A(X) = a0+a1 X, B(X)=b0+b1 X
dont le produit est P(X) = p0 + p1 X + p2 X2. Le calcul classique des pi se fait par :
p0 = a0 b0, p1 = a0 b1 + a1 b0, p2 = a1 b1
ce qui nécessite 4 multiplications.

L'idée est de calculer
p0 = a0 b0, p2 = a1 b1 et p1 = (a0+a1) (b0+b1) - p0 - p2.
On a gagné une multiplication, au prix de quatre additions supplémentaires.

Allons plus loin, en montrant comment calculer le produit de deux polynômes de degré n= 2t-1.
A(X) = a0 + a1 X+···+an-1 Xn-1, B(X) = b0 + b1 X+···+bn-1 Xn-1.
On peut couper en deux ces polynômes et écrire
A(X) = A0(X) + Xn/2 A1(X), B(X) = B0(X) + Xn/2 B1(X),
où les Ai et les Bi sont de degré n/2-1. On calcule alors
P0 = A0 B0,   P1 = (A0+A1)(B0+B1), P
 
¥
= A1 B1
par le même algorithme. On retrouve le produit P(X) par
P(X) = P0 + Xn/2 (P1 - P0 - P
 
¥
)+ Xn P1.
Implémenter cet algorithme et évaluer sa complexité en fonction de n.

Comment adapter cet algorithme quand les polynômes ne sont pas de mêmes degrés? Quand leur degrés sont très différents?

Lorsque les polynômes deviennent trop petits (seuil à déterminer), alors la multiplication naïve devient plus rentable, son utilisation dans l'implémentation de l'algorithme de Karatsuba constitue une optimisation.

Pour des polynômes plus gros, on dispose de la FFT (Fast Fourier Transform, transformée de Fourier rapide en français). Optimalement une procédure qui calcule le produit de deux polynômes utilise l'algorithme naïf sur les très petits polynômes, l'algorithme de Karatsuba sur les polynômes de taille moyenne et la FFT sur les gros polynômes. Le seuil de rentabilité d'un algorithme par rapport à un autre peut varier d'une machine à l'autre.



1.3  Factorisation de polynômes

Choisir un polynôme, consulter l'aide en ligne sur la factorisation Mathematics/Algebra/Polynomials/Factorization and root finding, essayer les différentes fonctions sur ce polynôme.



2  Fractions rationnelles

Choisir deux fractions rationnelles, consulter l'aide en ligne sur les fractions rationnelles Mathematics/Algebra/Rational Expressions, essayer les différentes fonctions sur ces fractions rationnelles.



Valérie Ménissier-Morain et Philippe Aubry
Friday 22 October 1999
This document was translated from LATEX by HEVEA.