X Informatique MP 2001

ÉCOLE POLYTECHNIQUE FILIÈRE MP

CONCOURS D'ADMISSION 2001

COMPOSITION D'INFORMATIQUE

(Durée : 4 heures)
L'utilisation des calculatrices n'est pas autorisée

***

AVERTISSEMENT. On attachera une grande importance à la clarté, a la précision 
et a la
concision de la rédaction.

On définit les arbres (binaires complets) de la façon suivante :

-- Une feuille est un arbre.
-- Si g et ci sont deux arbres, le couple (g, d) est un arbre.

Un arbre de la forme (g, d) est un noeud interne, dont 9 est le fils gauche et 
d le fils droit. Par
la suite, on note An l'ensemble des arbres possédant u feuilles (u 2 l). Les 
feuilles d'un arbre
de An sont numérotées de 1 a n dans l'ordre d'un parcours postfixe (dit aussi 
en-profondeur

d'abord) et de gauche a droite.

Un flot f de taille n est une suite de u entiers égaux à 1, 2, ou 3. Pour un 
arbre a de A,,
fixé, cette suite définit une fonction des sous--arbres de a dans les entiers, 
également notée f .
La fonction f associe le i--ème entier du flot f a la i-ème feuille de l'arbre 
a, et elle s'étend
récursivement aux noeuds internes, par la formule :

f ((9» d)) = f (9) + f (60 (modulo 4) ,

c'est--à--dire que si a = (g, d), alors f (a) est le reste de la division 
euclidienne par 4 de la somme
f(g) + f(d). On note F,, l'ensemble des flots de taille u. Un flot f de F,, est 
dit compatible
avec un arbre a de An si, pour tout noeud interne a: de a, on a : f (LE) # 0. 
La figure suivante
représente un arbre a a 5 feuilles (dont les noeuds internes sont désignés par 
sa, . . . ,ÇC4), et deux
flots. On notera que le premier flot est compatible avec a, tandis que le 
second ne l'est pas, car

f2(333) = O.

Les arbres sont représentés en machine par la structure de donnée usuelle :

(* Caml *) { Pascal }
type
type arbre = arbre = "cellule_arbre ;
| Feuille cellule_arbre = record
| Interne of arbre * arbre gauche, droite : arbre
end ;

En Pascal, une feuille est représentée par nil et on pourra utiliser la 
fonction noeud, constructeur
des noeuds internes :

function noeud (gauchezarbre ; droite arbre) : arbre ;
var r:arbre ;
begin
new(r) ;
r".gauche := gauche ; r".droite := droite ;
noeud := r
end ;

Les flots sont représentés en machine par des tableaux d'entiers.

(* Caml *) {Pascal}
const NMAX=... ;

t fl t = ' t t
ype 0 in vec type flot = array [l..NMAX] of integer ;

L'attention des candidats qui composent en Caml est attirée sur ce que les 
indices des tableaux
commencent a zéro. Les candidats qui composent en Pascal pourront supposer que 
la constante
NMAX est toujours plus grande que les valeurs de n utilisées en pratique.

NOTE. La plupart des fonctions demandées dans ce problème sont valides sous 
certaines
hypothèses portant sur leurs arguments, hypothèses qui sont énoncées à chaque 
question. Le
code écrit ne doit jamais vérifier les hypothèses portant sur les arguments, il 
doit au contraire
indiquer clairement comment il les utilise le cas échéant.

Partie I. Vérification de la compatibilité des flots.

Question 1. Ecrire une fonction compte_feuilles qui prend un arbre en argument 
et
renvoie le nombre de ses feuilles.

(* Caml *) ' {Pascal}

compte_feuilles : arbre --> int function compte_feuilles (azarbre) : integer

Question 2._ Écrire une fonction compatible qui prend en arguments un arbre a 
de A,, et
un flot f de F... et qui décide si f est compatible avec a. Cette fonction 
devra arrêter d'effectuer
des additions modulo 4 dès qu'un noeud interne oe vérifiant f(oe) : 0 est 
découvert.

(* Caml *) {Pascal}

compatible : function
arbre --> flot --> bool compatible(azarbre ; f:flot) : boolean

Question 3. Dans cette question et la suivante, a désigne un arbre de An et f 
un flot de F.".

a) Montrer que a possède n -- 1 noeuds internes.

b) On suppose que a n'est pas réduit à une feuille et on l'écrit a : (g,d). 
Soit un flot f
compatible avec a. Donner les valeurs possibles du couple ( f(g), f(d)) selon 
les valeurs possibles
de f (a).

c) Soit ?) un entier égal à 1, 2 ou 3. Calculer F (a, o), nombre de flots f 
compatibles avec a et
tels que f(a) : o. En déduire le nombre de flots compatibles avec a.

