ESSEC

CONCOURS D’ADMISSION DE 1999

Option économique
Mathématiques III
Exercice I : Etude du tri dichotomique.
Dans cet exercice, on considère un nombre entier naturel n et le nombre entier N = 2.
Dans N cases numérotées 1; 2; :::; N sont rangées N …ches (à raison d’une …che par case) qui conti-
ennent des informations dont un nombre noté F [1] pour la …che rangée dans la case 1, F [2] pour la
…che rangée dans la case 2, ... , F [N ] pour la …che rangée dans la case N .
Ces …ches peuvent représenter les clients d’une entreprise et les nombres F [1]; F [2]; :::; F [N ] les mon-
tants des commandes passées par ces clients, ou bien les candidats à un concours et les nombres
F [1]; F [2J; :::; F [N ] les totaux des points obtenus par ces candidats, etc.
L’objectif est ici de ”trier ces N …ches”, autrement dit de les ranger dans les cases de façon à ce que
les nombres F [1]; F [2]; :::; F [N ] soient dans l’ordre croissant.
Si par exemple les …ches 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 …che 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 …ches.

1. Tri des …ches de deux tas de …ches déjà triés.

On considère deux tas triés de …ches (ce qui signi…e qu’à l’intérieur de chacun des deux tas,
les …ches sont rangées dans l’ordre croissant des nombres F [i]). L’objectif est ici de réunir les
…ches de ces deux tas en un seul tas trié (à l’intérieur duquel les …ches seront donc rangées dans
l’ordre croissant des nombres F [i]).

a) Soient deux tas triés contenant respectivement p …ches et 1 …che.

On compare successivement l’unique …che du second tas aux …ches du premier tas a…n
d’obtenir un seul tas trié de p + 1 …ches. Déterminer alors le nombre maximal des com-
paraisons de …ches nécessaires à l’obtention d’un seul tas trié de p + l …ches.
b) Soient deux tas triés contenant respectivement p …ches et q …ches.
Raisonnant par récurrence sur q, on suppose qu’un majorant du nombre des comparaisons
de …ches nécessaires pour réunir en un seul tas trié de p + q …ches ces deux tas triés est
p + q 1.
Soient deux tas triés (dans l’ordre croissant) contenant respectivement p …ches et q + l
…ches.
On compare successivement la première …che du second tas aux …ches du premier tas.
Il existe donc un nombre entier k (1 k p + 1) tel que cette …che se classe en k ieme
position de ce premier tas trié. On place cette …che en k ieme position du premier tas qui
contient alors p + 1 …ches, le second tas ne contenant plus que q …ches.
Déterminer en fonction de k :
le nombre de comparaisons de …ches nécessaires à la recherche de ce nombre entier k
un majorant du nombre des comparaisons de …ches nécessaires pour réunir en un seul
tas trié les p + 1 k dernières …ches triées restant dans ce premier tas et les q …ches
triées restant dans le second tas.
un majorant du nombre des comparaisons de …ches nécessaires pour réunir en un seul
tas trié de p + q + 1 …ches les deux tas triés initialement donnés. Conclure

ESSEC 1999 Eco III Page 1/ 4

 c) En déduire en…n un majorant du nombre des comparaisons de …ches nécessaires pour
réunir en un seul tas trié de 2N …ches deux tas triés de N …ches. Ce majorant peut-il être
atteint?

2. L’algorithme du tri dichotomique.

a) On considère 4 …ches, que l’on trie de la façon suivante:

