X Informatique MP 2008

MP

ÉCOLE POLYTECHNIQUE

FILIÈRE
OPTION INFORMATIQUE

CONCOURS D'ADMISSION 2008

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.

Structure de corde
La majorité des langages de programmation fournissent une notion primitive de 
chaînes de caractères. Si ces chaînes s'avèrent adaptées à la manipulation de 
mots ou de textes relativement
courts, elles deviennent généralement inutilisables sur de très grands textes. 
L'une des raisons de
cette inefficacité est la duplication d'un trop grand nombre de caractères lors 
des opérations de
concaténation ou d'extraction d'une sous-chaîne. Or il existe des domaines où 
la manipulation efficace de grandes chaînes de caractères est essentielle 
(représentation du génôme en bio-informatique,
éditeurs de texte, etc.). Ce problème aborde une alternative à la notion 
usuelle de chaîne de caractères connue sous le nom de corde. Une corde est tout 
simplement un arbre binaire, dont les feuilles
sont des chaînes de caractères usuelles et dont les noeuds internes 
représentent des concaténations.
Ainsi la corde

représente le mot GATTACCATAGATTAC, obtenu par concaténation des cinq mots 
GATTAC, CAT, AG,
ATT et AC. L'intérêt des cordes est d'offrir une concaténation immédiate et un 
partage possible de
caractères entre plusieurs chaînes, au prix d'un accès aux caractères un peu 
plus coûteux.
La partie I traite de fonctions préliminaires sur les mots. La partie II 
définit les principales
opérations sur les cordes. Enfin, les parties III et IV étudient le problème de 
l'équilibrage des
cordes, selon deux algorithmes différents dont le second, l'algorithme de 
Garsia-Wachs, est optimal.
Les parties peuvent être traitées indépendamment. La partie IV utilise les 
notations de la
partie III.

Partie I.

Préliminaires sur les mots

On considère les mots dans  construits sur un alphabet . Le mot x = a0 a1 · · · 
an-1 de longueur n est représenté dans ce problème par la liste des entiers 
codant ses caractères a0 , a1 , . . .
an-1 . Ainsi le mot ATT est représenté par une liste h65, 84, 84i. Pour ne pas 
dépendre du codage des
caractères, on identifie les caractères et leurs codes. Le type des mots est 
défini par :
1

(* Caml *)
type mot == int list ; ;

{ Pascal }
type mot = ^cellule ; cellule = record
lettre : integer ; suite : mot ; end ;

En Pascal la liste vide est nil et on pourra utiliser la fonction suivante pour 
construire des mots :
function nouveauMot(a:integer; x:mot) : mot;
var r : mot;
begin new(r); r^.lettre := a; r^.suite := x; nouveauMot := r; end;
Question 1 Écrire la fonction longueurMot qui calcule la longueur d'un mot.
(* Caml *) longueurMot : mot -> int
{ Pascal } function longueurMot(x : mot) : integer

Question 2 Écrire la fonction iemeCar qui prend en arguments un entier i et un 
mot x =
a0 a1 . . . an-1 , et qui renvoie le caractère ai . On supposera 0  i < n.
(* Caml *) iemeCar : int -> mot -> int
{ Pascal } function iemeCar(i : integer ; x : mot) : integer

Question 3 Écrire la fonction prefixe qui prend en arguments un entier k et un 
mot x =
a0 a1 . . . an-1 , et qui renvoie le mot a0 a1 . . . ak-1 c'est-à-dire le mot 
constitué des k premiers caractères de x. On supposera 0  k  n.
(* Caml *) prefixe : int -> mot -> mot
{ Pascal } function prefixe(k : integer ; x : mot) : mot

Question 4 Écrire la fonction suffixe qui prend en arguments un entier k et un 
mot x =
a0 a1 . . . an-1 , et qui renvoie le mot ak ak+1 . . . an-1 c'est-à-dire le mot 
obtenu en supprimant les k
premiers caractères de x. On supposera 0  k  n.
(* Caml *) suffixe : int -> mot -> mot
{ Pascal } function suffixe(k : integer ; x : mot) : mot

Partie II.

Opérations sur les cordes

Comme expliqué dans l'introduction, une corde est un arbre binaire dont les 
feuilles sont des
mots. Plus précisément, une corde est soit vide, soit constituée d'un unique 
mot (une feuille), soit
un noeud constitué de deux cordes et représentant leur concaténation. Pour des 
raisons d'efficacité,
on conserve dans les feuilles aussi bien que dans les noeuds la longueur de la 
corde correspondante.
On définit donc le type corde suivant :
(* Caml *)
type corde =
| Vide
| Feuille of int*mot
| Noeud of int*corde*corde ; ;

