Exercices de programmation en CAML

niveau classes préparatoires

[Link]

6 septembre 2011
Table des matières

1 Techniques de programmation 3
1.1 Initiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Factorielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Exponentiation lente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.3 Exponentiation rapide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.4 PGCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.5 Caractères et entiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.6 Mise sous forme récursive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.7 Indicatrice d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Listes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Types récursifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.1 Tri par arbre binaire de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Problèmes d’algorithmique 9
2.1 Le carré qui rend fou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Affichage de carres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.2 Remplissage avec des étoiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.3 Enumération des carrés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.4 Enumération des rectangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 Autour du programme de maths 15

3.1 Calcul matriciel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1.1 Représentation des matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1.2 Opérations matricielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.1.3 Inversion de matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Polynômes et analyse numérique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.1 Représentation des polynômes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.2 Opérations sur les polynômes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.3 Évaluation et méthode de Horner . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2.4 Dérivée et intégrale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2.5 Calculs approchés d’intégrales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.6 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.7 Méthode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.8 Division euclidienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.9 Méthode de Sturm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4 Quelques corrigés 25
4.1 Initiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2 Listes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.3 Types récursifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.4 Le carré qui rend fou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.5 Algèbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

1
4.6 Polynômes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2
Chapitre 1

Techniques de programmation

1.1 Initiation
1.1.1 Factorielle
On définit la fonction factorielle par récurrence de la façon suivante :

n! = n.((n − 1)!)
0! = 1

Exercice 1
Écrire la fonction factorielle : int -> int qui à n associe n!.

Exercice 2
Écrire la fonction factorielle acc : int -> int -> int telle que factorielle acc n k calcule
k(n!)

Exercice 3
Écrire une fonction factorielle bis : int -> int qui invoque factorielle acc de sorte que
factorielle bis n calcule n!.

1.1.2 Exponentiation lente

L’élévation de b à la puissance n se définit récursivement par itération du produit
 n
b = [Link]−1
b0 = 1

Exercice 4
Écrire une fonction slow exp : int -> int -> int prenant b et n en paramètres en calculant bn à
l’aide de la relation de récurrence mentionnée ci-dessus.

Exercice 5
Écrire une fonction recursive terminale slow exp acc : int -> int -> int -> int prenant a, b et
n en paramètres en calculant [Link] .

3
Exercice 6
Écrire une fonction slow exp bis : int -> int -> int qui invoque slow exp acc de sorte que
slow exp bis b n calcule bn .

1.1.3 Exponentiation rapide

Nous allons calculer bn à l’aide des relations de récurrence suivantes

 bn = (bn/2 )2 , si n est pair
bn = [Link]−1 , si n est impair
 0
b =1

Exercice 7
Ecrire une fonction even : int -> bool telle que even n retourne true si et seulement si n est pair.

Exercice 8
Définir la fonction fast exp : int -> int -> int telle que fast exp b n calcule bn avec les égalités
ci-dessus.

Exercice 9
Prouvez que la fonction fast exp se termine toujours.

Exercice 10
Donnez une version récursive terminale de fast exp.

1.1.4 PGCD
On définit le plus grand commun diviseur (greatest common divider) de deux entiers récursivement
de la façon suivante :

gcd(n, m) = gcd(m, n mod m)
gcd(n, 0) = n

Exercice 11
Prouvez que cette relation de récurrence permet d’écrire une fonction qui se termine toujours.

Exercice 12
Définir la fonction gcd : int -> int -> int telle que gcd n m calcule le PGCD de n et de m à
l’aide des relations ci-dessus.

1.1.5 Caractères et entiers

Exercice 13
Écrire la fonction lettre suivante : char -> char telle que lettre suivante a retourne la lettre
située après a dans l’alphabet. Nous ne gérerons pas le cas particulier où a = ’z’.

Exercice 14
Écrire la fonction figure of int : int -> char telle que figure of int n retourne le caractère
représentant le chiffre n. Par exemple, figure of int 4 retourne ’4’. Nous ne gérerons pas les cas
particuliers où n est un nombre de plusieurs chiffres.

4
Exercice 15
Écrire la fonction compare lettres : char -> char -> bool telle que compare lettres a b re-
tourne vrai ssi la lettre a et située avant la lettre b dans l’alphabet ou si les deux lettres sont les mêmes.

Exercice 16
Écrire la fonction alphabet : char -> char -> unit telle que alphabet lettre depart lettre arrivee
affiche l’alphabet entre les lettres lettre depart et lettre arrivee.

1.1.6 Mise sous forme récursive

Exercice 17
Écrire la fonction mult : int -> int -> int telle que mult x y retourne le produit de x par y sans
effectuer de multiplication.

Exercice 18
Mettez la fonction précédente sous forme récursive terminale. Encapsulez-là dans une fonction mult bis :
int -> int -> int.

1.1.7 Indicatrice d’Euler

Exercice 19
Écrire une fonction ind euler : int -> int retournant l’indicatrice d’Euler de l’entier passé en
paramètre.

5
1.2 Listes
Exercice 1
Écrire la fonction n a un : int -> int list retournant la liste [n; . . . ; 2; 1].

Exercice 2
Écrire la fonction un a n : int -> int list retournant la liste [1; 2; . . . ; n].

Exercice 3
Écrire la fonction supprime : ’a list -> int -> ’a list retournant dans laquelle les n premiers
éléments ont été supprimés.

Exercice 4
Écrire la fonction long prefixe : ’a list -> int retournant le nombre d’entiers identiques se trou-
vant au début de la liste passée en paramètre.

6
1.3 Types récursifs
1.3.1 Tri par arbre binaire de recherche
Un ABR (arbre binaire de recherche) est un arbre tel que pour chaque noeud x, tous les éléments du
sous-arbre gauche ont une valeur inférieure à x et tous les éléments du sous-arbre droit ont une valeur
supérieure à x. Nous utiliserons dans les exercices suivants le type
type ’ a b i n t r e e =
Empty
| Node of ’ a b i n t r e e ∗ ’ a ∗ ’ a b i n t r e e ; ;

Exercice 1
Écrire une fonction ins abr : (’a -> ’a -> bool) -> ’a -> ’a bin tree -> ’a bin tree telle
que ins abr f x t insère l’élément x dans l’arbre t en utilisant la fonction de comparaison f .

Exercice 2
Écrire une fonction abr of list : (’a -> ’a -> bool) -> ’a list -> ’a bin tree telle que abr of list
f l retourne un arbre contenant tous les éléments de l, disposés avec la fonction f .

Exercice 3
Écrire la fonction list of abr : ’a bin tree -> ’a list retournant une liste contenant les éléments
de l’arbre passé en paramètre.

Exercice 4
Écrire une fonction tri liste : (’a -> ’a -> bool) -> ’a list -> ’a list qui trie la liste
passée en paramètre à l’aide d’un ABR.

1.3.2 Fonctions
Nous utiliserons le type suivant pour représenter des fonctions simples :
type exp =
Const of i n t
| X
| Somme of exp ∗ exp
| P r o d u i t of exp ∗ exp
| P u i s s of exp ∗ i n t ; ;

Exercice 5
Écrire une fonction str of exp : exp -> string telle que str of exp e retourne une représentation
sous forme de chaı̂ne de caractères de l’expression e.

Exercice 6
Écrire une fonction image : exp -> int -> int telle que image e x retourne l’image de x par la
fonction e.

Exercice 7
Écrire une fonction derive : exp -> exp retournant la dérivée de l’expression passée en paramètre.

7
Exercice 8
Écrire une fonction degre : exp -> int retournant le degré du polynôme représenté par l’expression
passée en paramètre.

8
Chapitre 2

Problèmes d’algorithmique

2.1 Le carré qui rend fou

2.1.1 Affichage de carres
Nous souhaitons afficher sur la console des carrés de la façon suivante :

# print_string (carre 5);;

. . . . .
. . . . .
. . . . .
. . . . .
. . . . .

Exercice 1
Écrire la fonction ligne : int -> string retournant n points séparés par des espaces avec un retour
à la ligne à la fin. Par exemple,

# ligne 6;;
- : string = ". . . . . . \n"

Exercice 2
Écrire la fonction carre : int -> string retournant un carré un coté n avec deux retours à la ligne
à la fin. Par exemple,

# carre 6;;
- : string =
". . . . . . \n. . . . . . \n. . . . . . \n. . . . . . \n. . . . . . \n. . . . . . \n\n"

2.1.2 Remplissage avec des étoiles

Nous souhaitons maintenant afficher un carré contenant un rectangle d’étoiles. Par exemple,

# print_string (carre_etoiles (2, 8, 4, 9) 10);;

. . . . . . . . . .
. . . * * * * * * .
. . . * * * * * * .
. . . * * * * * * .
. . . * * * * * * .
. . . * * * * * * .

9
. . . * * * * * * .
. . . * * * * * * .
. . . . . . . . . .
. . . . . . . . . .

Exercice 3
Écrire la fonction etoiles : int -> int -> int -> string telle que etoiles a b n retourne n
caractères séparés par des espaces avec un retour à la ligne à la fin, et dont les caractères dont l’indice se
trouve entre a et b sont des étoiles. Par exemple,

# etoiles 3 8 10;;
- : string = ". . * * * * * * . . \n"

Exercice 4
Écrire la fonction carre etoiles : int * int * int * int -> int -> string telle que carre etoiles
(lhaut, lbas, cgauche, cdroite) n retourne un carré un coté n contenant un rectangle d’étoiles dont
le sommet en haut à gauche admet pour coordonnées (cgauche, lhaut) et le sommet en bas à droite
(cdroite, lbas).

2.1.3 Enumération des carrés

Nous souhaitons afficher tous les carrés d’étoiles possible. Par exemple,

# print_str_list (tous_les_carres 3);;

* . .
. . .
. . .

. . .
* . .
. . .

