X Informatique MP/PC 2012

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