Corrigé X-ENS 2026 Informatique C MPI — Partie IV (1) (Q15 à Q19) : Indépendance et ensembles persistants

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

Énoncé

Le programme de la figure 5 (partie III, sans la correction de Q13) est modélisé par un système de transitions : un état donne m, la position $j \in {0, \dots, 4}$ de chaque thread (nombre d'instructions exécutées parmi les lignes 4 à 7) et ses variables locales définies ; l'action $t_{i}^{j}$ exécute la $j$ -ième instruction du thread $i$ , chaque instruction étant atomique. Quelques états :

$s_{0} s_{1} s^{''} = (m = - 1, t_{1} @0, t_{2} @0), s^{'} = (m = - 1, t_{1} @0, t_{2} @1 (m1 = 30)), = (m = - 1, t_{1} @2 (m1 = 10, m2 = 20), t_{2} @2 (m1 = 30, m2 = 40)), = δ (s_{1}, t_{1}^{3}) = (m = - 1, t_{1} @3 (m1 = 10, m2 = 20, m3 = 20), t_{2} @2 (m1 = 30, m2 = 40)) .$

Q15. Combien d'exécutions de longueur huit (la longueur maximale) depuis $s_{0}$ ?

Dans $T$ quelconque, deux actions $α \neq = β$ sont indépendantes ( $α \leftrightarrow β$ ) si, pour tout $s \in S$ : exécuter l'une ne change pas la disponibilité de l'autre, et si les deux sont disponibles en $s$ , $δ (δ (s, α), β) = δ (δ (s, β), α)$ :

On note $α \leftrightarrow u$ si $α \leftrightarrow u_{i}$ pour toute lettre de $u$ , et $α \leftrightarrow E$ pour un ensemble $E$ .
Q16. Figure 5 : les deux actions disponibles en $s_{0}$ sont-elles indépendantes ? En $s^{'}$ , $s_{1}$ , $s^{''}$ ?

$X \subseteq D (s_{0})$ est persistant pour $s_{0}$ si (A1) $X \neq = \emptyset$ quand $D (s_{0}) \neq = \emptyset$ , et (A2) pour toute exécution $s_{0} α_{0} \dots α_{n} s_{n + 1}$ avec tous les $α_{i} \in / X$ , on a $α_{i} \leftrightarrow X$ pour tout $i ⩽ n$ .
Q17. $X$ persistant pour $s_{0}$ , $α \in X$ , exécution comme dans (A2) : montrer que $α \in D (s_{i})$ pour tout $i ⩽ n + 1$ .
Q18. Figure 5 : un ensemble persistant minimal (pour l'inclusion) en $s_{0}$ ; en $s_{1}$ .
Q19. $X (s)$ persistant pour chaque $s$ , $s_{t}$ terminal accessible depuis $s_{0}$ : montrer qu'il existe une exécution $s_{0} α_{0} s_{1} \dots s_{n - 1} α_{n - 1} s_{t}$ ( $n ⩾ 0$ ) avec $α_{i} \in X (s_{i})$ pour tout $i < n$ .

Corrigé

Le modèle. Les états de $T$ sont les états du programme, c'est-à-dire ceux qu'il peut atteindre depuis $s_{0}$ : on en compte $28$ par énumération. (C'est la lecture imposée par le sujet : $S$ doit être fini, ce qui exclut de prendre pour états toutes les valuations entières imaginables des variables ; et les quatre états définis par le sujet sont tous accessibles depuis $s_{0}$ .) L'action $t_{i}^{j}$ est disponible exactement quand le thread $i$ est en position $j - 1$ ; elle ne modifie que la position du thread $i$ , ses variables locales, et m si $j = 4$ .

Q15. Le système est déterministe : une exécution depuis $s_{0}$ est déterminée par sa suite d'actions. Un thread n'est jamais bloqué (aucune attente dans max2) : une suite d'actions est exécutable depuis $s_{0}$ si et seulement si, pour chaque thread $i$ , les actions de ce thread qu'elle contient forment, dans l'ordre, un préfixe de $t_{i}^{1} t_{i}^{2} t_{i}^{3} t_{i}^{4}$ ( $t_{i}^{j}$ n'étant disponible qu'en position $j - 1$ ). Les exécutions de longueur huit sont donc les entrelacements de $t_{1}^{1} t_{1}^{2} t_{1}^{3} t_{1}^{4}$ et de $t_{2}^{1} t_{2}^{2} t_{2}^{3} t_{2}^{4}$ , déterminés par le choix des quatre positions (parmi huit) occupées par le thread 1 :

$(4 8) = 70 ex e ˊ cutions.$

Exécuté : l'énumération depuis $s_{0}$ trouve $70$ exécutions de longueur $8$ et aucune de longueur $9$ . Ce que le correcteur attend : on compte des exécutions, pas des états d'arrivée ; beaucoup de ces $70$ exécutions mènent au même état final.

Q16. L'indépendance est une propriété du couple d'actions, à vérifier sur tous les états $s$ de $S$ , pas seulement sur l'état cité. Pour deux actions de threads différents, les deux premières conditions sont toujours vraies : la disponibilité de $t_{i}^{j}$ ne dépend que de la position du thread $i$ , que l'autre thread ne modifie pas. Reste la commutation, sur les états où les deux sont disponibles.

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 →