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)
                 

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