J-0
00m
00j
00h
00min
00s

BCE Maths approfondies HEC/ESCP ECS 2000

Epreuve de maths approfondies - ECS 2000

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Suites et séries de fonctionsProbabilités finies, discrètes et dénombrementAlgèbre généraleInformatiqueFonctions (limites, continuité, dérivabilité, intégration)
RetourLire
Logo concours BCE - Voir tous les sujets BCE

Voir tous les sujets

Logo concours BCE
🔗 Explorer
Banque
BCE
Année
2000
Filière
ECS
Matière
Mathématiques
Annales BCE ECS MathématiquesBCE ECS 2000ECS MathématiquesMathématiques 2000

Téléchargements disponibles

Sujet et rapport

Télécharger le sujet →Rapport du jury → indisponible

Corrigés

Télécharger corrigé →

Lecture et formats

Lire en ligne →LaTeX →Word →

Description

Annale de maths approfondies BCE HEC/ESCP pour la filiere ECS, session 2000.

Lecture web du sujet

Version HTML avec rendu des formules, intégrée sur la page canonique.

PDF
d34f47e5-8179-4d3d-a500-5000f1ad96f6

ECOLE DES HAUTES ETUDES COMMERCIALES
E.S.C.P. - E.A.P.
ECOLE SUPERIEURE DE COMMERCE DE LYON

CONCOURS D'ADMISSION SUR CLASSES PREPARATOIRES

OPTION SCIENTIFIQUE

MATHEMATIQUES II

Mardi 16 Mai 2000, de 8h. à 12h.
La présentation, la lisibilité, l'orthographe, la qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l'appréciation des copies.
Les candidats sont invités à encadrer dans la mesure du possible les résultats de leurs calculs.
Ils ne doivent faire usage d'aucun document ; l'utilisation de toute calculatrice et de tout matériel électronique est interdite.
Seule l'utilisation d'une règle graduée est autorisée.
Le problème consiste en l'analyse d'un algorithme de tri et l'étude de sa complexité.
On note le logarithme népérien d'un réel strictement positif et son logarithme en base 2 . On rappelle que .

Partie I: Étude d'une suite réelle

Dans cette partie la lettre désignera toujours un entier naturel au moins égal à 2 .
On considère la suite définie par son premier terme et vérifiant, pour tout , la relation de récurrence : .
  1. a) Calculer et en fonction de .
    b) Montrer que, pour tout au moins égal à 3 , on a : .
  2. Pour tout entier naturel non nul, on pose : .
    a) Pour tout au moins égal à 3 , exprimer en fonction de .
    b) Déterminer deux réels et vérifiant, pour tout réel non nul et distinct de -1 , l'égalité:
c) Pour tout , établir l'égalité : .
3) Pour tout , on pose et .
a) Calculer en fonction de et .
b) Prouver l'égalité : .
c) Déterminer la nature de la série de terme général .
d) En déduire un équivalent de quand tend vers l'infini.
e) Déterminer un équivalent de quand tend vers l'infini.

Partie II: Étude d'une suite de variables aléatoires

A. On considère un espace probabilisé dont la probabilité est notée , une variable aléatoire , définie sur cet espace, prenant un nombre fini de valeurs réelles notées et un événement de probabilité non nulle.
On note l'espérance de la variable aléatoire pour la probabilité conditionnelle sachant , i.e.
Soit ( ) un système complet d'événements tous de probabilité non nulle. Prouver l'égalité :
B. Toutes les variables aléatoires considérées dans cette sous-partie sont définies sur un même espace probabilisé dont la probabilité est notée .
On considère une suite de variables aléatoires telle que, pour tout non nul, suit la loi uniforme sur l'ensemble des entiers compris, au sens large, entre 1 et .
D'autre part, on considère une suite de variables aléatoires ayant les propriétés suivantes:
  • est la variable constante égale à 0
  • pour tout entier naturel au moins égal à 2 , les lois conditionnelles de sachant et de sachant sont toutes deux égales à la loi de
  • pour tout entier naturel au moins égal à 3 et tout entier tel que , la loi conditionnelle de sachant est égale à la loi de où et sont deux variables aléatoires indépendantes, ayant même loi que et ayant même loi que .
Par exemple, on a :
et aussi ce qui, compte tenu des hypothèses, s'écrit : , la somme étant étendue aux valeurs convenables de l'entier .
  1. a) Montrer que est une variable aléatoire presque sûrement constante égale à 1 .
    b) Établir les égalités: et . Calculer l'espérance de qu'on notera .
  2. Déterminer la loi de et calculer son espérance qu'on notera .
  3. En procédant par récurrence, montrer que, pour tout entier naturel non nul, prend, presque sûrement, des valeurs entières inférieures ou égales à .
  4. Soit un entier naturel au moins égal à 2 . On note l'espérance de .
    a) À l'aide des résultats de la sous-partie , établir l'égalité : .
    b) À l'aide de la partie , donner l'expression de en fonction de ainsi qu'un équivalent de quand tend vers l'infini.
  5. Pour tout entier naturel non nul, on note la plus petite valeur (entière) prise par la variable avec une probabilité non nulle.
    a) Soit et deux entiers naturels, l'entier étant au moins égal à 3 .
