X Informatique MP 2012

ECOLE POLYTECHNIQUE ­ ECOLES NORMALES SUPERIEURES

FILIERE

CONCOURS D'ADMISSION 2012

MP SPECIALITE INFO

COMPOSITION D'INFORMATIQUE ­ A ­ (XULC)
(Duree : 4 heures)
L'utilisation des calculatrices n'est pas autorisee pour cette epreuve.
Le langage de programmation choisi par le candidat doit etre specifie en tete 
de la copie.

Arbres combinatoires
On etudie dans ce probleme des outils pour la combinatoire, qui peuvent etre 
utilises en
particulier pour repondre a des questions telles que : Combien existe-t-il de 
facons de paver un
echiquier 8 × 8 par 32 dominos de taille 2 × 1 ?
La partie I introduit la structure d'arbre combinatoire, qui permet de 
representer un ensemble
d'ensembles d'entiers. La partie II etudie quelques fonctions elementaires sur 
cette structure. La
partie III propose ensuite un principe de memorisation, pour definir des 
fonctions plus complexes
sur les arbres combinatoires. La partie IV utilise les resultats precedents 
pour repondre au
probleme de denombrement ci-dessus. Enfin, les deux dernieres parties 
expliquent comment
construire et manipuler efficacement des arbres combinatoires, a l'aide de 
tables de hachage.
Les parties peuvent etre traitees independamment. Neanmoins, chaque partie 
utilise des
notations et des fonctions introduites dans les parties precedentes. Les 
tableaux sont indexes a
partir de 0 et la notation t[i] est utilisee dans les questions pour designer 
l'element d'indice i du
tableau t, independamment du langage de programmation choisi.
La complexite, ou le cout, d'un programme P (fonction ou procedure) est le 
nombre
d'operations elementaires (addition, soustraction, multiplication, division, 
affectation, etc...)
necessaires a l'execution de P . Lorsque cette complexite depend d'un parametre 
n, on dira
que P a une complexite en O(f (n)), s'il existe K > 0 tel que la complexite de 
P est au plus
Kf (n), pour tout n. Lorsqu'il est demande de garantir une certaine complexite, 
le candidat
devra justifier cette derniere si elle ne se deduit pas directement de la 
lecture du code.
Dans l'ensemble de ce probleme, on se fixe une constante entiere n, avec n  1.
On note E l'ensemble {0, 1, . . . , n - 1}.

1

Partie I. Arbres combinatoires
Dans cette partie, on etudie les arbres combinatoires, une structure de donnees 
pour
representer un element de P(P(E)), c'est-a-dire un ensemble de parties de E. Un 
arbre combinatoire est un arbre binaire dont les noeuds sont etiquetes par des 
elements de E et les feuilles
par  ou . Voici un exemple d'arbre combinatoire :
0
1

1

2

2

Un noeud etiquete par i, de sous-arbre gauche A1 et de sous-arbre droit A2 sera 
note i  A1 , A2 .
L'arbre ci-dessus peut donc egalement s'ecrire sous la forme
0  (1  (2  , ), ), (1  , (2  , )).

(1)

Dans ce sujet, on impose la double propriete suivante sur tout (sous-)arbre 
combinatoire de la
forme i  A1 , A2 : d'une part
A1 et A2 ne contiennent pas d'element j avec j  i

(ordre)

et d'autre part
A2 6= .

(suppression)

Ainsi les deux arbres
0

0

1
2

2

1
1

2

1

2

ne correspondent pas a des arbres combinatoires, car celui de gauche ne verifie 
pas la condition
(ordre) et celui de droite ne verifie pas la condition (suppression).
A tout arbre combinatoire A on associe un ensemble de parties de E, note S(A), 
defini par
S() = 
S() = {}
S(i  A1 , A2 ) = S(A1 )  {{i}  s | s  S(A2 )}
L'interpretation d'un arbre A de la forme i  A1 , A2 est donc la suivante : i 
est le plus petit
element appartenant a au moins un ensemble de S(A), A1 est le sous-ensemble de 
S(A) des
ensembles qui ne contiennent pas i, et A2 est le sous-ensemble de S(A) des 
ensembles qui
contiennent i auxquels on a enleve i. Ainsi, l'arbre
0
1

est interprete comme l'ensemble {, {0, 1}}.
2

Question 1 Donner l'ensemble defini par l'arbre combinatoire de l'exemple (1).
Question 2 Donner les trois arbres combinatoires correspondant aux trois 
ensembles {{0}},
{, {0}} et {{0, 2}}.
Question 3 Soit A un arbre combinatoire different de . Montrer que A contient 
au moins
une feuille .
Question 4 Combien existe-t-il d'arbres combinatoires distincts (en fonction de 
n) ? On justifiera soigneusement la reponse.

