Informatique 2004 Classe Prepa MP Ecole Polytechnique

Description

Examen du Supérieur Ecole Polytechnique. Sujet de Informatique 2004. Retrouvez le corrigé Informatique 2004 sur Bankexam.fr.

Sujets

• Informatique
• 2004
• École polytechnique

Informations

• Publié par: bankexam
• Publié le: 28 février 2007
• Nombre de lectures: 100
• Langue: Français

Extrait

´ ECOLE POLYTECHNIQUE

CONCOURS D’ADMISSION 2004

` MP FILIERE OPTION INFORMATIQUE

COMPOSITION D’INFORMATIQUE (Dur´ee:4heures)

L’utilisation des calculatricesne’oris´eestpasautrpe´evuecruoettep. Lelangagedeprogrammationchoisiparlecandidatdoiteˆtrespe´cifie´enteˆtedelacopie.  

M´ediansetConvexite´

Onattacheraunegrandeimportancea`laconcision,`alaclarte´,eta`lapre´cisiondelare´daction. Lesdeuxprobl`emessontinde´pendants.

Premierprobl`eme:Se´lection

Unme´diand’un ensembleX={e 1 , e 2 , . . . e n }dennombres entiers distincts est un nombree dansXetsplutptrtsseittnemetcinargsulpombrlesn´el´esd’sttsmenemeneirtcdlsqquueeteedans Xdiff`eertn’dualpsued(1n >0). Sintiesaimpel,rde´menainutss;iqieunest pair, il y a deux m´edianspossibles. Leproble`medelactle´esoinnaregts`etaorcnoisl´ementduverl’´ekdansX,se’c’´el´eel`at-ir-dntmee se trouvant enkeme`i-noitisopdquanXceorrordtn1(siases´eenttri≤k≤n). Nous supposerons l’ensembleXlasietedes´slee´repr´esent´eparlpetylearepird-a`-tse’c,stnem ensemble:rinap´dfie (*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 -> int function card(X:ensemble) : integer; Quelleestlacomplexite´entempsdecettefonctionparrapporta`n? Soitpeblue,oconqqueltiernuneemns’erlneontitirapa`e´nemaaresnX´eeneml´tsensulpnarg,sd ´egauxoupluspetitsquep. ´ Question 2.Ecrire la fonctionnPetitsqui prend en arguments un entierpet l’ensembleX; et qui retournelenombred’e´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 (p∈X), et on effectue une partition deXppro`tapraarp. ´ Question 3.Ecrire la fonctionpartitionPqui prend en arguments un entierpet l’ensembleX; etquiretournel’ensembledetousles´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;

Lenombred’ope´rationsprisparlafonctionpr´ec´edentevarieenfonctionduchoixdupivot. Question 5.a`rtpoaprrpar,eundgearrddenuronnreDon, du nombre maximumM(n’op´eratoisn)d prisparlafonctionpre´c´edente. Ensupposante´quiprobablestouslesrangspossiblespourlepivotchoisidansXo,motnerr´etdeunp que le temps moyen pris parelementDeRangesn´´eupeurimereserobtrpantT(n`u)oTest une fonction croissante,ve´rifiantTumelfaroe0lt0(=)ncreuiesr´deurectnav:e n  1 T(n)≤ n+ max{T(i−1), T(n−i)} n i=1 (etsnuceetnatsnonepe´dnieedntdanetk). 2

Question 6.End´eduirueenocsnattneconu’etd´mierraneofneitcnednoq,, telle que, pour toutn entier naturel, on aT(n)≤cn.

Ons’inte´resse`apre´senta`optimiserlecoˆutdanslecaslepireM(nrdlessouonsd’abonois´dre)C.-s ensemblesX i ={e 5i+1 , e 5i+2 , e 5i+3 , e 5i+4 , e 5i+5 }ns´etscoemen´el´tdic5uedafsnsXpour 0≤5i < n. SoitYedslsne’embledesm´ediansX i . ´ 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)valofirefi:emrlu    n n    M(n)≤ n+M( )+M(7 +4) 5 10  ou`xlasteeniertpati`eredex, etticiE.rea`salpxecheraperonl’chneattnqeeuutenocsnesn   d´eduireque,pournsuffisamment grand, on aM(n)≤c no`ucnatsnocenutsea`ette´dimreerenn  fonction de. Question 10.Epxiluqerpourquoil’ordrnopsaritraalirpsdnargedemonudrueimaxembr´eopd’al fonctiondese´lectionseraitdiffe´rentsionavaitregroup´eles´el´ementsdeXottˆlu,pe3rguoepdspra que par groupes de 5.

Secondprobl`eme:Localisationdansunpolygoneconvexe

Dansunrep`erecart´esien,lespointssontrepre´sente´spardesenregistrementsdetypepointinfierapd´ (*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 ou−1 selon que l’angleαoitei-drs[pe´mrofmedselraP Q) et [P Re´irv)tiefios 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ρ(Q 1 Q 2 R 1 R 2 ncor),eel´eeappignoree´izudgazgioeta`rdQ 1 Q 2 R 1 R 2 iosepnitrarst,eefid´ ´ele´ments: −−−→ •la demi-droite partant de l’infini et finissant enQ 2 de vecteur directeurQ 2 Q 1 , •le segment de droiteQ 2 R 2 , −−−→ •la demi-droite partant deR 2 et de vecteur directeurR 1 R 2 . R 2 R 1 |

Q 2 | Q 1

Lare´gionρ(Q 1 Q 2 R 1 R 2 )secedetile´siortedtusiseroadc`onlesparcoervateuruouronsbe´emtnpsnarut danslesensindique´. ´ Question 12.Ecrire la fonctionaDroiteDequi prend comme arguments les pointsQ 1 ,Q 2 ,R 1 ,R 2 , T; et qui teste si le pointTroitt`adigzaeduzgseQ 1 Q 2 R 1 R 2 . (*Caml*){Pascal} function aDroiteDe aDroiteDe : (Q 1 :point;Q 2 :point; point -> point -> R 1 :point;R 2 :point; point -> point -> point -> bool T:point): boolean;

` Apre´sent,onsedonneunpolygoneconvexeP 0 P 1 P 2 . . . P n−1 denˆot´es(cn≥3), et on cherche a`de´terminersiunpointPpaanr´dcemoopastnellprdecepolygone,eni’la`tseueire´tnquuenqcoel rapportaupolygonedelafac¸onsuivante:

4