Connectez-vous pour consulter le corrigé.
Dans cet exercice, on considère un nombre entier naturel \(n\) et le nombre entier \(N=2^{n}\).
Dans \(N\) cases numérotées \(1,2, \ldots, N\) sont rangées \(N\) fiches (à raison d’une fiche par case) qui contiennent des informations dont un nombre noté \(F[1]\) pour la fiche rangée dans la case 1, \(F[2]\) pour la fiche rangée dans la case \(2, \ldots, F[N]\) pour la fiche rangée dans la case \(N\).
Ces fiches peuvent représenter les clients d’une entreprise et les nombres \(F[1], F[2], \ldots, F[N]\) les montants des commandes passées par ces clients, ou bien les candidats à un concours et les nombres \(F[1], F[2], \ldots, F[N]\) les totaux des points obtenus par ces candidats, etc.
L’objectif est ici de « trier ces \(N\) fiches », autrement dit de les ranger dans les cases de façon à ce que les nombres \(F[1], F[2], \ldots, F[N]\) soient dans l’ordre croissant.
Si par exemple les fiches considérées sont celles des \(N\) candidats à un concours, on cherche donc à les ranger dans l’ordre croissant des totaux obtenus (de façon à ce que la première fiche soit donc celle d’un candidat avec le plus faible total, la dernière celle d’un candidat avec le plus fort total).
On étudie maintenant un algorithme très performant de tri (« tri dichotomique ») de ces \(N\) fiches.
Tri des fiches de deux tas de fiches déjà triés.
On considère deux tas triés de fiches (ce qui signifie qu’à l’intérieur de chacun des deux tas, les fiches sont rangées dans l’ordre croissant des nombres \(F[i]\)). L’objectif est ici de réunir les fiches de ces deux tas en un seul tas trié (à l’intérieur duquel les fiches seront donc rangées dans l’ordre croissant des nombres \(F[i]\)).
Soient deux tas triés contenant respectivement \(p\) fiches et 1 fiche.
On compare successivement l’unique fiche du second tas aux fiches du premier tas afin d’obtenir un seul tas trié de \(p+1\) fiches. Déterminer alors le nombre maximal des comparaisons de fiches nécessaires à l’obtention d’un seul tas trié de \(p+1\) fiches.
Soient deux tas triés contenant respectivement \(p\) fiches et \(q\) fiches.
Raisonnant par récurrence sur \(q\), on suppose qu’un majorant du nombre des comparaisons de fiches nécessaires pour réunir en un seul tas trié de \(p+q\) fiches ces deux tas triés est \(p+q-1\). Soient deux tas triés (dans l’ordre croissant) contenant respectivement \(p\) fiches et \(q+1\) fiches. On compare successivement la première fiche du second tas aux fiches du premier tas. Il existe donc un nombre entier \(k\) (\(1 \leqslant k \leqslant p+1\)) tel que cette fiche se classe en \(k^{\text {ème }}\) position de ce premier tas trié. On place cette fiche en \(k^{\text {ème }}\) position du premier tas qui contient alors \(p+1\) fiches, le second tas ne contenant plus que \(q\) fiches. Déterminer en fonction de \(k\) :
le nombre de comparaisons de fiches nécessaires à la recherche de ce nombre entier \(k\).
un majorant du nombre des comparaisons de fiches nécessaires pour réunir en un seul tas trié les \(p+1-k\) dernières fiches triées restant dans ce premier tas et les \(q\) fiches triées restant dans le second tas.
un majorant du nombre des comparaisons de fiches nécessaires pour réunir en un seul tas trié de \(p+q+1\) fiches les deux tas triés initialement donnés. Conclure.
En déduire enfin un majorant du nombre des comparaisons de fiches nécessaires pour réunir en un seul tas trié de \(2 N\) fiches deux tas triés de \(N\) fiches. Ce majorant peut-il être atteint?
L’algorithme du tri dichotomique.
On considère 4 fiches, que l’on trie de la façon suivante:
on constitue deux tas, formés des 2 premières fiches et des 2 dernières fiches.
on trie chacun de ces tas, ce qui nécessite une comparaison de fiches dans chacun d’eux.
on réunit ces deux tas triés en un seul tas trié, à l’aide de la méthode de la question 1.
Combien de comparaisons de fiches doit-on faire au plus pour trier ainsi ces 4 fiches?
On considère 8 fiches que l’on trie de la façon suivante:
on constitue deux tas, formés des 4 premières fiches et des 4 dernières fiches.
on trie chacun de ces tas à l’aide de l’algorithme expliqué précédemment.
on réunit ces deux tas triés en un seul tas trié, à l’aide de la méthode de la question 1.
Combien de comparaisons de fiches doit-on faire au plus pour trier ainsi ces 8 fiches?
En poursuivant de même, combien de comparaisons de fiches doit-on faire au plus pour trier 16 fiches, 32 fiches, 64 fiches?
On revient aux conditions données au début de l’énoncé et, pour trier les \(N=2^{n}\) fiches, on procède comme suit:
on constitue deux tas, formés des \(2^{n-1}\) premières fiches et des \(2^{n-1}\) dernières fiches.
on trie chacun de ces tas à l’aide de l’algorithme expliqué précédemment.
on réunit ces deux tas triés en un seul tas trié, à l’aide de la méthode de la question 1.
On convient alors de noter \(u_{n}\) le nombre maximum de comparaisons de fiches nécessaires au tri de ces \(2^{n}\) fiches à l’aide de cet algorithme et l’on pose \(\displaystyle v_{n}=\frac{u_n}{2^n}\). Déterminer:
les valeurs de \(u_{1}, u_{2}\) et \(u_{3}\) (et on pose bien entendu \(u_{0}=0\)).
l’expression de \(u_{n}\) en fonction de \(u_{n-1}\) et \(n\), puis l’expression de \(v_{n}-v_{n-1}\) en fonction de \(n\).
la valeur de \(v_{n}\) en fonction de \(n\), puis la valeur de \(u_{n}\) en fonction de \(n\).
le nombre maximum de comparaisons de fiches ainsi nécessaires au tri de \(N=2^{n}\) fiches exprimé en fonction de \(n\), puis de \(N\), et un équivalent de celui-ci quand \(N\) tend vers \(+\infty\).
Indiquer le résultat des actions effectuées par le passage dans la boucle intérieure, puis extérieure de l’algorithme suivant, et préciser le nombre de comparaisons de fiches réalisées:
for i in range(N-1,0,-1):
for j in range(1,i+1):
if F[j-1]>F[j]:
F[j-1],F[j]=F[j],F[j-1]]
Comparer cet algorithme « naïf » au précédent. Qu’obtient-on, par exemple, pour \(N=1024\) ?
Dans cet exercice, l’espace vectoriel \(\mathbb{R}^{2}\) est rapporté à sa base canonique \(\mathcal{B}\) et on identifie:
tout vecteur de \(\mathbb{R}^{2}\) à la matrice colonne \(V\) de ses composantes \(x\) et \(y\) dans \(\mathcal{B}\).
tout endomorphisme de \(\mathbb{R}^{2}\) à sa matrice \(M\) dans \(\mathbf{B}\).
Pour tout vecteur \(V\) ou pour toute matrice \(M\), on désigne par \(\phi(V)\) ou \(\phi(M)\) la somme des carrés des deux composantes de \(V\) ou des quatre coefficients de \(M\).
On note enfin \(T\) l’ensemble des matrices réelles \(M\) d’ordre 2 telles que :
\(M\) est symétrique ;
\(M\) est nulle ou est de rang égal à 1 ;
\(M\) a des valeurs propres positives ou nulles.
Exemples de matrices appartenant ou non à \(T\).
Étudier l’appartenance à \(T\) des trois matrices \(A, B, C\) définies par: \[A=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \quad ; \quad B=\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} \quad ; \quad C=\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\]
Étude des matrices appartenant à \(T\).
Pour tout vecteur \(V\) de composantes \(x, y\) appartenant à \(\mathbb{R}^{2}\), on pose \(M=V\, {}^t V\) où \({ }\, {}^t V\) désigne la transposée de \(V\).
Comparer \(\phi(M)\) et \([\phi(V)]^{2}\) et montrer que \(M\) est nulle si et seulement si \(V\) est nul.
Montrer que \(M V=\phi(V) V\) et que \(M^{2}=\phi(V) M\).
Déterminer en fonction de \(V\) les valeurs propres et les vecteurs propres de \(M\) pour \(V \neq 0\).
Établir que \(M\) appartient à \(T\).
On considère réciproquement une matrice \(M\) non nulle de \(T\).
Montrer qu’il existe un vecteur non nul \(X\) appartenant à \(\mathbb{R}^{2}\) tel que \(\operatorname{Im} M=\operatorname{Vect}(X)\), puis un vecteur non nul \(Y\) appartenant à \(\mathbb{R}^{2}\) tel que \(M=X\, {}^t Y\).
Montrer, en utilisant la symétrie de la matrice \(M\), qu’il existe un nombre réel non nul \(\lambda\) tel que \(Y=\lambda X\).
Montrer enfin que \(\lambda\) est strictement positif et en déduire l’existence d’un vecteur non nul \(V\) tel que \(M=V\, {}^t V\).
On considère l’application \(f\) associant à tout vecteur \(V\) de \(\mathbb{R}^{2}\) la matrice carrée \(f(V)=V\, {}^t V\).
\(f\) est-elle surjective de \(\mathbb{R}^{2}\) dans \(T\) ?
\(f\) est-elle injective de \(\mathbb{R}^{2}\) dans \(T\) ?
Approximation d’une matrice symétrique d’ordre 2 par une matrice de T. On considère dans cette question deux nombres réels \(p, q\) tels que \(0<p<q<1\) et \(p+q=1\) et la matrice symétrique \(A\) définie par: \[A=\begin{pmatrix} p & q \\ q & p \end{pmatrix}\]
L’objectif de cette question est de trouver les matrices \(M\) appartenant à T qui minimisent l’expression \(\phi(A-M)\).
La matrice \(A\) appartient-elle à \(T\) ?
On désigne par \(x, y\) les composantes d’un vecteur \(V\). Expliciter la matrice \(A-V\, {}^t V\), puis exprimer en fonction de \(x, y\) :
\[F(x, y)=\phi(A-V\, {}^t V)\]
Calculer les dérivées partielles de \(F\) par rapport aux deux variables \(x\) et \(y\), puis en déduire deux conditions nécessaires pour que \(F\) présente un extremum en \((x, y)\).
Résoudre le système d’équations suivant: \[\begin{cases} \partial_1 F(x,y) + \partial_2 F(x,y) = 0 \\ \partial_1 F(x,y) - \partial_2 F(x,y) = 0 \end{cases}\]
Donner un équivalent de \(F(x, x)-F(0.0)\) et de \(F(x,-x)-F(0,0)\) quand \(x\) tend vers 0. \(F\) présente-t-elle un extremum en \(( 0,0 )\) ?
Calculer les dérivées partielles d’ordre 2 de \(F\) en \((x, x)\), en déduire les extrema locaux de \(F\) et indiquer s’il s’agit ou non de minima.
Établir pour tout couple \((x, y)\) de nombres réels l’ égalité suivante: \[F(x, y)=\left(x^{2}+y^{2}-1\right)^{2}+2 q \left( x-y \right)^{2}+(q-p)^{2}\]
En déduire le minimum de l’expression \(\phi(A-V\, {}^t V)\) lorsque \(V\) décrit l’ensemble des vecteurs de \(\mathbb{R}^{2}\) ainsi que les vecteurs \(V\) qui réalisent ce minimum.
Prouver enfin qu’il existe une matrice \(M\) appartenant à \(T\) et une seule qui minimise I’expression \(\phi(A-M)\).
Le corrigé pas à pas, les aides et les explications sont disponibles dans la plateforme.