Corrigé X-ENS 2026 Informatique C MPI — Partie IV (2) (Q20 à Q24) : Ordres induits et mise en veille

Sujet officiel du concours X-ENS, session 2026, épreuve Informatique C MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

On reprend l'indépendance $α \leftrightarrow β$ (Q16) ; $α \neq \leftrightarrow β$ note sa négation. L'équivalence par permutation $\sim$ est la plus petite relation d'équivalence sur $A^{*}$ telle que $uα β v \sim u β α v$ dès que $α \leftrightarrow β$ ; si $u \sim v$ et $s u s^{'}$ , alors $s v s^{'}$ . $A^{\neq =}$ est l'ensemble des mots sans lettre répétée. Pour $u \in A^{\neq =}$ de longueur $n$ , l'ordre induit $<_{u}$ est la plus petite relation transitive sur les lettres de $u$ telle que $u_{i} <_{u} u_{j}$ dès que $i < j$ et $u_{i} \neq \leftrightarrow u_{j}$ .
Q20. a. Si $β \neq \leftrightarrow α$ , $β \neq \leftrightarrow γ$ , $α \leftrightarrow γ$ : ordres induits de $α β γ$ , $α γ β$ , $γ α β$ . b. Si seuls $α \neq \leftrightarrow β$ et $α^{'} \neq \leftrightarrow β^{'}$ : ordres induits de $α α^{'} β β^{'}$ , $α β α^{'} β^{'}$ , $β α α^{'} β^{'}$ .
Q21. Pour $u, v \in A^{\neq =}$ de même longueur et mêmes lettres : $u \sim v$ si et seulement si $<_{u}$ et $<_{v}$ coïncident.

Mise en veille : pour un ordre total $<$ sur $A$ , $T^{<} = (S \times 2^{A}, A, D^{<}, δ^{<})$ avec $D^{<} ((s, Z)) = D (s) ∖ Z$ et $δ^{<} ((s, Z), α) = (δ (s, α), Z^{'})$ , où

$Z^{'} = {β \in Z ∣ α \leftrightarrow β} \cup {β \in D (s) ∣ α \leftrightarrow β, β < α} .$

Deux threads (figure 6 du sujet), variable globale v initialisée à $0$ :


void* thread1(void* _) {          void* thread2(void* _) {
  int a = v;                        int b = v+2;
  v = a+1;                          v = 3*b;
  return NULL;                      return NULL;
}                                 }

Q22. $A = {t_{1}^{1}, t_{1}^{2}, t_{2}^{1}, t_{2}^{2}}$ ( $t_{i}^{j}$ : $j$ -ième instruction du thread $i$ ), $s_{0}$ l'état initial. a. Dessiner $T$ (actions, variables définies). b. Pour $t_{1}^{1} < t_{1}^{2} < t_{2}^{1} < t_{2}^{2}$ , dessiner la partie de $T^{<}$ accessible depuis $(s_{0}, \emptyset)$ .

On munit $A^{\neq =}$ de l'ordre lexicographique $<$ ; $u^{<}$ est le plus petit mot de la classe de $u$ pour $\sim$ .
Q23. $u = u^{<}$ si et seulement si $u$ ne s'écrit pas $u_{1} β u_{2} α u_{3}$ avec $α < β$ et $α \leftrightarrow β u_{2}$ .
Q24. Pour $u \in A^{\neq =}$ : a. si $(s, Z) u (s^{'}, Z^{'})$ dans $T^{<}$ , alors $u = u^{<}$ ; b. si $s u s^{'}$ dans $T$ , il existe $Z$ tel que $(s, \emptyset) u^{<} (s^{'}, Z)$ dans $T^{<}$ .

Corrigé

Deux remarques utiles. (R1) La relation « se déduire de $u$ par une suite finie d'échanges de deux lettres adjacentes indépendantes » est une relation d'équivalence (réflexive, symétrique car un échange se défait, transitive par concaténation des suites) qui vérifie la propriété demandée ; elle est contenue dans toute relation d'équivalence qui la vérifie. C'est donc $\sim$ . En particulier $\sim$ conserve la longueur, les lettres et l'appartenance à $A^{\neq =}$ , et $u \sim v$ entraîne $xu y \sim xv y$ . (R2) Chaque couple générateur $u_{i} <_{u} u_{j}$ vérifie $i < j$ ; par transitivité, si $x <_{u} y$ , alors $x$ est avant $y$ dans $u$ : $<_{u}$ est un ordre strict, et rien n'est $<_{u}$ plus petit que la première lettre de $u$ .

Q20. a. On liste les couples de positions $i < j$ dont les lettres sont dépendantes, puis on clôt par transitivité.

$u = α β γ$ : $α <_{u} β$ , $β <_{u} γ$ , puis $α <_{u} γ$ par transitivité ( $α, γ$ sont pourtant indépendantes) : l'ordre total $α <_{u} β <_{u} γ$ .
$v = α γ β$ : $α <_{v} β$ et $γ <_{v} β$ ; $α$ et $γ$ sont incomparables.
$w = γ α β$ : $γ <_{w} β$ et $α <_{w} β$ : le même ordre que $<_{v}$ .

C'est cohérent avec Q21 : $v \sim w$ (échange de $α γ$ ), alors que $u$ , dont $β$ sépare $α$ et $γ$ , n'est équivalent à aucun des deux.

b. Seuls les couples ${α, β}$ et ${α^{'}, β^{'}}$ comptent.

$u = α α^{'} β β^{'}$ : $α <_{u} β$ et $α^{'} <_{u} β^{'}$ , rien d'autre (aucune chaîne à clore).
$v = α β α^{'} β^{'}$ : $α <_{v} β$ et $α^{'} <_{v} β^{'}$ : le même ordre que $<_{u}$ .
$w = β α α^{'} β^{'}$ : $β <_{w} α$ et $α^{'} <_{w} β^{'}$ .

Donc $u \sim v$ ( $α^{'} \leftrightarrow β$ : on les échange) mais $w \neq \sim u$ . Exécuté : la clôture transitive programmée redonne ces cinq ordres.

Q21. ( $\Rightarrow$ ) Par (R1), il suffit de voir qu'un échange préserve l'ordre induit. Soit $u = xα β y$ et $u^{'} = x β α y$ avec $α \leftrightarrow β$ . Notons $G_{u}$ l'ensemble des couples générateurs $(u_{i}, u_{j})$ , $i < j$ , $u_{i} \neq \leftrightarrow u_{j}$ . Les lettres étant distinctes, l'ordre relatif de deux lettres est le même dans $u$ et $u^{'}$ , sauf pour $α$ et $β$ , qui sont indépendantes et n'engendrent de couple ni dans $u$ ni dans $u^{'}$ : $G_{u} = G_{u^{'}}$ , donc $<_{u} = <_{u^{'}}$ (même clôture transitive).

( $\Leftarrow$ ) Récurrence sur $n$ ; le cas $n = 0$ est trivial. Soit $a = v_{0}$ , et $k$ la position de $a$ dans $u$ : $u = u_{0} \dots u_{k - 1} a u_{k + 1} \dots u_{n - 1}$ . Pour $i < k$ , si $u_{i} \neq \leftrightarrow a$ , alors $u_{i} <_{u} a$ , donc $u_{i} <_{v} a$ , ce que (R2) interdit puisque $a$ est la première lettre de $v$ . Donc $a \leftrightarrow u_{i}$ pour tout $i < k$ , et $k$ échanges successifs font passer $a$ en tête : $u \sim a u ~$ , où $u ~$ est $u$ privé de $a$ . Écrivons $v = a v^{'}$ .

Lemme : pour un mot $a w$ , l'ordre $<_{w}$ est la restriction de $<_{a w}$ aux lettres de $w$ . En effet $G_{a w} = G_{w} \cup {(a, y) ∣ y \neq \leftrightarrow a}$ , et une chaîne de $G_{a w}$ entre deux lettres de $w$ ne passe jamais par $a$ , qui n'a aucun prédécesseur.

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 →