Centrale Informatique optionnelle MP 2016

Thème de l'épreuve Un algorithme de tri
Principaux outils utilisés listes, tas, recursivité

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


Option informatique
MP

4 heures Calculatrices autorisées

2016

Un algorithme de tri

I Présentation

I. A -- Motivation

Trier des données est un problème récurrent dans tous les systèmes 
d'information. Dans un système travaillant
en temps réel (par exemple un système de freinage d'une voiture) ou un système 
pouvant être soumis a des
attaques (par exemple un serveur web), on s'intéresse à la complexité dans le 
pire des cas.

Or, dans une application réelle, les données que l'on veut trier ne sont pas 
quelconques mais suivent une certaine
distribution aléatoire, qui est loin d'être uniforme : ainsi, il est fréquent 
que les données soient déjà presque triées.
De plus, de nombreux algorithmes de tris (même les plus performants) atteignent 
leur complexité maximale
lorsque les données sont déjà triées.

Le but de ce problème est d'étudier un algorithme de tri, proche du tri par tas 
mais présentant avec lui
quelques différences significatives et notamment des performances intéressantes 
lorsque les données qu'il reçoit
sont presque triées.

Dans tout le problème, on triera, par ordre croissant, des valeurs entières.

Dans toutes les questions de complexité en temps, la mesure de complexité à 
considérer est le nombre de
comparaisons par la relation d'ordre < entre entiers.

I.B * Notations et préliminaires

Dans la suite, si un objet mathématique est noté t, on notera t l'objet Caml 
qui l'implante et, si t appartient a
un ensemble T implanté en Caml par le type T, on écrira de manière équivalente 
t EUR T ou t : T. Par exemple,
pour signifier que l désigne une liste d'entiers, on notera l : int list.

Étant donné deux fonctions f et g à valeurs positives, on note :

-- f : O(g) pour exprimer qu'il existe une constante C telle que, pour tout n 
suffisamment grand, f (n) < Cg(n) ;

-- f : Q(g) pour exprimer qu'il existe une constante C > 0 telle que pour, tout 
n suffisamment grand,
f(fl) ? Cg(fl) ;

-- f : ®(g) pour exprimer qu'on a f : O(g) et f : Q(g).

On tiendra compte dans la suite que la structure à trier n'est pas un ensemble, 
car le même élément peut être

répété plusieurs fois. Ainsi on sera amené à manipuler en Caml des listes ou 
des vecteurs dans lesquels un

même élément peut apparaitre plusieurs fois, et des arbres dans lesquels la 
même valeur peut étiqueter plusieurs

sommets différents. Dans la suite, lorsqu'il s'agira de déterminer le minimum 
d'une telle structure, il pourra être

atteint plusieurs fois ; de même, lorsqu'on triera ou « réunira » deux telles 
structures, ce sera toujours en tenant

compte des répétitions, c'est--à--dire sans perte d'éléments. Ainsi, par 
exemple, pour les listes l1 : (7, 4, 2, 8, 2, 7, 3)

et l2 : (5, 2, 3, 9), le minimum de l1 est 2, trier l1 consiste à renvoyer la 
liste [2 ;2 ;3 ;4 ;7 ;? ;8] et « réunir »

l1 et [2 consiste à renvoyer la liste [? ;4 ;2 ;8 ;2 ;? ;3 ;5 ;2 ;3 ;9].

De manière générale, lorsqu'on dira que deux structures de données contiennent 
les mêmes éléments, ce sera

toujours en tenant compte des répétitions. Par exemple les listes [1 ;2 ;2] et 
[2 ;1 ;2] contiennent les mêmes

éléments mais pas les listes [3 ;4 ;4] et [4 ;3 ;3].

II Algorithme sur des arbres

II.A * Tri par insertion

II.A.1) Écrire la fonction insere : int --> int list --> int list insérant un 
élément dans une liste sup--
posée triée, c'est--à--dire telle que pour toute liste 11 supposée triée et 
tout élément x, (insere :( u) renvoie une
liste v telle que

-- v contient les mêmes éléments que x : : u ;

-- v est triée.

II.A.2) Écrire la fonction tri_insertion : int list --> int list triant la 
liste reçue en argument en uti--
lisant la fonction précédente.

2016--03-03 07:54:57 Page 1/7 @@ BY--NC-SA

II.A.3) Pour n EUR IN, on note PI (n) le nombre de comparaisons effectuées par 
l'appel (tri_insertion 1) dans
le cas le pire pour une liste 1 de longueur n. On note de même M [(n) le nombre 
de comparaisons effectuées
dans le cas le meilleur.

Déterminer PI(n) et Ml(n).

II.B + Tas binaires

On appelle arbre un arbre binaire étiqueté par des éléments de N. Un tel arbre 
est implanté en Caml a l'aide
de la déclaration de type suivante :

type arbre =
| Vide
l Noeud of int * arbre * arbre ;;

On définit la hauteur et la taille (appelée aussi nombre d'éléments) d'un arbre 
a, notées respectivement haut(a)
et |a| par induction sur la structure de l'arbre :

-- haut(Vide) : 0 et haut(Noeud(x,al ,a2)) : 1 + max{haut(al), haut(a2)}

-- |Vide| : 0 et |Noeud(x,al,a2)| : 1 + |a1| + |a2|

pour tous arbres binaires al et a2 et tout entier x.

x, al et a2 sont appelés respectivement la racine, le fils gauche et le fils 
droit de l'arbre a.

On dit que deux arbres ont mêmes éléments s'ils ont les mêmes ensembles 
d'étiquettes et que chaque étiquette
présente apparait le même nombre de fois dans chacun des arbres.

On dit qu'un arbre binaire est parfait s'il s'agit de l'arbre vide Vide, ou 
s'il est de la forme Noeud(x, al , a2) où
al et a2 sont deux arbres parfaits de même hauteur.

On dit qu'un arbre binaire est un tas binaire parfait (ou simplement un tas 
parfait) si c'est un arbre parfait et
que la valeur étiquetant chaque noeud de l'arbre est inférieure ou égale à 
celle de ses fils.

On dit qu'un arbre binaire est un quasi--tas si c'est un arbre de la forme 
Noeud(x , al , a2) et que al et a2 sont des
tas binaires parfaits de même taille : aucune contrainte d'ordre n'est donc 
imposée sur l'étiquette de la racine x.

Etant donné un arbre non vide a, on note min A(a) le minimum des éléments qu'il 
contient.

II.B.1) Pour k: EUR IN, on note mk la taille d'un arbre binaire parfait de 
hauteur le. Déterminer mk pour tout
le EUR Ù\l. On justifiera la réponse en exprimant mk+1 en fonction de mk.