Partie II. Fonctions elementaires sur les arbres combinatoires
On se donne le type ac suivant pour representer les arbres combinatoires.
(* Caml *)
type ac = Zero | Un
| Comb of int * ac * ac;;

{ Pascal }
type ac = ^noeud;
noeud = record element : integer;
gauche : ac; droit : ac; end;

Le constructeur Zero represente  et le constructeur Un represente . En Pascal, 
on suppose
que deux constantes Zero et Un de type ac ont ete definies. On se donne une 
fonction cons pour
construire un noeud de la forme i  A1 , A2 .
(* Caml *) cons: int -> ac -> ac -> ac
{ Pascal } function cons(i: integer; a1: ac; a2: ac) : ac;

Cette fonction suppose que les proprietes (ordre) et (suppression) sont 
verifiees. On suppose que
cette fonction a un cout O(1).

Dans les questions suivantes, une partie de E est representee par la liste de 
ses elements,
triee par ordre croissant. On note ensemble le type correspondant, c'est-a-dire
(* Caml *)
type ensemble == int list;;

{ Pascal }
type ensemble =
record tete: integer; queue: ^ensemble; end;

Question 5 Ecrire une fonction un elt qui prend en argument un arbre 
combinatoire A,
suppose different de , et qui renvoie un ensemble s  S(A) arbitraire. On 
garantira une
complexite au plus egale a la hauteur de A.
(* Caml *) un elt: ac -> ensemble
{ Pascal } procedure un elt(a: ac; var v: ensemble);
3

Question 6 Ecrire une fonction singleton qui prend en argument un ensemble 5 
EUR P(E)
et qui renvoie l'arbre combinatoire représentant le singleton { 5} On garantira 
une complexité

O(n).

(* Caml *) singleton: ensemble --> ac
{ Pascal } function singleton(s: ensemble) : ac;

Question 7 Écrire une fonction appartient qui prend en arguments un ensemble 3 
EUR P(E) et
un arbre combinatoire A et qui teste si 3 appartient à S (A) On garantira une 
complexité O(n).

(* Caml *) appartient: ensemble --> ac --> bool
{ Pascal } function appartient(s: ensemble; a: ac) : boolean;

Question 8 Écrire une fonction cardinal qui prend en argument un arbre 
combinatoire A et
qui renvoie ca7'd(S(À))7 le cardinal de S (A) On garantira une complexité 
O(card(S(A))).

(* Caml *) cardinal: ac --> int
{ Pascal } function cardinal(az ac) : integer;

Partie III. Principe de mémorisation

Taille d'un arbre combinatoire. On définit l'ensemble des sous--arbres d'un 
arbre combi--
natoire A, noté LI(A)7 par

