X Informatique MP 2010

MP

ÉCOLE POLYTECHNIQUE

FILIÈRE
OPTION INFORMATIQUE

CONCOURS D'ADMISSION 2010

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.

Plus proche ancêtre commun
Ce problème s'intéresse à la question suivante : étant donné un arbre et deux 
noeuds dans
cet arbre, quel est le plus proche ancêtre commun de ces deux noeuds ? Une 
solution efficace à ce
problème a de nombreuses applications, notamment en bio-informatique. Ainsi, 
dans l'arbre
0
1
2

4
3

5

(1)

6

7
8

9

le plus proche ancêtre commun des noeuds 5 et 8 est le noeud 4, et celui des 
noeuds 3 et 7 est la
racine 0. De manière générale, on se donne un arbre quelconque, sur lequel on 
s'autorise un prétraitement, puis on souhaite calculer le plus efficacement 
possible le plus proche ancêtre commun
pour des couples de noeuds dans cet arbre.
Les arbres que l'on considère ici ont des noeuds étiquetés par des entiers 
distincts. Chaque
noeud a un nombre fini de descendants immédiats, appelés ses fils. Un noeud 
sans descendant est
appelé une feuille. Dans l'exemple ci-dessus, le noeud 4 a trois fils, à savoir 
5, 6 et 7, et les feuilles
sont 2, 3, 5, 6, 8 et 9. Le sous-arbre du noeud i est défini récursivement de 
la manière suivante :
c'est l'ensemble de noeuds contenant i et l'union de tous les sous-arbres des 
fils de i. On écrira
simplement « sous-arbre i » pour désigner le sous-arbre du noeud i. Si un noeud 
j appartient
au sous-arbre i, on dit que i est un ancêtre de j. En particulier, chaque noeud 
est son propre
ancêtre.
Le plus proche ancêtre commun de deux noeuds i et j, noté PPAC(i, j), est 
défini formellement
de la manière suivante :
­ si i est un ancêtre de j, alors PPAC(i, j) = i ;
­ symétriquement, si j est un ancêtre de i, alors PPAC(i, j) = j ;
­ sinon, PPAC(i, j) est l'unique noeud a possédant au moins deux fils distincts 
f1 et f2 tels
que i appartient au sous-arbre f1 et j au sous-arbre f2 .
1

Les arbres seront représentés en Caml et en Pascal de la manière suivante :
(* Caml *)
type arbre =
| Noeud of
int * arbre list ; ;

{ Pascal }
type arbre = ^noeud ;
liste_arbre = ^element ;
noeud = record n :integer ; l :liste_arbre ; end ;
element = record a :arbre ; r :liste_arbre ; end ;

Dans l'ensemble de ce problème, on se fixe une constante entière n, avec n  1, 
et un arbre A
contenant n noeuds numérotés de 0 à n - 1. On suppose en outre que cette 
numérotation vérifie
la propriété suivante :
Pour tout i, les noeuds du sous-arbre i portent des numéros consécutifs à 
partir de i.

(P)

On note que la racine de A est donc nécessairement le noeud 0.
La partie I propose une solution simple mais inefficace pour le problème du 
plus proche
ancêtre commun. La partie II propose ensuite une solution plus efficace, avec 
un pré-traitement
en O(n log n) et une réponse en temps constant. Les parties III et IV étudient 
le cas particulier
des arbres binaires complets. Enfin, la partie V étudie une application du 
calcul du plus proche
ancêtre commun.
Les parties peuvent être traitées indépendamment. Mais attention, chaque partie 
utilise des
notations et des fonctions introduites dans les parties précédentes. Les 
tableaux sont indexés à
partir de 0 et la notation t[i] est utilisée dans les questions pour désigner 
l'élément d'indice i
du tableau t, indépendamment du langage de programmation choisi. On appelle 
segment et on
note t[i..j] le sous-tableau du tableau t défini en considérant les indices 
compris entre i et j au
sens large.
I. Une solution simple
Dans cette partie, on considère une solution simple qui calcule le plus proche 
ancêtre commun
en temps O(n).
Question 1 On suppose avoir déclaré un tableau global taille de taille n. 
Écrire une procédure
remplir_taille qui stocke dans taille[i] le nombre de noeuds du sous-arbre i, 
pour tout i entre
0 et n - 1. On garantira une complexité O(n).
(* Caml *) remplir_taille : unit -> unit
{ Pascal } procedure remplir_taille ;
Par la suite, on suppose avoir appelé cette procédure.
Question 2 Écrire une fonction appartient qui prend en arguments deux noeuds i 
et j et
détermine, en temps constant, si i appartient au sous-arbre j.
(* Caml *) appartient : int -> int -> bool
{ Pascal } function appartient(i : integer ; j : integer) : boolean ;
2