. . .
. . .
* . .

* * .
* * .
. . .

. . .
* * .
* * .

* * *
* * *
* * *

. * .
. . .
. . .

. . .
. * .

10
. . .

. . .
. . .
. * .

. * *
. * *
. . .

. . .
. * *
. * *

. . *
. . .
. . .

. . .
. . *
. . .

. . .
. . .
. . *

Exercice 5
Écrire la fonction couples coordonnees a fixe : int -> int -> (int * int) list telle que couples coordon
a b retourne tous les couples (a, y) vérifiant a ≤ y ≤ b. Par exemple,

# couples_coordonnees_a_fixe 3 8;;
- : (int * int) list = [(3, 3); (3, 4); (3, 5); (3, 6); (3, 7); (3, 8)]

Combien de couples sont retournés par cette fonction ?

Exercice 6
Écrire la fonction couples coordonnees : int -> (int * int) list telle que couples coordonnees
n retourne tous les couples (x, y) vérifiant 1 ≤ x ≤ y ≤ n. Par exemple,

# couples_coordonnees 3;;
- : (int * int) list = [(1, 1); (1, 2); (1, 3); (2, 2); (2, 3); (3, 3)]

Combien de couples sont retournés par cette fonction ?

Exercice 7
Écrire la fonction coordonnees carres colonnes fixees : int * int -> int -> (int * int *
int * int) list telle que coordonnees carres colonnes fixees (cgauche, cdroite) n retourne les
coordonnées de tous les carrés d’étoiles dont les colonnes ont les indices (cgauche, cdroite). Par exemple,

# coordonnees_carres_colonnes_fixees (3, 5) 7;;

- : (int * int * int * int) list =
[(1, 3, 3, 5); (2, 4, 3, 5); (3, 5, 3, 5); (4, 6, 3, 5); (5, 7, 3, 5)]

Combien d’éléments contient la liste retournée par cette fonction ?

11
Exercice 8
Écrire la fonction coordonnees carres : int -> (int * int * int * int) list telle que coordonnees carres
n retourne les coordonnées de tous les carrés d’étoiles qu’il est possible de former dans un carré de côté
n. Par exemple,

# coordonnees_carres 3;;
- : (int * int * int * int) list =
[(1, 1, 1, 1); (2, 2, 1, 1); (3, 3, 1, 1); (1, 2, 1, 2); (2, 3, 1, 2);
(1, 3, 1, 3); (1, 1, 2, 2); (2, 2, 2, 2); (3, 3, 2, 2); (1, 2, 2, 3);
(2, 3, 2, 3); (1, 1, 3, 3); (2, 2, 3, 3); (3, 3, 3, 3)]

Combien d’éléments contient la liste retournée par cette fonction ?

Exercice 9
Définir une fonction tous les carres : int -> string list telle que tous les carres n retourne
un liste contenant tous les carrés d’étoiles au format chaı̂ne de caractère. Par exemple,

# tous_les_carres 3;;
- : string list =
["* . . \n. . . \n. . . \n\n"; ". . . \n* . . \n. . . \n\n";
". . . \n. . . \n* . . \n\n"; "* * . \n* * . \n. . . \n\n";
". . . \n* * . \n* * . \n\n"; "* * * \n* * * \n* * * \n\n";
". * . \n. . . \n. . . \n\n"; ". . . \n. * . \n. . . \n\n";
". . . \n. . . \n. * . \n\n"; ". * * \n. * * \n. . . \n\n";
". . . \n. * * \n. * * \n\n"; ". . * \n. . . \n. . . \n\n";
". . . \n. . * \n. . . \n\n"; ". . . \n. . . \n. . * \n\n"]

Exercice 10
Écrire la fonction print str list : string list -> unit telle que print str list l affiche toutes
les chaı̂nes de la liste l les unes à la suite des autres. Par exemple,

# print_str_list ["debut " ; "milieu et " ; "fin"];;

debut milieu et fin
- : unit = ()

2.1.4 Enumération des rectangles

Nous souhaitons afficher tous les rectangles d’étoiles possible. Par exemple,

# print_str_list (tous_les_rectangles 2);;

* .
. .

* *
. .

. *
. .

* .
* .

* *
* *

12
. *
. *

. .
* .

. .
* *

. .
. *

Exercice 11
Définir une fonction concat produits : ’a * ’b -> (’c * ’d) list -> (’a * ’b * ’c * ’d)
telle que concat produits (a, b) l retourne une liste de quadruplets dont les deux premiers éléments
sont a et b et les deux suivants pris dans la liste l. Par exemple,

# concat_produits (2, 4) [(1,2);(3,4);(5,6);(7,8);(9,0)];;

- : (int * int * int * int) list =
[(2, 4, 1, 2); (2, 4, 3, 4); (2, 4, 5, 6); (2, 4, 7, 8); (2, 4, 9, 0)]

Exercice 12
Définir une fonction croise coordonnees : (’a * ’b) list -> (’c * ’d) list -> (’a * ’b *
’c * ’d) list telle que croise coordonnees a b retourne tous les 4-uplets qu’il est possible de former
avec un élément de a et un élément de b. Par exemple,

# croise_coordonnees [(1,2);(3,4)] [(5,6);(7,8)];;

- : (int * int * int * int) list =
[(1, 2, 5, 6); (1, 2, 7, 8); (3, 4, 5, 6); (3, 4, 7, 8)]

Exercice 13
Définir une fonction coordonnees rectangles : int -> (int * int * int * int) list telle que
coordonnees rectangles n retourne la liste des coordonnées de tous les rectangles qu’il est possible de
former à l’intérieur d’un carré de côté n. Par exemple,

# coordonnees_rectangles 2;;
- : (int * int * int * int) list =
[(1, 1, 1, 1); (1, 1, 1, 2); (1, 1, 2, 2); (1, 2, 1, 1); (1, 2, 1, 2);
(1, 2, 2, 2); (2, 2, 1, 1); (2, 2, 1, 2); (2, 2, 2, 2)]

Exercice 14
Définir une fonction tous les rectangles : int -> string list telle que tous les rectangles
n retourne une liste contenant les représentations sous forme de chaı̂nes de caractères de tous les rectangles
qu’il est possible de former à l’intérieur d’un carré de côté n. Par exemple,

# tous_les_rectangles 2;;
- : string list =
["* . \n. . \n\n"; "* * \n. . \n\n"; ". * \n. . \n\n"; "* . \n* . \n\n";
"* * \n* * \n\n"; ". * \n. * \n\n"; ". . \n* . \n\n"; ". . \n* * \n\n";
". . \n. * \n\n"]

13
Exercice 15
Combien peut-on former de rectangles d’étoiles dans un carré de côté n ?

14
Chapitre 3

Autour du programme de maths

3.1 Calcul matriciel

3.1.1 Représentation des matrices
Dans cette section, nous mettrons au point des fonctions permettant de créer des matrices et de les
afficher sous un format lisible.

Exercice 1
Définir la fonction make matrix : int -> int -> float array array telle que make matrix n p
retourne un tableau de n tableaux à p éléments contenant des 0., par exemple :

# make_matrix 3 4;;
- : float array array =
[|[|0.; 0.; 0.; 0.|]; [|0.; 0.; 0.; 0.|]; [|0.; 0.; 0.; 0.|]|]

Notez bien qu’en caml light, Array est remplacé par vect.

Exercice 2
Définir les fonctions nb lines : ’a array -> int et nb columns : ’a array array -> int re-
tournant respectivement le nombre de lignes et de colonnes de la matrice passée en paramètre.

Exercice 3
Définir la fonction fill matrix : ’a array array -> (int * int -> ’a) -> unit telle que fill matrix
m f place dans la matrice m les images de ses coordonnées par f , ainsi on aura mij = f (i, j). Par exemple :

# let m = make_matrix 3 4;;

val m : float array array =
[|[|0.; 0.; 0.; 0.|]; [|0.; 0.; 0.; 0.|]; [|0.; 0.; 0.; 0.|]|]
# fill_matrix m (function i,j -> float_of_int (i + j + 1));;
- : unit = ()
# m;;
- : float array array =
[|[|1.; 2.; 3.; 4.|]; [|2.; 3.; 4.; 5.|]; [|3.; 4.; 5.; 6.|]|]

Exercice 4
Définir la fonction identity : int -> float array array telle que identity n retourne la matrice
identité d’ordre n.

15
Exercice 5
Définir la fonction copy matrix : float array array -> float array array telle que copy matrix
retourne une copie de la matrice m.

Exercice 6
Définir la fonction integers : int -> float array array telle que integers n retourne la matrice
ligne (123 . . . n).

Exercice 7
Définir la fonction str of matrix : float array array -> string retournant une représentation
en chaı̂ne de caractères de la matrice passée en paramètre. Par exemple :

# print_string (str_of_matrix (identity 4));;

1. 0. 0. 0.
0. 1. 0. 0.
0. 0. 1. 0.
0. 0. 0. 1.
- : unit = ()

Exercice 8
Définir la fonction print matrix : float array array -> unit affichant la matrice passée en pa-
ramètre. Par exemple :

# print_matrix (identity 4);;

1. 0. 0. 0.
0. 1. 0. 0.
0. 0. 1. 0.
0. 0. 0. 1.
- : unit = ()

Exercice 9
Définir la fonction matrix of list : float list -> float array array retournant une matrice
ligne contenant les éléments de la liste passée en paramètre. Par exemple,

# matrix_of_list [1.;2.;4.;3.;5.;6.];;
- : float array array = [|[|1.; 2.; 4.; 3.; 5.; 6.|]|]

Exercice 10
Définir la fonction list of vector : ’a array -> ’a list retournant une liste contenant les éléments
de la matrice passée en paramètre. Par exemple,

# list_of_vector [|1;2;3|];;
- : int list = [1; 2; 3]

Exercice 11
Définir la fonction list of matrix : ’a array array -> ’a list list retournant une liste de
liste contenant les éléments de la matrice passée en paramètre. Par exemple,

# list_of_matrix [|[|1;2;3|]; [|4;5;6|]|];;

- : int list list = [[1; 2; 3]; [4; 5; 6]]

16
3.1.2 Opérations matricielles
Nous allons maintenant implémenter les opérations les plus courantes sur les matrices : somme, produit,
transposition, etc.

Exercice 12
Définir la fonction transpose : float array array -> float array array retournant la trans-
posée de la matrice passée en paramètre.

Exercice 13
Définir la fonction rotation : float array array -> float array array retournant une copie
de la matrice passée en paramètre transformée de la façon suivante :

# rotation [|[|1. ; 2. ; 3.|] ; [|4. ; 5. ; 6. |]; [|7. ; 8. ; 9. |]; [|10. ; 11. ; 12. |]|];;
- : float array array =
[|[|12.; 11.; 10.|]; [|9.; 8.; 7.|]; [|6.; 5.; 4.|]; [|3.; 2.; 1.|]|]

Exercice 14
Définir la fonction add matrix : float array array -> float array array -> float array array
retournant la somme des matrices passées en paramètre. Vous créerez l’exception Dimensions mismatch
et l’utiliserez dans cette fonction si les deux matrices ne peuvent être additionnées..

Exercice 15
Définir la fonction trace : float array array -> float retournant la trace de la matrice passée
en paramètre. Vous lèverez l’exception Dimensions mismatch si la matrice n’est pas carrée.

Exercice 16
Définir la fonction mult matrix const : float array array -> float -> float array array telle
que mult matrix const m k retourne le produit de la matrice m par la constante k.

Exercice 17
Définir la fonction mult matrix : float array array -> float array array -> float array array
retournant le produit des matrices passées en paramètre. Vous contrôlerez les dimensions des deux ma-
trices.

Exercice 18
Définir la fonction exp matrix : float array array -> int -> float array array telle que exp matrix
m n retourne m élevée à la puissance n.

3.1.3 Inversion de matrices

Nous allons maintenant nous intéresser à une opération davantage subtile, l’inversion de matrice. Bien
qu’il existe de nombreux algorithmes très performants pour ce faire, nous allons implémenter celui que
vous connaissez déjà. Pour inverser une matrice m, on appliquera le pivot de Gauss sur m jusqu’à obtenir
la matrice identité, on appliquant simultanément ces opérations sur la matrice identité, on obtiendra à la
fin l’inverse de m.
Pour des raisons de simplicité, les indices que nous utiliserons ici ne seront pas les indices mathématiques
(commençant à 1), mais les indices telles qu’ils sont utilisés en caml, en comptant à partir de 0.

17
Exercice 19
Définir la fonction add linear combination : float array array -> int * float -> int * float
-> unit telle que add linear combination m (lg, wg) (ld, wd) effectue l’opération Llg ← wgLlg +
wdLld sur la matrice m. Cette opération consiste à remplacer la ligne d’indice lg par la combinaison
linéaire obtenue en additionnant les lignes d’indices lg et ld pondérées par les réels wd et wd.

Exercice 20
Définir la fonction pivot : float array array -> float array array -> int * int -> unit.
pivot m inv (a, b) effectue sur m une itération de l’algorithme du pivot de Gauss en utilisant mab
comme pivot. Les 0 se trouvant dans les b − 1 premières colonnes de m ne doivent pas être éliminés par
l’exécution de la fonction, et les coefficients de trouvant en dessous du pivot doivent passer à 0.
La matrice m ne doit pas être recopiée mais modifiée, les opérations effectuées sur les lignes de m
doivent être répercutées sur la matrice inv.
Par exemple, l’appel de pivot m inv (0, 0) sur les matrices
   
2 5 8 1 0 0
m =  4 7 0  et inv =  0 1 0 
1 9 3 0 0 1

transforme les variable m et inv de la façon suivante :

   
2 5 8 1 0 0
m= 0 −6 32  et inv =  −4 2 0 
0 13 −2 −1 0 2

Ce qui donne

val m : float array array =

[|[|2.; 5.; 8.|]; [|4.; 7.; 0.|]; [|1.; 9.; 3.|]|]
val inv : float array array =
[|[|1.; 0.; 0.|]; [|0.; 1.; 0.|]; [|0.; 0.; 1.|]|]
# pivot m inv (0, 0);;
- : unit = ()
# m;;
- : float array array =
[|[|2.; 5.; 8.|]; [|0.; -6.; -32.|]; [|0.; 13.; -2.|]|]
# inv;;
- : float array array = [|[|1.; 0.; 0.|]; [|-4.; 2.; 0.|]; [|-1.; 0.; 2.|]|]

Exercice 21
Il n’est possible d’utiliser mab comme pivot que s’il est est non nul. Si mab = 0, il convient de permuter
la ligne d’indice a avec une ligne k (vérifiant k > a) de sorte que le pivot soit non nul. Définir la fonction
find pivot : float array array -> int -> int telle que find pivot m i recherche un pivot dans
la colonne d’indice i, et retourne l’indice de la ligne k telle que mki 6= 0 et k ≥ i. Par exemple,

# find_pivot [|[|0.; 5.; 8.|]; [|0.; 7.; 0.|]; [|1.; 9.; 3.|]|] 0;;
- : int = 2

Si un tel k n’existe pas, alors la matrice n’est pas inversible, et vous lèverez l’exception Singular matrix.

Exercice 22
Définir la fonction swap items : ’a array array -> int * int -> int * int -> unit telle que
swap items m (l1, c1) (l2, c2) permute dans la matrice m les éléments ml1,c1 et ml2,c2 .

18
Exercice 23
Définir la fonction swap lines : ’a array array -> int -> int -> unit telle que swap lines m
i k permute dans la matrice m les lignes d’indices i et k.

Exercice 24
Définir la fonction iteration pivot : float array array -> float array array -> int -> unit
telle que iteration pivot m inv i recherche dans la colonne i de la matrice m un pivot, l’amène en
mii (en permutant éventuellement la ligne i avec une autre ligne), et annule tous les mij (i < j) avec des
opérations sur les lignes de m.
Toutes les opérations sur les lignes de m seront répercutées sur la matrice inv.

Exercice 25
Définir la fonction reduce diagonal : float array array -> float array array -> unit telle
que si m est une matrice diagonale, alors reduce diagonal m inv amène tous les coefficients diagonaux à
1 avec des opérations sur les lignes de m. Toutes ces opérations sur les lignes de m doivent être répercutées
sur inv.

Exercice 26
Définir la fonction apply function : (’a -> ’a) -> ’a -> int -> ’a telle que apply function
f x n retourne l’image de x par la fonction obtenue en composant f avec elle-même n fois. Par exemple,
apply function f x 3 retourne f 3 (x) = f (f (f (x))). On considérera que f 0 est la fonction identité.

Exercice 27
Définir la fonction inverse matrice : float array array -> float array array telle que inverse matrice
m retourne la matrice inverse de m. Attention, inverse matrice ne doit pas produire d’effet de bord.

Exercice 28
Définir la fonction solve system : float array array -> float array array -> float array
array tel que solve system a y retourne la solution x de l’équation Ax = y.

19
3.2 Polynômes et analyse numérique
3.2.1 Représentation des polynômes
Nous souhaitons représenter des polynômes à variable réelle et à coefficients réels. Nous représenterons
un monôme par un couple (c, e), où c est le coefficient du monôme de degré e. Un polynôme sera représenté
par une liste de couples disposés par ordre de degrés strictement décroissant. Par exemple, le polynôme
x2 − x + 1 est représenté par la liste [(2.,2) ;(-1., 1) ; (1.,0)].

Exercice 1
Comment représenter le polynôme x + 2 − x3 ?

Exercice 2
Quel polynôme est représenté par [(4., 4) ; (2., 3) ; (-3., 2) ; (3., 0)] ?

Exercice 3
Définir la fonction polynomeUnite : (float * int) list telle que polynomeUnite ; ; retourne le
polynome unité, c’est-à-dire l’élément neutre pour la multiplication dans l’anneau des polynômes.

Exercice 4
Définir la fonction polynomeNul : (float * int) list telle que polynomeNul ; ; retourne le poly-
nome nul, c’est-à-dire l’élément neutre pour l’addition dans l’anneau des polynômes.

Exercice 5
Définir la fonction strOfMonome : float * int -> string telle que strOfMonome m retourne une
représentation au format chaı̂ne de caractères du monôme m.

# strOfMonome (4., 3);;

- : string = "4.*X^3"
# strOfMonome (-2., 1);;
- : string = "-2.*X^1"
# strOfMonome (2., 0);;
- : string = "2.*X^0"

Exercice 6
Définir la fonction strOfPolynome : (float * int) list -> string telle que strOfPolynome p
retourne une représentation au format chaı̂ne de caractères du polynôme p. Par exemple,

# strOfPolynome [(0., 3) ; (-1., 2); (0., 1) ; (2., 0)];;

- : string = "0.*X^3 + -1.*X^2 + 0.*X^1 + 2.*X^0"

Exercice 7
Définir la fonction expOfPolynome : (float * int) list -> exp telle que expOfPolynome p conver-
tit le polynôme p en expression de la forme donnée dans 1.3.2, par exemple

# let k = expOfPolynome [(-1., 2);(2., 0)];;

val k : exp =
Somme (Produit (Const (-1.), Puiss (X, 2)),
Somme (Produit (Const 2., Puiss (X, 0)), Const 0.))
# str_of_exp k;;
- : string = "((-1.*(x^2))+((2.*(x^0))+0.))"

20
3.2.2 Opérations sur les polynômes
Nous allons dans cette section implémenter les opérations les plus courantes sur les polynômes :
addition, soustraction et produit. D’autres opérations, plus élaborées, seront examinées dans les sections
suivantes.
Pour toutes les questions suivantes, un coefficient sera considéré comme nul s’il contient une valeur
inférieure à 10−15 .

Exercice 8
Définir la fonction absFloat : float -> float telle que absFloat x retourne la valeur absolue de
x.

Exercice 9
Définir la fonction estNul : float -> bool telle que estNul x retourne vrai si et seulement si
|x| ≤ 10−15 .

Exercice 10
Définir la fonction addPolynomes : (float * ’a) list -> (float * ’a) list -> (float * ’a)
list telle que addPolynomes a b retourne la somme des polynômes a et b.

Exercice 11
Définir la fonction multConst : (float * ’a) list -> float -> (float * ’a) list telle que
multConst p k retourne le produit du polynôme p par la constante k.

Exercice 12
Définir la fonction subPolynomes : (float * ’a) list -> (float * ’a) list -> (float * ’a)
list telle que subPolynomes a b retourne le résultat de la soustraction du polynôme b au polynôme a.

Exercice 13
Définir la fonction multXk : (’a * int) list -> int -> (’a * int) list telle que multXk p k
retourne le polynôme p multiplié par X k .

Exercice 14
Définir la fonction multMonome : (float * int) list -> float * int -> (float * int) list
telle que multMonome p (c, e) retourne le produit de p par cX e .

Exercice 15
Définir la fonction multPolynomes : (float * int) list -> (float * int) list -> (float *
int) list telle que multPolynomes p q retourne le produit des polynômes p et q.

Exercice 16
Définir la fonction expPolynome : (float * int) list -> int -> (float * int) list telle que
expPolynome p n retourne le polynôme p élevé à la puissance n.

21
Exercice 17
Définir la fonction polynomeOfExp : exp -> (float * int) list telle que polynomeOfExp e conver-
tit en polynôme l’expression e donnée dans la forme décrite en 1.3.2, par exemple

# let k = polynomeOfExp (Puiss(Somme(Const(1.), X), 4));;

val k : (float * int) list = [(1., 4); (4., 3); (6., 2); (4., 1); (1., 0)]
# strOfPolynome k;;
- : string = "1.*X^4 + 4.*X^3 + 6.*X^2 + 4.*X^1 + 1.*X^0"

3.2.3 Évaluation et méthode de Horner

Exercice 18
Définir la fonction floatExp : float -> int -> float telle que floatExp x n retourne xn .

Exercice 19
Définir la fonction evalueMoche : (float * int) list -> float -> float telle que evalueMoche
p x retourne l’image de x par la fonction polynôme représentée par p.

Exercice 20
Quelle la complexité de l’évaluation d’un polynôme de degré n avec la fonction evalueMoche ?

Exercice 21
Nous allons redéfinir la fonction d’évaluation d’un polynôme en utilisant la méthode de Horner. A titre
d’exemple, observons que le polynôme 5x3 +x2 +3x−1 = (5x2 +x+3)x−1, que 5x2 +x+3 = (5x+1)x+3,
puis que 5x + 1 = (5)x + 1, ce qui nous donne

5x3 + x2 + 3x − 1 = (((5)x + 1)x + 3)x − 1

On généralise ce procédé avec la relation de récurrence

an xn + . . . + a1 x + a0 = (an xn−1 + . . . + a1 )x + a0

Utiliser ce procédé pour reformuler les expressions

x3 − 2x2 + 7x − 1

et
4x7 + 2x3 − 2x2 − x + 1

Exercice 22
Définir la fonction evalHorner : (float * int) list -> float -> float telle que evalHorner p
x retourne l’image de x par la fonction polynôme représentée par p. Vous utiliserez une fonction auxiliaire
avec un accumulateur.

Exercice 23
Quelle la complexité de l’évaluation d’un polynôme de degré n avec la fonction evalHorner ?

3.2.4 Dérivée et intégrale

Exercice 24
Définir la fonction derivePolynome : (float * int) list -> (float * int) list telle que derivePolynome
p retourne la dérivée de p.

22
Exercice 25
Définir la fonction primitivePolynome : (float * int) list -> (float * int) list telle que
primitivePolynome p retourne une primitive de p.

Exercice 26
Définir la fonction integrePolynome : (float * int) list -> float -> float -> float telle
Rb
que integrePolynome p a b retourne a p(x)dx.

3.2.5 Calculs approchés d’intégrales

Lorsque les fonctions à intégrer sont difficiles à primitiver, il est usuel d’utiliser des algorithmes
donnant rapidement des valeurs approchées d’une précision plus ou moins convenable selon le domaine
d’application. Nous implémenterons la méthode des rectangles ainsi que la méthode des trapèzes.
Dans les deux méthodes que nous implémenterons, nous utiliserons la subdivision du segment [a, b] en
n segments de même taille, que nous noterons [a0 , a1 ], [a1 , a2 ], . . . , [an , an−1 ] et tels que ∀i ∈ {1, . . . , n}
les valeurs (ai − ai−1 ) soient identiques.

Exercice 27
R ai
La méthode des rectangles consiste à approcher l’aire p(x)dx par la surface du rectangle délimité
ai−1
Rb
par les points de coordonnées (ai−1 , 0), (ai , 0), (ai−1 , p(ai−1 )) et (ai , p(ai−1 )). L’intégrale a p(x)dx sera
R ai
donc approchée par la somme sur i des ai−1 p(x)dx.
Définir la fonction rectangles : (float * int) list -> float -> float -> int -> float telle
Rb
que rectangles p a b n retourne une approximation de a p(x)dx en utilisant n rectangles.

Exercice 28
R ai
La méthode des trapèzes est une variante dans laquelle on approche chaque ai−1 p(x)dx par la surface
du trapèze délimité par les points de coordonnées (ai−1 , 0), (ai , 0), (ai−1 , p(ai−1 )) et (ai , p(ai )).
Définir la fonction trapezes : (float * int) list -> float -> float -> int -> float telle
Rb
que trapezes p a b n retourne une approximation de a p(x)dx en utilisant n trapèzes. Il est conseillé
de chercher à simplifier la formule donnant la valeur de l’approximation et de la calculer avec une boucle.

3.2.6 Interpolation
A partir d’une liste de n points du plan [(x0 , y0 ), (x1 , y1 ), . . . , (xn , yn )], nous souhaitons déterminer
un polynôme p, de degré n tel que tel que ∀i ∈ {0, . . . , n}, p(xi ) = yi .

Exercice 29
Définir la fonction facteurLagrange : float -> (float * int) list telle que facteurLagrange
z retourne le polynôme (x − z).

Exercice 30
Étant donné i, posons

fi (x) = Πj6=i (x − xj )

Exercice 31
Définir la fonction lagrange f i : (float * ’a) list -> float -> (float * int) list telle que
si pts est la liste de points [(x0 , y0 ), (x1 , y1 ), . . . , (xn , yn )], lagrange f i pts x i retourne fi .

23
Exercice 32
Déterminer en fonction de fi un polynôme pi vérifiant pi (xi ) = yi et ∀j{0, . . . , n} tel que i 6= j,
pi (xj ) = 0.

Exercice 33
Définir la fonction lagrange p i : (float * ’a) list -> float * float -> (float * int) list
telle que lagrange p i pts (x i, y i) retourne le polynôme pi .

Exercice 34
Déterminer en fonction des pi un polynôme p interpolant les points [(x0 , y0 ), (x1 , y1 ), . . . , (xn , yn )].

Exercice 35
Définir la fonction interpolationLagrange : (float * float) list -> (float * int) list telle
que interpolationLagrange pts retourne un polynôme interpolant les points pts.

Exercice 36
Il existe une façon assez élégante d’interpoler un polynôme p(x) = a0 + a1 x + a2 x2 + . . . + an xn passant
par les points [(x0 , y0 ), (x1 , y1 ), . . . , (xn , yn )] en posant l’équation matricielle

x20 . . . xj0 . . . xn0

     
1 x0 a0 y0
 1 x1 x21 . . . xj1 . . . xn1   a1   y1 
.. ..
     
 .. .. .. .. ..     

 . . . . .  
× .  
= . 


 1 xi x2i ... xji ... xni  
  ai  
  yi 

 .. .. .. .. ..   ..   .. 
 . . . . .   .   . 
1 xn x2n ... xjn ... xnn an yn
Définir la fonction interpolationVandermonde : (float * float) list -> (float * int) list
telle queinterpolationVandermonde pts retourne un polynôme interpolant les points pts. Vous utilise-
rez l’algorithme de résolution de systèmes linéaires codé dans le TP précédent.

3.2.7 Méthode de Newton

La méthode de Newton consiste, étant donnée une fonction dérivable f , à définir une suite numérique
convergeant vers un point l solution de l’équation f (l) = 0. Les conditions garantissant la convergence
sortent du cadre de cet exercice.
Étant donné un point xn de cette suite, on détermine le point suivant xn+1 en calculant la tangente
T à f au point d’abscisse xn . xn+1 est l’abscisse de l’intersection de T et de l’axe des abscisses.

Exercice 37
Exprimer xn+1 en fonction de f , de f 0 et de xn .

Exercice 38
Définir la fonction newton : (float * int) list -> float -> int -> float telle que si f est
la fonction polynôme représentée par p, et si le premier point de la suite x est z, alors newton p z n
retourne le n-ème point de la suite x.

3.2.8 Division euclidienne

3.2.9 Méthode de Sturm

24
Chapitre 4

Quelques corrigés

4.1 Initiation
(∗ 1 . 1 . 1 f a c t o r i e l l e ∗)

(∗ e x e r c i c e 1 ∗)

l e t rec f a c t o r i e l l e = function
0 −> 1
| n −> n ∗ ( f a c t o r i e l l e (n −1));;

(∗ e x e r c i c e 2 ∗)

l e t rec f a c t o r i e l l e a c c n k =
i f n = 0 then
k
else
factorielle acc ( n−1) ( n∗k ) ; ;