on constitue deux tas, formés des 2 premières …ches et des 2 dernières …ches.
on trie chacun de ces tas, ce qui nécessite une comparaison de …ches 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 …ches doit-on faire au plus pour trier ainsi ces 4 …ches?
b) On considère 8 …ches que l’on trie de la façon suivante:
on constitue deux tas, formés des 4 premières …ches et des 4 dernières …ches.
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 …ches doit-on faire au plus pour trier ainsi ces 8 …ches?
c) En poursuivant de même, combien de comparaisons de …ches doit-on faire au plus pour
trier 16 …ches, 32 …ches, 64 …ches?
d) On revient aux conditions données au début de l’énoncé et, pour trier les N = 2n …ches,
on procède comme suit :
on constitue deux tas, formés des 2n 1 premières …ches et des 2n 1 dernières …ches.
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 un le nombre maximum de comparaisons de …ches nécessaires
au tri de ces 2n …ches à l’aide de cet algorithme et l’on pose vn = un =2n .
Déterminer :
les valeurs de u1 ; u2 et u3 (et on pose bien entendu u0 = 0).
l’expression de un en fonction de un 1 et n, puis l’expression de vn vn 1 en fonction
de n.
la valeur de vn en fonction de n, puis la valeur de un en fonction de n.
le nombre maximum de comparaisons de …ches ainsi nécessaires au tri de N = 2n
…ches exprimé en fonction de n, puis de N , et un équivalent de celui-ci quand N tend
vers +1.
e) Indiquer le résultat des actions e¤ectuées par le passage dans la boucle intérieure, puis
extérieure de l’algorithme suivant, et préciser le nombre de comparaisons de …ches réalisées:
Pour i:=N-1 à 1 faire :
Pour j := 1 à i faire :
Si F[j] > F[j+i] alors échanger les fiches j et j+l.
Comparer cet algorithme ”naïf” au précédent. Qu’obtient-on, par exemple, pour N =
1024?

ESSEC 1999 Eco III Page 2/ 4

Exercice II : Algèbre linéaire et analyse.
Dans cet exercice, l’espace vectoriel R2 est rapporté à sa base canonique B et on identi…e :

tout vecteur de R2 à la matrice colonne Y de ses composantes x et y dans B.

tout endomorphisme de R2 à sa matrice M dans B.

Pour tout vecteur Y ou pour toute matrice M , on désigne par (V ) ou (M ) la somme des carrés
des deux composantes de V ou des quatre coe¢ cients de M .
On note en…n 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. (Notion hors programme !)

M a des valeurs propres positives ou nulles.

1. Exemples de matrices appartenant ou non à T .

Etudier l’appartenance à T des trois matrices A, B, C dé…nies par :

1 1 1 1 1 1
A= ; B= ; C=
1 0 1 1 1 1

2. Etude des matrices appartenant à T .

a) Pour tout vecteur V de composantes x, y appartenant à R2 , on pose M = V t

V où t V
désigne la transposée de V . (notion hors programme !)
Comparer (M ) et (V )2 et montrer que M est nulle si et seulement si V est nul.
Montrer que M V = (V ) V et que M 2 = (V ) M .
Déterminer en fonction de V les valeurs propres et les vecteurs propres de M pour
V 6= 0.
Etablir que M appartient à T
b) On considère réciproquement une matrice M non nulle de T .
Montrer qu’il existe un vecteur non nul X appartenant à R2 tel que ImM = Vect (X),
puis un vecteur non nul Y appartenant à R2 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
tel que Y = X:
Montrer en…n que est strictement positif et en déduire l’existence d’un vecteur non
nul V tel que M = Y t V .
c) On considère l’application f associant à tout vecteur V de R2 la matrice carrée f (V ) =
V tV.
f est-elle surjective de R2 dans T ?
f est-elle injective de R2 dans T ?

ESSEC 1999 Eco III Page 3/ 4

 3. 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 < y < 1 et p + q = 1
et la matrice symétrique A dé…nie par :

p q
A
q p

L’objectif de cette question est de trouver les matrices M appartenant à T qui minimisent
l’expression (A M )

a) La matrice A appartient-elle à T ?
t
b) On désigne par x, y les composantes d’un vecteur V . Expliciter la matrice A V V,
puis exprimer en fônction de x, y :
t
F (x; y) = (A V V)

c) 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).
d) Résoudre le système d’équations suivant :
8
> @F @F
< (x; y) + (x; y) = 0
@x @y
> @F @F
: (x; y) (x; y) = 0
@x @y

e) 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)?
f) 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.
g) Etablir pour tout couple (x; y) de nombres réels l’égalité suivante:

F (x; y) = (x2 + y 2 1)2 + 2q(x y)2 + (q p)2

En déduire le minimum de l’expression (A V t V ) lorsque V décrit l’ensemble des

vecteurs de R2 ainsi que les vecteurs Y qui réalisent ce minimum.
h) Prouver en…n qu’il existe une matrice M appartenant à T et une seule qui minimise
l’expression (A M:)
On précisera la nature de l’endomorphisme de R2 représenté par cette matrice M .

ESSEC 1999 Eco III Page 4/ 4