Mathématiques III 1999 Classe Prepa HEC (ECE) ESSEC

ESSEC CONCOURS D’ADMISSION DE 1999 Option economique ´ Math´ matiques III e Exercice I : Etude du tri dichotomique.
Dans cet exercice, on consid` re un nombre entier naturel Ò et le nombre entier Æ ¾. e e e Æ sont rang´ es Æ fiches (` raison d’une fiche par case) qui contiennent e a Dans Æ cases num´ rot´ es ½ ¾ des informations dont un nombre not´ e ½ pour la fiche rang´ e dans la case 1, ¾ pour la fiche rang´ e e e dans la case 2, ... , Æ pour la fiche rang´ e dans la case Æ . e ¾ Æ les montants Ces fiches peuvent repr´ senter les clients d’une entreprise et les nombres ½ e des commandes pass´ es par ces clients, ou bien les candidats a un concours et les nombres ½ e ` ¾Â Æ 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 facon a ce que les ¸ ` nombres ½ ¾ Æ soient dans l’ordre croissant. ` ` Si par exemple les fiches consid´ r´ es sont celles des Æ candidats a un concours, on cherche donc a les ee ranger dans l’ordre croissant des totaux obtenus (de facon a ce que la premi` re fiche soit donc celle d’un ¸ ` e candidat avec le plus faible total, la derni` re celle d’un candidat avec le plus fort total). e On etudie maintenant un algorithme tr` s performant de tri (” tri dichotomique ” ) de ces Æ fiches. ´ e 1. Tri des fiches de deux tas de fiches d´ j` tri´ s. ea e On consid` re deux tas tri´ s de fiches (ce qui signifie qu’` l’int´ rieur de chacun des deux tas, les fiches e e a e ). L’objectif est ici de r´ unir les fiches de ces e sont rang´ es dans l’ordre croissant des nombres e deux tas en un seul tas tri´ (` l’int´ rieur duquel les fiches seront donc rang´ es dans l’ordre croissant e a e e des nombres ). a) Soient deux tas tri´ s contenant respectivement Ô fiches et 1 fiche. e On compare successivement l’unique fiche du second tas aux fiches du premier tas afin d’obtenir e un seul tas tri´ de Ô · ½ fiches. D´ terminer alors le nombre maximal des comparaisons de fiches e n´ cessaires a l’obtention d’un seul tas tri´ de Ô · Ð fiches. e ` e b) Soient deux tas tri´ s contenant respectivement Ô fiches et Õ fiches. e Raisonnant par r´ currence sur Õ , on suppose qu’un majorant du nombre des comparaisons de e e fiches n´ cessaires pour r´ unir en un seul tas tri´ de Ô · Õ fiches ces deux tas tri´ s est Ô · Õ   ½. e e e Soient deux tas tri´ s (dans l’ordre croissant) contenant respectivement Ô fiches et Õ · Ð fiches. e On compare successivement la premi` re fiche du second tas aux fiches du premier tas. e Il existe donc un nombre entier (½ Ô · ½) tel que cette fiche se classe en Ñ position de ce premier tas tri´ . On place cette fiche en Ñ position du premier tas qui contient alors e Ô · ½ fiches, le second tas ne contenant plus que Õ fiches. D´ terminer en fonction de e

¯ ¯ ¯

le nombre de comparaisons de fiches n´ cessaires a la recherche de ce nombre entier e ` un majorant du nombre des comparaisons de fiches n´ cessaires pour r´ unir en un seul tas e e tri´ les Ô · ½   derni` res fiches tri´ es restant dans ce premier tas et les Õ fiches tri´ es e e e e restant dans le second tas. un majorant du nombre des comparaisons de fiches n´ cessaires pour r´ unir en un seul tas e e tri´ de Ô · Õ · ½ fiches les deux tas tri´ s initialement donn´ s. Conclure e e e

ESSEC 1999 Eco III

Page 1/ 4

c) En d´ duire enfin un majorant du nombre des comparaisons de fiches n´ cessaires pour r´ unir en e e e e ˆ un seul tas tri´ de ¾Æ fiches deux tas tri´ s de Æ fiches. Ce majorant peut-il etre atteint? e 2. L’algorithme du tri dichotomique. a) On consid` re 4 fiches, que l’on trie de la facon suivante: e ¸

¯ ¯ ¯ ¯ ¯ ¯

on constitue deux tas, form´ s des 2 premi` res fiches et des 2 derni` res fiches. e e e on trie chacun de ces tas, ce qui n´ cessite une comparaison de fiches dans chacun d’eux. e on r´ unit ces deux tas tri´ s en un seul tas tri´ , a l’aide de la m´ thode de la question 1. e e e ` e

