نموذج مباراة ولوج السنة الثانية من سلك مهندسي الدولة - المعهد الوطني للبريد والمواصلات (INPT) 2004 - اختبار الرياضيات والمعلوميات

Ce modèle est l'épreuve de mathématiques-informatique du concours d'accès en deuxième année du cycle d'ingénieurs d'État de l'INPT, session du 15 juillet 2004. Durée : 3 heures. Deux parties à rédiger sur des feuilles séparées : mathématiques (optimisation d'une fonction fortement convexe, statistiques d'ordre de lois exponentielles, formule d'inversion de Fourier) et informatique (deux algorithmes en pseudo-code). Voici une correction proposée.

💡 Dans la partie mathématique, citez précisément le théorème utilisé (Fubini, convergence dominée, complétude de ℝ^p) et vérifiez ses hypothèses : c'est l'essentiel de la note.

Partie mathématiques

Exercice 1 — Méthode du gradient à pas fixe

1) Soit φ(t) = f(x + t(y − x)) sur [0, 1] ; f étant C¹, φ′(t) = ⟨∇f(x_t), y − x⟩ avec x_t = x + t(y − x). Donc

f(y) − f(x) = ∫₀¹ φ′(t) dt = ⟨∇f(x), y − x⟩ + ∫₀¹ ⟨∇f(x_t) − ∇f(x), y − x⟩ dt.

Par (i) appliqué à x_t et x (x_t − x = t(y − x)) : t⟨∇f(x_t) − ∇f(x), y − x⟩ ≥ αt²‖y − x‖², donc l'intégrande est ≥ αt‖y − x‖² pour t > 0, et ∫₀¹ αt dt = α/2. D'où f(y) − f(x) ≥ ⟨∇f(x), y − x⟩ + (α/2)‖x − y‖².

2) Stricte convexité : pour x ≠ y, 1) donne f(y) > f(x) + ⟨∇f(x), y − x⟩. Soit z = θx + (1 − θ)y avec θ ∈ ]0, 1[ ; en écrivant cette inégalité en z vers x et vers y, puis en combinant avec les poids θ et 1 − θ, le terme en gradient disparaît : θf(x) + (1 − θ)f(y) > f(z). f est strictement convexe.

Coercivité : avec x = 0 dans 1) et Cauchy-Schwarz, f(y) ≥ f(0) − ‖∇f(0)‖·‖y‖ + (α/2)‖y‖² → +∞ quand ‖y‖ → +∞.

Existence : l'ensemble K = {x : f(x) ≤ f(0)} est fermé (f continue), borné (coercivité) et non vide, donc compact ; f continue y atteint un minimum en x*, qui est un minimum global (hors de K, f > f(0) ≥ f(x*)). Unicité : si x₁ ≠ x₂ étaient deux minimiseurs, la stricte convexité donnerait f((x₁ + x₂)/2) < f(x₁), absurde. De plus ∇f(x*) = 0 (point intérieur où f est minimale).

3) Soit Φ(x) = x − ρ∇f(x). En développant le carré puis en utilisant (i) et (ii) :

‖Φ(x) − Φ(y)‖² = ‖x − y‖² − 2ρ⟨∇f(x) − ∇f(y), x − y⟩ + ρ²‖∇f(x) − ∇f(y)‖² ≤ (1 − 2ρα + ρ²M²)‖x − y‖².

On pose k² = 1 − 2ρα + ρ²M². On a k² < 1 ⇔ ρ(ρM² − 2α) < 0 ⇔ 0 < ρ < 2α/M², ce qui est l'hypothèse ; et k² ≥ 1 − α²/M² ≥ 0 (car (i), (ii) et Cauchy-Schwarz donnent α ≤ M). Donc Φ est contractante de rapport k ∈ [0, 1[ et ‖x_n+1 − x_n‖ ≤ kⁿ‖x₁ − x₀‖. Pour m > n :

‖x_m − x_n‖ ≤ (kⁿ + … + k^m−1)‖x₁ − x₀‖ ≤ kⁿ/(1 − k) · ‖x₁ − x₀‖ → 0 : (x_n) est de Cauchy. ℝ^p étant complet, x_n → ℓ. Par continuité de ∇f, ℓ = ℓ − ρ∇f(ℓ), soit ∇f(ℓ) = 0 ; alors 1) donne f(y) ≥ f(ℓ) pour tout y : ℓ est un minimiseur, donc ℓ = x* par unicité.

Exercice 2 — Lois exponentielles et téléboutique

1.a) Les X_i ont une loi à densité, donc P(deux X_i égaux) = 0. Pour A ⊂ E borélien, on découpe selon l'ordre des X_i (6 permutations σ) : P((X₍₁₎, X₍₂₎, X₍₃₎) ∈ A) = Σ_σ P((X_σ(1), X_σ(2), X_σ(3)) ∈ A). Les X_i étant i.i.d., chaque vecteur permuté a la densité λ³e^{−λ(x₁+x₂+x₃)} sur (ℝ₊*)³ ; les 6 termes sont égaux, d'où f(x₁, x₂, x₃) = 6λ³e^{−λ(x₁+x₂+x₃)} 1_E.

1.b) Changement de variables linéaire y₁ = x₁, y₂ = x₂ − x₁, y₃ = x₃ − x₂, de jacobien 1, qui envoie E sur (ℝ₊*)³, avec x₁ + x₂ + x₃ = 3y₁ + 2y₂ + y₃. La densité de (Y₁, Y₂, Y₃) est

6λ³e^{−λ(3y₁+2y₂+y₃)} = (3λe^−3λy₁)(2λe^−2λy₂)(λe^−λy₃) sur (ℝ₊*)³.

