X Informatique MP 2009

Thème de l'épreuve Polynômes positifs
Principaux outils utilisés listes chaînées, fonctions récursives

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                       

Rapport du jury

(télécharger le PDF)
           

Énoncé obtenu par reconnaissance optique des caractères


MP

ÉCOLE POLYTECHNIQUE

FILIÈRE
OPTION INFORMATIQUE

CONCOURS D'ADMISSION 2009

COMPOSITION D'INFORMATIQUE
(Durée : 4 heures)
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête 
de la copie.

Ce polynôme est-il positif ?
Dans certains cas, la démonstration assistée par ordinateur demande de vérifier 
des inégalités
polynomiales de la forme :
x  [0, 1], x6 - 42x5 + 120x4 - 140x3 + 75x2 - 15x + 1  0
Ce problème étudie une technique basée sur les polynômes de Bernstein 
permettant de démontrer
ce style d'inégalités automatiquement.
Les parties I et II traitent de nombres en précision arbitraire, respectivement 
des entiers relatifs
et des nombres dyadiques. La partie III traite de listes que l'on peut 
manipuler par les deux bouts.
Enfin, la partie IV introduit les polynômes de Bernstein et traite d'un moyen 
de démontrer les
inégalités.
Les parties peuvent être traitées indépendamment. Mais attention, chaque partie 
utilise des
notations et des fonctions introduites dans les parties précédentes. L'énoncé 
utilise à plusieurs
reprises la formulation « on garantira l'invariant P sur le type  ». On entend 
par cela que les
fonctions que vous allez écrire peuvent supposer que la propriété P est vraie 
pour leurs arguments
de type  et qu'en contrepartie elles doivent produire des résultats de type  
vérifiant la propriété
P . Si la logique de la fonction conduit à identifier des arguments de type  « 
impossibles », le code
du candidat peut échouer en appelant la fonction (procédure en Pascal) echouer 
qui prend une
(courte) chaîne explicative en argument.
I. Grands entiers
Les nombres que nous allons manipuler nécessitent une précision qui dépasse 
celle des entiers
de la machine (types int en Caml et integer en Pascal). Nous allons donc 
commencer par définir
une arithmétique de précision arbitraire. On se donne pour cela une base de 
calcul, par exemple
base = 10000. La valeur de base importe peu et on supposera seulement qu'elle 
est paire, supérieure
ou égale à 2 et que son double n'excède pas le plus grand entier machine. Un 
entier naturel de
précision arbitraire est alors représenté par la liste de ses chiffres en base 
base, les chiffres les moins
significatifs étant en tête de liste. Ainsi la liste [1; 2; 3] représente 
l'entier 1 + 2 × base + 3 × base2 .
On définit le type nat suivant pour de tels entiers :
1

(* Caml *)
let base = ... ; ;
type nat == int list ; ;

{ Pascal }
const base : integer = ... ;
type nat = ^cellule ; cellule = record
valeur : integer ; suite : nat ; end ;

Dans la suite, on garantira l'invariant suivant sur le type nat :
­ tout élément de la liste est compris entre 0 et base - 1, au sens large ;
­ le dernier élément de la liste, lorsqu'il existe, n'est pas nul.
On notera que l'entier 0 est représenté par la liste vide.

Question 1 Définir une fonction cons_nat qui prend en argument un chiffre c (un 
entier machine,
0  c < base) et un grand entier n, et qui renvoie le grand entier c+base×n. La 
fonction cons_nat
peut aider à garantir l'invariant du type nat.
(* Caml *) cons_nat : int -> nat -> nat
{ Pascal } function cons_nat(c : integer ; n : nat) : nat

Question 2 Définir une fonction add_nat qui calcule la somme de deux grands 
entiers. Indication : on pourra commencer par écrire une fonction prenant 
également une retenue en argument et
appliquer l'algorithme traditionnel enseigné à l'école primaire.
(* Caml *) add_nat : nat -> nat -> nat
{ Pascal } function add_nat(n1 : nat ; n2 : nat) : nat

