X Informatique MP 2011

ÉCOLE POLYTECHNIQUE ­ ÉCOLES NORMALES SUPÉRIEURES

FILIÈRE

CONCOURS D'ADMISSION 2011

MP SPÉCIALITÉ INFO

COMPOSITION D'INFORMATIQUE ­ A ­ (XULC)
(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.

Transmission dans les arbres
On étudie dans ce problème des algorithmes de transmission d'informations dans 
les arbres,
avec le modèle dit "du téléphone". Dans la partie I, on étudie les arbres 
binomiaux. Dans la
partie II, on considère plusieurs calculs élémentaires sur les arbres. Dans la 
partie III, on étudie
la diffusion de l'information à partir de la racine de l'arbre. Dans la partie 
IV, on s'intéresse à
l'échange total d'informations entre tous les noeuds d'un arbre. Les parties I 
et II sont indépendantes.

Algorithmes et programmes
­ Pour les questions qui demandent la conception d'un algorithme : il s'agit de 
donner une
description concise mais précise, en français, d'un algorithme effectuant la 
tâche indiquée.
­ Pour les questions qui demandent l'écriture d'un programme : il s'agit 
d'exprimer votre algorithme dans un langage de programmation de votre choix. La 
lisibilité de votre programme
(notamment : mise en évidence de sa structure, indentation, commentaires 
pertinents) sera
prise en compte dans l'évaluation.
­ Lorsqu'elle est demandée, la complexité d'un algorithme ou d'un programme ne 
sera pas
calculée exactement mais seulement estimée en ordre de grandeur, avec des 
expressions du
type O(m+n), O(m2 log n), etc., où m, n, . . . sont des paramètres en entrée de 
l'algorithme.
­ Lorsqu'une question demande d'écrire un programme, et qu'une certaine 
complexité est
exigée, on ne demande pas de faire la preuve que le programme proposé a 
effectivement
cette complexité.

Définitions
­ Un arbre T = (r, L) est défini par la donnée d'un entier r, appelé noeud, et 
d'une liste
d'arbres L, éventuellement vide. Si la liste L est vide, on dit que r est un 
noeud externe.
Sinon, la liste L comprend  éléments Ti = (ri , Li ), 1  i  , on dit que r est 
un noeud
interne, que les noeuds ri sont les fils de r, et que r est le père des ri .

1

­ Tous les noeuds de T sont supposés distincts. On note N (T ) l'ensemble de 
tous les noeuds
de T et nbn(T ) leur nombre.
­ Dans un arbre, les voisins d'un noeud sont son père (s'il existe) et ses fils.
­ Entre deux noeuds s et t de T il existe un unique chemin, composé de noeuds 
x0 , x1 , . . . , xk
deux à deux distincts, tels que x0 = s, xk = t, et xi et xi+1 sont voisins pour 
0  i  k - 1.
On note chemin(s, t) ce chemin et on dit que k est sa longueur.
­ Le noeud r est appelé la racine de T .
­ La profondeur d'un noeud s est la longueur de chemin(s, r) ; en particulier, 
la racine r a
pour profondeur 0. La profondeur de T est le maximum de la profondeur de ses 
noeuds.
Les arbres seront représentés en Caml et en Pascal de la manière suivante :
{ Pascal }
type arbre = ^noeud ;
liste_arbre = ^element ;
noeud = record n :integer ; l :liste_arbre ; end ;
element = record a :arbre ; r :liste_arbre ; end ;

(* Caml *)
type arbre =
| Noeud of int * arbre list ; ;

Certaines questions font par ailleurs intervenir des listes d'entiers, qui 
seront représentées par
le type liste suivant :
type liste == int list ; ;

type liste = ^entier ;
entier = record e :integer ; s :liste ; end ;

Partie I.

Arbres binomiaux

