´ ECOLE POLYTECHNIQUE
CONCOURS D’ADMISSION 2004
` MP FILIERE OPTION INFORMATIQUE
COMPOSITION D’INFORMATIQUE (Dur´ee:4heures)
L’utilisation des calculatricesneoris´eestpasautrpe´evuecruoettep. Lelangagedeprogrammationchoisiparlecandidatdoiteˆtrespe´cie´enteˆtedelacopie.  
M´ediansetConvexite´
Onattacheraunegrandeimportancea`laconcision,`alaclarte´,eta`lapre´cisiondelare´daction. Lesdeuxprobl`emessontinde´pendants.
Premierprobl`eme:Se´lection
Unme´diand’un ensembleX={e1, e2, . . . en}dennombres entiers distincts est un nombree dansXetsplutptrtsseittnemetcinargsulpombrlesn´el´esdsttsmenemeneirtcdlsqquueeteedans Xdi`eertndualpsued(1n >0). Sintiesaimpel,rde´menainutss;iqieunest pair, il y a deux m´edianspossibles. Leproble`medelactle´esoinnaregts`etaorcnoisl´ementduverl´ekdansX,sec´el´eel`at-ir-dntmee se trouvant enkeme`i-noitisopdquanXceorrordtn1(siases´eenttrikn). Nous supposerons l’ensembleXlasietedes´slee´repr´esent´eparlpetylearepird-a`-tsec,stnem ensemble:rinap´de (*Caml*){Pascal} type ensemble = ^cellule; type ensemble == int list;; cellule = record contenu:integer; suivant:ensemble; end; En Pascal, la liste vide estnilet l’on pourra utiliser la fonction suivante pour construire les listes :
function cons(x:integer; 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 typeensemble.
1
´ Question 1.Ecrire la fonctioncardqui prend un ensemble en argument et retourne son nombre d´el´ements. (*Caml*){Pascal} card : ensemble -> intfunction card(X:ensemble) : integer; Quelleestlacomplexite´entempsdecettefonctionparrapporta`n? Soitpeblue,oconqqueltiernuneemnserlneontitirapa`e´nemaaresnX´eeneml´tsensulpnarg,sd ´egauxoupluspetitsquep. ´ Question 2.Ecrire la fonctionnPetitsqui prend en arguments un entierpet l’ensembleX; et qui retournelenombrede´l´ementsstrictementinf´erieurs`apdansX. (*Caml*){Pascal} function nPetits nPetits : int -> ensemble -> int (p:integer;X:ensemble) : integer; Quelleestlacomplexit´eentempsdecettefonctionparrapport`an? Pours´electionnerlekdtnee`e-i´emeeml´X, on prend un nombrepbien choisi dansX´eppel,apivot (pX), et on effectue une partition deXppro`tapraarp. ´ Question 3.Ecrire la fonctionpartitionPqui prend en arguments un entierpet l’ensembleX; etquiretournelensembledetousles´el´ementsdeXstrictement plus petits quep. (*Caml*){Pascal} function partitionP partitionP : int -> ensemble -> ensemble (p:integer;X:ensemble) : ensemble; Modifier cette fonction pour obtenir la fonctionpartitionGqui retourne l’ensemble de tous les e´l´ementsdeXstrictement plus grands quepestntie´lpxecsmontleessouell.Qc-onsfcedepsem tionsparrapporta`n? ´ Question 4.relafonctionr´ecisruevcEirelementDeRangqui prend en arguments un nombrekentier naturel et l’ensembleXdentngraelrnouetme´eel´riuqte;kdansX, en choisissant comme pivot le premier´ele´mentdelalisterepre´sentantX. (*Caml*){Pascal} function elementDeRang elementDeRang : int -> ensemble -> int (k:integer;X:ensemble) : integer;
Lenombredope´rationsprisparlafonctionpr´ec´edentevarieenfonctionduchoixdupivot. Question 5.a`rtpoaprrpar,eundgearrddenuronnreDon, du nombre maximumM(nop´eratoisn)d prisparlafonctionpre´c´edente. Ensupposante´quiprobablestouslesrangspossiblespourlepivotchoisidansXo,motnerr´etdeunp que le temps moyen pris parelementDeRangesn´´eupeurimereserobtrpantT(n`u)oTest une fonction croissante,ve´riantTumelfaroe0lt0(=)ncreuiesr´deurectnav:e n 1 T(n) n+ max{T(i1), T(ni)} n i=1 (etsnuceetnatsnonepe´dnieedntdanetk). 2
Question 6.End´eduirueenocsnattneconuetd´mierraneofneitcnednoq,, telle que, pour toutn entier naturel, on aT(n)cn.
Onsinte´resse`apre´senta`optimiserlecoˆutdanslecaslepireM(nrdlessouonsdabonois´dre)C.-s ensemblesXi={e5i+1, e5i+2, e5i+3, e5i+4, e5i+5}ns´etscoemen´el´tdic5uedafsnsXpour 05i < n. SoitYedslsneembledesm´ediansXi. ´ Question 7.Ecrire une fonctionmediansqui prend en arguments l’ensembleX; et qui retourne l’ensembleY. (*Caml*){Pascal} medians : ensemble -> ensemblefunction medians (X:ensemble) : ensemble; Quelleestlacomplexit´eentempsprisparcettefonctionparrapporta`n?
Pourame´liorerlavitessedelafonctiondes´election,onprenda`pre´sentcommepivotleme´diande l’ensembleY. ´ Question 8.Ecrire la fonctionelementDeRangBisqui prend en argument un entier naturelket l’ensembleX;quetngmentderale´lee´riteuonrkdansX´meltoviednaidenarenp,eepmmcont l’ensembleY. (*Caml*){Pascal} function elementDeRangBis elementDeRangBis : int -> ensemble -> int (k:integer;X:ensemble) : integer;
Question 9.Montrer que son temps maximumM(n´e)valofire:emrlu    n n   M(n) n+M( )+M(7 +4) 5 10 ou`xlasteeniertpati`eredex, etticiE.rea`salpxecheraperonlchneattnqeeuutenocsnesn  d´eduireque,pournsuffisamment grand, on aM(n)c no`ucnatsnocenutsea`ette´dimreerenn fonction de. Question 10.Epxiluqerpourquoilordrnopsaritraalirpsdnargedemonudrueimaxembr´eopdal fonctiondese´lectionseraitdie´rentsionavaitregroup´eles´el´ementsdeXottˆlu,pe3rguoepdspra que par groupes de 5.
Secondprobl`eme:Localisationdansunpolygoneconvexe
Dansunrep`erecart´esien,lespointssontrepre´sente´spardesenregistrementsdetypepointinerapd´ (*Caml*){Pascal} type point = {x:int; y:int};;type point = record x:integer; y:integer end;
3
´ Question 11.Ecrire la fonctionorientationqui prend comme arguments trois pointsP,Q,R; et qui retourne +1, 0 ou1 selon que l’angleαoitei-drs[pe´mrofmedselraP Q) et [P Re´irv)tieos 0< α < π, soitα∈ {0, π}, soitπ < α <2π.
R
P Q +1 (*Caml*) orientation : point -> point -> point -> int
Q
P R 1 {Pascal} function orientation (P:point;Q:point,R:point) : integer;
Lare´gionρ(Q1Q2R1R2ncor),eel´eeappignoree´izudgazgioeta`rdQ1Q2R1R2iosepnitrarst,eed´ ´ele´ments: −−−→ la demi-droite partant de l’infini et finissant enQ2de vecteur directeurQ2Q1, le segment de droiteQ2R2, −−−→ la demi-droite partant deR2et de vecteur directeurR1R2. R2R1 |
Q2 | Q1
Lare´gionρ(Q1Q2R1R2)secedetile´siortedtusiseroadc`onlesparcoervateuruouronsbe´emtnpsnarut danslesensindique´. ´ Question 12.Ecrire la fonctionaDroiteDequi prend comme arguments les pointsQ1,Q2,R1,R2, T; et qui teste si le pointTroitt`adigzaeduzgseQ1Q2R1R2. (*Caml*){Pascal} function aDroiteDe aDroiteDe : (Q1:point;Q2:point; point -> point -> R1:point;R2:point; point -> point -> point -> bool T:point): boolean;
` Apre´sent,onsedonneunpolygoneconvexeP0P1P2. . . Pn1denˆot´es(cn3), et on cherche a`de´terminersiunpointPpaanr´dcemoopastnellprdecepolygone,enila`tseueire´tnquuenqcoel rapportaupolygonedelafac¸onsuivante:
4