X Informatique MP/PC 2012

Thème de l'épreuve Le problème du « sandwich au jambon », ou théorème de Stone-Tukey
Principaux outils utilisés tableaux
Mots clefs sandwich au jambon, théorème de Stone-Tukey, hyperplan, partition

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


ECOLE POLYTECHNIQUE ­ ECOLE NORMALE SUPERIEURE DE CACHAN ECOLE SUPERIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES CONCOURS D'ADMISSION 2012 FILIERE MP HORS SPECIALITE INFO FILIERE PC COMPOSITION D'INFORMATIQUE ­ B ­ (XEC) (Duree : 2 heures) L'utilisation des calculatrices n'est pas autorisee pour cette epreuve. Le langage de programmation choisi par le candidat doit etre specifie en tete de la copie. Sandwich au jambon Le probleme dit du sandwich au jambon ou bien encore appele theoreme de Stone-Tukey s'enonce de la maniere suivante : un ensemble de n points en dimension d peut toujours etre separe en deux parties de cardinal au plus n/2 par un hyperplan de dimension d - 1 (certains points peuvent etre dans l'hyperplan), ou n/2 designe la partie entiere de n/2. De maniere concrete, un ensemble de points dans l'espace peut etre separe en deux parties quasi-egales par un plan. De meme un ensemble de points dans le plan peut etre separe en deux par une droite et meme en 4 a l'aide de deux droites. Ce sujet porte sur la resolution algorithmique de ce probleme et de problemes connexes selon differentes methodes. Dans tout le probleme, les tableaux sont indices a partir de 1. L'acces a la i-eme case d'un tableau tab est note tab[i]. Quel que soit le langage utilise, on suppose que les tableaux peuvent etre passes comme arguments des fonctions. En outre, il existe une primitive allouer(m, c) pour creer un tableau de taille m dont chaque case contient c a l'origine, ainsi qu'une primitive taille(t) qui renvoie la taille d'un tableau t. Enfin, on disposera d'une fonction floor(x) qui renvoie la partie entiere x pour tout reel x 0. La complexite, ou le temps d'execution, d'un programme P (fonction ou procedure) est le nombre d'operations elementaires (addition, soustraction, multiplication, division, affectation, etc...) necessaires a l'execution de P . Lorsque cette complexite depend d'un parametre n, on dira que P a une complexite en O(f (n)), s'il existe K > 0 tel que la complexite de P est au plus Kf (n), pour tout n. Lorsqu'il est demande de garantir une certaine complexite, le candidat devra justifier cette derniere si elle ne se deduit pas directement de la lecture du code. 1 Partie I. Grand, petit et median Dans cette partie, nous supposerons donne un tableau tab contenant n nombres reels. Les indices du tableau vont de 1 a n. Nous denoterons par tab[a..b] le tableau pris entre les indices a et b c'est-a-dire les cellules tab[a], tab[a + 1], . . . , tab[b - 1], tab[b]. Nous supposerons dans l'enonce que a b. Nous utiliserons le tableau de taille 11 suivant pour nos exemples : 3 2 5 8 1 34 21 6 9 14 8 Question 1 Ecrire une fonction calculeIndiceMaximum(tab, a, b) qui renvoie l'indice d'une case ou se trouve le plus grand reel de tab[a..b]. Sur le tableau precedent avec a = 1 et b = 11, la fonction renverra 6 car la case 6 contient la valeur 34. Question 2 Ecrire une fonction nombrePlusPetit(tab, a, b, val) qui renvoie le nombre d'elements dans le tableau tab[a..b] dont la valeur est plus petite ou egale a val. Sur le tableau exemple, pour une valeur de val egale a 5, et a = 1, b = 11, la fonction devra renvoyer la valeur 4 car seuls les nombres 3, 2, 5, 1 sont inferieurs ou egaux a 5. Nous allons maintenant calculer un median d'un tableau. Rappelons qu'une valeur mediane m d'un ensemble E de nombres est un element de E tel que les deux ensembles Em (les nombres de E strictement plus grands que m) verifient |Em | n/2. Notez que le probleme du median est une reformulation de probleme dit du sandwich au jambon pris en dimension 1. Une methode naive consiste donc a parcourir les elements de l'ensemble et a calculer pour chacun d'eux les valeurs de |Em | mais il est possible de faire mieux comme nous allons le voir dans la partie suivante. Partie II. Un tri pour accelerer Une methode plus efficace serait de trier le tableau par ordre croissant tout en prenant la cellule du milieu dans le tableau trie. Cette methode certes rapide requiert O(n ln n) operations. Il existe une methode optimale en temps lineaire O(n) pour trouver le median d'un ensemble de n elements. Cette partie a pour but d'en proposer une implementation. Une fonction annexe necessaire pour cet algorithme consiste a savoir separer en deux un ensemble de valeurs. Soit un tableau tab et un reel appele pivot p = tab[i], il s'agit de reordonner les elements du tableau en mettant en premier les elements strictement plus petits que le pivot tab

