X Informatique MP 2014

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

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.