Connectez-vous pour consulter le corrigé.
Dans les questions faisant intervenir des instructions en langage Python, on prendra soin d’importer les bibliothèques nécessaires lors de leur première utilisation.
Pour traiter les questions d’informatique, les candidats sont invités à se référer à l’annexe fournie en fin de sujet.
Ils ne sont pas limités à l’utilisation des seules fonctions mentionnées dans cette annexe.
Soit \(n\) un entier naturel non nul.
Une urne contient \(n\) boules indiscernables au toucher et numérotées de 1 à \(n\). On tire une boule au hasard dans l’urne. Si cette boule tirée porte le numéro \(k\), on place alors dans une seconde urne toutes les boules suivantes: une boule numérotée 1, deux boules numérotées 2, et plus généralement pour tout \(j\in \left[\kern-0.15em\left[ {1,k} \right]\kern-0.15em\right]\), \(j\) boules numérotées \(j\), jusqu’à \(k\) boules numérotées \(k\). Les boules de cette deuxième urne sont aussi indiscernables au toucher. On effectue alors un tirage au hasard d’une boule dans cette seconde urne.
Et on note \(X\) la variable aléatoire égale au numéro de la première boule tirée et on note \(Y\) la variable aléatoire égale au numéro de la deuxième boule tirée.
Reconnaître la loi de \(X\) et donner son espérance et sa variance.
Déterminer \(Y(\Omega)\).
Soit \(k\in\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\).
On suppose que l’événement \([X=k]\) est réalisé.
Déterminer, en fonction de \(k\), le nombre total de boules présentes dans la seconde urne.
Pour tout entier \(j\) de \(\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\), exprimer \(\mathbb{P}_{[X=k]}(Y=j)\) en fonction de \(k\) et \(j\).
On distinguera les cas \(j\leqslant k\) et \(j\geqslant k+1\).
Déterminer deux réels \(a\) et \(b\) tels que, pour tout entier naturel \(k\) non nul : \[\frac{1}{k \left( k+1 \right)}=\frac ak+\frac{b}{k+1}\]
En déduire que, pour tout élément \(j\) de \(Y(\Omega)\) : \[\mathbb{P}(Y=j)=\frac{2 \left( n+1-j \right)}{n \left(n+1 \right)}\]
Justifier que \(Y\) admet une espérance et montrer que \(\mathbb{E}(Y)=\dfrac{n+2}{3}\).
Les variables \(X\) et \(Y\) sont-elles indépendantes?
Montrer que \(\mathbb{E}(XY)=\dfrac{(n+1)(4n+5)}{18}\).
En déduire que \(\text{Cov}(X,Y)=\dfrac{n^2-1}{18}.\)
Écrire une fonction en langage Python,
nommée seconde_urne, prenant en entrée un entier naturel
k non nul, et renvoyant une liste contenant 1 élément
valant 1, 2 éléments valant 2, \(\ldots\), \(j\) éléments valant \(j\), \(\ldots\), jusqu’à \(k\) éléments valant \(k\).
Par exemple, l’appel de seconde_urne(4) renverra
[1,2,2,3,3,3,4,4,4,4].
Recopier et
compléter la fonction en langage Python
suivante pour qu’elle prenne en entrée un entier naturel \(n\) non nul, et qu’elle renvoie une
réalisation du couple de variables aléatoires \((X,Y)\).
On considère la fonction en langage
Python suivante, prenant en entrée un entier
naturel n non nul.
Quelles valeurs les éléments de la liste renvoyée permettent-ils d’estimer?
Dans toute cette question, on suppose \(n=20\). On simule 50 réalisations du couple
de variables aléatoires \((X,Y)\) à
l’aide de la fonction simul_XY définie à la question ???.
On représente alors les valeurs obtenues sous forme d’un nuage de
points, où les valeurs des réalisations de \(X\) sont représentées en abscisse et les
valeurs des réalisations de \(Y\) en
ordonnées. On trace également, sur la même figure, la droite de
régression linéaire associée à ce nuage de points.
Déterminer par un calcul une valeur approchée des coordonnées du point moyen du nuage de points. Quel théorème de probabilités permet de justifier cette approximation?
Parmi les figures représentées ci-dessous, en justifiant soigneusement votre réponse, indiquer celle qui correspond au nuage de points et à la droite de régression linéaire étudiés.
On considère la fonction \(f\) définie sur \(]0,+\infty[\) par : \[\forall x\in \left]0,+\infty \right[,\ f(x)=\frac{\mathrm{e}^{\frac{x}{2}}}{\sqrt x}\] On rappelle que \(2<\mathrm{e}<3\).
Montrer que \(f\) est dérivable sur \(\left] 0,{+\infty}\right[\) et que, pour tout réel \(x\) de \(\left] 0,{+\infty}\right[\) : \[f'(x)=\frac{x-1}{2x} \, f(x)\]
Dresser le tableau de variations de \(f\) et déterminer les limites suivantes : \(\lim\limits_{x\to 0}f(x)\) et \(\lim\limits_{x\to +\infty}f(x)\).
Tracer l’allure de la courbe représentative de \(f\).
Montrer que, pour tout entier \(n\) supérieur ou égal à 2, l’équation \(f(x)=n\), d’inconnue \(x\) dans \(\left] 0,{+\infty}\right[\), possède exactement deux solutions \(u_n\) et \(v_n\), avec : \[0<u_n<1<v_n\]
Montrer que la suite \((v_n)_{n\geqslant 2}\) est croissante.
Montrer par l’absurde que la suite \((v_n)_{n\geqslant 2}\) tend vers \(+\infty\) quand \(n\) tend vers \(+\infty\).
Montrer que la suite \((u_n)_{n\geqslant 2}\) est décroissante.
En déduire que la suite \((u_n)_{n\geqslant 2}\) converge. Dans les questions qui suivent, on note \(\ell\) la limite de la suite \((u_n)_{n\geqslant 2}\).
Montrer par l’absurde que \(\ell=0\).
En déduire que \(\lim\limits_{n\to+\infty}n^2u_n=1\) puis un équivalent simple de \(u_n\) lorsque \(n\) tend vers \(+\infty\).
Soient \(n\) un entier supérieur ou égal à 2 et \(\varepsilon\) un réel strictement positif.
On cherche à déterminer une valeur approchée de \(u_n\) avec une marge d’erreur inférieure ou égale à \(\varepsilon\).
On rappelle pour cela le principe de l’algorithme de dichotomie.
On initialise deux variables \(a\) et \(b\) en leur affectant respectivement les valeurs 0 et 1.
Tant que \(b-a>\varepsilon\), on répète les opérations suivantes.
On considère le milieu \(c\) du segment \([a,b]\). Par monotonie de \(f\) sur \(]0,1]\), en distinguant les cas \(f(c)\leqslant n\) et \(f(c)>n\), on peut déterminer si \(u_n\) appartient à l’intervalle \([a,c]\) ou à l’intervalle \([c,b]\).
Selon le cas, on met alors à jour la valeur de \(a\) ou de \(b\) pour se restreindre au sous-intervalle approprié.
On renvoie finalement la valeur \(\dfrac{a+b}{2}\), qui constitue une valeur approchée de \(u_n\) à \(\varepsilon\) près.
Recopier et compléter la fonction en langage
Python suivante, prenant en entrée un entier
n supérieur ou égal à 2 et un réel strictement positif
eps, et renvoyant une valeur approchée de \(u_n\) à eps près en appliquant
l’algorithme décrit ci-dessus.
Écrire une fonction en langage Python,
nommée sp, prenant en entrée un entier N
supérieur ou égal à 2 et un réel strictement positif eps et
renvoyant une valeur approchée de la somme \(\displaystyle \sum\limits_{n=2}^Nu_n\) à
eps près.
On pourra faire appel à la fonction approx_u définie
à la question précédente.
On considère la matrice \(A=\begin{pmatrix}1&0&0&1\\1&1&1&0\\1&1&1&0\\1&0&0&1\end{pmatrix}\). On note \(f\) l’endomorphisme de \(\mathbb{R}^4\) représenté par la matrice \(A\) dans la base canonique \(\mathcal{C}=(e_1,e_2,e_3,e_4)\) de \(\mathbb{R}^4\).
On considère les vecteurs suivants de \(\mathbb{R}^4\): \[u_1=(-1,1,0,1),\quad u_2=(0,-1,1,0), \quad u_3=(0,1,1,0)\quad u_4=(1,0,0,1)\] On note \(\mathcal{B}=(u_1,u_2,u_3,u_4)\).
Montrer que \(\mathcal{B}\) est une base de \(\mathbb{R}^4\).
Déterminer la matrice représentative de \(f\) dans la base \(\mathcal{B}\).
En déduire une matrice \(P\) de \(\mathcal{M}_4(\mathbb{R})\) inversible et une matrice \(T\) de \(\mathcal{M}_4(\mathbb{R})\) triangulaire telles que \(A=PTP^{-1}\).
Calculer \(A^2\), \(A^3\), puis vérifier que \(A^3=4A^2-4A\).
Montrer par récurrence que, pour tout entier naturel \(n\) non nul, il existe deux réels \(a_n\) et \(b_n\) tels que : \[A^n=a_nA^2+b_nA\] vérifiant, pour tout entier naturel \(n\) non nul, \(a_{n+1}=4a_n+b_n\) et \(b_{n+1}=-4a_n\).
Montrer que, pour tout entier naturel \(n\) non nul : \[a_{n+2}=4a_{n+1}-4a_n\]
Déterminer, pour tout entier naturel \(n\) non nul, une expression de \(a_n\) en fonction de \(n\).
En déduire, pour tout entier naturel \(n\) non nul, une expression de \(b_n\) en fonction de \(n\).
Montrer que, pour tout entier naturel \(n\) non nul : \[A^n=\begin{pmatrix} 2^{n-1} & 0 & 0 & 2^{n-1}\\ (n+1)2^{n-2} & 2^{n-1} & 2^{n-1} & (n-1)2^{n-2} \\ (n+1)2^{n-2} & 2^{n-1} & 2^{n-1} & (n-1)2^{n-2} \\ 2^{n-1} & 0 & 0 & 2^{n-1} \end{pmatrix}\]
Soient \(p\) un entier naturel non nul et \(G\) un graphe non pondéré orienté à \(p\) sommets. On note \(s_0\), \(s_1,\ldots, s_{p-1}\) les sommets de \(G\).
Rappeler la définition de la matrice d’adjacence du graphe \(G\).
Soient \(n\) un entier naturel
non nul, \(i\) un entier de \(\left[\kern-0.15em\left[ {1,p}
\right]\kern-0.15em\right]\) et \(j\) un entier de \(\left[\kern-0.15em\left[ {1,p}
\right]\kern-0.15em\right]\).
Rappeler sans justification l’interprétation du coefficient situé à la
ligne \(i\) et à la colonne \(j\) dans la matrice \(M^n\), où \(M\) est la matrice d’adjacence du graphe
\(G\).
Dans cette question uniquement, on suppose que \(p=4\) et que la matrice d’adjacence du graphe \(G\) est la matrice \(A=\begin{pmatrix}1&0&0&1\\1&1&1&0\\1&1&1&0\\1&0&0&1\end{pmatrix}\) étudiée dans la partie 1.
Représenter les sommets et les arêtes du graphe \(G\) sous forme d’un diagramme.
Le graphe \(G\) est-il connexe? Justifier votre réponse.
Soit \(n\) un entier naturel non nul.
Déterminer le nombre de chemins de longueur \(n\) menant du sommet \(s_3\) au sommet \(s_0\).
Dans cette question et les suivantes, on revient au cas général décrit au début de la partie 2.
Soit \(s\) un sommet de \(G\). On dit que le sommet \(t\) est un voisin de \(s\) quand \(s\neq t\) et \((s,t)\) est une arête du graphe.
Comme le graphe est orienté, si \(t\) est un voisin de \(s\), alors \(s\) n’est pas forcément un voisin de \(t\).
On appelle liste d’adjacence du graphe \(G\), une liste de \(p\) sous-listes telle que, pour tout entier \(k\) de \(\left[\kern-0.15em\left[ {0,p-1} \right]\kern-0.15em\right]\), la sous-liste située à la position \(k\) contient tous les numéros des sommets voisins de \(s_k\).
Par exemple, la liste d’adjacence du graphe étudié à la question ??? est :
L=[[0,3],[0,1,2],[0,1,2],[0,3]]
Écrire une fonction en langage Python,
nommée matrice_vers_ligne, prenant en entrée la matrice
d’adjacence A d’un graphe \(G\) (définie sous forme de listes de
listes) et renvoyant la liste d’adjacence de \(G\).
On cherche à écrire une fonction en langage
Python permettant d’obtenir la longueur du
plus court chemin menant d’un sommet de départ \(s_i\) à chaque sommet du graphe \(G\).
On souhaite pour cela appliquer un algorithme faisant intervenir les variables suivantes :
Une liste distances à \(p\) éléments, où l’élément situé à la
position \(k\) sera égal, à la fin de
l’algorithme, à la longueur du plus court chemin menant du sommet de
départ \(s_i\) au sommet \(s_k\).
Une liste a_explorer contenant tous les sommets
restant à traiter.
Une liste marques contenant tous les sommets déjà
traités.
Nous donnons ci-dessous la description de l’algorithme :
Initialisation des trois listes décrites ci-dessus :
Initialement, chaque élément de la liste distances
est égal à \(p\), à l’exception du
sommet \(s_i\), auquel on affecte la
distance 0.
La liste marques ne contient initialement que le
numéro du sommet de départ \(s_i\).
La liste a_explorer ne contient initialement que le
numéro du sommet de départ \(s_i\).
Tant que la liste a_explorer n’est pas vide, on
répète les opérations suivantes :
Nommer s le premier sommet de la liste
a_explorer, et le retirer de cette liste.
Pour chaque voisin v du sommet s : si
v n’est pas dans la liste marques, on l’ajoute
à la fin de la liste a_explorer, et on lui affecte une
distance égale à distances[s]+1.
On considère le graphe orienté \(G\) étudié à la question ???.
Donner la valeur de la liste distances à l’issue de
l’exécution de l’algorithme décrit ci-dessus, lorsqu’on l’applique au
graphe \(G\) en choisissant \(s_1\) comme sommet de départ.
Recopier et compléter la fonction suivante, prenant en entrée la
liste d’adjcacence L du graphe \(G\) et le numéro i0 du sommet
de départ \(s_i\), et renvoyant la
liste distances après exécution de l’algorithme décrit
ci-dessus.
Modifier la fonction précédente pour qu’elle renvoie la liste de tous les sommets \(s\) pour lesquels il existe un chemin menant du sommet de départ \(s_i\) au sommet \(s\).
On suppose que L désigne une liste à \(n\) éléments.
L’opérateur de concaténation +, appliqué entre deux
listes, renvoie la liste obtenue en plaçant les éléments de la seconde
liste à la suite de ceux de la première liste.
Par exemple, [1,2,5]+[4,3] renvoie la liste
[1,2,5,4,3].
L’opérateur *, appliqué entre une liste
L et un entier n, renvoie la liste obtenue en
concaténant n fois la liste L avec
elle-même.
Par exemple, [1,4,2]*3 renvoie la liste
[1,4,2,1,4,2,1,4,2].
La fonction len prend en argument d’entrée une liste
et renvoie le nombre d’éléments dans cette liste.
La commande L.append(x) permet d’inclure l’élément
x à la fin de la liste L.
Pour tout entier i entre 0 et \(n_1\), L[i] désigne l’élément
d’indice i de la liste L (les indices
commencent à 0).
Pour tout entier i entre 0 et \(n_1\), la commande del L[i]
retire de la liste L l’élément situé à la position
i.
Par exemple, à l’issue des instructions la liste L vaut
[5,8,1].
Exemple d’importation : import numpy as np.
Les opérations +, -, *,
/, **, lorsqu’elles sont possibles, peuvent
être réalisées entre deux tableaux Numpy de dimensions compatibles et
agissent coefficient par coefficient.
Les fonctions np.sqrt (racine carrée),
np.abs (valeur absolue), np.log (logarithme
népérien) et np.exp (fonction exponentielle) s’appliquent à
une quantité numérique ou à un tableau Numpy de nombres. Dans ce dernier
cas, les fonctions sont appliquées à chaque élément du tableau donné en
argument d’entrée.
Exemple d’importation :
import numpy.random as rd.
La fonction rd.random, appelée sans argument
d’entrée, renvoie une réalisation aléatoire de la loi uniforme sur
l’intervalle \([0,1[\). Il est
également possible de spécifier les dimensions d’un tableau Numpy en
argument d’entrée pour obtenir un tableau dont les coefficients sont des
réalisations indépendantes de la loi uniforme sur \([0,1[\).
La fonction rd.randint prend en entrée deux entiers
\(n\) et \(p\) (avec \(p>n\)) et renvoie une réalisation
aléatoire de la loi uniforme discrète sur \(\left[\kern-0.15em\left[ {n,p-1}
\right]\kern-0.15em\right]\)
Le corrigé pas à pas, les aides et les explications sont disponibles dans la plateforme.
L'exercice 1, sans grande difficulté et en grande partie faisable en première année, reprend les notions de base de probabilités discrètes.
Dans l'exercice 2, on étudie une suite définie de manière implicite et un algorithme d'approximation de la valeur des termes de cette suite.
Dans l'exercice 3, on étudie les adjacentes de sommets d'un graphe orienté.
L'énoncé de l'exercice 3 peut parfois prêter à confusion.