{ Pascal }
type corde = ^arbre ; nature = (Feuille, Noeud) ;
arbre = record case indicateur : nature of
Feuille : (n :integer ; x :mot) ;
Noeud : (n :integer ; g, d :corde) ; end ;
2

En Pascal la corde vide est représentée par nil.
Dans la suite, on garantira l'invariant suivant sur les cordes :
­ dans une corde de la forme Feuille(n, x), on a n = longueurMot(x) et n > 0 ;
­ dans une corde de la forme Noeud(n, c1 , c2 ), on a c1 6= Vide, c2 6= Vide et 
n est la longueur
totale de la corde, c'est-à-dire la somme des longueurs de c1 et c2 .
On notera en particulier que la corde de longueur 0 est nécessairement 
représentée par Vide.
Question 5 Écrire la fonction longueur qui renvoie la longueur d'une corde.
(* Caml *) longueur : corde -> int
{ Pascal } function longueur(c : corde) : integer
Question 6 Écrire la fonction nouvelleCorde qui construit une corde à partir 
d'un mot.
(* Caml *) nouvelleCorde : mot -> corde
{ Pascal } function nouvelleCorde(m : mot) : corde
Question 7 Écrire la fonction concat qui construit la concaténation de deux 
cordes.
(* Caml *) concat : corde -> corde -> corde
{ Pascal } function concat(c1 : corde ; c2 : corde) : corde
Question 8 Écrire la fonction caractere qui prend en arguments un entier i et 
une corde c
représentant le mot a0 a1 · · · an-1 , et qui renvoie le caractère ai . On 
supposera 0  i < n.
(* Caml *) caractere : int -> corde -> int
{ Pascal } function caractere(i : integer ; c : corde) : integer
Question 9 Écrire la fonction sousCorde qui prend en arguments un entier i, un 
entier m
et une corde c représentant le mot a0 a1 · · · an-1 , et qui renvoie une corde 
représentant le mot
ai ai+1 · · · ai+m-1 c'est-à-dire la sous-corde de c débutant au caractère i et 
de longueur m. On supposera 0  i < i + m  n.
(* Caml *) sousCorde : int -> int -> corde -> corde
{ Pascal } function sousCorde(i : integer ; m : integer ; c : corde) : corde
On s'attachera à réutiliser dans la corde résultat autant de sous-arbres de la 
corde c que possible.

Partie III.

Équilibrage

Le hasard des concaténations peut amener une corde à se retrouver 
déséquilibrée, c'est-à-dire à
avoir certaines de ses feuilles très éloignées de la racine et donc d'accès 
plus coûteux. Le but de
cette partie est d'étudier une stratégie de rééquilibrage a posteriori.
Considérons une corde c composée de k + 1 feuilles, et donc de k noeuds 
internes. Notons ces
k + 1 feuilles x0 , x1 , . . . xk lorsqu'on les considère de la gauche vers la 
droite, si bien que c représente
3

le mot x0 x1 . . . xk . La profondeur de la feuille xi dans c est notée prof(xi 
) et est définie comme la
distance de xi à la racine de c. Voici un exemple de corde pour k = 5 où la 
profondeur de chaque
feuille est indiquée entre parenthèses :

(1)

(3)

(3)

(4)

(3)

(4)

Le coût de l'accès à un caractère de la feuille xi est défini comme la 
profondeur de cette feuille
dans c, soit prof(xi ) (on ne considère donc pas le coût de l'accès dans le mot 
xi lui-même). Le coût
total d'une corde est alors défini comme la somme des coûts d'accès à tous ses 
caractères, et vaut
donc
Coût(c) =

k
X

longueurMot(xi ) × prof(xi )

i=0