p . Sur le tableau exemple, en prenant comme valeur de pivot 8 on obtiendra le tableau resultat suivant : 3, 2, 5, 1, 6 8, 8 21, 34, 9, 14 Notez que dans le resultat les nombres plus petits que le pivot 3, 2, 5, 1, 6 peuvent etre dans n'importe quel ordre les uns par rapport aux autres. 2 Question 3 Ecrire une fonction partition(tab, a, b, indiceP ivot) qui prend en parametre un tableau d'entiers tab[a..b] ainsi qu'un entier a indiceP ivot b. Soit p = tab[indiceP ivot]. La fonction devra reordonner les elements de tab[a..b] comme explique precedemment en prenant comme pivot le nombre p. La fonction retournera le nouvel indice de la case ou se trouve la valeur p. Dans cette question, on suppose que les modifications effectuees par la fonction sur le tableau tab sont persistantes, meme apres l'appel de la fonction. Remarquons que le n/2-eme element dans l'ordre croissant d'un tableau de taille n est un element median du tableau considere. Nous allons donc non pas programmer une methode pour trouver le median mais plus generalement pour trouver le k-eme element d'un ensemble. Nous allons utiliser l'algorithme suivant : On cherche le k-eme element du tableau tab[a..b]. ­ Si k = 1 et a = b alors renvoyer tab[a] ­ Sinon, soit p = tab[a]. Partitionner le tableau tab[a..b] en utilisant le pivot p en mettant en premier les elements plus petits que p. Soit i l'indice de p dans le tableau resultant. ­ Si i - a + 1 > k chercher le k-eme element dans tab[a..i - 1] et renvoyer cet element. ­ Si i - a + 1 = k renvoyer le pivot. ­ Si i - a + 1 < k chercher le (k - i + a - 1)-eme element dans tab[i + 1..b] et renvoyer cet element. Question 4 Ecrire une fonction elementK(tab, a, b, k) qui realise l'algorithme de selection du k-eme element dans le tableau tab[a..b] decrit precedemment et renvoie cet element. Question 5 Supposons que dans l'algorithme precedent nous voulions rechercher le premier element mais qu'a chaque etape le pivot choisi est le plus grand element, quel est un ordre de grandeur du nombre d'operations realisees par votre fonction ? L'algorithme precedent ne semble donc pas ameliorer le calcul du median. Le probleme vient du fait que le pivot choisi peut etre mauvais c'est-a-dire qu'a chaque etape un seul element du tableau a ete elimine. En fait, si l'on peut choisir un pivot p dans tab[a..b] tel qu'il y ait au moins (b - a)/5 elements plus petits et (b - a)/5 plus grands alors on peut montrer que l'algorithme precedent fonctionne optimalement en temps O(n). Pour choisir un tel element dans tab[a..b], on realise l'algorithme choixPivot suivant ou chaque etape sera illustree en utilisant le tableau donne en introduction en prenant a = 2 et b = 9. ­ On decoupe le tableau en paquets de 5 elements plus eventuellement un paquet plus petit. On calcule l'element median de chaque paquet. xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx 3 2 5 8 1 34 21 6 9 xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx 14 8 S'il n'y a qu'un paquet on renvoie son median. Sinon on place ces elements medians au debut du tableau. xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx 3 5 9 2 8 1 3 34 21 6 xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx 14 8 ­ On realise choixPivot sur les medians precedents. Dans notre exemple on recommence donc les etapes precedentes en prenant a = 2 et b = 3. xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx 3 5 9 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 2 8 1 34 21 6 14 8 Question 6 Ecrire la fonction choixPivot(tab, a, b) qui realise l'algorithme precedent et renvoie la valeur du pivot. Partie III. De la 1D vers la 2D, des nombres aux points. Pour un reel x 0, on note dans cette partie x la partie entiere superieure de x, c'esta-dire, le plus petit entier qui est plus grand ou egal a x : x - 1 < x x. On supposera disposer d'une fonction ceil(x) qui renvoie la partie entiere superieure x pour tout reel x 0. Dans la partie precedente, nous avons etudie le probleme du median en dimension 1. On supposera donc que vous disposez maintenant d'une fonction indiceMedian(tab, a, b) qui calcule un element median du tableau tab[a..b] et renvoie l'indice de cet element. Vous supposerez de plus que cette fonction ne modifie pas l'ordre des elements du tableau tab. Dans cette partie, nous generalisons l'algorithme de maniere a trouver deux droites dans le plan separant un ensemble de n points en 4 parties de cardinal plus petit que n/4, Soit E un ensemble de n points tel qu'il n'existe pas trois points alignes. Nous allons chercher deux lignes L= et L/ separant cet ensemble de points en 4 parties comme le montre la troisieme figure ci-dessous. En effet, dans cette figure chaque partie est composee d'exactement 2 points, les points situes sur les lignes n'etant pas pris en compte. Nous supposerons donnes dans cette partie deux tableaux tabX et tabY de taille n contenant les coordonnees des n points. Ainsi le point i a comme abscisse tabX[i] et comme ordonnee tabY [i]. L= L= L/ La premiere etape est de separer les points en deux ensembles de meme cardinal. Il suffit de remarquer que l'on peut toujours effectuer cette separation par une ligne horizontale notee L= passant par un point d'ordonnee mediane comme le montre le second schema ci-dessus. Question 7 Ecrire une fonction coupeY(tabX, tabY ) qui renvoie l'ordonnee d'une ligne horizontale separant les points en deux parties de cardinal au plus n/2. 4 La seconde ligne L/ est plus difficile a trouver. Nous allons en realite trouver le point d'intersection des deux lignes L= et L/ . Soit P un point sur la droite horizontale L= precedente de coordonnees (x, y). On veut verifier si ce point peut etre le point d'intersection des deux lignes L= et L/ . Nous allons trouver dans un premier temps l'angle entre L= et L/ en utilisant le fait que L/ doit separer en deux parties de cardinal proche les points au dessus de L= . Ensuite nous allons verifier si la droite L/ ainsi devinee separe les points en dessous de L= en deux parties presque egales. L/ ? L= P Concretement on considere les demi-droites partant de P = (x, y) et joignant les k points de E au dessus strictement de L= comme indique sur le schema ci-dessus. On calcule ensuite les angles entre L= et ces demi-droites. Remarquez alors que toute demi-droite d'angle median partage en deux parties de cardinal k/2 les points au dessus de L= . Nous supposerons donnee une fonction angle(x, y, x2, y2) qui calcule et renvoie l'angle forme par une demi-droite horizontale partant de (x, y) et allant vers la droite et le segment (x, y) - (x2, y2). La valeur retournee sera comprise dans l'intervalle [0, 2[. Question 8 Ecrire une fonction demiDroiteMedianeSup(tabX, tabY, x, y) qui calcule et renvoie un angle median entre L= et les segments reliant P = (x, y) avec les points de E dont l'ordonnee est superieure a y. Pour un point P donne, nous avons determine l'angle que doit prendre L/ pour couper les points au dessus de L= en 2 parties de taille au plus moitie. Il faut maintenant verifier que cette droite L/ coupe aussi les points en dessous de L= en 2 parties quasi-egales. Il suffit de verifier que l'angle de L/ partitionne les angles formes entre P et les points en dessous de L= en deux parties de cardinal /2. Question 9 Ecrire une fonction verifieAngleSecondeDroite(tabX, tabY, x, y, theta) qui calcule les angles formes entre L= et les points strictement au dessous de L= . Votre fonction devra renvoyer : 0 si theta est une mediane des angles. -1 si le nombre d'angles strictement plus petits que theta est > /2 1 si le nombre d'angles strictement plus grands que theta est > /2 Si xmin est l'abscisse minimale des points de E et xmax l'abscisse maximale, alors il est evident que l'intersection entre L= et L/ ait une abscisse entre xmin et xmax. Nous allons donc rechercher cette abscisse en utilisant l'algorithme suivant : 5 1. 2. 3. 4. 5. Trouver L= d'ordonnee y. Soit = xmin et = xmax. On calcule P le point au milieu de (, y) et (, y). On calcule l'angle possible de la droite L/ par la fonction demiDroiteMedianeSup. Soit d la valeur donnee par la fonction verif ieAngleSecondeDroite avec l'angle trouve precedemment. Si d = 0 alors on a trouve L/ . Si d = -1 on recommence a partir du point 3 en prenant l'abscisse de P a la place de . Si d = 1 on recommence mais en prenant l'abscisse de P a la place de . Question 10 Ecrire la fonction secondeMediane(tabX, tabY, y) qui a partir d'un ensemble E de points donnes par leurs coordonnees et de l'ordonnee de la droite L= calcule et renvoie un tableau contenant dans la premiere case l'abscisse x du point d'intersection de L= et de L/ ainsi que l'angle de L/ dans la seconde case. 6

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


 X Informatique MP/PC 2012 -- Corrigé Ce corrigé est proposé par Céline Chevalier (Enseignant-chercheur à l'université) ; il a été relu par Guillaume Batog (Professeur agrégé) et Arnaud Borde (École Polytechnique). Ce sujet s'intéresse au problème dit du « sandwich au jambon », aussi appelé théorème de Stone-Tukey, qui s'énonce de la manière suivante : « Un ensemble de n points en dimension d peut toujours être séparé en 2 parties de cardinal au plus n/2 par un hyperplan de dimension d - 1 ». Il procède pour cela en trois temps. · Une courte première partie, très facile, permet d'obtenir deux algorithmes de base sur les tableaux, l'un pour renvoyer l'indice d'une case contenant le plus grand élément du tableau, l'autre pour renvoyer le nombre d'éléments du tableau qui sont plus petits qu'une valeur donnée. · La deuxième partie a pour objectif de calculer l'élément médian d'un tableau. L'énoncé demande en fait une généralisation de ce problème, à savoir la recherche du k-ième élément. Cet algorithme repose sur une partition des données du tableau, en les comparant à une valeur particulière appelée « pivot ». Afin d'améliorer la complexité de la recherche, la dernière question permet de déterminer le pivot à utiliser dans cette partition. · Enfin, la troisième partie se place en dimension 2 et utilise les algorithmes précédents pour généraliser le problème du médian. L'objectif est de séparer un ensemble de n points par deux droites, de telle sorte que chaque cadran contienne moins de n/4 points. Au final, ce problème est plutôt facile. Comme souvent, il est regrettable que le jury ait fait le choix de détailler précisément plusieurs algorithmes (questions 4 et 10), ne demandant aux candidats que de traduire ces lignes dans le langage de leur choix. Ce sujet permet malgré tout de bien réviser les opérations classiques sur les tableaux. Indications Partie 1 1 Utiliser une variable temporaire resultat pour stocker la valeur de l'indice de la plus grande case du tableau. Parcourir le tableau en comparant pour chaque indice i la valeur de la case tab[i] et celle de tab[resultat]. Si la première est plus grande, mettre à jour la variable resultat. 2 Effectuer un parcours du tableau en comparant à chaque étape i la valeur de la case tab[i] et val. Le cas échéant, incrémenter la variable résultat. Partie 2 3 Parcourir le tableau en utilisant deux tableaux annexes pour stocker les éléments plus petits (dans tab_inf) et plus grands (dans tab_sup) que le pivot. Les compter à l'aide de deux variables temporaires et compter les éléments égaux au pivot à l'aide d'une variable supplémentaire nb_pivot. Finalement, écraser le tableau initial avec les éléments de tab_inf puis nb_pivot éléments égaux au pivot et enfin les éléments de tab_sup. 6 Calculer l'indice médian de chaque sous-tableau et enregistrer les résultats dans un tableau indicemedian. Décaler ensuite les éléments correspondants au début du tableau. Partie 3 8 Créer un tableau pour contenir les angles entre (x, y) et les éléments dont l'ordonnée est supérieure à y. Renvoyer alors l'indice médian de ce tableau. 9 Comme à la question précédente, enregistrer les angles entre (x, y) et les éléments dont l'ordonnée est strictement inférieure à y. Parcourir ensuite ce tableau pour compter le nombre d'angles inférieurs ou supérieurs à theta. Sandwich au jambon Les programmes de ce corrigé sont écrits en Maple. L'énoncé demande des modifications des tableaux donnés en argument, ce qui n'est pas possible avec la structure de liste. Afin de respecter cette demande tout en proposant des codes qui fonctionnent, les programmes de ce corrigé utilisent la structure array, ce qui crée quelques complications dans leur écriture. Un jour de concours, une structure de liste aurait parfaitement fait l'affaire. L'énoncé fait l'hypothèse de l'existence d'une primitive allouer(m,c), qui crée un tableau de taille m dont chaque case contient c à l'origine, ainsi que d'une primitive taille(t) qui renvoie la taille d'un tableau t. On donne ici deux instanciations possibles de ces primitives et les exemples associés : allouer := proc(m,c) local t,i; t := array(1..m); for i from 1 to m do t[i] := c; od; RETURN(t); end; t := allouer(7,4); print(t); t := t [4, 4, 4, 4, 4, 4, 4] taille := proc(t) RETURN(nops([entries(t)])); end; taille(t); 7 Enfin, l'énoncé suppose l'existence d'une fonction floor(x) qui renvoie la partie entière x pour tout réel x > 0. Cette fonction a bien ce nom en Maple. I. Grand, petit et médian 1 La fonction calculeIndiceMaximum prend en argument un tableau tab et deux indices a et b, et doit renvoyer un indice a<=i<=b du tableau tel que l'élément tab[i] soit le plus grand du tableau. Pour cela, elle initialise le résultat resultat à a. Elle parcourt ensuite les cases du tableau à l'aide d'une boucle for. Pour tout i de a+1 jusqu'à b, elle teste la valeur de tab[i]. Si cette valeur est supérieure à tab[resultat], alors la variable resultat prend la valeur i, sinon, la fonction passe à la case d'indice i+1. Enfin, elle renvoie la variable resultat. calculeIndiceMaximum := proc(tab,a,b) local resultat, i; resultat := a; for i from a+1 to b do if tab[i] > tab[resultat] then resultat := i; fi; od; RETURN(resultat); end; Sur l'exemple demandé, l'application de ce programme donne tableau := array(1..11,[3,2,5,8,1,34,21,6,9,14,8]); tableau := [3, 2, 5, 8, 1, 34, 21, 6, 9, 14, 8] calculeIndiceMaximum(tableau,1,11); 6 Notons que l'énoncé demande de renvoyer l'indice d'une case, mais que ce dernier n'est pas unique (si plusieurs cases contiennent le plus grand élément du tableau). On peut donc choisir de renvoyer le premier (comme ici, en utilisant un supérieur strict dans le test), le dernier (il faudrait alors utiliser un supérieur ou égal), ou encore n'importe quel autre. Remarquons également que l'énoncé ne demande jamais de vérifier si le calcul demandé est licite, à savoir si 1<=a<=b<=taille(tab). On a pris le parti dans ce corrigé de ne pas tester ces inégalités, mais on pourrait rajouter, au début de chaque programme demandé, des lignes du type if not(1<=a and a<=b and b<=taille(tab)) then ERROR('Les indices demandés ne sont pas compatibles avec le tableau tab.'); fi; 2 La fonction nombrePlusPetit prend en argument un tableau tab, deux indices a et b et un nombre val, et doit renvoyer le nombre d'éléments du tableau tab[a..b] dont la valeur est inférieure ou égale à val. Pour cela, elle initialise ce nombre nombre à 0 et parcourt le tableau à l'aide d'une boucle for. À l'étape i, si l'élément tab[i] est inférieur ou égal à la valeur val, la variable nombre est augmentée de 1. Sinon, on passe directement à l'élément i+1. Cela donne le code suivant : nombrePlusPetit := proc(tab,a,b,val) local nombre, i; nombre := 0; for i from a to b do if tab[i] <= val then nombre := nombre + 1; fi; od; RETURN(nombre); end; On a bien le résultat demandé par l'énoncé : nombrePlusPetit(tableau,1,11,5); 4