Corrigé CCINP 2026 Informatique MPI — Partie II (II.1) (Q23 à Q29) : Suite de Prouhet-Thue-Morse : quatre définitions équivalentes

Sujet officiel du concours CCINP, session 2026, épreuve Informatique MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

$Σ = {0, 1}$ , $ε$ le mot vide, $∣ m ∣$ la longueur, « . » la concaténation, $m ˉ$ le mot $m$ où l'on échange $0$ et $1$ . On note $t_{n}$ le $n$ -ième terme de la suite PTM et $T_{n} = t_{0} t_{1} \dots t_{2^{n} - 1}$ (ses $2^{n}$ premiers termes). Langage imposé : OCaml.

Définition 1. Si $n = \sum_{i} d_{i} 2^{i}$ en base 2 et $b_{n} = \sum_{i} d_{i}$ , alors $t_{0} = 0$ et, pour $n > 0$ , $t_{n} = 1$ si $b_{n}$ est impair, $0$ sinon.
Q23. Donner $T_{3}$ .
Q24. Écrire une fonction récursive compte_bits_a_un : int -> int (nombre de bits à $1$ de $n$ ).
Q25. En déduire affiche_ptm : int -> unit qui affiche $T_{n}$ , avec une fonction récursive puissance2 : int -> int ( $2^{n}$ ) et print_int.

Définition 2. $t_{0} = 0$ et $T_{n + 1} = T_{n} T ˉ_{n}$ , c'est-à-dire $t_{2^{n} + i} = t ˉ_{i}$ pour $i \in [[0, 2^{n} - 1]]$ .
Q26. Montrer par récurrence qu'elle donne la même suite que la définition 1.

Définition 3. $t_{0} = 0$ et, pour $n > 0$ , $t_{2 n} = t_{n}$ et $t_{2 n + 1} = t ˉ_{n}$ .
Q27. Montrer qu'elle donne la même suite que la définition 1 ou 2.

Définition 4. Un morphisme $μ$ de $Σ^{*}$ vérifie $μ (ε) = ε$ et $μ (u . v) = μ (u) . μ (v)$ ; on prend $μ (0) = 01$ , $μ (1) = 10$ , et $u_{0} = 0$ , $u_{i + 1} = μ (u_{i})$ .
Q28. Montrer que $u_{i} = T_{i}$ pour tout $i \in N^{*}$ .
Q29. Les mots sont des int list. Écrire thue_morse_4 : int -> int list ( $T_{n}$ ), à l'aide d'une fonction récursive morphisme : int list -> int list qui lève l'exception INVALID_ARGUMENT si le mot n'est pas binaire.

Corrigé

On note $par (x) = x mod 2$ . La définition 1 se résume en $t_{n} = par (b_{n})$ pour tout $n$ , y compris $n = 0$ ( $b_{0} = 0$ ).

Q23. Pour $n = 0, \dots, 7$ : $b_{n} = 0, 1, 1, 2, 1, 2, 2, 3$ , donc $t_{n} = 0, 1, 1, 0, 1, 0, 0, 1$ et

$T_{3} = 01101001.$

Q24. Le bit de poids faible de $n$ est $n mod 2$ , et les autres bits de $n$ sont ceux de $n /2$ (quotient entier).


let rec compte_bits_a_un n =
  if n = 0 then 0
  else n mod 2 + compte_bits_a_un (n / 2)

Précondition $n ⩾ 0$ . Correction par récurrence forte : si $n = \sum_{i ⩾ 0} d_{i} 2^{i}$ alors $n /2 = \sum_{i ⩾ 0} d_{i + 1} 2^{i}$ , donc $b_{n} = d_{0} + b_{n /2}$ . Terminaison : pour $n > 0$ , $0 ⩽ n /2 < n$ . Le nombre d'appels est le nombre de chiffres binaires de $n$ , soit $⌊ lo g_{2} n ⌋ + 2$ pour $n > 0$ . Exécuté : $0, 1, 3, 1, 8, 10$ pour $n = 0, 1, 7, 8, 255, 1023$ .

Q25.


let rec puissance2 n =
  if n = 0 then 1 else 2 * puissance2 (n - 1)

let affiche_ptm n =
  for i = 0 to puissance2 n - 1 do
    print_int (compte_bits_a_un i mod 2)
  done

puissance2 vérifie $2^{0} = 1$ et $2^{n} = 2 \cdot 2^{n - 1}$ (terminaison : $n ⩾ 0$ décroît strictement) ; une exponentiation rapide serait ici sans objet, le coût étant dominé par l'affichage. La boucle affiche $t_{i} = par (b_{i})$ pour $i$ de $0$ à $2^{n} - 1$ , c'est-à-dire $T_{n}$ . Coût : $2^{n}$ appels à compte_bits_a_un, chacun en $O (n)$ appels puisque $i < 2^{n}$ a au plus $n$ chiffres, soit $O (n 2^{n})$ . Exécuté : affiche_ptm 3 imprime 01101001 et affiche_ptm 0 imprime 0.

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 →