BCE Maths approfondies HEC/ESCP ECS 2000, épreuve 2Sujet et corrigé

Epreuve de maths approfondies - ECS 2000

Pas encore noté

Explorer les annales

BanqueBCE Année2000 FilièreECS MatièreMathématiques

Annales BCE ECS Mathématiques BCE ECS 2000 ECS Mathématiques Mathématiques 2000

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Lire en ligne LaTeX Word

Rapport du jury : non disponible

Source du document : annales-prepa.fr

Description

Annale de maths approfondies BCE HEC/ESCP pour la filiere ECS, session 2000.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

ECOLE DES HAUTES ETUDES COMMERCIALES
E.S.C.P. - E.A.P.
ECOLE SUPERIEURE DE COMMERCE DE LYON

CONCOURS D'ADMISSION SUR CLASSES PREPARATOIRES

OPTION SCIENTIFIQUE

MATHEMATIQUES II

Mardi 16 Mai 2000, de 8h. à 12h.

La présentation, la lisibilité, l'orthographe, la qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l'appréciation des copies.
Les candidats sont invités à encadrer dans la mesure du possible les résultats de leurs calculs.
Ils ne doivent faire usage d'aucun document ; l'utilisation de toute calculatrice et de tout matériel électronique est interdite.
Seule l'utilisation d'une règle graduée est autorisée.

Le problème consiste en l'analyse d'un algorithme de tri et l'étude de sa complexité.
On note

lnx

le logarithme népérien d'un réel strictement positif

x

log_2 x

son logarithme en base 2 . On rappelle que

log_2 x = (lnx)/(ln2)

Partie I: Étude d'une suite réelle

Dans cette partie la lettre

n

désignera toujours un entier naturel au moins égal à 2 .
On considère la suite

(u_k)_(k \in ℕ^*)

définie par son premier terme

u_1

et vérifiant, pour tout

n

, la relation de récurrence :

u_n = n - 1 + 2/n\sum_(i = 1)^(n - 1)u_i

a) Calculer $u_2$ et $u_3$ en fonction de $u_1$ .
b) Montrer que, pour tout $n$ au moins égal à 3 , on a : $nu_n - (n + 1)u_(n - 1) = 2n - 2$ .
Pour tout entier naturel $k$ non nul, on pose : $v_k = (u_k)/(k + 1)$ .
a) Pour tout $n$ au moins égal à 3 , exprimer $v_n - v_(n - 1)$ en fonction de $n$ .
b) Déterminer deux réels $α$ et $β$ vérifiant, pour tout réel $x$ non nul et distinct de -1 , l'égalité:

(2x - 2)/(x(x + 1)) = α/x + β/(x + 1)

c) Pour tout

n

, établir l'égalité :

v_n = 2\sum_(k = 2)^n 1/k + (u_1)/3 - 2 + 4/(n + 1)

.
3) Pour tout

n

, on pose

h_n = \sum_(k = 2)^n 1/k

z_n = 1/n - ln(n/(n - 1))

.
a) Calculer

u_n

en fonction de

h_n, u_1

n

.
b) Prouver l'égalité :

h_n = \sum_(k = 2)^n z_k + lnn

.
c) Déterminer la nature de la série de terme général

z_n

.
d) En déduire un équivalent de

h_n

quand

n

tend vers l'infini.
e) Déterminer un équivalent de

u_n

quand

n

tend vers l'infini.

Partie II: Étude d'une suite de variables aléatoires

A. On considère un espace probabilisé dont la probabilité est notée

P

, une variable aléatoire

Z

, définie sur cet espace, prenant un nombre fini de valeurs réelles notées

z_1, z_2, \dots, z_p

et un événement

A

de probabilité non nulle.
On note

E(Z/A)

l'espérance de la variable aléatoire

Z

pour la probabilité conditionnelle sachant

A

, i.e.

E(Z/A) = \sum_(i = 1)^p z_i P([Z = z_i]/A)

Soit (

A_1, A_2, \dots, A_q

) un système complet d'événements tous de probabilité non nulle. Prouver l'égalité :

E(Z) = \sum_(j = 1)^q P(A_j)E(Z/A_j)

B. Toutes les variables aléatoires considérées dans cette sous-partie sont définies sur un même espace probabilisé dont la probabilité est notée

P

.
On considère une suite

(I_n)_(n \in ℕ^*)

de variables aléatoires telle que, pour tout

n

non nul,

I_n

suit la loi uniforme sur l'ensemble

{1, 2, \dots, n}