Question 3 Écrire une fonction ppac1 qui prend en arguments deux noeuds i et j 
et détermine
PPAC(i, j) en temps O(n).
(* Caml *) ppac1 : int -> int -> int
{ Pascal } function ppac1(i : integer ; j : integer) : integer ;

II. Une solution plus efficace
Dans cette partie, on va effectuer un pré-traitement de l'arbre A qui permettra 
de déterminer
ensuite en temps constant le plus proche ancêtre commun pour tout couple de 
noeuds.
On commence par construire une séquence de noeuds en effectuant un tour 
Eulérien de
l'arbre A à partir de sa racine. D'une manière générale, le tour Eulérien à 
partir du noeud i est
défini comme agissant sur une séquence résultat, construite de la manière 
suivante :
1. ajouter le noeud i à la fin de la séquence résultat ;
2. pour chaque fils j de i,
(a) effectuer un tour Eulérien à partir de j,
(b) ajouter le noeud i à la fin de la séquence résultat.
Ainsi, sur l'exemple de l'arbre (1), on obtient la séquence suivante :
0, 1, 2, 1, 3, 1, 0, 4, 5, 4, 6, 4, 7, 8, 7, 9, 7, 4, 0
Question 4 Montrer que le tour Eulérien de A contient exactement 2 × n - 1 
éléments. Par la
suite, on appelle m cette valeur et on suppose avoir déclaré un tableau global 
euler de taille m
destiné à contenir le résultat du tour Eulérien.
Question 5 On suppose avoir déclaré un tableau global index de taille n. Écrire 
une procédure
remplir_euler qui remplit le tableau euler avec le résultat du tour Eulérien de 
A et, dans le
même temps, le tableau index de telle sorte que euler[index[i]] = i pour tout i 
entre 0 et n - 1
(s'il existe plusieurs valeurs possibles pour index[i], on pourra choisir 
arbitrairement).
(* Caml *) remplir_euler : unit -> unit
{ Pascal } procedure remplir_euler ;
Par la suite, on suppose avoir appelé cette procédure.
Question 6 Montrer que le plus proche ancêtre commun de i et j dans A est égal 
au plus petit
élément du tableau euler compris entre les indices index[i] et index[j].
Question 7 Écrire une fonction log2 qui prend en argument un entier n, avec n  
1, et calcule
le plus grand entier k tel que 2k  n.
(* Caml *) log2 : int -> int
{ Pascal } function log2(n : integer) : integer ;

3

Question 8 On pose k = log2(m). On suppose avoir déclaré une matrice globale M 
de taille
m × (k + 1). Écrire une procédure remplir_M qui remplit la matrice M de telle 
sorte que, pour
tout 0  j  k et tout 0  i  m - 2j , on ait
M[i][j] =

min euler[l]

il unit
{ Pascal } procedure remplir_M ;
Par la suite, on suppose avoir appelé cette procédure.

Question 9 Écrire une fonction minimum qui prend en arguments deux entiers i et 
j, avec
0  i  j < m, et qui détermine le plus petit élément du segment euler[i..j] en temps constant. (* Caml *) minimum : int -> int -> int
{ Pascal } function minimum(i : integer ; j : integer) : integer ;

Question 10 Écrire une fonction ppac2 qui prend en arguments deux noeuds i et j 
et qui
détermine PPAC(i, j) en temps constant.
(* Caml *) ppac2 : int -> int -> int
{ Pascal } function ppac2(i : integer ; j : integer) : integer ;

III. Opérations sur les bits des entiers primitifs
Dans cette partie, on introduit des notations et des fonctions qui seront 
utiles pour la partie
IV. Il s'agit de fonctions opérant sur la représentation binaire des entiers 
primitifs (type int de
Caml ou integer de Pascal). On ne considère ici que des entiers positifs ou 
nuls, s'écrivant en
binaire sur un nombre de bits N dont la valeur est non précisée et non connue 
(mais inférieure
ou égale à 30). Un entier x s'écrivant en binaire sur N bits est noté (xN -1 . 
. . x1 x0 )2 où chaque
bit xi vaut 0 ou 1. Les chiffres les moins significatifs sont écrits à droite, 
de sorte que la valeur
P -1
i
de x est donc N
i=0 xi 2 .
On suppose que le langage fournit les trois opérations et_bits, ou_bits et 
ou_excl_bits
calculant respectivement les opérations ET, OU et OU-exclusif sur les 
représentations binaires de deux entiers, en temps constant. Plus précisément, 
si x = (xN -1 . . . x1 x0 )2 et
y = (yN -1 . . . y1 y0 )2 , alors et_bits(x, y) est l'entier z = (zN -1 . . . 
z1 z0 )2 défini par
zi = ET(xi , yi ) pour tout i ; de même pour les opérations ou_bits et 
ou_excl_bits. On rappelle
que les opérations ET, OU et OU-exclusif sont définies par les tables de vérité 
suivantes :
ET
OU
OU-exclusif
0 1
0 1
0 1
0 0 0
0 0 1
0 0 1
1 0 1
1 1 1
1 1 0
4

