Corrigé Centrale 2025 Informatique MPI — Partie A, III (Q12 à Q16) : Table de hachage à adressage ouvert

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

Énoncé

Un ensemble d'états (de type etat *) est rangé dans une table de hachage en adressage ouvert. Pour un état $e$ ,

$hash (e) = 0 ⩽ i < M, 0 ⩽ j < M \sum d_{i, j} 3^{i M + j},$

où $d_{i, j}$ vaut $0$ si la case $(i, j)$ est libre, $1$ si elle porte un véhicule horizontal, $2$ un véhicule vertical. On dispose de plateau *p_hash(etat *e), qui renvoie le plateau des $d_{i, j}$ .
Q12. int64_t e_hash(etat *e) renvoie $hash (e)$ .
Q13. Si $e_{1}$ et $e_{2}$ sont accessibles depuis un même état initial et $hash (e_{1}) = hash (e_{2})$ , alors $e_{1} = e_{2}$ .

La table a une capacité $2^{p}$ et une taille (nombre d'états) ; on range $e$ dans la première case vide à partir de $h = hash (e) mod 2^{p}$ , en avançant circulairement. Insertions successives de $e_{0}, \dots, e_{4}$ , de hachés $1, 7, 3, 3, 7$ , dans une table vide de capacité $8$ :

Trop peuplée, la table double sa capacité et réinsère ses éléments.


struct tableh_s {
    etat **tab;
    int taille;
    int capacite;
};
typedef struct tableh_s tableh;

Les cases vides valent NULL. On dispose de tableh *t_nouveau(void) (table vide de capacité $1$ ), de void t_libere(tableh *t) (qui libère aussi les états contenus) et de void t_augmente_capacite(tableh *t) (capacité $c ⩾ 1$ portée à $2 c$ ).
Q14. bool t_contient(tableh *t, etat *e).
Q15. void t_ajoute(tableh *t, etat *e), en maintenant $m ⩽ 2 c /3$ ( $m$ taille, $c$ capacité).
Q16. Pourquoi serait-ce une mauvaise idée de remplacer $3^{i M + j}$ par $4^{i M + j}$ ?

Corrigé

Le code a été compilé et exécuté avec celui des parties I et II (une implémentation de p_hash, t_nouveau, t_libere et t_augmente_capacite complète le programme de test) ; les propriétés de Q13 et Q16 ont été vérifiées en Python sur les $111$ états accessibles depuis la configuration de la figure 1.

Q12. On évalue le polynôme en $3$ par la méthode de Horner, en partant du terme de plus haut degré $i M + j = M^{2} - 1$ .


int64_t e_hash(etat *e) {
    plateau *p = p_hash(e);
    int64_t h = 0;
    for (int i = M - 1; i >= 0; i--)
        for (int j = M - 1; j >= 0; j--)
            h = 3 * h + p->tab[i][j];
    free(p);
    return h;
}

Invariant : après le traitement de la case d'indice linéaire $s = i M + j$ , $h = \sum_{s ⩽ t < M^{2}} d_{t} 3^{t - s}$ ; à la fin ( $s = 0$ ), $h = hash (e)$ . Pas de dépassement : $0 ⩽ h ⩽ \sum_{t < 36} 2 \cdot 3^{t} = 3^{36} - 1 \approx 1, 5 \cdot 1 0^{17}$ , bien en dessous de $2^{63} - 1 \approx 9, 2 \cdot 1 0^{18}$ , et c'est aussi vrai de toutes les valeurs intermédiaires. Le plateau renvoyé par p_hash est alloué sur le tas : il faut le libérer, sinon chaque calcul de haché perd $144$ octets. Coût $O (M^{2})$ .

Q13. Le haché détermine les $d_{i, j}$ . Les $d_{i, j}$ sont les chiffres de $hash (e)$ en base $3$ ( $d_{i, j} \in {0, 1, 2}$ ), et l'écriture en base $3$ est unique : $hash (e_{1}) = hash (e_{2})$ entraîne $d_{i, j} (e_{1}) = d_{i, j} (e_{2})$ pour toutes les cases.

Ce que les déplacements conservent. Un déplacement valide fait glisser un véhicule le long de sa ligne (horizontal) ou de sa colonne (vertical), à travers des cases libres — c'est la règle du jeu rappelée en tête du sujet, les véhicules « bloquent » ceux qu'ils précèdent, et c'est ce que calcule e_deplacements ; on l'énonce explicitement, car la preuve en dépend : il ne change ni $n$ , ni l'indice, la longueur, la direction d'un véhicule, ni la ligne d'un véhicule horizontal, ni la colonne d'un véhicule vertical. Il ne change pas non plus l'ordre de deux véhicules horizontaux d'une même ligne : pour que $A$ , à gauche de $B$ , passe à sa droite, il devrait glisser à travers les cases de $B$ , qui ne sont pas libres. De même pour deux véhicules verticaux d'une même colonne. Par récurrence sur le nombre de coups, tout état accessible depuis $e$ a donc, ligne par ligne, les mêmes véhicules horizontaux, dans le même ordre, que $e$ , et, colonne par colonne, les mêmes véhicules verticaux dans le même ordre.

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 →