II.B.2) Écrire la fonction min_tas : arbre --> int telle que pour tout tas 
binaire parfait a non vide, (min_tas a)
renvoie min A (a). On fera en sorte que la complexité en temps de min_tas soit 
constante.

II.B.3) Écrire la fonction min_quasi : arbre --> int tel que pour tout 
quasi-tas a, (min_quasi a) renvoie
min A(a) en temps constant.

II.B.4) Écrire la fonction percole: arbre --> arbre telle que (percole a) 
renvoie a si a est l'arbre vide
et, si a est un quasi--tas, renvoie un tas binaire parfait contenant les mêmes 
éléments. Donner la complexité de
percole dans le cas le pire, en fonction de la hauteur le du quasi--tas a.

II.C + Décomposition parfaite d'un entier

L'algorithme de tri que l'on va étudier repose sur une propriété remarquable 
des nombres mk obtenus à la
question II.B.1.

Étant donné un entier naturel r, on dit qu'un r--uplet (k1, ..., k,.) d'entiers 
naturels non--nuls vérifie la propriété
QS C (pour « quasi strictement croissant ») si l'une des trois conditions 
suivantes est vérifiée :

-- r < 1 ;

-- our=2etklgk2;

-- our23etklgk2 int list telle que, pour tout 
entier naturel 11, (decomp_parf n)
renvoie la liste (mkl, ..., mk.' des entiers apparaissant dans la décomposition 
parfaite de n (dans cet ordre). Cette
fonction devra avoir une complexité temporelle en 001).

II.D + Création d'une liste de tas

On appelle liste de tas une liste de couples de la forme (a, t) où a désigne un 
arbre binaire parfait et t : |a| est
la taille de l'arbre a : il existe donc un entier naturel le tel que t : mk.

Une liste de tas est implantée en Caml par le type (arbre * int) list.

Étant donnée une liste de tas h de la forme précédente, on définit :
-- la longueur de h, notée long(h), par

0 si h est la liste vide

