X Informatique MP 2004

ÉCOLE POLYTECHNIQUE FILIÈRE MP
(JPÏÈUÛPJlÎOEFCHRLÆAOEÈUQÏIË

CONCOURS D'ADMISSION 2004

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.

***

Médians et Convexité

On attachera une grande importance à la concisz'on, & la clarté, et à la 
précision de la rédaction.
Les deux problèmes sont indépendants.

Premier problème : Sélection

Un médian d'un ensemble X : {e1,e2, . . . en} de n nombres entiers distincts 
est un nombre e
dans X tel que les nombres d'éléments strictement plus petits et strictement 
plus grands que e dans
X diffèrent d'au plus de 1 (n > 0). Si n est impair, le médian est unique ; si 
n est pair, il y a deux
médians possibles.

Le problème de la sélection consiste à trouver l'élément de rang le dans X, 
c'est--à--dire l'élément e
se trouvant en k-ième position quand X est trié en ordre croissant (1 5 k 5 n).

Nous supposerons l'ensemble X représenté par la liste de ses éléments, 
c'est-à--dire par le type
ensemble défini par :

(* Caml *) { Pascal }

type
ensemble = "cellule;
cellule = record contenuzinteger;

suivant:ensemble; end;

type ensemble == int list;;

En Pascal, la liste vide est nil et l'on pourra utiliser la fonction suivante 
pour construire les listes :

function cons(xzinteger; s:ensemble) : ensemble;

var r:ensemble;
begin new(r); r'.contenu := X; r".suivant := s; cons := r end;

Cette fonction est applicable pour construire les listes du type ensemble.

Question 1. Ecrire la fonction card qui prend un ensemble en argument et 
retourne son nombre
d'éléments.

(* Caml *) { Pascal}

card : ensemble --> int function card(X:ensemble) : integer;

Quelle est la complexité en temps de cette fonction par rapport a n?

Soit p un entier quelconque, on sera amené à partitionner l'ensemble X en 
éléments plus grands,
égaux ou plus petits que p.

Question 2. Écrire la fonction nPet its qui prend en arguments un entier p et 
l'ensemble X ; et qui
retourne le nombre d'éléments strictement inférieurs à p dans X.

(* Caml *) { Pascal }

function nPetits

nPetits : int -> ensemble --> int . .
(p:1nteger; X:ensemble) : 1nteger;

Quelle est la complexité en temps de cette fonction par rapport à n?

Pour sélectionner le [»:--ième élément de X, on prend un nombre p bien choisi 
dans X , appelé pivot
(p E X), et on effectue une partition de X par rapport a p.

Question 3. Écrire la fonction partitionP qui prend en arguments un entier p et 
l'ensemble X ;
et qui retourne l'ensemble de tous les éléments de X strictement plus petits 
que p.

(* Caml *) { Pascal}

function partitionP

artitionP : int --> ensemble --> ensemble
p (pzinteger; )ï:ensemble) : ensemble;

Modifier cette fonction pour obtenir la fonction partitionG qui retourne 
l'ensemble de tous les
éléments de X strictement plus grands que p. Quelles sont les complexités en 
temps de ces fonc--
tions par rapport a n?

Question 4. Écrire la fonction récursive elementDeRang qui prend en arguments 
un nombre k entier
naturel et l'ensemble X ; et qui retourne l'élément de rang lc dans X, en 
choisissant comme pivot le
premier élément de la liste représentant X.

(* Caml *) { Pascal }

function elementDeRang

elementDeRan : int --> ensemble --> int
g (kzinteger; )(:ensemble) : integer;

Le nombre d'opérations pris par la fonction précédente varie en fonction du 
choix du pivot.

Question 5. Donner un ordre de grandeur, par rapport a n, du nombre maximum M 
(n) d'opérations
pris parla fonction précédente.

En supposant équiprobables tous les rangs possibles pour le pivot choisi dans X 
, on peut démontrer
que le temps moyen pris par elementDeRang est borné supérieurement par T (n) où 
T est une fonction
croissante, vérifiant T (O) = 0 et la formule de récurrence suivante :

T(n) S Ën + % Zmax{T(i --- 1),T(n -- i)}

(E est une constante indépendante de n et k).

Question 6. En déduire une constante c, qu'on déterminera en fonction de EUR, 
telle que, pour tout n
entier naturel, on a T(n) 5 ca.

On s'intéresse à présent à optimiser le coût dans le cas le pire M (n) 
Considérons d'abord les sous--
ensembles X.- = {65i+1,65i+2,651+3, e5i+4,e5i+5} de 5 éléments consécutifs dans 
X pour 0 5 51 < n. Soit Y l'ensemble des médians des Xi.' Question 7. Écrire une fonction medians qui prend en arguments l'ensemble X ; et qui retourne l'ensemble Y. (* Caml *) ' { Pascal} medians : ensemble --> ensemble function medians (X:ensemble) : ensemble;

Quelle est la complexité en temps pris par cette fonction par rapport à n?

Pour améliorer la vitesse de la fonction de sélection, on prend a présent comme 
pivot le médian de
l'ensemble Y.

Question 8. Écrire la fonction elementDeRangBis qui prend en argument un entier 
naturel k et
l'ensemble X ; et qui retourne l'élément de rang 1: dans X , en prenant comme 
pivot le médian de
l'ensemble Y.

(* Caml *) { Pascal}

function elementDeRangBis

elementDeRan Bis : ' t --> ensemble --> ' t
g in in (kzinteger; )(:ensemble) : integer;

Question 9. Montrer que son temps maximum M ' (n) vérifie la formule :

M'(n) S Ë'n+M'({--ÊJ) +M'(7 {%J +4)

où {cd est la partie entière de :c, et EUR' est une constante que l'on ne 
cherchera pas a expliciter. En
déduire que, pour n suffisamment grand, on a M ' (n) S c'n où c' est une 
constante à déterminer en
fonction de E' .

Question 10. Expliquer pourquoi l'ordre de grandeur du nombre maximal 
d'opérations pris par la
fonction de sélection serait différent si on avait regroupé les éléments de X 
par groupes de 3, plutôt
que par groupes de 5.

Second problème : Localisation dans un polygone convexe

Dans un repère cartés1en, les points sont représentés par des enregistrements 
de type point défini par

(* Caml *) { Pascal }

type point = {x:int; y:int};; type point = record x:integer; y:integer end;

Question 11. Écrire la fonction orientation qui prend comme arguments trois 
points P, Q, R ;
et qui retourne +1, 0 ou --1 selon que l'angle & formé par les demi--droites 
[PQ) et [FR) vérifie soit
0 point --> point --> int (Pzpoint; Q:point, R:point) : integer;

La région p(Q1Q2R1 R2), encore appelée région à droite du zlgzag Q1Q2R1R2, est 
définie par trois
éléments :

o la demi-droite partant de l'infini et finissant en Q2 de vecteur directeur 
Q2Q1,

. le segment de droite Q2R2,

. la demi-droite partant de R2 et de vecteur directeur R1 R2.

R2 R1

Q2
Q1

La région p(Q1Q2R1 R2) se situe donc à droite de ces trois éléments pour un 
observateur les parcourant
dans le sens indiqué.

Question 12. Écrire la fonction aDroiteDe qui prend comme arguments les points 
Q1, Q2, R1, R2,
T ; et qui teste si le point T est a droite du zigzag Q1Q2R1R2.

(* Caml *) { Pascal}

function aDroiteDe
(Qypoint; Q2:point;
Rppoint; R2zpoint;
T:point): boolean;

aDroiteDe :
point -> point -->
point --> point --> point --> bool

À présent, on se donne un polygone convexe POP1P2 . . . Pn_1 de n côtés (n 2 
3), et on cherche
à déterminer si un point P quelconque est a l'intérieur de ce polygone, en 
décomposant le plan par
rapport au polygone de la façon suivante :

L'extérieur du polygone est composée des secteurs si délimités par les 
demi-droites [R-_1R-) et
[BH-+1) pour tout z' vérifiant 0 S 2' < 71 (les calculs d'indice se feront toujours dans l'arithmétique modulo n). L'intérieur du polygone est décomposé en triangles en considérant la construction arbores- cente suivante : plan p(P0P1P3P4) p(P3P4POP1) [)(P1P2P3P4) ,O(P3P4P5P6) p( ()P5P6P0P1 && JëA La racine est un noeud spécial représentant tout le plan. Tout noeud interne p (P--1,PPj_ 1Pj) représente la région a droite du zigzag Pz_1P Pj_1Pj . Remarque . p(Pz_1P Pj_1Pj) est la réunion des secteurs si, si+1, . . . sj_1 et de l'intérieur du polygone HP.--+1 . . . Pj_1PJ--. Les feuilles sont les secteurs si déterminés par les trois points Pi_1, Pi, Pi+1 comme expliqué précédemment. Dans cette construction arborescente, chaque noeud (sauf la racine) est découpé en trois parties disjointes, deux de ces parties correspondent aux régions associées aux deux fils, et la troisième est le triangle EPkPj intérieur au polygone (où Pk est le nouveau point apparaissant dans la définition des fils, en 4ème position dans le fils gauche et en 2ème dans le fils droit). Le polygone est représenté par la liste (PO, P1, . . . Pn_1) de ses sommets (dans l'ordre). L'arbre précédent de décomposition du plan est représenté par des éléments du type arbre défini par : (* Caml *) { Pascal } type listePoints == type point list;; listePoints = "cellule; cellule = record type arbre = contenu:point; suivantzlistePoints; Racine of end; arbre*arbre tNoeud = (Racine, Noeudlnterne, Feuille); | Noeud of arbre = "noeud; noeud = record case indicateur of point*point Racine: (gauchezarbre; droitezarbre); *point*point Noeudlnterne: (q1:point; q2:point; *arbre*arbre r1:point; r2:point; | Feuille of gauchezarbre; droitezarbre); point*point Feuille: (q1:point; q2:point; q3:point); *point;; end; L'arbre est équilibré si, pour chacun de ses noeuds, la différence de hauteur entre ses deux fils a une valeur absolue inférieure ou égale à 1. Question 13. Écrire la fonction construire qui prend en argument la liste (P0, P1, . . . Pn__1) ; et qui retourne un arbre équilibré représentant sa décomposition arborescente. Donner la complexité en temps pris par cette fonction en fonction de n. (* Caml *) { Pascal} construire : listePoints --> arbre function construire 
(polygone:listePoints):arbre;

Question 14. Avec quels arguments peut--on appeler la fonction aDroiteDe pour 
tester si le point
T est dans le secteur si?

Question 15. Écrire la fonction aLlnterieurDe qui prend en argument un arbre 
équilibré a et un
point T ; et qui teste si T est dans le polygone représenté par a. Donner la 
complexité en temps de

cette fonction par rapport à. n.

(* Caml *) { Pascal }
aLlnterieurDe : function aLlnterieurDe
arbre ---> point --> bool ' (azarbre; T:point) : boolean;

Si T est un point a l'extérieur du polygone, les tangentes a partir de T par 
rapport au
polygone convexe POP1 . . . Pn_1 sont les deux droites issues de T qui touchent 
le polygone sans couper
son intérieur. La tangente de gauche se trouve a gauche pour un observateur en 
T faisant face au

polygone ; l'autre tangente est la tangente de droite.

Question 16. Écrire la fonction tangenteG qui prend en arguments un arbre 
équilibré a et un point
T ; et qui retourne un sommet P; du polygone P0P1 . . . Pn_1, représenté par 
l'arbre a, point de contact
de la tangente de gauche issue d'un point T a l'extérieur du polygone. Donner 
la complexité en temps

de cette fonction par rapport à n.

(* Caml *) { Pascal }
tangenteG : arbre --> point --> point function tangenteG (azarbre; T:point) : 
point;

Question 17. Donner une idée de modification des fonctions ou des structures de 
données

précédentes pour obtenir également un point de contact de la tangente de droite.

* *
*