des entiers compris, au sens large, entre 1 et

n

.
D'autre part, on considère une suite

(X_n)_(n \in ℕ^*)

de variables aléatoires ayant les propriétés suivantes:

$X_1$ est la variable constante égale à 0
pour tout entier naturel $n$ au moins égal à 2 , les lois conditionnelles de $X_n$ sachant $[I_n = 1]$ et de $X_n$ sachant $[I_n = n]$ sont toutes deux égales à la loi de $n - 1 + X_(n - 1)$
pour tout entier naturel $n$ au moins égal à 3 et tout entier $i$ tel que $2 ⩽ i ⩽ n - 1$ , la loi conditionnelle de $X_n$ sachant $[I_n = i]$ est égale à la loi de $n - 1 + Z_(n, i) + T_(n, i)$ où $Z_(n, i)$ et $T_(n, i)$ sont deux variables aléatoires indépendantes, $Z_(n, i)$ ayant même loi que $X_(i - 1)$ et $T_(n, i)$ ayant même loi que $X_(n - i)$ .

Par exemple, on a :

P([X_6 = 9]/[I_6 = 1]) = P([X_5 = 4])

et aussi

P([X_6 = 9]/[I_6 = 3]) = P([Z_(6, 3) + T_(6, 3) = 4])

ce qui, compte tenu des hypothèses, s'écrit :

P([X_6 = 9]/[I_6 = 3]) = \sum_j P([X_2 = j])P([X_3 = 4 - j])

, la somme étant étendue aux valeurs convenables de l'entier

j

a) Montrer que $X_2$ est une variable aléatoire presque sûrement constante égale à 1 .
b) Établir les égalités: $P([X_3 = 2]) = 1/3$ et $P([X_3 = 3]) = 2/3$ . Calculer l'espérance de $X_3$ qu'on notera $U_3$ .
Déterminer la loi de $X_4$ et calculer son espérance qu'on notera $U_4$ .
En procédant par récurrence, montrer que, pour tout entier naturel $n$ non nul, $X_n$ prend, presque sûrement, des valeurs entières inférieures ou égales à $(n(n - 1))/2$ .
Soit $n$ un entier naturel au moins égal à 2 . On note $U_n$ l'espérance de $X_n$ .
a) À l'aide des résultats de la sous-partie $A$ , établir l'égalité : $U_n = n - 1 + 2/n\sum_(i = 1)^(n - 1)U_i$ .
b) À l'aide de la partie $I$ , donner l'expression de $U_n$ en fonction de $n$ ainsi qu'un équivalent de $U_n$ quand $n$ tend vers l'infini.
Pour tout entier naturel $n$ non nul, on note $α_n$ la plus petite valeur (entière) prise par la variable $X_n$ avec une probabilité non nulle.
a) Soit $n$ et $k$ deux entiers naturels, l'entier $n$ étant au moins égal à 3 .

Montrer que

P([X_n = k])

est nul si et seulement si les nombres

P(⌊n - 1 + X_(n - 1) = k⌋)

P([n - 1 + Z_(n, i) + T_(n, i) = k])

(l'entier

i

variant de 2 à

n - 1

) sont nuls.
En déduire que

α_n

est au moins égal au minimum des nombres

n - 1 + α_(n - 1), n - 1 + α_1 + α_(n - 2)

n - 1 + α_2 + α_(n - 3), \dots, n - 1 + α_(n - 2) + α_1

.
b) On considère la fonction

g

définie, pour tout

x

strictement positif, par

g(x) = xlog_2 x - 2x + 2

.
i) Montrer que

g

est convexe. Pour tout couple d'entiers (

i, n

) tel que

2 ⩽ i ⩽ n - 1

, en déduire l'inégalité :

g(i) + g(n + 1 - i) ⩾ 2g((n + 1)/2)

.
ii) Pour tout entier naturel

n

non nul, établir l'inégalité :

g(n + 1) - g(n) ⩽ log_2(n + 1)

. En traitant à part les cas

n = 1

n = 2

, montrer que, pour tout entier naturel

n

non nul, on a :

g(n + 1) - g(n) ⩽ n - 1

.
6) En procédant par récurrence, établir, pour tout entier naturel

n

non nul, l'inégalité:

α_n ⩾ (n + 1)log_2(n + 1) - 2n

Partie III : Étude d'un algorithme de tri

A. On considère un entier naturel

n

non nul et un ensemble

E = {e_1, e_2, …, e_n}

où

e_1, e_2, \dots, e_n

sont des réels vérifiant