long(h) : {r si h : ((a1,t1), ..., (a...tT))

-- la taille de h, notée |hl, par

0 si h est la liste vide
lhl : lÊLI+...+IOETI Si h= ((a17t1>7"'7(ar7tr))
=t1 =t7'

-- la hauteur de h, notée haut(h), par

haut(h) -- 0 si h est la liste vide
_ max{haut(al),...,haut(a,)} si h =((a17t1)7...,(a t >)

T'?"

-- le minimum de h, noté minÿf(h), par

. +oo si h est la liste vide
minH (h) :

min{minfl(al), ...,minfl(ar)} si h : ((a1,tl), ..., (ar,tr))

Comme pour les arbres binaires, on dit que deux listes de tas ont mêmes 
éléments si les deux listes des arbres
les constituant font apparaitre exactement les mêmes étiquettes avec exactement 
le même nombre d'apparitions
de chaque étiquette. De même, une liste l d'entiers naturels et une liste de 
tas constituée d'arbres dont les
étiquettes appartiennent a N ont mêmes éléments si les deux structures font 
apparaitre exactement les mêmes
éléments avec le même nombre d'apparitions de chaque élément.

On dit qu'une liste de tas h : ((a1,tl), ..., (a,, t,)) vérifie la condition TC 
(pour « tas croissants ») si le r--uplet
d'entiers naturels (tl, ..., t,,) vérifie la propriété QSC. On peut remarquer 
qu'une liste de tas h vérifie la condition

TC si et seulement si |h| : tl + + t,, est une décomposition parfaite de |h|. 
En particulier, la liste de tas vide

vérifie la condition TC ; on constate enfin que toute liste de tas de la forme 
h = ((a, |a|)) vérifie la condition
TC.

II.D.1)

a) Si h est une liste non vide de tas, a--t--on nécessairement haut(h) : O(log2 
|hl) '? A--t--on nécessairement
long(h) : O(log2 |hl) ? Justifier.

b) Même question si h est une liste de tas vérifiant la condition TC.

II.D.2) Considérons un arbre réduit à sa racine (c'est--à--dire un couple (a, 
l) correspondant à un tas binaire
parfait) et une liste de tas h : ((a1,tl), ..., (a,.,t,.)) vérifiant la 
condition TC. Si l'on ajoute le couple (a, l)
en tête de la liste h, on obtient bien une liste de tas (a, 1) :: h = ((a, l), 
(a1,t1), ..., (a,,,t,,)), mais qui ne vérifie
peut--être plus la condition TO. L'objectif de cette question consiste à 
concevoir, en utilisant les outils mis en
oeuvre dans les questions précédentes, un algorithme qui construit une liste de 
tas h' ayant les mêmes éléments
que (a, l) :: h telle que h' vérifie la condition TC.

(1) On considère h1 : ((aî,l),(aî,3),(aî,7)) et h2 : ((aâ,3),(aâ,3), (aâ,7)) 
deux listes de tas vérifiant la

condition TC, où les arbres aî, aÎ, aÎ et aâ, aâ, aâ sont donnés figure 1.

2016--03-03 07:54:57 Page 3/7 @@ BY--NC-SA

Figure 1

Expliquer de manière détaillée (à l'aide de représentations graphiques) comment 
on construit les listes de tas
h'1 et h'2 lors de l'ajout de l'arbre a réduit à sa racine d'étiquette 8 dans 
chacune des listes de tas h1 et %.

b) Décrire le plus précisément possible un algorithme qui consiste a construire 
h' a partir d'un arbre a réduit à
sa racine et d'une liste de tas h vérifiant la condition TC. On fera en sorte 
que cet algorithme ait une complexité
dans le cas le pire en O(haut(afl) (où al est le premier tas de la liste h) et 
en O(1) dans le cas le meilleur. On
justifiera soigneusement la correction de la fonction et brièvement sa 
complexité dans le cas le pire.

0) Écrire la fonction ajoute : int --> (arbre * int) list --> (arbre * int) 
list telle que
(ajoute x h) renvoie la liste de tas vérifiant la condition TC construite par 
l'algorithme de la question précé--
dente a partir d'un arbre a réduit à sa racine :( et une liste de tas h 
vérifiant la condition TC.

II.D.3) On définit la fonction suivante, de type int list --> (arbre * int) 
list :

let rec constr_liste_tas l = match 1 with

| [] -> []

| X : : r --> ajoute x (constr_liste_tas r)
Il est clair que l'appel (constr_liste_tas l) renvoie une liste de tas 
vérifiant la condition TC et ayant les
mêmes éléments que la liste 1.
a) Montrer que le coût en temps de l'appel (constr_liste_tas l) pour une liste 
1 : int list déjà triée de
longueur 71 dans le cas le pire est en O(n).

b) Montrer que, pour une liste 1 : int list de longueur 71, (constr_liste_tas 
l) a une complexité tempo--
relle en O(n log2 n) dans le cas le pire.1

II.E * Tri des racines

On dit qu'une liste de tas h : ((a1,t1). ..., (a...tr)) vérifie la condition RO 
(pour « racines ordonnées ») si les