Montrer que est nul si et seulement si les nombres et (l'entier variant de 2 à ) sont nuls.
En déduire que est au moins égal au minimum des nombres , .
b) On considère la fonction définie, pour tout strictement positif, par .
i) Montrer que est convexe. Pour tout couple d'entiers ( ) tel que , en déduire l'inégalité : .
ii) Pour tout entier naturel non nul, établir l'inégalité : . En traitant à part les cas et , montrer que, pour tout entier naturel non nul, on a : .
6) En procédant par récurrence, établir, pour tout entier naturel non nul, l'inégalité:

Partie III : Étude d'un algorithme de tri

A. On considère un entier naturel non nul et un ensemble où sont des réels vérifiant . On munit l'ensemble des permutations de de la probabilité uniforme notée . On considère les variables aléatoires qui, à toute permutation de , associent les images des éléments de par , i.e. , et on note le vecteur aléatoire ( ). Pour toute liste ( ) d'éléments distincts de on a donc
  1. Déterminer la loi de la variable aléatoire .
  2. On suppose au moins égal à 2 . Pour toute permutation de on note le premier élément de la liste inférieur à si un tel élément existe et sinon, le deuxième élément inférieur à si un tel deuxième élément existe et sinon, etc., le -ième élément inférieur à si un tel -ième élément existe et sinon.
    Par exemple, si
    et
    alors et .
    Soit un entier vérifiant .
    a) Combien y a-t-il de listes ( ) d'entiers vérifiant ?
    b) Soit ( ) une liste d'éléments distincts de . Établir l'égalité:
c) En déduire l'égalité :
où désigne la probabilité conditionnelle de sachant .
Ainsi la loi conditionnelle de ( ) sachant est uniforme.
B. Dans un programme écrit en langage Pascal on fait les déclarations suivantes :
const n = «entier naturel non nul fixé par l'utilisateur» ;
type tableau = array [1..n] of integer;
Soit une variable de type tableau qu'on suppose constituée d'éléments distincts. Si deb et fin sont deux entiers tels que on dira qu'un élément de la liste est à sa place dans le sous-tableau si les éléments sont inférieurs à et si les éléments sont supérieurs à (bien sûr, si ou , une seule de ces conditions subsiste).
Ainsi, si et alors est à sa place dans le sous-tableau mais n'est pas à sa place dans le le sous-tableau .
On dira que le tableau est trié si chacun de ses éléments est à sa place dans .
On suppose qu'on dispose d'une procédure (écrite en langage Pascal) dont l'en-tête est
Placer (var T : tableau ; deb, fin : integer ; var pl: integer);
qui ne fait rien si fin et qui, si , effectue, à l'aide de ( ) comparaisons, les opérations suivantes:
i) d'une part, elle ne modifie que le sous-tableau de sorte que les éléments de ce soustableau plus petits que "ont glissé" (sans permutation entre-eux) à gauche de et les éléments de ce sous-tableau plus grands que "ont glissé" (sans permutation entre-eux) à droite de . Ainsi [deb] se retrouve à sa place dans le sous-tableau modifié.
ii) d'autre part, elle met dans la variable l'indice tel que reçoit, au cours de la procédure, la valeur qui était stockée dans deb avant l'exécution de la procédure.
Par exemple, si l'instruction une fois exécutée aura changé en et affecté la valeur 5 à la variable , alors que l'instruction aura laissé inchangé et affecté la valeur 3 à la variable .
Par ailleurs on considère la procédure suivante:
procedure Tri(varT:tableau;deb,fin: integer);
var pl: integer;
begin
    if fin > deb then begin Placer(T, deb, fin,pl);
            if pl > deb then Tri(T, deb,pl-1);
            if pl<fin then Tri(T,pl+1,fin);
        end ;
end ;
  1. a) L'entier étant compris entre 1 et , quel est l'effet sur la variable de l'instruction ?
    b) Dans cette sous-question on suppose qu'initialement .
Déterminer la «trace»de l'instruction en donnant la liste des procédures successives (avec les valeurs de leurs paramètres) qui sont effectuées et en indiquant à chaque fois les affectations des variables pl et .
c) Expliquer succinctement l'effet et le principe de fonctionnement de la procédure Tri en indiquant, en particulier, pourquoi l'algorithme s'arrête.
2) On se place à nouveau dans le contexte probabiliste de la sous-partie et, si est une permutation de , on affecte la valeur à la variable de type tableau, i.e. , . On note le nombre de comparaisons faites lors des différentes exécutions de la procédure Placer (et seulement au cours de celles-ci) quand on effectue la procédure .
a) À l'aide de la sous-partie , montrer que la suite de variables aléatoires vérifie les hypothèses de II.B. En déduire un équivalent de l'espérance de lorsque l'entier naturel tend vers l'infini.
b) Dans le cas où , donner (en le commentant de manière succincte) un exemple de tableau nécessitant comparaisons pour être trié.
c) Dans le cas où , donner de même un exemple de tableau nécessitant 10 comparaisons pour être trié.
d) Déterminer une suite d'entiers pour lesquels, dans le cas où , il existe un tableau d'éléments nécessitant comparaisons pour être trié.

Pas de description pour le moment