e_1 < e_2 < \dots < e_n

. On munit l'ensemble des permutations de

E

de la probabilité uniforme notée

P

. On considère les

n

variables aléatoires

T_1, T_2, \dots, T_n

qui, à toute permutation

σ

E

, associent les images des éléments de

E

par

σ

, i.e.

T_1(σ) = σ(e_1), T_2(σ) = σ(e_2), \dots, T_n(σ) = σ(e_n)

, et on note

T

le vecteur aléatoire (

T_1, T_2, \dots, T_n

). Pour toute liste (

α_1, α_2, \dots, α_n

) d'éléments distincts de

E

on a donc

P([T = (α_1, α_2, \dots, α_n)]) = 1/(n!)

Déterminer la loi de la variable aléatoire $T_1$ .
On suppose $n$ au moins égal à 2 . Pour toute permutation $σ$ de $E$ on note $T_1^'(σ)$ le premier élément de la liste $(σ(e_1), σ(e_2), \dots, σ(e_n))$ inférieur à $σ(e_1) = T_1(σ)$ si un tel élément existe et $T_1^'(σ) = 0$ sinon, $T_2^'(σ)$ le deuxième élément inférieur à $σ(e_1)$ si un tel deuxième élément existe et $T_2^'(σ) = 0$ sinon, etc., $T_(n - 1)^'(σ)$ le $(n - 1)$ -ième élément inférieur à $σ(e_1)$ si un tel $(n - 1)$ -ième élément existe et $T_(n - 1)^'(σ) = 0$ sinon.
Par exemple, si
$n = 4, (e_1, e_2, e_3, e_4) = (3, 5, 7, 10)$ et $(σ(e_1), σ(e_2), σ(e_3), σ(e_4)) = (7, 10, 5, 3)$
alors $T_1^'(σ) = 5, T_2^'(σ) = 3$ et $T_3^'(σ) = 0$ .
Soit $k$ un entier vérifiant $1 ⩽ k ⩽ n - 1$ .
a) Combien y a-t-il de listes ( $i_1, i_2, \dots, i_k$ ) d'entiers vérifiant $2 ⩽ i_1 < i_2 < \dots < i_k ⩽ n$ ?
b) Soit ( $α_1, α_2, \dots, α_k$ ) une liste d'éléments distincts de ${e_1, e_2, …, e_k}$ . Établir l'égalité:

P(⋂_(j = 1)^k[T_j^' = α_j] \cap [T_1 = e_(k + 1)]) = 1/(nk!)

c) En déduire l'égalité :

P(⋂_(j = 1)^k[T_j^' = α_j]/[T_1 = e_(k + 1)]) = 1/(k!)

où

P(A/B)

désigne la probabilité conditionnelle de

A

sachant

B

.
Ainsi la loi conditionnelle de (

T_1^', T_2^', \dots, T_k^'

) sachant

[T_1 = e_(k + 1)]

est uniforme.
B. Dans un programme écrit en langage Pascal on fait les déclarations suivantes :

const n = «entier naturel non nul fixé par l'utilisateur» ;
type tableau = array [1..n] of integer;

Soit

T

une variable de type tableau qu'on suppose constituée d'éléments distincts. Si deb et fin sont deux entiers tels que

1 ⩽ deb < fin ⩽ n

on dira qu'un élément

T[k]

de la liste

(T[deb], T[deb + 1], \dots, T[fin])

est à sa place dans le sous-tableau

[T[deb], \dots, T[fin]]

si les éléments

T[deb], T[deb + 1], \dots, T[k - 1]

sont inférieurs à

T[k]

et si les éléments

T[k + 1], T[k + 2], \dots, T[fin]

sont supérieurs à

T[k]

(bien sûr, si

k = deb

k = fin

, une seule de ces conditions subsiste).
Ainsi, si

n = 4

T = [3, 1, 7, 5]

alors

T[3](= 7)

est à sa place dans le sous-tableau

[T[1], T[2], T[3]](= [3, 1, 7])

mais n'est pas à sa place dans le le sous-tableau

[T[2], T[3], T[4]](= [1, 7, 5])

.
On dira que le tableau

T

est trié si chacun de ses éléments est à sa place dans

T

.
On suppose qu'on dispose d'une procédure (écrite en langage Pascal) dont l'en-tête est
Placer (var T : tableau ; deb, fin : integer ; var pl: integer);
qui ne fait rien si fin

⩽ deb

et qui, si

1 ⩽ deb < fin ⩽ n

, effectue, à l'aide de (

fin - deb

) comparaisons, les opérations suivantes:
i) d'une part, elle ne modifie que le sous-tableau

[T[deb], \dots, T[fin]]

de sorte que les éléments de ce soustableau plus petits que

T[deb]

"ont glissé" (sans permutation entre-eux) à gauche de

T[deb]

et les éléments de ce sous-tableau plus grands que

T[deb]

"ont glissé" (sans permutation entre-eux) à droite de

T[deb]

. Ainsi

T

[deb] se retrouve à sa place dans le sous-tableau modifié.
ii) d'autre part, elle met dans la variable