tas présents dans la liste apparaissent par ordre croissant de leurs racines 
ou, ce qui est équivalent, par ordre
croissant de leurs minimums : min/, (al) < < min/{(ar)

On considère une liste de tas h : ((a1,t1), ..., (a... tr)) vérifiant la 
condition T C et ne vérifiant pas nécessairement
la condition RO. On veut réarranger les éléments apparaissant dans h de façon a 
obtenir une liste de tas h'
vérifiant a la fois la condition TC et la condition RO. Si l'on trie 
brutalement par insertion les tas de h dans
l'ordre croissant des racines, on risque de perdre la condition TO. On va donc 
mettre en place un tri s'inspirant

du tri par insertion mais consistant à échanger les racines des tas présents 
dans h plutôt que les tas eux--mêmes.

II.E.1) Écrire la fonction echange_racines : arbre --> arbre --> (arbre * 
arbre) de complexité constante
telle que, si al et a2 sont deux arbres binaires non vides, (echange_racines al 
a2) renvoie le couple d'arbres
passés en argument en se contentant d'échanger les étiquettes de leurs racines.

II.E.2) On considère une liste de tas non vide h : ((a1,t1), ..., (a... fin)) 
vérifiant la condition BO et un quasi--tas
@ de taille t. Montrer que :

a) si minfl(a) < minA (al), alors (percole a, t) : : h est une liste de tas 
vérifiant la condition RO ;

b) si minfl(a) > min/[(el) et si on pose (b,b1) = (echange_racines a al), alors 
b est un tas binaire parfait,
bl est un quasi--tas et minfl(b) : min/[(el) g minfl(b1).

II.E.3) On examine maintenant trois exemples de couples (a,h) pour lesquels @ 
est un quasi--tas et h est
une liste de tas non vide vérifiant la condition RO. On souhaite a chaque fois 
faire évoluer la liste de tas
(a, |a|) :: h jusqu'à obtenir une liste de tas vérifiant la condition RO7 en ne 
s'autorisant pour seules opérations

On peut en fait démontrer que cette complexité est un O(n) mais cela n'est pas 
demandé.

2016--03-03 07:54:57 Page 4/7 @@ BY--NC-SA

que d'éventuelles permutations entre des étiquettes d'un même arbre ou entre 
des étiquettes de deux arbres
distincts (aucune modification de la forme ou de la taille d'aucun arbre en jeu 
n'est autorisée).

Les couples considérés sont notés (a1,h1), (a2,h2) et (a3,h3), avec h1 : 
((aî,7)), h2 : ((aâ,7)) et % :

((aâ, 3), (aâ, 7)), où les arbres al, a1 a? sont donnés figure 2.

1 1
1, a2, (1.2 et (L3, a3, %

CL1=

Figure 2

Pour chacun de ces trois couples, détailler (à l'aide de représentations 
graphiques) les étapes de la transformation
de la liste (a, |a|) :: h en une liste de tas vérifiant la condition RO. Chaque 
étape devra être clairement identifiée
comme faisant appel a un procédé précédemment décrit.
II.E.4) Décrire et justifier le plus précisément possible un algorithme qui, a 
partir d'un quasi--tas a, de sa
taille t et d'une liste de tas h, renvoie une liste de tas h' identique a (a, 
t) :: h a permutation près des étiquettes
des arbres et tel que si h vérifie la condition RO, alors h' vérifie la 
condition RO.
Montrer que sa complexité en temps est en O(1) si a est un tas non vide, que la 
liste de tas h vérifie la condition
R0 et que min/[(a) g minfl(h).
Montrer que sa complexité en temps est en O(k' + r) où k : max{haut(a), 
haut(h)} et r : long(h).
II.E.5) Écrire la fonction

insere_quasi : arbre --> int --> (arbre * int) list --> (arbre * int) list

telle que (insere_quasi a t h) renvoie la liste de tas vérifiant la condition 
RO construite par l'algorithme de
la question précédente à partir d'un quasi--tas a de taille t et une liste de 
tas h vérifiant la condition RO.

II.E.6) Écrire la fonction tri_racines : (arbre * int) list --> (arbre * int) 
list transformant une
liste de tas h supposée vérifier la condition TC en une liste de tas h' 
vérifiant a la fois la condition BO et la
condition TC et telle que n et h' aient mêmes éléments.

II.E.7) Montrer que la fonction tri_racines, appliquée à une liste de tas h 
vérifiant la condition TC, a une
complexité temporelle en O((log2 |h|)2).

II.F * Eætraction des éléments d'une liste de tas

On souhaite dans cette sous--partie récupérer une liste d'étiquettes à partir 
d'une liste de tas vérifiant les proprié--
tés précédentes. Soit h : (Noeud(æ, al, a2), t) :: h' une liste de tas non vide 
vérifiant R0 et TC. Pour supprimer cc

de h, si al et a2 ne sont pas vides, il sufit de construire h" : (insere_quasi 
a1 |a1| (insere_quasi % |a2| h')),
où |a1| et |a2| peuvent se calculer en temps constant.

II.F.1) Montrer que h" vérifie R0 et TC.

II.F.2) Donner la complexité temporelle de l'évaluation de (insere_quasi a1 
|a1| (insere_quasi a2 |a2l h'))
dans le cas le pire, sous la forme 0( f (|h|)) pour une fonction f que l'on 
précisera.

II.F.3) Écrire la fonction extraire : (arbre * int) list --> int list prenant 
en argument une liste de
tas h vérifiant les conditions BO et TC et renvoyant la liste triée des 
éléments de h en utilisant les idées ci--dessus.