Un rééquilibrage consiste à construire une corde différente, dont les feuilles 
sont x0 , x1 . . . xk dans
le même ordre (le mot représenté ne doit pas changer) et dont le coût est, 
éventuellement, meilleur.
L'algorithme proposé est le suivant.
On considère un tableau file de cordes dans lequel les feuilles de c vont être 
successivement
insérées dans le sens des indices croissants. Les cases d'indices 0 et 1 ne 
sont pas utilisées. La case
d'indice i contient soit la corde vide (Vide), soit une corde de hauteur 
inférieure ou égale à i - 2 et
dont la longueur est comprise dans l'intervalle [Fi , Fi+1 [ où Fi désigne le 
i-ème terme de la suite de
Fibonacci. La hauteur d'une corde c, notée hauteur(c), est la profondeur 
maximale de ses feuilles,
c'est-à-dire :
hauteur(Vide) = 0
hauteur(Feuille(n, x)) = 0
hauteur(Noeud(n, c1 , c2 )) = 1 + max{hauteur(c1 ), hauteur(c2 )}
Pour équilibrer la corde c dont les feuilles sont les mots x0 , x1 , . . . xk , 
dans cet ordre, on procède
ainsi :
1. On insère successivement chaque feuille xj dans le tableau file à partir de 
la case 2. L'insertion
d'une feuille, et plus généralement d'une corde, à partir de la case d'indice i 
se fait ainsi :
(a) La corde à insérer est concaténée à droite de la corde se trouvant dans la 
case i ; soit c
le résultat. Si la longueur de c est comprise dans l'intervalle [Fi , Fi+1 [, 
on affecte c à la
case i et on a terminé l'insertion de cette corde.
(b) Sinon, on affecte Vide à la case i et on retourne à l'étape (a) pour 
effectuer l'insertion
de c à partir de la case d'indice i + 1.
On garantit l'invariant suivant : après l'insertion de la feuille xj , la 
concaténation successive
de toutes les cordes contenues dans les cases de file, considérées dans le sens 
des indices
décroissants, est égale à une corde représentant le mot x0 x1 . . . xj .
2. Le résultat est alors la corde résultant de la concaténation successive de 
toutes les cordes de
file, considérées dans le sens des indices décroissants.
4

Question 10 Calculer le résultat de cet algorithme sur la corde de l'exemple 
précédent.
Question 11 On rappelle que la suite de Fibonacci (Fn ) est définie par

F0 = 0,
F1 = 1,

 F
n+2 = Fn+1 + Fn

pour n  0.