Question 4. Pour un a et un f donnés, la fonction compatible de la question 2 
effectue
N+(a, f) additions modulo 4 (avant de trouver un noeud interne a; tel que f 
(a:) = 0 ou de revenir
a la racine de a). Sur l'exemple du préambule, on a N+(a, f1) : 4 et N+(a, f2) 
: 3. Pour tout
entier le, avec 1 S le S n ---- 1, on définit yk(a) comme étant le nombre de 
flots f incompatibles
avec a et tels que N+(a, f) = le.

a) Calculer y1(a). Sa valeur dépend elle de la forme de l'arbre a ?

b) Montrer qu'il existe un arbre a' possédant n -- 1 feuilles et tel que, pour 
tout le 2 2, on a
yk(a) : 2yk_1(a' ) En déduire l'expression de Vk(a) dans le cas général.

c) On admet que N+(a, f ) est une bonne mesure de la complexité de l'appel de 
compatible
sur a et f. En considérant une distribution équiprobable des flots, la 
complexité moyenne de
cette fonction pour a fixé est définie comme

1
23--nN+(OEaf)
f

où f parcourt l'ensemble des 3" flots de taille n. Calculer cette complexité 
moyenne, ainsi que
sa limite lorsque n _, oo.

NOTE. On pourra utiliser sans la démontrer la formule suivante :

TL

ZIÇOZIÇ_1 _ 1 ----oz"(n+ 1 --noz)

k=1 (1 -- d)2

Partie II. Triangu1ation des polygones.

Soit P,, un polygone convexe a n côtés (n 2 3), dont les sommets sont numérotés 
de 1 a n en
suivant le sens trigonométrique. Une corde est un segment qui joint deux 
sommets non--contigus
du polygone. Une subdivision de Pn est un ensemble de segments qui comprend au 
moins les
côtés de P,, plus un certain nombre de cordes. Une subdivision est dite propre 
lorsque toutes
ses cordes sont non--sécantes (sauf éventuellement en leurs extrémités). Une 
subdivision propre
définit un ensemble de faces, qui sont les polygones {nécessairement convexes) 
formés a l'aide
de ses segments et dont l'intérieur ne contient aucun autre segment.

Une triangulation de Pn est une subdivision propre dont les faces sont des 
triangles. Voici
par exemple une triangulation de P8 :

En revanche, les deux dessins suivants ne décrivent pas des triangulations : le 
premier parce
que la corde qui relie les sommets 4 et 8 coupe trois autres cordes; le second 
parce que la face
dont les sommets sont 1, 2, 3 et 6 n'est pas un triangle.

Un segment quelconque reliant deux sommets de Pn est codé par le couple (71, 
j),i < j de ses extrémités, et un ensemble de segments par la liste de ses éléments. On notera que les éléments d'une liste qui représente un ensemble sont supposés deux a deux distincts. (* Caml *) {Pascal} type segment = record debut,fin : integer ,end ; segments = "cellule_segments ; cellule_segments = record type segment == int * int and segments == segment list tete : segment ; suite : segments end ; En Pascal, on pourra utiliser le constructeur des cellules de liste cons : function cons(tetezsegment ; suite:segments) : segments ; Ainsi, la triangulation donnée en exemple peut être codée par [(1, 2) ; (1, 3) ; (1, 6) ; (1, 8) ; (2, 3) ; (?>, 4) ; (3,5); (3, 6) ; (4, 5) ; (5, 6) ; (6, 7) ; (6,8) ; (7, 8)], tandis 
que l'ensemble de ses cordes peut
être codé par l(173); (1,6); (3,5); (3,6); (6,8)l-

Question 5. Montrer que le nombre de cordes d'une triangulation de Pn est une 
fonction
de n et donner son expression p(n).

Question 6. On admet qu'un ensemble de p(n) cordes non--sécantes (sauf 
éventuellement
en leurs extrémités) définit une triangulation de Pn. Ecrire une fonction 
triangulation, de

complexité O(n2), qui prend en arguments un entier n et un ensemble de cordes C 
de P... et qui
décide si C définit une triangulation de Pn.

(* Caml *) {Pascal}
triangulation : function
int --> segments --> bool triangulation(nzinteger ; c:segments) : boolean

Conformément à la note préalable, il n'appartient pas a la fonction 
triangulation de vérifier
que c est bien une liste de segments distincts, dont chaque élément est bien 
une corde de Pn.

Question 7. On dessine une triangulation en représentant les n ----- 1 côtés 
(k,k + 1),
1 5 k < n, du polygone, sous forme d'un segment de longueur n ---- 1, et chaque corde (i, j), ainsi que le côté (1, n), comme un arc reliant @ à j. Voici le dessin représentant la triangulation donnée en exemple : AAA 1 2 3 4 5 6 7 8 a) Utiliser cette représentation de l'exemple de triangulation pour lui associer un arbre a 7 feuilles et dont les noeuds internes et les feuilles correspondent aux segments de la triangula-- tion. b) Généraliser le procédé en décrivant comment on peut associer un arbre a de An_1 a une triangulation t de Pn. On raisonnera en termes de polygones, il pourra être utile de remarquer que le côté (1, n) est particulier. c) Écrire une fonction triangle_arbre, qui prend en arguments un entier n et une triangu-- lation t de P,, et renvoie un arbre qui représente 75. (* Caml *) {Pascal} triangle_arbre : function int -> segments --> arbre triangle_arbre(nzinteger ; t:segments)zarbre