2016--03-03 07:54:57 Page 5/7 @@ BY--NC-SA

II.F.4) Montrer que la fonction extraire, appliquée à une liste de tas h 
vérifiant les conditions BO et TC, a
une complexité temporelle en O(hlog2 |h|) dans le pire des cas.

II.G * Synthèse

II.G.1) Écrire la fonction tri_lisse : int list --> int list qui trie une liste 
en construisant une liste de
tas intermédiaire vérifiant R0 et TC avant d'en extraire les éléments.

II.G.2) Montrer que la complexité de cette fonction est en O(nlog2 n) où n est 
la longueur de la liste donnée
en argument.

II.G.3) Déterminer la complexité temporelle de la fonction tri_lisse dans le 
cas particulier où la liste passée
en argument est déjà triée.

III Implantation dans un tableau

On s'intéressera dans cette partie a la complexité spatiale de certaines 
fonctions. Par complexité spatiale d'une
fonction, on entend ici la quantité de mémoire dont elle a besoin pour 
s'exécuter7 la place utilisée par les données
qu'elle reçoit en argument n'étant pas prise en compte. Dit autrement, c'est la 
quantité de mémoire minimum qui
doit rester disponible sur l'ordinateur au moment de l'appel de la fonction 
pour que son exécution ne provoque
pas une erreur de capacité mémoire.

Le but de cette partie est de proposer un algorithme avec la même complexité 
temporelle que tri_lisse et une
meilleure complexité spatiale.

III .A * Justifier brièvement que la complexité spatiale de tri_1isse sur une 
liste l de longueur n est un Q(n).

Au lieu d'utiliser comme précédemment une structure d'arbres persistante, on va 
utiliser une structure impé--

rative : on représentera des arbres sous forme d'une partie d'un tableau t : si 
a est un arbre de taille k, on le

représente dans les le cases de t commençant à l'indice p comme suit :

-- si a est vide, la représentation de a ne nécessite aucune place :

-- si a est de la forme Noeud(æ, a1,a2), où (1.1 et % sont de tailles 
respectives k1 et 142, on met a: dans la case p
du tableau, puis on représente al dans les k1 cases commençant à l'indice p + 
1, puis on représente (12 dans
le tableau t dans les k2 cases commençant à l'indice ]) ---- 1 + k1 (cf. figure 
3).

a: représentation de al représentation de %
T T p++, l l
. 11 .
p p+l p+k1+1 P+k1+k2
Figure 3

Au lieu de trier une liste d'entiers, on va trier un tableau d'entiers. Ce 
tableau servira a la fois à représenter les
données initiales et les tas que nous manipulerons. Le tableau sera alors trié 
par échanges successifs.

Par la suite, tous les arbres que l'on représentera seront ou bien l'arbre 
vide, ou bien des quasi--tas (qui pourront
éventuellement être des tas). On définit le type enregistrement suivant pour 
représenter l'arbre vide ou un
quasi--tas stocké dans un tableau :

type tasbin " {donnees : int vect ; pos : int ; taille : int} ;;

Les champs donnees, pos et taille d'un tel l'enregistrement contiennent 
respectivement le tableau où sont
stockés les éléments, la position de la racine dans le tableau et le nombre 
d'éléments du quasi--tas (si ce nombre
d'éléments est nul, le tableau et la position n'ont aucune importance).

Si le tableau stocké dans le champ donnees de cet enregistrement est le tableau 
t à trier, dont la consommation
mémoire n'est pas comptée, la place mémoire prise par un élément de type tasbin 
est constante.