Dans cette partie, on étudie des arbres particuliers, appelés "binomiaux".
Soit k un entier positif ou nul. Un arbre binomial d'ordre k est défini comme 
suit :
­ un arbre binomial d'ordre 0 est réduit à sa racine ;
­ si k > 0, un arbre binomial d'ordre k est de la forme (rk , (Tk-1 , . . . , 
T1 , T0 )) où chaque Ti
est un arbre binomial d'ordre i.
Dans la suite, Bk désigne un arbre binomial d'ordre k.
Question 1

Dessiner B4 , avec une numérotation des noeuds de votre choix.

Question 2

Quel est le nombre de noeuds de Bk ? Combien sont externes ?

Question 3 Pour k > 0, montrer qu'on peut aussi définir récursivement Bk à 
l'aide de deux
copies de Bk-1 .
Question 4 Écrire une fonction copie qui prend en arguments un entier n et un 
arbre T et
renvoie une copie de l'arbre T dans laquelle chaque noeud de numéro i est 
remplacé par un noeud
de numéro i + n.
2

(* Caml *) copie : int -> arbre -> arbre
{ Pascal } function copie(n : integer ; t : arbre) : arbre ;

Question 5 Écrire une fonction bin qui prend en argument un entier k  0 et qui 
renvoie l'arbre
Bk , avec une numérotation des noeuds de votre choix. On garantira une 
complexité proportionnelle
au nombre de noeuds de Bk .
(* Caml *) bin : int -> arbre
{ Pascal } function bin(k : integer) : arbre ;

Question 6 Quelle est la profondeur de Bk ? Quelle est la longueur maximale 
d'un chemin
entre deux noeuds ?
Question 7

Combien de noeuds ont une profondeur donnée  ?

Question 8 Pour n  1, on définit Cn comme un arbre de racine r et à n noeuds, 
qu'on obtient
avec la numérotation suivante des noeuds : la racine r a le numéro 1, et le 
père du noeud de
numéro i, où 2  i  n, est le noeud de numéro i - 2log2 i-1 , où la notation x 
désigne le plus
petit entier supérieur ou égal à x. Dessiner C16 . Justifier que la définition 
de Cn conduit bien à
un arbre. Donner, sans la justifier, une relation entre Bk et C2k .
Question 9 Écrire une fonction cn qui prend en argument un entier n  1 et qui 
renvoie
l'arbre Cn . On garantira une complexité O(n).
(* Caml *) cn : int -> arbre
{ Pascal } function cn(n : integer) : arbre ;

Partie II.

Fonctions élémentaires sur les arbres

Question 10 Écrire une fonction profondeur qui prend en argument un arbre T et 
renvoie sa
profondeur. On garantira une complexité O(nbn(T )).
(* Caml *) profondeur : arbre -> int
{ Pascal } function profondeur(t : arbre) : integer ;

Question 11 Écrire une fonction noeud_externe_max qui prend en argument un 
arbre T et
qui renvoie le numéro d'un noeud externe de T de profondeur maximale. En cas 
d'égalité, on
choisira arbitrairement. On garantira une complexité O(nbn(T )).
(* Caml *) noeud_externe_max : arbre -> int
{ Pascal } function noeud_externe_max(t : arbre) : integer ;
3

Question 12 Soit T un arbre de racine r et s un noeud de T . Écrire une 
fonction chemin
qui prend en arguments T et s et renvoie l'unique chemin de r à s sous la forme 
d'une liste
d'entiers [x0 ; x1 ; . . . ; xk ] avec x0 = r, xk = s et xi père de xi+1 pour 0 
 i < k. On garantira une complexité O(nbn(T )). (* Caml *) chemin : arbre -> int -> liste
{ Pascal } function chemin(t : arbre ; s : integer) : liste ;

