Polynômes creux






Contexte informatique

Un programme à trous poly.ml est fourni. Il suffit de le récupérer et de le modifier. Ce programme contient du code qui teste (un peu) les fonctions que vous allez écrire. Chaque fois que vous avez écrit une nouvelle fonction, vous pouvez lancer l'exécutable et cette nouvelle fonction subira quelques tests.

Representation creuse des polynômes

L'objet de ce TD est la manipulation de polynômes à une variable, codés par des listes. On parle alors de polynômes creux. Précisément, on va créer un type enregistrement monome contenant un champs coefficient et un champ degré puis définir le type polynome comme une liste de monômes.

  type monome = {coeff: int; degre: int}
  
  type polynome = monome list

On impose deux conditions : les monômes d'un polynôme devront toujours être triés par degré décroissant ; aucun coefficient ne doit être nul. Le polynôme nul est représenté par la liste vide [].

Par exemple, le polynôme X5-2X4+1 sera représenté par la liste
[{coeff=1;degre=5}; {coeff=(-2);degre=4}; {coeff=1;degre=0}]

1 Polynômes à coefficients entiers

On pourra chercher à tirer profit des fonctions de la bibliothèque List sur les listes et en particulier de List.iter, List.map, et List.fold_right.

  1. Écrivez une fonction afficher: polynome -> unit qui affiche un polynôme à l'écran. Dans un premier temps, on peut ne pas chercher à obtenir le plus bel affichage possible. Pour afficher diverses valeurs, le plus simple est sans doute de recourir à la fonction Printf.printf, mais on peut aussi utiliser des fonctions ad-hoc, du genre de print_int.
    Solution.


  2. Écrivez une fonction somme: polynome -> polynome -> polynome qui renvoie le polynôme somme des deux polynômes passés en arguments. On peut assez facilement atteindre une complexité linéaire en s'inspirant de la fusion de deux listes triées (en effet, les polynômes sont des listes de monômes ordonnés selon les degrés décroissants).
    Solution.


  3. Écrivez une fonction deriver: polynome -> polynome qui renvoie le polynôme dérivé du polynôme passé en argument.
    Solution.


  4. Écrivez une fonction produit: polynome -> polynome -> polynome qui renvoie le produit des polynômes passés en arguments.
    Solution.


  5. Écrivez une fonction evaluer: polynome -> int -> int qui calcule la valeur d'un polynôme en un point. On pourra introduire une fonction intermédiaire puissance: int -> int -> int qui calcule (efficacement, tant qu'à faire) l'élévation d'un entier à une certaine puissance.
    Solution.

Le programme sol.ml est une une solution complète, qui peut servir de point de départ pour l'exercice suivant.

2 Polynômes à coefficients arbitraires

Si l'on veut maintenant manipuler des polynômes dont les coefficients ne sont plus des entiers, il faut modifier tout le code précédent pour chaque type de coefficient. Pour éviter cela, vous allez reprendre le code précédent en le généralisant pour des types arbitraires.

La méthode suggérée est de paramétrer les fonctions déjà écrites par un enregistrement de type 'a dico regroupant ce qui dépend du type des coefficients 'a.

Dans un nouveau fichier gpoly.ml sont définis les types polymorphes suivants :

(* Types des coefficients *)
type 'a dico = {print : 'a -> unit}

(* Qui sont ici des flottants *)
let dico_float = {print=print_float}

(* Types des polynomes *)
type 'a monome = {coeff: 'a; degre: int}

type 'a polynome = 'a monome list

Si on insère les cinq fonctions solutions de la question précédente, on obtient les types suivants :
type 'a dico = { print : 'a -> unit; }
val dico : float dico
type 'a monome = { coeff : 'a; degre : int; }
and 'a polynome = 'a monome list
val afficher : int monome list -> unit
val somme : int monome list -> int monome list -> int monome list
val deriver : int monome list -> int monome list
val produit : int monome list -> int monome list -> int monome list
val evaluer : int monome list -> int -> int

Il faut maintenant modifier chacune des fonctions (ainsi que le type dico) pour arriver aux types suivants (avec les significations généralisées « évidentes ») :
val afficher : 'a dico -> 'a monome list -> unit
val somme : 'a dico -> 'a monome list -> 'a monome list -> 'a monome list
val deriver : 'a dico -> 'a monome list -> 'a monome list
val produit : 'a dico -> 'a monome list -> 'a monome list -> 'a monome list
val evaluer : 'a dico -> 'a monome list -> 'a -> 'a

En Caml les opérations sur les flottants sont les opérateurs usuels suivis du point «.» (l'addition est (+.) par exemple, à utiliser comme x +. y).

Solution.

3 Méthode de Newton

On va coder une routine très simple d'approximation numérique d'une racine d'un polynôme P : la méthode de Newton. À partir d'une valeur initiale x0, on définit la suite xn par :
xn+1 = xn -
P(xn)
P'(xn)

où P' est le polynôme dérivé de P. On décide de s'arrêter quand |xn+1-xn| devient inférieur à un certain epsilon donné à l'avance ; on parlera alors un peu abisivement de racine approchée à epsilon près.

Coder la fonction newton: float polynôme -> float -> float -> float, telle que l'appel newton p e x0 renvoie une racine approchée de P à e près, en partant de x0.

On testera cette fonction en calculant par exemple la racine carrée de deux.
Solution.

Ce document a été traduit de LATEX par HEVEA et HACHA.