Epreuve facultative 2004 Classe Prepa PC Ecole Polytechnique
4 pages
Français
Cet ouvrage peut être téléchargé gratuitement

Epreuve facultative 2004 Classe Prepa PC Ecole Polytechnique

Cet ouvrage peut être téléchargé gratuitement
4 pages
Français

Description

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

Sujets

Informations

Publié par
Publié le 28 février 2007
Nombre de lectures 59
Langue Français

Exrait

´ ECOLE POLYTECHNIQUE ´ ´ ECOLE SUPERIEURE DE PHYSIQUE ET CHIMIE INDUSTRIELLES
CONCOURS 2004
`´ MP FILIERE-OPTION PHYSIQUE ET SCIENCES DE L’INGENIEUR
COMPOSITION D’INFORMATIQUE (Dure´e:2heures)
FILIEREPC `
L’utilisation des calculatricesee´orissautstpanerpe´ettecruop.veeu Lelangagedeprogrammationchoisiparlecandidatdoitˆetresp´ecie´entˆetedelacopie.  
Compressionternaire
Onattacheraunegrandeimportance`alaconcision,a`laclarte´,et`alapre´cisiondelare´daction. Onsupposeraquelelangagedeprogrammationutilis´eposse`dedeuxope´rationsxdivyetxmody donnant le quotient et le reste de la division euclidienne dexpary.
Letempsdex´ecutionT(f) d’une fonctionflestmbnodre´eopitar´snoe´letnemid-(sdaiaere tion,soustraction,multiplication,division,aectation,etc.)ne´cessaireaucalculdef. Lorsque cetempsdexe´cutionde´penddunparam`etrene´tonarels,iTn(f). Ondit que la fonctionf sex´ecute:
etnpsemn´liaierenren, s’il existeK >0 tel que pour toutn,Tn(f)Kn; 2 en temps quadratique enn, s’il existeK >0 tel que pour toutn,Tn(f)Kn.
Nombres ternaires
Enbase3,lesentiers0,1,2,3,4,5,6,7,8sontrepr´esente´spar00,01,02,10,11,12,20, 21,22. Lechiffre de poids fort debcestb; le chiffre de poids faible estc.
Question 1. bcen base 3.
´ Ecrire la fonctionentier(b,cneitreocpmirestnre0et8quis´ecritltnanruoter)
1
´ Question 2.Soitxtierunenianv´er0txune fonction8. EcrirepoidsFort(x) retournant ´ le chiffre de poids fort dexEcrire la fonctionen base 3.poidsFaible(x) retournant le chiffre de poids faible dex.
Textes ternaires
Dansceproble`me,lestextessontrepre´sent´esenrepre´sentationternaire.Unsavantrusse nousaconvaincusdelapertinencedecechoixpluscompactquelarepre´sentationbinaire.Un texteestrang´edansuntableautdeNact`eresv´eriantract[i]∈ {0,1,2}pour toutiv´tanier 0i < Npar ailleurs1 ;t[N1] =X >nreteriasensaptOn).(led2reacreine`erartc supposeN1.
Quelquesde´nitionssontne´cessaires:lachaıˆnedecaract`eresdelongueurtnneraar´dmei est la suitet[i], t[i+ 1], . . . t[i+1]O.dneuedriqaınaˆchuxest[i], t[i+ 1], . . . t[i+1]et   t[j], t[j+ 1], . . . t[j+1]t´onalegsiess=ett[i+k] =t[j+k] pour 0k < .
´ Question 3.Ecrire une fonctionlongueurMotif(t, i, j, mreui)qarn´eaireptnmespilotruene, rapporta`N, la plus grande longueurdd´neeˆcıuhnantraaremneied´eaˆınantmarrlage´hcenua`e enjontuE.teeterc,nglourueitdoerv´reim.
´ Question 4.On supposei < june fonction. EcrirelongueurMotifMax(t, i, j, m) qui retourne, entempsquadratiqueparrapporta`N, la plus grande longueure´amrrnahcˆanıdedneuten i+ktnnegda´leem`aarruanechaˆı´neejpour 0k < moutre, on exige. Eni+k < jetm.
Onsupposequilexistetroisvariablesglobalesentie`resA,L,C.
Question 5.ec´edentepourobtelrfanotcoipn´ridoMrineofalitcnnomotifMax(t, i, j, m) qui rend, en temps quadratique, dansLla plus grande longueureunnndtenmedˆ´ırhaaaerci+k ´egalea`unechaıˆned´emarrantenjpour 0k < m; qui rend dansAla valeur dekpour lequeli+kltseparted´eicedindenedahıˆttceedecgnolrueuixamelamui;qndrenennsda ` Critrapa`edlceraca`treseiuvantcettechaˆınejdanstveouAn.teet,caueuruolgn´vreodtiier m. Eton ai+k < j(cf. l’exempledans la figure suivante).
t
= 8 2 1 2 0 1 1 0 2 0 1 1 0 2 0 1 1 2 1 2 0 2 2 C i i+k j A=k= 3;L== 8;C= 2
2
Compression
Lam´ethodedecompressiondeZivetLempel,adopt´eedanslescommandeszipougzip, consistea`rep´ererlesmotifsmaximauxd´ej`arencontr´esdansuntexteeta`indiquerpourchacun d’eux le triplet (A, L, Cdreaiepscediineetnede´tuotertnl´cuanedal)cpnoice´rqalstseuietj. Pourmesurerlefacteurdecompression,nousutilisonslemˆemecodagepourcestripletsque pourlescaracte`resdutexte,cest-a`-direlesyst`emeternairedansceproble`me.
´ Question 6.Ecrire une fonctionimprimerTriplet(A, L, C) qui imprime les argumentsA,L,C sousformedecinqchiresconse´cutifs,lesdeuxcaract`eresternairesdeAsiel,uperesact`xcarsdeu ternaires deL, puis le chiffreC, en imposant 0A <9, 0L <9 et 0C9.
Onsupposea`pre´sentquetesercitnoutnenolnxetgrnaitetemmenrecoptrac¸naca`tc9ra 0 ;en outre,tnuraptine`etrcaracx(laisce´px >efˆnteerettxueenesacceurnd.Opl´e)2 delongueur18.Aude´but,cettefeneˆtreestaligne´e`agauchesurlede´butdutableau,eton posejnteald`eer´neeˆrtceroerpsnoixi`emecasedelafrcedisioere`dal,.E=9´enrmegijdu tableautehedagcuˆntealefdansche,rtielapa.rehcernOedolıˆencaaherl,urnguemaximale ve´riant <rese´dmeceraca`tarrantenge´te9edınaˆchneaue`alja`ecal,emiaˆrg.Onimpr fonctionimprimerTriplet, le triplet (A, L, C)odaprnne´motifMaxe.nr,oisPulertnecerteˆnefa surlecaract`eresuivantlecaract`eredarrˆetC. Ceprocessus continue jusqu’au bout du tableau tiqndeimmco.egruraal´upe
Ainsipourletextesuivant,onobtientlesd´ecompositionsdechacunedeslignes,soitautotal le facteur de compression 30/resiuq73´eupeuri`aret3eadsnelrusasenubeetteaitnmeilment silatailledelafenˆetre´etaitplusgrandeque18(Ilyaeneet30caract`eresdansler´esultatet 37dansletextedentr´ee).
t (0,0,1) (0,1,2) (6,5,1) (2,6,0) (2,8,1) (5,2, x) r´esultat
0 0 0 0 0 0 0 0 0 1 0 2 1 0 2 1 0 1 2 1 0 2 1 0 0 2 1 0 2 1 0 0 2 1 0 0 x 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 2 0 0 0 0 0 0 1 0 2 1 0 2 1 0 1 1 0 2 1 0 2 1 0 1 2 1 0 2 1 0 0 0 1 2 1 0 2 1 0 0 2 1 0 2 1 0 0 2 1 2 1 0 2 1 0 0 2 1 0 0 x 0 0 0 0 10 0 0 1 22 0 1 2 10 2 2 0 00 2 2 2 11 2 0 2 x
´ Question 7.Ecrire une fonctioncompresser(t) qui imprime sur le terminal de sortie le texte compresse´parlame´thodepre´c´edente.
3