Question 8. Écrire la fonction inverse de la fonction de la question 
précédente. O'est--à--dire,
programmer la fonction arbre_triangle qui prend en argument un arbre a de An_1 
et renvoie
la triangulation de Pn représentée par a.

(* Caml *) {Pascal}
arbre_triangle : function
arbre --> segments arbre_triangle (azarbre) : segments

NOTE. On ne cherchera pas a prouver que les fonctions arbre_triangle et 
triangle_arbre
sont inverses l'une de l'autre.

Partie III. Les quatre couleurs.

Le problème des quatre couleurs consiste à colorier une carte géographique avec 
au plus
quatre couleurs, de telle sorte que deux pays voisins soient coloriés 
différemment. Le théorème
des quatre couleurs affirme qu'une telle coloration est possible pour toute 
carte dessinée sur une

sphère.

On admettra que la coloration d'une carte se ramène a la coloration d'une 
double triangula--
tion d'un polygone P... qui a son tour se ramène à la construction d'un flot 
compatible avec deux
arbres donnés de An_1. Le théorème des quatre couleurs exprime qu'un tel flot 
existe toujours.
L'objet de cette partie est de vérifier expérimentalement ce théorème.

Étant donné un ensemble fini E, de cardinal (, une génération de E est une 
bijection de
l'intervalle entier [0 . . . c -- 1} dans E.

Question 9. Soient E et E' , deux ensembles finis, générés respectivement par 
çb et d)' .
a) Donner une génération du produit cartésien E >< E' . b) On suppose que E et E' sont disjoints. Donner une génération de l'union E U E' . c) On suppose que E et E' sont disjoints et de même cardinal. Donner une autre génération de l'union E U E' , qui n'utilise pas la valeur du cardinal de E. Question 10. On note Na(n) le nombre d'arbres à n feuilles (Na(n) est le cardinal de An). a) Exprimer Na(n) sous forme d'une récurrence faisant intervenir les Na(i) avec l 5 i < n. En déduire une fonction (procédure en Pascal) calcule_na qui prend un entier n en argument et range les Na(i) avec l 5 l 5 n, dans un tableau global d'entiers na réputé de taille suffisante. (* Caml *) {Pascal} calcule_na : int --> unit procedure calcule_na(nzinteger)

b) Construire une génération de A... c'est--à--dire écrire une fonction 
int_arbre qui prend
en arguments un entier n et un entier k compris entre zéro et Na(n)--l et 
renvoie un arbre a
77. feuilles.

(* Caml *)

int_arbre : int --> int --> arbre

{ Pascal }

function int_arbre (n,k:integer) : arbre

Question 11. Étant donnés a, un arbre a n feuilles, et u, un entier égal à l, 2 
ou 3, il est
rappelé (cf. question 3) que F (a, u) est le cardinal de l'ensemble des flots f 
compatibles avec a
et tels que f(a) : u.

Construire une génération de cet ensemble, c'est-à--dire écrire une fonction 
int_flot qui
prend en arguments un entier n, un arbre a a n feuilles, un entier 1) compris 
entre 1 et 3 et un
entier le compris entre 0 et F (a, u) -- l, et qui renvoie un flot f de taille 
n tel que f (a) = 1). En
Caml on se conformera au type suivant :

int_flot : int --> arbre --> int --> int --> flot

En Pascal, le flot sera renvoyé par le truchement d'un argument supplémentaire 
passé par
variable.

procedure int_flot (nzinteger ; a:arbre ; v,k:integer ; var f:flot)

Question 12.
a) Écrire une fonction (procédure en Pascal) trouve_compatible qui prend en 
arguments un
entier n et deux arbres a n feuilles a et b, et qui renvoie un flot compatible 
à la fois avec a et b.
La terminaison de trouve_compatible doit être garantie.

(* Caml *) {Pascal}

_ procedure
trouve_compat1ble

_ trouve_compatible
1nt --> arbre --> arbre --> flot

(nzinteger ; a,b:arbre ; var f:flot)

b) Écrire une fonction (procédure en Pascal) quatre_couleurs qui prend en 
argument un
entier n, tire au hasard deux arbres a n feuilles et renvoie un flot compatible 
avec ces deux
arbres.

(* Caml *) {Pascal}
procedure

quatre_couleurs : int --> flot _
quatre_couleurs (n:1nteger ; var f:flot)

On pourra utiliser la fonction random_int qui prend un entier maæ en argument 
et renvoie un
entier aléatoire compris entre zéro et maa: -- 1.