Corrigé Mines-Ponts 2026 Informatique option MP — Partie 1 (Q1 à Q4) : Puissance rapide et écriture binaire des lettres

Sujet officiel du concours Mines-Ponts, session 2026, épreuve Informatique option MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

Pour $n ⩾ 1$ , $Σ_{n}$ est l'alphabet des vecteurs colonnes de taille $n$ à coefficients dans ${0, 1}$ ; par exemple $Σ_{2} = {(0 0), (0 1), (1 0), (1 1)}$ . Pour un mot $u = u_{0} \dots u_{k - 1}$ sur ${0, 1}$ , $v (u) = \sum_{j = 0}^{k - 1} 2^{j} u_{j}$ (bit de poids faible à gauche). Pour un mot $m$ sur $Σ_{n}$ , $π_{i} (m)$ est le mot formé par la ligne $i$ de ses lettres et $v_{i} (m) = v (π_{i} (m))$ . En OCaml, une lettre de $Σ_{n}$ est un int array de taille $n$ à valeurs dans ${0, 1}$ ; on suppose les entiers non bornés.

Q1. Écrire une fonction récursive pow2 : int -> int calculant $2^{n}$ en $O (lo g n)$ , sans lsl ni lsr.
Q2. Démontrer que sa complexité est en $O (lo g n)$ .
Q3. Exhiber une bijection entre $[[0, 2^{n} - 1]]$ et $Σ_{n}$ .
Q4. Écrire decompose : int -> int -> int array qui, pour $x \in [[0, 2^{n} - 1]]$ , renvoie la lettre de $Σ_{n}$ associée à $x$ par cette bijection, en vérifiant l'entrée par une assertion.

Corrigé

Q1. C'est l'exponentiation rapide : $2^{n} = (2^{⌊ n /2 ⌋})^{2}$ si $n$ est pair et $2^{n} = 2 (2^{⌊ n /2 ⌋})^{2}$ si $n$ est impair.


let rec pow2 n =
  if n = 0 then 1
  else
    let p = pow2 (n / 2) in
    if n mod 2 = 0 then p * p else 2 * p * p

Correction, par récurrence forte sur $n$ : pow2 0 vaut $1 = 2^{0}$ ; pour $n ⩾ 1$ , $⌊ n /2 ⌋ < n$ donc p vaut $2^{⌊ n /2 ⌋}$ par hypothèse de récurrence, et $n = 2 ⌊ n /2 ⌋ + (n mod 2)$ donne $2^{n} = p^{2}$ ou $2 p^{2}$ . Terminaison : l'argument, entier naturel, décroît strictement à chaque appel. Exécutée : pow2 10 = 1024, et pow2 n = 1 lsl n pour tout $n \in [[0, 61]]$ .

Ce que le correcteur attend : un seul appel récursif, dont le résultat est nommé (p). Écrire pow2 (n/2) * pow2 (n/2) fait deux appels par étage : $C (n) = 2 C (n /2) + O (1)$ , soit une complexité linéaire, ce que le jury a relevé dans de nombreuses copies.

Q2. On compte les opérations arithmétiques en temps constant (hypothèse de l'énoncé : les entiers sont non bornés, on ne compte pas leur taille). Chaque appel fait, hors appel récursif, un nombre borné d'opérations (un test, une division, un reste, au plus deux multiplications) : coût $O (1)$ . Il suffit donc de compter les appels.

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →