X Informatique MP 2014

Thème de l'épreuve Arbres croissants
Principaux outils utilisés arbres binaires, programmation récursive, complexité amortie

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


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

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



X Informatique MP 2014 -- Corrigé
Ce corrigé est proposé par Benjamin Monmege (ENS Cachan) ; il a été relu par
Charles-Pierre Astolfi (ENS Cachan) et Guillaume Batog (Professeur en CPGE).

Ce problème étudie les arbres croissants, ou tas auto-équilibrés (skew heaps en
anglais). Cette structure de données permet une implémentation efficace des 
files de
priorité. Le sujet est composé de 4 parties.
· La partie I permet de se familiariser avec cette nouvelle structure de 
données,
en testant si un arbre binaire est croissant et en dénombrant les arbres 
croissants
d'une taille donnée.
· La structure d'arbre croissant doit son efficacité à une opération spéciale de
fusion de deux arbres croissants, étudiée dans la partie II. Le sujet propose
de montrer qu'une telle fusion produit un arbre croissant. On utilise ensuite
cette opération pour implémenter d'autres opérations, telles que la suppression
du minimum d'un arbre et la construction itérative d'arbres croissants 
contenant une séquence d'entiers fournie. Cette construction itérative est 
également
étudiée sur des exemples.
· La partie III propose d'analyser la complexité amortie, ainsi que la 
complexité
dans le pire cas, de l'opération de fusion. Le sujet emploie une méthode à base
de potentiel pour montrer que la complexité amortie de la fusion est 
logarithmique. En particulier, cela permet de prouver que la construction 
itérative de
la partie II a une complexité en O(n log2 n).
· Enfin, la partie IV s'intéresse à deux applications des arbres croissants. La 
première consiste en une fonction de tri en temps O(n log2 n). La seconde 
propose
la construction en temps linéaire d'un arbre croissant contenant un ensemble
donné d'entiers, améliorant ainsi la construction itérative de la partie II.
Les parties sont indépendantes, même si chacune utilise des notations 
introduites
dans les parties précédentes. Il s'agit d'un sujet principalement centré sur 
l'étude
d'arbres binaires, de facture assez classique pour l'X. De nombreuses questions 
de programmation assez faciles sont ponctuées par des études d'exemples et des 
questions
parfois délicates d'analyse de complexité. L'étude de complexité amortie est 
une spécificité intéressante de ce sujet, puisque celle-ci n'est que peu 
abordée dans les sujets
de concours. Elle entraîne des questions calculatoires assez difficiles, en 
particulier
la question 12. Les questions 9 et 14, demandant d'exhiber des exemples 
pathologiques d'arbres croissants, peuvent également s'avérer difficiles en 
temps limité.
Enfin, la question 10, qui demande une justification soigneuse, est la plus 
difficile
du sujet.

Indications
Partie I
2 Implémenter une fonction récursive utilisant la fonction minimum de la 
question 1.
3 Montrer par récurrence sur n que l'ensemble A{1,...,n} des arbres croissants 
à n
noeuds étiquetés par {1, . . . , n} est de cardinal n!. Pour prouver 
l'hérédité, utiliser
de manière plus générale l'ensemble AF des arbres croissants dont les m noeuds
sont étiquetés par les m éléments d'un ensemble F. Pour un arbre t  
A{1,...,n+1} ,
décomposer alors l'ensemble {2, . . . , n + 1} en l'union disjointe F  F avec F
l'ensemble des étiquettes des noeuds du sous-arbre gauche de t.
Partie II
5 Montrer la propriété par récurrence sur n = |t1 | + |t2 |. Utiliser le fait 
que pour
tout arbre t = N(g, x, d), l'étiquette x de la racine est inférieure à tous les 
éléments
de g et d si et seulement si occ(y, t) = 0 pour tout entier y < x.
9 Montrer que la séquence x0 = n, x1 = n - 1, . . . , xn-1 = 1 conduit à un 
arbre tn
de hauteur n.
10 Commencer par construire les arbres tn pour n 6 8. Conjecturer alors la 
hauteur
de l'arbre tn . Pour prouver la conjecture, remarquer que les sous-arbres gauche
et droit de tn sont reliés aux arbres tn/2 et tn/2-1 .
Partie III
11 Pour garantir la complexité linéaire, utiliser une fonction auxiliaire qui 
associe à
un arbre t le couple ((t), |t|).
12 Montrer la propriété par récurrence forte sur n = |t1 | + |t2 |. Utiliser le 
fait que
si la racine de t1 est un noeud lourd alors la racine de t est un noeud léger.
13 Utiliser la question 12.
14 Pour un entier n = 2k, commencer par étudier l'arbre produit par l'ajout 
successif
des entiers x0 = k, x1 = k - 1, x2 = k + 1, x3 = k - 2, x4 = k + 1, . . . , 
x2k-3 = 1,
x2k-2 = k + 1. Trouver ensuite un élément x2k-1 dont l'ajout a un coût k = n/2.
15 Utiliser la question 12 et le fait que le potentiel d'un arbre t = N(g, x, 
d) vérifie
(t) > (g) + (d).
Partie IV
16 Utiliser la fonction ajouts_successifs de la question 8, ainsi que les 
fonctions
minimum de la question 1, et supprime_minimum de la question 7. Pour prouver
la complexité, utiliser les résultats des questions 13 et 15.
17 Utiliser la formule de la question 12. Montrer alors que la partie faisant 
intervenir
la fonction de potentiel est négative. Montrer finalement que la partie faisant
intervenir les logarithmes est en O(2k ), en vérifiant dans un premier temps que
log2 |tji | 6 i + 2.
18 Justifier qu'il s'agit de calculer l'arbre t0k .
19 Supposer que 2k-1 < n 6 2k et modifier la définition de tj0 en ajoutant des
arbres E lorsque n 6 j < 2k . Changer la fonction de la question 18 pour 
refléter
ce changement.

I. Structure d'arbres croissants
1 Par définition d'un arbre croissant, le plus petit élément d'un arbre 
croissant se
situe à sa racine. Ainsi, lorsque l'arbre est de la forme N(g, x, d), il s'agit 
de l'entier x.
let minimum t =
match t with
N(_,x,_) -> x;;
2 Vérifions par une fonction récursive si un arbre est croissant, en suivant la 
définition. En effet, afin de tester si un arbre non vide N(g, x, d) est 
croissant, il suffit de
vérifier que les sous-arbres g et d sont eux-mêmes croissants, puis que 
l'entier x est
inférieur ou égal à tous les éléments de g et d. Notons que l'entier x est 
inférieur ou
égal au minimum d'un arbre t si et seulement si soit t est vide, soit t est non 
vide
et x est inférieur ou égal au minimum de t. L'évaluation paresseuse des 
opérateurs
booléens en Caml est utilisée afin de tester d'abord si les sous-arbres g et/ou 
d sont
vides, et sinon appliquer la fonction minimum de la question 1.
let rec est_un_abre_croissant t =
match t with
E -> true
| N(g,x,d) ->
(est_un_abre_croissant g) && ((g = E) || (x <= minimum g))
&& (est_un_abre_croissant d) && ((d = E) || (x <= minimum d));;
Puisqu'un nombre borné d'opérations est réalisé à chaque noeud de l'arbre et que
chaque noeud est visité au plus une fois, la fonction a une complexité linéaire 
en la
taille de l'arbre en argument.
est_un_arbre_croissant s'exécute sur un arbre t en une complexité O(|t|).

Montrons précisément que cette fonction s'exécute en temps O(|t|). Notons Cn le 
nombre d'opérations élémentaires exécutées lors de l'appel
est_un_arbre_croissant t pour un arbre t de taille |t| = n. Lorsque n = 1,
t = E et la fonction retourne true sans calculs intermédiaires. Ainsi C1 = 0.
Lorsque n > 1, si t = N(g, x, d), en supplément des deux appels récursifs sur
les arbres g et d, au plus un nombre  constant d'opérations élémentaires
est réalisé : en particulier, notons que la fonction minimum s'exécute en temps
constant. Par conséquent, Cn 6 C|g| + C|d| + . En développant l'inégalité
de récurrence, on obtient que Cn est majoré par la somme des coûts des
opérations élémentaires réalisées sur chaque noeud N(g, x, d) de l'arbre et sur
les arbres vides E (coût nul), d'où Cn 6  × n.
3 Notons Tn le nombre d'arbres croissants possédant n noeuds étiquetés par les 
entiers 1, . . . , n. Commençons par établir une relation de récurrence sur la 
suite (Tn )n>1 .
Notons dans un premier temps qu'il existe un unique arbre possédant un noeud 
étiqueté par 1, donc T1 = 1.

Considérons ensuite l'ensemble A{1,...,n+1} des arbres croissants possédant n + 
1
noeuds étiquetés par les entiers 1, . . . , n + 1. Tout arbre t  A{1,...,n+1} 
est nécessairement non vide. Notons alors t = N(g, x, d). Puisque t est un 
arbre croissant, x = 1
et g et d sont des arbres croissants. Notons alors F l'ensemble des étiquettes 
des
noeuds de g : F est un sous-ensemble de {2, . . . , n + 1}. Son complémentaire 
F dans
{2, . . . , n + 1} est l'ensemble des étiquettes des noeuds de d. Pour un 
ensemble G quelconque à m noeuds, notons AG l'ensemble des arbres croissants 
possédant m noeuds
étiquetés par les entiers de G. Ainsi A{1,...,n+1} est en bijection avec 
l'ensemble
S
AF × AF
F{2,...,n+1}

Notons que le cardinal de l'ensemble AG ne dépend que du cardinal m de G,
puisqu'un renommage des étiquettes par une bijection croissante permet de 
supposer, sans perte de généralité, que G = {1, . . . , m}. Ainsi, AG est de 
cardinal Tm.
n
Le nombre de sous-ensemble F de cardinal m de {2, . . . , n + 1} est donné par m
.
En utilisant également que F est de cardinal n - m, la bijection précédente 
permet
donc d'obtenir la relation de récurrence suivante :
n
X

n
pour tout n > 1
Tn+1 =
m × Tm × Tn-m
m=0

Montrons alors par récurrence sur n > 1 que Tn = n! est l'unique suite 
satisfaisant
l'équation de récurrence précédente. Pour n = 1, T1 = 1 = 1! convient. Pour n > 
1,
si Tm = m! pour tout m 6 n, on obtient
Tn+1 =

n
X

n
X
n!
× m! × (n - m)! =
n! = (n + 1)!
m! × (n - m)!
m=0
m=0

Il y a exactement n! arbres croissants possédant
n noeuds étiquetés par les entiers 1, . . . , n.