X Informatique MP 2014

ÉCOLE POLYTECHNIQUE -- ÉCOLES NORMALES SUPÉRIEURES

CONCOURS D'ADMISSION 2014 FILIÈRE MP SPÉCIALITÉ INFO

COMPOSITION D'INFORMATIQUE -- A -- (XULCR)

(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.

***

Arbres croissants

On étudie dans ce problème la structure d'arbre croissant, une structure de 
données pour
réaliser des files de priorité.

La partie I introduit la notion d'arbre croissant et la partie Il les 
opérations élémentaires sur
les arbres croissants. L'objet de la partie III est l'analyse des performances 
de ces opérations.
Enfin la partie IV applique la structure d'arbre croissant, notamment au 
problème du tri.

Les parties peuvent être traitées indépendamment. Néanmoins, chaque partie 
utilise des
notations et des fonctions introduites dans les parties précédentes. Les 
tableaux sont indexés a
partir de O, indépendamment du langage de programmation choisi. On note log(n) 
le logarithme
a base 2 de n.

Arbres binaires. Dans ce problème, on considère des arbres binaires. Un arbre 
est soit l'arbre
vide, noté E, soit un noeud constitué d'un sous-arbre gauche g, d'un entier a: 
et d'un sous-arbre
droit d, noté N(g, a:, d). La taille d'un arbre t, notée ltl, est définie 
récursivement de la manière
suivante :
W = 1
lN(gaaæd)l = 1 + M + M-

La hauteur d'un arbre t, notée h(t), est définie récursivement de la manière 
suivante :

h(E) : O
h(N(g,oe,d)) : 1 + max(h(g), h(d)).

Le nombre d'occurrences d'un entier y dans un arbre t, noté occ(y, t), est 
défini récursivement
de la manière suivante :

occ(y, E) = O
OCC(y. N(9. az d)) = 1 + OCC(yag) + OCC(% d) si y = a?
occ(y, N(g, a:, d)) : occ(y,g) + occ(y, d) sinon.

L'ensemble des éléments d'un arbre t est l'ensemble des entiers y pour lesquels 
occ(y, t) > 0.

Par la suite, on s'autorisera a dessiner les arbres de la manière usuelle. 
Ainsi l'arbre
N(N(E, 2, E), 1, E) pourra être dessiné sous la forme

On se donne le type arbre suivant pour représenter les arbres binaires.

(* Caml *) { Pascal }
type arbre = type arbre = "noeud;
E | N of arbre * int * arbre;; noeud = record gauche: arbre;

element: integer; droit: arbre; end;

En Pascal, l'arbre vide est la constante const E: arbre = nil et on suppose 
donnée une
fonction function N(g: arbre; X: integer; d: arbre) : arbre; pour construire le 
noeud

N(a X, d)-

Partie I. Structure d'arbre croissant

On dit qu'un arbre t est un arbre croissant si, soit 15 = E, soit 15 : N(g,a:, 
d) où g et d sont
eux--mêmes deux arbres croissants et a: est inférieur ou égal a tous les 
éléments de g et d. Ainsi
les arbres

1
/ \
1 3 2
/ \ / \ / \
2 4 et 3
/ \ / \ / \
sont des arbres croissants mais les arbres 1
/ \
4 3 4
/ \ / \ / \
3 5 et 2
/ \ / \ / \

n'en sont pas

Question 1 Ecrire une fonction minimum qui prend en argument un arbre croissant 
15, en
supposant t # E, et renvoie son plus petit élément.

(* Caml *) minimum: arbre --> int
{ Pascal } function minimum(t: arbre) : integer;

Question 2 Ecrire une fonction est.un-arbre-croissant qui prend en argument un 
arbre t
et détermine s'il a la structure d'arbre croissant. On garantira une complexité 
O(\t\).

(* Caml *) est.un_arbre_croissant: arbre --> bool
{ Pascal } function est.un-arbre-croissant(t: arbre) : boolean;

Question 3 Montrer qu'il y a exactement n! arbres croissants possédant n noeuds 
étiquetés
par les entiers 1, . . . ,n (chaque noeud étant étiqueté par un entier 
distinct).

Partie II. Opérations sur les arbres croissants

L'opération de fusion de deux arbres croissants t1 et @, notée fusion(t1, É2), 
est définie par
récurrence de la manière suivante :

: t1

: 152

= N(fusion(d1, N(QQ,ÇC2, d2)),561,ÿ1) 81561 S 5172
: N(fusion(dg, N(Q1,OE1,d1)),OE2,Qg) sinon.