Question 13 Soit T un arbre et s un noeud de T . On définit l'arbre obtenu par 
changement
de racine s, noté pivot(T , s), comme l'arbre T  de racine s dont les noeuds 
sont les mêmes que
ceux de T et tel que deux noeuds sont voisins dans T  si et seulement s'ils le 
sont dans T .
Écrire une fonction pivot qui prend en arguments T et s et renvoie l'arbre 
pivot (T , s).
On garantira une complexité O(nbn(T )). S'il y a plusieurs tels arbres T  , on 
en choisit un
arbitrairement.
(* Caml *) pivot : arbre -> int -> arbre
{ Pascal } function pivot(t : arbre ; s : integer) : arbre ;

Question 14 Étant donné un arbre T , on définit son diamètre comme la longueur 
du plus
long chemin dans T . Soit r1 l'un des noeuds externes de T de profondeur 
maximale, et T  =
pivot(T , r1 ) l'arbre obtenu à partir de T par changement de racine r1 . 
Montrer que le diamètre
de T est égal à la profondeur de T  .
Question 15
son diamètre.

En déduire une fonction diametre qui prend en argument un arbre et qui renvoie

(* Caml *) diametre : arbre -> int
{ Pascal } function diametre(t : arbre) : integer ;

Question 16 Soit T un arbre de diamètre D. Montrer que D est la plus grande 
profondeur
d'un arbre obtenu par changement arbitraire de racine et que  D2  est la plus 
petite profondeur
d'un arbre obtenu par changement arbitraire de racine.

Partie III.

Diffusion dans les arbres

