Informatique 2004 Classe Prepa MP Ecole de l'Air

pages

Français

Documents

2007

Lire

Cet ouvrage peut être téléchargé gratuitement

pages

Français

Ebook

2007

Lire

Cet ouvrage peut être téléchargé gratuitement

Publié par

bankexam

Publié le

28 février 2007

Nombre de lectures

Langue

Français

Examen du Supérieur Ecole de l'Air. Sujet de Informatique 2004. Retrouvez le corrigé Informatique 2004 sur Bankexam.fr.

Voir

Publié par

bankexam

Publié le

28 février 2007

Nombre de lectures

Langue

Français

Exercice 1

Version

Soit l’alphabetB={0,1}. 1) a) Soit l’ensembleLdes mots surBcontenant un nombre impair d’occurrences de 1 et l’automateAaipn:ﬁre´d 0 0

1L’´etatiest initial. ✗✔ ✗✔ ✢ ✢ q L’e´tatfest ﬁnal. ✲ ✲ i f ✐ ✖✕ ✖✕ 1 Montrer queAreconnaˆıt le langageL. b) Montrer que le langageMsmuotessedru´itstonc{0,1}contenant un nombre pair de 0 et un nombre impair de 1 est reconnaissable. 2) On souhaite maintenant concevoir un circuit logique qui renvoie le nombre modulo 2 de 0 pr´esentsdanslemotpasse´enentr´eeaucircuit. Onpourrautiliserlesporteslogiques´el´ementaireset,ou,nonetxor(ou exclusif), que l’onrepre´sentesimplementpar: ✎☞ ET OU XOR ✍✌ Porte Non Porte Et Porte Ou Porte Xor a)Commenc¸onsparunmotdelongueur1:u=a, aveca∈ {0,1}. Construire un circuitP0ee´rtneeuleunes`aaet une sortiesqui vaut 0 siucontient un nombre pair de 0 et 1 sinon. n b)Supposonsconc¸uuncircuitPntntqnepdreueinmouneer´ugnoledte2rueu`edeposs une sortiesqui vaut 0 siucontient un nombre pair de 0 et 1 sinon. Construire,`al’aidedePn, un circuitPn+1tnuomurpome`eblroepemˆmeltuose´riuq n+1 delongueur2enentr´ee. c)De´terminer,lorsquentend vers +∞teslogiqubersedepornedtnumoe´uqvilaun, ´el´ementairesutilise´esdansPn. 3) SoitNl’ensemble des motsusur{0,1}tels que :

|u|= 2|u| 0 1

ou`|u|et|u|er’dcoucrrneecdse0etde1danssprentneigesd´bmoneltnemevitceu. 0 1 Ce langage est-il reconnaissable ?

Exercice 2

Ondisposed’unepilederondellesdediam`etresvarie´s,quel’onsouhaiterangerparordre de´croissantdetaille,lapluslargedevantˆetreenbasdelapile.Malheureusement,onnepeut manipuler la pile que«par morceaux»eslu:alretaoe´paptreipa`etsisalerdnerorutnaioonec´eis delapilesurmontantunecertainerondelleeta`retournerd’unbloctoutlepaquet. Parexemple,siunepilecontientdesrondellesdediame`tres7,10,20,2et5etquel’onretourne lebloccommen¸cant`alarondelledediame`tre20,onobtientlapiledediame`tressuccessifs7, 10, 5, 2 et 20.

