2026-X-Ens-OptionInfo-MpPcPsi-B-Corrigé

Informatique B

— Filières MP-PC-PSI

— Concours 2026

École polytechnique

— ESPCI

— Écoles normales supérieures. Épreuve n° 8, jeudi 16 avril 2026, 16h30–18h30. Durée : 2 heures. L’utilisation des calculatrices n’est pas autorisée pour cette épreuve.

Cycles et unification

Contexte. Soit {G} un graphe orienté dont les arcs sont étiquetés par des entiers naturels. On suppose que :
A0. Les arcs sortants d’un sommet donné sont étiquetés par des entiers consécutifs en partant de {0}.
A1. {G} est acyclique.
Le graphe {G} est représenté en Python par une variable globale G. C’est un dictionnaire dont les clés sont les sommets et les valeurs sont des listes représentant les arcs sortants. L’étiquette d’un arc correspond à son indice dans la liste. En particulier, les étiquettes des arcs sont implicites et l’hypothèse A0 est automatiquement satisfaite. La figure 1 présente un exemple.
Dans ce problème, certaines des fonctions étudiées modifient G en ajoutant de nouveaux arcs. L’hypothèse A1 est un invariant qui sera maintenu en toute circonstance.
Organisation du sujet. La première partie étudie finement un parcours en profondeur pour pouvoir vérifier efficacement qu’un nouvel arc ne crée pas de cycles dans {G}. La deuxième partie étudie les notions de forme normale et d’unification dans {G}. Cette partie peut être traitée indépendamment de la première. La troisième partie étudie la notion de forme normale dans le contexte d’une base de données relationnelle.
Rappels de Python. On rappelle ici quelques opérations sur les listes et les dictionnaires de Python, avec leur complexité. Si a désigne une liste en Python de longueur {n} :
— L’expression len(a) renvoie la longueur {n}.
— L’expression a[i] désigne le {i}-ième élément de la liste, pour {0\leq i\lt n}.
— L’instruction a[i] = v affecte la valeur v au {i}-ième élément de la liste, pour {0\leq i\lt n}.
— L’instruction a.append(e) ajoute l’élément e à la fin de la liste a.
— L’expression a.pop() supprime et renvoie le dernier élément de la liste a.
Toutes ces opérations sont de complexité {O(1)}. Par ailleurs, la boucle for x in a parcourt tous les éléments de a, dans l’ordre des indices croissants. La complexité est {O(n)}.
Si d désigne un dictionnaire en Python :
— Le test (k in d) renvoie True si k est une clé du dictionnaire d, et False sinon.
— L’expression d[k] renvoie la valeur associée à la clé k dans le dictionnaire d, le cas échéant.
— L’instruction d[k] = v affecte la valeur v à la clé k dans le dictionnaire d.
Toutes ces opérations sont de complexité {O(1)}.

Partie I. Détection de cycles

On note {s\rightsquigarrow t} l’existence d’un chemin de {s} vers {t} dans {G}, et {s\not\rightsquigarrow t} sa négation. Avant d’ajouter un arc de liaison {s\to t}, on souhaite vérifier que {t\not\rightsquigarrow s}. On introduit pour cela des variables globales :
— époque et sortie sont des dictionnaires associant un entier à chaque sommet de {G},
— présent et compteur sont des entiers.
Ces variables globales sont mises à jour par une fonction pp, donnée en figure 2, qui réalise un parcours en profondeur.
En plus de l’invariant A1, on considère les invariants suivants. Ils seront maintenus en toute circonstance, sauf pendant l’exécution de la fonction pp.
A2. {\operatorname{époque}[s]\leq\operatorname{présent}}, pour tout sommet {s} de {G}.
A3. {\operatorname{époque}[s]\leq\operatorname{époque}[t]} pour tout arc {s\to t} de {G}.
A4. {\operatorname{époque}[s]=\operatorname{époque}[t]\Rightarrow\operatorname{sortie}[s]\geq\operatorname{sortie}[t]} pour tout arc {s\to t} de {G}.
On commence par l’étude de la fonction pp.

Figure 2 – Parcours en profondeur.
En s’appuyant sur la fonction pp, on définit les fonctions accessible et lier (figure 3).

Partie II. Unification

On suppose désormais que :
A5. Le degré sortant des sommets de {G} est au plus {2}.
Les sommets de degré {0} sont appelés sommets libres. Les sommets de degré {1} sont appelés sommets liés. Les sommets de degré {2} sont appelés sommets internes.
Si {s} est un sommet lié, on note {s^*} la cible de l’unique arc sortant de {s}. Si {s} est un sommet interne, on note {s_0} la cible de l’arc sortant de {s} étiqueté {0}, et {s_1} la cible de l’arc sortant de {s} étiqueté {1}.

On définit de manière récursive la forme normale d’un sommet {s}, notée {\operatorname{fn}(s)}, par : {\operatorname{fn}(s)=\begin{cases}s&\text{si }s\text{ est libre},\\[4pt]\operatorname{fn}(s^*)&\text{si }s\text{ est lié},\\[4pt](\operatorname{fn}(s_0),\operatorname{fn}(s_1))&\text{si }s\text{ est interne}.\end{cases}}Dans l’exemple de la figure 1, {\operatorname{fn}(a)=((X,Y),(Y,X))} et {\operatorname{fn}(e)=(Z,Z)}. En Python, la définition se traduit comme suit.

Figure 3 – Ajout d’arcs de liaison avec détection de cycle.

Soit {T(s)} le nombre de chemins dans {G} partant d’un sommet {s} et aboutissant à un sommet libre. Par exemple, dans la figure 1, on vérifie que {T(a)=4} et {T(W)=1}.

Une extension de {G} est un graphe {H} acyclique obtenu par ajout, pour certains sommets libres distincts de {G}, d’un arc sortant étiqueté {0} (ces sommets deviennent donc liés dans {H}). En particulier, une extension satisfait bien les invariants A0, A1 et A5.
Un problème d’unification est un ensemble {P} de paires de sommets de {G}. Une solution d’un problème d’unification {P} est une extension de {G} telle que {\operatorname{fn}(s)=\operatorname{fn}(t)} dans cette extension, pour tout {(s,t)\in P}.
Par exemple, dans le contexte de la figure 1, le problème d’unification {\{(a,b)\}} admet comme solution l’extension de {G} obtenue par ajout de l’arc {X\to Y}.

Soit {P} un problème d’unification, {(s,t)} un élément de {P}, et {P'=P\setminus\{(s,t)\}} l’ensemble obtenu en retirant {(s,t)} de {P}. On admet que :
T1. {P'\cup\{(t,s)\}} a les mêmes solutions que {P}.
T2. Si {s} est lié, alors {P'\cup\{(s^*,t)\}} a les mêmes solutions que {P}.
T3. Si {s} et {t} sont internes, alors {P'\cup\{(s_0,t_0),(s_1,t_1)\}} a les mêmes solutions que {P}.
T4. Si {s} est libre, {t} n’est pas lié et {s\neq t}, alors {\begin{array}{l}P\text{ admet une solution}\\[8pt]\quad\Longleftrightarrow P'\text{ admet une solution avec l’arc }s\to t.\end{array}}En s’appuyant sur ces équivalences, on propose la fonction unif(P) (figure 4). Elle prend en argument un problème d’unification P (comme une liste de paires de sommets) et renvoie True si et seulement si G admet une extension solution de P. De plus, si unif(P) renvoie True, alors la variable globale G contient désormais une solution de P. Autrement dit, les arcs d’une solution sont ajoutés directement à G. Par exemple, dans le contexte de la figure 1, unif([('X', 'Y')]) renvoie True et ajoute l’arc {X\to Y} (ou {Y\to X}).

Figure 4 – Fonction unif.

Partie III. Représentation relationnelle

On suppose maintenant que le graphe {G} est représenté dans une base de données relationnelle avec le schéma suivant :
— une table sommets dont les colonnes sont

• id, clé primaire entière,
• degré, entier, représente le degré sortant,
• sortie, entier,
• époque, entier ;

— une table arcs dont les colonnes sont

• étiquette, entier,
• source, clé étrangère vers sommets,
• cible, clé étrangère vers sommets.

Fin du sujet.