Polynômes

Didier Rémy

Objectif

Il s'agit d'écrire une librairie d'opérations sur les polymônes en utilisant les modules pour abstraire la structure d'anneau sur les coefficients. L'intérêt pédagogique de cet exercice est aussi d'apprendre à maîtriser les modules de OCaml.

Structure d'anneau

On donne la signature OCaml suivante permettant de représenter des structures d'anneaux:
module type ANNEAU = sig type t (* type des éléments de l'anneau *) val zero : t val unit : t val plus : t -> t -> t val symm : t -> t val mult : t -> t -> t val equal : t -> t -> bool val tostring : t -> string end ;;
Le type t est le type (abstrait) des éléments de l'anneau. Les champs suivants sont les opérations sur la structure d'anneau. Nous avons ajouté le champ equal pour tester l'égalité de deux éléments sans supposer que les éléments en formes canoniques (on ne peut donc pas utiliser l'égalité générique =). Le champ tostring est utilisé pour afficher les éléments de l'anneau.
  1. Donner une implémentation de l'anneau Int des entiers et de l'anneau Bool des Booléens ayant tous deux l'interface ANNEAU.
    Solution.
  2. Placer les définitions précédentes dans un fichier poly.ml et écrire le fichier poly.mli lui servant d'interface.
    Solution.
  3. Écrire un foncteur permettant de créer les anneaux Z/nZ pour n entier positif arbitraire. En déduire les anneaux Z7Z et Z13Z. On placera ces définitions dans un fichier ZnZ.ml. Vérifier que le système de module empêche de confondre les éléments des deux anneaux.
    Solution.
  4. On peut injecter les entiers dans un anneau A par la fonction
    n ↦ A.zero + A.unit + … + A.unitn fois
    Définir la fonction power qui élève une fonction n à la puissance n. (Par commodité, on ajoutera cette définition dans le fichier poly.ml.) En déduire une définition simple de l'injection des entiers dans l'anneau des entiers Z7Z (que l'on décrira dans le fichier anneau.ml).
    Solution.

Structure de polynômes

On donne l'interface de la structure des polynômes:
module type POLYNOME = sig type c type t val zero : t val unit : t val symm : t -> t val plus : t -> t -> t val mult : t -> t -> t val equal : t -> t -> bool val tostring : t -> string val monome : c -> int -> t val eval : t -> c -> c end ;;
  1. Vérifiez que les polynômes ont une structure d'anneau, ie. qu'une structure de polynôme peut être vue par OCaml comme une structure d'anneau.
    Solution.
  2. En déduire une représentation plus concise de la définition de la signature POLYNOME.
    module type POLYNOME = sig type c include ANNEAU val monome : c -> int -> t val eval : t -> c -> c end ;;
    Faut-il ajouter cette définition dans le fichier poly.mli? dans le fichier poly.ml?
    Solution.
  3. Le type c représente le type des coefficients. Quel est à votre avis le sens de la fonction monome? de la fonction eval?
    Solution.
  4. L'«implémentation» des polynômes étant la partie longue de l'exercice, nous allons la retarder et dans un premier temps vérifier que l'interface (sa spécification) est bien choisie.

    Nous voulons écrire une implémentation des polynômes qui soit paramétrée par le nom de la variable. Donner la signature du foncteur Make qui permet de réaliser une telle abstraction (on écrira la signature de Make dans le fichier poly.mli).
    Solution.
  5. Il y a une petite subtilité: sauriez-vous l'expliquer (en particulier si vous ne l'aviez pas remarquée)?
    Solution.
Nous laissons pour l'instant de coté l'implémentation du foncteur Make. Nous allons voir comment l'utiliser avant de l'implémenter.

Polynômes à plusieurs variables

Un polynôme en X et Y peut être vu comme un polynôme en X dont les coefficients sont des polynômes en Y (rappelez-vous qu'un polynôme est en particulier un anneau). On veut s'assurer que cela est bien possible à partir des polynômes à une variable.
  1. Donner une implémentation naive du foncteur de signature:
    open Poly module Make2 (A : ANNEAU) (X : VAR) (Y : VAR) : POLYNOME;;
    dont le sens est évident.
    Solution.
  2. Quel problème cela pose-t-il?
    Solution.
  3. En fait, on voudrait voir les polynômes à deux variables avec l'interface suivante et non comme des polynômes de polynômes:
    open Poly module Make2 (A : ANNEAU) (X : VAR) (Y : VAR) : sig include ANNEAU type c = A.t val monome : c -> int -> int -> t val eval : t -> c -> c -> c end
    Donner une implémentation de ce foncteur.
    Solution.
  4. En déduire une définition des polynômes en XY à coefficients entiers.
    Solution.
  5. Développer (X - Y) ^ 4 et évaluer ce polynome en X=7 et Y=5.
    Solution.

Implémentation des polynômes

Écrire finalement l'implémentation des polynômes à une variable, c'est-à-dire du module Make.

On pourra représenter les polynômes par des listes de monômes triés dans l'ordre des puissances croissantes. De plus afin que la représentations soit canonique on éliminera systématiquement les monomes nuls (le polynôme nul sera donc représenté par la liste vide).
Solution.

Un vrai programme

Écrire un programme qui prend un polynôme à une variable à coefficients flottants sur la ligne de commande (les coefficients de chaque puissance sont donnés dans l'ordre des puissances croissantes, jusqu'à ce que tous les coefficients restant soient nuls) et l'évalue en chacun des points lus dans stdin (un flottant par ligne). Le résultat est imprimé dans stdout. On pourra tester avec la commande
./eval 2. -2. 1. < eval.in > eval.out
Puis comparer le fichier eval.out avec eval.ref

Solution.

Compilation avec Makefile

Utiliser la commande make pour compiler le programme.
Solution.


This document was translated from LATEX by HEVEA.