(∗ e x e r c i c e 3 ∗)

let factorielle bis n = factorielle acc n 1;;

(∗ 1 . 1 . 2 e x p o n e n t i a t i o n l e n t e ∗)

(∗ e x e r c i c e 4 ∗)

l e t rec s l o w e x p b = function
0 −> 1
| n −> s l o w e x p b ( n − 1 ) ∗ b ; ;

(∗ e x e r c i c e 5 ∗)

l e t rec s l o w e x p a c c b n a c c =
i f ( n = 0 ) then
acc
else
slow exp acc b (n − 1) ( acc ∗ b ) ; ;

(∗ e x e r c i c e 6 ∗)

let slow exp bis b n = slow exp acc b n 1 ; ;

(∗ 1 . 1 . 3 e x p o n e n t i a t i o n r a p i d e ∗)

(∗ e x e r c i c e 7 ∗)

let rec e v e n r e c = function

0 −> t r u e
| 1 −> f a l s e
| n −> e v e n r e c ( n − 2 ) ; ;

l e t even n = n mod 2 = 0 ; ;

(∗ e x e r c i c e 8 ∗)

l e t rec f a s t e x p b n =
i f ( n = 0 ) then
1

25
 else
i f ( even n ) then
f a s t e x p ( b∗b ) ( n / 2 )
else
f a s t e x p ( b ) ( n−1) ∗ b ; ;

(∗ e x e r c i c e 9 ∗)

(∗
Le parametre n de l a f o n c t i o n d e c r i t une s u i t e d ’ e n t i e r s s t r i c t e m e n t
d e c r o i s s a n t e au f i l d e s a p p e l s r e c u r s i f s . Donc l a f o n c t i o n s e t e r m i n e .

Notez b i e n que ca ne s e r a i t pas l e c a s s i l ’ on a v a i t p l a c e

f a s t e x p f a s t e x p ( b ) ( n /2) 2
dans l e premier a p p e l r e c u r s i f .
∗)

(∗ e x e r c i c e 10 ∗)

l e t rec f a s t e x p a c c b n a c c =
i f ( n = 0 ) then
acc
else
i f ( even n ) then
f a s t e x p a c c ( b∗b ) ( n / 2 ) a c c
else
f a s t e x p a c c ( b ) ( n−1) ( a c c ∗ b ) ; ;

let fast exp bis b n = fast exp acc b n 1;;

(∗ 1 . 1 . 4 pgcd ∗)

(∗ e x e r c i c e 11 ∗)

(∗
Lors de chaque a p p e l r e c u r s i f Le deuxieme parametre de l a f o n c t i o n (m)
d e v i e n t ( n mod m) . Or | n mod m| < |m| , ce q u i s ’ o b t i e n t a i s e m e n t av ec l a
d e f i n i t i o n de l a d i v i s i o n dans z :

on d i v i s e n par m en d e t e r m i n a n t q e t r t e l s que n = mq + r , | r | < |m|

I c i on a r = n mod m. Comme l e deuxieme parametre e s t t o u j o u r s s t r i c t e m e n t

d e c r o i s s a n t , e t que l ’ a l g o r i t h m e s ’ a r r e t e l o r s q u ’ i l a t t e i n t 0 , l a f o n c t i o n
se termine .
∗)

(∗ e x e r c i c e 12 ∗)

l e t rec gcd n m =
i f (m = 0 ) then
n
else
gcd m ( n mod m ) ; ;

(∗ 1 . 1 . 5 a l p h a b e t ∗)

(∗ e x e r c i c e 13 ∗)

let lettre suivante a = char of int ( int of char a + 1);;

(∗ e x e r c i c e 14 ∗)

let f i g u r e o f i n t n = char of int (n − 1 + ( int of char ’1 ’));;

(∗ e x e r c i c e 15 ∗)

l e t c o m p a r e l e t t r e s a b = i n t o f c h a r a <= i n t o f c h a r b ; ;

(∗ e x e r c i c e 16 ∗)

l e t rec a l p h a b e t l e t t r e d e p a r t l e t t r e a r r i v e e =
i f ( c o m p a r e l e t t r e s l e t t r e d e p a r t l e t t r e a r r i v e e ) then
(
print char lettre depart ;
alphabet ( l e t t r e s u i v a n t e l e t t r e d e p a r t ) l e t t r e a r r i v e e
)
else
();;

(∗ 1 . 1 . 6 mise s o u s forme r e c u r s i v e ∗)

26
(∗ e x e r c i c e 17 ∗)

l e t rec mult x y =
i f ( y = 0 ) then
y
else
mult x ( y − 1 ) + x ; ;

(∗ e x e r c i c e 18 ∗)

l e t rec m u l t a c c x y a c c =
i f ( y = 0)
then a c c
else
mult acc x ( y − 1) ( acc + x ) ; ;

let mult bis x y = mult acc x y 0 ; ;

(∗ 1 . 1 . 7 i n d i c a t r i c e d ’ E u l e r ∗)

(∗ e x e r c i c e 19 ∗)

l e t rec nb prem a n =
i f ( a >= n ) then
0
else
(
i f ( gcd a n = 1 ) then
1
else
0
)
+ nb prem ( a + 1 ) n ; ;

let i n d e u l e r n = nb prem 0 n ; ;

4.2 Listes
(∗ e x e r c i c e 1 ∗)

l e t rec n a u n = function
0 −> [ ]
| n −> n : : ( n a u n ( n − 1 ) ) ; ;

(∗ e x e r c i c e 2 ∗)

l e t rec u n a n a c c n a c c =
i f ( n = 0 ) then
acc
else
u n a n a c c ( n−1) ( n : : a c c ) ; ;

let un a n n = un a n acc n [ ] ; ;

(∗ e x e r c i c e 3 ∗)

l e t rec s u p p r i m e l n =
i f ( n <= 0 ) then
l
else
match l with
[ ] −> [ ]
| head : : t a i l −> s u p p r i m e t a i l (n −1);;

(∗ e x e r c i c e 4 ∗)

l e t rec l o n g p r e f i x e l =
match l with
[ ] −> 0
| x : : [ ] −> 1
| x : : y : : t a i l −>
i f ( x = y ) then
1 + long prefixe (y : : t a i l )
else
1;;

4.3 Types récursifs

27
(∗ 1 . 3 . 1 Tri par a r b r e b i n a i r e de r e c h e r c h e ∗)

type ’ a b i n t r e e = Empty | Node o f ’a bin tree ∗ ’a ∗ ’a bin tree ; ;

(∗ e x e r c i c e 1 ∗)

l e t rec i n s a b r f x t = match t with

Empty −> Node ( Empty , x , Empty )
| Node ( l e f t , y , r i g h t ) −> i f ( f x y ) then
Node ( i n s a b r f x l e f t , y , r i g h t )
else
Node ( l e f t , y , i n s a b r f x r i g h t ) ; ;

(∗ e x e r c i c e 2 ∗)

l e t rec a b r o f l i s t f l = match l with

[ ] −> Empty
| x : : t a i l −> i n s a b r f x ( a b r o f l i s t f tail );;

(∗ e x e r c i c e 3 ∗)
l e t rec l i s t o f a b r = function
Empty −> [ ]
| Node ( l e f t , x , r i g h t ) −> ( l i s t o f a b r l e f t )@[ x ]@( l i s t o f a b r right ) ; ;

(∗ e x e r c i c e 4 ∗)

let tri liste f l = list of abr ( abr of list f l );;

(∗ 1 . 3 . 2 F o n c t i o n s polynomes ∗)

type exp =
Const o f f l o a t
| X
| Somme o f exp ∗ exp
| P r o d u i t o f exp ∗ exp
| P u i s s o f exp ∗ i n t ; ;

(∗ e x e r c i c e 5 ∗)

l e t rec s t r o f e x p = function
Const ( x ) −> ( s t r i n g o f f l o a t x )
| X −> ”x”
| Somme( l e f t , r i g h t ) −> ” ( ” ˆ ( s t r o f e x p l e f t ) ˆ ”+” ˆ ( s t r o f e x p r i g h t ) ˆ ”)”
| P r o d u i t ( l e f t , r i g h t ) −> ” ( ” ˆ ( s t r o f e x p l e f t ) ˆ ” ∗ ” ˆ ( s t r o f e x p r i g h t ) ˆ ”)”
| P u i s s ( l e f t , n ) −> ” ( ” ˆ ( s t r o f e x p l e f t ) ˆ ” ˆ ” ˆ ( s t r i n g o f i n t n ) ˆ ”)” ; ;

(∗ e x e r c i c e 6 ∗)

l e t rec image e x = match e with

Const ( c ) −> c
| X −> x
| Somme( l e f t , r i g h t ) −> image l e f t x +. image r i g h t x
| P r o d u i t ( l e f t , r i g h t ) −> image l e f t x ∗ . image r i g h t x
| P u i s s ( l e f t , n ) −> l e t rec f a s t e x p b = function
0 −> 1 .
| n −> i f ( n mod 2 = 0 ) then
f a s t e x p (b ∗ . b) (n/2)
else
f a s t e x p ( b ∗ . b ) ( ( n −1)/2) ∗ . b
in
f a s t e x p ( image l e f t x ) n ; ;

(∗ e x e r c i c e 7 ∗)

l e t rec d e r i v e = function
Const ( ) −> Const ( 0 . )
| X −> Const ( 1 . )
| Somme( l e f t , r i g h t ) −> Somme( d e r i v e l e f t , d e r i v e r i g h t )
| P r o d u i t ( l e f t , r i g h t ) −> Somme( P r o d u i t ( d e r i v e l e f t , r i g h t ) , P r o d u i t ( l e f t , d e r i v e r i g h t ) )
| P u i s s ( l e f t , n ) −> P r o d u i t ( P r o d u i t ( Const ( f l o a t o f i n t n ) , d e r i v e l e f t ) , P u i s s ( l e f t , n − 1 ) ) ; ;