Par la suite, tous les éléments t: tasbin que nous manipulerons partageront le 
même tableau t.donnees
sous--jacent, qui sera le tableau à trier.

III.B * Écrire les fonctions fg: tasbin --> tasbin et fd: tasbin --> tasbin 
telles que si a représente un
quasi--tas, (fg &) et (fd a) retournent respectivement une représentation de 
son fils--gauche et son fils--droit.
Ces fonctions devront avoir une complexité constante.

III. C * Ecrire les fonctions min_tas_vect et min_quasi_vect, de type tasbin 
--> int qui prennent en argu--
ment respectivement une représentation d'un tas binaire parfait non vide et une 
représentation d'un quasi--tas
binaire et qui renvoient le minimum de leurs éléments.

III.B * Écrire la fonction percole_vect : tasbin --> unit tel que si a est un 
quasi--tas, (percole_vect &)
échange des éléments dans le tableau a.data de façon que a devienne un tas avec 
préservation de l'ensemble
des étiquettes aux répétitions près. Si a est un tas vide, (percole_vect &) ne 
fait rien.

2016--03-03 07:54:57 Page 6/7 ("à BY--NC-SA

Comme précédemment, on s'intéressera à des listes de tas. De plus, tous les 
éléments de type tasbin list
que nous manipulerons seront soit la liste vide soit des listes de la forme 
(al,...,aT) telles que pour tout
i EUR {l, ...,7' -- l}, a,.pos + a,.taille : ai+1.pos et que a,_1.pos + 
arÿl.taille : n où n est la longueur du
tableau sous--jacent. La place mémoire occupée par une liste de tas est alors 
linéaire en sa longueur (et non en
la longueur du tableau contenant ses éléments). Dans le cas où tous les 
éléments du tableau sont représentés
dans la liste de tas, on aura de plus a1.pos : O.

représentation de al représentation de (12 représentation de a,.

î ,, .*_1l l l l

0 1 a1| |a1|+|a2l--l |a1|+"'+lar=1| ""1
Figure 4

III.E = Étant donné un tableau t, on va construire un h: tasbin en parcourant t 
de droite à gauche de
la façon suivante : on démarre avec h vide et, pour k allant de n -- l a 0 
inclus, on ajoute l'élément situé à
l'indice le à h, de façon similaire a l'algorithme utilisé pour ajoute, de 
façon à garantir que la condition T C est
préservée. À la fin, tous les éléments de t sont représentés dans h. On trie 
alors h, puis on extrait successivement
le minimum de h.

Écrire la fonction aj oute_vect : int vect --> int --> tasbin --> tasbin 
analogue à la fonction ajoute pré--
cédemment définie et telle que (aj oute_vect d p h) ajoute l'élément d'indice p 
du tableau d à h. On supposera
que h est vide ou que la position du premier tas de h est p+1.

Chidéfinü;aknslafbnctku1constr_liste_tas_vect : int vect --> tasbin 
list,analogueà.constr_liste_tas,
comme suit :
(* constr_liste_tas_aux : int vect --> int --> tasbin --> tasbin
ajoute les elements du tableau d d'indice i,
pour i tasbin --> unit 
échangeant les racines des tas qui
lui sont donnés en argument.

III.G = Écrire la fonction insere_quasi_vect: tasbin --> tasbin list --> unit 
analogue de la fonction
insert_quasi.

III.H = Écrire la fonction tri_racines_vect: tasbin --> tasbin list --> unit 
analogue de la fonction
tri_racines.

III.I = Écrire la fonction extraire_vect : tasbin list --> unit analogue de la 
fonction extraire.

III.J = Écrire la fonction tri_lisse_vect : int vect --> unit triant un tableau 
en utilisant les fonctions
précédentes.

III.K = Quelle est la complexité temporelle de tri_lisse_vect dans le cas le 
pire ?
III.L = Quelle est la complexité temporelle de tri_lisse_vect pour un tableau 
déjà trié '?

III.M = Quelle est la complexité spatiale de tri_lisse_vect dans le cas le pire 
?

. o . FIN . o .

2016--03-03 07:54:57 Page 7/7 GQ BY--NC-SA

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



Centrale Informatique optionnelle MP 2016
Corrigé
Ce corrigé est proposé par Vincent Puyhaubert (Professeur en CPGE) ; il a été
relu par Benjamin Monmege (Enseignant-chercheur à l'université) et Guillaume 
Batog (Professeur en CPGE).

Cette épreuve est intégralement consacrée à l'étude et l'implémentation du tri 
lisse
(de son nom anglais smooth-sort ). Il s'agit d'un algorithme de tri 
particulièrement
efficace puisque sa complexité est quasi-linéaire dans le pire cas, tout en 
corrigeant
certains défauts du tri par tas (heap-sort ) dont il est inspiré. Il est 
notamment efficace
sur les listes partiellement triées, ce qui n'est pas le cas de la plupart des 
algorithmes
de tri classiques ; le tri rapide (quicksort), en particulier, atteint sa pire 
complexité
sur ce type de données.
Le sujet comporte trois parties.
· De manière assez originale, la première partie ne comporte aucune question !
Elle présente simplement la problématique et les notations utilisées.
· La deuxième partie constitue l'essentiel de l'épreuve. Elle permet 
l'implémentation du tri lisse en utilisant une structure extérieure sous forme 
de liste de tas
binaires parfaits. Le fonctionnement est assez similaire au tri par tas : les 
éléments à trier sont insérés les uns après les autres dans ce type de 
structure,
puis extraits un à un, cette fois dans l'ordre croissant. Puisque l'on manipule
essentiellement des listes, on utilise exclusivement la programmation récursive
et des structures de données persistantes.
L'algorithme est relativement bien présenté et l'auteur du sujet a fait preuve
d'une bonne pédagogie en faisant traiter à la main de nombreux exemples.
Les questions de complexité sont omniprésentes et deux questions demandent
une preuve de correction d'un programme.
· La troisième partie ne demande quasiment que l'écriture de codes. Il s'agit de
réécrire la totalité des fonctions de la deuxième partie en utilisant une 
nouvelle
structure extérieure moins gourmande en espace. Les données à trier sont cette
fois stockées dans un tableau, et l'on procède essentiellement par permutation
sur les éléments du tableau.
Le sujet est très bien écrit, malgré quelques petites coquilles sans importance 
dans
la dernière partie. Il a l'avantage de s'inscrire parfaitement dans l'esprit 
des nouveaux
programmes de l'option informatique en prépa en faisant manipuler des structures
de données fines. En ce sens, il est grandement conseillé de s'y intéresser.

Indications
II.A.1 Écrire une fonction récursive qui compare l'élément à insérer avec la 
tête de
la liste.
II.A.2 Procéder de manière récursive en triant la queue, puis en insérant la 
tête
dans la queue triée.
II.A.3 Examiner les cas de listes triées par ordres croissant et décroissant.
II.B.1 Justifier les égalités mk+1 = 2mk + 1 et mk = 2k - 1 pour tout entier k.
II.B.2 Il suffit de renvoyer la racine.
II.B.3 Il n'y a que trois éléments bien choisis du quasi-tas à considérer. 
Renvoyer
le plus petit des trois.
II.B.4 Dans le cas général, permuter la racine avec le plus petit de ses fils 
et lancer
un appel récursif dans le sous-arbre modifié.
II.C.1 Écrire chaque valeur à décomposer comme somme des quantités
m1 = 1

m2 = 3

m3 = 7

m4 = 15

m5 = 31

m6 = 63

II.C.2 Utiliser la relation de récurrence obtenue à la question II.B.1.
II.C.3 Implémenter directement une fonction récursive en utilisant la « 
relation de
récurrence » de la question précédente.
II.D.1.a Remarquer qu'un tas de hauteur k contient O(log2 k) éléments.
II.D.1.b Remarquer que dans une décomposition parfaite, on a nécessairement 
l'inégalité kr > r - 1, et en déduire une majoration de long(h) en fonction de
la quantité log2 |h|.
II.D.2.a Dans le premier cas, il n'y a rien à faire. Dans le second, fusionner 
les trois
premiers arbres de la liste, puis appliquer une percolation.
II.D.2.b S'inspirer de l'exemple précédent en distinguant notamment le cas où la
liste h débute par deux arbres de même taille.
Pour la preuve de la correction, utiliser la question II.C.2.
II.D.2.c Implémenter directement le pseudo-code de la question précédente.
II.D.3.a Justifier que dans le cas d'une liste triée, toutes les percolations 
sont de
coût constant.
II.D.3.b Justifier que chaque ajout est de coût O(log2 n).
II.E.2.b Faire un dessin !
II.E.3 Procéder à des permutations des racines de la gauche vers la droite 
jusqu'à
rencontrer la situation du II.E.2.a.
II.E.4 Généraliser le procédé utilisé sur les exemples.
II.E.5 Suivre l'algorithme en pseudo-code de la question précédente.
II.E.6 Procéder via insere_quasi par insertions successives des tas de h dans 
une
liste initialement vide.
II.E.7 Utiliser les résultats des questions II.E.4 et II.D.1.
II.F.1 Remarquer que insere_quasi ne modifie pas la structure des arbres insérés
et conserve RO.
II.F.2 Justifier que la complexité est un O(log2 |h|) à l'aide à nouveau des 
résultats
de la question II.1.D.

II.F.3 La question précédente décrit ce qu'il faut faire dans le cas général. 
Il reste
à étudier le cas d'un arbre réduit à la racine pour en déduire une 
implémentation par une fonction récursive.
II.F.4 Examiner le nombre d'appels récursifs effectués par la fonction de la 
question
précédente.
II.G.1 Combiner les fonctions précédentes.
II.G.2 Donner un ordre de grandeur de la somme des coûts des trois fonctions
constr_liste_tas, tri_racines et extraire.
II.G.3 Étudier soigneusement la forme de la liste de tas renvoyée par la 
fonction
constr_liste_tas lorsque la liste est triée pour justifier que tri_racines
s'exécute en coût logarithmique, et extraire en temps linéaire.
III.B Utiliser le dessin fourni par l'énoncé.
III.C Renvoyer à nouveau le minimum entre la racine du quasi-tas et ses deux 
fils,
en les récupérant « au bon endroit » dans le tableau associé.
III.D Procéder comme à la question II.B.4 en utilisant le champ taille de 
l'arbre
en argument pour savoir quand s'arrêter. On pourra implémenter la fonction
habituelle permettant de permuter deux éléments dans un tableau.
III.K Il n'est pas nécessaire de réécrire toutes les preuves. Comparer 
essentiellement les différences de coût entre les versions de la partie II et 
leurs homologues de la partie III.
III.L Justifier que les utilisations des fonctions percole_vect, ajoute_vect et
insere_quasi_vect sont à nouveau toutes de coût constant.
III.M Examiner l'occupation mémoire prise par la liste de tas h dans cette 
nouvelle
implémentation.

II. Algorithme sur des arbres
II.A.1 L'implémentation se fait naturellement par une fonction récursive.
let rec
match
[] ->
|t::q

insere x u =
u with
[x]
-> if x <= t then x::u
else t::(insere x q) ;;

II.A.2 La fonction précédente permet de procéder au tri d'une liste de manière
récursive : on trie la queue de la liste par un appel récursif, puis on insère 
la tête dans
la queue triée. Le cas d'arrêt est celui d'une liste vide qui est bien entendu 
triée.
let rec tri_insertion = function
[] -> []
|t::q -> insere t (tri_insertion q) ;;
II.A.3 Le coût d'exécution de la fonction tri_insertion, dans le meilleur comme
dans le pire cas, est le coût cumulé de toutes les insertions effectuées lors 
des appels
récursifs. Notons que insere effectue au minimum une comparaison (sauf cas 
particulier de la liste vide) et au maximum m comparaisons où m est la longueur 
de la
liste fournie en argument. On en déduit donc que
MI (n) > 0 + 1| + ·{z
· · + 1} = n - 1
n-1

et cette borne inférieure est atteinte lorsque la liste l est déjà triée. Par 
ailleurs,
n(n - 1)
2
et ce majorant est atteint lorsque la liste est triée dans l'ordre décroissant. 
Par suite,
PI (n) 6 0 + 1 + 2 + · · · + n - 1 =

MI (n) = n - 1

et PI (n) =

n(n - 1)
2

II.B.1 Procédons par récurrence sur k  N pour établir la propriété suivante :
P(k) :

« Tout arbre binaire parfait de hauteur k est de taille 2k - 1. »

L'énoncé admet implicitement que tous les arbres parfaits de hauteur k sont
de même taille, ce qui n'est pas une conséquence immédiate de la définition.
· P(0) est vraie. En effet, seul l'arbre Vide est de hauteur 0, et il est par 
définition
de taille nulle.
· P(k) = P(k + 1) : Supposons le résultat vrai pour k  N et considérons
cette fois un arbre a de hauteur k + 1. Ce n'est pas l'arbre vide, il est donc 
de
la forme Noeud(x,a1,a2) où a1 et a2 sont parfaits de même hauteur. Ainsi,
haut(a) = k + 1 = 1 + max{haut(a1), haut(a2)}
La hauteur commune de a1 et a2 vaut donc nécessairement k. L'hypothèse de
récurrence s'applique et prouve que ces deux sous-arbres sont de taille 2k - 1.
La définition même de la taille donne alors

|a| = 1 + |a1| + |a2| = 1 + 2k - 1 + 2k - 1 = 2k+1 - 1
Ainsi, P(k + 1) est vraie.