On suppose que le langage fournit également deux opérations decalage_gauche et
decalage_droite décalant respectivement les bits d'un entier vers la gauche et 
vers la droite, en
insérant des bits 0 respectivement à droite et à gauche. Plus précisément, si x 
= (xN -1 . . . x1 x0 )2
et si 0  k  N alors
decalage_gauche(x, k) = (xN -1-k . . . x1 x0 0| .{z
. . 0})2
k

decalage_droite(x, k) = (0
. . 0} xN -1 . . . xk+1 xk )2
| .{z
k

Question 11 Écrire une fonction bit_fort qui prend en argument un entier
x = (xN -1 . . . x1 x0 )2 , supposé non nul, et détermine le plus grand indice 
i tel que xi = 1,
c'est-à-dire la position du bit le plus significatif de x. On garantira une 
complexité O(N ).
(* Caml *) bit_fort : int -> int
{ Pascal } function bit_fort(n : integer) : integer ;
Question 12 Pour plus d'efficacité, on peut pré-calculer et ranger dans un 
tableau les valeurs
de bit_fort pour les 256 premiers entiers. Écrire une nouvelle version de 
bit_fort qui exploite
cette idée pour n'effectuer pas plus de deux décalages. (On rappelle qu'on a 
supposé N  30.)
IV. Cas particulier d'un arbre binaire complet
Dans cette partie, on considère le problème du plus proche ancêtre commun dans 
le cas
particulier où l'arbre A est un arbre binaire complet, c'est-à-dire que tout 
noeud de A a exactement
zéro ou deux fils et toutes les feuilles de A sont à la même distance de la 
racine. (On continue
cependant d'utiliser le même type arbre.) Voici un exemple d'arbre binaire 
complet de hauteur 2 :
0
1
2

4
3

5

6

D'une manière générale, si on note d la hauteur de A, alors A possède 2d 
feuilles et n = 2d+1 - 1
noeuds au total. La hauteur d'un noeud dans l'arbre A est définie comme sa 
distance aux feuilles.
Dans l'exemple ci-dessus, les feuilles 2, 3, 5, 6 ont pour hauteur 0, les 
noeuds 1 et 4 ont pour
hauteur 1 et la racine 0 a pour hauteur 2.
L'idée consiste alors à associer à chaque noeud i un entier B(i) dont la 
représentation en
binaire sur d + 1 bits encode sa position dans l'arbre. On procède ainsi : le 
chemin qui mène de
la racine au noeud est représenté par une suite de 0 et de 1, avec la 
convention que 0 représente
un déplacement vers le sous-arbre gauche et 1 un déplacement vers le sous-arbre 
droit. Pour un
noeud de hauteur h, on obtient donc un chemin de longueur d - h, soit xd . . . 
xh+1 . À ce chemin,
on concatène alors à droite la représentation binaire de 2h , c'est-à-dire un 
bit 1 suivi de h bits 0.
Au final, on a donc pour tout noeud i de hauteur h dans A :
B(i) = ( xd . . . xh+1 1 0| .{z
. . 0} )2
|
{z
}
chemin de 0 à i

h

On note que le chemin est vide pour la racine et que le suffixe de zéros est 
vide pour les feuilles.
Pour l'arbre ci-dessus, on obtient les valeurs suivantes de B(i), données en 
binaire :
5

(100)2
(010)2
(001)2

(110)2

(011)2

(101)2

(111)2

On note que les B(i) prennent toutes les valeurs entre 1 et n, et qu'il y a 
donc bijection entre les
noeuds et les valeurs que leur associe la fonction B.
Question 13 On suppose avoir déclaré deux tableaux globaux, B de taille n et 
Binv de taille
n + 1. Écrire une procédure remplir_B qui remplit le tableau B avec les valeurs 
de B et le
tableau Binv avec les valeurs de B -1 (l'élément d'indice 0 de Binv étant 
inutilisé). On garantira
une complexité O(n).
(* Caml *) remplir_B : unit -> unit
{ Pascal } procedure remplir_B ;
Par la suite, on suppose avoir appelé cette procédure.
Question 14 Soient i et j deux noeuds de A tels que i n'est pas un ancêtre de j 
et j n'est pas un
ancêtre de i. Soit x le résultat de ou_excl_bits(B(i), B(j)), puis k le 
résultat de bit_fort(x).
Que représente k ? Comment en déduire la valeur de B(a), où a est le plus 
proche ancêtre commun
de i et j dans A ?
Question 15 Déduire de la question précédente une fonction ppac3 qui prend en 
arguments
deux noeuds i et j et qui détermine PPAC(i, j) en temps constant. On prendra 
soin de traiter
différemment le cas où i est un ancêtre de j ou j un ancêtre de i ; on pourra 
réutiliser à cet effet
la fonction appartient de la question .
(* Caml *) ppac3 : int -> int -> int
{ Pascal } function ppac3(i : integer ; j : integer) : integer ;
V. Application
Dans cette partie, on considère une application du calcul du plus proche 
ancêtre commun au
problème suivant : étant donné un tableau T de n entiers, on souhaite calculer, 
pour des paires
d'indices i et j tels que 0  i  j < n, l'élément minimum du segment T[i..j]. Comme pour le calcul du plus proche ancêtre commun, on s'autorise un pré-traitement du tableau T permettant ensuite de répondre en temps constant pour tout segment. L'idée est de construire un arbre A contenant les n éléments de T et de se ramener au problème du plus proche ancêtre commun. D'une manière générale, on définit un arbre binaire à partir d'un segment non vide T[i..j] en procédant récursivement de la manière suivante : 1. si i = j, l'arbre est réduit à la feuille T[i] ; 2. sinon, sa racine est le plus petit élément de T[i..j] ; soit T[m] cet élément, avec i  m  j (s'il y a plusieurs valeurs possibles de m, on choisit arbitrairement). On distingue alors trois cas : 6 (a) si m = i, on construit un unique sous-arbre à partir de T[m + 1..j], (b) si m = j, on construit un unique sous-arbre à partir de T[i..m - 1], (c) sinon, on construit deux sous-arbres, respectivement à partir de T[i..m - 1] et de T[m + 1..j]. L'arbre A est alors défini en partant du segment complet T[0..n - 1]. On note que les noeuds de A ont directement pour valeurs les éléments de T, i.e. on ne se soucie pas ici de numéroter les noeuds de A de 0 à n - 1 afin de vérifier la propriété (P). On admet le résultat suivant : le plus proche ancêtre commun des noeuds correspondant à i et j dans A est égal à l'élément minimum du segment T[i..j]. Question 16 Donner la complexité dans le pire des cas de l'algorithme récursif ci-dessus construisant A à partir de T, en fonction de n (en supposant le minimum calculé en temps linéaire). On propose un algorithme plus efficace pour construire l'arbre A. Cet algorithme construit incrémentalement l'arbre correspondant aux éléments de T[0..i], pour i allant de 0 à n - 1. Initialement, l'arbre est réduit à l'unique noeud T[0]. Supposons avoir déjà construit l'arbre correspondant aux i premiers éléments de T, c'est-à-dire au segment T[0..i - 1]. Cet arbre a la forme suivante v 1 v2 t1 (2) vk-1 t2 vk tk-1 tk avec une « branche droite » formée de k noeuds tels que v1  v2  . . .  vk-1  vk . Chaque arbre ti est éventuellement vide et ne contient que des éléments strictement plus grands que vi . Pour insérer l'élément suivant, soit v = T[i], on cherche la position de v dans la liste v1 , v2 , . . . , vk , c'est-à-dire le plus grand j tel que vj  v < vj+1 (si v < v1 on pose j = 0 et si vk  v on pose j = k). On crée alors un nouveau noeud v que l'on insère à la place de vj+1 et le sous-arbre vj+1 est accroché sous le noeud v. On obtient le nouvel arbre v1 vj t1 tj v vj+1 vk tj+1 tk dont la nouvelle branche droite est donc v1 , . . . , vj , v. Si j = k, alors on ajoute v comme fils droit de vk , et la nouvelle branche droite est simplement l'ancienne étendue par v (à la fin). On ne demande pas de montrer la correction de cet algorithme. 7 Question 17 Écrire une fonction construire_A qui construit l'arbre A à partir du tableau T en suivant ce nouvel algorithme. (* Caml *) construire_A : int array -> arbre
{ Pascal } function construire_A(t : array[0..n-1] of integer) : arbre ;
Indication : on pourra représenter la branche droite par une liste d'arbre (du 
type arbre list
en Caml et liste_arbre en Pascal), dans l'ordre inverse, c'est-à-dire vk , . . 
. , v1 . Chacun de ces
arbres a une racine vi et au plus un fils ti .

Question 18 Montrer que la complexité de cet algorithme est O(n).

Note : En 1984, Harel et Tarjan ont montré qu'il existe un pré-traitement de 
complexité linéaire sur un arbre qui permet d'obtenir ensuite le plus proche 
ancêtre commun en temps constant. On a donc le même résultat pour le problème 
du minimum
du segment.

8