fusion(t1, E
fusion(E, @
ÎUSiOH(N(91,OE1,di)7 N(927OE2,d2)
ÎUSiOH(N(91,OE1,di)7 N(927OE2,d2)

VVVV

Note importante : dans la troisième (resp. la quatrième) ligne de cette 
définition, on a sciemment
échangé les sous--arbres g1 et d1 (resp. g2 et dg). Dans les parties III et IV 
de ce problème
apparaîtront les avantages de la fusion telle que réalisée ci--dessus (d'autres 
façons de réaliser la
fusion n'auraient pas nécessairement de telles propriétés).

1 3
/ \ / \
Question 4 Donner le résultat de la fusion des arbres croissants 2 4 et 5 6 .
/ \ / \ / \ / \

Question 5 Soit 15 le résultat de la fusion de deux arbres croissants t1 et @. 
Montrer que t
possède la structure d'arbre croissant et que, pour tout entier a:, occ(oe, t) 
: occ(oe, t1)+ occ(oe, É2).

Question 6 Déduire de l'opération fusion une fonction ajoute qui prend en 
arguments un
entier a: et un arbre croissant 15 et renvoie un arbre croissant t' tel que 
occ(oe, t' ) = 1 + occ(oe, t)
et occ(y,t') : occ(y,t) pour tout y # a:.

(* Caml *) ajoute: int --> arbre --> arbre
{ Pascal } function ajoute(x: integer; t: arbre) : arbre;

Question 7 Déduire de l'opération fusion une fonction supprime.minimum qui 
prend en ar--
gument un arbre croissant 15, en supposant t # E, et renvoie un arbre croissant 
t' tel que, si m
désigne le plus petit élément de t, on a occ(m,t') : occ(m,t) -- 1 et occ(y,t') 
: occ(y,t) pour
tout y # m.

(* Caml *) supprime.minimum: arbre --> arbre
{ Pascal } function supprime.minimum(t: arbre) : arbre;

Question 8 Soient 550, . . . ,a:n_1 des entiers et 15... . . . ,tn les n+1 
arbres croissants définis par 150 =
E et ti+1 : fusion(ti7 N(E,oei,E)) pour 0 S 75 < n. Ecrire une fonction aj outs-successifs qui prend en argument un tableau contenant les entiers 560, . . . ,a:n_1 et qui renvoie l'arbre croissant tn. (* Caml *) ajouts-successifsz int vect --> arbre
{ Pascal } function ajouts-successifs(xz array[O...n--l] of integer) : arbre;

Question 9 Avec les notations de la question précédente, donner, pour tout n, 
des valeurs
550, . . . ,a:n_1 qui conduisent a un arbre croissant tn de hauteur au moins 
égale a n / 2.

Question 10 Toujours avec les notations de la question 8, donner la hauteur de 
l'arbre tn obtenu
a partir de la séquence d'entiers 1, 2, . . . ,n, c'est--à--dire 55,- = 75 + 1. 
On justifiera soigneusement
la réponse.

Partie III. Analyse

On dit qu'un noeud N(g,oe,d) est lourd si \g\ < \d\ et qu'il est léger sinon. On définit le potentiel d'un arbre t, noté (t), comme le nombre total de noeuds lourds 
qu'il contient.

Question 11 Écrire une fonction potentiel qui prend en argument un arbre t et 
renvoie (t),
tout en garantissant une complexité O(\t\).

(* Caml *) potentiel: arbre --> int
{ Pascal } function potentiel(t: arbre) : integer;

On définit le coût de la fusion des arbres croissants t1 et @, noté C(t1, 152), 
comme le nombre
d'appels récursifs a la fonction fusion effectués pendant le calcul de 
fusion(t1, 152). En parti--
culier, on a C(t,E) : C(E,t) : 0.

Question 12 Soient t1 et 152 deux arbres croissants et t le résultat de 
fusion(t1, t2). Montrer
que
C(É1,É2) £ <Ï)(É1) + <Ï)(É2) _ <Ï)(É) + 2(108l751l +108lt2l)- (1) Question 13 Soient 550, . . . ,a:n_1 des entiers et 150, . . . ,tn les n + 1 arbres croissants définis par 150 = E et ti+1 : fusion(t,, N(E,oe,,E)) pour 0 £ 75 < n. Montrer que le coût total de cette construction est en O(nlog(n)). Question 14 Montrer que, dans la construction de la question précédente, une des opérations fusion peut avoir un coût au moins égal a n / 2 (on exhibera des valeurs 550, . . . ,a:n_1 le mettant en évidence). Justifier alors la notion de complexité amortie logarithmique pour la fusion de deux arbres croissants. Question 15 Soit 150 un arbre croissant contenant n noeuds, c'est--à--dire de taille 271 + 1. On construit alors les n arbres croissants t1, . . . ,tn par t,-+1 : fusion(g,, d,) où 15,- : N(g,,oe,, d,), pour 0 £ 75 < n. En particulier, on a tn : E. Montrer que le coût total de cette construction est en O(n log(n)). Partie IV. Applications Question 16 En utilisant la structure d'arbre croissant, écrire une fonction tri qui trie un tableau a de n entiers, dans l'ordre croissant, en temps O(n log(n)). Ainsi, si le tableau a contient initialement [3; 2; 7 ; 2; 4], il devra contenir [2; 2; 3; 4; 7] après l'appel a la fonction tri. La fonction tri pourra allouer autant de structures intermédiaires que nécessaire, en particulier des arbres croissants. On justifiera soigneusement la complexité. (* Caml *) tri: int vect --> unit
{ Pascal } procedure tri(a: array[O..n--1] of integer);

_ Soient 550, . . . ,a:n_1 des entiers, avec n = 275 et lt 2 0. On définit une 
famille d'arbres croissants
tg, avec 0 S i S lEUR et 0 £ j < 2k_', de la façon suivante : t{, = N(E,æ,--,E) pour 0 5j < 21", t? Z+1 : fusion(t2j, tÎj+1) pour 0 S i < lEUR et 0 Sj < 2k--i--1_ i Question 17 Montrer que le coût total de la construction de tous les arbres croissants tg est en O(2'""). Question 18 En déduire une fonction construire qui prend en argument un tableau a de taille n, avec n = 275 et lt 2 O, et renvoie un arbre croissant contenant les éléments de a en temps O(n). (* Caml *) construire: int vect --> arbre
{ Pascal } function construire(a: array[O..n--1] of integer) : arbre;

Question 19 Comment relâcher la contrainte n = 275 pour traiter le cas d'un 
nombre quelconque
d'éléments, toujours en temps O(n) ? Donner le programme correspondant.

Note : Ces tas auto-équilibrés sont appelés << skew heaps >> en anglais. Outre 
leur
caractère persistant, ils offrent l'une des solutions les plus simples pour 
obtenir un
tri de oompleoeite' optimale.