X Informatique MP 2004

Thème de l'épreuve Médiane en temps linéaire. Appartenance à un polygone convexe.
Principaux outils utilisés programmation récursive et diviser pour régner, calculs de complexité, arbres binaires

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

(PDF non trouvé ! |/net/www/doc-solus.fr/www//prepa/sci/adc/pdf/rapports.pdf/2004/MP_INFO_X_1_2004.rapport.pdf|)

Énoncé obtenu par reconnaissance optique des caractères


É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.

* *
*

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



X Informatique MP 2004 -- Corrigé
Ce corrigé est proposé par Jean-Baptiste Rouquier (ENS Lyon) ; il a été relu par
Samuel Mimram (ENS Lyon) et Vincent Puyhaubert (Professeur en CPGE).

Ce sujet est principalement axé sur la programmation. Les questions qui
ne demandent pas de code proposent de calculer des complexités (questions 6, 9 
et 10)
ou d'expliquer comment adapter des fonctions déjà écrites (questions 14 et 17). 
La
difficulté est progressive dans la première partie ; les questions 12 et 13 de 
la seconde
sont les plus difficiles.
Le sujet est constitué de deux problèmes indépendants :
· Le premier propose de construire un algorithme linéaire (qui est classique) 
pour
calculer la médiane d'un ensemble. Les fonctions demandées sont relativement
faciles à écrire, tandis que les questions de complexité sont plus délicates à
rédiger proprement.
· Le second traite de géométrie algorithmique : il propose une méthode efficace
pour tester l'appartenance d'un point à un polygone, puis pour calculer les 
tangentes à ce polygone passant par un point donné. Il est nettement plus 
difficile,
le principale écueil étant souvent de trouver une caractérisation géométrique
efficace de la propriété que doit tester la fonction.
Ces deux problèmes nécessitent des connaissances sur la programmation récursive
(« diviser pour régner »), sur les arbres binaires et sur les calculs de 
complexité à
partir d'une relation de récurrence. Les questions de géométrie algorithmique 
peuvent
être déroutantes à cause des notions introduites, que l'on manipule peu 
souvent. La
question 13 propose de construire un arbre, ce qui peut être traité sans 
utiliser les
notions géométriques.
Pour notre corrigé, nous avons choisi le langage Caml. Tous nos codes ont été 
testés sur ordinateur, de sorte que vous pouvez prendre modèle sur notre 
syntaxe : même
si les correcteurs s'attachent principalement aux aspects algorithmiques, les 
erreurs
de syntaxe répétées peuvent agacer ­ particulièrement quand elles introduisent 
une
ambiguïté.

Indications
I.

Sélection

2 Initialiser un compteur à 0 et le mettre à jour en parcourant la liste.
3 Adapter la fonction précédente : au lieu d'avoir un compteur qui stocke le 
nombre
d'éléments inférieurs à p, maintenir une liste contenant ces éléments.
4 Distinguer trois cas : selon que l'élément cherché est inférieur, égal ou 
supérieur
au pivot. Utiliser les questions précédentes.
5 Supposer par exemple que l'on cherche l'élément de rang 1 (le plus petit 
élément).
Seconde indication : le pire des cas est celui où le pivot est le maximum de
l'ensemble à chaque étape.
6 Procéder par substitution, c'est-à-dire remplacer T(n) par c n dans le membre
de droite et obtenir une majoration de la forme T(n) 6 ( +  c) n avec  < 1.
En déduire c en fonction de  et rédiger dans le bon ordre.
7 Utiliser elementDeRang pour trouver le médian de Xi .
8 Il s'agit de rassembler les questions précédentes. Utiliser elementDeRang 
pour les
cas où |X| < 5 (et uniquement pour ces cas).
9 Soit Z l'ensemble sur lequel est effectué le dernier appel récursif. Quels 
éléments
de X ne peuvent pas appartenir à Z ?
Pour la deuxième partie de la question, procéder par substitution comme à
la question 6. « Pour n assez grand » signifie que l'on peut choisir c de sorte
que la propriété soit vraie pour tout n inférieur à une certaine constante.
10 La complexité moins bonne que O(n) la plus classique est O(n log n).
Seconde indication : procéder là encore par substitution ; cette fois-ci on 
cherche à
montrer que M (n) est de complexité au moins O(n log n) : les inégalités sont 
donc
inversées.
II. Localisation dans un polygone convexe
11 Quel est l'ensemble des vecteurs dont le produit scalaire avec un vecteur 
donné
est positif ?
12 On peut ne traiter que le cas où le zigzag tourne à droite, puis à gauche. 
Exprimer
la région à droite du zigzag comme l'union de deux régions, chacune définie par
deux droites.
Si l'on veut donner une fonction correcte dans tous les cas, utiliser la 
caractérisation suivante : soit S dans la région R voulue, T  R si et seulement 
si le segment
[ST] coupe la frontière de R un nombre pair de fois.
Seconde indication : choisir Q2 comme point de R et dénombrer soigneusement
les intersections.
13 Construire d'abord, par une fonction récursive, un arbre stockant les 
entiers i et j
sur ses noeuds (au lieu des coordonnées des points Pi , Pi+1 , Pj et Pj+1 ).
15 Quels sont les noeuds dont les régions associées contiennent le point T ?
Écrire une fonction récursive.
16 Quel est l'ensemble des points pour lesquels tangenteG doit renvoyer Pi ?
17 Tracer de même l'ensemble des points pour lesquels tangenteD doit renvoyer 
Pi .
On voit que l'on ne peut pas travailler sur le même arbre.

I.

Sélection

Les fonctions comme it_list ou init_vect sont très utiles et sont présentées 
lors de leur utilisation. Elles sont détaillées dans le manuel Caml
(rubrique « The core library ») disponible sur http ://caml.inria.fr/,
ou peuvent être téléchargées sur ftp ://ftp.inria.fr/INRIA/caml-light/.
Si vous avez installé Caml sous Windows grâce au programme cl74win.exe,
ce dernier doit avoir créé un manuel dont le nom est proche de « cl73refman »
ou « cl74refman ».
C'est une erreur de syntaxe en Caml de faire commencer le nom d'une
fonction par une majuscule. Il est donc recommandé par les concepteurs
du langage eux-mêmes de séparer les mots par des soulignés (exemple :
liste_points) au lieu de majuscules (listePoints) comme le fait le sujet.

1 Cette fonction initialise un compteur (accu) à 0 et l'augmente de 1 pour 
chaque
élément de l'ensemble passé en argument.
let card = it_list (fun accu _ -> succ accu) 0;;
Quelques explications sur cette fonction :
· succ i est équivalent à i + 1.
· it_list a pour type ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a.
it_list f a [b1 ; ... ; bn] s'évalue en :
f (... (f (f a b1) b2) ...) bn. L'argument de type 'a est souvent utilisé comme 
un accumulateur qui stocke les résultats intermédiaires.
· On a fait ici une application partielle : it_list attend trois arguments
et n'en reçoit que deux, donc la fonction card attend un argument :
l'ensemble X. On aurait pu écrire de façon équivalente :
let card x = it_list (fun accu _ -> succ accu) 0 x
· Le souligné (_) indique que la fonction anonyme (celle donnée en
argument à it_list) ignore son second argument. En effet, on n'a pas
besoin de la valeur des éléments d'une liste pour compter sa longueur.

La fonction it_list est puissante et l'on gagne souvent un temps précieux
quand on la maîtrise. Mais on peut en général s'en passer ; on aurait ici écrit
simplement :
let rec card = function
| _ :: queue -> 1 + card queue
| [] -> 0
;;

ou bien si l'on souhaite une fonction récursive terminale :
let card ensemble =
let rec recursif_terminal accu = function
| _ :: queue -> recursif_terminal (succ accu) queue
| [] -> accu in
recursif_terminal 0 ensemble
;;
Une fonction est dite récursive terminale si chacun des appels récursifs
possibles est le dernier calcul effectué. Ce n'est pas le cas de la première
fonction de cette remarque, car le dernier calcul de 1 + card queue est
celui de « + » et non l'appel récursif card (c'est-à-dire que l'on doit encore
ajouter 1 après avoir calculé récursivement card queue). Une telle propriété
permet des optimisations économisant de la mémoire lors de la compilation.

Cette première question est destinée à rassurer le candidat et vérifier
qu'il a bien compris les définitions de l'énoncé.
Cette fonction existe déjà en Caml-light, c'est list_length. Cependant,
elle ne coûte qu'une minute à détailler et on fait ainsi bonne impression
auprès du correcteur.
La fonction demandée parcourt tous les éléments de la liste un par un donc :
card s'exécute en temps (n).
On note f (n) = (g(n)) si l'on a f (n) = O(g(n)) et g(n) = O(f (n)).
La notation (n) indique donc que le nombre d'opérations est linéaire,
ce qui est plus précis que O(n) qui signifie que le nombre d'opérations est au
plus linéaire.
2 On modifie la fonction précédente : la seule différence est que l'on 
n'incrémente
le compteur que si l'élément examiné est strictement inférieur à p.
let nPetits p =
it_list (fun accu element ->
if element < p then succ accu else accu) 0;;
Cette fonction parcours également tous les éléments de la liste un par un :
nPetits s'exécute en temps (n).
Ici aussi on peut se passer de it_list, ce qui conduit de même à une fonction
plus longue :
let nPetits p ensemble =
let rec recursif_terminal accu = function
| tete :: queue ->
recursif_terminal
(if tete < p then succ accu else accu)