(∗ e x e r c i c e 8 ∗)

l e t rec d e g r e = function
Const ( ) −> 0
| X −> 1
| Somme( l e f t , r i g h t ) −> max ( d e g r e l e f t ) ( d e g r e r i g h t )
| Produit ( l e f t , r i g h t ) −> d e g r e l e f t + ( d e g r e r i g h t )
| Puiss ( l e f t , n ) −> d e g r e l e f t ∗ n ; ;

28
4.4 Le carré qui rend fou
(∗ A f f i c h a g e de carrà c s ∗)

(∗ e x e r c i c e 1 ∗)

l e t rec l i g n e n =
”. ” ˆ (
i f ( n > 1 ) then
l i g n e (n − 1)
else
” \n”
);;

(∗ e x e r c i c e 2 ∗)

l e t rec c a r r e n =
l e t rec c a r r e a u x = function
0 −> ” \n”
| k −> l i g n e n ˆ ( c a r r e a u x ( k − 1 ) )
in
carre aux n ; ;

(∗ A f f i c h a g e de carrà c s d ’ à c toiles ∗)

(∗ e x e r c i c e 3 ∗)

l e t rec e t o i l e s a b n =
i f ( n = 0 ) then
” \n”
else
(
i f ( a <= 1 && b >= 1 ) then
”∗ ”
else
”. ”
)
ˆ ( e t o i l e s ( a −1) ( b−1) ( n − 1 ) ) ; ;

(∗ e x e r c i c e 4 ∗)

l e t c a r r e e t o i l e s ( l h a u t , l b a s , cgauche , c d r o i t e ) n =
l e t rec c a r r e a u x l h a u t l b a s k =
i f ( k > n ) then
” \n”
else
(
(
i f ( l h a u t <= 1 && l b a s >= 1 ) then
e t o i l e s cgauche c d r o i t e n
else
ligne n
)
ˆ ( carre aux ( lhaut − 1) ( lbas − 1) ( k + 1))
)
in
carre aux lhaut lbas 1 ; ;

(∗ Enumà c ration d e s carrà c s ∗)

(∗ e x e r c i c e 5 ∗)

l e t rec c o u p l e s c o o r d o n n e e s a f i x e a b =
i f ( a > b ) then
[]
else
( c o u p l e s c o o r d o n n e e s a f i x e a ( b −1))@ [ ( a , b ) ] ; ;

(∗ e x e r c i c e 6 ∗)

let couples coordonnees n =

l e t rec c o u p l e s c o o r d o n n e e s a u x a =
i f ( a > n ) then
[]
else
c o u p l e s c o o r d o n n e e s a f i x e a n@( c o u p l e s c o o r d o n n e e s a u x ( a +1))
in
couples coordonnees aux 1 ; ;

(∗ e x e r c i c e 7 ∗)

29
l e t rec c o o r d o n n e e s c a r r e s c o l o n n e s f i x e e s ( cgauche , c d r o i t e ) n =
i f ( n <= c d r o i t e − c g a u c h e ) then
[]
else
c o o r d o n n e e s c a r r e s c o l o n n e s f i x e e s ( cgauche , c d r o i t e ) ( n−1)
@ [ ( n − ( c d r o i t e − c g a u c h e ) , n , cgauche , c d r o i t e ) ] ; ;

(∗ e x e r c i c e 8 ∗)

let coordonnees carres n =

l e t c o l o n n e s = c o u p l e s c o o r d o n n e e s n in
l e t rec c o m p l e t e c o o r d o n n e e s c o l o n n e s =
match c o l o n n e s with
[ ] −> [ ]
| h : : t −> c o o r d o n n e e s c a r r e s c o l o n n e s f i x e e s h n
@( c o m p l e t e c o o r d o n n e e s t ) in
complete coordonnees colonnes ; ;

(∗ e x e r c i c e 9 ∗)

let t o u s l e s c a r r e s n =
l e t rec l i s t e c a r r e s l = match l with
[ ] −> [ ]
| c o o r d : : t −> c a r r e e t o i l e s c o o r d n : : ( l i s t e c a r r e s t)
in
l i s t e c a r r e s ( coordonnees carres n ) ; ;

(∗ e x e r c i c e 10 ∗)

l e t rec p r i n t s t r l i s t = function
[ ] −> p r i n t s t r i n g ” \n” ;
| h : : t −> p r i n t s t r i n g h ; p r i n t s t r l i s t t ;;

print str list ( tous les carres 3);;

(∗ Enumà c ration d e s r e c t a n g l e s ∗)

(∗ e x e r c i c e 11 ∗)

l e t rec c o n c a t p r o d u i t s ( a , b ) l = match l with

[ ] −> [ ]
| ( c , d ) : : t −> ( a , b , c , d ) : : ( c o n c a t p r o d u i t s ( a , b ) t ) ; ;

(∗ e x e r c i c e 12 ∗)

l e t rec c r o i s e c o o r d o n n e e s a b = match a with

[ ] −> [ ]
| h : : t −> ( c o n c a t p r o d u i t s h b )@( c r o i s e c o o r d o n n e e s t b ) ; ;

(∗ e x e r c i c e 13 ∗)

let coordonnees rectangles n =

l e t c o l o n n e s = c o u p l e s c o o r d o n n e e s n in
croise coordonnees colonnes colonnes ; ;

(∗ e x e r c i c e 14 ∗)

let tous les rectangles n =

l e t rec l i s t e r e c t a n g l e s l = match l with
[ ] −> [ ]
| c o o r d : : t −> c a r r e e t o i l e s c o o r d n : : ( l i s t e r e c t a n g l e s t)
in
l i s t e r e c t a n g l e s ( coordonnees rectangles n ) ; ;

(∗ e x e r c i c e 15 ∗)

(∗

I l e x i s t e C n+1 n fa çons de c h o i s i r les l i g n e s e t a u t a n t de fa çons de

c h o i s i r l e s c o l o n n e s , donc . . .

∗)

4.5 Algèbre
l e t m a k e v e c t = Array . make ; ;
l e t l e n g t h v e c t = Array . l e n g t h ; ;

