Corrigé X-ENS 2025 Informatique C MPI — Partie II (Q22 à Q31) : Déterminant par l'algorithme de Mahajan et Vinay

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

Énoncé

En C, $A_{i, j}$ est A[i*n+j] ; calculs en $O (1)$ . $G (A)$ : sommets $0, \dots, n - 1$ , arc $(i, j)$ de poids $A_{i, j}$ si $A_{i, j} \neq = 0$ .

Marche fermée $v_{0} \dots v_{m}$ ( $m > 0$ ) : arcs de $G (A)$ , tête $v_{0} = v_{m}$ minimale et absente de l'intérieur ; longueur $m$ , poids $ω$ produit des poids. Suite $S = C_{1} \dots C_{k}$ : têtes croissantes, longueur totale $n$ ; $ω (S) = \prod ω (C_{j})$ , $sgn (S) = (- 1)^{n + k}$ , et $det A = \sum_{S} sgn (S) ω (S)$ .

$H_{A}$ : sommets $s$ , $t_{0}$ , $t_{1}$ et $⟨ p, h, u, i ⟩$ ( $p \in {0, 1}$ , $h ⩽ u < n$ , $i < n$ : parité, tête, sommet courant, arcs parcourus). Arcs : (1) $s \to ⟨ n mod 2, h, h, 0 ⟩$ , poids $1$ ; depuis $⟨ p, h, u, i ⟩$ : (2) vers $⟨ p, h, v, i + 1 ⟩$ , poids $A_{u, v} \neq = 0$ , si $h < v$ et $i < n - 1$ ; (3) vers $⟨ 1 - p, h^{'}, h^{'}, i + 1 ⟩$ , poids $A_{u, h} \neq = 0$ , si $h < h^{'}$ et $i < n - 1$ ; (4) si $i = n - 1$ , vers $t_{1 - p}$ , poids $A_{u, h} \neq = 0$ . Admis : les chemins de $s$ à $t_{0}$ (resp. $t_{1}$ ) sont en bijection avec les suites positives (resp. négatives). $F_{A} (x)$ : somme des poids des chemins de $s$ à $x$ ; couche $i$ : les $⟨ p, h, v, i ⟩$ . Fournis : Fourtable, create (table nulle, $O (n^{3})$ ), read, write, free(t) ( $O (1)$ ) :


int read_sqmatrix(int n, int *A, int i, int j);               /* Q22 */
void write_sqmatrix(int n, int *A, int i, int j, int val);   /* Q22 */
Fourtable *create(int n);
void write(Fourtable *t, int val, int p, int h, int v, int i);
int read(Fourtable *t, int p, int h, int v, int i);
Fourtable *initialise(int n);                                 /* Q29 */
Fourtable *remplit(int n, int *A);                            /* Q30 */
int determinant(int n, int *A);                               /* Q31 */

Q22. Écrire read_sqmatrix et write_sqmatrix, en $O (1)$ .
Q23. Dessiner $G (A)$ pour $A = (2 - 2 31)$ .
Q24. Graphe de gauche (poids $1$ ) : marche fermée de longueur $3$ , de tête $1$ .
Q25. Graphe du milieu : (1) marches fermées de longueur au plus $3$ ; (2) suites ; avec poids.
Q26. Même $A$ : arcs manquants, avec poids, de la figure de droite.
Q27. Pour une marche fermée $h, u_{1}, \dots, u_{m}, h$ et $u_{0} = h$ , montrer que les $⟨ p, h, u_{j}, i + j ⟩$ ( $0 ⩽ j ⩽ m$ , $i ⩽ n - 1 - m$ ) forment un chemin de $H_{A}$ ; en déduire qu'une suite positive donne un chemin de $s$ à $t_{0}$ .
Q28. Exprimer $F_{A} (⟨ p, h, v, i ⟩)$ par la couche $i - 1$ .
Q29. initialise(n) : $F_{A}$ sur la couche $0$ , en $O (n^{3})$ .
Q30. remplit(n, A) : toutes les couches, $O (n^{4})$ justifié.
Q31. determinant(n, A), mémoire libérée, $O (n^{4})$ justifié.

Corrigé

Q22. Le coefficient $A_{i, j}$ est la case i*n+j :


int read_sqmatrix(int n, int *A, int i, int j) {
  return A[i * n + j];
}

void write_sqmatrix(int n, int *A, int i, int j, int val) {
  A[i * n + j] = val;
}

Un calcul d'indice et un accès : $O (1)$ . write_sqmatrix ne renvoie rien (type void).

Q23. Les quatre coefficients sont non nuls : $G (A)$ a une boucle sur chaque sommet et un arc dans chaque sens.

Arcs : $(0, 0)$ de poids $2$ , $(0, 1)$ de poids $3$ , $(1, 0)$ de poids $- 2$ , $(1, 1)$ de poids $1$ (l'arc $(i, j)$ porte $A_{i, j}$ : ligne $i$ , colonne $j$ ).

Q24. $1 \to 3 \to 2 \to 1$ : les arcs $(1, 3)$ , $(3, 2)$ , $(2, 1)$ existent, la tête $1$ est le plus petit sommet et n'apparaît qu'aux extrémités ; longueur $3$ . (C'est la seule : une marche de tête $1$ évite $0$ , et le seul arc entrant dans $1$ vient de $2$ .)

Q25. Les arcs sont $(1, 2)$ de poids $1$ , $(2, 1)$ de poids $3$ , $(2, 2)$ de poids $5$ , $(0, 1)$ de poids $2$ et $(2, 0)$ de poids $2$ ; ici $n = 3$ .

(1) Marches fermées de longueur au plus $3$ , classées par tête :

tête $0$ : $0 \to 1 \to 2 \to 0$ , de poids $2 \times 1 \times 2 = 4$ (de $0$ on ne peut aller qu'en $1$ , de $1$ qu'en $2$ , et $0$ ne se rejoint que depuis $2$ ) ;
tête $1$ (sommets $⩾ 1$ ) : $1 \to 2 \to 1$ , de poids $1 \times 3 = 3$ ; $1 \to 2 \to 2 \to 1$ , de poids $1 \times 5 \times 3 = 15$ ;
tête $2$ : $2 \to 2$ , de poids $5$ (une marche de tête $2$ ne passe que par $2$ , qui ne peut apparaître qu'aux extrémités).

(2) Suites de marches fermées (têtes croissantes, longueur totale $3$ ) :

$(0 \to 1 \to 2 \to 0)$ , de poids $4$ ;
$(1 \to 2 \to 2 \to 1)$ , de poids $15$ ;
$(1 \to 2 \to 1) (2 \to 2)$ , de poids $3 \times 5 = 15$ .

Il n'y en a pas d'autre : une suite commençant par la tête $0$ n'a que la marche de longueur $3$ , et une suite de tête $1$ est soit une marche de longueur $3$ , soit une marche de longueur $2$ suivie de la boucle en $2$ . Contrôle : les signes sont $+ 1, + 1, - 1$ et $4 + 15 - 15 = 4$ est bien le déterminant de $002203015$ . (Énumération exhaustive exécutée : mêmes marches, mêmes suites.)

Q26. Ici $n = 2$ , $n mod 2 = 0$ , $A_{0, 0} = 2$ , $A_{0, 1} = 3$ , $A_{1, 0} = - 2$ , $A_{1, 1} = 1$ . Il manque cinq arcs :

$s \to ⟨ 0, 0, 0, 0 ⟩$ , poids $1$ (type 1, $h = 0$ ) ;
$⟨ 0, 0, 0, 0 ⟩ \to ⟨ 0, 0, 1, 1 ⟩$ , poids $A_{0, 1} = 3$ (type 2 : $u = 0$ , $v = 1 > h = 0$ ) ;
$⟨ 0, 0, 0, 0 ⟩ \to ⟨ 1, 1, 1, 1 ⟩$ , poids $A_{0, 0} = 2$ (type 3 : $u = h = 0$ , $h^{'} = 1$ ) ;
$⟨ 0, 0, 1, 1 ⟩ \to t_{1}$ , poids $A_{1, 0} = - 2$ (type 4 : $p = 0$ , $h = 0$ , $u = 1$ ) ;
$⟨ 1, 1, 1, 1 ⟩ \to t_{0}$ , poids $A_{1, 1} = 1$ (type 4 : $p = 1$ , $h = u = 1$ ).

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 →