Informatique B
X-ENSMP2026
Cherchez d'abord seul. En cas de blocage, ouvrez une indication, réessayez, puis seulement la solution.
Rédigé par IA, non vérifié
Signaler une erreur# X-ENS MP-PC-PSI — Informatique B 2026 · Corrigé guidé
*Corrigé rédigé par IA (La Belle Copie), non officiel. Signalez toute erreur.*
## Présentation du sujet
**Thème.** Le sujet s'intitule « Cycles et unification ». On manipule un graphe orienté acyclique $G$, codé en Python par un dictionnaire de listes d'adjacence : l'étiquette d'un arc est son indice dans la liste. Le fil conducteur est simple : on veut ajouter des arcs à $G$ sans jamais créer de cycle, puis se servir de cette opération pour résoudre des problèmes d'**unification**, c'est-à-dire rendre égales les « formes normales » de plusieurs paires de sommets.
**Format.** 2 heures, sans calculatrice, 16 questions, 8 pages. L'épreuve est commune aux filières MP, PC et PSI. Elle relève du tronc commun d'informatique : Python, parcours de graphes, terminaison, complexité, SQL.
**Découpage.**
| Partie | Questions | Contenu | Outils |
|---|---|---|---|
| I. Détection de cycles | Q1–Q7 | parcours en profondeur `pp` avec époques et numéros de sortie ; preuve de `accessible` et `lier` par invariants | DFS, invariants, récurrence le long d'un chemin |
| II. Unification | Q8–Q14 | forme normale `fn`, terminaison, explosion exponentielle, mémoïsation, comptage de chemins, algorithme `unif` | variant de terminaison, récurrences, mémoïsation |
| III. Représentation relationnelle | Q15–Q16 | vérification des invariants en SQL, recherche de deux sommets de même forme normale | jointures, `UNION`, `LIMIT` |
La partie II peut se traiter sans la partie I, à l'exception de Q14, qui utilise `lier`. La partie III ne demande que les définitions des deux premières parties.
**Notions mobilisées.** Parcours en profondeur et ordre de fin de traitement (post-ordre), invariants de boucle et de structure, variant de terminaison, complexité d'une fonction récursive (équation $c_i=1+2c_{i-1}$), mémoïsation par dictionnaire, requêtes SQL avec jointures et auto-jointures.
**Difficulté.** Les preuves de la partie I sont courtes, mais elles demandent de la rigueur : il faut dire précisément quels invariants sont vrais à quel moment, et à quelle étape sert A1. La partie II alterne des questions immédiates (Q8, Q9, Q12) et des questions plus fines (Q10 demande de construire un contre-exemple, Q13 et Q14 portent sur la sémantique de l'unification). La Q16 est la plus discriminante : la recherche naïve en SQL demande une récursion que le programme ne fournit pas, et il faut d'abord trouver une caractérisation locale.
**À ne pas laisser passer.** Q1, Q2, Q8, Q9, Q12 et Q15 sont rapides et sûres. Q11 (mémoïsation) et Q14 (trois lignes de code) rapportent beaucoup pour peu d'effort, si l'on pense au cas `s == t`.
**Gestion du temps.** Prévoir environ 50 minutes pour la partie I, 45 minutes pour la partie II et 20 minutes pour la partie III, en gardant 5 minutes pour relire le code.
## Partie I — Détection de cycles
Avant d'ajouter un arc $u\to s$, on veut vérifier que $s\not\rightsquigarrow u$. La fonction `pp` attribue l'époque courante à tous les sommets qu'elle visite et numérote les sommets par ordre de fin de traitement. Les invariants A2–A4 servent à répondre `False` sans parcours dans certains cas. Toute la partie consiste à prouver que ce raccourci est juste, puis que les invariants survivent aux appels.
### Question 1
> [!INDICATION]
> Simulez l'appel pas à pas. `sortie[s]` n'est affecté qu'**après** la boucle sur les successeurs : c'est un numéro de fin de traitement.
> [!INDICATION]
> Lorsque `pp('d')` s'exécute, regardez l'époque de ses deux cibles à cet instant.
#### Solution
Avec `présent = 1`, `compteur = 0`, `pp('a')` procède ainsi :
- elle visite $a$, puis $c$ ;
- elle visite $X$ (sortie 0), puis $Y$ (sortie 1), et termine $c$ (sortie 2) ;
- elle visite $d$, dont les cibles $Y$ et $X$ ont déjà l'époque 1, et termine $d$ (sortie 3) ;
- elle termine $a$ (sortie 4).
Les sommets $b,e,W,Z$ ne sont pas atteints.
| | 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 |
On retrouve bien `sortie['a'] = 4` et `sortie['X'] = 0`, comme l'indique l'énoncé.
> [!PIEGE]
> L'ordre des successeurs compte : `G['d']` vaut `['Y', 'X']`, mais $d$ ne revisite ni $Y$ ni $X$, qui portent déjà l'époque courante. Les sommets non visités gardent leurs valeurs initiales, 0 pour les deux dictionnaires.
### Question 2
> [!INDICATION]
> Quel invariant borne les époques par `présent` ? Est-il valide au moment de l'incrémentation ?
#### Solution
Soit $p$ la valeur de `présent` avant l'incrémentation. L'instruction s'exécute hors de `pp`, donc A2 est vrai : $\texttt{époque}[t]\le p$ pour tout sommet $t$. L'incrémentation ne modifie pas `époque`, et `présent` vaut ensuite $p+1$. Donc
$$\texttt{époque}[t]\le p<p+1=\texttt{présent},$$
d'où **$\texttt{époque}[t]\neq\texttt{présent}$ pour tout sommet $t$**.
> [!METHODE]
> Une époque fraîche, strictement supérieure à toutes celles déjà distribuées, permet de marquer « visité pendant ce parcours » sans réinitialiser tout le dictionnaire. C'est l'intérêt du compteur `présent`.
### Question 3
> [!INDICATION]
> Deux sens à démontrer. Pour l'un, il faut savoir qui peut recevoir l'époque `présent` ; pour l'autre, il faut suivre un chemin de $s$ à $t$.
> [!INDICATION]
> Le résultat de Q2 dit qu'avant l'appel, aucun sommet ne porte l'époque `présent`. Pour le sens direct, montrez que tout successeur d'un sommet visité est visité, puis raisonnez par récurrence le long du chemin.
#### Solution
Pendant `pp(s)`, `présent` est constant. Une époque n'est modifiée qu'à la ligne 16, et elle reçoit alors la valeur `présent`, sur le sommet visité.
*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 en cours de visite, 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.* Soit $x$ visité et $x\to y$ un arc. Quand la boucle de `pp(x)` examine $y$, deux cas sont possibles : soit $y$ porte déjà l'époque `présent`, et il a donc été visité pendant cet appel (Q2) ; soit `pp(y)` est appelée. Dans les deux cas, $y$ est visité. Pour un chemin $s=x_0\to\dots\to x_k=t$, une récurrence sur $i$ montre que chaque $x_i$ est visité. Donc $t$ reçoit l'époque `présent`, qui n'est plus modifiée par la suite.
$$\boxed{\ s\rightsquigarrow t\iff \texttt{époque}[t]=\texttt{présent}\ }$$
> [!PIEGE]
> Sans Q2, le sens indirect tombe : un sommet pourrait porter l'époque `présent` héritée d'un parcours antérieur sans être accessible depuis $s$.
### Question 4
> [!INDICATION]
> Placez-vous à l'instant où la boucle de `pp(u)` examine $v$. Distinguez selon que $v$ porte déjà l'époque courante ou non.
> [!INDICATION]
> Si $v$ a déjà été atteint, sa visite peut être terminée ou encore en cours. Que signifierait « encore en cours » pour le graphe ?
#### Solution
On se place dans le contexte d'`accessible` : l'appel `pp(s)` suit `présent += 1`, donc aucun sommet ne porte l'époque courante au départ (Q2). Comme $s\rightsquigarrow u$, `pp(u)` s'exécute (Q3). Le compteur croît strictement à chaque affectation de `sortie`. Considérons l'instant où la boucle de `pp(u)` examine $t=v$.
- **$v$ n'a pas l'époque courante.** Alors `pp(v)` est appelée et se termine, en affectant `sortie[v]`, avant que `pp(u)` n'affecte `sortie[u]`. Donc $\texttt{sortie}[v]<\texttt{sortie}[u]$.
- **$v$ a l'époque courante.** Alors `pp(v)` a commencé pendant cet appel. Supposons qu'elle ne soit pas terminée. Alors `pp(u)` a été déclenchée, directement ou non, par `pp(v)`, et la pile d'appels fournit un chemin $v\rightsquigarrow u$. Avec l'arc $u\to v$, cela forme un cycle, ce qu'exclut A1. Donc `pp(v)` est terminée, et `sortie[v]` est strictement inférieur à la valeur que recevra `sortie[u]`.
Dans les deux cas, $\texttt{sortie}[u]>\texttt{sortie}[v]$, donc **$\texttt{sortie}[u]\ge\texttt{sortie}[v]$**.
> [!METHODE]
> C'est la propriété classique de l'ordre de fin dans un parcours en profondeur d'un graphe sans cycle : un sommet finit après tous ses successeurs. L'acyclicité sert à exclure exactement un cas, l'arc vers un sommet dont la visite est encore en cours (un « arc arrière »).
> [!PIEGE]
> Oublier ce second cas, c'est démontrer la propriété seulement pour les arcs de l'arbre de parcours.
### Question 5
> [!INDICATION]
> Montrez d'abord que les lignes 5–6 ne renvoient jamais `False` à tort, c'est-à-dire que si $s\rightsquigarrow t$, leur condition est fausse. Concluez ensuite avec Q3.
> [!INDICATION]
> Le long d'un chemin, A3 rend les époques croissantes. Si les époques des extrémités sont égales, que dire des époques intermédiaires ? Quel invariant s'applique alors à chaque arc ?
> [!INDICATION]
> N'oubliez pas le cas $t=s$, qui correspond au chemin vide.
#### Solution
On suppose $s\rightsquigarrow t$ par un chemin $s=x_0\to\dots\to x_k=t$, éventuellement vide. A3 donne $\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 des époques est constante, et A4 s'applique à chaque arc : $\texttt{sortie}[x_0]\ge\dots\ge\texttt{sortie}[x_k]$. La condition des lignes 5–6 est donc fausse.
- Si $s\rightsquigarrow t$, la fonction 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. Le résultat est `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}$ : le résultat est `False`.
**`accessible(s, t)` renvoie `True` si et seulement si $s\rightsquigarrow t$.**
> [!METHODE]
> Pour prouver un test « raccourci », on montre qu'il ne répond jamais faux. La justesse de la réponse donnée sans raccourci vient ensuite d'un résultat déjà établi.
### Question 6
> [!INDICATION]
> Notez $V$ l'ensemble des sommets visités. Que valent les époques dans $V$ et hors de $V$ ? Qu'est-ce qui a changé hors de $V$ ?
> [!INDICATION]
> Propriété clé : si $x\in V$ et $x\to y$, alors $y\in V$. Pour A4, montrez que l'égalité des époques force $x$ et $y$ à être tous deux dans $V$ ou tous deux hors de $V$, puis utilisez Q4.
#### Solution
Si la fonction sort ligne 7, rien n'est modifié. Sinon, soit $p$ la valeur de `présent` avant la ligne 9, et $V=\{x : s\rightsquigarrow x\}$ l'ensemble des sommets visités. D'après Q3, ce sont exactement les sommets d'époque $p+1$. Hors de $V$, `époque` et `sortie` sont inchangés, et les époques y restent $\le p$ par A2. De plus, $V$ est stable par les arcs.
- **A2.** Dans $V$, $\texttt{époque}=p+1=\texttt{présent}$. Hors de $V$, $\texttt{époque}\le p<\texttt{présent}$.
- **A3.** Soit un arc $x\to y$. Si $x\in V$, alors $y\in V$, et les deux époques sont égales. Si $x\notin V$ et $y\in V$, alors $\texttt{époque}[x]\le p<\texttt{époque}[y]$. Si $x,y\notin V$, A3 valait déjà avant l'appel.
- **A4.** Soit un arc $x\to y$ dont les extrémités ont la même époque. Les époques valent $p+1$ dans $V$ et au plus $p$ hors de $V$, donc les deux sommets sont tous deux dans $V$ ou tous deux hors de $V$. Dans $V$, Q4 s'applique ($s\rightsquigarrow x$) et donne $\texttt{sortie}[x]\ge\texttt{sortie}[y]$. Hors de $V$, A4 valait déjà avant l'appel.
`accessible` ne modifie pas le graphe. **A2, A3 et A4 sont préservés.**
> [!PIEGE]
> Le cas « $x$ non visité, $y$ visité » existe bel et bien : par exemple $b\to c$ après `pp('a')` en Q1. A3 y est strict, donc A4 ne s'y applique pas.
### Question 7
> [!INDICATION]
> Commencez par A1 : tout cycle créé emprunterait le nouvel arc. Pour A2–A4, utilisez Q6 sur les arcs anciens. Il ne reste alors qu'à étudier l'arc ajouté.
> [!INDICATION]
> L'arc $u\to s$ n'est ajouté que si `accessible(s, u)` a renvoyé `False`. Distinguez les lignes qui ont pu produire ce `False` : chacune donne une information sur les époques et les sorties de $u$ et $s$.
#### Solution
`accessible(s, u)` préserve A2–A4 (Q6) et ne modifie pas le graphe. Si son résultat est `True`, rien n'est ajouté. Sinon, $s\not\rightsquigarrow u$ (Q5) et l'on ajoute l'arc $u\to s$.
- **A1.** Un cycle du nouveau graphe emprunterait l'arc $u\to s$ et se refermerait par un chemin $s\rightsquigarrow u$ de l'ancien graphe, ce qui est impossible. Notamment $u\neq s$, car `accessible(s, s)` renvoie `True`.
- **A2.** Ni `époque` ni `présent` ne changent.
- **A3, A4.** Les arcs anciens vérifient A3–A4 (Q6). Pour le nouvel arc $u\to s$ :
- sortie ligne 7 avec $\texttt{époque}[s]>\texttt{époque}[u]$ : A3 est strict, et A4 est vide ;
- sortie ligne 7 avec $\texttt{époque}[s]=\texttt{époque}[u]$ et $\texttt{sortie}[s]<\texttt{sortie}[u]$ : A3 et A4 sont vrais ;
- sortie ligne 12 : $\texttt{époque}[s]=\texttt{présent}\neq\texttt{époque}[u]$. Comme $\texttt{époque}[u]\le\texttt{présent}$ (A2), A3 est strict, et A4 est vide.
**`lier(u, s)` préserve A1, A2, A3 et A4.**
> [!JURY]
> Dans une preuve d'invariants, il faut traiter chaque invariant séparément et dire à quel moment il est supposé vrai. Ici, A2–A4 sont valides à l'entrée de `lier` mais pas pendant `pp`. Une phrase générale du type « les invariants sont préservés car on ne crée pas de cycle » ne suffit pas.
## Partie II — Unification
On suppose maintenant que les sommets ont au plus deux arcs sortants. Chaque sommet représente alors un terme binaire, sa forme normale, avec des sommets libres aux feuilles. Unifier, c'est lier certains sommets libres pour rendre égales des formes normales, comme on unifie des termes avec variables. Les outils sont un variant de terminaison, une récurrence de complexité, la mémoïsation et l'exploitation des équivalences T1–T4.
### Question 8
> [!INDICATION]
> Lisez la longueur de chaque liste dans la représentation Python.
#### Solution
- **Internes** (degré 2) : $a,b,c,d,e$.
- **Lié** (degré 1) : $W$.
- **Libres** (degré 0) : $X,Y,Z$.
### Question 9
> [!INDICATION]
> Cherchez une quantité entière, attachée à chaque sommet, qui diminue quand on suit un arc. Pourquoi est-elle bien définie dans ce graphe ?
#### Solution
On pose $N(s)$ = longueur du plus long chemin issu de $s$. Cette quantité est finie, car $G$ est fini et acyclique : un chemin ne repasse par aucun sommet et a donc au plus $|S|-1$ arcs. Pour tout arc $s\to t$, on prolonge un plus long chemin issu de $t$ par cet arc, 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$. L'entier naturel $N$ décroît donc strictement à chaque appel : **`fn` termine**.
> [!PIEGE]
> Sans A1, $N$ ne serait pas défini et `fn` pourrait boucler. Il faut citer l'acyclicité explicitement.
### Question 10
> [!INDICATION]
> Il faut construire une famille de graphes, et pas seulement observer un cas. Comptez le nombre d'appels $C(s)$ et écrivez sa relation de récurrence.
> [!INDICATION]
> Cherchez des étages de sommets internes dont les deux fils sont à l'étage inférieur, de sorte que chaque étage double le nombre d'appels. On peut éviter les arcs multiples en mettant deux sommets par étage.
#### Solution
On note $C(s)$ le nombre d'appels déclenchés par `fn(s)`, cet appel compris. On a $C(s)=1$ si $s$ est libre, $1+C(s^*)$ si $s$ est lié, et $1+C(s_0)+C(s_1)$ si $s$ est interne.
Pour $m\ge 0$, on prend $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}]
```
Les arcs descendent d'un étage, donc le graphe est acyclique. Le degré sortant est au plus 2, et il n'y a pas d'arc multiple. Par symétrie, $c_i:=C(x_i)=C(y_i)$ vérifie $c_0=1$ et $c_i=1+2c_{i-1}$. Comme $c_i+1=2(c_{i-1}+1)$, on obtient $c_i=2^{i+1}-1$, d'où
$$\boxed{C(x_m)=2^{n/2}-1}$$
Chaque appel coûte au moins une opération. **La complexité dans le pire cas de `fn` est donc au moins exponentielle en le nombre de sommets.**
Si l'on accepte deux arcs parallèles vers le même sommet (`G[s_i] = [s_{i-1}, s_{i-1}]`), une simple chaîne donne $2^n-1$ appels.
> [!METHODE]
> Pour minorer une complexité, on exhibe une famille d'entrées et on résout la récurrence du nombre d'appels. Ici, $u_i=1+2u_{i-1}$ se résout en posant $u_i+1$.
### Question 11
> [!INDICATION]
> La lenteur de `fn` vient de ce qu'elle recalcule la même valeur pour un même sommet. Comment ne la calculer qu'une fois ?
> [!INDICATION]
> Utilisez un dictionnaire de résultats. Pour la complexité, comptez combien de fois le corps « utile » s'exécute, et vérifiez que construire un couple coûte $O(1)$.
#### Solution
```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 la définition de $\mathrm{fn}$, et la valeur mémorisée pour $x$ est $\mathrm{fn}(x)$. La terminaison découle de Q9.
*Complexité.* Le calcul de `memo[x]` s'exécute au plus une fois par sommet, en $O(1)$ hors appels récursifs. La construction d'un couple se contente de référencer deux valeurs déjà construites, sans les recopier. Chaque exécution de ce calcul lance au plus deux appels, donc il y a au plus $1+2|S|$ appels en tout. **Complexité $O(|S|)$.**
> [!PIEGE]
> La forme normale peut avoir une taille exponentielle si on la « déplie » en arbre. Elle n'est pourtant jamais recopiée : les sous-termes sont **partagés** par référence. Une version qui convertirait le résultat en chaîne de caractères perdrait la linéarité.
### Question 12
> [!INDICATION]
> Écrivez une relation de récurrence sur $T$ en fonction du premier arc d'un chemin. Que vaut $T$ sur un sommet libre ?
> [!INDICATION]
> Le chemin vide compte. La même astuce qu'en Q11 évite une explosion du temps de calcul.
#### Solution
Si $s$ est libre, $T(s)=1$ : le seul chemin est le chemin vide. Sinon, les chemins voulus se répartissent selon leur premier arc, d'où $T(s)=\sum_{s\to t}T(t)$. La récursion termine par Q9.
```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|)$.**
> [!METHODE]
> $T(s)$ est exactement le nombre de feuilles de l'arbre $\mathrm{fn}(s)$ déplié. Elle mesure donc la taille de la forme normale « à plat », qui peut être exponentielle (Q10), alors que son calcul est linéaire.
### Question 13
> [!INDICATION]
> Une extension ne modifie que les sommets libres. Que devient alors $c$, et quelle forme a nécessairement $\mathrm{fn}(c)$ ?
> [!INDICATION]
> Un terme fini peut-il être égal à l'un de ses sous-termes stricts ? Définissez une taille pour le démontrer.
#### Solution
Soit $H$ une extension. Le sommet $c$ reste interne, avec $c_0=X$ et $c_1=Y$, donc $\mathrm{fn}_H(c)=(\mathrm{fn}_H(X),\mathrm{fn}_H(Y))$. On définit la taille par $|v|=1$ pour un sommet et $|(\alpha,\beta)|=1+|\alpha|+|\beta|$. Les formes normales sont finies (Q9), et
$$|\mathrm{fn}_H(c)|=1+|\mathrm{fn}_H(X)|+|\mathrm{fn}_H(Y)|>|\mathrm{fn}_H(X)|.$$
Donc $\mathrm{fn}_H(c)\neq\mathrm{fn}_H(X)$ pour toute extension $H$. **Le problème $\{(c,X)\}$ n'a pas de solution.**
> [!PIEGE]
> Montrer seulement que $\mathrm{fn}(c)\neq\mathrm{fn}(X)$ dans $G$ ne suffit pas : il faut considérer toutes les extensions, y compris celles où $X$ devient lié. C'est l'analogue du test d'occurrence en unification : $x$ ne s'unifie pas avec un terme qui contient strictement $x$.
### Question 14
> [!INDICATION]
> Quand cette branche est atteinte, que sait-on de $s$, et de $t$ compte tenu des branches précédentes ? Quelle équivalence parmi T1–T4 s'applique alors ?
> [!INDICATION]
> T4 a une hypothèse $s\neq t$. Que se passe-t-il si $s=t$ ? Et que renverrait `lier(s, s)` ?
> [!INDICATION]
> Si l'arc voulu crée un cycle, peut-il appartenir à une extension ?
#### Solution
```python
elif len(G[s]) == 0:
if s != t and not lier(s, t):
return False
```
Dans cette branche, $s$ est libre et $t$ n'est pas lié : les cas « $t$ lié » et « deux internes » ont été traités avant, et la branche `else` ramène « $s$ interne, $t$ libre » à ce cas, grâce à T1.
- Si $s=t$, la paire est satisfaite par toute extension, et on la retire simplement. Sans le test `s != t`, `lier(s, s)` renverrait `False` puisque $s\rightsquigarrow s$, et `unif` répondrait à tort « pas de solution ».
- Si $s\neq t$, T4 s'applique : $P$ a une solution si et seulement si $P'$ en a une qui contient $s\to t$. Une extension est acyclique et contient $G$. Si $t\rightsquigarrow s$, aucune extension ne contient $s\to t$ : `lier(s, t)` renvoie `False`, et la fonction aussi. Sinon, `lier` ajoute $s\to t$, étiqueté 0 puisque $s$ était libre. Le nouveau $G$ est une extension, et l'on continue avec $P'$, puisque `P.pop()` a déjà retiré la paire.
> [!PIEGE]
> Écrire `lier(t, s)` est faux quand $t$ est interne : le sommet qui reçoit un arc sortant doit être libre, sinon on viole la définition d'une extension et A5.
## Partie III — Représentation relationnelle
Le graphe est maintenant stocké dans deux tables, `sommets` et `arcs`. La Q15 est une vérification de routine par double jointure. La Q16 paraît demander de calculer `fn`, ce qui serait récursif. Il faut d'abord un raisonnement de graphe pour la ramener à une propriété locale.
### Question 15
> [!INDICATION]
> Pour vérifier un invariant en SQL, on cherche ses contre-exemples : la requête doit renvoyer un résultat vide si l'invariant est vrai.
> [!INDICATION]
> Pour chaque arc, il faut les colonnes de sa source et de sa cible : joignez deux fois la table `sommets`.
#### Solution
```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);
```
**A3 et A4 sont vérifiés si et seulement si cette requête ne renvoie aucune ligne.** Les lignes renvoyées, s'il y en a, sont les arcs fautifs. On peut aussi remplacer la première ligne par `SELECT COUNT(*)` et tester que le résultat vaut 0.
> [!PIEGE]
> La négation de « $P\Rightarrow Q$ » est « $P$ et non $Q$ ». Il faut donc écrire une égalité des époques **et** l'inégalité stricte `s.sortie < t.sortie`.
### Question 16
> [!INDICATION]
> Le SQL au programme ne permet pas de calculer `fn` récursivement. Cherchez une propriété **locale** qui détecte l'existence d'une paire.
> [!INDICATION]
> Commencez par les cas évidents : un sommet lié et sa cible ont-ils la même forme normale ? Deux sommets internes qui ont exactement les mêmes fils ?
> [!INDICATION]
> En l'absence de sommet lié, prenez une paire solution qui minimise $N(s)$ (Q9), et regardez les fils.
#### Solution
**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 0 et 1.
*Preuve.* Si $s$ est lié, $\mathrm{fn}(s)=\mathrm{fn}(s^*)$, et $s\neq s^*$ par acyclicité. Si deux internes ont les mêmes fils, leurs formes normales coïncident.
Réciproquement, on suppose qu'aucun sommet n'est lié et qu'il existe des paires solutions. On en choisit une, $(s,t)$, qui minimise $N(s)$. Un libre a pour forme normale un sommet, un interne un couple. Si l'un des deux est libre, les deux le sont, et alors $s=\mathrm{fn}(s)=\mathrm{fn}(t)=t$, ce qui est exclu. Les deux 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)$ contredirait la minimalité, puisque $N(s_0)<N(s)$. Donc $s_0=t_0$, et de même $s_1=t_1$. $\square$
```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;
```
L'existence 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$ et évite les doublons. **Toute ligne renvoyée est une paire valide, et le lemme garantit qu'une ligne est renvoyée dès qu'une paire existe.** Sur la figure 1, la requête renvoie $(W,Z)$.
> [!PIEGE]
> Si l'on ne traite que les sommets internes de mêmes fils, on oublie les sommets liés. Sur la figure 1, la requête ne renverrait alors rien, alors que $\mathrm{fn}(W)=\mathrm{fn}(Z)$.
> [!METHODE]
> Quand une propriété globale semble exiger une récursion, on cherche un **contre-exemple minimal** : un argument de minimalité montre souvent qu'il existe un témoin local, détectable par une jointure de profondeur fixe.
## Bilan
**Méthodes à retenir.**
- Prouver un algorithme de graphe par **invariants**, en disant quand chacun est valide : ici, A2–A4 sont vrais hors de `pp`.
- L'ordre de **fin de traitement** d'un parcours en profondeur dans un graphe acyclique : un sommet finit après ses successeurs. L'acyclicité exclut les arcs vers un sommet dont la visite est en cours.
- Prouver la terminaison par un **variant entier** : la longueur du plus long chemin dans un graphe acyclique.
- Minorer une complexité par une famille d'exemples et une **récurrence** du type $u_i=1+2u_{i-1}$.
- La **mémoïsation** par dictionnaire, avec le partage des sous-structures, fait passer d'un coût exponentiel à un coût linéaire.
- En SQL, vérifier un invariant revient à chercher ses **contre-exemples** ; on remplace une récursion par un argument de **témoin minimal**.
**Prérequis à revoir.** Le parcours en profondeur récursif en Python, les variables globales (`global`), la complexité des opérations sur les dictionnaires, les jointures multiples et les auto-jointures, ainsi que `UNION` et `LIMIT`.
**Questions classiques transposables.** Le test d'accessibilité incrémental dans un graphe acyclique se retrouve dans l'ordonnancement et les dépendances de compilation. Le test d'occurrence en unification (Q13) se retrouve en typage et en programmation logique. La forme normale mémoïsée (Q11) se retrouve dans le partage de sous-expressions et les diagrammes de décision binaires. Le comptage de chemins dans un graphe acyclique (Q12) est un exercice classique de programmation dynamique.
Aide sur le corrigé
Connectez-vous pour demander une explication.