Composition d

Composition d'Informatique 2004 Classe Prepa PC Ecole Supérieure de Physique et de Chimie Industrielles

Documents
4 pages
Lire
YouScribe est heureux de vous offrir cette publication

Description

Examen du Supérieur Ecole Supérieure de Physique et de Chimie Industrielles. Sujet de Composition d'Informatique 2004. Retrouvez le corrigé Composition d'Informatique 2004 sur Bankexam.fr.

Sujets

Informations

Publié par
Ajouté le 28 février 2007
Nombre de lectures 42
Langue Français
Signaler un abus
´ 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