On étudie dans cette partie le problème de la diffusion dans les arbres. La 
racine r de l'arbre
T = (r, L) possède un message qu'elle doit transmettre à tous les autres 
noeuds. La diffusion
procède par étapes, toutes de temps unitaire. À une étape donnée, chacun des 
noeuds déjà en
possession du message le transmet à un et un seul de ses fils (sauf si tous ses 
fils l'ont déjà reçu).
Une diffusion D est caractérisée par un ensemble de fonctions : à chaque noeud 
interne v de
l'arbre, avec nv fils, on associe une fonction injective fv qui numérote ses 
fils de 1 à nv dans
l'ordre dans lequel v leur transmet le message.

4

Pour v  N (T ), on note tD (v) le numéro de l'étape à laquelle v reçoit le 
message :

0
si v = r,
tD (v) =
tD (v  ) + fv (v) si v  est le père de v.
Voici un exemple :
·
·
·

3

·
·
·

·
·
·

Un arbre

·

·
·
·

1

·

1
1

·
2

1
·

·
·

0

1

1

·

·

2
·
·

3

2

4

3

2

3

4

3

4

1

Valeurs des fonctions fv

1

Valeurs des numéros
des étapes tD (v)

La durée de la diffusion est son nombre d'étapes, soit t(D) = maxvN (T ) tD 
(v). Une diffusion
est optimale si sa durée est minimale parmi les durées de toutes les diffusions.

Diffusion dans les arbres binomiaux
On considère l'arbre binomial Bk défini dans la partie I. Tout noeud interne v 
a pour fils les
racines r1 , . . . , rnv d'arbres binomiaux B0 , B1 , . . . , Bnv -1 . La 
numérotation naturelle s'obtient en
posant fv (ri ) = i pour chaque noeud v et chaque i, 1  i  nv , tandis que la 
numérotation
renversée s'obtient en posant fv (ri ) = nv - i + 1.
Question 17 Quelle est la durée de la diffusion qui choisit la numérotation 
naturelle pour
chaque noeud ?
Question 18 Même question pour la diffusion qui choisit la numérotation 
renversée pour
chaque noeud.
Question 19 Quelle est la durée d'une diffusion optimale dans Bk ? Justifier 
votre réponse.

Diffusion dans un arbre quelconque
Question 20 Proposer un algorithme pour déterminer une diffusion optimale dans 
un arbre
T quelconque. Quelle est sa complexité en fonction de nbn(T ) ?
Question 21 Écrire une fonction diffusion_optimale qui prend en argument un 
arbre T et
qui calcule la durée d'une diffusion optimale pour T . (On pourra supposer que 
le langage de
programmation contient une fonction qui trie un tableau ou une liste d'entiers.)
(* Caml *) diffusion_optimale : arbre -> int
{ Pascal } function diffusion_optimale(t : arbre) : integer ;
5

Durée de la diffusion optimale
Question 22 Donner une borne supérieure pour la durée d'une diffusion optimale 
dans un
arbre arbitraire à n noeuds, et exhiber pour tout n un arbre pour lequel cette 
borne est atteinte.
Question 23 Donner une borne inférieure pour la durée d'une diffusion optimale 
dans un arbre
arbitraire à n noeuds, et exhiber pour tout n un arbre pour lequel cette borne 
est atteinte.

Partie IV.

Échange total dans les arbres

On étudie dans cette partie le problème de l'échange total dans les arbres. 
Chaque noeud v
de l'arbre possède un message msgv qu'il doit transmettre à tous les autres 
noeuds. L'échange
total procède par étapes, toutes de temps unitaire. Lors d'une étape, certaines 
paires de voisins
s'échangent tous les messages qu'ils ont reçus dans les étapes précédentes ; 
chaque noeud ne peut
communiquer qu'avec un seul voisin lors d'une étape donnée. La durée d'un 
échange total est
son nombre d'étapes, et son trafic est le nombre d'échanges entre voisins ayant 
eu lieu au cours
de l'algorithme. Voici un exemple pour un arbre à 4 noeuds, dont la durée est 3 
et le trafic 5 :
Étape 0

Étape 1
msg2
msg1

msg1 , msg2
msg1 , msg2

msg3

msg3 , msg4
msg3 , msg4

msg4
Étape 2

Étape 3
msg1 , msg2
msg3 , msg4

msg1 , msg2
msg3 , msg4
msg1 , msg2

msg1 , msg2
msg3 , msg4

msg1 , msg2
msg3 , msg4

msg1 , msg2
msg3 , msg4
msg1 , msg2
msg3 , msg4

msg3 , msg4

Échange total dans les arbres binomiaux
On revient dans cette question sur l'arbre binomial Bk d'ordre k  1 introduit 
dans la partie I.
Question 24 Proposer un algorithme d'échange total dans Bk dont la durée est 2k 
- 1.
Question 25 Montrer que tout échange total dans Bk a une durée au moins égale à 
2k - 1.

6

Question 26 Plus généralement, donner une borne inférieure pour la durée de 
tout échange
total dans un arbre T quelconque à n  2 noeuds.

Échange total de trafic minimal
Soit T un arbre à n  2 noeuds. On considère l'échange total suivant, où il y a 
un seul échange
à chaque étape :
1. Tant que l'arbre contient au moins trois noeuds :
(a) On choisit un noeud externe s (arbitrairement s'il y en a plusieurs), qui 
effectue un
échange avec son père ;
(b) On efface le noeud s de l'arbre.
2. Les deux derniers noeuds échangent leur information et possèdent désormais 
les messages
de tous les noeuds de T .
3. On effectue à nouveau tous les échanges de l'étape 1, dans l'ordre inverse, 
pour propager
l'information à tous les noeuds.
Question 27 Montrer que le trafic de l'échange total précédent est égal à 2n - 
3.
Question 28 Écrire une fonction echange_total qui prend en argument un arbre T 
et renvoie
la liste des n - 2 noeuds externes successivement retirés de l'arbre T par 
l'étape 1 de l'algorithme
d'échange total ci-dessus. On garantira une complexité O(nbn(T )).
(* Caml *) echange_total : arbre -> liste
{ Pascal } function echange_total(t : arbre) : liste ;

Question 29 Montrer que le trafic de tout échange total dans un arbre à n  2 
noeuds est au
moins égal à 2n - 3.

7