Mathématiques II 2000 Classe Prepa HEC (S) HEC
3 pages
Français

Mathématiques II 2000 Classe Prepa HEC (S) HEC

Cet ouvrage peut être téléchargé gratuitement
3 pages
Français
Cet ouvrage peut être téléchargé gratuitement

Description

Examen du Supérieur HEC. Sujet de Mathématiques II 2000. Retrouvez le corrigé Mathématiques II 2000 sur Bankexam.fr.

Sujets

Informations

Publié par
Publié le 17 mars 2007
Nombre de lectures 473
Langue Français

Extrait

HEC-ESCP-EML 2000.Math 2, option scientifique Leproble`meconsisteenlanalysedunalgorithmedetrietle´tudedesacomplexite´. On note lnxnee´´pregoratimh´eelstriiendunrtisofimetcptnelelxet logxson logarithme en base 2. On rappelle que 2 lnx logx= 2 ln 2 ´ PartieI:Etudedunesuitere´elle Dans cette partie la lettrendise´alegs´in2.`atneinrtaruleuaomgneratoujoursune Onconside`relasuite(uk)kNrpmesrnoreemeitrdiepa´enu1tourutnaiop,ttere´vnrelatila,ruercn:enoed´rce n1 X 2 un=n1 +ui n i=1 1)a)Calculeru2etu3en fonction deu1. b)Montrer que, pour toutnol`ian3s´aeugma:,onanun(n+ 1)un1= 2n2. uk 2)Pour tout entier naturelknon nul, on pose :vk= . k+ 1 a)Pour toutnegs´`aalex3,imprreuaomnivnvn1en fonction den. b)etmrDe´lsr´eedeuxinerαetβruop,tnaire´vleer´uttoxnon nul et distinct de´e:1l,´egalit 2x2α β = + x(x+ 1)x x+ 1 n X 1u14 c)Pour toutnaelt,eg´l´iarbl:´eitvn= 2+2 +. k3n+ 1 k=2 n X 1 1n 3)Pour toutn, on posehn= etzn=ln( ). k nn1 k=2 a)Calculerunen fonction dehn,u1etn. n X b)rPuoevlr´ge:e´tilahn=zk+ lnn. k=2 c)g´enermeedet´erilesarudenataenlrmieretD´are´lzn. d)ivquenalreui´eunnEde´ddtehnquandntend vers l’infini. e)un´equDi´veterminerlanedteunquandntend vers l’infini. ´ PartieII:Etudedunesuitedevariablesal´eatoires
AOspneeuerd`sionncde´silibaborpecanoltpaorabibil´teestnot´eePairaaelbae´lriote,unevZec,seap,dn´esuieetrc prenantunnombrenidevaleursre´ellesnote´esz1, z2, . . . , zpntmeetvun´ene´eAne´tunnoaborilibepdlle. On noteE(Z/Aeroiat´ealleabrivanaecedallse´pre)Zibaborpalruoptncaahllseonneditieconlit´A, i. e. p X P E(Z/A) =ziP([Z=zi]/A) i=1 Soit (A1, A2, . . . , Aqbibaroeponent´liemene´vedsuotstnit´eegal.erPunlllr´uoevst`emecompletd´)nuys q X E(Z) =P(Aj)E(Z/Aj) j=1
Broepbibaeeemacspalt´silnodeartiesontesous-pssrunuˆmdte´neinscoesirtoeal´satecsnadsee´re´diTbaelavirlsseuoet probabilit´eestnot´eeP. Onconsid`ereunesuite(In)nNedleabrivatoeal´sariseetllqeeup,uortoutnnon nul,Insuit la loi uniforme sur l’ensemble [1, nteui(re`eesunsndinoocra,trtpeDauetn.tre1e,engralsnesua,sirpmcorsientsede]]Xn)nNbairaselavedesl´eatoir ayantlesproprie´t´essuivantes X1ela`e´ag0ecbliaarteanstonvaltse pour tout entier naturelnenllseedsllescoidionontiomua´snilage,2a`Xnsachant [In= 1] et deXnsachant [In=n] sonttoutesdeuxe´gales`alaloiden1 +Xn1 pour tout entier natureln3ateag`lneitottuaerns´eumoiitel que 2in1, la loi conditionnelle deXnsachant [In=i´egale`a]estolaledin1 +Zn,i+Tn,iou`Zn,ietTn,isindoire´eatesalailbvxradtuesno,setnadnepe´Zn,iayant mˆemeloiqueXi1, etTn,iantyameˆmioleeuqXni. Par exemple, on a :P([X6= 9]/[I6= 1]) =P([X5= 4]) et aussiP([X6= 9]/[I6= 3]) =P([Z6,3+T6,3= 4]) ce qui, X comptetenudeshypothe`ses,s´ecrit:P([X6= 9]/[I6= 3]) =P([X2=j])P([X3= 4je´tnate´emmosal,])uendte j aux valeurs convenables de l’entierj. 1)a)Montrer queX2etnatsnoa`elage´sˆuesqretcenemurae´lailbripeaeot1.eevarstun
1 2 ´ b)e´:slatis´egirletablEP([X3= 2]) =etP([X3decnare´]3=)=ealcu.CesplerlX3qu’on noteraU3. 3 3 2)mrnirealoldiete´eDX4etcalculersonesp´nareuqecnnoretoaU4. 3)encecurrrr´entpaopruuq,ertrem,noretunaertienuttolEnocprda´ennon nul,Xnsˆuremen,presquednerp,teds n(n1) valeursenti`eresinf´erieuresou´egalesa`. 2 4)Soitnuratrnieinmoaueltnenulaa`´sgeonet.2nOUnesp´lcedeeranXn. n1 X 2 ` a)esr´tauldetssolalAdiasedelirl´egalit´e:sup-raitAe´,tebaUn=n1 +Ui. n i=1 ` b)A l’aide de la partie I, donner l’expression deUnen fonction denaviutneluuqqe´nasiindeUnquandntend vers l’infini. 5)Pour tout entier naturelnnon nul, on noteαntitelavepalpsulre`eri)pr(eutienlberaailrvaesapXnavec une probabilite´nonnulle. a)Soitnetkdeux entiers naturels, l’entiernegs´`aal3.e´attnuaomni Montrer queP([Xn=k]) est nul si et seulement si les nombresP([n1 +Xn1=k]) etP([n1 +Zn,i+Tn,i=k]) (l’entierivairadenta2`n1) sont nuls. Ende´duirequeαnmoins´egestausrembonsedmuminimualan1 +αn1, n1 +α1+αn2, nl+α2+ αn3, . . . , n1 +αn2+α1. b)ere`ofalitcnnocoOnidnsgd´enie,pourtoutxstrictement positif, parg(x) =xlogx2x+ 2. 2 i.Montrer quegest convexe. Pour tout couple d’entiers (i, n) tel que 2ine´tilage´nileri´edu,end1:   n+ 1 g(i) +g(n+ 1i)2g. 2 ii.Pour tout entier naturelnate´rilbnon,lunt´lie:inlga´eg(n+ 1)g(n)log (nsclertpaasnErt1+.)tna`iaat 2 n= 1 etn= 2, montrer que, pour tout entier naturelnnon nul, on a :g(n+ 1)g(n)n1. 6)pnE´cornaderaptntteourtou,pirblate´,ecnerruce´rletarueinrnt´e:galiin´el,lnounn αn(n(+ 1) logn+ 1)2n 2
´ Partie III :Etude d’un algorithme de tri
Alerenunre`etunaertiOnconsidnnon nul et un ensembleE={e1, e2, . . . , en}`oue1, e2, . . . , en´vsliretnaonsestdeer´ e1< e2. .< e< .n. On munit l’ensemble des permutations deErobabilit´edlepauniformene´toePd`sieerO.nocn lesnviaarlae´lbseerstaioT1, T2, . . . , Tnnui,`qepetuotaoitatumrσdeEas,tlencisoemtndsedes´el´eesimagesEparσ, i.e.T1(σ) =σ(e1), T2(σ) =σ(e2), . . . , Tn(σ) =σ(en), et on noteT´laeuearevtcele(irtoT1, T2, . . . , Tn). Pour toute liste (α1, α2, . . . , αn´edeml´tsen)distinctsdeEon a donc :   1 P[T= (α1, α2, . . . , αn)] = n! 1)lbaeraaiotri´laeeete´DlaerinrmavelidloT1. 0 2)On supposentionaleg2.`amoaus´inrepeatumruoPtuotσdeEon noteT(σestliladentme´emeei´rle)elrp 1   0 0 ntele´l´ementexistee(σ) = 0 sinon,T(σme`eixuedel) σ(e1), σ(e2), . . . , σ(enieurf´er)ina`σ(e1) =T1(σ) si utT1 2 0 0 le´mentexisteetT) = 0 sinon, etc ´el´ementinfe´rieur`aσ(e1unteldeuxi`eme´e)is2(σ.,T(σ) le (nemtnlee´me´e-)`i1 n1 0 eme´el´ementexisteetT σ) = 0 sinon. infe´rieur`aσ(e1) si un tel (n1)-i`n1( Par exemple, si n= 4,(e1, e2, e3, e4) = (3,5,7,10) et (σ(e1), σ(e2), σ(e3), σ(e4)) = (7,10,5,3) 0 00 alorsT(σ) = 5, T(σ) = 3 etT(σ) = 0. 1 23 Soitkvre´iratn1neuientkn1. a)Combien y a-t-il de listes (i1, i2, . . . , iknt2riasv´ereitned)i1< i2. .< .< ikn? ´ b)Soit (α1, α2, . . . , αk)untsle´eme´ilendetsdistinctsde{e1, e2, . . . , ek}:gelati.et´Ebaillr´k \   1 0 P=α] [Tj j[T1=ek+1] = nk! j=1 c)reui´elEnedd´´teagil k \   1 0 P[T=α j j]/[T1=ek+1] = k! j=1 ou`P(A/Bilabobprlaneiges´d)eledit´econditionnelAsachantB. 0 00 Ainsi la loi conditionnelle de(T ,. . .T ,)sachant 1 2, Tk[T1=ek+l]est uniforme. 2
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents