Corrigé CCINP 2025 Informatique MPI — Partie III (III.3) (Q32 à Q38) : Gale-Shapley et graphe des premiers choix en C

Sujet officiel du concours CCINP, session 2025, épreuve Informatique MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Les individus sont numérotés $V = {0, \dots, n - 1}$ et $U = {0, \dots, n - 1}$ . Deux matrices $n \times n$ donnent les préférences : Lv[i][j] est le $j$ -ième élément de $U$ préféré par $i \in V$ , Lu[i][j] le $j$ -ième élément de $V$ préféré par $i \in U$ . La taille est une constante de compilation, #define n 4, et les matrices sont déclarées dans main par int Lv[n][n], Lu[n][n];. III.3.1. Rang[i][j] est le rang (depuis $0$ ) de $j \in V$ dans la liste de $i \in U$ .
Q32. void calcule_rang(int Lu[n][n], int Rang[n][n]) construit Rang.

CoupleV[i] et CoupleU[i] donnent le partenaire actuel de $i$ ; USuiv[i] est, pour $i \in V$ , le rang du prochain élément de $U$ auquel il peut proposer.
Q33. Valeurs d'initialisation de ces trois tableaux.
Q34. void gale_shapley(int Lv[n][n], int Lu[n][n], int CoupleU[n], int CoupleV[n]) réalise l'algorithme 3 en remplissant CoupleU et CoupleV ; le $v$ qui propose est à chaque fois le premier libre par numéro croissant.

III.3.2. Pour l'algorithme 4, les sommets sont numérotés $V = {0, \dots, n - 1}$ , $U = {n, \dots, 2 n - 1}$ , et le graphe $G$ (arc de chaque individu vers son premier choix) est codé par listes d'adjacence :


struct noeud {
        int individu;                 // Element de U union V
        struct noeud* suivant;
};
typedef struct noeud *liste;

struct graphe_s {
        int nb_sommets;
        liste *liste_adjacence;
};
typedef struct graphe_s graphe;

Q35. void ajoute_arc(graphe *g, int i, int j) ajoute l'arc $(i, j)$ .
Q36. void supprime_arc(graphe *g, int i, int j) supprime l'arc $(i, j)$ .
Q37. void supprime_sommet(graphe *g, int s) supprime tous les arcs d'origine ou de destination $s$ .
Q38. graphe *construit_graphe(int Lv[n][n], int Lu[n][n]) construit $G$ , en prenant garde à la numérotation de $U$ .

Corrigé

Toutes les fonctions utilisent la constante n du #define et supposent <stdlib.h> inclus (malloc, free).

Q32. L'élément Lu[i][j] de $V$ occupe le rang $j$ dans la liste de $i$ : on « inverse » chaque ligne de Lu.


void calcule_rang(int Lu[n][n], int Rang[n][n]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            Rang[i][Lu[i][j]] = j;          /* Lu[i][j] est au rang j pour i */
        }
    }
}

Chaque ligne Lu[i] étant une permutation de ${0, \dots, n - 1}$ , chaque case Rang[i][x] est écrite exactement une fois, avec le rang de $x$ . Coût $Θ (n^{2})$ . Ensuite, « $u$ préfère $v$ à $w$ » se teste en $O (1)$ par Rang[u][v] < Rang[u][w]. Sur $D$ (avec $v_{k}, u_{k}$ numérotés $k - 1$ ), les lignes de Rang valent $(0, 2, 1)$ , $(1, 0, 2)$ , $(1, 0, 2)$ : par exemple $u_{1}$ classe $v_{1}$ au rang $0$ , $v_{2}$ au rang $2$ , $v_{3}$ au rang $1$ .

Q33. Au départ, personne n'est apparié et chaque $v$ n'a encore proposé à personne :

CoupleV[i] = -1 et CoupleU[i] = -1 pour tout $i$ : $- 1$ n'est le numéro d'aucun individu et code « libre » ;
USuiv[i] = 0 pour tout $i$ : le prochain élément auquel $v = i$ propose est celui de rang $0$ , son préféré Lv[i][0].

Ce que le correcteur attend : USuiv contient un rang dans la ligne Lv[i], pas un individu ; l'initialiser avec une case de Lu ou de Rang est l'erreur relevée par le jury.

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 →