Informatique 2004 Classe Prepa MP Ecole de l'Air

Description

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

Sujets

• Informatique
• 2004
• École de l'air

Informations

• Publié par: bankexam
• Publié le: 28 février 2007
• Nombre de lectures: 59
• Langue: Français

Extrait

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

1 L’´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 circuitP 0 ee´rtneeuleunes`aaet une sortiesqui vaut 0 siucontient un nombre pair de 0 et 1 sinon. n b)Supposonsconc¸uuncircuitP n tntqnepdreueinmouneer´ugnoledte2rueu`edeposs une sortiesqui vaut 0 siucontient un nombre pair de 0 et 1 sinon. Construire,`al’aidedeP n , un circuitP n+1 tnuomurpome`eblroepemˆmeltuose´riuq n+1 delongueur2enentr´ee. c)De´terminer,lorsquentend vers +∞teslogiqubersedepornedtnumoe´uqvilaun, ´el´ementairesutilise´esdansP n . 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.