Combien de comparaisons de fiches doit-on faire au plus pour trier ainsi ces 4 fiches? b) On consid` re 8 fiches que l’on trie de la facon suivante: e ¸ on constitue deux tas, form´ s des 4 premi` res fiches et des 4 derni` res fiches. e e e on trie chacun de ces tas a l’aide de l’algorithme expliqu´ pr´ c´ demment. ` e e e on r´ unit ces deux tas tri´ s en un seul tas tri´ , a l’aide de la m´ thode de la question 1. e e e ` e

Combien de comparaisons de fiches doit-on faire au plus pour trier ainsi ces 8 fiches? c) En poursuivant de mˆ me, combien de comparaisons de fiches doit-on faire au plus pour trier 16 e fiches, 32 fiches, 64 fiches? d) On revient aux conditions donn´ es au d´ but de l’´ nonc´ et, pour trier les Æ e e e e proc` de comme suit : e
¾Ò

fiches, on

¯ ¯ ¯

on constitue deux tas, form´ s des ¾Ò ½ premi` res fiches et des ¾Ò ½ derni` res fiches. e e e on trie chacun de ces tas, a l’aide de l’algorithme expliqu´ pr´ c´ demment. ` e e e on r´ unit ces deux tas tri´ s en un seul tas tri´ , a l’aide de la m´ thode de la question 1. e e e ` e

On convient alors de noter ÙÒ le nombre maximum de comparaisons de fiches n´ cessaires au tri e Ò Ò de ces ¾ fiches a l’aide de cet algorithme et l’on pose ÚÒ ÙÒ ¾ . ` D´ terminer : e

¯ ¯ ¯ ¯

les valeurs de Ù½ Ù¾ et Ù¿ (et on pose bien entendu Ù¼ ¼). 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 n´ cessaires au tri de Æ e ¾Ò fiches ´ exprim´ en fonction de Ò, puis de Æ , et un equivalent de celui-ci quand Æ tend vers ·½. e

e) Indiquer le r´ sultat des actions effectu´ es par le passage dans la boucle int´ rieure, puis ext´ rieure e e e e de l’algorithme suivant, et pr´ ciser le nombre de comparaisons de fiches r´ alis´ es: e e e 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. ´ ¨ au pr´ c´ dent. Qu’obtient-on, par exemple, pour Æ ½¼¾ ? Comparer cet algorithme ”naif” e e

Exercice II : Alg` bre lin´ aire et analyse. e e ¾
¯
tout vecteur de ʾ a la matrice colonne `

Dans cet exercice, l’espace vectoriel Ê est rapport´ a sa base canonique e`

et on identifie :

de ses composantes Ü et Ý dans . Page 2/ 4

ESSEC 1999 Eco III

¯

tout endomorphisme de ʾ a sa matrice Šdans . `

e e Pour tout vecteur ou pour toute matrice Å , on d´ signe par ´Î µ ou ´Å µ la somme des carr´ s des deux composantes de Î ou des quatre coefficients de Å . e On note enfin Ì l’ensemble des matrices r´ elles Å d’ordre 2 telles que :

¯ ¯ ¯

Å est sym´ trique. e Å 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´ finies par : e
½ ½

 ½
Î

½

` 2. Etude des matrices appartenant a Ì . a) Pour tout vecteur Î de composantes Ü, Ý appartenant a ʾ, on pose Å ` la transpos´ e de Î . (notion hors programme !) e

¡Ø Î

o` Ø Î d´ signe u e

b) On consid` re r´ ciproquement une matrice Å non nulle de Ì . e e

¯ ¯ ¯ ¯ ¯

Comparer ´Å µ et ´Î µ et montrer que Å est nulle si et seulement si Î est nul. Montrer que ÅÎ ´Î µ Î et que Å ¾ ´Î µ Å . D´ terminer en fonction de Î les valeurs propres et les vecteurs propres de Å pour Î e Etablir que Å appartient a Ì `

¾

¼.

¯ ¯ ¯ ¯

Montrer qu’il existe un vecteur non nul appartenant a ʾ tel que ÁÑÅ Î Ø ´ µ, puis ` ¾ tel que Å ` ¡Ø un vecteur non nul appartenant a Ê Montrer, en utilisant la sym´ trie de la matrice Å , qu’il existe un nombre r´ el non nul tel e e que Montrer enfin que est strictement positif et en d´ duire l’existence d’un vecteur non nul Î e Ø tel que &