Informatique 2004 Classe Prepa MP Ecole de l'Air
10
pages
Français
Documents
2007
Cet ouvrage peut être téléchargé gratuitement
10
pages
Français
Documents
2007
Cet ouvrage peut être téléchargé gratuitement
Examen du Supérieur Ecole de l'Air. Sujet de Informatique 2004. Retrouvez le corrigé Informatique 2004 sur Bankexam.fr.
Voir
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:fire´d 0 0
1L’´etatiest initial. ✗✔ ✗✔ ✢ ✢ q L’e´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 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.niefid´ En Caml,dest de typeint vect, et en Pascal de typePileipfin: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 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) modifie 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
B
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 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:efiirerev´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´rifierquecetarbresatisfaitencorelarelationf(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 classedelafilie`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.Ladifficult´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.
