Corrigé Mines-Ponts 2026 Informatique I MPI — Partie 1 (Q1 à Q3) : Puissance rapide et écriture binaire des lettres

Sujet officiel du concours Mines-Ponts, session 2026, épreuve Informatique I MPI. 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)$ .
Q2. Exhiber une bijection entre $[[0, 2^{n} - 1]]$ et $Σ_{n}$ .
Q3. É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.

Complexité. Les entiers étant supposés non bornés, chaque opération arithmétique compte pour $O (1)$ ; un appel fait, hors appel récursif, un nombre borné d'opérations (un test, une division, un reste, au plus deux multiplications). Soit $A (n)$ le nombre d'appels déclenchés par pow2 n : $A (0) = 1$ et $A (n) = 1 + A (⌊ n /2 ⌋)$ pour $n ⩾ 1$ . Par récurrence forte, $A (n) = ⌊ lo g_{2} n ⌋ + 2$ pour $n ⩾ 1$ : $A (1) = 2$ , et pour $n ⩾ 2$ , si $2^{b} ⩽ n < 2^{b + 1}$ alors $2^{b - 1} ⩽ ⌊ n /2 ⌋ < 2^{b}$ , d'où $A (n) = 1 + (b - 1) + 2 = b + 2$ . Chaque appel efface un bit de l'écriture binaire de $n$ : le coût total est $O (lo g n)$ . Exécutée : pow2 10 = 1024, et pow2 n = 1 lsl n pour tout $n \in [[0, 61]]$ .

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 →