X Informatique MP 2011

Thème de l'épreuve Transmission dans les arbres
Principaux outils utilisés arbres, algorithmique
Mots clefs arbre, arbre binomial, diamètre, diffusion, échange total, profondeur, modèle « du téléphone »

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 ­ ÉCOLES NORMALES SUPÉRIEURES FILIÈRE CONCOURS D'ADMISSION 2011 MP SPÉCIALITÉ INFO COMPOSITION D'INFORMATIQUE ­ A ­ (XULC) (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. Transmission dans les arbres On étudie dans ce problème des algorithmes de transmission d'informations dans les arbres, avec le modèle dit "du téléphone". Dans la partie I, on étudie les arbres binomiaux. Dans la partie II, on considère plusieurs calculs élémentaires sur les arbres. Dans la partie III, on étudie la diffusion de l'information à partir de la racine de l'arbre. Dans la partie IV, on s'intéresse à l'échange total d'informations entre tous les noeuds d'un arbre. Les parties I et II sont indépendantes. Algorithmes et programmes ­ Pour les questions qui demandent la conception d'un algorithme : il s'agit de donner une description concise mais précise, en français, d'un algorithme effectuant la tâche indiquée. ­ Pour les questions qui demandent l'écriture d'un programme : il s'agit d'exprimer votre algorithme dans un langage de programmation de votre choix. La lisibilité de votre programme (notamment : mise en évidence de sa structure, indentation, commentaires pertinents) sera prise en compte dans l'évaluation. ­ Lorsqu'elle est demandée, la complexité d'un algorithme ou d'un programme ne sera pas calculée exactement mais seulement estimée en ordre de grandeur, avec des expressions du type O(m+n), O(m2 log n), etc., où m, n, . . . sont des paramètres en entrée de l'algorithme. ­ Lorsqu'une question demande d'écrire un programme, et qu'une certaine complexité est exigée, on ne demande pas de faire la preuve que le programme proposé a effectivement cette complexité. Définitions ­ Un arbre T = (r, L) est défini par la donnée d'un entier r, appelé noeud, et d'une liste d'arbres L, éventuellement vide. Si la liste L est vide, on dit que r est un noeud externe. Sinon, la liste L comprend éléments Ti = (ri , Li ), 1 i , on dit que r est un noeud interne, que les noeuds ri sont les fils de r, et que r est le père des ri . 1 ­ Tous les noeuds de T sont supposés distincts. On note N (T ) l'ensemble de tous les noeuds de T et nbn(T ) leur nombre. ­ Dans un arbre, les voisins d'un noeud sont son père (s'il existe) et ses fils. ­ Entre deux noeuds s et t de T il existe un unique chemin, composé de noeuds x0 , x1 , . . . , xk deux à deux distincts, tels que x0 = s, xk = t, et xi et xi+1 sont voisins pour 0 i k - 1. On note chemin(s, t) ce chemin et on dit que k est sa longueur. ­ Le noeud r est appelé la racine de T . ­ La profondeur d'un noeud s est la longueur de chemin(s, r) ; en particulier, la racine r a pour profondeur 0. La profondeur de T est le maximum de la profondeur de ses noeuds. Les arbres seront représentés en Caml et en Pascal de la manière suivante : { Pascal } type arbre = ^noeud ; liste_arbre = ^element ; noeud = record n :integer ; l :liste_arbre ; end ; element = record a :arbre ; r :liste_arbre ; end ; (* Caml *) type arbre = | Noeud of int * arbre list ; ; Certaines questions font par ailleurs intervenir des listes d'entiers, qui seront représentées par le type liste suivant : type liste == int list ; ; type liste = ^entier ; entier = record e :integer ; s :liste ; end ; Partie I. Arbres binomiaux Dans cette partie, on étudie des arbres particuliers, appelés "binomiaux". Soit k un entier positif ou nul. Un arbre binomial d'ordre k est défini comme suit : ­ un arbre binomial d'ordre 0 est réduit à sa racine ; ­ si k > 0, un arbre binomial d'ordre k est de la forme (rk , (Tk-1 , . . . , T1 , T0 )) où chaque Ti est un arbre binomial d'ordre i. Dans la suite, Bk désigne un arbre binomial d'ordre k. Question 1 Dessiner B4 , avec une numérotation des noeuds de votre choix. Question 2 Quel est le nombre de noeuds de Bk ? Combien sont externes ? Question 3 Pour k > 0, montrer qu'on peut aussi définir récursivement Bk à l'aide de deux copies de Bk-1 . Question 4 Écrire une fonction copie qui prend en arguments un entier n et un arbre T et renvoie une copie de l'arbre T dans laquelle chaque noeud de numéro i est remplacé par un noeud de numéro i + n. 2 (* Caml *) copie : int -> arbre -> arbre { Pascal } function copie(n : integer ; t : arbre) : arbre ; Question 5 Écrire une fonction bin qui prend en argument un entier k 0 et qui renvoie l'arbre Bk , avec une numérotation des noeuds de votre choix. On garantira une complexité proportionnelle au nombre de noeuds de Bk . (* Caml *) bin : int -> arbre { Pascal } function bin(k : integer) : arbre ; Question 6 Quelle est la profondeur de Bk ? Quelle est la longueur maximale d'un chemin entre deux noeuds ? Question 7 Combien de noeuds ont une profondeur donnée ? Question 8 Pour n 1, on définit Cn comme un arbre de racine r et à n noeuds, qu'on obtient avec la numérotation suivante des noeuds : la racine r a le numéro 1, et le père du noeud de numéro i, où 2 i n, est le noeud de numéro i - 2log2 i-1 , où la notation x désigne le plus petit entier supérieur ou égal à x. Dessiner C16 . Justifier que la définition de Cn conduit bien à un arbre. Donner, sans la justifier, une relation entre Bk et C2k . Question 9 Écrire une fonction cn qui prend en argument un entier n 1 et qui renvoie l'arbre Cn . On garantira une complexité O(n). (* Caml *) cn : int -> arbre { Pascal } function cn(n : integer) : arbre ; Partie II. Fonctions élémentaires sur les arbres Question 10 Écrire une fonction profondeur qui prend en argument un arbre T et renvoie sa profondeur. On garantira une complexité O(nbn(T )). (* Caml *) profondeur : arbre -> int { Pascal } function profondeur(t : arbre) : integer ; Question 11 Écrire une fonction noeud_externe_max qui prend en argument un arbre T et qui renvoie le numéro d'un noeud externe de T de profondeur maximale. En cas d'égalité, on choisira arbitrairement. On garantira une complexité O(nbn(T )). (* Caml *) noeud_externe_max : arbre -> int { Pascal } function noeud_externe_max(t : arbre) : integer ; 3 Question 12 Soit T un arbre de racine r et s un noeud de T . Écrire une fonction chemin qui prend en arguments T et s et renvoie l'unique chemin de r à s sous la forme d'une liste d'entiers [x0 ; x1 ; . . . ; xk ] avec x0 = r, xk = s et xi père de xi+1 pour 0 i < k. On garantira une complexité O(nbn(T )). (* Caml *) chemin : arbre -> int -> liste { Pascal } function chemin(t : arbre ; s : integer) : liste ; Question 13 Soit T un arbre et s un noeud de T . On définit l'arbre obtenu par changement de racine s, noté pivot(T , s), comme l'arbre T de racine s dont les noeuds sont les mêmes que ceux de T et tel que deux noeuds sont voisins dans T si et seulement s'ils le sont dans T . Écrire une fonction pivot qui prend en arguments T et s et renvoie l'arbre pivot (T , s). On garantira une complexité O(nbn(T )). S'il y a plusieurs tels arbres T , on en choisit un arbitrairement. (* Caml *) pivot : arbre -> int -> arbre { Pascal } function pivot(t : arbre ; s : integer) : arbre ; Question 14 Étant donné un arbre T , on définit son diamètre comme la longueur du plus long chemin dans T . Soit r1 l'un des noeuds externes de T de profondeur maximale, et T = pivot(T , r1 ) l'arbre obtenu à partir de T par changement de racine r1 . Montrer que le diamètre de T est égal à la profondeur de T . Question 15 son diamètre. En déduire une fonction diametre qui prend en argument un arbre et qui renvoie (* Caml *) diametre : arbre -> int { Pascal } function diametre(t : arbre) : integer ; Question 16 Soit T un arbre de diamètre D. Montrer que D est la plus grande profondeur d'un arbre obtenu par changement arbitraire de racine et que D2 est la plus petite profondeur d'un arbre obtenu par changement arbitraire de racine. Partie III. Diffusion dans les arbres On étudie dans cette partie le problème de la diffusion dans les arbres. La racine r de l'arbre T = (r, L) possède un message qu'elle doit transmettre à tous les autres noeuds. La diffusion procède par étapes, toutes de temps unitaire. À une étape donnée, chacun des noeuds déjà en possession du message le transmet à un et un seul de ses fils (sauf si tous ses fils l'ont déjà reçu). Une diffusion D est caractérisée par un ensemble de fonctions : à chaque noeud interne v de l'arbre, avec nv fils, on associe une fonction injective fv qui numérote ses fils de 1 à nv dans l'ordre dans lequel v leur transmet le message. 4 Pour v N (T ), on note tD (v) le numéro de l'étape à laquelle v reçoit le message : 0 si v = r, tD (v) = tD (v ) + fv (v) si v est le père de v. Voici un exemple : · · · 3 · · · · · · Un arbre · · · · 1 · 1 1 · 2 1 · · · 0 1 1 · · 2 · · 3 2 4 3 2 3 4 3 4 1 Valeurs des fonctions fv 1 Valeurs des numéros des étapes tD (v) La durée de la diffusion est son nombre d'étapes, soit t(D) = maxvN (T ) tD (v). Une diffusion est optimale si sa durée est minimale parmi les durées de toutes les diffusions. Diffusion dans les arbres binomiaux On considère l'arbre binomial Bk défini dans la partie I. Tout noeud interne v a pour fils les racines r1 , . . . , rnv d'arbres binomiaux B0 , B1 , . . . , Bnv -1 . La numérotation naturelle s'obtient en posant fv (ri ) = i pour chaque noeud v et chaque i, 1 i nv , tandis que la numérotation renversée s'obtient en posant fv (ri ) = nv - i + 1. Question 17 Quelle est la durée de la diffusion qui choisit la numérotation naturelle pour chaque noeud ? Question 18 Même question pour la diffusion qui choisit la numérotation renversée pour chaque noeud. Question 19 Quelle est la durée d'une diffusion optimale dans Bk ? Justifier votre réponse. Diffusion dans un arbre quelconque Question 20 Proposer un algorithme pour déterminer une diffusion optimale dans un arbre T quelconque. Quelle est sa complexité en fonction de nbn(T ) ? Question 21 Écrire une fonction diffusion_optimale qui prend en argument un arbre T et qui calcule la durée d'une diffusion optimale pour T . (On pourra supposer que le langage de programmation contient une fonction qui trie un tableau ou une liste d'entiers.) (* Caml *) diffusion_optimale : arbre -> int { Pascal } function diffusion_optimale(t : arbre) : integer ; 5 Durée de la diffusion optimale Question 22 Donner une borne supérieure pour la durée d'une diffusion optimale dans un arbre arbitraire à n noeuds, et exhiber pour tout n un arbre pour lequel cette borne est atteinte. Question 23 Donner une borne inférieure pour la durée d'une diffusion optimale dans un arbre arbitraire à n noeuds, et exhiber pour tout n un arbre pour lequel cette borne est atteinte. Partie IV. Échange total dans les arbres On étudie dans cette partie le problème de l'échange total dans les arbres. Chaque noeud v de l'arbre possède un message msgv qu'il doit transmettre à tous les autres noeuds. L'échange total procède par étapes, toutes de temps unitaire. Lors d'une étape, certaines paires de voisins s'échangent tous les messages qu'ils ont reçus dans les étapes précédentes ; chaque noeud ne peut communiquer qu'avec un seul voisin lors d'une étape donnée. La durée d'un échange total est son nombre d'étapes, et son trafic est le nombre d'échanges entre voisins ayant eu lieu au cours de l'algorithme. Voici un exemple pour un arbre à 4 noeuds, dont la durée est 3 et le trafic 5 : Étape 0 Étape 1 msg2 msg1 msg1 , msg2 msg1 , msg2 msg3 msg3 , msg4 msg3 , msg4 msg4 Étape 2 Étape 3 msg1 , msg2 msg3 , msg4 msg1 , msg2 msg3 , msg4 msg1 , msg2 msg1 , msg2 msg3 , msg4 msg1 , msg2 msg3 , msg4 msg1 , msg2 msg3 , msg4 msg1 , msg2 msg3 , msg4 msg3 , msg4 Échange total dans les arbres binomiaux On revient dans cette question sur l'arbre binomial Bk d'ordre k 1 introduit dans la partie I. Question 24 Proposer un algorithme d'échange total dans Bk dont la durée est 2k - 1. Question 25 Montrer que tout échange total dans Bk a une durée au moins égale à 2k - 1. 6 Question 26 Plus généralement, donner une borne inférieure pour la durée de tout échange total dans un arbre T quelconque à n 2 noeuds. Échange total de trafic minimal Soit T un arbre à n 2 noeuds. On considère l'échange total suivant, où il y a un seul échange à chaque étape : 1. Tant que l'arbre contient au moins trois noeuds : (a) On choisit un noeud externe s (arbitrairement s'il y en a plusieurs), qui effectue un échange avec son père ; (b) On efface le noeud s de l'arbre. 2. Les deux derniers noeuds échangent leur information et possèdent désormais les messages de tous les noeuds de T . 3. On effectue à nouveau tous les échanges de l'étape 1, dans l'ordre inverse, pour propager l'information à tous les noeuds. Question 27 Montrer que le trafic de l'échange total précédent est égal à 2n - 3. Question 28 Écrire une fonction echange_total qui prend en argument un arbre T et renvoie la liste des n - 2 noeuds externes successivement retirés de l'arbre T par l'étape 1 de l'algorithme d'échange total ci-dessus. On garantira une complexité O(nbn(T )). (* Caml *) echange_total : arbre -> liste { Pascal } function echange_total(t : arbre) : liste ; Question 29 Montrer que le trafic de tout échange total dans un arbre à n 2 noeuds est au moins égal à 2n - 3. 7

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


 X Informatique MP 2011 -- Corrigé Ce corrigé est proposé par Benjamin Monmege (ENS Cachan) ; il a été relu par Vincent Puyhaubert (Professeur en CPGE) et Guillaume Batog (ENS Cachan). Ce sujet aborde le problème de la transmission d'information dans les arbres, selon le modèle dit « du téléphone ». On considère ainsi un arbre comme un réseau de communication, dans lequel les noeuds sont les acteurs du réseau et les arêtes sont les canaux par lesquels peuvent transiter les messages. Dans un tel réseau, au moins deux types de protocoles de communication peuvent être intéressants. Dans le premier, un des acteurs possède un message qu'il souhaite transmettre à tous les autres : c'est le problème de la diffusion. Dans le second, chaque acteur possède un message, et l'objectif consiste à transmettre l'ensemble des messages à tous les acteurs du réseau : c'est le problème de l'échange total. Il est souvent plus naturel de considérer des graphes généraux pour modéliser de tels réseaux de communication. Cependant, en se limitant au cas des arbres, ce sujet étudie déjà un grand nombre de difficultés du domaine. Le sujet est divisé en quatre parties dont les deux premières sont indépendantes. · La première partie introduit une classe d'arbres particuliers, les arbres binomiaux, qui seront utilisés dans la suite pour donner des exemples des protocoles de communication. · La deuxième partie, majoritairement algorithmique, introduit quelques fonctions élémentaires sur les arbres, tels que la profondeur ou le diamètre. · La troisième partie résout le problème de la diffusion dans les arbres, en commençant par la diffusion dans les arbres binomiaux. On cherche ensuite la durée optimale d'un protocole de diffusion. Des bornes inférieures et supérieures sont données, ainsi que des exemples de classes d'arbres qui atteignent ces bornes. · La quatrième partie résout le problème d'échange total dans les arbres, en commençant à nouveau par l'échange total dans les arbres binomiaux. Dans la suite, le sujet propose de minimiser la durée d'un protocole d'échange total, puis son trafic (nombre total de messages échangés). Il s'agit d'un sujet long, comportant à la fois des questions théoriques de niveau avancé et des questions algorithmiques demandant beaucoup de vigilance et de clairvoyance. Il est nécessaire de bien maîtriser la partie du programme sur les arbres pour aborder le plus sereinement possible ce sujet. Du point de vue de la programmation, ce sujet permet de réviser les fonctions récursives et doublement récursives. Indications Partie I 2 Le nombre de noeuds d'un arbre de la forme (r, L) vaut la somme du nombre de noeuds des arbres de la liste L à laquelle on ajoute 1 pour le noeud r. 3 Dans l'arbre de la question 1, essayer de repérer deux copies de l'arbre B3 . 4 Utiliser la fonction Caml map, de type ('a -> 'b) -> 'a list -> 'b list, qui prend en argument une fonction f ainsi qu'une liste [a1 ;... ;an] et renvoie la liste [f a1 ;... ;f an]. 5 Utiliser la construction de la question 3, puis appliquer la fonction de la question 4 avec un paramètre n bien choisi. 6 La profondeur d'un arbre de la forme (r, L), non réduit à sa racine, vaut le maximum des profondeurs des arbres de la liste L auquel on ajoute 1. Montrer ainsi que Bk possède un unique noeud à profondeur maximale. Pour construire un chemin de longueur maximale, utiliser la définition de la question 3 et concaténer des chemins des deux copies de Bk-1 . 7 En notant uk, le nombre de noeuds à profondeur dans l'arbre Bk , utiliser la caractérisation de la question 3 pour exhiber une formule de récurrence reliant les nombres uk, , uk-1, et uk-1,-1 . 8 Justifier que Cn est un arbre par récurrence sur n. 9 Commencer par montrer que les fils du noeud j dans Cn sont tous les noeuds d'indice j + 2k pour k vérifiant j 6 2k 6 n - j. Partie II 11 Modifier légèrement la fonction de la question 10 afin qu'elle renvoie à la fois la profondeur de l'arbre et un noeud qui possède cette profondeur. 12 Pour un noeud s fixé, écrire deux fonctions mutuellement récursives qui prennent en argument un arbre ou une liste d'arbres et recherchent un chemin vers s. Par défaut, si s ne fait pas partie de l'arbre ou de la liste d'arbres donnés, on peut par exemple renvoyer le chemin vide. 13 On pourra commencer par décrire une opération de rotation d'un arbre, qui consiste à réaliser un échange de la racine avec un de ses fils. Ensuite, en s'aidant de la fonction chemin pour trouver le noeud auquel on veut appliquer le changement de racine, on applique une succession de rotations le long de ce chemin. 14 Montrer d'abord que la profondeur de T est inférieure ou égale à D. Montrer ensuite qu'il existe un chemin partant de r1 de longueur maximale parmi les chemins de T . 15 Fusionner les résultats des questions précédentes de la partie II. 16 Pour la première partie de la question, utiliser la question 14. Pour la seconde partie, commencer par montrer que la profondeur de tout pivot T est supérieure ou égale à D/2, puis construire un arbre de profondeur D/2 obtenu par changement de racine, en considérant le noeud au milieu d'un chemin de longueur maximale dans T . Partie III 17 Trouver une relation de récurrence reliant les durées de diffusion dans les arbres Bk . La simplifier en remarquant que la suite de ces durées est croissante. 18 Procéder de la même manière qu'à la question 17 en utilisant la construction de la question 3. 19 Combien de fils possède la racine de Bk ? 20 En supposant que l'arbre T est de la forme (r, (T1 , . . . , T )) et qu'on dispose de diffusions optimales pour les arbres T1 , . . . , T , comment en déduire une diffusion optimale pour T à l'aide d'une approche gloutonne ? 21 Utiliser l'algorithme que vous avez décrit dans la question 20 en ne calculant que la durée de la diffusion et pas la diffusion elle-même. 22 Combien de messages peuvent être transmis dans le pire des cas à chaque étape ? 23 Montrer par récurrence sur k, qu'après k étapes, au plus 2k noeuds possèdent le message. Utiliser l'arbre Cn défini dans la question 8 pour fournir un exemple d'arbre qui atteint la borne inférieure et le prouver en utilisant le résultat de la question 19. Partie IV 24 Construire par récurrence un algorithme d'échange total dans l'arbre Bk tel qu'après k étapes, la racine possède les messages de tous les noeuds. Les k dernières étapes pourront utiliser l'algorithme de diffusion étudié dans la question 18. 25 Montrer que pour tout arbre la durée de tout échange total est supérieure ou égale au diamètre de l'arbre, et conclure en utilisant le résultat de la question 6. 26 Montrer que le nombre total de messages transmis double au plus à chaque étape. 28 Il s'agit de procéder à un parcours de l'arbre, en commençant par exemple par le noeud externe le plus à droite de l'arbre. 29 Après avoir remarqué que tout algorithme d'échange total contient un échange entre chaque voisin de l'arbre, montrer par l'absurde qu'il n'existe pas de tel algorithme avec un trafic inférieur ou égal à 2(n - 2). Pour cela, montrer qu'il existe deux paires de voisins qui ne s'échangent leurs messages qu'une unique fois et aboutir à une contradiction en considérant un chemin qui lie ces deux paires de voisins. I. Arbres binomiaux 1 L'arbre dessiné ci-dessous est un arbre binomial d'ordre 4, dans lequel les noeuds ont été indexés en suivant un parcours postfixe de l'arbre. 15 7 3 1 5 2 11 6 9 4 13 10 14 12 8 0 Le sujet n'exige pas d'expliquer la manière dont les noeuds sont étiquetés, mais un correcteur aura sans doute une meilleure appréciation de la copie si le candidat est d'ores et déjà capable de justifier une certaine cohérence dans son choix. 2 Un arbre binomial d'ordre 0 étant réduit à sa racine, il possède un unique noeud qui est externe. Montrons par récurrence forte que la propriété : P(k) : « Bk possède 2k noeuds, dont 2k-1 noeuds externes. » est vraie pour tout k > 1. · P(1) : un arbre binomial d'ordre 1 consiste en une racine avec un unique fils, qui est un noeud externe. Ainsi B1 possède 2 noeuds, dont 1 externe. · P(k - 1) = P(k) : par définition, un arbre binomial d'ordre k est de la forme (rk , (Bk-1 , . . . , B1 , B0 )). En utilisant l'hypothèse de récurrence, on sait que pour tout j {1, . . . , k - 1}, l'arbre Bj possède 2j noeuds dont 2j-1 sont externes. Par ailleurs, on a vu précédemment que B0 possède un unique noeud, qui est externe. Ainsi, en comptant la racine qui est un noeud interne, Bk possède k-1 k-1 P j P j-1 1+ 2 = 2k noeuds dont 1 + 2 = 2k-1 noeuds externes. j=0 j=1 · Conclusion : Pour tout k > 0, Bk possède 2k noeuds, donc 2k-1 noeuds externes, sauf pour B0 qui possède 1 noeud externe.