Epita 2004 epreuve optionnelle classe prepa mp epreuve optionnelle 2004 classe prepa mp
2 pages
Français

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Epita 2004 epreuve optionnelle classe prepa mp epreuve optionnelle 2004 classe prepa mp

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
2 pages
Français
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

6´ ´EPREUVE OPTIONNELLE de MATHEMATIQUESDans ce probl`eme, on note D(a,b) l’ensemble des diviseurs communs `a deux entiers naturels a, b ou`(a,b)=(0,0), et le plus grand ´el´ement de cet ensemble D(a,b) est donc le PGCD de a et b. Le probl`eme apour but l’´etude de la complexit´e du calcul du PGCD des entiers naturels a et b par ...

Sujets

Informations

Publié par
Nombre de lectures 173
Langue Français

Exrait

´ ´ EPREUVE OPTIONNELLE de MATHEMATIQUES
Dansceprobl`eme,onnoteD(a, bsemblensdivledesrocsiue`sdammnuientxeeuretunarssl)a,bou` (a, b)6=(0,peulgsar)0e,ltentdecetnd´el´emesneelbmD(a, b) est donc le PGCD deaetbae`lmerpbo.eL pourbutle´tudedelacomplexite´ducalculduPGCDdesentiersnaturelsaetbpar l’algorithme d’Euclide d´ecritci-dessous.One´tudiea`titrepr´eliminairelasuitedeFibonacci,quiestd´enieparF0= 0,F1= 1, et Fn+2=Fn+1+FnpournN.
1˚)anD(ciacnobiFedetiusaledlecalculn´etudieseitnoo,csteetuqFn). ´ a) Ecrireun algorithme de calcul deFnlorsque le nombre entiernno´nsedt.e b)Pre´ciserFnpourn612. 2˚)csnaDseuqetteuiasdeteboFiccna(ition,on´etudielepsorrp´itee´dsleFn). a) Prouverque (Fn) est une suite de nombres entiers naturels, strictement croissante pourn>2. b)De´terminerlessuitesg´eome´triques(unv)relatiolnari´entaun+2=un+1+un. c)De´terminerlexpressiondutermege´ne´ralFnde la suite de Fibonacci en fonction den. d)End´eduirelencadrementsuivantdeFndentelaviuqe´nusiup,Fnlorsquentend vers +:  !! ! ! nn 1 5+ 11 5+ 1 √ −16Fn6+ 1. 5 25 2
e)De´terminerledomaineded´enitionetlasommedelafonctiong´ene´ratrice: +P n F(x) =Fnx. n=0 3˚)i´etropruespuelqlbesnmeleee´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 queFk+2=Fk+1+Fknd,eGeCleiPreduD´deFn+1et deFnpournN. Onconsid`eredeuxnombresentiersnaturelsaetbtels quea > b >enuuqellepparnO0.edelit´´ega la formea=bq+rest la division euclidienne deaparbsiqetronsrelsv´eriantdtueextneisranut 06r < b, et que l’algorithme d’Euclide est la suite des divisions euclidiennes suivantes, poursuivies jusqua`lobtentiondunpremierrestenul,etdanslesquellesa0=aeta1=b: a0=q1a1+a2avec 0< a2< a1 a1=q2a2+a3avec 0< a3< a2 ...................................... an1=qnan+an+1avec 0< an+1< an an=qn+1an+1+an+2aveca2= 0 Onditalors,pluspre´cis´ement,quelalgorithmedEuclidepouraetbs’effectue enndivisions.+ 1 Lensembledecesnotationsestd´esormaisconserve´jusqu`alanduproble`me.
4˚)nacsteetDmedrithide.Euclitnoilaclaogedlemexunieppaedplnoitseuqdute´no, ´ a) Ecrirel’algorithme d’Euclide pourF3etF2, pourF4etF3, pourF5etF4. b)Prouverquel´egalite´Fk+2=Fk+1+Fkest la division euclidienne deFk+2parFk+1pourk>2. Ende´duirequelalgorithmedEuclidepourFn+2etFn+1s’effectue enndivisions euclidiennes.
1
  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents