Connectez-vous pour consulter le corrigé.
L’objet du problème consiste en l’étude de la complexité de deux algorithmes. Dans la partie I, on s’intéresse à un premier algorithme, permettant la recherche du plus grand élément d’un tableau de nombres non triés, et dans la partie II, à un second algorithme permettant la recherche des deux plus grands éléments d’un tableau de nombres non triés.
On se propose d’étudier la suite \((u_n)_{n\in\mathbb{N}^\ast}\) définie par: \[\forall n \in \mathbb{N}^\ast,\ u_{n}=1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{n}-\ln (n) = \sum_{k=1}^n \frac{1}{k} - \ln(n)\]
À cet effet, on introduit la suite \(\left(v_{n}\right)_{n\in\mathbb{N}^\ast}\) définie par : \[\forall n \in \mathbb{N}^\ast,\ v_n = u_n - \frac{1}{n}\]
Établir l’encadrement suivant: \[\forall n \in \mathbb{N}^\ast,\ \frac{1}{n+1} \leqslant \ln (n+1)-\ln (n) \leqslant \frac{1}{n}\]
En déduire le sens de variation des suites \((u_n)\) et \(\left(v_{n}\right)\), et prouver qu’elles sont adjacentes.
On note \(\gamma\) la limite commune des suites \(\left(u_{n}\right)\) et \(\left(v_{n}\right)\) et, pour évaluer numériquement \(\gamma\), on se propose d’utiliser la moyenne arithmétique \(m_{n}\) de \(u_n\) et \(v_{n}\) : \[\forall n \in \mathbb{N}^\ast,\ m_{n}=\frac{u_{n}+v_{n}}{2}\]
Prouver l’inégalité suivante: \[\forall n \in \mathbb{N}^\ast,\ \left|m_{n}-\gamma\right| \leqslant \frac{1}{2 n}\]
Quelle valeur de \(n\) choisir pour que \(m_n\) soit une valeur approchée de \(\gamma\) à \(10^{-2}\) près ?
Écrire un programme Python permettant
de calculer \(m_n\) pour un entier
naturel non nul \(n\) donné.
On améliore dans cette question la majoration obtenue pour \(|m_n-\gamma|\).
Pour tout \(k\in\mathbb{N}^\ast\), comparer \(m _{k+1} - m_k\) à l’intégrale: \[\int_{k}^{k+1} \frac{(t-k)(k+1-t)}{t^{3}} \,\mathrm{d}t\]
En déduire l’inégalité suivante: \[\forall k \in\mathbb{N}^\ast,\ 0 \leqslant m_{k+1}-m_{k} \leqslant \int_{k}^{k+1} \frac{\mathrm{d}t}{4 t^{3}}\]
En déduire par sommation un encadrement de \(m_{n+p}-m_{n}\) pour tout couple \((n,p)\) d’entiers naturels non nuls, puis de \(\gamma-m_n\).
Écrire un programme Python permettant
de renvoyer une valeur approchée de \(\gamma\) à \(10^{-5}\) près.
On considère une urne remplie de \(n\) boules (\(n \geqslant 1\)) numérotées respectivement \(1,2, \ldots, n\). On extrait ces \(n\) boules, une à une et sans remise, et l’on désigne par \(Z_{1}, Z_{2}, \ldots, Z_{n}\) les variables aléatoires indiquant, dans cet ordre, les numéros des boules ainsi obtenues.
Pour tout entier \(p\) tel que \(1 \leqslant p \leqslant n\), on note d’autre part \(X_p\) la variable aléatoire indiquant le plus grand des \(p\) numéros obtenus au cours des \(p\) premiers tirages, autrement dit: \(X_{p}=\sup \left(Z_{1}, Z_{2}, \ldots, Z_{p}\right)\).
On se propose de déterminer \(\mathbb{P}(Z_{p}>X_{p-1})\) pour \(1<p \leqslant n\).
On pose \(\mathbb{N}_{n}=\{1,2, \ldots, n\}\). Préciser :
le nombre de parties \(A\) à \(p\) éléments choisis dans l’ensemble \(\mathbb{N}\).
le nombre de suites \((a_1, a_2,\dots, a_p)\) composées de \(p\) éléments deux à deux distincts d’une partie donnée \(A\) à \(p\) éléments de l’ensemble \(\mathbb{N}_{n}\).
le nombre de suites \((a_1, a_2,\dots, a_p)\) composées de \(p\) éléments deux à deux distincts de l’ensemble \(\mathbb{N}^{n}\).
le nombre de suites \((a_1, a_2,\dots, a_p)\) composées de \(p\) éléments deux à deux distincts d’une partie donnée \(A\) à \(p\) éléments de l’ensemble \(\mathbb{N}_{n}\) et telles que le plus grand des \(p\) éléments soit situé en \(p^{\grave{e}me}\) position.
le nombre de suites \((a_1, a_2,\dots, a_p)\) composées de \(p\) éléments deux à deux distincts de l’ensemble \(\mathbb{N}_{n}\) et telles que le plus grand des \(p\) éléments soit situé en \(p^{\grave{e}me}\) position.
la probabilité \(\mathbb{P}( Z_{p}>X_{p-1} )\) pour \(1<p \leqslant n\).
Pour \(1<p \leqslant n\), on note \(B_p\) la variable aléatoire prenant pour valeurs 1 si l’événement \([ Z_{p}>X_{p-1} ]\) est réalisé, et 0 sinon. Montrer que l’espérance de \(B_p\) est égale à \(\frac{1}{p}\), et donner l’expression et l’interprétation de \(\mathbb{E}({B}_{2}+{B}_{3}+\ldots+{B}_n)\).
On considère le programme Python
suivant, dans lequel Z est un tableau de \(n\) cases et où l’on a affecté un entier
supérieur à 1 à la variable \(n\), et
les entiers \(1,2 ,\dots, n\) dans un
ordre quelconque à Z[0],
Z[1],…Z[n-1].
X=Z[0]
for p in range(1,n):
if Z[p]>X:
X=Z[p]
Indiquer les valeurs successivement prises par
X au cours de l’algorithme:
d’une part lorsque \(Z[1]=1, Z[2]=2, \ldots, Z[n]=n\),
d’autre part lorsque \(Z[1]=n, Z[2]=n-1, \ldots, Z[n]=1\).
On revient au cas général. Indiquer la valeur contenue dans la
variable X à l’issue de l’algorithme.
Déterminer le nombre de comparaisons (\(>\)) effectuées entre les valeurs de
deux variables ainsi que le nombre maximal et le nombre minimal
d’affectations (\(=\))
effectuées.
À l’aide des résultats précédents, exprimer l’espérance \(E_n\) du nombre d’affectations effectuées au cours de l’algorithme en fonction de \(u_n\), puis expliciter à l’aide du nombre \(\gamma\) des réels \(a\) et \(b\) tels que l’on ait: \[E_{n}=a \ln (n)+b+ \circ(1)\]
Les notations \(u_n\) et \(\gamma\) ont été introduites dans la partie préliminaire.
Le contexte probabiliste est celui introduit au début de la partie précédente.
Pour \(2 \leqslant p \leqslant n\), on note \(Y_{p}\) la variable aléatoire telle que \(X_{p}\) et \(Y_{p}\) indiquent respectivement les deux plus grands des \(p\) numéros obtenus au cours des \(p\) premiers tirages, avec \(Y_{p}<X_{p}\).
En reprenant et en adaptant le raisonnement de la question I.5, préciser, pour tout entier \(p\) tel que \(2<p \leqslant n\), la probabilité \(\mathbb{P}(Y_{p-1}<Z_{p}<X_{p-1})\).
Pour \(2<p \leqslant n\), on note \(C_{p}\) la variable aléatoire prenant pour valeurs 0 si l’événement \([ Z_{p}<Y_{p-1}]\) est réalisé, 1 si l’événement \([ Y_{p-1}<Z_{p}<X_{p-1}]\) est réalisé, et 2 si l’événement \([X_{p-1}<Z_{p}]\) est réalisé.
Montrer que l’espérance de \(C_{p}\) est égale à \(\frac{3}{p}\).
On modifie l’algorithme de la question I.7 de la façon suivante:
if Z[1]>Z[0]:
X=Z[1]
Y=Z[0]
else:
X=Z[0]
Y=Z[1]
for p in range(2,n):
if Z[p]>Y:
if Z[p]<X:
Y=Z[p]
else:
Y=X
X=Z[p]
Indiquer les valeurs successivement prises par \(X\) et \(Y\) au cours de l’algorithme:
d’une part lorsque \(Z[1]=1, Z[2]=2, \ldots, Z[n]=n\).
d’autre part lorsque \(Z[1]=n, Z[2]=n-1, \ldots, Z[n]=1\).
On revient au cas général. Indiquer les valeurs contenues dans
les variables X et Y
à l’issue de l’algorithme. Déterminer le nombre maximal et le nombre
minimal de comparaisons (\(>\))
effectuées entre les valeurs de deux variables ainsi que d’affectations
(\(=\)) effectuées.
À l’aide des résultats précédents, calculer les espérances \(E^{\prime}_n\) et \(E^{\prime \prime}_n\) des nombres de comparaisons et d’affectations effectuées au cours de l’algorithme, puis expliciter à l’aide du nombre \(\gamma\) défini dans les préliminaires des réels \(a^{\prime}\), \(b^{\prime}, c^{\prime}, a^{\prime \prime}, b^{\prime \prime}\) tels que l’on ait: \[E_n' = a'n + b' \ln(n) + c' + \circ(1) \quad \text{et} \quad E_n'' = a''\ln(n) + b'' + \circ(1)\]
Le corrigé pas à pas, les aides et les explications sont disponibles dans la plateforme.