ESSEC concours mathématiques III 1999 option économique

Informations

• Publié par: aiolos
• Nombre de lectures: 203
• Langue: Français

Extrait

] p N p [ p ] + N l [ p [1] q J q 2 p F + F q N p n + :; q F 1 N p [1] q 1 + : l p k ] ] F i F [ F F N 1 ]  N k F   p N k N i N  [ k [2 i F  N p ; q ; k ::; : [  [1] k N  N p [ k + q q ] i [ ESSEC CONCOURS D’ADMISSION DE 1999 Option economique´ Mathematiques´ III Exercice I : Etude du tri dichotomique. Dans cet exercice, on consider` e un nombre entier naturel et le nombre entier =2 . Dans cases numer´ otees´ sont rangees´ fiches (a` raison d’une fiche par case) qui contiennent des informations dont un nombre note´ pour la fiche rangee´ dans la case 1, pour la fiche rangee´ dans la case 2, ... , pour la fiche rangee´ dans la case . Ces fiches peuvent repres´ enter les clients d’une entreprise et les nombres ;F ;: : :; F les montants des commandes passees´ par ces clients, ou bien les candidats a` un concours et les nombres ;F ;: : ;F les totaux des points obtenus par ces candidats, etc. L’objectif est ici de ”trier ces fiches”, autrement dit de les ranger dans les cases de fac¸on ac` equeles nombres ;F ;: : soient dans l’ordre croissant. Si par exemple les fiches consider´ ees´ sont celles des candidats a` un concours, on cherche donc al` es ranger dans l’ordre croissant des totaux obtenus (de fac ¸on a` ce que la premier` e fiche soit donc celle d’un candidat avec le plus faible total, la dernier` e celle d’un candidat avec le plus fort total). On et´ udie maintenant un algorithme tres` performant de tri (” tri dichotomique ” ) de ces fiches. 1. Tri des fiches de deux tas de fiches dej´ at` ries´ . On consider` e deux tas tries´ de fiches (ce qui signifie qu’al` ’inter´ ieur de chacun des deux tas, les fiches sont rangees´ dans l’ordre croissant des nombres ). L’objectif est ici de reuni´ r les fiches de ces deux tas en un seul tas trie(´ al` ’int er´ ieur duquel les fiches seront donc rangees´ dans l’ordre croissant des nombres ). a) Soient deux tas tries´ contenant respectivement fiches et 1 fiche. On compare successivement l’unique fiche du second tas aux fiches du premier tas afin d’obtenir un seul tas tried´ e +1 fiches. Deter´ miner alors le nombre maximal des comparaisons de fiches n´ ecessaires a` l’obtention d’un seul tas tried´ e fiches. b) Soient deux tas tries´ contenant respectivement fiches et fiches. Raisonnant par recur´ rence sur , on suppose qu’un majorant du nombre des comparaisons de fiches neces´ saires pour reuni´ r en un seul tas tried´ e fiches ces deux tas tries´ est . Soient deux tas tries´ (dans l’ordre croissant) contenant respectivement fiches et fiches. On compare successivement la premier` e fiche du second tas aux fiches du premier tas. Il existe donc un nombre entier ( +1 ) tel que cette fiche se classe en position de ce premier tas trie.´ On place cette fiche en position du premier tas qui contient alors +1 fiches, le second tas ne contenant plus que fiches. D´ eterminer en fonction de le nombre de comparaisons de fiches neces´ saires a` la recherche de ce nombre entier un majorant du nombre des comparaisons de fiches neces´ saires pour reuni´ r en un seul tas triel´ es +1 dernier` es fiches triees´ restant dans ce premier tas et les fiches triees´ restant dans le second tas. un majorant du nombre des comparaisons de fiches neces´ saires pour reuni´ r en un seul tas tried´ e +1 fiches les deux tas tries´ initialement donnes´ . Conclure ESSEC 1999 Eco III Page 1/ 4 eme eme [2] [2] [2] 1] N  n 2 2 2 n n v N n 2 = n u  n  = 2 2 + n 1024   u Y 1 B 2 1 u n 3  u u 0 N  n  N u N n 1 u = n R 1 B n R v N n x v y n 1 1 2 n n   v N n  n  u  n n c) En deduir´ e enfin un majorant du nombre des comparaisons de fiches neces´ saires pour reunir´ en un seul tas tried´ e fiches deux tas tries´ de fiches. Ce majorant peut-il eˆtre atteint? 2. L’algorithme du tri dichotomique. a) On consider` e 4 fiches, que l’on trie de la fac¸on suivante: on constitue deux tas, formes´ des 2 premier` es fiches et des 2 dernier` es fiches. on trie chacun de ces tas, ce qui neces´ site une comparaison de fiches dans chacun d’eux. on reunit´ ces deux tas tries´ en un seul tas trie,´ al` ’aidedelamethode´ de la question 1. Combien de comparaisons de fiches doit-on faire au plus pour trier ainsi ces 4 fiches? b) On consider` e 8 fiches que l’on trie de la fac¸on suivante: on constitue deux tas, formes´ des 4 premier` es fiches et des 4 dernier` es fiches. on trie chacun de ces tas a` l’aide de l’algorithme expliquep´ rec´ edem´ ment. on reunit´ ces deux tas tries´ en un seul tas trie,´ al` ’aidedelamethode´ de la question 1. Combien de comparaisons de fiches doit-on faire au plus pour trier ainsi ces 8 fiches? c) En poursuivant de meme,ˆ combien de comparaisons de fiches doit-on faire au plus pour trier 16 fiches, 32 fiches, 64 fiches? d) On revient aux conditions donnees´ au deb´ ut de l’enonc´ e´ et, pour trier les =2 fiches, on proce`de comme suit : on constitue deux tas, formes´ des premier` es fiches et des dernier` es fiches. on trie chacun de ces tas, a` l’aide de l’algorithme expliquep´ rec´ edem´ ment. on reunit´ ces deux tas tries´ en un seul tas trie,´ al` ’aidedelamethode´ de la question 1. On convient alors de noter le nombre maximum de comparaisons de fiches neces´ saires au tri de ces fiches a` l’aide de cet algorithme et l’on pose . D´ eterminer : les valeurs de ;u et (et on pose bien entendu =0 ). l’expression de en fonction de et , puis l’expression de en fonction de . la valeur de en fonction de , puis la valeur de en fonction de . le nombre maximum de comparaisons de fiches ainsi neces´ saires au tri de =2 fiches exprimee´ nfonctionde , puis de ,etunequi´ valent de celui-ci quand tend vers . e) Indiquer le res´ ultat des actions effectuees´ par le passage dans la boucle inter´ ieure, puis exter´ ieure de l’algorithme suivant, et precis´ er le nombre de comparaisons de fiches re´alisees´ : Pour i:=N-1 a` 1 faire : Pour j := 1 a` i faire : Si F[j] > F[j+i] alors echanger´ les fiches j et j+l. ¨Comparer cet algorithme ”naif” au prec´ edent.´ Qu’obtient-on, par exemple, pour ? Exercice II : Algebre` lineair´ e et analyse. Dans cet exercice, l’espace vectoriel est rapporte`´ a sa base canonique et on identifie : tout vecteur de a` la matrice colonne de ses composantes et dans . ESSEC 1999 Eco III Page 2/ 4M A 1  M Y V  ; Y 6 t V
) X y R  2 A = A M  = 2 X  2 M R  : =     M 1 V 1 B T M T Y M = M Y )
 Y V t M V  f ) V ( ) ( X V (
M 2 ect V R 1 M M Im C 2 1 f = 2 0   ( B V ( ) M R )  T (  M V ) V ( M V V V (
= t M X ) V   ( f = R V 2 2 T   V f  R M 2  T V T t p t q V 0 M  R V x 1 T T  p 1 +  q 1 M = A ; A 1  1 M  p B q  q 1 p 1  = T C M A T M  tout endomorphisme de a` sa matrice dans . Pour tout vecteur ou pour toute matrice ,ondes´ igne par ou la somme des carres´ des deux composantes de ou des quatre coefficients de . On note enfin l’ensemble des matrices re´elles d’ordre 2 telles que : est symetr´ ique. est nulle ou est de rang egal´ a` 1. (Notion hors programme !) a des valeurs propres positives ou nulles. 1. Exemples de matrices appartenant ou non a` . Etudier l’appartenance a` T des trois matrices , , d´ efinies par : 2. Etude des matrices appartenant a` . a) Pour tout vecteur de composantes , appartenant a` , on pose o` u d´ esigne la transposee´ de . (notion hors programme !) Comparer et et montrer que est nulle si et seulement si est nul. Montrer que MV et que . D´ eterminer en fonction de les valeurs propres et les vecteurs propres de pour =0 . Etablir que appartient a` b) On consider` e recipr´ oquement une matrice non nulle de . Montrer qu’il existe un vecteur non nul appartenant a` tel que =V , puis un vecteur non nul appartenant a` tel que Montrer, en utilisant la symet´ rie de la matrice , qu’il existe un nombre reel´ non nul tel que Montrer enfin que est strictement positif et en deduir´ e l’existence d’un vecteur non nul tel que . c) On consider` e l’application associant a` tout vecteur de la matrice carree´ )= . est-elle surjective de dans ? est-elle injective de dans ? 3. Approximation d’une matrice syme´trique d’ordre 2 par une matrice de . On consider` e dans cette question deux nombres reel´ s , tels que

( x F (0 x ) x (0 y ) 2 x; + x y ( 2 y 1) M 2 ( q t ( ) x F y ) ) x; 2 x; q ( ) ( p > ) y V y ( 0) 2 ; F :  ( ( 2 A  V A

t V V F ) x V ( R ; 2 F A ( V y
( t y V ( Y x; M y T F  : ( < A 8 ) ) R x; : F (0 F x b) On des´ igne par , les composantes d’un vecteur . Expliciter la matrice , puis exprimer en fonctionˆ de , )= c) Calculer les der´ ive´es partielles de par rapport aux deux variables et , puis en deduir´ e deux conditions neces´ saires pour que pres´ ente un extremum en . d) R´ esoudre le system` e d’equations´ suivant : @F @F )+ )= 0 @x @y @F @F )= 0 @x @y e) Donner un equi´ valent de x; x 0) et de quand tend vers 0. pres´ ente-t-elle un extremum en ? f) Calculer les der´ ive´es partielles d’ordre 2 de en x; x ,end eduir´ e les extrema locaux de et indiquer s’il s’agit ou non de minima. g) Etablir pour tout couple de nombres reel´ s l’ egal´ ite´ suivante: )= ( +2 +( En deduir´ e le minimum de l’expression lorsque d´ ecrit l’ensemble des vecteurs de ainsi que les vecteurs qui re´alisent ce minimum. h) Prouver enfin qu’il existe une matrice appartenant a` et une seule qui minimise l’expression M: On precis´ era la nature de l’endomorphisme de repres´ ente´ par cette matrice . ESSEC 1999 Eco III Page 4/ 4 y x; 0) y x;