uc) : ...
Z/{('*) = {T}
M(i-->A1,A2) {i-->A;,Ag}UM(AÙUU(A2)

La taille d'un arbre combinatoire A, notée T(A), est définie comme le cardinal 
de M(A), c'est--
êrdirc comme le nombre de ses sous--arbres distincts.

Question 9 Quelle est la taille de l'arbre combinatoire de l'exemple (1) 7

Principe de mémorisation. Pour écrire efficacement une fonction sur les arbres 
combina--
toires7 on va mémoriser tous les résultats obtenus par cette fonction, de 
manière à ne pas refaire
deux fois le même calcul. Pour cela, on suppose donnée une structure de table 
d'association
indexée par des arbres combinatoires. Plus précisément, on suppose donné un 
type tablel
représentant une table associant à des arbres combinatoires des valeurs d'un 
type quelconque et
les quatre fonctions suivantes :

* creel() renvoie une nouvelle table7 initialement vide;

* aj oute1(t, a, v) ajoute l'association de la valeur 11 à l'arbre a dans la 
table t;

­ present1(t, a) renvoie un booleen indiquant si l'arbre a est associe a une 
valeur dans la
table t ;
­ trouve1(t, a) renvoie la valeur associee a l'arbre a dans la table t, en 
supposant qu'elle
existe.
On suppose que les trois fonctions ajoute1, present1 et trouve1 ont toutes un 
cout constant
O(1). On suppose de meme l'existence d'un type table2 representant des tables 
d'association
indexees par des couples d'arbres combinatoires et quatre fonctions similaires 
cree2, ajoute2,
present2 et trouve2, egalement de cout constant. (Les parties V et VI 
expliqueront comment
de telles tables peuvent etre construites.)
Question 10 Reecrire la fonction cardinal de la question 8 a l'aide du principe 
de
memorisation pour garantir une complexite O(T (A)). Justifier soigneusement la 
complexite du
code propose.
(* Caml *) cardinal: ac -> int
{ Pascal } function cardinal(a: ac) : integer;

Question 11 Ecrire une fonction inter qui prend en arguments deux arbres 
combinatoires A1
et A2 et qui renvoie l'arbre combinatoire representant leur intersection, 
c'est-a-dire l'arbre A tel
que S(A) = S(A1 )  S(A2 ).
(* Caml *) inter: ac -> ac -> ac
{ Pascal } function inter(a1: ac; a2: ac) : ac;

Question 12 Montrer que, pour tous arbres combinatoires A1 et A2 , on a
T (inter(A1 , A2 ))  T (A1 ) × T (A2 ).

Partie IV. Application au denombrement
On en vient maintenant au probleme de denombrement evoque dans l'introduction. 
Soit p
un entier pair superieur ou egal a 2. On cherche a determiner le nombre de 
facons de paver un
2
echiquier de dimensions p × p avec p2 dominos de taille 2 × 1. Voici un exemple 
de tel pavage
pour p = 8 :

5

Pour cela, on va construire un arbre combinatoire A tel que le cardinal de S 
(A) est exactement
le nombre de pavages possibles.

Question 13 Combien existe-til de façons différentes de placer un domino 2 >< 1 sur l'échiquier '? Dans ce qui suit, on suppose que n est égal à la réponse a la question précédente, et que chaque élément i E E représente un placement possible de domino. Chaque case de l'échiquier est représentée par un entier j tel que 0 5 j < 102, les cases étant numérotées de gauche à droite, puis de haut en bas. On se donne une matrice de booléens m de taille n >< 112. Le booléen m...- vaut true si et seulement si la ligne i correspond a un placement de domino qui occupe la case j . (On suppose avoir rempli ainsi la matrice m, qui est une variable globale.) Un élément s de P(P(E)) représente un ensemble de lignes de la matrice m. Il correspond à un pavage si et seulement si chaque case de l'échiquier est occupée par exactement un domino, i,e. si et seulement si pour toute colonnej il existe une unique ligne 71 EUR 3 telle que m['i] [j] = true. On parle alors de couverture exacte de la matrice 111. Question 14 Ecrire une fonction colonne qui prend en argument un entier j' avec 0 S j < p2, et qui renvoie un arbre combinatoire A tel que, pour tout 87 3 & S(A) si et seulement si il existe un unique i EUR 3 tel que m[i][j] = true. On garantira une complexité O(n). (* Caml *) colonne: int --> ac
{ Pascal } function colonne(j: integer) : ac;

Question 15 En déduire une fonction pavage qui renvoie un arbre combinatoire A 
tel que le
cardinal de S (A) est égal au nombre de façons de paver l'échiquier, et majorer 
le coût de pavage
en fonction de n.

(* Caml *) pavage: unit --> ac
{ Pascal } function pavage : ac;

Partie V. Tables de hachage

Dans cette partie, on explique comment réaliser les structures de données 
tablel et table2,
qui ont notamment permis d'obtenir des fonctions inter et cardinal efficaces. 
L'idée consiste

a utiliser des tables de hachage.

On abstrait le problème en considérant qu'on cherche a construire une structure 
de table
d'association pour des clés d'un type clé et des valeurs d'un type valeur, ces 
deux types étant
supposés déjà définis. On se donne un entier H > 1 et on suppose l'existence 
d'une fonction
hache de coût constant, des clés vers les entiers7 telle que pour toute clé k

0 5 hache(k) < H. L'idee consiste alors a utiliser un tableau de taille H et a stocker dans la case i les entrees correspondant a des cles k pour lesquelles hache(k) = i. Chaque case du tableau est appelee un seau. Comme plusieurs cles peuvent avoir la meme valeur par la fonction hache, un seau est une liste d'entrees, c'est-a-dire une liste de couples (cle, valeur). On adopte donc le type suivant : { Pascal } type table = array[0..H-1] of ^seau; type seau = record k: cle; v: valeur; suivant: ^seau; end; (* Caml *) type table == (cle * valeur) list vect;; On suppose par ailleurs qu'on peut comparer deux cles a l'aide d'une fonction egal a valeurs dans les booleens, egalement de cout constant, telle que pour toutes cles k1 et k2 si egal(k1 , k2 ) alors hache(k1 ) = hache(k2 ). (2) Question 16 Ecrire une fonction ajoute qui prend en argument une table de hachage t, une cle k et une valeur v, et ajoute l'entree (k, v) a la table t. On ne cherchera pas a tester si l'entree (k, v) existe deja dans t et on garantira une complexite O(1). (* Caml *) ajoute: table -> cle -> valeur -> unit
{ Pascal } procedure ajoute(t: table; k: cle; v: valeur);

Question 17 Ecrire une fonction present qui prend en argument une table de 
hachage t et
une cle k, et qui teste si la table t contient une entree pour la cle k.
(* Caml *) present: table -> cle -> bool
{ Pascal } function present(t: table; k: cle) : boolean;

Question 18 Ecrire une fonction trouve qui prend en argument une table de 
hachage t et une
cle k, et qui renvoie la valeur associee a la cle k dans t, en supposant 
qu'elle existe.
(* Caml *) trouve: table -> cle -> valeur
{ Pascal } function trouve(t: table; k: cle) : valeur;

Question 19 Sous quelles hypotheses sur la valeur de H et la fonction hache 
peut-on esperer
que le cout des fonctions ajoute, present et trouve soit effectivement O(1) ?

Partie VI. Construction des arbres combinatoires
Il reste enfin a expliquer comme realiser une fonction de hachage, une fonction 
d'egalite et
une fonction cons sur les arbres combinatoires, qui soient toutes les trois de 
complexite O(1).

7

L'idee consiste a associer un entier unique a chaque arbre combinatoire A, note 
unique(A), et
a garantir la propriete suivante pour tous arbres combinatoires A1 et A2 :
A1 = A2 si et seulement si unique(A1 ) = unique(A2 ).

(3)

Pour cela, on pose unique(Zero) = 0 et unique(Un) = 1. Pour un arbre A de la 
forme i  A1 , A2 ,
on choisira pour unique(A) une valeur arbitraire superieure ou egale a 2, 
stockee dans le noeud
de l'arbre. On modifie donc ainsi la definition du type ac :
(* Caml *)
type unique == int;;
type ac = Zero | Un
| Comb of unique * int * ac *
ac;;

{ Pascal }
type ac = ^noeud;
noeud = record unique: integer;
element: integer; gauche: ac; droit: ac;
end;

On propose alors la fonction hache suivante sur les arbres combinatoires :
hache() = 0,
hache() = 1,
hache(i  A1 , A2 ) = (192 × i + 19 × unique(A1 ) + unique(A2 ))

mod H.

(Le choix de cette fonction, et du coefficient 19 en particulier, releve de 
considerations pratiques
uniquement.) De meme, on propose la fonction egal suivante sur les arbres 
combinatoires :
egal(, ) = true,
egal(, ) = true,
egal((i1  L1 , R1 ), (i2  L2 , R2 )) = i1 = i2 et unique(L1 ) = unique(L2 )
et unique(R1 ) = unique(R2 ),
egal(A1 , A2 ) = false, sinon.

Question 20 Montrer que les fonctions hache et egal ci-dessus verifient bien la 
propriete (2).
Question 21 Proposer un code pour la fonction cons qui garantisse la propriete 
(3), en supposant que les arbres combinatoires sont exclusivement construits a 
partir de Zero, Un et de la
fonction cons. On garantira un cout O(1) en utilisant une table globale de type 
table1 contenant les arbres combinatoires deja construits. (On suppose que le 
type table1 et ses operations
ont ete adaptes au nouveau type ac.)
(* Caml *) cons: int -> ac -> ac -> ac
{ Pascal } function cons(i: integer; a1: ac; a2: ac) : ac;

Pour resoudre le probleme de pavage de la partie IV, on construit au total 22 
518 arbres
combinatoires. Si on prend H = 19 997 et la fonction de hachage proposee 
ci-dessus, la longueur
des seaux dans la table utilisee par la fonction cons n'excede jamais 7. Plus 
precisement, les
arbres se repartissent dans cette table de la maniere suivante :
8

longueur du seau
nombres de seaux
de cette longueur

0

1

2

3

4

5

6

7

6450

7340

4080

1617

400

96

11

3

Question 22 Quel est, dans cet etat, le nombre moyen d'appels a la fonction 
egal realises par
un nouvel appel a la fonction cons
1. dans le cas ou l'arbre doit etre construit pour la premiere fois ;
2. dans le cas ou l'arbre apparaissait deja dans la table ?
On donnera les valeurs avec deux decimales, en les justifiant soigneusement.

Note : La solution au probleme du pavage est obtenue en quelques secondes avec 
la
technique proposee ici ; on trouve 12 988 816. L'interet de cette technique est 
qu'elle
s'applique facilement a d'autres problemes de combinatoire. Par ailleurs, le 
probleme
de la couverture exacte peut etre attaque par d'autres techniques, telle que 
les  liens
dansants  de Knuth.

9