X Informatique MP 2003

Thème de l'épreuve Optimisation du routage dans un réseau arborescent
Principaux outils utilisés parcours d'arbre, récursivité
Mots clefs étiquette, ppac

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

(télécharger le PDF)
                    

Énoncé obtenu par reconnaissance optique des caractères


ÉCOLE POLYTECHNIQUE ' ' FILIÈRE MP OPTION INFORMATIQUE CONCOURS D'ADMISSION 2003 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. On attachera une grande importance à. la clarté, a la précision et a la concision de la rédaction. *** Routage dans un. réseau arborescent Dans ce problème on aborde une question soulevée dans la conception des réseaua: : il s'agit d'afiecter des adresses distinctes aua: noeuds d'un réseau de façon telle que la route entre deuæ noeuds puisse être déterminée par un calcul utilisant uniquement leurs deuoe adresses, sans ré- férence a une connaissance globale du réseau. On s'intéresse plus particulièrement auoe réseauoe ayant une forme d'arbre. Le problème est composé de trois parties indépendantes. Dans tout le problème un n-arbre est un arbre dont l'ensemble des sommets (on dit aussi parfois les noeuds) est {O, 1, . .. ,n ---- l}, et dont la racine est 0. Chaque sommet a possède un père noté pere[a], par convention la racine est son propre père, ainsi pere[0] : O. L'ensemble des n--arbres est noté A(n). L'ensemble des ancêtres du sommet a est constitué de a et des ancêtres de son père pere[a] ; la racine 0 est ainsi ancêtre de tous les sommets de l'arbre. Le sous-arbre de racine a, noté A... est formé de tous les sommets de l'arbre A dont a est ancêtre. Les fils d'un sommet a sont ainsi les b # 0 tels que pere[b] : a, (attention la racine n'est pas fils d'elle même). Une feuille est un sommet qui n'a pas de fils. La hauteur (on dit aussi parfois profondeur) d'un sommet a, notée h(a) est un entier égal à 0 si a est la racine, elle est égale à la hauteur du père de a augmentée de 1 sinon. Le plus proche ancêtre commun à. deux sommets a et b, noté ppac(a, b), est le sommet de hauteur maximale qui est a la fois ancêtre de a et de b. Noter que si a est ancêtre de b alors ppac(a, b) = a. Dans tout le problème, on considère que l'entier n est fixé, d'autre part pour un tableau t, t[i] dénote l'élément d'indice i; une liste contenant les entiers 120, 5121, . .. ,a:p est représentée par (oe0,oe1, . .. ,æp); la liste vide est notée < ). On utilisera pour un n--arbre A : -- Un tableau de listes d'entiers fils de taille n tel que fils[i] est la liste des fils de z'. -- Un tableau d'entiers pere de taille n tel que pere[i] est le père de i. On a ainsi en Caml et en Pascal let n = ..... ;; const n = ...; type vint = array[0..n--1] of integer ; type vint == int vect ;; lint = "cellule; type lint == int list ;; cellule = record type vlint == lint vect ;; val : integer; suiv : lint; end; vlint = array[0..n--1] of lint; On pourra utiliser en Pascal le constructeur pour les listes qui est donné ci--dessous : function cons (contenu : integer; suivant : lint) : lint; begin var res : lint; new(res); res".val := contenu; res".suiv := suivant; cons := res; end; FIG. 1: Un arbre A E A(8) et un arbre binaire complet B E B(2). Les tableaux pere et fils de l'arbre A situé a gauche de la Figure 1 sont donnés par : I. FONCTIONS ÉLÉMENTAIRES Question 1. Calculer ppac(i, j ) pour tous les couples de sommets de l'arbre A donné plus haut. On présentera le résultat sous forme d'un tableau de 8 lignes et 8 colonnes tel que la case sur la ligne z' et la colonne j contienne le plus proche ancêtre de 71 et j . Question 2. Ecrire une fonction 1 hauteur : vint --> int --> int function hauteur (pere : vint; a : integer) : integer qui étant donné un sommet a d'un arbre, pour lequel on donne son tableau des pères7 calcule la hauteur de ce sommet. Question 3. Ecrire une fonction filsEnPere : vlint --> vint procedure filsEnPere (fils : vlint; var pere : vint) qui a partir d'un arbre, donné par ses listes de fils, calcule le tableau des pères. Question 4. Ecrire une fonction ppacMemeH : vint --> int -> int --> int function ppacMemeH (pere: vint; a, b: integer) : integer qui calcule le plus proche ancêtre commun de deux sommets a et b supposés de même hauteur dans un arbre pour lequel on donne le tableau des pères. En déduire une fonction ppac qui effectue le même calcul pour deux sommets a et b n'ayant pas nécessairement la même hauteur. 11. ARBRES BINAIRES COMPLETS Un arbre binaire complet est un arbre dans lequel tout sommet qui n'est pas une feuille a exactement deux fils, et tel que toutes les feuilles sont a la même hauteur. On note B(h) l'ensemble des n-arbres binaires complets dans lesquels les feuilles sont à. hauteur h. Un exemple d'arbre binaire complet B est donné a droite de la Figure 1. Question 5. Déterminer pour 0 { [EUR { h le nombre sk de sommets de hauteur lc dans un arbre B de B(h), justifiez votre réponse. En déduire le nombre n de sommets d'un arbre de B(h) en fonction de h. Dans la suite B est un arbre de B(h) ayant n sommets; a chaque sommet a de B on associe une étiquette Ë(a) EUR {1,2, . .. ,n} satisfaisant la condition suivante : pour chaque sommet & ayant pour liste de fils (b, c) : æaÈx £(u) < Æ(a) < 52%. £(v) 1Dans tout l'énoncé du problème les déclarations de fonctions et procédures sont proposées d'abord en Caml puis en Pascal. Question 6. Calculer les valeurs de EUR(a) pour les 7 sommets de l'arbre binaire complet représenté sur la droite de la Figure 1 : l'ordre des fils dans les listes correspond à la lecture de gauche a droite de la figure. Question 7. Ecrire une fonction etiquettes : v1int --> vint procedure etiquettes (fils : vlint; var etiq : vint) qui calcule les étiquettes EUR(a) pour tous les sommets d'un arbre de B (h) donné par ses listes de fils. Question 8. Un arbre B de B(h) de racine 0 ayant pour liste de fils (a, b) se décompose en deux sous--arbres Ba et Bb. Déterminer les valeurs de £(O), de EUR(a) et de £(b) pour les fils a et b de la racine. Question 9. Démontrer que si a et b sont deux sommets quelconques de B alors 7° = EUR(ppac(a, b)) est déterminé de manière unique a partir de p = EUR(a) et q = EUR(b) par la propriété suivante : 7° est parmi les entiers compris (au sens large) entre p et q celui possédant le plus grand diviseur qui soit une puissance de 2. Question 10. Donner une fonction récursive mu : int --> int --> int function mu (p, q : integer) : integer qui détermine ?" = Ë(ppac(a, b)) a partir de p = EUR(a) et q = EUR(b) ; on supposera que p { q. Votre fonction doit être de complexité O(log2(q -- p)). 111. ARBRES GÉNÉRAUX Dans cette partie on utilise les définitions et notations suivantes : Dans un arbre A le poids w[a] d'un sommet a, est le nombre de sommets du sous--arbre Aa de racine a, ainsi w[a] = 1 si et seulement si a est une feuille, noter que w[0] = n (c'est le nombre de sommets de A). Un arbre A est dit gauche si pour chaque sommet a (qui n'est pas une feuille) le premier élément de la liste des fils est de poids supérieur ou égal à celui de tous les autres sommets de cette liste. Dans un arbre gauche, le premier élément de la liste des fils d'un sommet est dit lourd, les autres sommets sont dits légers. La racine est un sommet léger. O léger . lourd FIG. 2: Sommets lourds et légers. Question 11. Ecrire une fonction poids : vlint --> vint procedure poids(fils : vlint; var poids : vint) qui calcule les poids de tous les sommets d'un arbre donné par ses listes de fils. Puis une fonction : gauchir : vlint -> vint --> vlint procedure gauchir (fils : vlint; W : vint; var filsG : vlint) qui calcule un arbre gauche obtenu en réordonnant les fils de chaque sommet de façon telle que le premier fils soit de poids supérieur ou égal à celui des autres. Sont donnés dans cette fonction les listes des fils et le tableau des poids des sommets de l'arbre. Question 12. Soit a un sommet léger d'un arbre gauche A et b son père, montrer que w[b] > 2w[a]. En déduire que le nombre d'ancétres légers de a est inférieur à 1 + log2 n. On utilise dans toute la suite la notion de cime d'un sommet. -- Si a est léger cime[a] est égale à pere[a]. -- Si a. est lourd cime[a] est le plus proche ancêtre de a qui est léger. Ainsi en raison de nos conventions cime[0] = 0. On appelle A' l'arbre gauche obtenu en appli- quant la fonction gauchir à l'arbre A de la figure 1. Les cimes des sommets de l'arbre A' sont alors données par le tableau suivant : "..." -u-uuuunn Question 13. Ecrire une fonction cimes : vlint --> vint procedure cimes (fils : vlint; var cime : vint) qui calcule les sommets cimes de tous les sommets à partir des listes de fils d'un arbre gauche. On se propose d'attribuer des étiquettes aux sommets d'un arbre gauche A. Pour cela on commence par construire deux tableaux d'entiers tl et 72 associés aux sommets. Le tableau tl est tel que t1[0] = 0 et t1[a] = 72 si a est le i-ème élément de la liste des fils de son père. Le tableau t2 est tel que t2[a] = 0 si a est léger et t2[a] = t2 [pere[a]] + 1 si a est lourd. Les étiquettes À(a) des sommets sont alors des listes d'entiers construites de la façon suivante : À(O) = (> et pour a 74 0 À(a) = À(cime[a]) o (tl[a],t2[a]> dans cette formule @ dénote la concaténation des listes. Question 14. Donner l'arbre A' défini a la question 12; puis donner les valeurs de t2[a] pour tous les sommets a; calculer enfin leurs étiquettes À(a). Question 15. Ecrire une fonction etiquettes : vlint --> vint -> vlint procedure etiquettes (fils : Vlint; cime : vint; var lambda : vlint) qui calcule les étiquettes des sommets d'un arbre gauche donné par ses listes de fils et pour lequel on donne aussi le tableau des cimes des sommets. En Caml on pourra utiliser l'opérateur @ et en Pascal la fonction : function concat (x, y : lint): lint; qui calcule laconcaténation de deux listes et dont on ne demande pas le corps. Question 16. Ecrire une fonction : trouve : Vlint -> lint --> int function trouveSommet(fils : Vlint; etiq : lint): integer qui, à partir de l'étiquette d'un sommet d'un arbre gauche A et des listes de fils des sommets de cet arbre, détermine ce sommet. Question 17. &) Montrer que, pour tout sommet a d'un arbre, la longueur de l'étiquette À(a) est majorée par 4 fois le nombre de ses ancêtres légers. b) Indiquer comment on calcule À(ppac(a, b)) a partir des deux listes u = À(a) et u = À(b) ; on ne demande pas de justifier la réponse a cette question. On a donné dans ce problème une technique permettant d'étiqueter les noeuds des sommets d'un réseau qui a une forme d'arbre. Dans cet étiquetage la recherche du plus proche ancêtre commun de deuæ sommets (et donc de la route qui les relie} s'efiectue uniquement à l'aide de leurs étiquettes. Des techniques plus compleoees, qui généralisent les techniques données ici, utilisent des étiquettes de taille O(log2 n) bits qui permettent aussi un calcul du plus proche ancêtre commun en O(l) opérations.

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


 X Informatique MP 2003 -- Corrigé Ce corrigé est proposé par Jean-Baptiste Rouquier (ENS Lyon) ; il a été relu par Samuel Mimram (ENS Lyon) et Vincent Puyhaubert (Professeur en CPGE). Il y a beaucoup de code à écrire dans ce problème, qui ne nécessite que peu de connaissances de cours. Il propose de manipuler les arbres (notamment les manières de les parcourir), et fait intervenir de nombreuses récurrences. Certaines questions théoriques, comme la question 9, sont difficiles. · La première partie consiste en l'écriture de quelques fonctions simples sur les arbres : hauteur d'un sommet, conversion entre deux représentations d'un arbre et plus proche ancêtre commun, notion définie dans l'énoncé. · La deuxième travaille sur les arbres binaires complets. Elle propose un étiquetage des sommets permettant de calculer rapidement le plus proche ancêtre commun de deux sommets en n'utilisant que leurs étiquettes. · La troisième fait la même étude sur les arbres généraux et définit pour cela les notions d'arbre gauche et de cime. Ce sujet est une bonne préparation aux concours, à condition de tester ses fonctions pour qui ne maîtrise pas encore Caml. En effet, c'est principalement l'algorithme qui est pris en compte par le correcteur, mais trop d'erreurs de syntaxe peuvent agacer. Comme souvent, la difficulté est progressive au sein de chaque partie, même si l'alternance de questions théoriques et des fonctions à implanter peut modifier la difficulté perçue. Il ne faut donc pas hésiter à passer à la partie suivante, quitte à revenir sur les dernières questions d'une partie. Les concepts étudiés dans ce problème servent surtout de support pour faire des exercices et ne sont pas très généraux. On retiendra de ce sujet les techniques mises en oeuvre (en particulier les parcours d'arbre et les récurrences) et le style de programmation. Indications 2 Traduire la définition de la hauteur en Caml, en utilisant un filtrage. 3 Pour chaque sommet, chercher les sommets dont il est le père. 4 Pour ppacMemeH, que peut-on dire des pères des deux arguments ? 5 Deviner une formule simple sur de petits exemples et la montrer par récurrence. Les puissances de 2 ne sont pas loin. . . 6 Étiqueter d'abord un arbre binaire à trois sommets pour voir comment ça marche. 7 Cette fois, un parcours en profondeur est utile. Préfixe, infixe ou postfixe ? 8 S'inspirer de la question précédente ; une récurrence n'est pas indispensable. Pour (a), quel est l'ensemble des étiquettes de Ba ? Idem pour Bb . Indication supplémentaire : penser également à la médiane. 9 Procéder en plusieurs étapes : · Montrer que r [[ p ; q ]]. · Soit g le plus proche ancêtre commun de a et b. Remarquer que tout sommet f tel que h(f ) 6 h(g) vérifie (f ) 6 [[ p ; q ]]. Utiliser la question 7 et raisonner par l'absurde. · Prouver que c, d h(c) > h(d) val 2 ((c)) < val 2 ((d)) val 2 ((c)) est la valuation en 2, c'est-à-dire l'exposant de 2 dans la décomposition en facteurs premiers de (c). Utiliser la question 8 et faire une récurrence sur la hauteur de l'arbre. · Conclure. 10 Utiliser la question 9 et oublier la représentation arborescente. Distinguer le cas p = q. Pour l'autre cas, ne considérer que les nombres pairs de [[ p ; q ]] (à justifier) et écrire une fonction récursive. 12 Première question : s'inspirer de la fonction poids de la question 11. Seconde question : faire une récurrence sur le nombre d'ancêtres légers du sommet qui en a le plus. 13 Faire un parcours en profondeur en donnant comme argument à la fonction récursive le plus proche ancêtre léger. Indication supplémentaire : le traitement d'un sommet consiste à calculer la cime de ses fils (et non la sienne). 15 Encore un parcours d'arbre. La principale difficulté est de s'assurer que (cime[a]) est calculée lorsque l'on arrive au calcul de (a). 16 Descendre l'arbre en choisissant le bon fils d'après les couples (t1(a), t2(a)). On peut descendre plusieurs étages en une fois. 17.a Étudier, dans l'ordre de profondeur croissante, la nature des sommets b tels que le couple (t1(b), t2(b)) fasse partie de (a), en particulier leurs liens de parenté et leur poids. 17.b S'inspirer de la fonction trouveSommet de la question précédente : descendre l'arbre et s'arrêter sur le plus proche ancêtre commun. L'énoncé commence par plusieurs notations, rappels et définitions de concepts nouveaux. Ces derniers sont utiles dès la première question, qui vise à vérifier leur compréhension. D'autres éléments sont introduits au début des parties suivantes. Certains autres sujets introduisent au contraire tous les nouveaux objets dont ils ont besoin au début ; il est alors bon de ne pas perdre de temps sur ces définitions pour n'y revenir que lorsque l'on aborde les question qui les utilisent. La définition des types vint, lint et vlint est assez étrange, elle n'apporte aucune information et ne sert apparemment qu'à économiser un peu d'encre. Toute variable de type vlint sera ici la représentation d'un arbre par ses listes de fils (sauf une fois) ; on aurait donc pu choisir un nom de type plus explicite (comme arbre). Mais il faut bien sûr se conformer à l'énoncé pour ne pas agacer le correcteur. C'est une erreur de syntaxe en Caml de faire commencer le nom d'une fonction par une majuscule. Il est donc recommandé par les concepteurs du langage eux-mêmes de séparer les mots par des soulignés (exemple : fils_en_pere) au lieu de majuscules (filsEnPere) comme le fait le sujet. Les fonctions comme do_list ou map_vect sont expliquées dans le manuel Caml (rubrique « the core library ») disponible sur caml.inria.fr, ou en téléchargement sur ftp.inria.fr/INRIA/caml-light. Si vous avez installé Caml sous Windows par le programme cl74win.exe, ce dernier doit avoir créé un manuel dont le nom est proche de « cl74refman ». Ces fonctions sont très utiles et map doit absolument être maîtrisée. Elles sont également présentées à la fin de ce corrigé. I. Fonctions élémentaires 1 Quelques remarques permettent de remplir une bonne partie du tableau : · Le tableau est symétrique car ppac(a, b) = ppac(b, a) pour tous a, b ; · pour tout a, ppac(0, a) = 0 car le seul ancêtre de la racine est 0 ; · pour tout a, ppac(a, a) = a. Le reste se fait en appliquant la définition du plus proche ancêtre commun. 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 0 1 4 0 4 4 0 0 2 0 4 2 0 4 2 0 0 3 0 0 0 3 0 0 0 0 4 0 4 4 0 4 4 0 0 5 0 4 2 0 4 5 0 0 6 0 0 0 0 0 0 6 6 7 0 0 0 0 0 0 6 7 Cette question sert, comme dans beaucoup d'autres sujets, à rassurer le candidat en lui faisant manipuler les concepts qui viennent d'être introduits. Pour faire un peu de gymnastique et continuer à manipuler ces concepts, on peut voir ppac(a, b) comme la racine du plus petit sous-arbre contenant a et b. Une session Caml à la fin de ce corrigé montre comment calculer automatiquement ce tableau ; c'est d'ailleurs ce qui a été fait ici. 2 Appliquons la définition de la hauteur : ( 0 si a est la racine h(a) = 1 + h(pere[a]) sinon ce qui se traduit par : let rec hauteur pere = function | 0 -> 0 | a -> 1 + hauteur pere pere.(a) ;; 3 Commençons par une évidence : a est le fils de b si et seulement si b est le père de a. Il suffit donc, pour chaque sommet, de le « déclarer » comme père de ses fils. Précisément, on crée le tableau peres, qui sera renvoyé. Puis on définit la fonction declare_pere qui prend un sommet et parcourt la liste de ses fils. Pour chaque fils, elle écrit qui est son père dans le résultat. On l'applique alors à tous les sommets. Il faut enfin régler le cas de la racine, la convention étant ici qu'elle a un père. let filsEnPere fils = let n = vect_length fils in let peres = make_vect n (-1) in let declare_pere p = do_list (fun son -> peres.(son) <- p) fils.(p) in for p=0 to n-1 do declare_pere p done; peres.(0) <- 0; peres ;; Le tableau peres est initialisé avec -1, ce qui aide à déboguer : si le résultat contient encore des -1, c'est qu'il y a eu un problème. Cela ne marche que si les sommets ont toujours des numéros positifs. Un parcours d'arbre est inutile pour cette question. 4 Définissons une fonction récursive : si les deux sommets sont égaux, alors leur plus proche ancêtre commun est l'un des deux, sinon c'est le plus proche ancêtre commun de leurs pères, qui sont à la même hauteur. let rec ppacMemeH pere a b = if a = b then a else ppacMemeH pere pere.(a) pere.(b) ;;