EA 2004 informatique classe prepa mp

Publié par

Version AExercice 1Soit l’alphabet B ={0,1}.1) a) Soit l’ensemble L des mots sur B contenant un nombre impair d’occurrences de 1 etl’automate A d´efini par :0 01 L’´etat i est initial. q L’´etat f est final.- -fii 1Montrer que A reconnaˆıt le langage L.b) Montrer que le langage M constitu´e des mots sur {0,1} contenant un nombre pairde 0 et un nombre impair de 1 est reconnaissable.2) On souhaite maintenant concevoir un circuit logique qui renvoie le nombre modulo 2 de 0pr´esents dans le mot pass´e en entr´ee au circuit.On pourra utiliser les portes logiques ´el´ementaires et, ou, non et xor (ou exclusif), quel’on repr´esente simplement par :ET OU XORPorte Non Porte Et Porte Ou Porte Xora) Commen¸cons par un mot de longueur 1 : u =a, avec a∈{0,1}.Construire un circuit P `a une seule entr´ee a et une sortie s qui vaut 0 si u contient0un nombre pair de 0 et 1 sinon.nb) Supposonscon¸cuuncircuitP quiprendenentr´eeunmotudelongueur2 etposs`edenune sortie s qui vaut 0 si u contient un nombre pair de 0 et 1 sinon.Construire, a` l’aide deP , un circuitP qui r´esout le mˆeme probl`eme pour un motn n+1n+1de longueur 2 en entr´ee.c) D´eterminer, lorsque n tend vers +∞, un ´equivalent du nombre de portes logiques´el´ementaires utilis´ees dans P .n3) Soit N l’ensemble des mots u sur {0,1} tels que :|u| = 2|u|0 1ou` |u| et |u| d´esignent respectivement le nombre d’occurrences de 0 et de 1 dans u.0 1Ce langage est-il reconnaissable ...
Publié le : jeudi 21 juillet 2011
Lecture(s) : 70
Nombre de pages : 10
Voir plus Voir moins
Exercice 1
Version
A
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 Le´tatfest final. ✲ ✲ 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 lonrepre´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,`alaidedePn, 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|erdcoucrrneecdse0etde1danssprentneigesd´bmoneltnemevitceu. 0 1 Ce langage est-il reconnaissable ?
Exercice 2
Ondisposedunepilederondellesdediam`etresvarie´s,quelonsouhaiterangerparordre de´croissantdetaille,lapluslargedevantˆetreenbasdelapile.Malheureusement,onnepeut manipuler la pile que«par morceaux»eslu:alretaoe´paptreipa`etsisalerdnerorutnaioonec´eis delapilesurmontantunecertainerondelleeta`retournerdunbloctoutlepaquet. Parexemple,siunepilecontientdesrondellesdediame`tres7,10,20,2et5etquelonretourne 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`dentiers,indic´ n,1`ounsellcal,nesae´muentlbromereddeonseoriedsertelim`nmiltreeam`eelidantnnoetc la rondelleiro´eumenasac.L.delapilenoadbusac0roerps En Caml comme en Pascal, nous supposerons la constantene.nied´ En Caml,dest de typeint vect, et en Pascal de typePileipn:arde´
Pile = ARRAY[0..n-1] OF INTEGER ´ 1) Ecrire : – en Caml une fonctionretourne : int vect -> int -> unittelle queretourne d i modifie le vecteurdpour«retourner»raitdrlepali`epaaaltrapurieeledsuieerp´ rondelle d’indicei(incluse) ; enPascaluneproce´dureretourne(VAR d : Pile ; i : INTEGER)telle queretourne(d,i) modifie le tableaudpour«retourner»partirdelaron-irueeredalipela`e´puseitrapal delle d’indicei(incluse). 2) Quel est, en nombre d’affectations 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 imodifie le vecteurdemruerttla`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) modifie le tableaudla`erttemruopindiceila 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,ennombrederetournementsdunmorceaude pile ?
Exercice 1
Version
B
AliceetBobjouenta`unjeudanslequelchacundentreeuxaunechancesurdeuxderemporter ` chaquepartie.Onconvientquelegagnantestlepremierquiaremport´etroisparties.Achaque instant,nousrepre´senteronslasituationparuncouple(a, bu,)`oa(resp.b) est le nombre de partiesremporte´esparAlice(resp.Bob). SupposonsparexemplequAliceaitd´eja`remport´edeuxpartiesetBobuneseule:lescoreactuel est donc (2,etre(3,ilpeutˆr`Ap).1puocniahcorpelse,1acAsilec,)uauqleejtleseuagageen´t fini, 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:eirerev´tarb,ce
2 X k f(k)2 = 1. k=0
1)a)Dessinerlarbrequelonobtientdelamˆemefac¸ona`partirduscore(1,0) (i.e. lors-quAliceagagne´unepartieetBobaucune). 4 P k b)Ve´rierquecetarbresatisfaitencorelarelationf(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´ationduncolloscopepourune classedelalie`reMP-MP*. Onsupposeles´etudiantsre´partisenunnombrepair2nep(suqtiedrguorcr´e´edte`aavoise groupesvidesoupartiellementvides,parexempleavecdeux´etudiants,encasdebesoin),avec n>upeestrep´er´epasrnoun´mre,oocpmserirentt20eC.1orgeuqahn1. Chaquegroupedoitavoirchaquesemaineuneinterrogationdemathe´matiques,etuneinterro-gationdephysique-chimieoudelangueenalternanceunesemainesurdeux.Ladicult´eest que la classe est bilingue :pciliesstt2,eitutocsnagne´dsgrosontupesnpde germanistes. Onsupposeraquelesgroupesdanglicistessontceuxnum´erot´esde0`ap1, les groupes de germanistese´tantnum´erote´sdep`2an1. Onadoncrecrut´e2nemh´atems,ueiqatorretnidsruetagninterrogateurs de physique-chimie,q   l m p2np interrogateurs d’anglais etrlad`und,olemaq= etr= (la notationdxegnsi´ede 2 2 lapartieentie`resupe´rieuredextneisrpue´irue`ra,e.i.pllepeustetix). Les interrogateurs sont repe´r´esparunnum´erocomprisentre0etrespectivement2n1 ounsmleh´at1urpostameeuqi ou la physique, 0 etq1 pour l’anglais,qetq+r1 pour l’allemand.
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.