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 II 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 à partir de 0 , indépendamment du langage de programmation choisi. On note le logarithme à base 2 de .
Arbres binaires. Dans ce problème, on considère des arbres binaires. Un arbre est soit l'arbre vide, noté E, soit un nœud constitué d'un sous-arbre gauche , d'un entier et d'un sous-arbre droit , noté . La taille d'un arbre , notée , est définie récursivement de la manière suivante :
La hauteur d'un arbre , notée , est définie récursivement de la manière suivante :
Le nombre d'occurrences d'un entier dans un arbre , noté , est défini récursivement de la manière suivante :
L'ensemble des éléments d'un arbre est l'ensemble des entiers pour lesquels occ .
Par la suite, on s'autorisera à dessiner les arbres de la manière usuelle. Ainsi l'arbre 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 I 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 : arbre; : integer; : arbre) : arbre; pour construire le nœud .
Partie I. Structure d'arbre croissant
On dit qu'un arbre est un arbre croissant si, soit , soit où et sont eux-mêmes deux arbres croissants et est inférieur ou égal à tous les éléments de et . Ainsi les arbres
sont des arbres croissants mais les arbres
et
n'en sont pas.
Question 1 Écrire une fonction minimum qui prend en argument un arbre croissant , en supposant , et renvoie son plus petit élément.
(* Caml *) minimum: arbre -> int
{ Pascal } function minimum(t: arbre) : integer;
Question 2 Écrire une fonction est_un_arbre_croissant qui prend en argument un arbre et détermine s'il a la structure d'arbre croissant. On garantira une complexité .
Question 3 Montrer qu'il y a exactement ! arbres croissants possédant nœuds étiquetés par les entiers (chaque nœud étant étiqueté par un entier distinct).
Partie II. Opérations sur les arbres croissants
L'opération de fusion de deux arbres croissants et , notée fusion , est définie par récurrence de la manière suivante :
Note importante : dans la troisième (resp. la quatrième) ligne de cette définition, on a sciemment échangé les sous-arbres et (resp. et ). 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).
Question 4 Donner le résultat de la fusion des arbres croissants
Question 5 Soit le résultat de la fusion de deux arbres croissants et . Montrer que possède la structure d'arbre croissant et que, pour tout entier .
Question 6 Déduire de l'opération fusion une fonction ajoute qui prend en arguments un entier et un arbre croissant et renvoie un arbre croissant tel que et pour tout .
(* 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 argument un arbre croissant , en supposant , et renvoie un arbre croissant tel que, si désigne le plus petit élément de , on a et pour tout .
(* Caml *) supprime_minimum: arbre -> arbre
{ Pascal } function supprime_minimum( t : arbre) : arbre;
Question 8 Soient des entiers et les arbres croissants définis par E et pour . Écrire une fonction ajouts_successifs qui
prend en argument un tableau contenant les entiers et qui renvoie l'arbre croissant .
(* Caml *) ajouts_successifs: int vect -> arbre
{ Pascal } function ajouts_successifs( x : array[0.. ] of integer) : arbre;
Question 9 Avec les notations de la question précédente, donner, pour tout , des valeurs qui conduisent à un arbre croissant de hauteur au moins égale à .
Question 10 Toujours avec les notations de la question 8, donner la hauteur de l'arbre obtenu à partir de la séquence d'entiers , c'est-à-dire . On justifiera soigneusement la réponse.
Partie III. Analyse
On dit qu'un nœud est lourd si et qu'il est léger sinon. On définit le potentiel d'un arbre , noté , comme le nombre total de nœuds lourds qu'il contient.
Question 11 Écrire une fonction potentiel qui prend en argument un arbre et renvoie , tout en garantissant une complexité .
(* Caml *) potentiel: arbre -> int
{ Pascal } function potentiel(t: arbre) : integer;
On définit le coût de la fusion des arbres croissants et , noté , comme le nombre d'appels récursifs à la fonction fusion effectués pendant le calcul de fusion . En particulier, on a .
Question 12 Soient et deux arbres croissants et le résultat de fusion . Montrer que
Question 13 Soient des entiers et les arbres croissants définis par et pour . Montrer que le coût total de cette construction est en .
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 à (on exhibera des valeurs le mettant en évidence). Justifier alors la notion de complexité amortie logarithmique pour la fusion de deux arbres croissants.
Question 15 Soit un arbre croissant contenant nœuds, c'est-à-dire de taille . On construit alors les arbres croissants par où , pour . En particulier, on a . Montrer que le coût total de cette construction est en .
Partie IV. Applications
Question 16 En utilisant la structure d'arbre croissant, écrire une fonction tri qui trie un tableau a de entiers, dans l'ordre croissant, en temps . Ainsi, si le tableau a contient initialement , il devra contenir après l'appel à 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[0..n-1] of integer);
Soient des entiers, avec et . On définit une famille d'arbres croissants , avec et , de la façon suivante :
Question 17 Montrer que le coût total de la construction de tous les arbres croissants est en .
Question 18 En déduire une fonction construire qui prend en argument un tableau a de taille , avec et , et renvoie un arbre croissant contenant les éléments de a en temps .
(* Caml *) construire: int vect -> arbre
{ Pascal } function construire(a: array[0..n-1] of integer) : arbre;
Question 19 Comment relâcher la contrainte pour traiter le cas d'un nombre quelconque d'éléments, toujours en temps ? 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 complexité optimale.
X ENS Option Informatique MP 2014 - Version Web LaTeX | WikiPrépa | WikiPrépa
