Polynômes creux

Contexte informatique

Un programme à trous poly.ml est fourni. Il suffit de le récupérer et de le modifier.

Pour le compiler, on fera simplement : 

% ocamlc poly.ml

Et on produira l'exécutable a.out. Cet exécutable contient du code qui teste (un peu) les fonctions que vous allez écrire. Chaque fois que vous avez écrit une nouvelle fonction, vous pouvez compiler et 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

Le module des listes List sera sans doute bien utile. On pourra chercher à tirer profit des fonctions de librairie sur les listes et en particulier de List.iter, List.map, List.fold_right, etc.

  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) la puissance d'un entier.
    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 peut compiler et on obtient (option -i) 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.
This document was translated from LATEX by HEVEA.