Elle est produit de densités : Y₁, Y₂, Y₃ sont indépendantes et Y_k suit la loi exponentielle de paramètre (4 − k)λ.

2.a) D entre à l'instant X₍₁₎ = min(X₁, X₂, X₃). Par l'absence de mémoire de la loi exponentielle (c'est aussi ce que traduit 1.b), les durées restantes des deux autres clients sont, à cet instant, deux exponentielles de paramètre λ indépendantes, et indépendantes de X₄. Trois durées i.i.d. démarrent ensemble : chacune a la même chance d'être la plus longue.

P(D sort le dernier) = 1/3.

2.b) T = X₍₁₎ + X₄ (attente puis communication), somme indépendante d'une Exp(3λ) et d'une Exp(λ). Par convolution, pour t > 0 :

f_T(t) = ∫₀^t 3λe^−3λs λe^−λ(t−s) ds = (3λ/2)(e^−λt − e^−3λt), et E(T) = 1/(3λ) + 1/λ = 4/(3λ).

2.c) Le dernier départ a lieu à S = X₍₁₎ + max(R₁, R₂, X₄), où le maximum de trois Exp(λ) i.i.d. est, d'après 1.b, la somme de trois exponentielles indépendantes de paramètres 3λ, 2λ et λ. Donc S est la somme de quatre exponentielles indépendantes de paramètres 3λ, 3λ, 2λ, λ. Le calcul des convolutions donne, pour t ≥ 0 :

F_S(t) = P(S ≤ t) = 1 − (9/2)e^−λt + 9e^−2λt − (11/2 + 3λt)e^−3λt, de densité f_S(t) = (9λ/2)e^−λt − 18λe^−2λt + (27λ/2 + 9λ²t)e^−3λt, et E(S) = 2/(3λ) + 1/(2λ) + 1/λ = 13/(6λ).

Exercice 3 — Formule d'inversion de Fourier

Convention : f̂(y) = ∫_ℝ f(t)e^−2iπty dt.

1.a) Non. ∫ f̂(y)e^2iπxy dy = ∫∫ f(t)e^2iπ(x−t)y dt dy, mais le module de l'intégrande vaut |f(t)| et ∫∫_ℝ² |f(t)| dt dy = +∞ (rien n'est intégrable en y) : l'hypothèse du théorème de Fubini n'est pas satisfaite et on ne peut pas échanger les intégrales.

1.b) Pour x fixé, posons g(t) = f(t + x) : g est continue, bornée, intégrable et ĝ(y) = e^2iπxy f̂(y) est intégrable. Alors g(0) = f(x) et ∫ ĝ(y) dy = ∫ f̂(y)e^2iπxy dy. Il suffit donc d'établir g(0) = ∫ ĝ pour toute fonction g de la même classe (inversion au point 0) ; on l'applique ensuite au translaté de f.

2) ∫ f(εt)ĥ(t) dt = ∫ f(εt) [∫ h(s)e^−2iπst ds] dt. Ici Fubini s'applique : ∫∫ |f(εt)h(s)| ds dt = ‖f‖₁‖h‖₁/ε < ∞. En échangeant puis en posant u = εt : ∫ f(εt)e^−2iπst dt = (1/ε) f̂(s/ε). D'où ∫ h(s)(1/ε) f̂(s/ε) ds, et le changement s = εt donne ∫ h(εt) f̂(t) dt.

3) On prend h(t) = e^−πt², dont la transformée est elle-même (ĥ = h) et ∫ h = 1. L'égalité 2) devient ∫ f(εt)e^−πt² dt = ∫ e^−πε²t² f̂(t) dt. Quand ε → 0, par convergence dominée (dominations ‖f‖_∞e^−πt² à gauche, |f̂| intégrable à droite) et continuité de f en 0 : f(0)∫ e^−πt² dt = f(0) = ∫ f̂(t) dt. C'est l'inversion en 0 ; par 1.b, f(x) = ∫_ℝ f̂(y)e^2iπxy dy pour tout x.

Partie informatique

Exercice 1 — Maximum et ses indices

On lit le tableau, on calcule le maximum en un parcours, puis on affiche tous les indices où il est atteint (second parcours).

T : Tableau[1..10] of Real
Emax : Real
i : Integer

For (i variant de 1 à 10)
Début
    Lire(T[i])
Fin
Emax ← T[1]
For (i variant de 2 à 10)
Début
    If (T[i] > Emax)
    Début
        Emax ← T[i]
    Fin
Fin
Afficher("La variable Emax = ")
Afficher(Emax)
Afficher("Les indices de Emax dans T sont : ")
For (i variant de 1 à 10)
Début
    If (T[i] = Emax)
    Début
        Afficher(i)
    Fin
Fin

Sur l'exemple : Emax = 9, indices affichés 4, 6, 10.

Exercice 2 — Palindrome

On compare Ch[i] et Ch[N − i + 1] pour i allant de 1 à N/2 ; on s'arrête dès qu'une différence est trouvée.

Ch : Tableau[1..10] of Char
N, i : Integer
pal : Boolean

Lire(Ch)
N ← taille(Ch)
Afficher("N=")
Afficher(N)
pal ← True
i ← 1
While (i <= N / 2 et pal)      /* division entière */
Début
    If (Ch[i] ≠ Ch[N - i + 1])
    Début
        pal ← False
    Fin
    i ← i + 1
Fin
If (pal)
Début
    Afficher("La chaîne ")  Afficher(Ch)  Afficher(" est un palindrome")
Fin
Else
Début
    Afficher("La chaîne ")  Afficher(Ch)  Afficher(" n'est pas un palindrome")
Fin

Contrôle : AZIZA (N = 5) compare A/A puis Z/Z → palindrome ; ELLA (N = 4) compare E/A → n'est pas un palindrome.