X Informatique MP 2003

Thème de l'épreuve Optimisation du routage dans un réseau arborescent
Principaux outils utilisés parcours d'arbre, récursivité
Mots clefs étiquette, ppac

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

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



X Informatique MP 2003 -- Corrigé
Ce corrigé est proposé par Jean-Baptiste Rouquier (ENS Lyon) ; il a été relu par
Samuel Mimram (ENS Lyon) et Vincent Puyhaubert (Professeur en CPGE).

Il y a beaucoup de code à écrire dans ce problème, qui ne nécessite que peu de
connaissances de cours. Il propose de manipuler les arbres (notamment les 
manières
de les parcourir), et fait intervenir de nombreuses récurrences. Certaines 
questions
théoriques, comme la question 9, sont difficiles.
· La première partie consiste en l'écriture de quelques fonctions simples sur 
les
arbres : hauteur d'un sommet, conversion entre deux représentations d'un arbre
et plus proche ancêtre commun, notion définie dans l'énoncé.
· La deuxième travaille sur les arbres binaires complets. Elle propose un 
étiquetage des sommets permettant de calculer rapidement le plus proche ancêtre
commun de deux sommets en n'utilisant que leurs étiquettes.
· La troisième fait la même étude sur les arbres généraux et définit pour cela 
les
notions d'arbre gauche et de cime.
Ce sujet est une bonne préparation aux concours, à condition de tester ses 
fonctions pour qui ne maîtrise pas encore Caml. En effet, c'est principalement 
l'algorithme
qui est pris en compte par le correcteur, mais trop d'erreurs de syntaxe peuvent
agacer. Comme souvent, la difficulté est progressive au sein de chaque partie, 
même
si l'alternance de questions théoriques et des fonctions à implanter peut 
modifier la
difficulté perçue. Il ne faut donc pas hésiter à passer à la partie suivante, 
quitte à
revenir sur les dernières questions d'une partie.
Les concepts étudiés dans ce problème servent surtout de support pour faire
des exercices et ne sont pas très généraux. On retiendra de ce sujet les 
techniques
mises en oeuvre (en particulier les parcours d'arbre et les récurrences) et le 
style de
programmation.

Indications
2 Traduire la définition de la hauteur en Caml, en utilisant un filtrage.
3 Pour chaque sommet, chercher les sommets dont il est le père.
4 Pour ppacMemeH, que peut-on dire des pères des deux arguments ?
5 Deviner une formule simple sur de petits exemples et la montrer par 
récurrence.
Les puissances de 2 ne sont pas loin. . .
6 Étiqueter d'abord un arbre binaire à trois sommets pour voir comment ça
marche.
7 Cette fois, un parcours en profondeur est utile. Préfixe, infixe ou postfixe ?
8 S'inspirer de la question précédente ; une récurrence n'est pas indispensable.
Pour (a), quel est l'ensemble des étiquettes de Ba ? Idem pour Bb .
Indication supplémentaire : penser également à la médiane.
9 Procéder en plusieurs étapes :
· Montrer que r  [[ p ; q ]].
· Soit g le plus proche ancêtre commun de a et b. Remarquer que tout
sommet f tel que h(f ) 6 h(g) vérifie (f ) 6 [[ p ; q ]]. Utiliser la question 7
et raisonner par l'absurde.
· Prouver que
c, d
h(c) > h(d)  val 2 ((c)) < val 2 ((d))
val 2 ((c)) est la valuation en 2, c'est-à-dire l'exposant de 2 dans la 
décomposition en facteurs premiers de (c). Utiliser la question 8 et faire une
récurrence sur la hauteur de l'arbre.
· Conclure.
10 Utiliser la question 9 et oublier la représentation arborescente.
Distinguer le cas p = q. Pour l'autre cas, ne considérer que les nombres pairs 
de
[[ p ; q ]] (à justifier) et écrire une fonction récursive.
12 Première question : s'inspirer de la fonction poids de la question 11.
Seconde question : faire une récurrence sur le nombre d'ancêtres légers du 
sommet qui en a le plus.
13 Faire un parcours en profondeur en donnant comme argument à la fonction
récursive le plus proche ancêtre léger.
Indication supplémentaire : le traitement d'un sommet consiste à calculer la
cime de ses fils (et non la sienne).
15 Encore un parcours d'arbre. La principale difficulté est de s'assurer que
(cime[a]) est calculée lorsque l'on arrive au calcul de (a).
16 Descendre l'arbre en choisissant le bon fils d'après les couples (t1(a), 
t2(a)).
On peut descendre plusieurs étages en une fois.
17.a Étudier, dans l'ordre de profondeur croissante, la nature des sommets b 
tels que
le couple (t1(b), t2(b)) fasse partie de (a), en particulier leurs liens de 
parenté
et leur poids.
17.b S'inspirer de la fonction trouveSommet de la question précédente : 
descendre
l'arbre et s'arrêter sur le plus proche ancêtre commun.

L'énoncé commence par plusieurs notations, rappels et définitions de
concepts nouveaux. Ces derniers sont utiles dès la première question, qui vise
à vérifier leur compréhension. D'autres éléments sont introduits au début des
parties suivantes. Certains autres sujets introduisent au contraire tous les
nouveaux objets dont ils ont besoin au début ; il est alors bon de ne pas
perdre de temps sur ces définitions pour n'y revenir que lorsque l'on aborde
les question qui les utilisent.
La définition des types vint, lint et vlint est assez étrange, elle n'apporte 
aucune information et ne sert apparemment qu'à économiser un peu
d'encre. Toute variable de type vlint sera ici la représentation d'un arbre
par ses listes de fils (sauf une fois) ; on aurait donc pu choisir un nom de 
type
plus explicite (comme arbre). Mais il faut bien sûr se conformer à l'énoncé
pour ne pas agacer le correcteur.
C'est une erreur de syntaxe en Caml de faire commencer le nom d'une
fonction par une majuscule. Il est donc recommandé par les concepteurs
du langage eux-mêmes de séparer les mots par des soulignés (exemple :
fils_en_pere) au lieu de majuscules (filsEnPere) comme le fait le sujet.
Les fonctions comme do_list ou map_vect sont expliquées dans le manuel Caml 
(rubrique « the core library ») disponible sur caml.inria.fr, ou
en téléchargement sur ftp.inria.fr/INRIA/caml-light. Si vous avez installé Caml 
sous Windows par le programme cl74win.exe, ce dernier doit avoir
créé un manuel dont le nom est proche de « cl74refman ». Ces fonctions sont
très utiles et map doit absolument être maîtrisée. Elles sont également 
présentées à la fin de ce corrigé.

I. Fonctions élémentaires
1 Quelques remarques permettent de remplir une bonne partie du tableau :
· Le tableau est symétrique car ppac(a, b) = ppac(b, a) pour tous a, b ;
· pour tout a, ppac(0, a) = 0 car le seul ancêtre de la racine est 0 ;
· pour tout a, ppac(a, a) = a.
Le reste se fait en appliquant la définition du plus proche ancêtre commun.
0
1
2
3
4
5
6
7

0
0
0
0
0
0
0
0
0

1
0
1
4
0
4
4
0
0

2
0
4
2
0
4
2
0
0

3
0
0
0
3
0
0
0
0

4
0
4
4
0
4
4
0
0

5
0
4
2
0
4
5
0
0

6
0
0
0
0
0
0
6
6

7
0
0
0
0
0
0
6
7

Cette question sert, comme dans beaucoup d'autres sujets, à rassurer le
candidat en lui faisant manipuler les concepts qui viennent d'être introduits.

Pour faire un peu de gymnastique et continuer à manipuler ces concepts,
on peut voir ppac(a, b) comme la racine du plus petit sous-arbre contenant
a et b.
Une session Caml à la fin de ce corrigé montre comment calculer automatiquement 
ce tableau ; c'est d'ailleurs ce qui a été fait ici.
2 Appliquons la définition de la hauteur :
(
0
si a est la racine
h(a) =
1 + h(pere[a]) sinon
ce qui se traduit par :
let rec hauteur pere = function
| 0 -> 0
| a -> 1 + hauteur pere pere.(a)
;;
3 Commençons par une évidence : a est le fils de b si et seulement si b est le 
père
de a. Il suffit donc, pour chaque sommet, de le « déclarer » comme père de ses 
fils.
Précisément, on crée le tableau peres, qui sera renvoyé. Puis on définit la 
fonction
declare_pere qui prend un sommet et parcourt la liste de ses fils. Pour chaque 
fils,
elle écrit qui est son père dans le résultat. On l'applique alors à tous les 
sommets.
Il faut enfin régler le cas de la racine, la convention étant ici qu'elle a un 
père.
let filsEnPere fils =
let n = vect_length fils in
let peres = make_vect n (-1) in
let declare_pere p =
do_list (fun son -> peres.(son) <- p) fils.(p)
in
for p=0 to n-1 do
declare_pere p
done;
peres.(0) <- 0;
peres
;;
Le tableau peres est initialisé avec -1, ce qui aide à déboguer : si le
résultat contient encore des -1, c'est qu'il y a eu un problème. Cela ne
marche que si les sommets ont toujours des numéros positifs.
Un parcours d'arbre est inutile pour cette question.
4 Définissons une fonction récursive : si les deux sommets sont égaux, alors 
leur plus
proche ancêtre commun est l'un des deux, sinon c'est le plus proche ancêtre 
commun
de leurs pères, qui sont à la même hauteur.
let rec ppacMemeH pere a b =
if a = b
then a
else ppacMemeH pere pere.(a) pere.(b)
;;