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

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