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.
´ 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´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,iTn(f). Ondit que la fonctionf s’ex´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’´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.
Quelquesde´finitionssontne´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 0≤k < .
´ 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´refii≤m.
´ Question 4.On supposei < june fonction. EcrirelongueurMotifMax(t, i, j, m) qui retourne, entempsquadratiqueparrapporta`N, la plus grande longueure´amrrnahcˆanıdedne’uten i+ktnnegda´leem`aarruanechaˆı´neejpour 0≤k < moutre, on exige. Eni+k < jet≤m.
Question 5.ec´edentepourobtefilrfanotcoipn´ridoMrineofalitcnnomotifMax(t, i, j, m) qui rend, en temps quadratique, dansLla plus grande longueureunnndt’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).
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.
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