30
(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t make matrix n p =
l e t m = m a k e v e c t n [ | | ] in
f o r i = 0 to ( n−1) do
m. ( i ) <− m a k e v e c t p 0 . ;
done ;
m; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let n b l i n e s m = l e n g t h v e c t m; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t n b c ol u m n s m = l e n g t h v e c t m . ( 0 ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let f i l l l i n e m i f =
l e t p = n b c o l u m n s m in
f o r j = 0 to ( p−1) do
m. ( i ) . ( j ) <− f j ;
done ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let f i l l m a t r i x m f =
l e t n = n b l i n e s m in
f o r i = 0 to ( n − 1 ) do
f i l l l i n e m i ( function j −> f ( i , j ) ) ;
done ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let identity n =
l e t m = make matrix n n in
f i l l m a t r i x m ( function i , j −> i f ( i = j ) then 1 . e l s e 0.);
m; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let copy matrix m =

l e t c = make matrix ( n b l i n e s m) ( n b c o l u m n s m) in
f i l l m a t r i x c ( function i , j −> m. ( i ) . ( j ) ) ;
c ;;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let integers n =
l e t m = make matrix 1 n in
f i l l m a t r i x m ( function , j −> f l o a t o f i n t ( j +1));
m; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let str of matrix m =

l e t s t r = r e f ” ” in
l e t n = n b l i n e s m in
l e t p = n b c o l u m n s m in
f o r i = 0 to ( n − 1 ) do
f o r j = 0 to ( p − 1 ) do
s t r := ! s t r ˆ ” ” ˆ s t r i n g o f f l o a t m. ( i ) . ( j ) ;
done ;
s t r := ! s t r ˆ ” \n”
done ;
! str ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let print matrix m =

p r i n t s t r i n g ( s t r o f m a t r i x m) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let m a t r i x o f l i s t l =
l e t m = make matrix 1 ( L i s t . l e n g t h l ) in
l e t rec f i l l i l = match l with
[ ] −> ( )
| h : : t −> m. ( 0 ) . ( i ) <− h ; f i l l ( i +1) t in
fill 0 l;

31
 m; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let l i s t o f v e c t o r v =
l e t rec l i s t o f v e c t o r a c c a c c = function
−1 −> a c c
| j −> l i s t o f v e c t o r a c c ( v . ( j ) : : a c c ) ( j −1) in
list of vector acc [ ] ( length vect v − 1 ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let l i s t o f m a t r i x m =
l e t rec l i s t o f m a t r i x a c c a c c m = function
−1 −> a c c
| i −> l i s t o f m a t r i x a c c ( ( l i s t o f v e c t o r m. ( i ) ) : : a c c ) m ( i −1) in
list of matrix acc [ ] m ( nb lines m − 1);;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let transpose m =
l e t n = n b l i n e s m in
l e t p = n b c o l u m n s m in
l e t t = make matrix p n in
f i l l m a t r i x t ( function i , j −> m. ( j ) . ( i ) ) ;
t ;;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let rotation m =
l e t n = n b l i n e s m in
l e t p = n b c o l u m n s m in
l e t t = make matrix n p in
f i l l m a t r i x t ( function i , j −> m. ( n − i − 1 ) . ( p − j − 1 ) ) ;
t ;;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

exception D i m e n s i o n s m i s m a t c h ; ;

let add matrix a b =

l e t l a = n b l i n e s a in
l e t l b = n b l i n e s b in
l e t ca = n b c o l u m n s a in
l e t cb = n b c o l u m n s b in
i f ( l a = l b && ca = cb ) then
l e t c = make matrix l a ca in
f i l l m a t r i x c ( function i , j −> a . ( i ) . ( j ) +. b . ( i ) . ( j ) ) ;
c;
else
r a i s e Dimensions mismatch ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let trace m =
l e t n = n b l i n e s m in
l e t p = n b c o l u m n s m in
i f ( n <> p ) then
r a i s e Dimensions mismatch
else
l e t somme = r e f 0 . in
f o r i = 0 to ( n − 1 ) do
somme := ! somme +. m. ( i ) . ( i ) ;
done ;
! somme ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let mult matrix const m k =

l e t n = n b l i n e s m in
l e t p = n b l i n e s m in
l e t c = make matrix n p in
f i l l m a t r i x c ( function ( i , j ) −> k ∗ . m. ( i ) . ( j ) ) ;
c ;;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let mult matrix a b =

let la = n b l i n e s a in
let lb = n b l i n e s b in
l e t ca = n b c o l u m n s a in

32
 l e t cb = n b c o l u m n s b in
i f ( ca = l b ) then
l e t c = make matrix l a cb in
let f i l l f u n c t i o n ( i , j ) =
(
l e t t o t a l = r e f 0 . in
f o r k = 0 to ( ca − 1 ) do
t o t a l := ! t o t a l +. a . ( i ) . ( k ) ∗ . b . ( k ) . ( j ) ;
done ;
! total ;
) in
fill matrix c fill function ;
c;
else
r a i s e Dimensions mismatch ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec e x p m a t r i x m n =
i f ( n = 0 ) then
i d e n t i t y ( n b c o l u m n s m)
else
mult matrix m ( exp matrix m (n − 1 ) ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t a d d l i n e a r c o m b i n a t i o n m ( l g , wg ) ( l d , wd) =
f i l l l i n e m l g ( function j −> m. ( l g ) . ( j ) ∗ . wg +. m. ( l d ) . ( j ) ∗ . wd ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let pivot m inv (a , b) =

l e t n = n b l i n e s m in
l e t v a l e u r p i v o t = m. ( a ) . ( b ) in
f o r i = ( a+1) to ( n−1) do
l e t r = −.m. ( i ) . ( b ) in
add linear combination inv ( i , v a l e u r p i v o t ) (a , r ) ;
add linear combination m ( i , valeur pivot ) (a , r ) ;
done ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

exception S i n g u l a r m a t r i x ; ;

let find pivot m i =

l e t k = r e f i in
l e t p = n b l i n e s m in
while ( ! k < p && m . ( ! k ) . ( i ) = 0 . ) do
k := ! k + 1 ;
done ;
i f ! k = p then
raise Singular matrix ;
!k;;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t s w a p i t e m s m ( l 1 , c1 ) ( l 2 , c2 ) =
l e t tmp = m. ( l 1 ) . ( c1 ) in
m. ( l 1 ) . ( c1 ) <− m. ( l 2 ) . ( c2 ) ;
m. ( l 2 ) . ( c2 ) <− tmp ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let swap lines m i k =

f o r j = 0 to ( n b c o l u m n s m − 1 ) do
swap items m ( i , j ) (k , j ) ;
done ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let i t e r a t i o n p i v o t m inv i =
l e t k = f i n d p i v o t m i in
i f ( i <> k ) then
( swap lines m i k ;
swap lines inv i k ;
);
pivot m inv ( i , i ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let reduce diagonal m inv =

33
 l e t n = n b l i n e s m in
f o r i = 0 to ( n−1) do
l e t c o e f f = m. ( i ) . ( i ) in
f i l l l i n e m i ( function j −> m. ( i ) . ( j ) / . c o e f f ) ;
f i l l l i n e i n v i ( function j −> i n v . ( i ) . ( j ) / . c o e f f ) ;
done ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec a p p l y f u n c t i o n f x = function
0 −> x
| n −> a p p l y f u n c t i o n f ( f x ) ( n − 1 ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let invert matrix m =

l e t n = n b l i n e s m in
let reduce and rotate (a , b) =
(
f o r k = 0 to ( n − 2 ) do
iteration pivot a b k;
done ;
( rotation a , rotation b)
)
in
l e t (m, i n v ) = a p p l y f u n c t i o n r e d u c e a n d r o t a t e ( c o p y m a t r i x m, i d e n t i t y n ) 2 in
reduce diagonal m inv ;
inv ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let solve system a y =

mult matrix ( i n v e r t m a t r i x a ) y ; ;

4.6 Polynômes
[( −1. ,3);(1. , 1); (2. ,0)];;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

(∗ 4Xˆ4 + 2Xˆ3 −3Xˆ2 + 3 ∗)

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t polynomeUnite = [ ( 1 . , 0 ) ] ; ;
l e t polynomeNul = [ ( 0 . , 0 ) ] ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t strOfMonome ( c o e f f , exp ) =
s t r i n g o f f l o a t c o e f f ˆ ” ∗Xˆ ” ˆ s t r i n g o f i n t exp ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec st r O f P o ly n o m e = function
| [ ] −> s t r O f P o l yn o m e polynomeNul
| h : : [ ] −> strOfMonome h
| h : : t −> strOfMonome h ˆ ” + ” ˆ s t r O f P o l y n o m e t ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec expOfPolynome = function

[ ] −> Const 0 .
| ( c , e ) : : t −> Somme ( P r o d u i t ( Const ( c ) , P u i s s (X, e ) ) , expOfPolynome t ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let absFloat x =
i f x > 0 . then
x
e l s e ( −. x ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let estNul x = absFloat x < 1. e −15;;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec addPolynomes p q = match ( p , q ) with

| [] , −> q

34
| , [ ] −> p
| ( c o e f f p , expp ) : : t a i l p , ( c o e f f q , expq ) : : t a i l q −>
i f ( expp = expq ) then
(
i f ( e s t N u l ( c o e f f p +. c o e f f q ) ) then
( addPolynomes t a i l p t a i l q )
else
( c o e f f p +. c o e f f q , expp ) : : ( addPolynomes t a i l p tailq )
)
else
i f ( expp > expq ) then
( c o e f f p , expp ) : : ( addPolynomes t a i l p q )
else
( c o e f f q , expq ) : : ( addPolynomes p t a i l q ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec multConst p k = match p with

[ ] −> [ ]
| ( c , e ) : : t −>
( i f ( a b s F l o a t ( k ∗ . c ) > 1 . e −15) then
[ ( k ∗. c , e ) ]
else
[]
)@( multConst t k ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t subPolynomes a b = addPolynomes a ( multConst b ( − 1 . ) ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec multXk p k = match p with

[ ] −> [ ]
| ( c , e ) : : t −> ( c , e+k ) : : ( multXk t k ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t multMonome p ( c , e ) = multXk ( multConst p c ) e ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec multPolynomes p q = match p with

[ ] −> [ ]
| h : : t −> addPolynomes ( multMonome q h ) ( multPolynomes t q ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec expPolynome p = function

0 −> polynomeUnite
| n −> multPolynomes p ( expPolynome p ( n − 1 ) ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec polynomeOfExp = function

Const ( x ) −> [ ( x , 0 ) ]
| X −> [ ( 1 . , 1 ) ]
| Somme( l e f t , r i g h t ) −> addPolynomes ( polynomeOfExp l e f t ) ( polynomeOfExp r i g h t )
| P r o d u i t ( l e f t , r i g h t ) −> multPolynomes ( polynomeOfExp l e f t ) ( polynomeOfExp r i g h t )
| P u i s s ( l e f t , n ) −> expPolynome ( polynomeOfExp l e f t ) n ; ;

l e t k = polynomeOfExp ( P u i s s (Somme( Const ( 1 . ) , X) , 4));;

strOfPolyn o m e k ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec f l o a t E x p x = function
0 −> 1 .
| n −>
( i f n mod 2 = 0 then
1.
else
x
) ∗. floatExp (x ∗. x) (n / 2 ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec evalueMoche p x = match p with

[ ] −> 0 .
| ( c , e ) : : t −> c ∗ . ( f l o a t E x p x e ) +. evalueMoche t x ; ;

35
(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

(∗
un monome de d e g r e k s ’ e v a l u e en O( l o g k ) , q u i e s t l e temps n e c e s s a i r e pour
m e t t r e X a l a p u i s s a n c e k . On d e t e r m i n e l e temps que met un polynome
de d e g r e n pour s ’ e v a l u e r en c a l c u l a n t

u n = log 1 + log 2 + . . . + log n

q u i e s t l a somme d e s temps d ’ e x p o n e n t i a t i o n de chaqe monome . On a

u n <= l o g n + . . . + l o g n <= n l o g n

evalueMoche s ’ e x e c u t e en O( n l o g n ) .
∗)

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

(∗

( ( x − 2) x + 7) x −1

( ( ( 4 x ˆ4 + 2) x − 2) x − 1) x + 1

∗)

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec e v a l H o r n e r A c c p x a c c =
match p with
[ ] −> a c c
| ( c , e ) : : [ ] −> ( a c c +. c ) ∗ . ( f l o a t E x p x e )
| ( c , e1 ) : : t a i l −>
( match t a i l with
| ( , e2 ) : : −> e v a l H o r n e r A c c t a i l x ( ( a c c +. c ) ∗ . ( f l o a t E x p x ( e1 − e2 ) ) )
| −> f a i l w i t h ”Oups . . . ” ) ; ;

l e t evalHorner p x = evalHornerAcc p x 0 . ;;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

(∗

Supposons que l e s d e g r e s d e c r i v e l a s u i t e

n , n−1, n−2, . . . , 2 , 1 , 0

A l o r s chaque chacune d e s ( n + 1) i t e r a t i o n s s ’ e x e c u t e en temps

c o n s t a n t . Dans ce c a s l ’ a l g o r i t h m e s ’ e x e c u t e en O( n ) .

Dans l e c a s i l e x i s t e au moins un e n t i e r k < n t e l qu ’ i l n ’ y

a pas de monome de d e g r e k , a l o r s i l s u f f i t de c o n s i d e r e r dans
l e c a l c u l que l e polynome c o n t i e n t un monome 0 .Xˆk , ce q u i ne change
rien a la complexite qui a ete calculee .

∗)

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec d e r i v e P o l y n o m e = function
[ ] −> [ ]
| ( c o e f f , 0 ) : : [ ] −> [ ]
| ( c o e f f , exp ) : : t a i l −> ( c o e f f ∗ . ( f l o a t o f i n t exp ) , exp − 1 ) : : ( d e r i v e P o l y n o m e tail );;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec p r i m i t i v e P o l y n o m e = function
[ ] −> [ ]
| ( c o e f f , exp ) : : t a i l −> ( c o e f f / . ( f l o a t o f i n t exp +. 1 . ) , exp + 1 ) : : ( p r i m i t i v e P o l y n o m e tail );;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec i n t e g r e P o l y n o m e p a b =
l e t q = p r i m i t i v e P o l y n o m e p in
e v a l H o r n e r q b −. ( e v a l H o r n e r q a ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let rectangles p a b n =
l e t n F l o a t = f l o a t o f i n t n in
l e t rec aux p a b m =

36
 ( b −. a ) ∗ . ( e v a l H o r n e r p a ) / . n F l o a t +.
( i f (m = 1 ) then
0.
else
aux p ( ( b −. a ) / . n F l o a t +. a ) b (m−1)
) in
aux p a b n ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let trapezes p a b n =
l e t n F l o a t = f l o a t o f i n t n in
l e t dx = ( b −. a ) / . ( f l o a t o f i n t n ) in
l e t somme = r e f ( e v a l H o r n e r p a +. e v a l H o r n e r p b ) in
f o r i = 1 to n−1 do
l e t j = f l o a t o f i n t i in
somme := 2 . ∗ . ( e v a l H o r n e r p ( dx ∗ . j ) ) + . ! somme ;
done ;
( b −. a ) / . ( 2 . ∗ . n F l o a t ) ∗ . ! somme ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let facteurLagrange x = [ ( 1 . , 1 ) ; ( −. x , 0)];;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec l a g r a n g e f i p t s x i = match p t s with

[ ] −> polynomeUnite
| ( x , y ) : : t −> i f x = x i then
lagrange f i t x i
else
multPolynomes ( f a c t e u r L a g r a n g e x ) ( l a g r a n g e f i t x i ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

(∗
p i = y i ∗ f i ( x )/ f i ( x i )
∗)

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let l a g r a n g e p i pts ( x i , y i ) =
l e t f i = l a g r a n g e f i p t s x i in
multConst f i ( y i / . ( e v a l H o r n e r f i x i ));;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

(∗
p ( x ) = somme d e s p i ( x )
∗)

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let interpolationLagrange pts =

l e t rec a d d p i l =
( match l with
[ ] −> polynomeNul
| h : : t −> addPolynomes ( l a g r a n g e p i p t s h ) ( a d d p i t )
) in a d d p i p t s ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let interpolationVandermonde pts =

l e t n = L i s t . l e n g t h p t s in
l e t x = m a k e v e c t n 0 . in
l e t y = make matrix n 1 in
l e t rec i n i t T a b l m =
match l with
| [ ] −> ( )
| ( x i , y i ) : : t a i l −>
(
x . (m) <− x i ;
y . (m) . ( 0 ) <− y i ;
i n i t T a b t a i l (m+1)
) in
initTab pts 0;
l e t a = make matrix n n in
f i l l m a t r i x a ( function ( i , j ) −> i f ( j = 0 ) then 1 . e l s e a . ( i ) . ( j −1) ∗ . x . ( i ) ) ;
l e t x = s o l v e s y s t e m a y in
l e t rec c o e f f s k =
i f ( k >= 0 ) then

37
 ( x . ( k ) . ( 0 ) , k ) : : ( c o e f f s ( k −1))
else
[ ] in
c o e f f s (n −1);;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

(∗

u ( n+1) = u n − f ( x )/ f ’ ( x )

∗)

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec newton p x = function

0 −> x
| n −> newton p ( x −. ( e v a l H o r n e r p x ) / . ( e v a l H o r n e r ( d e r i v e P o l y n o m e p ) x ) ) ( n − 1 ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t d e g r e = function
| [ ] −> −1
| ( c , e ) : : −> i f ( e <> 0 ) then
e
else
i f ( e s t N u l c ) then
−1
else
0;;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec d i v i s i o n P o l y n o m e s a b =
i f ( d e g r e a < d e g r e b ) then
( polynomeNul , a )
else
(
match a , b with
( ca , ea ) : : , ( cb , eb ) : : −>
l e t q = [ ( ca / . cb , ea−eb ) ] in
l e t r = subPolynomes a ( multPolynomes b q ) in
l e t ( q r e c , r r e c ) = d i v i s i o n P o l y n o m e s r b in
( ( addPolynomes q q r e c ) , r r e c )
);;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec pgcd a b =
i f ( d e g r e b <= 0 ) then
a
else
l e t ( , r ) = d i v i s i o n P o l y n o m e s a b in
pgcd b r ; ;

l e t r = multPolynomes ( f a c t e u r L a g r a n g e ( − . 1 . ) ) ( f a c t e u r L a g r a n g e 4 . ) ; ;
strOfPolyn o m e r ; ;
l e t p = multPolynomes ( f a c t e u r L a g r a n g e 5 . ) ( multPolynomes r ( f a c t e u r L a g r a n g e 2.));;
l e t q = multPolynomes ( f a c t e u r L a g r a n g e 6 . ) ( multPolynomes r ( f a c t e u r L a g r a n g e 1.));;

strOfPolyn o m e ( pgcd p q ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec e u c l i d e E a b l a s t V =
i f ( d e g r e b <= 0 ) then
( a , polynomeNul , l a s t V )
else
l e t ( q , r ) = d i v i s i o n P o l y n o m e s a b in
l e t ( p , u , v)= e u c l i d e E b r l a s t V in
( d , v , subPolynomes u ( multPolynomes v q ) ) ; ;

strOfPolyn o m e ( e u c l i d e E p q polynomeNul ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t sturmNext n npUn =
l e t q , r = d i v i s i o n P o l y n o m e s n npUn in
multConst r ( − 1 . ) ; ;

let sturmSuite p =

38
 l e t rec sturmSuiteAux u0 u1 =
l e t u2 = sturmNext u0 u1 in
u2 : : (
i f ( d e g r e u2 <= 0 ) then
[]
else
sturmSuiteAux u1 u2
) in
l e t dp = multConst ( d e r i v e P o l y n o m e p ) ( − 1 . ) in
p : : dp : : ( sturmSuiteAux p dp ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec nbSignChange s x = match s with

[ ] −> 0
| h : : [ ] −> 0
| h1 : : h2 : : t −>
(
l e t h1x = e v a l H o r n e r h1 x in
l e t h2x = e v a l H o r n e r h2 x in
i f ( h1x < 0 . && h2x > 0 . ) or ( h1x > 0 . && h2x < 0 . ) then
1
else
0
) + ( nbSignChange ( h2 : : t ) x ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec map f = function [ ] −> [ ] | h : : t −> ( f h ) : : ( map f t ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec t r o u v e R a c i n e s s i n f sup e p s =
l e t s i n f = nbSignChange s i n f in
l e t s s u p = nbSignChange s sup in
i f ( s i n f = s s u p ) then
[]
else
l e t mid = ( i n f +. sup ) / . 2 . in
i f ( a b s F l o a t ( sup −. i n f ) < e p s ) then
[ mid ]
else
( t r o u v e R a c i n e s s i n f mid e p s )@( t r o u v e R a c i n e s s mid sup e p s ) ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

let majoreRacines p =
l e t maxFloat a b =
i f ( a < b ) then b e l s e a in
match p with
(a n , ) : : −> l e t rec maxCoeff l =
(
match l with
| (h , ) : : [ ] −> a b s F l o a t h
| (h , ) : : t −> maxFloat ( a b s F l o a t h ) ( maxCoeff t )
| −> f a i l w i t h ” oups ”
) in ( maxCoeff p ) / . ( a b s F l o a t a n ) +. 1 .
| −> f a i l w i t h ” oups ” ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t sturm p e p s =
l e t s = s t u r m S u i t e p in
l e t a = m a j o r e R a c i n e s p in
t r o u v e R a c i n e s s ( −. a ) a e p s ; ;

(∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗)

l e t rec monstronome n = match n with

0 −> polynomeUnite
| n−> multPolynomes ( expPolynome ( f a c t e u r L a g r a n g e ( f l o a t o f i n t n ) ) ( n mod 4 + 1 ) ) ( monstronome ( n − 1 ) ) ; ;

l e t rec gronome = function

0 −> [ ( − . 1 . , 0 ) ]
| n−> ( f l o a t o f i n t ( ( i f n mod 2 = 0 then (−n ) e l s e n ) / 2 ) , n ) : : ( gronome ( n − 1 ) ) ; ;

f o r i =1 to 8 do
let p = monstronome i in
print f l o a t ( integrePolynome p 0 . 5 . ) ;
print s t r i n g ” \n” ;
print f l o a t ( rectangles p 0. 5. 100000);

39
 p r i n t s t r i n g ” \n” ;
p r i n t f l o a t ( trapezes p 0. 5. 100000);
p r i n t s t r i n g ” \n” ;
p r i n t s t r i n g ( st r O f P o l y n o m e p ) ;
p r i n t s t r i n g ” \n” ;
p r i n t f l o a t ( majoreRacines p ) ;
p r i n t s t r i n g ” \n” ;
map ( function e −> p r i n t f l o a t e ; p r i n t s t r i n g ” ; ” ) ( sturm p 1 . e − 1 0 ) ;
p r i n t s t r i n g ” \n” ;
done ; ;

40