X Informatique MP 2001

Thème de l'épreuve Arbres binaires complets, triangulations, théorème des quatre couleurs
Principaux outils utilisés parcours postfixe et infixe, codage des triangulations par des arbres, fonctions associant des valeurs entières à des nœuds, implémentation en Caml et en Pascal

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

(PDF non trouvé ! |/net/www/doc-solus.fr/www//prepa/sci/adc/pdf/rapports.pdf/2001/MP_INFO_X_1_2001.rapport.pdf|)

Énoncé obtenu par reconnaissance optique des caractères


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

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



X Informatique MP 2001 -- Corrigé
Ce corrigé est proposé par Codrin Nichitiu (Maître de conférence) ; il a été 
relu
par Olivier Bertrand (ENS Lyon) et Xavier Goaoc (ENS Cachan).

Ce sujet comporte trois parties, convergeant vers le célèbre problème des quatre
couleurs. Le candidat est amené à étudier deux concepts auxiliaires, les flots 
dans les
arbres et les triangulations, avant de les utiliser ensemble.
L'étude est faite à travers quelques algorithmes de vérification et de 
génération
qui doivent être implémentés en Camllight ou en Pascal, et à travers la 
démonstration
de quelques propriétés simples de dénombrement.
Les flots sont définis ici sur des arbres binaires complets enracinés comme 
étant
des fonctions donnant à chaque noeud une valeur parmi 0, 1, 2 et 3. Plus 
précisément,
ces fonctions sont calculées à partir de valeurs initialement données aux 
feuilles (1, 2
ou 3), par une somme modulo 4 des valeurs des fils pour chaque noeud. On remonte
ainsi vers la racine et une notion de compatibilité est introduite (aucun sommet
interne de valeur nulle). L'étude se poursuit alors autour de quelques 
propriétés.
La deuxième partie introduit les triangulations des polygones convexes. On 
représente tout d'abord une triangulation par la liste de ses cordes (segments 
intérieurs au
polygone), puis par un arbre. Le candidat doit faire le lien, et écrire des 
programmes
de traduction d'une représentation vers l'autre.
Enfin, la troisième partie demande d'écrire des programmes d'énumération 
d'arbres,
de flots compatibles et de flots compatibles pour deux arbres (au sens des 
définitions
précédentes).

Indications

Partie I
I.1 Effectuer un parcours en profondeur, en incrémentant un compteur à chaque
feuille rencontrée.
I.2 Comme à la question précédente, un parcours en profondeur peut être utilisé,
avec arrêt immédiat. Attention à la numérotation des feuilles.
I.3.a La preuve est immédiate en procédant par récurrence.
I.3.b Énumérer tout simplement les cas, en éliminant ceux qui annulent le flot.
I.3.c Combiner les réponses aux deux questions précédentes, en utilisant 
l'indépendance des choix.
I.4.a Nombre minimum d'additions, donc valeurs possibles pour un groupe de
sommets, et libres pour les autres.
I.4.b Utiliser le fait que le nombre minimum d'additions est au moins 2 pour 
avoir
une propriété sur les feuilles et l'exploiter récursivement.
I.4.c Appliquer les formules précédemment obtenues.
Partie II
II.5 Raisonner par récurrence en analysant les cas possibles.
II.6 Vérifier exactement ce que dit l'énoncé. Pour vérifier que deux cordes ne
sont pas sécantes, analyser les trois cas possibles pour l'ordonnancement
circulaire des extrémités (sommets).
II.7.a Les feuilles peuvent être les côtés (sauf (8, 1)). Observer une relation 
entre
les extrémités des cordes (dessinées avec un arc) et celles des arcs (ou côtés)
« englobés ».
II.7.b Essayer de formuler la relation de manière explicite, pour définir 
l'arbre en
général, même si on le fait à partir des feuilles.
II.7.c Essayer maintenant de partir de la racine (comme toujours, on suppose 
récursivement que pour les fils le travail a été fait et l'on cueille ce qui est
nécessaire pour construire le noeud courant). Observer que les noeuds ne
contiennent aucune information explicite : seule la structure de l'arbre est
suffisante.
II.8 Un simple parcours en profondeur, avec un compteur pour les feuilles, 
suffit.
Partie III
III.9.a Penser à l'écriture binaire.
III.9.b Accoler les intervalles.
III.9.c Penser à la parité.
III.10.a Les deux fils d'un noeud peuvent être choisis indépendamment l'un de 
l'autre,
et il faut que la somme totale de leurs feuilles soit égale à la somme initiale
n.
III.10.b Utiliser les questions précédentes et trouver le lien entre somme, 
produit et
opérations ensemblistes correspondantes.

III.11 La question I.3.c donne la cardinalité de l'ensemble ; la décomposition 
en
chiffres dans la base qui s'impose permet alors de choisir, dans un parcours
en profondeur, les valeurs à imposer dans chaque noeud, selon la table de la
question I.3.b.
III.12.a Générer tous les flots pour un arbre, puis vérifier.
III.12.b Utiliser la fonction précédente.

I.

Vérification de la compatibilité des flots

I.1 La fonction effectue un simple parcours en profondeur, incrémentant à chaque
feuille rencontrée un compteur. La définition récursive peut être lue comme 
suit :
· un arbre réduit à un noeud comporte une feuille (ce noeud) ;
· un autre arbre a = (f, g) a un nombre de feuilles égal à la somme des nombres
de feuilles de f et de g.
Version Camllight
type arbre = Feuille | Interne of arbre * arbre ;;
let rec compte_feuilles = function
Feuille
-> 1
| Interne(f,g) -> (compte_feuilles f) + (compte_feuilles g);;

Version Pascal
function compte_feuilles (a: arbre): integer;
begin
if (a = nil) then compte_feuilles := 1
else compte_feuilles :=
compte_feuilles(a^.gauche)
+ compte_feuilles(a^.droite)
end; {compte_feuilles}
I.2 La fonction de test part des feuilles, selon un parcours en profondeur, mais
ne continue celui-ci que si aucun noeud de flot nul n'est découvert. Il faut 
pouvoir
« numéroter » les feuilles, pour bien leur associer les valeurs du tableau 
d'entiers
qu'est le flot. Ceci peut être facilement fait à l'aide d'un parcours postfixe, 
avec un
compteur de feuilles rencontrées, donnant aussi l'indice dans le tableau du 
flot.
Version Camllight
type flot == int vect;;
let compatible a (f: flot) =
let rec compat_parcours i = function
(* pour une feuille, c'est toujours bon, *)
(* car non nul par définition
*)
Feuille
-> (f.(i),true,i+1)
(* pour un noeud interne, on vérifie chaque fils *)
| Interne (f,g) ->
(match (compat_parcours i f) with (* le fils gauche *)
(_,false,_) -> (-1,false,-1)
| (n,true,j) ->
(* le fils droit *)
(match (compat_parcours j g) with
(_,false,_) -> (-1,false,-1)
| (p,true,k) -> let r = ((n+p) mod 4) in
(* on vérifie le noeud lui-même *)
(r,(r!=0),k)