Espci 2004 epreuve d algorithmique classe prepa pc epreuve d algorithmique 2004 classe prepa pc

Publié par

´ECOLE POLYTECHNIQUE´ ´ECOLE SUPERIEURE DE PHYSIQUE ET CHIMIE INDUSTRIELLESCONCOURS 2004` `´FILIEREMP - OPTION PHYSIQUE ET SCIENCES DE L’INGENIEUR FILIEREPCCOMPOSITION D’INFORMATIQUE(Dur´ee : 2 heures)L’utilisation des calculatrices n’est pas autoris´ee pour cette ´epreuve.Le langage de programmation choisi par le candidat doit ˆetre sp´ecifi´eentˆete de la copie.Compression ternaireOn attachera une grande importance `a la concision, `alaclart´e, et `alapr´ecision de la r´edaction.On supposera que le langage de programmation utilis´eposs`ede deux op´erations x div y et x mod ydonnant le quotient et le reste de la division euclidienne de x par y.Le temps d’ex´ecution T(f) d’une fonction f est le nombre d’op´erations ´el´ementaires (addi-tion, soustraction, multiplication, division, affectation, etc.) n´ecessaire au calcul de f.Lorsquece temps d’ex´ecution d´epend d’un param`etre n,ilseranot´e T (f). On dit que la fonction fns’ex´ecute :• en temps lin´eraire en n, s’il existe K>0 tel que pour tout n, T (f)≤ Kn ;n2• en temps quadratique en n, s’il existe K>0 tel que pour tout n, T (f)≤ Kn .nNombres ternairesEn base 3, les entiers 0, 1, 2, 3, 4, 5, 6, 7, 8 sont repr´esent´es par 00, 01, 02, 10, 11, 12, 20,21, 22.Lechiffredepoidsfortdebc est b ;lechiffredepoidsfaibleestc.´Question 1. Ecrire la fonction entier(b,c) retournant l’entier compris entre 0 et 8 qui s’´ecritbc en base 3.1´Question 2. Soit x un entier v´erifiant 0≤ x≤ 8. Ecrire une fonction ...
Publié le : mardi 5 juillet 2011
Lecture(s) : 161
Nombre de pages : 4
Voir plus Voir moins
´ 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
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.