Polynômes

I) Présentation

1) Objectif

On souhaite modéliser un polynôme et implémenter des opérations usuelles les concernant.

2) Modélisation d'un polynôme

  Les coefficients d'un polynôme peuvent être des réels ou des complexes, on considère par exemple ici des polynômes à coefficients réels.
  Un polynôme est en mathématiques une suite (la suite des coefficients du polynôme) dont tous les termes sont nuls à partir d'un certain rang. Comme une liste informatique ne peut comporter qu'un nombre fini de termes, on pourrait décider que la liste p = [ a 0 , a 1 , ... , a n ] de flottants représente le polynôme P ( X ) = Σ k = 0 n a k X k de R[X].

  Le problème qui se pose est alors q'un même polynôme peut être représenté d'une infinité de façons. Par exemple, P ( X ) = X - 2 X 2 peut être représenté par p = [0, 1, -2] mais aussi par p = [0, 1, -2, 0, 0, 0] : on peut ajouter à droite autant de zéro que l'on veut. Il est préférable d'imposer une condition supplémentaire pour avoir une unique liste représentant un polynôme donné. On décide ainsi que:

  Le polynôme non nul de degré n N     P ( X ) = Σ k = 0 n a k X k de R[X] est la liste de flottants  p = [ a 0 , a 1 , ... , a n ] (avec a n 0 )  .
  Le polynôme nul est la liste [0], et son degré sera -1 .
  
  Donc: une liste de réels p = [ a 0 , a 1 , ... , a n ] est un polynôme si et seulement si a n 0 ou ( n = 0 et a 0 = 0 ) .
  
  Dans toute la suite, un polynôme est une liste de réels du type défini ci-dessus. Tous les résultats des fonctions demandées dans les questions du problème sont des listes de réels de ce type.

3) Exemples

  Le polynôme P(X) associé à  p = [3, 1, 0, -2] est P ( X ) = 3 + X - 2 X 3 .
  La liste q associée au polynôme X 4 - 2 X est q = [0, -2, 0, 1] (attention à l'ordre).

II) Algorithmes

  Toutes les fonctions écrites jusqu'à la question n peuvent être utilisées dans la question n + 1 .

Normalisation, degré, valeur en un réel

Q1) Ecrire une fonction eliminer_zero(s)  (avec s liste de flottants) calculant le polynôme obtenu en supprimant les éventuels zéro à la fin de la liste s. (Si la liste s n'est composée que de zéro, le résultat doit être le polynôme nul [0]).
Par exemple, eliminer_zero([1, 0, 2, 0, 0]) = [1, 0, 2] ; eliminer_zero([3, 1]) = [3, 1] et eliminer_zero([0, 0, 0]) = [0] .

Q2) Ecrire une fonction deg(p) (avec p polynôme) calculant le degré du polynôme p.
  Par exemple deg([1, 0, 2]) = 2 et deg([0]) = -1.

Q3) Ecrire une fonction valeur(p, x) (avec p polynôme et x réel) calculant le réel p(x) par l'algorithme de Horner.
Quelle est la complexité de cette fonction en fonction de la longueur np de la liste p ?

  On rappelle cette méthode de Horner: avec   p ( X ) = Σ k = 0 n a k X k , alors   p ( x ) = ( ... ( ( a n x + a n - 1 ) x + a n - 2 ) x + ... + a 1 ) x + a 0 .
  Par exemple, valeur([-1, 3, -3, 1], 1.5) = 0.125 .

Opérations usuelles

Q4) Ecrire une fonction somme(p, q) (avec p et q polynômes) calculant le polynôme p + q.
  Par exemple: somme([1, 2, 3], [5, 2]) = [6, 4, 3] et  somme([1, 2, 3], [5, -2, -3]) = [6]

Q5) Ecrire une fonction fois(a, p) (avec a ∈ R et p polynôme) calculant le polynôme a.p
  Par exemple: fois(-2, [4, 5, 6]) = [-8, -10, -12] et fois(0, [4, 5, 6]) = [0]

Q6) Ecrire une fonction difference(p, q) (avec p et q polynômes) calculant le polynôme p - q.
  Par exemple: difference([1, 2, 3], [5, 2]) = [-4, 0, 3] et difference([1, 2, 3], [5, 2, 3]) = [-4]

Q7a) Ecrire une fonction produit(p, q) (avec p et q polynômes) calculant le polynôme p × q.
  Par exemple produit([1, 2, 3], [1,-1]) = [1, 1, 1, -3] et produit([1, 2, 3], [0]) = [0]
Q7b) Prouver que la complexité de produit(p, q) est en O ( np nq ) avec np et nq les longueurs des listes p et q.

Q8a) Ecrire une fonction puissance(p, n) (avec p polynôme et n ∈ N) calculant le polynôme p n .
  On convient que pour tout polynôme p (même nul),   p 0 = [ 1 ] .
  Par exemple, puissance([1, 2, 3], 3) = [1, 6, 21, 44, 63, 54, 27] et  puissance([1, 2, 3], 0) = [1]
Q8b) En fonction de n et de np (la longueur de la liste p), quelle est la complexité de cette fonction puissance(p, n) ?

Q9a) Ecrire une fonction composition(p, q) (avec p et q polynômes) calculant le polynôme p◦q .
  Par exemple, composition([0, 1, 2], [1, 2, -1]) = [3, 10, 3, -8, 2] et composition([0], [1, 2, -1]) = [0]
Q9b) Prouver que la complexité de cette fonction composition(p, q) est en O ( nq 2 np 3 ) avec np et nq les longueurs des listes p et q.

Dérivées

Q10) Ecrire une fonction derivee_1(p)  (avec p polynôme) calculant le polynôme dérivée du polynôme p.
  Par exemple derivee_1([1, 2, 3, 4, 5], 1) = [2, 6, 12, 20] et derivee_1([3]) = [0].

Q11) Ecrire une fonction derivee(p, n)  (avec p polynôme et n ∈ N) calculant le polynôme dérivée n ième du polynôme p.
  Par exemple derivee([1, 2, 3, 4, 5], 3) = [24, 120] et derivee([1, 2, 3, 4, 5], 6) = [0].

Affichage usuel

Q12) Ecrire une fonction affiche(p) (avec p polynôme) qui calcule sous la forme usuelle Σ k = 0 n a k X k le polynôme
p = [ a 0 , ... a n ] . Le résultat est une chaîne de caractères.

On impose que:
    • le signe éventuel + devant a n ne doit pas apparaître
    • les 1 sont supprimés dans les coefficients égaux à 1 ou -1, sauf pour le terme constant
    • les termes avec un coefficient nul n'apparaissent pas
    • X^1 s'écrit X        

On pourra écrire des fonctions supplémentaitres pour sous-traiter le problème.
Par exemple, affiche([-1, 1, 5, -2, 0, 3]) = 3 X^5 - 2 X^3 + 5 X^2 + X - 1

Division euclidienne

Q13a) Ecrire une fonction reste_1(a , b) et une une fonction quotient_1(a , b) (avec a et b polynômes, b ≠ [0]) calculant le reste et le quotient de la division euclidienne de a par b.
  Par exemple, reste_1([0] * 9 + [1], [2, 3, 1]) = [510.0, 511.0] et  quotient_1([0] * 4 + [1], [2, 3, 1]) = [7.0, -3.0, 1.0]

Q13b) Essayer maintenant ces fonctions avec par exemple a = puissance([1, -7, 3.6], 3) et b = puissance([10, -70, 36], 2). Les résultats sont faux (quels devraient être les bons résultats ?) car des erreurs d'élimination se produisent lors des calculs des restes successifs.  On essaie de remédier à ce problème.

Q13c) Ecrire une fonction norme(p) (avec p polynôme) calculant la plus grande valeur absolue des coefficients de p.
  Par exemple norme([1, -3, 2]) = 3.

Q13d) Ecrire une fonction nettoyer(p, m) (avec p polynôme et m réel > 0) qui met à 0 tous les coefficients c du polynome p tels que | c m | < 2 - 30 . (Tester aussi avec d'autres valeurs que 30).
  Par exemple, nettoyer([4, 31, 3], 10**10) = [0, 31]

Q13e) Utiliser ces fonctions nettoyer() et norme() pour écrire des fonctions reste(a, b) et quotient(a, b) qui atténuent largement les erreurs d'éliminations des fonctions reste_1(a, b) et quotient_1(a, b).
Au lieu de calculer le reste suivant r = r - r 1 dans l'algorithme de la division, on le calculera sous la forme r = nettoyer ( r - r 1 , m ) avec m = norme ( r ) .  

  Essayer avec a = puissance([1, -7, 3.6], 3) et b = puissance([10, -70, 36], 2), puis d'autres polynômes plus compliqués, par exemple:
a = produit(puissance([1, -3, 2.7], 5), puissance([2, -7], 4)) et b = produit(puissance([1, -3, 2.7], 3), puissance([2, -7], 2))

Polynôme unitaire, PGCD

Q14) Ecrire une fonction unitaire(p) (avec p polynôme) calculant le polynôme q unitaire colinéaire à p. (Si p = [0], q = [0])
  On rappelle qu'un polynôme unitaire est un polynôme de coefficient dominant égal à 1, et donc que si cd est le coefficient dominant de p non nul, alors q = 1 cd p .
  Par exemple, unitaire([1, 2, 3, 4, 5]) = [0.2, 0.4, 0.6, 0.8, 1.0]

Q15) Ecrire une fonction pgcd(p, q) (avec p et q polynômes non tous deux nuls) calculant le pgcd unitaire de p et q par l'algorithme d'Euclide.
  Par exemple avec p = produit ( puissance ( [ 1 , 2 , 3 ] , 3 ) , puissance ( [ 1.5 , - 2 ] , 2 ) ) et q = produit ( puissance ( [ 1 , 2 , 3 ] , 2 ) , puissance ( [ 1.5 , - 2 ] , 4 ) ) , vérifier que pgcd(p,q)=unitaire(produit(puissance([1,2,3],2),puissance([1.5,-2],2)))

© 2014 - Eric Obermeyer      Powered by      Corrigé