ÉCOLE POLYTECHNIQUE ' ' FILIÈRE MP
OPTION INFORMATIQUE
CONCOURS D'ADMISSION 2003
COMPOSITION D'INFORMATIQUE
(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.
On attachera une grande importance à. la clarté, a la précision et a la
concision de la rédaction.
***
Routage dans un. réseau arborescent
Dans ce problème on aborde une question soulevée dans la conception des
réseaua: : il s'agit
d'afiecter des adresses distinctes aua: noeuds d'un réseau de façon telle que
la route entre deuæ
noeuds puisse être déterminée par un calcul utilisant uniquement leurs deuoe
adresses, sans ré-
férence a une connaissance globale du réseau. On s'intéresse plus
particulièrement auoe réseauoe
ayant une forme d'arbre.
Le problème est composé de trois parties indépendantes.
Dans tout le problème un n-arbre est un arbre dont l'ensemble des sommets (on
dit aussi
parfois les noeuds) est {O, 1, . .. ,n ---- l}, et dont la racine est 0. Chaque
sommet a possède un
père noté pere[a], par convention la racine est son propre père, ainsi pere[0]
: O. L'ensemble des
n--arbres est noté A(n).
L'ensemble des ancêtres du sommet a est constitué de a et des ancêtres de son
père pere[a] ;
la racine 0 est ainsi ancêtre de tous les sommets de l'arbre. Le sous-arbre de
racine a, noté A...
est formé de tous les sommets de l'arbre A dont a est ancêtre.
Les fils d'un sommet a sont ainsi les b # 0 tels que pere[b] : a, (attention la
racine n'est pas
fils d'elle même). Une feuille est un sommet qui n'a pas de fils.
La hauteur (on dit aussi parfois profondeur) d'un sommet a, notée h(a) est un
entier égal à
0 si a est la racine, elle est égale à la hauteur du père de a augmentée de 1
sinon. Le plus proche
ancêtre commun à. deux sommets a et b, noté ppac(a, b), est le sommet de
hauteur maximale qui
est a la fois ancêtre de a et de b. Noter que si a est ancêtre de b alors
ppac(a, b) = a.
Dans tout le problème, on considère que l'entier n est fixé, d'autre part pour
un tableau t,
t[i] dénote l'élément d'indice i; une liste contenant les entiers 120, 5121, .
.. ,a:p est représentée par
(oe0,oe1, . .. ,æp); la liste vide est notée < ). On utilisera pour un n--arbre A : -- Un tableau de listes d'entiers fils de taille n tel que fils[i] est la liste des fils de z'. -- Un tableau d'entiers pere de taille n tel que pere[i] est le père de i. On a ainsi en Caml et en Pascal let n = ..... ;; const n = ...; type vint = array[0..n--1] of integer ; type vint == int vect ;; lint = "cellule; type lint == int list ;; cellule = record type vlint == lint vect ;; val : integer; suiv : lint; end; vlint = array[0..n--1] of lint; On pourra utiliser en Pascal le constructeur pour les listes qui est donné ci--dessous : function cons (contenu : integer; suivant : lint) : lint; begin var res : lint; new(res); res".val := contenu; res".suiv := suivant; cons := res; end; FIG. 1: Un arbre A E A(8) et un arbre binaire complet B E B(2). Les tableaux pere et fils de l'arbre A situé a gauche de la Figure 1 sont donnés par : I. FONCTIONS ÉLÉMENTAIRES Question 1. Calculer ppac(i, j ) pour tous les couples de sommets de l'arbre A donné plus haut. On présentera le résultat sous forme d'un tableau de 8 lignes et 8 colonnes tel que la case sur la ligne z' et la colonne j contienne le plus proche ancêtre de 71 et j . Question 2. Ecrire une fonction 1 hauteur : vint --> int --> int
function hauteur (pere : vint; a : integer) : integer
qui étant donné un sommet a d'un arbre, pour lequel on donne son tableau des
pères7 calcule la
hauteur de ce sommet.
Question 3. Ecrire une fonction
filsEnPere : vlint --> vint
procedure filsEnPere (fils : vlint; var pere : vint)
qui a partir d'un arbre, donné par ses listes de fils, calcule le tableau des
pères.
Question 4. Ecrire une fonction
ppacMemeH : vint --> int -> int --> int
function ppacMemeH (pere: vint; a, b: integer) : integer
qui calcule le plus proche ancêtre commun de deux sommets a et b supposés de
même hauteur
dans un arbre pour lequel on donne le tableau des pères.
En déduire une fonction ppac qui effectue le même calcul pour deux sommets a et
b n'ayant
pas nécessairement la même hauteur.
11. ARBRES BINAIRES COMPLETS
Un arbre binaire complet est un arbre dans lequel tout sommet qui n'est pas une
feuille
a exactement deux fils, et tel que toutes les feuilles sont a la même hauteur.
On note B(h)
l'ensemble des n-arbres binaires complets dans lesquels les feuilles sont à.
hauteur h. Un exemple
d'arbre binaire complet B est donné a droite de la Figure 1.
Question 5. Déterminer pour 0 { [EUR { h le nombre sk de sommets de hauteur lc
dans un arbre
B de B(h), justifiez votre réponse. En déduire le nombre n de sommets d'un
arbre de B(h) en
fonction de h.
Dans la suite B est un arbre de B(h) ayant n sommets; a chaque sommet a de B on
associe
une étiquette Ë(a) EUR {1,2, . .. ,n} satisfaisant la condition suivante :
pour chaque sommet & ayant pour liste de fils (b, c) :
æaÈx £(u) < Æ(a) < 52%. £(v) 1Dans tout l'énoncé du problème les déclarations de fonctions et procédures sont proposées d'abord en Caml puis en Pascal. Question 6. Calculer les valeurs de EUR(a) pour les 7 sommets de l'arbre binaire complet représenté sur la droite de la Figure 1 : l'ordre des fils dans les listes correspond à la lecture de gauche a droite de la figure. Question 7. Ecrire une fonction etiquettes : v1int --> vint
procedure etiquettes (fils : vlint; var etiq : vint)
qui calcule les étiquettes EUR(a) pour tous les sommets d'un arbre de B (h)
donné par ses listes de
fils.
Question 8. Un arbre B de B(h) de racine 0 ayant pour liste de fils (a, b) se
décompose en deux
sous--arbres Ba et Bb. Déterminer les valeurs de £(O), de EUR(a) et de £(b)
pour les fils a et b de la
racine.
Question 9. Démontrer que si a et b sont deux sommets quelconques de B alors 7°
= EUR(ppac(a, b))
est déterminé de manière unique a partir de p = EUR(a) et q = EUR(b) par la
propriété suivante :
7° est parmi les entiers compris (au sens large) entre p et q celui possédant
le plus grand diviseur
qui soit une puissance de 2.
Question 10. Donner une fonction récursive
mu : int --> int --> int
function mu (p, q : integer) : integer
qui détermine ?" = Ë(ppac(a, b)) a partir de p = EUR(a) et q = EUR(b) ; on
supposera que p { q. Votre
fonction doit être de complexité O(log2(q -- p)).
111. ARBRES GÉNÉRAUX
Dans cette partie on utilise les définitions et notations suivantes :
Dans un arbre A le poids w[a] d'un sommet a, est le nombre de sommets du
sous--arbre Aa de
racine a, ainsi w[a] = 1 si et seulement si a est une feuille, noter que w[0] =
n (c'est le nombre de
sommets
de A).
Un arbre A est dit gauche si pour chaque sommet a (qui n'est pas une feuille)
le premier
élément de la liste des fils est de poids supérieur ou égal à celui de tous les
autres sommets de
cette liste. Dans un arbre gauche, le premier élément de la liste des fils d'un
sommet est dit
lourd, les autres sommets sont dits légers. La racine est un sommet léger.
O léger . lourd
FIG. 2: Sommets lourds et légers.
Question 11. Ecrire une fonction
poids : vlint --> vint
procedure poids(fils : vlint; var poids : vint)
qui calcule les poids de tous les sommets d'un arbre donné par ses listes de
fils. Puis une fonction :
gauchir : vlint -> vint --> vlint
procedure gauchir (fils : vlint; W : vint; var filsG : vlint)
qui calcule un arbre gauche obtenu en réordonnant les fils de chaque sommet de
façon telle que
le premier fils soit de poids supérieur ou égal à celui des autres. Sont donnés
dans cette fonction
les listes des fils et le tableau des poids des sommets de l'arbre.
Question 12. Soit a un sommet léger d'un arbre gauche A et b son père, montrer
que w[b] >
2w[a]. En déduire que le nombre d'ancétres légers de a est inférieur à 1 + log2
n.
On utilise dans toute la suite la notion de cime d'un sommet.
-- Si a est léger cime[a] est égale à pere[a].
-- Si a. est lourd cime[a] est le plus proche ancêtre de a qui est léger.
Ainsi en raison de nos conventions cime[0] = 0. On appelle A' l'arbre gauche
obtenu en appli-
quant la fonction gauchir à l'arbre A de la figure 1. Les cimes des sommets de
l'arbre A' sont
alors données par le tableau suivant :
"..."
-u-uuuunn
Question 13. Ecrire une fonction
cimes : vlint --> vint
procedure cimes (fils : vlint; var cime : vint)
qui calcule les sommets cimes de tous les sommets à partir des listes de fils
d'un arbre gauche.
On se propose d'attribuer des étiquettes aux sommets d'un arbre gauche A. Pour
cela on
commence par construire deux tableaux d'entiers tl et 72 associés aux sommets.
Le tableau tl
est tel que t1[0] = 0 et t1[a] = 72 si a est le i-ème élément de la liste des
fils de son père.
Le tableau t2 est tel que t2[a] = 0 si a est léger et t2[a] = t2 [pere[a]] + 1
si a est lourd.
Les étiquettes À(a) des sommets sont alors des listes d'entiers construites de
la façon suivante :
À(O) = (> et pour a 74 0 À(a) = À(cime[a]) o (tl[a],t2[a]>
dans cette formule @ dénote la concaténation des listes.
Question 14. Donner l'arbre A' défini a la question 12; puis donner les valeurs
de t2[a] pour
tous les sommets a; calculer enfin leurs étiquettes À(a).
Question 15. Ecrire une fonction
etiquettes : vlint --> vint -> vlint
procedure etiquettes (fils : Vlint; cime : vint; var lambda : vlint)
qui calcule les étiquettes des sommets d'un arbre gauche donné par ses listes
de fils et pour
lequel on donne aussi le tableau des cimes des sommets.
En Caml on pourra utiliser l'opérateur @ et en Pascal la fonction :
function concat (x, y : lint): lint;
qui calcule laconcaténation de deux listes et dont on ne demande pas le corps.
Question 16. Ecrire une fonction :
trouve : Vlint -> lint --> int
function trouveSommet(fils : Vlint; etiq : lint): integer
qui, à partir de l'étiquette d'un sommet d'un arbre gauche A et des listes de
fils des sommets de
cet arbre, détermine ce sommet.
Question 17.
&) Montrer que, pour tout sommet a d'un arbre, la longueur de l'étiquette À(a)
est majorée
par 4 fois le nombre de ses ancêtres légers.
b) Indiquer comment on calcule À(ppac(a, b)) a partir des deux listes u = À(a)
et u = À(b) ;
on ne demande pas de justifier la réponse a cette question.
On a donné dans ce problème une technique permettant d'étiqueter les noeuds des
sommets d'un
réseau qui a une forme d'arbre. Dans cet étiquetage la recherche du plus proche
ancêtre commun
de deuæ sommets (et donc de la route qui les relie} s'efiectue uniquement à
l'aide de leurs
étiquettes. Des techniques plus compleoees, qui généralisent les techniques
données ici, utilisent
des étiquettes de taille O(log2 n) bits qui permettent aussi un calcul du plus
proche ancêtre
commun en O(l) opérations.