Afin d'éviter tout débordement arithmétique en calculant Fn , on limite la 
taille de file à 44 cases
indexées de 0 à 43 (les cases 0 et 1 n'étant pas utilisées). On introduit la 
constante tailleMax = 44
et on calcule les valeurs de Fn pour 0  n  tailleMax une fois pour toutes dans 
un tableau fib
ainsi déclaré :
{ Pascal }
(* Caml *)
let tailleMax = 44 ; ;
const tailleMax = 44 ;
let fib = make_vect (tailleMax+1) 0 ; ; var fib :array[0..tailleMax] of integer 
;
Écrire la fonction initialiserFib qui initialise le tableau fib.
Question 12 Le tableau file utilisé par l'algorithme est déclaré comme un 
tableau global contenant des cordes :
{ Pascal }
(* Caml *)
let file = make_vect tailleMax Vide ; ; var file :array[0..tailleMax-1] of 
corde ;
Écrire la fonction inserer qui prend en arguments une corde c et un entier i, 
tels que
2  i < tailleMax, hauteur(c)  i - 2 et longueur(c)  Fi , et réalise l'insertion 
de c dans
le tableau file à partir de la case d'indice i.
(* Caml *) inserer : corde -> int -> unit
{ Pascal } procedure inserer(c : corde ; i : integer)
Question 13 Montrer que l'invariant hauteur(ci )  i - 2 et longueur(ci )  Fi 
est préservé par
cette fonction pour toutes les valeurs ci non vides des cases du tableau file 
(2  i < tailleMax).
Question 14 Écrire la fonction equilibrer qui réalise l'équilibrage d'une corde 
par l'algorithme
ci-dessus.
(* Caml *) equilibrer : corde -> corde
{ Pascal } function equilibrer(c : corde) : corde
Question 15 Soit c une corde non vide renvoyée par la fonction equilibrer 
ci-dessus. Soit n sa
longueur et h sa hauteur. Montrer que l'on a
n  Fh+1
En déduire qu'il existe une constante K (indépendante de n) telle que

Coût(c)  n (log (n) + K)

où  est le nombre d'or (1 + 5)/2 et log désigne le logarithme à base . On 
admettra que l'on a

Fi+1  i / 5 pour tout i  0.
5

Partie IV.

Équilibrage optimal

Bien que satisfaisant en pratique, l'équilibrage étudié dans la partie 
précédente n'est pas optimal.
Le but de cette partie est d'étudier une stratégie optimale de rééquilibrage 
(algorithme de GarsiaWachs). Les notations sont celles de la partie III. 
L'algorithme proposé procède en deux temps :
il commence par construire une corde de coût minimal, ayant les mêmes feuilles 
que c mais pas
nécessairement dans le même ordre ; puis, dans un deuxième temps, il transforme 
cette corde en une
autre de même coût où les feuilles sont maintenant dans le même ordre que dans 
c.
La première partie de l'algorithme opère sur une liste de cordes q = hq0 , q1 , 
. . . qm i et procède
de la manière suivante :
1. Initialement, la liste q est la liste hx0 , x1 , . . . xk i des k + 1 
feuilles de c.
2. Tant que la liste q contient au moins deux éléments, on effectue l'opération 
suivante :
(a) Déterminer le plus petit indice i tel que
longueur(qi-1 )  longueur(qi+1 )
le cas échéant, et poser i = m sinon.
(b) Ôter qi-1 et qi de la liste q et former leur concaténation ; soit c la 
corde obtenue.
(c) Déterminer le plus grand indice j < i tel que
longueur(qj-1 )  longueur(c )
le cas échéant, et poser j = 0 sinon.
(d) Insérer c dans la liste q juste après qj-1 (et donc au début de la liste q 
si j = 0).
3. Le résultat est l'unique élément restant dans la liste q.
Il est clair que le résultat de cet algorithme est une corde ayant les mêmes 
feuilles que c mais que
ces feuilles ne sont pas nécessairement dans le bon ordre. On admettra le 
résultat suivant : l'arbre
obtenu est de coût minimal.
Question 16 Pour simplifier le codage, on suppose que le nombre k de feuilles 
est inférieur à une
certaine valeur (ici maxf = 1000) et que la liste q est représentée dans un 
tableau global q :
(* Caml *)
let maxf = 1000 ; ;
let q = make_vect maxf Vide ; ;

{ Pascal }
const maxf :integer = 1000 ;
var q :array[0..maxf-1] of corde ;

Écrire la fonction initialiserQ qui prend en argument une corde c, remplit les 
k + 1 premiers
éléments de q avec les feuilles x0 , . . . , xk de c (c'est-à-dire des cordes 
de la forme Feuille), et
renvoie la valeur de k. On supposera c 6= Vide.
(* Caml *) initialiserQ : corde -> int
{ Pascal } function initialiserQ(c : corde) : integer
On admettra avoir effectué le reste de l'algorithme ci-dessus et avoir donc 
écrit une fonction
phase1 qui prend en argument une corde c et renvoie la corde obtenue par 
l'algorithme ci-dessus.
(* Caml *) phase1 : corde -> corde
{ Pascal } function phase1(c : corde) : corde
6

La deuxième étape de l'algorithme procède ainsi. Soit c1 la corde obtenue à 
l'issue de la première
étape de l'algorithme. Chaque feuille xi de c se trouve dans c1 à une certaine 
profondeur ; notons
pi cette profondeur. On admet la propriété suivante : il existe une corde c2 
dont les feuilles sont
exactement x0 , x1 , . . . xk dans cet ordre et où la profondeur de chaque xi 
est exactement pi . On peut
alors construire c2 en ne connaissant que les pi , et c2 est dès lors un 
rééquilibrage optimal de c.
Question 17 Les profondeurs pi seront stockées dans un tableau global prof :
(* Caml *)
let prof = make_vect maxf 0 ; ;

{ Pascal }
var prof :array[0..maxf-1] of
integer ;

Écrire la fonction initialiserProf qui prend en argument les cordes c et c1 et 
range dans le
tableau prof, à l'indice i, la profondeur de la feuille xi (de c) dans c1 pour 
0  i  k. On pourra
avantageusement réutiliser le tableau q et la fonction initialiserQ.
(* Caml *) initialiserProf : corde -> corde -> unit
{ Pascal } procedure initialiserProf(c : corde ; c1 : corde)
Indication : on admettra que, pour comparer les feuilles de c et c1 , on peut 
utiliser l'égalité fournie
par le langage, i.e. le symbole =.
Question 18 Écrire la fonction reconstruire qui construit c2 à partir de la 
seule donnée des
tableaux q et prof. Attention : pour des profondeurs pi quelconques, il 
n'existe pas nécessairement
de corde où chaque xi a la profondeur pi . On demande ici un algorithme qui 
fonctionne uniquement
sous l'hypothèse qu'une telle corde existe (ce qui est le cas ici).
(* Caml *) reconstruire : unit -> corde
{ Pascal } function reconstruire : corde

Question 19

Combiner les fonctions ci-dessus pour obtenir une fonction de rééquilibrage 
optimal.

(* Caml *) equilibrerOpt : corde -> corde
{ Pascal } function equilibrerOpt(c : corde) : corde

7

X Informatique MP 2008 -- Corrigé
Ce corrigé est proposé par Vincent Danjean (Enseignant-chercheur en école 
d'ingénieur) ; il a été relu par Marc Mezzarobba (ENS Ulm) et Vincent Puyhaubert
(Professeur en CPGE).

Ce sujet traite de la manipulation de très grandes chaînes que l'on stocke sous
forme d'arbres. Dans ces arbres (appelés cordes), un noeud représente la 
concaténation
des chaînes stockées dans les sous-arbres. Ce genre de représentation est 
essentiel
lorsque le coût de recopie des chaînes lors de concaténations « classiques » 
est trop
important. C'est le cas pour la manipulation du génome en bio-informatique ou 
encore
pour les éditeurs de texte qui veulent stocker un document entier.
Le sujet, de difficulté progressive, est découpé en 4 parties.
· La première partie traite de la manipulation des chaînes de longueur 
habituelle,
représentées ici sous forme de listes (au lieu du traditionnel tableau de 
caractères). Les fonctions demandées dans cette partie permettent d'effectuer 
des
opérations classiques : recherche d'un caractère, extraction d'un prefixe et 
d'un
suffixe.
· La deuxième partie introduit quelques opérations relatives aux cordes, pour 
les
construire ou en extraire des parties.
Les deux parties suivantes ont pour but de déterminer une méthode de 
rééquilibrage des cordes. Il s'agit d'une opération destinée à minimiser la 
hauteur de l'arbre
afin de diminuer le coût d'accès à ses éléments. La difficulté est qu'il faut 
préserver
l'ordre dans lequel apparaissent les feuilles lors d'un parcours en profondeur.
· La troisième partie présente une première méthode de rééquilibrage. On 
commence par traiter un exemple à la main, avant de produire le code et de 
montrer
certains résultats sur la hauteur finale de l'arbre.
· La quatrième partie aborde une seconde méthode, qui est optimale. Il n'y a
que du code à produire dans cette dernière partie puisque tous les résultats
théoriques sont admis.
La plupart des questions demandent d'écrire des fonctions bien spécifiées par
l'énoncé ou dont l'algorithme est décrit de manière détaillée. Les codes sont 
généralement simples mais ils font beaucoup intervenir la récursivité, car le 
sujet fait
travailler sur des listes puis sur des arbres. Très peu de questions portent 
sur des
analyses d'algorithmes ou de leur complexité.
Le rapport du jury souligne que les réponses courtes ont souvent été plus justes
et mieux justifiées.

Indications
2 Faire une fonction récursive en remarquant que pour i > 0, la i-ième lettre
d'une liste est la (i - 1)-ième de sa queue.
3 Construire le préfixe récursivement. On peut remarquer que le préfixe de 
longueur k > 0 d'une liste est égal à la tête de cette liste suivie du préfixe 
de
longueur k - 1 de sa queue.
4 Remarquer que le suffixe ak , . . . , an d'une liste a0 , . . . , an 
s'obtient pour k > 0
par un appel récursif simple sur un entier bien choisi et la queue de la liste.
5 Exploiter les champs disponibles dans le type corde.
6 Penser à utiliser les fonctions de la partie I pour calculer la longueur puis
utiliser le constructeur adapté.
7 Traiter correctement le cas de la corde vide en argument.
8 Parcourir récursivement la corde et bien penser à mettre à jour la position
recherchée quand on descend dans une sous-corde droite.
9 Reconstruire une nouvelle corde en effectuant un parcours en profondeur et en
ne gardant que les parties intéressantes.
11 Compléter le tableau avec une boucle en utilisant pour le calcul d'une case 
les
valeurs des deux cases précédentes.
12 Suivre la partie 1 de l'algorithme décrit au début de la partie III.
13 Bien vérifier les hypothèses faites sur les arguments de la fonction inserer
lors des appels récursifs.
14 Implémenter les deux étapes de l'algorithme décrit au début de la partie III.
Les feuilles xj de la corde initiale pourront être insérées par une fonction
annexe récursive.
15 Remarquer que dans l'étape 2 de l'algorithme, pour tout i, la corde obtenue
après concaténation de l'élément ci d'indice i du tableau file est de hauteur
inférieure ou égale à i - 1. Montrer ensuite que Coût(c) 6 hn.
16 Faire un parcours récursif de la corde en maintenant à jour l'indice de la
prochaine feuille à stocker dans le tableau q.
17 Effectuer un parcours en profondeur de c1 : à chaque feuille trouvée, noter 
la
profondeur et chercher de quelle feuille il s'agit à l'aide du tableau q. Mettre
alors à jour le tableau prof.
18 La nouvelle corde doit être construite de manière récursive par un nouveau
parcours en profondeur. Utiliser comme argument du programme la profondeur 
actuelle dans l'arbre en construction p et l'indice de la nouvelle feuille
à insérer i. On distinguera plusieurs cas suivant les valeurs respectives de p
et prof.(i).

I. Préliminaires sur les mots
1 Un mot étant représenté sous la forme d'une liste, la longueur d'un mot est la
longueur de la liste.
let rec (longueurMot : mot -> int ) = function
[] -> 0
| _::t -> 1 + longueurMot t;;
Cette fonction a pour type :
longueurMot : mot -> int

Le type de la fonction longueurMot est forcé ici. Ce n'est pas une obligation 
mais cela permet de restreindre le typage que camllight aurait inféré.
En l'absence de typage explicite, il serait en effet
longueurMot : 'a list -> int
Un meilleur typage permet des vérifications du code lors de la compilation.
C'est toujours une bonne chose.
On pourrait penser ne contraindre que le type de l'argument :
let rec longueurMot (m:mot) =
match m with
[] -> 0
| _::(t:mot) -> 1+longueurMot t;;
Mais, contrairement à OCaml, camllight souffre de quelques bugs pour
le typage forcé. Ainsi, si l'on ne force pas aussi le type de la variable t
(comme cela est fait dans le code ci-dessus), camllight renverrait comme
type longueurMot : int list -> int, ce qui est équivalent mais moins joli :
il est mieux de faire afficher l'alias que l'on a spécialement créé pour le 
type.
2 Recherchons par une récursion terminale le i-ième élément de la liste.
let rec
match
0
| _

(iemeCar : int -> mot -> int) = fun i m ->
i with
-> hd m
-> iemeCar (i-1) (tl m);;

Cette fonction a pour type :
iemeCar : int -> mot -> int

Même remarque que précédemment : le typage forcé de (tl m) n'est là
que pour contourner le bug de camllight.
L'énoncé précise que l'on suppose que l'entier i a une valeur correcte
(0 6 i < n). Si ce n'est pas le cas, l'implémentation donnée déclenchera une
exception lors de l'exécution de tl m ou de hd m (si i est trop grand), ou
alors elle partira dans une récursion infinie (si i est négatif).

3 Construisons récursivement une liste constituée des k premiers éléments de la
liste de départ.
let rec (prefixe : int -> mot -> mot) = fun k m ->
if k <= 0
then []
else (hd m)::(prefixe (k-1) (tl m));;
Cette fonction a pour type :
prefixe : int -> mot -> mot
On peut aussi utiliser une récursion terminale pour plus d'efficacité (le 
compilateur évite alors de gérer une pile d'appels de fonction). Il faut alors 
utiliser
un paramètre supplémentaire (dans une fonction auxiliaire) qui stocke (en
ordre inverse) le début du mot.
let (prefixe : int -> mot -> mot) = fun k m ->
let rec prefixe_rec k m accu =
if k <= 0
then rev accu
else prefixe_rec (k-1) (tl m) ((hd m)::accu)
in prefixe_rec k m [];;

4 Il suffit de renvoyer la fin de la liste après avoir éliminé les k premiers 
éléments.
Comme on souhaite obtenir la fin de la liste de départ, il n'y a pas besoin d'en
construire une nouvelle.
let rec (suffixe : int -> mot -> mot) = fun k m ->
if k = 0
then m
else suffixe (k-1) (tl m);;
Cette fonction a pour type :
suffixe : int -> mot -> mot

II. Opérations sur les cordes
L'énoncé impose le type Caml suivant :
type corde =
| Vide
| Feuille of int*mot
| Noeud of int*corde*corde;;
Il précise ensuite que les sous-cordes d'un Noeud ne peuvent pas être Vide.
Le rapport du jury souligne l'importance dans cette partie de toujours
respecter cette propriété.
On peut remarquer que cette propriété aurait pu être directement intégrée dans 
les types utilisés, par exemple en écrivant :