Composition d'Informatique 2004 Classe Prepa PC Ecole Polytechnique

Description

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

Sujets

• 2004
• École polytechnique

Informations

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

Extrait

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

FILIERE PC `

L’utilisation des calculatricesee´orissautstpan’erpe´ettecruop.veeu Lelangagedeprogrammationchoisiparlecandidatdoitˆetresp´ecifie´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.

Letempsd’ex´ecutionT(f) d’une fonctionflestmbnod’re´eopitar´snoe´letnemid-(sdaiaere tion,soustraction,multiplication,division,affectation,etc.)ne´cessaireaucalculdef. Lorsque cetempsd’exe´cutionde´pendd’unparam`etrene´tonarels,iT n (f). Ondit que la fonctionf s’ex´ecute:

•etnpsemn´liaierenren, s’il existeK >0 tel que pour toutn,T n (f)≤Kn; 2 •en temps quadratique enn, s’il existeK >0 tel que pour toutn,T n (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’´ecrit’ltnanruoter)

1

´ Question 2.Soitxtierunenifianv´er0t≤x≤une 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´erifiantract[i]∈ {0,1,2}pour toutiv´tanifier 0≤i < N−par ailleurs1 ;t[N−1] =X >nreteriase’nsaptOn).(led2reacreine`erartc supposeN≥1.

Quelquesde´finitionssontne´cessaires:lachaıˆnedecaract`eresdelongueurtnneraar´dmei est la suitet[i], t[i+ 1], . . . t[i+−1]O.dneuedriqaınaˆchuxest[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 0≤k < .

´ Question 3.Ecrire une fonctionlongueurMotif(t, i, j, mreui)qarn´eaireptnmespilotruene, rapporta`N, la plus grande longueurdd´’neeˆcıuhnantraaremneied´eaˆınantmarrlage´hcenua`e enjontuE.teeterc,nglourueitdoerv´refii≤m.

´ Question 4.On supposei < june fonction. EcrirelongueurMotifMax(t, i, j, m) qui retourne, entempsquadratiqueparrapporta`N, la plus grande longueure´amrrnahcˆanıdedne’uten i+ktnnegda´leem`aarruanechaˆı´neejpour 0≤k < moutre, on exige. Eni+k < jet≤m.

Onsupposequ’ilexistetroisvariablesglobalesentie`resA,L,C.

Question 5.ec´edentepourobtefilrfanotcoipn´ridoMrineofalitcnnomotifMax(t, i, j, m) qui rend, en temps quadratique, dansLla plus grande longueureunnndt’enmedˆ´ırhaaaerci+k ´egalea`unechaıˆned´emarrantenjpour 0≤k < m; qui rend dansAla valeur dekpour lequeli+kltseparted´eiced’indenedahıˆttceedecgnolrueuixamelamui;qndrefinennsda ` Critrapa`edlceraca`treseiuvantcettechaˆınejdanstveouAn.teet,caueuruolgn´vreodtiifier ≤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, Cd’reaiepscediineetnede´tuotertnl´cuanedal)cpnoice´rqalstseuietj. Pourmesurerlefacteurdecompression,nousutilisonslemˆemecodagepourcestripletsque pourlescaracte`resdutexte,c’est-a`-direlesyst`emeternairedansceproble`me.

´ Question 6.Ecrire une fonctionimprimerTriplet(A, L, C) qui imprime les argumentsA,L,C sousformedecinqchiffresconse´cutifs,lesdeuxcaract`eresternairesdeAsiel,uperesact`xcarsdeu ternaires deL, puis le chiffreC, en imposant 0≤A <9, 0≤L <9 et 0≤C≤9.

Onsupposea`pre´sentquetesercitnoutnenolnxetgrnaitetemmenrecoptrac¸naca`tc9ra 0 ;en outre,tfinuraptine`etrcaracx(laisce´px >efˆnteerettxueenesacceurnd.Opl´e)2 delongueur18.Aude´but,cettefeneˆtreestaligne´e`agauchesurlede´butdutableau,eton posejnt’eald`eer´neeˆrtceroerpsnoixi`emecasedelafrcedisioere`dal,.E=9´enrmegijdu tableautehedagcuˆntealefdansche,rtielapa.rehcernOedolıˆencaaherl,urnguemaximale ve´rifiant <rese´dmeceraca`tarrantenge´te9edınaˆchneaue`alja`ecal,emiaˆrg.Onimpr fonctionimprimerTriplet, le triplet (A, L, C)odaprnne´motifMaxe.nr,oisPulertnecerteˆnefa surlecaract`eresuivantlecaract`ered’arrˆetC. Ceprocessus continue jusqu’au bout du tableau tiqndeimmco.egfiruraal´upe

Ainsipourletextesuivant,onobtientlesd´ecompositionsdechacunedeslignes,soitautotal le facteur de compression 30/resiuq73´eupeuri`aret3eadsnelrusasenubeetteaitnmeilment silatailledelafenˆetre´etaitplusgrandeque18(Ilyaeneffet30caract`eresdansler´esultatet 37dansletexted’entr´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