Informatique B
X-ENSMP2026
Rédigé par IA, non vérifié
Signaler une erreur# X-ENS MP-PC-PSI — Informatique B 2026 · Corrigé brut
*Corrigé rédigé par IA (La Belle Copie), non officiel. Signalez toute erreur.*
Sujet : « Cycles et unification ». Durée 2 h, calculatrice interdite. Notations : $s\rightsquigarrow t$ signifie qu'il existe un chemin (éventuellement vide) de $s$ à $t$ ; on note `époque`, `sortie`, `présent`, `compteur` les variables globales de l'énoncé.
Rappel du graphe de la figure 1 (listes d'adjacence, l'étiquette d'un arc est son indice) :
```text
a : [c, d] b : [d, c] c : [X, Y] d : [Y, X]
e : [W, Z] W : [Z] X : [] Y : [] Z : []
```
## Partie I. Détection de cycles
### Question 1
Avec `présent = 1`, `compteur = 0`, `pp('a')` visite $a$, puis $c$, $X$ (sortie 0), $Y$ (sortie 1), termine $c$ (sortie 2), visite $d$ dont les deux cibles $Y$ et $X$ portent déjà l'époque 1, termine $d$ (sortie 3), puis $a$ (sortie 4). Les sommets $b,e,W,Z$ ne sont pas visités.
| | a | b | c | d | e | W | X | Y | Z |
|---|---|---|---|---|---|---|---|---|---|
| `époque` | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
| `sortie` | 4 | 0 | 2 | 3 | 0 | 0 | 0 | 1 | 0 |
### Question 2
Soit $p$ la valeur de `présent` avant l'incrémentation. On est hors de `pp`, donc A2 est vrai : $\texttt{époque}[t]\le p$ pour tout sommet $t$. Après l'incrémentation, `présent` vaut $p+1$, et l'incrémentation ne modifie pas `époque`. Donc
$$\texttt{époque}[t]\le p<p+1=\texttt{présent},$$
d'où **$\texttt{époque}[t]\neq\texttt{présent}$ pour tout sommet $t$**.
### Question 3
Soit $p+1$ la valeur de `présent` après la ligne 1. Pendant `pp(s)`, `présent` n'est pas modifié. Une époque n'est modifiée qu'à la ligne 16, et elle reçoit alors la valeur `présent`, sur un sommet visité, c'est-à-dire un sommet sur lequel `pp` est appelée.
*Sens indirect.* On suppose $\texttt{époque}[t]=\texttt{présent}$ après l'appel. D'après Q2, cette égalité était fausse avant l'appel, donc $t$ a été visité. Or `pp` n'est appelée récursivement que sur un successeur d'un sommet visité, en partant de $s$. Par récurrence sur l'ordre des appels, tout sommet visité est accessible depuis $s$. Donc $s\rightsquigarrow t$.
*Sens direct.* Montrons d'abord que si $x$ est visité et $x\to y$ est un arc, alors $y$ est visité. Dans `pp(x)`, la boucle examine $y$ : soit $\texttt{époque}[y]=\texttt{présent}$, et $y$ a déjà été visité pendant l'appel (Q2), soit `pp(y)` est appelée. Soit alors un chemin $s=x_0\to x_1\to\dots\to x_k=t$. Le sommet $x_0$ est visité, puis chaque $x_{i+1}$ l'est par récurrence. Donc $t$ est visité et reçoit l'époque `présent`, qui n'est ensuite plus modifiée.
$$\boxed{\ s\rightsquigarrow t\iff \texttt{époque}[t]=\texttt{présent}\ \text{après l'exécution}\ }$$
### Question 4
On se place, comme dans `accessible`, juste après `présent += 1`. D'après Q2, au début de `pp(s)` aucun sommet ne porte l'époque courante. Comme $s\rightsquigarrow u$, le sommet $u$ est visité (Q3), donc `pp(u)` s'exécute une fois. La valeur de `compteur` croît strictement à chaque affectation de `sortie`. Considérons l'instant où la boucle de `pp(u)` examine $t=v$.
- Si $\texttt{époque}[v]\neq\texttt{présent}$, alors `pp(v)` est appelée. Elle se termine, en affectant `sortie[v]`, avant que `pp(u)` n'affecte `sortie[u]` après sa boucle. Donc $\texttt{sortie}[v]<\texttt{sortie}[u]$.
- Si $\texttt{époque}[v]=\texttt{présent}$, alors `pp(v)` a déjà commencé pendant cet appel. Supposons que `pp(v)` ne soit pas terminée. Alors `pp(u)` a été appelée, directement ou non, depuis `pp(v)`. La pile d'appels fournit un chemin $v\rightsquigarrow u$, qui forme un cycle avec l'arc $u\to v$, ce qu'exclut A1. Donc `pp(v)` est terminée, et `sortie[v]` a reçu une valeur de `compteur` strictement inférieure à celle que recevra `sortie[u]`.
Dans les deux cas, $\boxed{\texttt{sortie}[u]>\texttt{sortie}[v]}$, donc a fortiori $\texttt{sortie}[u]\ge\texttt{sortie}[v]$.
### Question 5
**Le test des lignes 5–6 n'élimine jamais à tort.** On suppose $s\rightsquigarrow t$ par un chemin $s=x_0\to\dots\to x_k=t$. Par A3 appliqué à chaque arc, $\texttt{époque}[x_0]\le\dots\le\texttt{époque}[x_k]$, donc $\texttt{époque}[s]\le\texttt{époque}[t]$. Si de plus $\texttt{époque}[s]=\texttt{époque}[t]$, la suite croissante a des extrémités égales, donc elle est constante. A4 s'applique alors à chaque arc du chemin : $\texttt{sortie}[x_0]\ge\dots\ge\texttt{sortie}[x_k]$, donc $\texttt{sortie}[s]\ge\texttt{sortie}[t]$. La condition des lignes 5–6 est donc fausse. Pour $t=s$, cela couvre le chemin vide.
**Conclusion.**
- Si $s\rightsquigarrow t$, on exécute `présent += 1` puis `pp(s)`. Pour $t\neq s$, Q3 donne $\texttt{époque}[t]=\texttt{présent}$. Pour $t=s$, la ligne 16 l'impose. La fonction renvoie `True`.
- Si $s\not\rightsquigarrow t$, alors $t\neq s$. Soit le test renvoie `False`, soit `pp(s)` s'exécute, et Q3 donne $\texttt{époque}[t]\neq\texttt{présent}$ : la fonction renvoie `False`.
**`accessible(s, t)` renvoie `True` si et seulement si $s\rightsquigarrow t$.**
### Question 6
On suppose A1–A4 vrais à l'appel. Si la fonction sort ligne 7, rien n'est modifié. Sinon, soit $p$ la valeur de `présent` avant la ligne 9. Après `pp(s)`, on note $V$ l'ensemble des sommets visités. D'après Q3, $V=\{x : s\rightsquigarrow x\}$, et ce sont exactement les sommets d'époque $p+1$. Les sommets hors de $V$ gardent leurs `époque` et `sortie` inchangées, et leur époque reste $\le p$ (A2 avant l'appel). Enfin, $V$ est stable par les arcs : si $x\in V$ et $x\to y$, alors $y\in V$.
- **A2.** Si $x\in V$, $\texttt{époque}[x]=p+1=\texttt{présent}$. Sinon, $\texttt{époque}[x]\le p<\texttt{présent}$.
- **A3.** Soit un arc $x\to y$. Si $x\in V$, alors $y\in V$, et les deux époques valent $p+1$. Si $x\notin V$ et $y\in V$, alors $\texttt{époque}[x]\le p<p+1=\texttt{époque}[y]$. Si $x,y\notin V$, rien n'a changé et A3 valait avant.
- **A4.** Soit un arc $x\to y$ dont les deux extrémités ont la même époque. Un sommet de $V$ et un sommet hors de $V$ ont des époques différentes, donc $x$ et $y$ sont tous deux dans $V$ ou tous deux hors de $V$. S'ils sont dans $V$, on a $s\rightsquigarrow x$, et Q4 donne $\texttt{sortie}[x]\ge\texttt{sortie}[y]$. Sinon, rien n'a changé et A4 valait avant.
`accessible` n'ajoute aucun arc. **A2, A3 et A4 sont préservés.**
### Question 7
`lier(u, s)` appelle `accessible(s, u)`, qui préserve A2–A4 (Q6) sans modifier le graphe. Si le résultat est `True`, rien d'autre n'est fait. Sinon, $s\not\rightsquigarrow u$ (Q5) et l'on ajoute l'arc $u\to s$. Il reste à étudier ce cas.
- **A1.** Le graphe était acyclique. Un cycle du nouveau graphe emprunterait donc l'arc $u\to s$ et se refermerait par un chemin $s\rightsquigarrow u$ de l'ancien graphe, ce qui est impossible. En particulier $u\neq s$, car `accessible(s, s)` renvoie `True`.
- **A2.** L'ajout d'un arc ne modifie ni `époque` ni `présent`.
- **A3, A4.** Les arcs anciens vérifient A3–A4 (Q6), et `époque`/`sortie` ne changent plus. Il suffit d'étudier le nouvel arc $u\to s$, selon la branche qui a renvoyé `False` :
- sortie ligne 7 avec $\texttt{époque}[s]>\texttt{époque}[u]$ : A3 est strict pour $u\to s$, et A4 est vide ;
- sortie ligne 7 avec $\texttt{époque}[s]=\texttt{époque}[u]$ et $\texttt{sortie}[s]<\texttt{sortie}[u]$ : A3 tient (égalité), et A4 tient puisque $\texttt{sortie}[u]>\texttt{sortie}[s]$ ;
- sortie ligne 12 : `pp(s)` a posé $\texttt{époque}[s]=\texttt{présent}$, et $\texttt{époque}[u]\neq\texttt{présent}$. Comme $\texttt{époque}[u]\le\texttt{présent}$ par A2, on a $\texttt{époque}[u]<\texttt{époque}[s]$ : A3 est strict, et A4 est vide.
**`lier(u, s)` préserve A1, A2, A3 et A4.**
## Partie II. Unification
### Question 8
D'après les longueurs des listes :
- **sommets internes** (degré 2) : $a,b,c,d,e$ ;
- **sommet lié** (degré 1) : $W$ ;
- **sommets libres** (degré 0) : $X,Y,Z$.
### Question 9
On pose $N(s)$ = longueur, en nombre d'arcs, du plus long chemin issu de $s$. Elle est bien définie : $G$ est fini et acyclique (A1), donc un chemin ne repasse jamais par un sommet et a au plus $|S|-1$ arcs. Pour tout arc $s\to t$, on prolonge un plus long chemin issu de $t$ par l'arc $s\to t$, d'où $N(s)\ge 1+N(t)>N(t)$. Les appels récursifs de `fn(s)` portent sur $s^*$, $s_0$ ou $s_1$, qui sont des cibles d'arcs issus de $s$. Donc $N$, entier naturel, décroît strictement à chaque appel récursif, et **`fn` termine**.
### Question 10
On note $C(s)$ le nombre d'appels à `fn` déclenchés par `fn(s)`, cet appel compris. On a $C(s)=1$ si $s$ est libre, $C(s)=1+C(s^*)$ si $s$ est lié, et $C(s)=1+C(s_0)+C(s_1)$ si $s$ est interne.
Pour $m\ge 0$, on considère le graphe à $n=2(m+1)$ sommets $x_0,y_0,\dots,x_m,y_m$, avec $x_0,y_0$ libres et, pour $1\le i\le m$ :
```text
x_i : [x_{i-1}, y_{i-1}] y_i : [y_{i-1}, x_{i-1}]
```
Ce graphe est acyclique (les arcs vont de l'étage $i$ à l'étage $i-1$), de degré sortant au plus 2, et sans arc multiple. Par symétrie, $C(x_i)=C(y_i)=:c_i$, avec $c_0=1$ et $c_i=1+2c_{i-1}$. Comme $c_i+1=2(c_{i-1}+1)$, on obtient $c_m=2^{m+1}-1$. Donc
$$\boxed{C(x_m)=2^{n/2}-1}$$
Chaque appel coûte au moins une opération élémentaire. **La complexité dans le pire cas de `fn` est donc au moins exponentielle en le nombre de sommets.**
Si l'on accepte des arcs parallèles (`G[s_i] = [s_{i-1}, s_{i-1}]`), une simple chaîne donne même $2^n-1$ appels pour $n$ sommets.
### Question 11
On mémoïse le résultat par sommet dans un dictionnaire :
```python
def fn_efficace(s):
memo = {}
def aux(x):
if x not in memo:
if len(G[x]) == 0: # libre
memo[x] = x
elif len(G[x]) == 1: # lié
memo[x] = aux(G[x][0])
else: # interne
memo[x] = (aux(G[x][0]), aux(G[x][1]))
return memo[x]
return aux(s)
```
*Correction.* `aux` suit exactement la définition de $\mathrm{fn}$. La valeur mémorisée pour $x$ est $\mathrm{fn}(x)$, et elle termine par Q9.
*Complexité.* Le corps principal de `aux(x)` (calcul et affectation de `memo[x]`) s'exécute au plus une fois par sommet. Hors appels récursifs, il coûte $O(1)$ : tests, accès au dictionnaire, construction d'un couple. Un couple ne contient que deux références vers des valeurs déjà construites : les sous-termes sont **partagés** et ne sont pas recopiés. Le nombre total d'appels à `aux` est au plus $1+2|S|$, car chaque exécution du corps lance au plus deux appels. **La complexité est $O(|S|)$.**
### Question 12
$T(s)=1$ si $s$ est libre, car le seul chemin est le chemin vide. Sinon, un chemin issu de $s$ qui aboutit à un sommet libre commence par l'un des arcs sortants de $s$, ce qui donne une partition : $T(s)=\sum_{s\to t}T(t)$. La récursion termine par Q9. On mémoïse pour obtenir un coût linéaire :
```python
def taille(s):
memo = {}
def aux(x):
if x not in memo:
if len(G[x]) == 0:
memo[x] = 1
else:
total = 0
for y in G[x]:
total = total + aux(y)
memo[x] = total
return memo[x]
return aux(s)
```
Vérification sur la figure 1 : $T(a)=T(c)+T(d)=2+2=4$ et $T(W)=T(Z)=1$. **Complexité $O(|S|)$** grâce à la mémoïsation. Sans elle, le coût serait exponentiel sur l'exemple de Q10.
### Question 13
Soit $H$ une extension de $G$. Une extension n'ajoute d'arcs qu'aux sommets libres, donc $c$ reste interne dans $H$, avec $c_0=X$ et $c_1=Y$ :
$$\mathrm{fn}_H(c)=\big(\mathrm{fn}_H(X),\ \mathrm{fn}_H(Y)\big).$$
On définit la taille d'une forme normale par $|v|=1$ pour un sommet et $|(\alpha,\beta)|=1+|\alpha|+|\beta|$. Les formes normales sont finies par Q9. On a donc
$$|\mathrm{fn}_H(c)|=1+|\mathrm{fn}_H(X)|+|\mathrm{fn}_H(Y)|>|\mathrm{fn}_H(X)|.$$
Ainsi $\mathrm{fn}_H(c)\neq\mathrm{fn}_H(X)$, quelle que soit l'extension $H$, que $X$ y reste libre ou y devienne lié. **Le problème $\{(c,X)\}$ n'a pas de solution.**
### Question 14
Ligne 17, on complète par :
```python
elif len(G[s]) == 0:
if s != t and not lier(s, t):
return False
```
*Justification.* Cette branche n'est atteinte que si $s$ est libre et $t$ n'est pas lié, c'est-à-dire $t$ libre ou interne. Les cas « $t$ lié » et « $s,t$ internes » sont traités avant, et la branche `else` ramène le cas « $s$ interne, $t$ libre » à celui-ci par T1.
- Si $s=t$, la paire est satisfaite par toute extension. On la retire simplement de $P$. Le test `s != t` est indispensable : `lier(s, s)` renverrait `False`, puisque $s\rightsquigarrow s$.
- Si $s\neq t$, on est dans les hypothèses de T4 : $P$ a une solution si et seulement si $P'$ en a une qui contient l'arc $s\to t$. Une extension est acyclique et contient $G$. Si $t\rightsquigarrow s$, aucune extension ne contient $s\to t$, et `lier(s, t)` renvoie `False` (partie I) : $P$ n'a pas de solution. Sinon, `lier` ajoute l'arc $s\to t$, étiqueté 0 puisque $s$ était libre. Le nouveau $G$ est une extension, et l'on poursuit avec $P'$, déjà privé de $(s,t)$ par `P.pop()`.
### Question 15
On renvoie les arcs qui violent A3 ou A4. Les deux invariants sont vérifiés si et seulement si le résultat est vide.
```sql
SELECT a.source, a.cible
FROM arcs AS a
JOIN sommets AS s ON s.id = a.source
JOIN sommets AS t ON t.id = a.cible
WHERE s.époque > t.époque
OR (s.époque = t.époque AND s.sortie < t.sortie);
```
La violation de A3 s'écrit $\texttt{époque}[s]>\texttt{époque}[t]$. La négation de l'implication A4 s'écrit $\texttt{époque}[s]=\texttt{époque}[t]$ et $\texttt{sortie}[s]<\texttt{sortie}[t]$. On peut aussi remplacer la première ligne par `SELECT COUNT(*)`, qui doit valoir 0.
### Question 16
**Lemme.** Il existe deux sommets $s\neq t$ tels que $\mathrm{fn}(s)=\mathrm{fn}(t)$ si et seulement si (i) $G$ a un sommet lié, ou (ii) deux sommets internes distincts ont les mêmes fils : $s_0=t_0$ et $s_1=t_1$.
*Preuve.* Si $s$ est lié, alors $\mathrm{fn}(s)=\mathrm{fn}(s^*)$, et $s\neq s^*$ par acyclicité. Si $s,t$ sont internes et ont les mêmes fils, alors $\mathrm{fn}(s)=(\mathrm{fn}(s_0),\mathrm{fn}(s_1))=\mathrm{fn}(t)$.
Réciproquement, on suppose qu'aucun sommet n'est lié et qu'il existe des paires $s\neq t$ avec $\mathrm{fn}(s)=\mathrm{fn}(t)$. On en choisit une qui minimise $N(s)$ (Q9). La forme normale d'un sommet libre est un sommet, celle d'un sommet interne est un couple. Si $s$ ou $t$ est libre, les deux le sont, et $s=\mathrm{fn}(s)=\mathrm{fn}(t)=t$, ce qui est exclu. Les deux sommets sont donc internes, avec $\mathrm{fn}(s_0)=\mathrm{fn}(t_0)$ et $\mathrm{fn}(s_1)=\mathrm{fn}(t_1)$. Si $s_0\neq t_0$, la paire $(s_0,t_0)$ conviendrait avec $N(s_0)<N(s)$, ce qui contredit la minimalité. Donc $s_0=t_0$, et de même $s_1=t_1$ : on est dans le cas (ii). $\square$
La requête suivante renvoie une telle paire, ou un résultat vide s'il n'en existe pas :
```sql
SELECT a.source, a.cible -- (i) un sommet lié et sa cible
FROM arcs AS a
JOIN sommets AS s ON s.id = a.source
WHERE s.degré = 1
UNION
SELECT a0.source, b0.source -- (ii) deux internes de mêmes fils
FROM arcs AS a0
JOIN arcs AS b0 ON b0.cible = a0.cible AND b0.étiquette = 0
JOIN arcs AS a1 ON a1.source = a0.source AND a1.étiquette = 1
JOIN arcs AS b1 ON b1.source = b0.source AND b1.étiquette = 1
AND b1.cible = a1.cible
WHERE a0.étiquette = 0 AND a0.source < b0.source
LIMIT 1;
```
La présence d'un arc d'étiquette 1 garantit que les sommets de la seconde partie sont internes. La condition `a0.source < b0.source` impose $s\neq t$. Dans la première partie, $s\neq s^*$ par acyclicité. **Toute ligne renvoyée vérifie $s\neq t$ et $\mathrm{fn}(s)=\mathrm{fn}(t)$, et le lemme garantit qu'une ligne est renvoyée dès qu'une telle paire existe.** Sur la figure 1, la requête renvoie $(W,Z)$.
Aide sur le corrigé
Connectez-vous pour demander une explication.