pl

l'indice

i

tel que

T[i]

reçoit, au cours de la procédure, la valeur qui était stockée dans

T[

deb

]

avant l'exécution de la procédure.

Par exemple, si

T = [12, 3, 8, 10, 6, 4, 5]

l'instruction

Placer(T, 3, 6, pl)

une fois exécutée aura changé

T

[12, 3, 6, 4, 8, 10, 5]

et affecté la valeur 5 à la variable

pl

, alors que l'instruction

Placer(T, 3, 4, pl)

aura laissé

T

inchangé et affecté la valeur 3 à la variable

pl

.
Par ailleurs on considère la procédure suivante:

procedure Tri(varT:tableau;deb,fin: integer);
var pl: integer;
begin
    if fin > deb then begin Placer(T, deb, fin,pl);
            if pl > deb then Tri(T, deb,pl-1);
            if pl<fin then Tri(T,pl+1,fin);
        end ;
end ;

a) L'entier $i$ étant compris entre 1 et $n$ , quel est l'effet sur la variable $T$ de l'instruction $Tri(T, i, i)$ ?
b) Dans cette sous-question on suppose qu'initialement $T = [2, 9, 6, 1, 5]$ .

Déterminer la «trace»de l'instruction

Tri(T, 1, 5)

en donnant la liste des procédures successives (avec les valeurs de leurs paramètres) qui sont effectuées et en indiquant à chaque fois les affectations des variables pl et

T

.
c) Expliquer succinctement l'effet et le principe de fonctionnement de la procédure Tri en indiquant, en particulier, pourquoi l'algorithme s'arrête.
2) On se place à nouveau dans le contexte probabiliste de la sous-partie

A

et, si

σ

est une permutation de

E

, on affecte la valeur

[σ(e_1), σ(e_2), \dotsσ(e_n)]

à la variable

T

de type tableau, i.e.

T[1]:=σ(e_1), T[2]:=σ(e_2), \dots

T[n]:=σ(e_n)

. On note

X_n(σ)

le nombre de comparaisons faites lors des différentes exécutions de la procédure Placer (et seulement au cours de celles-ci) quand on effectue la procédure

Tri(T, 1, n)

.
a) À l'aide de la sous-partie

A

, montrer que la suite de variables aléatoires

(X_n)_(n \in ℕ^*)

vérifie les hypothèses de II.B. En déduire un équivalent de l'espérance de

X_n

lorsque l'entier naturel

n

tend vers l'infini.
b) Dans le cas où

E = {1, 2, \dots, n}

, donner (en le commentant de manière succincte) un exemple de tableau nécessitant

(n(n - 1))/2

comparaisons pour être trié.
c) Dans le cas où

E = {1, 2, \dots, 7}

, donner de même un exemple de tableau nécessitant 10 comparaisons pour être trié.
d) Déterminer une suite d'entiers

n

pour lesquels, dans le cas où

E = {1, 2, \dots, n}

, il existe un tableau d'éléments nécessitant

g(n + 1)

comparaisons pour être trié.

Pas de description pour le moment

Commentaires• BCE Maths approfondies HEC/ESCP ECS 2000, épreuve 2

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...

Explorer les annales

Téléchargements

Description

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

ECOLE DES HAUTES ETUDES COMMERCIALES E.S.C.P. - E.A.P. ECOLE SUPERIEURE DE COMMERCE DE LYON

OPTION SCIENTIFIQUE

MATHEMATIQUES II

Partie I: Étude d'une suite réelle

Partie II: Étude d'une suite de variables aléatoires

Partie III : Étude d'un algorithme de tri

Commentaires• BCE Maths approfondies HEC/ESCP ECS 2000, épreuve 2

Commentaires• BCE Maths approfondies HEC/ESCP ECS 2000, épreuve 2

ECOLE DES HAUTES ETUDES COMMERCIALES
E.S.C.P. - E.A.P.
ECOLE SUPERIEURE DE COMMERCE DE LYON