Question 3 Définir une fonction cmp_nat qui prend en arguments deux grands 
entiers n1 et n2 ,
et qui renvoie un entier machine valant, -1 si n1 < n2 , 1 si n1 > n2 , et 0 si 
n1 = n2 .
(* Caml *) cmp_nat : nat -> nat -> int
{ Pascal } function cmp_nat(n1 : nat ; n2 : nat) : integer

Question 4 Définir une fonction sous_nat qui prend en arguments deux grands 
entiers n1 et n2
et qui calcule la différence n1 - n2 , en supposant n1  n2 . Indication : comme 
pour l'addition, on
pourra commencer par écrire une fonction prenant également une retenue en 
argument.
(* Caml *) sous_nat : nat -> nat -> nat
{ Pascal } function sous_nat(n1 : nat ; n2 : nat) : nat

Question 5 Définir une fonction div2_nat qui prend en argument un grand entier 
n et qui calcule
le quotient et le reste de la division euclidienne de n par 2. Le quotient est 
un grand entier et le
reste un entier machine valant 0 ou 1. On rappelle que la constante base est 
paire.
(* Caml *) div2_nat : nat -> nat * int
{ Pascal } procedure div2_nat(n : nat ; var q : nat ; var r : integer)
2

À partir de ces grands entiers naturels, on va maintenant construire de grands 
entiers relatifs.
Pour cela, on introduit le type enregistrement z suivant, où le champ signe 
contient le signe de
l'entier relatif, à savoir 1 ou -1, et le champ nat sa valeur absolue.
(* Caml *) type z = { signe: int; nat: nat };;
{ Pascal } type z = record signe: integer; nat: nat; end;
On notera que 0 admet deux représentations, ce qui n'est pas gênant par la 
suite.
Question 6 Définir une fonction neg_z qui calcule la négation d'un grand entier 
relatif.
(* Caml *) neg_z : z -> z
{ Pascal } function neg_z(z : z) : z

Question 7 Définir une fonction add_z qui calcule la somme de deux grands 
entiers relatifs.
(* Caml *) add_z : z -> z -> z
{ Pascal } function add_z(z1 : z ; z2 ; z) : z

Question 8 Définir une fonction mul_puiss2_z qui prend en arguments un entier 
machine
p (p  0), un grand entier relatif z, et qui renvoie le grand entier relatif 2p 
z. On se contentera
d'une solution simple, sans viser particulièrement l'efficacité.
(* Caml *) mul_puiss2_z : int -> z -> z
{ Pascal } function mul_puiss2_z(p : integer ; z : z) : z

Question 9 Définir une fonction decomp_puiss2_z qui prend en argument un grand 
entier relatif
z non nul, et qui renvoie un grand entier relatif u impair et un entier machine 
p tels que z = 2p u.
Cette fonction calcule donc la plus grande puissance de 2 qui divise z et 
renvoie la décomposition
correspondante. Comme ci-dessus, on visera la simplicité et on supposera que z 
est tel que p est
bien représentable par un entier machine.
(* Caml *) decomp_puiss2_z : z -> z * int
{ Pascal } procedure decomp_puiss2_z(z : z ; var u : z ; var p : integer)
II. Nombres dyadiques
Un nombre dyadique est un nombre rationnel qui peut s'écrire sous la forme
a × 2b

avec a, b  Z.

On note D l'ensemble des nombres dyadiques. On définit le type dya suivant pour 
représenter les
nombres dyadiques :
3

(* Caml *)
type dya = { m : z ; e : int } ; ;

{ Pascal }
type dya = record m : z ; e : integer ;
end ;

Si d est une valeur du type dya, on l'interprète donc comme le nombre rationnel 
d.m × 2d.e , où d.m
est parfois appelé mantisse, et d.e exposant.
On garantira l'invariant suivant sur le type dya : la valeur du champ m est 
soit nulle, soit impaire.
On supposera par ailleurs que la capacité des entiers machines ne sera jamais 
dépassée dans le calcul
des exposants.

Question 10 Définir une fonction div2_dya qui divise un nombre dyadique par 2.
(* Caml *) div2_dya : dya -> dya
{ Pascal } function div2_dya(d : dya) : dya

Question 11 Définir une fonction add_dya qui calcule la somme de deux nombres 
dyadiques.
(* Caml *) add_dya : dya -> dya -> dya
{ Pascal } function add_dya(d1 : dya ; d2 ; dya) : dya

Question 12 Définir une fonction sous_dya qui calcule la différence de deux 
nombres dyadiques.
(* Caml *) sous_dya : dya -> dya -> dya
{ Pascal } function sous_dya(d1 : dya ; d2 ; dya) : dya
III. Listes à deux bouts
On considère maintenant des listes de nombres dyadiques. Si une telle liste 
contient les n éléments
x1 , x2 , . . . , xn , dans cet ordre, on la note hx1 ; x2 ; . . . ; xn i. Dans 
la partie IV, nous aurons besoin de
manipuler de telles listes aux deux extrémités, c'est-à-dire d'ajouter et de 
supprimer des éléments à
gauche comme à droite, et également de calculer efficacement l'image miroir 
d'une telle liste, c'està-dire la liste hxn ; . . . ; x2 ; x1 i. La notion 
usuelle de liste se prêtant mal à de telles opérations (seule
la manipulation de l'extrémité gauche de la liste est aisée), l'objectif de 
cette partie est de réaliser
une structure de données raisonnablement efficace pour représenter une telle « 
liste à deux bouts ».
Pour éviter les confusions, nous utiliserons dorénavant le terme de « LDB » 
pour désigner une liste à
deux bouts, et nous continuerons d'utiliser le terme « liste » pour désigner 
une liste usuelle (le type
list de Caml ou une liste chaînée traditionnelle de Pascal).
L'idée est d'utiliser non pas une liste mais deux pour représenter une LDB, la 
première liste
représentant la partie gauche de la LDB et la seconde liste sa partie droite. 
Ainsi l'ensemble des
deux listes g = [1; 2] et d = [5; 4; 3] représentera la LDB h1; 2; 3; 4; 5i. La 
liste g contient les premiers
éléments de la LDB, dans le bon ordre, et la tête de cette liste coïncide donc 
avec l'extrémité gauche
4

de la LDB ; symétriquement, la liste d contient les derniers éléments de la 
LDB, en ordre inverse,
et la tête de cette liste coïncide donc avec l'extrémité droite de la LDB.
On définit le type ldb suivant pour représenter les LDB :
(* Caml *)
type ldb = {
lg : int ; g : dya list ;
ld : int ; d : dya list } ; ;

{ Pascal }
type liste_dya = ^cell_ld ; cell_ld = record
dya : dya ; suite_ld : liste_dya ; end ;
type ldb = record
lg : integer ; g : liste_dya ;
ld : integer ; d : liste_dya ; end ;

On se donne une constante entière c  2 et on impose sur le type ldb les deux 
invariants suivants :
Le champ lg contient la longueur de la liste g, et le champ ld celle de la 
liste d.

(1)

lg  c × ld + 1 et ld  c × lg + 1

(2)

Toutes les questions de cette partie garantiront les invariants au sens précisé 
dans l'introduction du
problème, la question 16 étant un peu particulière.

Question 13 Définir une fonction ldb_est_vide qui détermine si une LDB est vide.
(* Caml *) ldb_est_vide : ldb -> bool
{ Pascal } function ldb_est_vide(l : ldb) : boolean

Question 14 Définir une fonction premier_g qui renvoie l'élément le plus à 
gauche d'une LDB,
i.e. telle que premier_g hx1 ; x2 ; . . . ; xn i = x1 . On supposera que la LDB 
contient au moins un
élément.
(* Caml *) premier_g : ldb -> dya
{ Pascal } function premier_g(l : ldb) : dya

Question 15 Définir une fonction inverse_ldb qui inverse l'ordre des éléments 
d'une LDB, i.e.
telle que inverse_ldb hx1 ; x2 ; . . . ; xn i = hxn ; . . . ; x2 ; x1 i.
(* Caml *) inverse_ldb : ldb -> ldb
{ Pascal } function inverse_ldb(l : ldb) : ldb

Question 16 Définir une fonction invariant_ldb qui vérifie si une LDB satisfait 
bien l'invariant
(2) et le rétablit si ce n'est pas le cas. Plus précisément, la fonction 
invariant_ldb renvoie son
argument inchangé lorsqu'il vérifie l'invariant et, dans le cas contraire, 
renvoie une LDB de même
contenu vérifiant l'invariant. Attention, dans ce dernier cas, on demande un 
coût de l'ordre de la
taille de la LDB. Indication : pour une LDB contenant  éléments, la répartition 
qui range les /2
premiers éléments dans la liste g satisfait (2). Enfin les candidats pourront 
utiliser, sans les définir,
5

une fonction concatener qui concatène deux listes, ainsi qu'une fonction 
inverser qui inverse une
liste.
concatener([x1 ; · · · ; xn ], [y1 ; · · · ; ym ]) = [x1 ; · · · ; xn ; y1 ; · 
· · ; ym ]
inverser([x1 ; x2 ; · · · ; xn ]) = [xn ; · · · ; x2 ; x1 ]
(* Caml *) invariant_ldb : ldb -> ldb
{ Pascal } function invariant_ldb(l : ldb) : ldb

Question 17 Définir une fonction ajoute_g qui ajoute un élément à gauche d'une 
LDB, i.e. telle
que ajoute_g x hx1 ; x2 ; . . . ; xn i = hx; x1 ; x2 ; . . . ; xn i.
(* Caml *) ajoute_g : dya -> ldb -> ldb
{ Pascal } function ajoute_g(d : dya ; l : ldb) : ldb

Question 18 Définir une fonction enleve_g qui supprime l'élément le plus à 
gauche dans une
LDB, i.e. telle que enleve_g hx1 ; x2 ; . . . ; xn i = hx2 ; . . . ; xn i. On 
supposera que la LDB contient au
moins un élément.
(* Caml *) enleve_g : ldb -> ldb
{ Pascal } function enleve_g(l : ldb) : ldb
On supposera avoir écrit les fonctions symétriques opérant sur l'extrémité 
droite de la LDB :
ajoute_d pour ajouter un élément à droite, premier_d pour obtenir l'élément le 
plus à droite, et
enleve_d pour supprimer l'élément le plus à droite.

Question 19 Dans cette question, on suppose c = 3. On considère une LDB de 
longueur N
obtenue en appliquant successivement N opérations ajoute_g à partir d'une LDB 
vide. Quel est le
coût moyen de chaque opération ajoute_g ? On supposera que le coût de 
l'opération invariant_ldb
est constant lorsque la LDB vérifie l'invariant (2) et proportionnel à la 
longueur de la LDB lorsque
celle-ci est réarrangée.
IV. Polynômes de Bernstein
On considère les polynômes
sives :

B0

 0
Bik

 k
Bi

Bik définis, pour i, k  Z, par l'ensemble suivant d'équations récur= 1
k-1
= (1 - X)Bik-1 + XBi-1

si 0  i  k

= 0 si i < 0 ou i > k

On note que Bik est non nul si et seulement si 0  i  k et que les Bik sont des 
polynômes à
coefficients entiers.

6

Étant donnée une séquence de k + 1 nombres dyadiques p = hd0 ; . . . ; dk i, on 
l'interprète comme
un polynôme à coefficients dyadiques, noté I(p), de la manière suivante :
def

I(hd0 ; . . . ; dk i) =

k
X

di Bik

i=0

Dans la suite de ce problème, on ne s'intéresse qu'à des polynômes qui 
s'écrivent sous cette forme.
En particulier, quand on écrira « le polynôme p » on signifiera implicitement 
que p est une LDB de
nombres dyadiques, de type ldb, interprétée comme le polynôme I(p). On 
introduit donc le type
poly suivant pour les polynômes, comme un synonyme pour le type ldb des listes 
à deux bouts de
nombres dyadiques :
(* Caml *) type poly == ldb;;
{ Pascal } type poly = ldb;
Pour un polynôme p = hd0 ; . . . ; dk i, on appelle k sa taille ; le polynôme 
vide a la taille -1 par
convention. On suppose avoir écrit deux fonctions add_poly et sous_poly 
calculant respectivement
la somme et la différence de deux polynômes de même taille, ainsi qu'une 
fonction div2_poly
multipliant un polynôme par la fraction 1/2.
Question 20 Soit p = hd0 ; . . . ; dk i un polynôme. Montrer que si, pour tout 
i, di est positif ou nul,
alors
x  [0, 1], I(p)(x)  0
Montrer que la réciproque est fausse avec p = h2; -1; 2i.
Pour un polynôme p de taille k  0, on définit le polynôme derive p de taille k 
- 1 par
def

derive p = sous_poly (enleve_g p) (enleve_d p)
Pour un polynôme p de taille k quelconque et c  D, on définit le polynôme 
integre c p de taille
k + 1 par
(
ajoute_g c ldb_vide
si p est vide
def
integre c p =
ajoute_g c (add_poly p (integre c (enleve_d p))) sinon
Où ldb_vide représente la LDB vide.
Enfin, pour un polynôme p de taille k quelconque, on définit les polynômes 
raffine_g p et
raffine_d p, de taille k, par
(
ldb_vide
si p est vide
def
raffine_g p =
integre (premier_g p) (div2_poly (raffine_g (derive p))) sinon
et
def

raffine_d p = inverse_ldb (raffine_g (inverse_ldb p))
On admet alors les résultats suivants : pour tout polynôme p, on a
x, I(raffine_g p)(x) = I(p)(x/2)

(3)

x, I(raffine_d p)(x) = I(p)(1/2 + x/2)

(4)

et
7

Question 21 Un calcul donne raffine_g h2; -1; 2i = h2; 1/2; 1/2i et raffine_d 
h2; -1; 2i =
h1/2; 1/2; 2i. Que peut-on en conclure ?

Question 22 Définir une fonction test_pos qui prend en argument un polynôme p 
et qui est
une procédure de semi-décision pour la propriété x  [0, 1], I(p)(x)  0. Une 
procédure de semidécision termine toujours ; si elle renvoie vrai, alors la 
propriété est vraie ; si elle renvoie faux, alors
on ne sait rien de la validité de la propriété. La procédure envisagée est du 
style « diviser pour
régner », et on fixera une limite maximale sur la profondeur de décomposition, 
au delà de laquelle
l'effort de preuve est abandonné. Il n'est pas démandé d'écrire le code des 
fonctions raffine_g et
raffine_d, que l'on pourra donc appeler sans les définir.
(* Caml *) test_pos : poly -> bool
{ Pascal } function test_pos(p : poly) : boolean

Question 23 Montrer que pour tout polynôme p et tout nombre dyadique c on a les 
égalités
suivantes :
raffine_g (c · p) = c · raffine_g p
raffine_d (c · p) = c · raffine_d p

Question 24 Montrer que la méthode ci-dessus est incomplète, c'est-à-dire qu'il 
existe un polynôme p tel que x  [0, 1], I(p)(x)  0, et tel que test_pos renvoie 
faux quelle que soit la profondeur de décomposition. Indication : considérer p 
= h1; -2; 4i, et admettre sans démonstration que
raffine_d (raffine_g p) = 1/16 p.

8

Extrait du corrigé obtenu par reconnaissance optique des caractères



X Informatique MP 2009 -- Corrigé
Ce corrigé est proposé par Vincent Danjean (Enseignant-chercheur en école 
d'ingénieur) ; il a été relu par Antoine Taveneaux (ENS Lyon) et Olivier 
Levillain (École
Polytechnique).

Cette épreuve propose d'étudier une technique basée sur les polynômes de 
Bernstein pour démontrer à l'aide d'un ordinateur que certains polynômes sont à 
valeurs
positives ou nulles sur un intervalle donné. Pour ce faire, l'épreuve est 
découpée en
4 parties qui construisent progressivement les objets informatiques nécessaires 
pour
traiter le problème.
· La première partie introduit deux structures pour manipuler dans un premier
temps des entiers naturels en précision arbitraire, puis dans un second temps
des entiers relatifs. Seules les opérations dont on aura besoin pour la suite 
sont
définies sur ces structures (la multiplication n'en fait pas partie, par 
exemple).
· La deuxième partie introduit une nouvelle famille de nombres (les nombres
dyadiques) qui ont la particularité d'être faciles à multiplier ou diviser par 
2.
· La troisième partie traite de listes à deux bouts permettant, contrairement 
aux
listes classiques, de faire des opérations d'insertion et de suppression 
efficacement au début et à la fin de la liste.
· Enfin, la dernière partie traite de la résolution effective du problème 
initial en
utilisant les structures définies précédemment.
On peut noter que, même si l'énoncé parle dans son introduction des polynômes
de Bernstein et donne ce titre à sa quatrième partie, il n'est nul part écrit 
explicitement ce que sont ces polynômes. On peut cependant se douter qu'il 
s'agit des
polynômes notés Bki dans l'énoncé et l'on pourra se référer à la page de 
wikipedia fr.wikipedia.org/wiki/Polynome_de_Bernstein pour plus d'informations à
ce sujet.
L'énoncé introduit plusieurs invariants. Il s'agit de propriétés particulières 
sur les
structures informatiques manipulées, propriétés que le programmeur s'oblige à 
respecter : les fonctions utilisant ces structures peuvent supposer ces 
propriétés vérifiées
en entrée et se doivent de les respecter en sortie. Parfois, un invariant peut 
être garanti par le système de types de Camllight lui-même et donc vérifié à la 
compilation
du code ; c'est par exemple le cas des types des arguments et du type de la 
valeur
de retour des fonctions. D'autres fois, l'invariant est un contrat 
supplémentaire qui
n'est pas vérifié par le système, ni même par le code. Par exemple, on peut 
avoir
une structure contenant une liste et un entier donnant la taille de cette 
liste. Il ne
faut pas hésiter à se servir de ces invariants pour répondre aux questions, 
mais il
faut également penser à toujours les respecter. Le sujet traitant de listes, la 
notion
de récursivité est également beaucoup employée.
La plupart des questions demandent d'écrire du code. Il y a quelques 
considérations de complexité, mais ce n'est pas le coeur de cette épreuve. Il 
n'y a également
rien sur les automates. Ce sujet est donc l'occasion de développer son aptitude 
à la
programmation en manipulant des structures de données complexes. Les questions
sont de difficulté constante, hormis la question 19 qui demande beaucoup de 
soin.

Indications
Partie I
1 Multiplier un nombre par la base de calcul, c'est décaler tous les chiffres 
de ce
nombre d'une position.
3 Comparer les chiffres les plus significatifs en premier.
6 Exploiter directement le champ signe.
7 Traiter différemment les cas où les signes sont identiques et où ils sont 
différents.
8 Multiplier par 2 un nombre, c'est ajouter ce nombre à lui-même.
9 Utiliser div2_nat tant que le reste est nul.
Partie II
10 Utiliser la structure même d'un nombre dyadique.
11 Ramener les deux nombres au même exposant. Attention à l'invariant pour le
résultat.
12 Soustraire, c'est ajouter l'opposé.
Partie III
13 Calculer la longueur de la LDB pour répondre.
14 Si la liste gauche est vide, l'invariant assure que la liste droite est très 
courte.
15 Exploiter la structure des LDB.
16 Lorsque l'invariant n'est pas vérifié, calculer la liste complète des 
éléments de
la LDB puis couper cette liste comme proposé dans l'énoncé.
17 Se servir de la fonction invariant_ldb pour normaliser le résultat.
18 Utiliser les indications 14 et 17.
19 Montrer que la LDB est
 réorganisée par la fonction invariant_ldb lorsqu'il y a
exactement 2 × 2i - 1 éléments dans la LDB.
Partie IV
20 Montrer tout d'abord la propriété par récurrence pour tous les polynômes Bki 
.
21 Utiliser les propriétés (3) et (4) de l'énoncé en remarquant que, quand x 
parcourt
le segment [ 0 ; 1 ], x/2 parcourt [ 0 ; 1/2 ] et 1/2 + x/2 parcourt [ 1/2 ; 1 
].
22 Appliquer récursivement la technique de la question précédente si les 
coefficients
de la LDB ne sont pas tous positifs ou nuls.
23 Démontrer la propriété demandée pour toutes les fonctions utilisées 
récursivement
dans la définition de raffine_g et raffine_d.
24 Remarquer grâce à l'indication du sujet que l'arbre d'appels récursifs de 
test_pos
a une branche où les coefficients de la LDB ne seront jamais tous positifs ou 
nuls.

I. Grands entiers
1 Il faut distinguer le cas où c et n représentent tous les deux zéro, 
c'est-à-dire
lorsque c = 0 et n = []. Dans ce cas, l'invariant nécessite de renvoyer la 
liste vide.
let (cons_nat : int -> nat -> nat) = fun c n ->
if c < 0 || c >= base then
echouer "constante invalide" ;
match (c,n) with
0,[] -> []
| _ -> c::n
;;
Cette fonction a pour type :
cons_nat : int -> nat -> nat
Le type de la fonction cons_nat est forcé. Ce n'est pas une obligation
mais cela permet de restreindre le typage que Camllight aurait inféré. En
l'absence de typage explicite, le type serait
cons_nat : int -> int list -> int list
Un meilleur typage permet une meilleure vérification du code lors de la 
compilation. C'est toujours une bonne chose.
La fonction echouer peut être définie facilement grâce au mécanisme des
exceptions de Camllight. On peut par exemple la définir ainsi :
let echouer s = failwith s;;
2 La fonction add_nat est écrite à l'aide de add_nat_ret, fonction auxiliaire 
récursive qui prend une retenue en paramètre supplémentaire. Plusieurs cas sont 
à
considérer selon que les grands entiers sont nuls ou pas. Pour éviter d'écrire 
plusieurs fois le test vérifiant si une retenue doit être générée ou pas, une 
autre fonction
auxiliaire add_cons_nat est définie et utilisée.
let (add_nat : nat -> nat -> nat) = fun a b ->
let rec add_nat_ret a b retenue =
match a, b, retenue with
[]
, _
, 0 -> b
| _
, []
, 0 -> a
| []
, []
, _ -> cons_nat retenue []
| []
, b1::bn, _ -> add_cons_nat (b1+retenue) [] bn
| a1::an, []
, _ -> add_cons_nat (a1+retenue) an []
| a1::an, b1::bn, _ -> add_cons_nat (a1+b1+retenue) an bn
and add_cons_nat c a b =
if c nat -> nat
Les deux premiers cas de add_nat_ret pourraient ne pas être écrits sans
que cela ne modifie la correction de cette fonction. Leur présence permet
cependant d'avoir une complexité linéaire en la taille du plus petit des deux
grands entiers plutôt qu'en la taille du plus grand des deux.
3 Comparons récursivement les deux nombres en faisant attention au fait qu'il 
faut
comparer en priorité les chiffres les plus significatifs (ceux en fin de liste).
let rec (cmp_nat : nat -> nat -> int) = fun a b ->
match a, b with
[], [] -> 0
| _ , [] -> 1
| [], _ -> -1
| a1::an, b1::bn ->
let cmp=cmp_nat an bn in
if (cmp != 0) then
cmp
else if (a1 < b1) then
-1
else if (a1 > b1) then
1
else
0
;;
Cette fonction a pour type :
cmp_nat : nat -> nat -> int
4 Écrivons la fonction sous_nat à l'aide de sous_nat_ret, fonction auxiliaire
récursive basée sur le même modèle que celle de la question 2. On appelle 
echouer
quand on se rend compte qu'on essaie de soustraire quelque chose (non nul) de 
zéro.
let (sous_nat : nat -> nat -> nat) = fun a b ->
let rec sous_nat_ret a b retenue =
match a, b, retenue with
[]
, []
, 0 -> []
| []
, _
, _ -> echouer "résultat négatif"
| _
, []
, 0 -> a
| a1::an, []
, _ -> sous_cons_nat (a1-retenue) an []
| a1::an, b1::bn, _ -> sous_cons_nat (a1-b1-retenue) an bn
and sous_cons_nat c a b =
if (c<0) then
cons_nat (c+base) (sous_nat_ret a b 1)
else
cons_nat c (sous_nat_ret a b 0)
in
sous_nat_ret a b 0
;;