HEC 2000 mathematiques ii classe prepa hec (s)

Description

HEC-ESCP-EML 2000. Math 2, option scientifiqueLe probl`eme consiste en l’analyse d’un algorithme de tri et l’´etude de sa complexit´e.On note lnx le logarithme n´ep´erien d’un r´eel strictement positif x et log x son logarithme en base 2. On rappelle que2lnxlog x =2 ln2´Partie I : Etude d’une suite r´eelleDans cette partie la lettre n d´esignera toujours un entier naturel au moins ´egal `a 2.On consid`ere la suite (u ) ∗ d´efinie par son premier terme u et v´erifiant, pour tout n, la relation de r´ecurrence :k k∈N 1n−1X2un = n−1+ uini=11)a)Calculer u et u en fonction de u .2 3 1b)Montrer que, pour tout n au moins ´egal a` 3, on a : nu −(n+1)u = 2n−2.n n−1uk2) Pour tout entier naturel k non nul, on pose : v = .kk +1a) Pour tout n au moins ´egal a` 3, exprimer v −v en fonction de n.n n−1b)D´eterminer deux r´eels α et β v´erifiant, pour tout r´eel x non nul et distinct de −1, l’´egalit´e :2x−2 α β= +x(x+1) x x+1nX 1 u 41c) Pour tout n, ´etablir l’´egalit´e : v = 2 + −2+ .nk 3 n+1k=2nX 1 1 n3) Pour tout n, on pose h = et z = −ln( ).n nk n n−1k=2a) Calculer u en fonction de h , u et n.n n 1nXb)Prouver l’´egalit´e : h = z +lnn.n kk=2c) D´eterminer la nature de la s´erie de terme g´en´eral z .nd)En d´eduire un ´equivalent de h quand n tend vers l’infini.ne) D´eterminer un ´equivalent de u quand n tend vers l’infini.n´Partie II : Etude d’une suite de variables al´eatoiresA On consid`ere un espace probabilis´e dont la probabilit´e est not´ee P, une ...

Informations

• Publié par: aiolos
• Nombre de lectures: 220
• Langue: Français

Extrait

HEC-ESCP-EML 2000.Math 2, option scientifique Leproble`meconsisteenl’analysed’unalgorithmedetrietl’e´tudedesacomplexite´. On note lnxnee´´pregoratimh´eelstriiend’unrtisofimetcptnelelxet logxson logarithme en base 2. On rappelle que 2 lnx logx= 2 ln 2 ´ PartieI:Etuded’unesuitere´elle Dans cette partie la lettrendise´alegs´in2.`atneinrtaruleuaomgneratoujoursune Onconside`relasuite(u k ) k∈N rpmesrnoreemeitrdiepa´efinu 1 tourutnafiiop,ttere´vnrelatila,ruercn:enoed´rce ∗ n−1 X 2 un=n−1 +u i n i=1 1)a)Calculeru 2 etu 3 en fonction deu 1 . b)Montrer que, pour toutnol`ian3s´aeugma:,onanu n −(n+ 1)u n−1 = 2n−2. u k 2)Pour tout entier naturelknon nul, on pose :v k = . k+ 1 a)Pour toutnegs´`aalex3,imprreuaomniv n −v n−1 en fonction den. b)etmrDe´lsr´eedeuxinerαetβruop,tnafiire´vleer´uttoxnon nul et distinct de−´e:1l,’´egalit 2x−2α β = + x(x+ 1)x x+ 1 n X 1u 1 4 c)Pour toutnaelt,eg´l’´iarbl:´eitv n = 2+−2 +. k3n+ 1 k=2 n X 1 1n 3)Pour toutn, on poseh n = etz n =−ln( ). k nn−1 k=2 a)Calculeru n en fonction deh n ,u 1 etn. n X b)rPuoevlr´’ge:e´tilah n =z k + lnn. k=2 c)g´enermeedet´erilesarudenataenlrmieretD´are´lz n . d)ivquenalreui´eunnEde´ddteh n quandntend vers l’infini. e)un´equDi´veterminerlanedteu n quandntend vers l’infini. ´ PartieII:Etuded’unesuitedevariablesal´eatoires

AOspneeuerd`sionncde´silibaborpecanoltpaorabibil´teestnot´eePairaaelbae´lriote,unevZec,seap,dfin´esuieetrc prenantunnombrefinidevaleursre´ellesnote´esz 1 , z 2 , . . . , z p ntmeetvun´ene´eAne´tunnoaborilibepdlle. On noteE(Z/Aeroiat´ealleabrivanaecedal’lse´pre)Zibaborpalruoptncaahllseonneditieconlit´A, i. e. p X P E(Z/A) =z i P([Z=z i ]/A) i=1 Soit (A 1 , A2, . . . , A q bibaroeponent´liemene´vedsuotstnit´eegal.erPunlllr´’uoevst`emecompletd’´)nuys q X E(Z) =P(A j )E(Z/A j ) j=1

Broepbibaeeemacspalt´silnodeartiesontesous-pssrunuˆmdte´nfieinscoesirtoeal´satecsnadsee´re´diTbaelavirlsseuoet probabilit´eestnot´eeP. Onconsid`ereunesuite(I n ) n∈N edleabrivatoeal´sariseetllqeeup,uortoutnnon nul,I n suit la loi uniforme sur l’ensemble ∗ [1, nteui(re`eesunsndinoocra,trtpeD’auetn.tre1e,engralsnesua,sirpmcorsientsede]]X n ) n∈N bairaselavedesl´eatoir ∗ ayantlesproprie´t´essuivantes •X 1 ela`e´ag0ecbliaarteanstonvaltse •pour tout entier naturelnenllseedsllescoidionontiomua´snilage,2a`X n sachant [In= 1] et deX n sachant [I n =n] sonttoutesdeuxe´gales`alaloiden−1 +X n−1 •pour tout entier natureln3ateag`lneitottuaerns´eumoiitel que 2≤i≤n−1, la loi conditionnelle deX n sachant [In=i´egale`a]estolaledin−1 +Z n,i +T n,i ou`Z n,i etT n,i sindoire´eatesalailbvxradtuesno,setnadnepe´Z n,i ayant mˆemeloiqueX i−1 , etT n,i antyameˆmioleeuqX n−i . Par exemple, on a :P([X 6 = 9]/[I 6 = 1]) =P([X 5 = 4]) et aussiP([X 6 = 9]/[I 6 = 3]) =P([Z 6,3 +T 6,3 = 4]) ce qui, X comptetenudeshypothe`ses,s’´ecrit:P([X 6 = 9]/[I 6 = 3]) =P([X 2 =j])P([X 3 = 4−je´tnate´emmosal,])uendte j aux valeurs convenables de l’entierj. 1)a)Montrer queX 2 etnatsnoa`elage´sˆuesqretcenemurae´lailbripeaeot1.eevarstun