Mines Informatique optionnelle MP 2020

Thème de l'épreuve Enumération des lettres d'un texte et arbres de codage optimaux
Principaux outils utilisés programmation OCaml, listes, tableaux, complexité en temps, complexité en espace, arbres binaires de recherche, programmation dynamique
Mots clefs compression, Unicode, occurrences, encodeur, fréquence, texte, valence, distribution, répartition, table modulaire de comptage, espérance conditionnelle, complexité en moyenne, tableau creux, arbre de code, profondeur pondérée

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


A2020 -- INFO MP

Cm

Concours commun

Mines-Ponts

ÉCOLE DES PONTS PARISTECH,
ISAE-SUPAERO, ENSTA PARIS,
TÉLÉCOM PARIS. MINES PARISTECH.
MINES SAINT-ÉTIENNE, MINES NANCY,
IMT ATLANTIQUE, ENSAE PARIS, CHIMIE PARISTECH.

Concours Centrale-Supélec (Cycle International),
Concours Mines-Télécom, Concours Commun TPE/EIVP.

CONCOURS 2020
ÉPREUVE D'INFORMATIQUE MP

Durée de l'épreuve : 3 heures

L'usage de la calculatrice et de tout dispositif électronique est interdit.

Cette épreuve concerne uniquement les candidats de la filière MP.
Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :
INFORMATIQUE - MP
L'énoncé de cette épreuve comporte 9 pages de texte.
Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur

d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant 
les
raisons des initiatives qu'il est amené à prendre.
Épreuve d'option informatique MP 2020

Les techniques de compression sans perte permettent d'encoder des données 
telles que
des textes afin de les stocker en occupant un minimum d'espace. Elles 
s'appuient sur
une estimation de la fréquence d'apparition des symboles qui composent le 
texte. Dans
ce problème, nous étudions comment compter efficacement le nombre d'occurrences 
de
chaque symbole dans un texte, que l'on entendra dans la suite comme une suite 
finie de
numéros (par exemple, des numéros Unicode), et comment optimiser le 
fonctionnement
d'un encodeur pour passer d'un texte à une suite de bits.

Préliminaires

L'épreuve est composée d'un problème unique, comportant 33 questions. Après 
cette
section de préliminaires, le problème est divisé en deux parties indépendantes. 
Pour
répondre à une question, un candidat pourra réutiliser le résultat d'une 
question antérieure,
même s'il n'est pas parvenu à établir ce résultat.

Concernant la programmation

Il faudra coder des fonctions à l'aide du langage de programmation OCamil, tout 
autre
langage étant exclu. Lorsque le candidat écrira une fonction, il pourra faire 
appel à
d'autres fonctions définies dans les questions précédentes de la même 
sous-partie: il
pourra aussi définir des fonctions auxiliaires. Quand l'énoncé demande de coder 
une
fonction, il n'est pas nécessaire de justifier que celle-ci est correcte, sauf 
si l'énoncé le
demande explicitement. Si les paramètres d'une fonction à coder sont supposés 
vérifier
certaines hypothèses, il ne sera pas utile de tester si les hypothèses sont 
bien vérifiées
dans le code de la fonction.

Dans tout l'énoncé, un même identificateur écrit dans deux polices de caractères
différentes désignera la même entité, mais du point de vue mathématique pour la 
police
en italique (par exemple n) et du point de vue informatique pour celle en 
romain avec
espacement fixe (par exemple n).

On suppose codées les fonctions suivantes :

-- list _ length, de type 'a list -> int, de complexité en temps linéaire, qui 
renvoie
la longueur d'une liste,

-- list append, de type 'a list -> 'a list -> ?'a list, de complexité en temps
linéaire en la longueur du premier argument, qui concatène deux listes.

-- array make, de type int -> 'a -> 'a array, de complexité en temps linéaire en
la valeur du premier argument, qui crée un tableau d'une longueur spécifiée en

premier argument et dont chacune des cases est initialisée à une valeur donnée 
en
second argument,

-- array _length, de type 'a array -> int, de complexité en temps constante, qui
renvoie la longueur d'un tableau.

On rappelle que a mod b renvoie le reste de la division euclidienne de a par b.

Page 1 sur 9
Épreuve d'option informatique MP 2020

Dans les calculs de complexité en espace, on considérera qu'un entier occupe 
une place
constante en mémoire quelle que soit sa valeur.

Concernant les objets manipulés et leur type

L'intervalle des entiers compris entre a et b est noté [a, b]|.
La lettre Z désigne un alphabet fini ordonné de cardinal À; ses lettres, 
numérotées
dans l'ordre croissant, sont les éléments

O0, 01, 02, ..., O1-2, O1.

Par exemple, la norme Unicode est une norme fréquemment utilisée en 
informatique qui
consiste à travailler sur un alphabet de 1114112 symboles. Elle permet 
d'identifier toute
sorte de caractères (lettre de l'alphabet latin, idéogramme chinois, émoticône, 
symbole
de l'alphabet phonétique international, etc.) par un numéro unique entre 0 et 
1114111
quelle que soit la plate-forme informatique employée.

Définitions : Un mot sur un alphabet À est une suite finie de lettres de ». 
Leur en-
semble est noté »*, le mot vide est noté EUR. Un mot possède plusieurs 
caractéristiques :
la longueur d'un mot w EUR Y*, notée [w|, est le nombre de lettres qui 
composent w; la
fréquence d'une lettre o EUR Y dans un mot w EUR Y*, notée [w|,, est le nombre 
d'occurrences
de & dans w'; la valence d'un mot w EUR Y*, notée [w|, est le nombre de 
symboles distincts
qui composent w.

Un texte est une suite finie d'entiers de l'intervalle [0, À -- 1]. Le mot 
associé au texte
de s entiers [u1,u2,u3,...,u.| est le mot ou, Ou... Ou, EUR XX.

Indication OCaml : On définit les types unicode, texte et la constante globale 
lambda
par les déclarations suivantes :

type unicode = int;;
type texte = unicode list;;
let lambda = 1114112; ;

Une fonction de l'alphabet Y vers un ensemble X est représentée par un tableau 
de
longueur À de type 'a array où ?'a est le type par lequel on représente les 
éléments de X.

1 Fonction de distribution des lettres d'un texte

Le but de cette partie est de produire une structure de données qui permette de 
vérifier
la présence d'une lettre dans un mot et de stocker les valeurs non nulles de la 
fonction
de distribution des fréquences des lettres dans un mot w EUR Y* définie comme 
suit

FD

o + [wl,

Page 2 sur 9
Épreuve d'option informatique MP 2020

de trois manières différentes et de comparer les complexités en temps et en 
espace de
chaque approche.

1.1 Avec un tableau exhaustif et une liste

C] 1 -- On définit une fonction fonction1i par le code suivant

let rec fonctioni (t:texte) =
match t with
| [ ] -> array make lambda O0
| u::tprime -> let theta = fonctioni tprime in
theta.(u)<-theta. (u)+1; theta; ; Inférer le type de la fonction fonction1i. Expliquer ce que calcule fonctioni t et le démontrer par récurrence sur |t|. Définition : Soit >} un sous-alphabet de l'alphabet Y. On appelle répartition 
du sous-
alphabet ©' dans le mot w EUR X* toute liste constituée de tous les couples 
(o,[w|,) tels
que o EUR X'et [w|, > 0. Cette liste peut être dans un ordre quelconque. La 
répartition
d'un sous-alphabet dans un texte est la répartition de ce sous-alphabet dans le 
mot
associé au texte.

Par exemple, une répartition des lettres du mot acad est la liste 
[(a,2),(c,1),(d,1)|.

Indication OCaml : En OCamil, on pourra se servir du type

type repartition = (unicode *x int) list;;

CT 2 -- Ecrire une fonction cree _repartition, de type texte -> repartition
qui renvoie une répartition d'un texte en utilisant la fonction fonction!
définie à la question I.

CT] 3 -- Déterminer la complexité en temps de la fonction cree _repartition
en fonction du cardinal À de l'alphabet et d'une caractéristique du texte
donné en entrée.

[] 4 -- Déterminer la complexité en espace de la fonction cree _repartition
en fonction du cardinal À de l'alphabet.

[] 5 -- Donner sans justification un ordre de grandeur de la taille de la valeur
de retour de cree repartition en fonction d'une caractéristique du texte
donné en entrée.

[] 6 -- Comparer les ordres de grandeur obtenus dans les trois questions
précédentes quand le texte donné en entrée est le texte d'un courriel de la vie
courante rédigé en langue française et X est l'alphabet Unicode.

Page 3 sur 9
Épreuve d'option informatique MP 2020

1.2 Avec une table modulaire

Définition : Soient w EUR >* un mot et m EUR N° un entier non nul. Pour tout 
entier L
compris entre 0 et m -- 1, on note Xl] le sous-alphabet de Y défini par

DT = fos, u EUR [0, À -- 1]; (u -- L) est divisible par m}.

Une table modulaire de comptage d'ordre m du mot w est un tableau de longueur m 
dont
la £-ième case contient une répartition des lettres de Xl dans w.

Par exemple, avec l'alphabet © = {a,b,c,d,e} muni de l'ordre alphabétique et 
l'entier
m = 3, une table modulaire de comptage d'ordre 3 du mot acad est le tableau de 
trois

listes
| [Ca, 2); (d, 1)1 | [1 L I(c; 1)1 |

[] 7 - Ecrire une fonction incremente_ repartition, de type repartition ->

unicode -> repartition telle que incremente repartition r u renvoie la
répartition d'un mot qui contient la lettre o, une fois de plus qu'un mot de
répartition r.

[] 8 -- Écrire une fonction cree modulaire, dont le type est texte -> int ->
repartition array, qui utilise la fonction définie à la question 7, telle que la
valeur de retour de cree modulaire t m est une table modulaire de comptage
d'ordre m du texte t.

Le recours à la fonction fonctioni de la question 1 n'est pas autorisé pour
répondre à cette question.

CT 9 -- Ecrire une fonction valence, de type repartition array -> int, qui
renvoie la valence d'un mot à partir de sa table modulaire de comptage.

[] 10 -- Soient m et v deux entiers non nuls et X3, X2. ... X, des variables
aléatoires discrètes à valeurs dans l'intervalle entier [0,m -- 1], mutuellement
indépendantes et qui suivent la loi de distribution uniforme. Soient encore
un entier t fixé dans l'intervalle [1,v] et un entier {9 fixé dans l'intervalle
[0,m -- 1]. Pour tout entier { compris entre 0 et m -- 1, on appelle Z, le
cardinal

Z= Elo: Xi= tj].
Pour tout entier { compris entre 0 et m -- 1, calculer l'espérance

ElZ1X; = bol.

CT 11 -- Soit w EUR Y* le mot d'un texte t de valence v. En supposant que
l'ensemble des v lettres distinctes présentes dans le mot w a été choisi unifor-
mément dans l'ensemble des parties à v éléments de l'alphabet Ï, montrer
que la complexité moyenne en temps de la fonction cree modulaire t m est

o(m+le+ LR)

Page 4 sur 9
Épreuve d'option informatique MP 2020

L] 12 -- Donner sans justification la complexité en espace de la fonction
cree modulaire t m en fonction de m et d'une caractéristique du texte #.

[] 13 -- Quelle valeur numérique de m suggérez-vous de choisir lorsque t est

le texte d'un courriel de la vie courante rédigé en langue française et Y est
l'alphabet Unicode ?

1.3 Avec un tableau creux

Définition : Un tableau creux de comptage du mot w EUR Y* est un quadruplet (v, 
F, 1, A)

formé d'un entier v et de trois fonctions F:È=N 1:25 Yet À: Y tels que
(i) l'entier v est la valence du mot w,

(ii) pour toute lettre o EUR Y présente dans le mot w, il existe une lettre 7 
EUR Y telle que
T < Ow-1 et Î(T) = 0. (iii) pour toute lettre Tr EUR Y telle que 7 < 0,_1, on a A(J(T)) =7, (iv) pour toute lettre o EUR Y présente dans le mot w, on à F(o) = [w|,. Par exemple, avec l'alphabet Y = {à,b,c,d,e, f,g,h}, le mot bbbbbbbbbbbbehhhhhhhhh admet comme tableau de comptage le quadruplet (v, F1, A) __jalo]c]dle/flglh] Flx|12/*x) x | 1|xlx)9 Tlblelhlixlxl x |x)x Alxlalxlx| blxlxlc où chaque symbole *x représente une valeur particulière mais non significative. Indication OCaml : En OCamil, on pourra se servir du type type creux = int * int array * unicode array * unicode array;; On pourra utiliser une fonction make _ creux, de type int -> creux qui crée et 
renvoie
un tableau creux de comptage du mot vide en temps constant, aucune hypothèse ne
pouvant être faite sur le contenu des trois tableaux constituant la valeur de 
retour de
cette fonction.

CT 14 -- Soit (v,F,1, A) un tableau creux de comptage du mot w EUR Y*.
Montrer que pour toute lettre 7 EUR Y avec T7 < o%_1, la lettre Z(T) est une lettre présente dans le mot w. CT 15 -- Soit (v, F,1, A) un tableau creux de comptage du mot w EUR Y*. Montrer que pour toute lettre o EUR »;, la lettre o est présente dans le mot w si et seulement si on à A(o) < o4_1 et 1(A(o)) = ©. Page 5 sur 9 Épreuve d'option informatique MP 2020 CT 16 -- Écrire une fonction est_present de type creux -> unicode -> bool
telle que la valeur de retour de tableau creux theta u est vraie si et seulement
si la lettre o, est une lettre présente dans un mot de tableau creux de
comptage 0. Justifier la correction et la terminaison de la fonction.

[] 17 -- Écrire une fonction incremente tableaucreux, de type creux ->
unicode -> creux, telle que la valeur de retour de incremente tableaucreux
theta u est un tableau creux de comptage d'un mot qui contient la lettre ©,
une fois de plus qu'un mot de tableau creux de comptage 6.

CT 18 -- Écrire une fonction cree _tableaucreux de type texte ---> creux qui
renvoie le tableau creux de comptage du texte donné en argument.

Le recours à la fonction fonctioni de la question 1 n'est pas autorisé pour
répondre à cette question.

[] 19 -- Déterminer la complexité en temps de la fonction cree _tableaucreux.

[] 20 -- Donner sans justification la complexité en espace de la fonction
cree tableaucreux.

[] 21 -- Est-il réaliste d'utiliser cette fonction pour le texte d'un courriel 
de
la vie courante rédigé en langue française encodé avec l'alphabet Unicode
lorsqu'on utilise un ordinateur ou un téléphone actuel ?

2 Un encodeur optimal

2.1 Codes et codages

Définitions : Un code c est une application
ci {0,1}*.
Le codage associé à un code c est l'application

.- >* -- {0,1}*

TiT2...7n > C(n)c(n)---c(T)
Un arbre de code représentant un code c est un arbre binaire, dont l'ensemble 
des sommets
est »;, tel que
-- pour toute lettre o EUR Y, l'étiquette du sommet © est c(o),

-- pour toutes lettres o et 7 de l'alphabet », si 7 appartient au sous-arbre 
gauche
de ©, alors on a T7 < © dans l'ordre de l'alphabet » : si 7 appartient au sous-arbre droit de ©, alors on a 7 > © dans l'ordre de l'alphabet ».

Page 6 sur 9
Épreuve d'option informatique MP 2020

Indication OCaml : On adopte les déclarations de type suivantes afin de 
représenter
les mots binaires et les arbres de code en OCamil :
type binaire = bool list;;
type code =
| Nil
| Noeud of unicode * binaire * code * code: ;

[] 22 -- Écrire une fonction encodeur, de type texte -> code -> bool list,
qui, à partir d'un texte t et d'un code c, renvoie le codage du mot du texte t
par le codage associé au code c.

On note prof ,(o) la profondeur d'un sommet o dans un arbre À, c'est-à-dire le 
nombre
de sommets de l'unique chemin entre le sommet © et la racine de À. En 
particulier, la
racine p d'un arbre À est de profondeur prof 4(p) = 1.

[] 23 -- Pour un code c donné, exprimer la complexité en temps de la fonction
encodeur à l'aide de L -- max,-s |[c(o)|, des profondeurs des sommets de
l'arbre de code À et de la distribution des fréquences dans le mot w donnés
en argument

2.2 Arbre de code optimal

On fixe un code c de l'alphabet À ainsi que des poids réels positifs sous la 
forme d'une
application f : © -- R.. La profondeur pondérée d'un arbre de code À 
représentant le
code c est la somme

Prof(.A) -- > f(o) prof 4A(o).

oEr

[1 24 -- Exprimer la profondeur pondérée Prof(.4) d'un arbre de code À en
fonction de f, de la profondeur pondérée Prof(A4,) du sous-arbre gauche À,
de l'arbre de code À et de la profondeur pondérée Prof(4;) du sous-arbre
droit À, de l'arbre de code À.

On dit qu'un arbre de code est optimal si sa profondeur pondérée est la plus 
petite des
profondeurs pondérées des arbres de code représentant un code de l'alphabet Y. 
Pour
tous entiers u et vu compris entre 0 et À -- I avec u < v, on note c,., la restriction du code c à l'alphabet 2,4 = {ou, Our1,..., 001,0}. On note Il, la profondeur pondérée d'un arbre de code représentant le code c,, optimal. C1 25 -- Pour tout entier u compris entre 0 et À -- 1, calculer IL, 4. Pour tous entiers u et v compris entre 0 et À -- 1 vérifiant u < v, exprimer une relation entre Il, et les quantités (IL, )ucreu-1 EURt (lro)ur1 IL, 0+1

est une application continue et affine par morceaux sur R.; dont on précisera
la pente pour chaque morceau et que, pour tout intervalle ouvert 1 EUR R,
sur lesquels l'application ñ; +1 est affine, les indices (ru)
constants lorsque f(0,:1) varie dans J.

u a un
réel tel que l'application 7,41 soit affine sur l'intervalle 2* = |a, BY.

On construit deux suites (d,) et (dÿ) par récurrence. Chaque suite s'arrête si 
le terme
suivant n'est plus défini. Pour construire la première suite, on choisit 
f(o,:1) dans
l'intervalle 77 et on pose

dy -- Tu,v+1

Pour construire la seconde suite, on choisit f(0,:1) dans l'intervalle 77 et on 
pose

+
dj -- Tu,v+1
° + + nn .
si dy  m*.

On suppose avoir démontré la validité de l'encadrement £EUR(n) pour un certain 
entier n.
On suppose que les entiers u et v vérifient v---u £ 

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



Mines Informatique optionnelle MP 2020 --
Corrigé
Ce corrigé est proposé par Vincent Puyhaubert (professeur en CPGE) ; il a été
relu par Guillaume Batog (professeur en CPGE) et Benjamin Monmege 
(enseignantchercheur à l'université).

Cette épreuve est composée de deux parties indépendantes.
· La première aborde plusieurs façons de compter les occurrences de chaque 
lettre
dans un texte. On cherche des solutions efficaces pour des textes écrits avec
un alphabet de grande taille (l'alphabet Unicode, qui comporte de l'ordre du
million de caractères différents). Cette partie propose trois implémentations
différentes. Elle est assez simple.
· La partie II s'intéresse aux arbres de recherche optimaux, dans un contexte
d'encodage de texte. Encoder un texte nécessite d'associer un code binaire à
chaque lettre de l'alphabet. L'ensemble des lettres et leur code est stocké 
sous la
forme d'un arbre binaire de recherche. Pour trouver le code d'une lettre, il 
faut
parcourir l'arbre, ce qui est d'autant plus coûteux que la lettre est profonde.
Le coût total d'encodage d'un texte dépend donc du nombre d'occurrences et
de la profondeur de chaque lettre. On veut alors trouver la forme de l'arbre qui
minimise ce coût.
Dans la première sous-partie, plutôt élémentaire, il faut écrire l'algorithme 
d'encodage et déterminer sa complexité. La deuxième sous-partie, plus difficile,
donne une méthode de programmation dynamique qui permet de déterminer
un arbre de code optimal en O(3 ) opérations élémentaires où  est le cardinal
de l'alphabet. La dernière sous-partie démontre un résultat qui permet 
d'améliorer cette méthode pour construire l'arbre en seulement O(2 ) opérations
élémentaires. Elle est aussi technique que difficile.
Ce sujet aborde des problématiques classiques, importantes et très intéressantes
en algorithmique. Hélas, il souffre de deux défauts : la faible qualité de son 
écriture
et la grande hétérogénéité dans la difficulté des questions. Si la majeure 
partie des
questions de la première partie ne devraient pas poser de problème, les 
questions de la
dernière partie nécessitent une finesse et une technicité (magnifique) qu'il 
est difficile
d'acquérir après deux années de classe préparatoire. Par ailleurs, les 
questions 10
et 11 sont hors-programme.

Indications
Partie I
1 Justifier que fonction1 renvoie un tableau dont la i-ième case contient |t|i .
2 Parcourir le tableau renvoyé par fonction1 à la recherche des cases contenant
des valeurs non nulles.
6 Noter qu'un courriel classique contient de 1 000 à 10 000 caractères, et 
utilise une
centaine de lettres différentes.
7 Parcourir la liste pour voir si elle contient un couple dont le premier 
élément est u
auquel cas on incrémente le deuxième. Dans le cas contraire, il suffit de lui 
ajouter
un nouveau couple.
8 On peut utiliser le même principe que pour fonction1 en créant un tableau
de m listes dans le cas d'arrêt et en utilisant incremente_repartition dans le
cas général.
9 Il suffit de sommer les longueurs des listes dans la table renvoyée par la 
question 8.
10 L'espérance conditionnelle n'est pas au programme des classes préparatoires, 
cette
question n'est pas traitable.
11 La notion de complexité en moyenne n'est pas non plus au programme, cette
question n'est pas non plus traitable.
13 Justifier qu'il est plus judicieux de prendre m de l'ordre de la valence de 
t.
14 Vérifier que I induit une injection sur {0 , . . . , v-1 } et préciser son 
image.
15 Le sens indirect découle de la question précédente. Pour le sens direct, 
utiliser (ii)
puis appliquer A.
16 Utiliser la question précédente. La terminaison et la correction de cette 
fonction
est triviale, ne pas s'étonner.
17 Il s'agit juste de tester si u est présent grâce à la fonction précédente, 
puis de
mettre à jour les tableaux représentant A et I en conséquence.
18 On peut encore une fois garder le même schéma de rédaction que fonction1, en
utilisant cette fois make_creux pour le cas d'arrêt et incremente_tableaucreux
dans le cas général.
21 Les machines actuelles sont capables d'effectuer de l'ordre de 1012 
opérations
élémentaires par seconde.
Partie II
22 Implémenter une fonction qui encode une lettre à l'aide d'un parcours 
récursif de
l'arbre représentant le code, comme pour un arbre binaire de recherche.
23 Le coût d'une recherche dans un arbre est proportionnel à la profondeur de la
valeur cherchée (lorsqu'elle s'y trouve). Une concaténation de deux listes a un
coût linéaire en la taille de celle de gauche.
24 Dans la définition de la profondeur, séparer la somme en trois en 
distinguant le
noeud contenant la racine et les sous-arbres gauche et droit.
25 Démontrer l'égalité
v

P
u,v =
f (k ) + min
u,-1 + +1,v
k=u

[[ u ; v ]]

en utilisant les techniques classiques de programmation dynamique.

26 Appliquer les méthodes de programmation dynamique pour calculer les 
quantités (u,v )06u6v6-1 les unes après les autres. On utilisera la question 
précédente
pour calculer (u,u+d )06u6-d-1 pour d croissant de 1 à  - 1.
27 Chaque application de la formule de la question 25 nécessite une recherche 
de minimum qui s'effectue en O(v -u) opérations élémentaires. Remarquer que 
E(-2)
permet de ramener ce coût à un O(ru,v+1 - ru,v ) et utiliser un téléscopage.
28 On rappelle que dans un arbre de code, les lettres apparaissant dans le fils 
droit
d'un noeud sont strictement plus grandes que celle contenue dans le noeud.
29 Remarquer que A et A0 ont la même profondeur puis, à partir d'un arbre B 0 de
code représentant cu,v+1 quelconque, construire un arbre B représentant cu,v de
profondeur inférieure à B 0 .
30 Remarquer que si A est un arbre de code quelconque représentant cu,v+1 , la
formule donnant la profondeur définit une fonction affine de f (v+1 ) et 
déterminer
sa pente. Puis, utiliser le fait que u,v+1 est défini comme le minimum de toutes
les profondeurs des arbres de code représentant cu,v+1 .
31 Une suite strictement croissante d'entiers majorée est nécessairement finie. 
Pour la
+
deuxième partie, remarquer que par définition des suites (d-
k ) et (dk ), on peut
construire un arbre de code optimal de la forme
d-
0

d -
1

d -
m-

Faire ensuite le lien entre m- et m+ et la pente de la fonction affine par 
morceaux u,v+1 à l'aide de la question précédente. Enfin, justifier que, en 
chaque
point où la pente de u,v+1 change, celle-ci ne peut que décroître.
32 Cette question est à l'origine de beaucoup de souffrances. Il est conseillé 
de ne
pas chercher à la résoudre, et de se contenter de lire le « corrigé ».
33 Raisonner par récurrence sur n. Pour l'hérédité, l'une des égalités se 
déduit en faisant le bilan des questions précédentes, afin d'en conclure que f 
(v+1 ) 7- ru,v+1
est une fonction croissante sur R+ qui prend en 0 une valeur supérieure ou
égale à ru,v .
On utilisera également un argument de symétrie pour l'autre inégalité.

Les fonctions fournies par l'énoncé existent déjà en OCaml (avec des noms
quasiment identiques). Dans ce cas de figure, il est toutefois impératif 
d'utiliser les outils du sujet. Pour ceux qui souhaiteraient tester leur code, 
il suffit
de définir les 4 fonctions données, par exemple de la manière suivante :
let
let
let
let

list_length = List.length ;;
list_append l1 l2 = l1@l2 ;;
array_make = Array.make ;;
array_length = Array.length ;;

Pour simplifier la rédaction, on identifiera directement un texte (qui est ici
une suite d'entiers) et le mot associé (qui est une suite de lettres). En 
particulier, on utilisera directement la notation |t| lorsque t est un texte et 
une lettre.

I. Fonction de distribution des lettres d'un texte
1 La fonction fonction1 possède un unique argument du type texte. Lorsque ce
dernier est une liste vide, elle renvoie un tableau d'entiers de  = 1 114 112 
cases
initialisées à 0. On en déduit donc que
La fonction fonction1 est de type texte -> int array.
Rappelons que, contrairement à un langage comme Python, les fonctions
OCaml doivent renvoyer des résultats ayant le même type. Par conséquent, il
suffit d'identifier ce type dans n'importe quel cas d'arrêt de la fonction pour
en déduire le type du résultat dans tous les cas.
Justifions maintenant que fonction1 prend en argument un texte t et renvoie un
tableau de la forme [| |t|0 , |t|1 , . . . , |t|-1 |], c'est-à-dire un tableau 
dont la i-ième
case contient la fréquence de la i-ième lettre de  dans t. Comme l'impose 
l'énoncé,
on procède par récurrence à l'aide du prédicat suivant :
P(k) :

« Si t est un texte de longueur k, alors fonction1 t renvoie
un tableau de  cases dont la i-ième case contient |t|i . »

· P(0) est trivialement vrai car si k = 0, cela signifie que t est un texte 
vide, auquel cas la fonction renvoie un tableau de taille  dont toutes les 
cases valent 0.
· P(k) = P(k + 1) : Supposons le résultat vrai pour tout texte de longueur k.
Soit t un texte de longueur k + 1. Nécessairement, t n'est pas vide car k + 1
n'est pas nul. La fonction fonction1 appelle alors le deuxième cas du filtrage
qui lance un appel récursif sur la queue tprime de t qui est de longueur k ce 
qui
permet d'appliquer l'hypothèse de récurrence. Le résultat theta de cet appel
récursif est un tableau de  cases dont la i-ième case contient la valeur |t|i .
Cet appel est suivi d'une instruction qui incrémente de 1 la case de theta
correspondant à l'indice de la tête (c'est-à-dire la première lettre) du texte.
On en déduit donc clairement qu'à la fin de cette instruction, le tableau theta
qui est renvoyé est de la forme souhaitée. Ainsi, P(k + 1) est vraie.
· Conclusion : Pour tout k > 0, P(k) est vrai.
Notamment,
La fonction fonction1 prend en argument un texte t et renvoie un tableau
dont la i-ième case contient la fréquence de la lettre i dans le mot associé à 
t.