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)
                    

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