Epreuve optionnelle 2004 Classe Prepa MP EPITA

Description

Examen du Supérieur EPITA. Sujet de Epreuve optionnelle 2004. Retrouvez le corrigé Epreuve optionnelle 2004 sur Bankexam.fr.

Sujets

• 2004
• Epitaph

Informations

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

Extrait

´ ´ EPREUVE OPTIONNELLE de MATHEMATIQUES

Dansceprobl`eme,onnoteD(a, bsembl’ensdivledesrocsiue`sdammnuientxeeuretunarssl)a,bou` (a, b)6=(0,peulgsar)0e,ltentdecetnd´el´emesneelbmD(a, b) est donc le PGCD deaetbae`lmerpbo.eL pourbutl’e´tudedelacomplexite´ducalculduPGCDdesentiersnaturelsaetbpar l’algorithme d’Euclide d´ecritci-dessous.One´tudiea`titrepr´eliminairelasuitedeFibonacci,quiestd´efinieparF 0 = 0,F 1 = 1, et F n+2 =F n+1 +F n pourn∈N.

1˚)anD(ciacnobiFedetiusaledlecalculn´etudieseitnoo,csteetuqF n ). ´ a) Ecrireun algorithme de calcul deF n lorsque le nombre entiernno´nsedt.e b)Pre´ciserF n pourn612. 2˚)csnaDseuqetteuiasdeteboFiccna(ition,on´etudielepsorrp´itee´dsleF n ). a) Prouverque (F n ) est une suite de nombres entiers naturels, strictement croissante pourn>2. b)De´terminerlessuitesg´eome´triques(u n v)relatiolnari´entfiau n+2 =u n+1 +u n . c)De´terminerl’expressiondutermege´ne´ralF n de la suite de Fibonacci en fonction den. d)End´eduirel’encadrementsuivantdeF n dentelaviuqe´nusiup,F n lorsquentend vers +∞:  !! ! ! √ n √ n 1 5+ 11 5+ 1 √ − 16F n 6 √ + 1. 5 25 2

e)De´terminerledomaineded´efinitionetlasommedelafonctiong´ene´ratrice: +∞ P n F(x) =F n x. n=0 3˚)i´etropruespuelqlbesnmelee’e´dsttceueeqnsDaute´qeidoitsno,nD(a, b). a)Quelssontlese´le´mentsdeD(a,0) et le PGCD deaet de 0 poura>1 ? b) Montrer,sia=bq+r, queD(a, b) =D(b, r) et PGCD(a, b) = PGCD(b, r). c) Enremarquant queF k+2 =F k+1 +F k nd,eGeCleiPreduD´deF n+1 et deF n pourn∈N. Onconsid`eredeuxnombresentiersnaturelsaetbtels quea > b >enu’uqellepparnO0.edelit´´ega la formea=bq+rest la division euclidienne deaparbsiqetronsrelsv´erifiantdtueextneisranut 06r < b, et que l’algorithme d’Euclide est la suite des divisions euclidiennes suivantes, poursuivies jusqu’a`l’obtentiond’unpremierrestenul,etdanslesquellesa 0 =aeta 1 =b: a 0 =q 1 a 1 +a 2 avec 0< a 2 < a 1 a 1 =q 2 a 2 +a 3 avec 0< a 3 < a 2 ...................................... a n−1 =q n a n +a n+1 avec 0< a n+1 < a n a n =q n+1 a n+1 +a n+2 aveca 2 = 0 Onditalors,pluspre´cis´ement,quel’algorithmed’Euclidepouraetbs’effectue enndivisions.+ 1 L’ensembledecesnotationsestd´esormaisconserve´jusqu’`alafinduproble`me.

4˚)nacsteetDmed’rithide.Euclitnoilaclaoged’lemexuniepp’aedplnoitseuqdute´no, ´ a) Ecrirel’algorithme d’Euclide pourF 3 etF 2 , pourF 4 etF 3 , pourF 5 etF 4 . b)Prouverquel’´egalite´F k+2 =F k+1 +F k est la division euclidienne deF k+2 parF k+1 pourk>2. Ende´duirequel’algorithmed’EuclidepourF n+2 etF n+1 s’effectue enndivisions euclidiennes.

1

5˚)itoredhmuc’Edelielpm´tixledegla’n´etudieenfinlacocsteetuqseitnoo,anDameLedemr`eoh´(T.)e´ a) Prouverque le PGCD deaetbest´noteulnnrrsenreiuaedgelaa n+1 . b)Prouverparre´currencelesin´egalite´sq k >1 pour 16k6n+ 1eta k >F n+2−k pour 06k6n+ 2. c)End´eduire,sil’algorithmed’Euclides’effectueenn+ 1divisions, quea>F n+2 ,b>F n+1 , et :    ! √ n+1 1 5+ 1   √ − 16b. 5 2

p−1p d)Ende´duire,sil’´ecritured´ecimaledebcomptepchiffres, autrement dit si 106b <10 ,que le nombrendsnoisivrogla’le’Eedhmitesdeliucpar5tmajor´ededi+1p+ 2. ´ 6˚)ra´efotithriitmeacfilucle´rusrucernulaogcEiresn´euxnDdedePGCantldsnoitresenemorbaetbpar cetteme´thode.

2