Diam`etre5Diame`tre20 Diame`tre2Diam`etre2 Diam`etre20Diam`etre5 Diam`etre10Diame`tre10 Diame`tre7Diam`etre7 Pileaude´partPileapre`sretournement Nousmod´eliseronslapilederondellesparuntableau(ouvecteur)dde0ea`d’entiers,indic´ n−,1`ounsellcal,nesae´muentlbromereddeonseoriedsertelim`nmiltreeam`eelidantnnoetc la rondelleiro´eumenasac.L.delapilenoadbusac0roerps En Caml comme en Pascal, nous supposerons la constantene.nieﬁd´ En Caml,dest de typeint vect, et en Pascal de typePileipﬁn:arde´

Pile = ARRAY[0..n-1] OF INTEGER ´ 1) Ecrire : – en Caml une fonctionretourne : int vect -> int -> unittelle queretourne d i modiﬁe le vecteurdpour«retourner»raitdrlepali`epaaaltrapurieeledsuieerp´ rondelle d’indicei(incluse) ; –enPascaluneproce´dureretourne(VAR d : Pile ; i : INTEGER)telle queretourne(d,i) modiﬁe le tableaudpour«retourner»partirdelaron-irueeredalipela`e´puseitrapal delle d’indicei(incluse). 2) Quel est, en nombre d’aﬀectations dansd?ntecoˆ,lerecedtuemenruot 3) Comment faire pour mettre en bas de pile la rondelle la plus large ? ´ 4) Ecrire – en Caml une fonctionplace : int vect -> int -> unittelle queplace d imodiﬁe le vecteurdemruertt’la`idnicoepila rondelle la plus large de la partie de la pile surmontant la rondelle d’indicei(incluse) ; –enPascaluneproc´edure; i : INTEGER)place(VAR d : Pile telle queplace(d,i) modiﬁe le tableaudla`erttemruop’indiceila rondelle la plus large de la partie de la pile surmontant la rondelle d’indicei(incluse) ; 5)Ende´duire,selonlelangagechoisi,unefonctionouuneproce´durequitried. 6)Quelestlecouˆtaupiredecetteme´thode,ennombrederetournementsd’unmorceaude pile ?

Exercice 1

Version

AliceetBobjouenta`unjeudanslequelchacund’entreeuxaunechancesurdeuxderemporter ` chaquepartie.Onconvientquelegagnantestlepremierquiaremport´etroisparties.Achaque instant,nousrepre´senteronslasituationparuncouple(a, bu,)`oa(resp.b) est le nombre de partiesremporte´esparAlice(resp.Bob). Supposonsparexemplequ’Aliceaitd´eja`remport´edeuxpartiesetBobuneseule:lescoreactuel est donc (2,etre(3,ilpeutˆr`Ap).1puocniahcorpelse,1acAsilec,)uauqleejtleseuagageen´t ﬁni, ou (2,enesr´eppacicetetnocuejernO.eunisiblsposes:b)r2erllrtae’,oceredss

(2,1) ❅  ❅  ❅ (3,1) (2,2) ❅  ❅  ❅ (3,2) (2,3)

Danscetarbre,laracine,´etiquet´ee(2,e`uvroet,s1)a laprofondeur0.Lafeuille´etiquete´e(3,1) est la seule feuillea`laprofondeur1,etilexiste`alaprofondeur2 deuxfeuilles,´etiquete´es(3,2) et (2,3). On remarque que, sif(p)se´dseiullrembfedeneignole a`laprofondeurp:eﬁirerev´tarb,ce

2 X −k f(k)2 = 1. k=0

1)a)Dessinerl’arbrequel’onobtientdelamˆemefac¸ona`partirduscore(1,0) (i.e. lors-qu’Aliceagagne´unepartieetBobaucune). 4 P −k b)Ve´riﬁerquecetarbresatisfaitencorelarelationf(k1.)2 = k=0 2) Montrer que, pour tout arbre binaire, de hauteur quelconqueh, on a : h P −k f(k1=`o2)uf(kelensign)d´epalaoforuednrbromefedileus`lek. k=0

Exercice 2

Onsouhaiteg´ererdefac¸onaussiautomatiquequepossiblelacre´ationd’uncolloscopepourune classedelaﬁlie`reMP-MP*. Onsupposeles´etudiantsre´partisenunnombrepair2nep(suqtiedrguorcr´e´edte`aavoise groupesvidesoupartiellementvides,parexempleavecdeux´etudiants,encasdebesoin),avec n>upeestrep´er´epasrnoun´mre,oocpmserirentt20eC.1orgeuqahn−1. Chaquegroupedoitavoirchaquesemaineuneinterrogationdemathe´matiques,etuneinterro-gationdephysique-chimieoudelangueenalternanceunesemainesurdeux.Ladiﬃcult´eest que la classe est bilingue :pciliesstt2,eitutocsna’gne´dsgrosontupesn−pde germanistes. Onsupposeraquelesgroupesd’anglicistessontceuxnum´erot´esde0`ap−1, les groupes de germanistese´tantnum´erote´sdep`2an−1. Onadoncrecrut´e2nemh´atems,ueiqatorretnidsruetagninterrogateurs de physique-chimie,q   l m p2n−p interrogateurs d’anglais etrla’d`und,olemaq= etr= (la notationdxegnsi´ede 2 2 lapartieentie`resupe´rieuredextneisrpue´irue`ra,e.i.pllepeustetix). Les interrogateurs sont repe´r´esparunnum´erocomprisentre0etrespectivement2n−1 oun−smleh´at1urpostameeuqi ou la physique, 0 etq−1 pour l’anglais,qetq+r−1 pour l’allemand.

Voir

Univers
Ebooks
Livres audio
Presse
Podcasts
BD
Documents

Informatique 2004 Classe Prepa MP Ecole de l'Air

YouScribe

Le catalogue

Le service

Les conditions