Corrigé X-ENS 2026 Informatique B MP-PC-PSI — Partie II (Q8 à Q14) : Forme normale et unification

Sujet officiel du concours X-ENS, session 2026, épreuve Informatique B MP-PC-PSI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Graphe $G$ de la partie I, avec de plus (A5) : degré sortant au plus 2. Un sommet de degré 0 est libre, de degré 1 lié, de degré 2 interne. Pour $s$ lié, $s^{*}$ est la cible de son arc sortant ; pour $s$ interne, $s_{0}$ et $s_{1}$ sont les cibles de ses arcs étiquetés 0 et 1. Figure 1 :


G = {'a': ['c', 'd'], 'b': ['d', 'c'], 'c': ['X', 'Y'], 'd': ['Y', 'X'],
     'e': ['W', 'Z'], 'W': ['Z'], 'X': [], 'Y': [], 'Z': []}

La forme normale est définie par $fn (s) = s$ si $s$ est libre, $fn (s^{*})$ si $s$ est lié, $(fn (s_{0}), fn (s_{1}))$ si $s$ est interne ; sur l'exemple, $fn (a) = ((X, Y), (Y, X))$ et $fn (e) = (Z, Z)$ . Code du sujet :


def fn(s):
    if len(G[s]) == 0:      # sommet libre
        return s
    elif len(G[s]) == 1:    # sommet lié
        return fn(G[s][0])
    else:                   # sommet interne
        return (fn(G[s][0]), fn(G[s][1]))

$T (s)$ désigne le nombre de chemins partant de $s$ et aboutissant à un sommet libre ( $T (a) = 4$ , $T (W) = 1$ ). Une extension de $G$ est un graphe acyclique obtenu en ajoutant à certains sommets libres un arc sortant étiqueté 0. Un problème d'unification $P$ est un ensemble de paires de sommets ; une solution est une extension où $fn (s) = fn (t)$ pour tout $(s, t) \in P$ (ainsi ${(a, b)}$ est résolu par l'ajout de $X \to Y$ ). Pour $(s, t) \in P$ et $P^{'} = P ∖ {(s, t)}$ , on admet : (T1) $P^{'} \cup {(t, s)}$ a les mêmes solutions que $P$ ; (T2) si $s$ est lié, $P^{'} \cup {(s^{*}, t)}$ aussi ; (T3) si $s$ et $t$ sont internes, $P^{'} \cup {(s_{0}, t_{0}), (s_{1}, t_{1})}$ aussi ; (T4) si $s$ est libre, $t$ non lié et $s \neq = t$ , alors $P$ a une solution si et seulement si $P^{'}$ a une solution contenant l'arc $s \to t$ . unif(P) (figure 4) doit renvoyer True si et seulement si $P$ (liste de paires) a une solution, en ajoutant alors à G les arcs d'une solution :


def unif(P):
    while len(P) > 0:
        s, t = P.pop()
        if len(G[s]) == 1:
            P.append((G[s][0], t))
        elif len(G[t]) == 1:
            P.append((s, G[t][0]))
        elif len(G[s]) == 2 and len(G[t]) == 2:
            P.append((G[s][0], G[t][0]))
            P.append((G[s][1], G[t][1]))
        elif len(G[s]) == 0:
            ...  # à compléter
        else:
            P.append((t, s))
    return True

Q8. Sommets internes, liés, libres de la figure 1 ?
Q9. Prouver la terminaison de fn par une quantité $N (s)$ strictement décroissante.
Q10. Montrer que la complexité de fn dans le pire cas est au moins exponentielle en le nombre de sommets.
Q11. Écrire fn_efficace(s), même résultat que fn(s), en complexité linéaire en le nombre de sommets.
Q12. Écrire taille(s) qui renvoie $T (s)$ .
Q13. Montrer que ${(c, X)}$ n'a pas de solution (figure 1).
Q14. Compléter unif ; on peut utiliser lier(u, s) (partie I), qui ajoute l'arc $u \to s$ si et seulement si cet ajout ne crée pas de cycle.

Corrigé

Q8. Les sommets internes (deux successeurs) sont $a, b, c, d, e$ ; le seul sommet lié est $W$ (avec $W^{*} = Z$ ) ; les sommets libres sont $X$ , $Y$ et $Z$ .

Q9. Posons $N (s)$ la longueur maximale d'un chemin issu de $s$ . Elle est bien définie : $G$ étant acyclique, un chemin ne repasse jamais par un sommet (sinon la portion entre deux passages serait un cycle), donc sa longueur est au plus $n - 1$ où $n$ est le nombre de sommets ; $N (s) \in N$ . Les appels récursifs de fn(s) portent sur G[s][0] et G[s][1], c'est-à-dire sur des successeurs $t$ de $s$ . Or, pour tout arc $s \to t$ , faire précéder un chemin maximal issu de $t$ de l'arc $s \to t$ donne un chemin issu de $s$ , d'où $N (s) ⩾ N (t) + 1 > N (t)$ . La profondeur de la récursion est donc au plus $N (s) + 1 ⩽ n$ ; chaque appel en faisant au plus deux, l'arbre des appels est fini : fn termine. ( $N (s) = 0$ exactement pour $s$ libre, cas de base sans appel.)

Q10. Le temps de calcul est au moins proportionnel au nombre d'appels de fn. Construisons, pour $k \in N$ , le graphe $G_{k}$ à $n = 2 k + 1$ sommets $v_{0}, v_{1}, \dots, v_{k}$ et $w_{0}, \dots, w_{k - 1}$ , avec $v_{0}$ libre, $w_{i}$ lié à $v_{i}$ , et $v_{i}$ interne de successeurs $v_{i - 1}$ (étiquette 0) et $w_{i - 1}$ (étiquette 1) pour $1 ⩽ i ⩽ k$ : c'est le motif $e, W, Z$ de la figure 1 empilé $k$ fois. Il est acyclique (les arcs font décroître les indices ou vont de $w_{i}$ à $v_{i}$ ), de degré au plus 2.


def graphe_pire(k):
    H = {'v0': []}
    for i in range(1, k + 1):
        H['w' + str(i - 1)] = ['v' + str(i - 1)]
        H['v' + str(i)] = ['v' + str(i - 1), 'w' + str(i - 1)]
    return H

Soit $C (i)$ le nombre d'appels déclenchés par fn $(v_{i})$ (lui compris). On a $C (0) = 1$ , et fn $(v_{i})$ appelle fn $(v_{i - 1})$ et fn $(w_{i - 1})$ , lequel appelle fn $(v_{i - 1})$ : $C (i) = 1 + C (i - 1) + 1 + C (i - 1) = 2 C (i - 1) + 2$ . Donc $C (i) + 2 = 2 (C (i - 1) + 2)$ , puis $C (k) = 3 \cdot 2^{k} - 2 ⩾ 2^{k} = 2^{(n - 1) /2}$ . Le sous-calcul de $fn (v_{i - 1})$ est refait deux fois à chaque étage, et ces doublements se composent. La complexité de fn sur $G_{k}$ est donc $Ω ((2)^{n})$ : au moins exponentielle en $n$ . Le décompte $C (k) = 3 \cdot 2^{k} - 2$ a été vérifié en exécution pour $k ⩽ 10$ avec une version instrumentée de fn. (Si l'on admet deux arcs parallèles, $v_{i}$ de successeurs $v_{i - 1}, v_{i - 1}$ donne même $2^{n} - 1$ appels pour $n$ sommets.)

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 →