Maîtrise d'Informatique Maîtrise d'ingénierie mathématique	Module de Calcul Formel Année 2001-2002

Manipulations de Polynômes

Le but du TD est de réaliser les opérations simples sur les polynômes, en une ou plusieurs variables. Nous allons adopter une représentation distribuée creuse pour les polynômes: un polynôme sera une liste de monômes non nuls triés dans l'ordre lexicographique décroissant des exposants. La liste des variables est implicite (et n'est donc pas codée dans la représentation). Comment représente-t-on le polynôme nul?

Un monôme sera représenté comme une liste à deux éléments où le premier terme est l'exposant et le deuxième est le coefficient.

Un exposant est une liste de longueur le nombre de variables contenant les degrés en chaque variable. Un coefficient est un objet maple quelconque.

Ainsi nous avons la forme suivante pour un polynôme ayant m monômes non nuls sur n variables:

[ [ [ deg_1,1 , ... , deg_n,1 ] , coeff₁ ], ... , [ [ deg_1,m , ... , deg_n,m ] , coeff_m ] ]

En particulier en une seule variable on aura:

[ [ [ deg₁ ] , coeff₁ ], ... , [ [ deg_m ] , coeff_m ] ]

Nous allons d'abord nous donner quelques utilitaires de programmation:

Écrivez des procédures maple mainMon et redPol qui retournent respectivement le monôme de tête et le polynôme formé de tous les autres monômes d'un polynôme (i.e privé du monôme de tête).
Écrivez une fonction consPol à deux arguments (un monôme et un polynôme) et qui retourne le polynôme formé du monôme argument (en tête) et du polynôme argument. Faites de même une fonction insereMon qui mette le monôme argument « à sa place » dans le polynôme et non plus en tête.
Écrivez des procédures maple exposant et terme qui retournent respectivement la liste des degrés en les différentes variables, et le coefficient d'un monôme.
Écrivez une fonction lexGt qui prenne deux monômes en arguments et qui retourne un booléen (true ou false) suivant que le premier monôme est ou non supérieur au second dans l'ordre lexicographique des exposants. Vous pourrez commencer par le cas simple d'une seule variable (c'est l'ordre usuel), puis de deux, puis généraliser.
Écrivez une fonction lexOrder qui trie une liste de monômes pour retourner un polynôme et une fonction makeCan qui enlève d'une liste de monômes ceux dont le coefficient est nul.
Écrivez une fonction polToMaple qui prenne en arguments un polynôme et une liste de variables (ayant le même nombre d'éléments que les listes des exposants des monômes) et qui retourne un objet maple usuel.

Nous pouvons maintenant penser à implémenter les opérations arithmétiques, nous allons réaliser l'addition de 2 polynômes P₁ et P₂.

Que retourner si l'un des 2 polynômes est nul?
Nous allons examiner les monômes de tête M₁ et M₂ de P₁ et de P₂. Que faut-il retourner si l'exposant de M₁ est plus grand (strictement pour l'ordre lexicographique), plus petit, égal à celui de M₂?
Implémentez cet algorithme en maple (attention au cas où les exposants sont égaux!).

Nous pouvons passer à la multiplication de P₁ et P₂.

Comment multiplier un polynôme par un monôme? Implémentez une fonction maple monMul qui multiplie un polynôme (passé en premier argument) par un monôme (passé en deuxième argument).
Que reste-t-il à faire pour multiplier deux polynômes? Écrivez une fonction maple qui multiplie deux polynômes.

Pourquoi n'a-t-on pas de notion de division euclidienne sur les polynômes en plusieurs variables? Lorsqu'il n'y a qu'une seule variable nous pouvons écrire la division euclidienne en utilisant les opérations sur les coefficients.

Comment calcule-t-on le premier terme du quotient de la division de P par Q?
Écrivez une fonction maple polDiv à deux arguments (P et Q) qui calcule le quotient et le reste de la division euclidienne. Le résultat sera une liste de longueur 2 contenant le quotient et le reste.
Écrivez deux fonctions maple polQuo et polRem analogues à polDiv qui calculent directement le quotient et le reste.

Maintenant que nous avons la base, rajoutez quelques fonctions utilitaires! Inspirez vous des fonctions déjà existantes en maple.

Ce document a été traduit de L^AT_EX par H^EV^EA.