Mines Informatique 2 MPI 2026Sujet et rapport du jury

ÉCOLE NATIONALE DES PONTS et CHAUSSÉES, ISAE-SUPAERO, ENSTA, TÉLÉCOM PARIS, MINES PARIS - PSL, MINES SAINT-ÉTIENNE, MINES NANCY, IMT ATLANTIQUE, ENSAE PARIS, CHIMIE PARISTECH - PSL.

Regards contemporains sur des algorithmes des années 1990

Préliminaires

Travail attendu

1 Représentation relationnelle des données

On considère les trois tables relationnelles suivantes :

où :

• -salle.id est la clé primaire de la table salle ;
• -salle.x et salle.y sont des entiers correspondant aux coordonnées du coin supérieur gauche de la salle ;
• -passage.entree et passage.sortie sont des clés étrangères référençant salle.id ;
• -passage.cout est un entier correspondant au coût, pour un joueur, d'emprunter ce passage qui conduit de la salle passage.entree vers la salle passage.sortie;
• -objet.salle_id est une clé étrangère référençant salle.id;
• -objet.type est une chaîne de caractères décrivant l'objet concerné.

2 Représentation en mémoire et navigation dans le monde

2.1 Implémentation classique du graphe pondéré

struct _passage {
    int cout;
    int sortie;
    struct _passage* suivant;
};
typedef struct _passage passage;
struct _salle {
    int id;
    passage* passages;
};
typedef struct _salle salle;
struct _monde {
    salle** salles;
    int taille;
};
typedef struct _monde monde;

• -un identifiant unique id;
• -un pointeur passages vers une liste chaînée de passages sortants.

• -le coût du passage (cout);
• -l'indice de la salle de destination (sortie);
• -un pointeur suivant vers le passage suivant dans la liste.

monde* monde_init(int n);

int monde_degre(monde* m, int s);

int monde_sommeDegres(monde* m);

int monde_coutTotal(monde* m);

• chaque entier est encodé sur 32 bits;
• chaque pointeur est encodé sur 32 bits; exprimer en octets l'occupation mémoire totale de cette représentation en fonction de ns et np.
  □ 11 - On se place dans un contexte très contraint en mémoire, typique des moteurs de jeux vidéo anciens, et l'on suppose que l'on dispose de 64 Ko de mémoire pour stocker l'ensemble des structures du graphe, représenté à l'aide des listes chaînées décrites précédemment. On suppose que :

• -chaque entier est codé sur 32 bits;
• -chaque pointeur est codé sur 32 bits;
• -en moyenne, chaque salle possède un nombre constant de quatre passages sortants.

2.2 Représentation CSR pour un graphe

• -un tableau sorties contenant, de manière contiguë, les indices des salles de destination de tous les passages du monde;
• -un tableau indices indiquant, pour chaque salle s, l'indice dans le tableau sorties où commence la liste de ses passages sortants ;
• -un tableau couts, de même taille que sorties, tel que couts[k] soit le coût du passage allant de la salle d'indice s vers la salle d'indice sorties [k], pour tout k dans l'intervalle【indices[s]; indices[s + 1] - 1].

sorties = {1,3,2,0,4,1,2},
indices = {0,2,3,5,6,7},
couts = {2,5,1,4,3,6,2}

struct _mondeCSR {
    int* sorties;
    int* indices;
    int* couts;
    int nb_salles;
};
typedef struct _mondeCSR mondeCSR;

mondeCSR* mondeCSR_init(int ns, int np);

int mondeCSR_degre(mondeCSR* mc, int s);

int mondeCSR_sommeDegres(mondeCSR* mc);

int mondeCSR_coutTotal(mondeCSR* mc);

mondeCSR* monde_vers_CSR(monde* m);

2.3 Recherche d'un chemin de coût minimal

typedef struct _file file;
file* file_init(int taille);
bool file_vide(file *f);
void file_enfile(file *f, int x);
int file_defile(file *f);
void file_libere(file *f);

• -Un appel file_init(n) renvoie un pointeur vers une file vide pour laquelle on a alloué de la mémoire nécessaire pour contenir jusqu'à n éléments.
• -Un appel file_vide(f) permet de vérifier si la file pointée par f est vide.
• -Un appel file_enfile(f,x) permet d'ajouter l'entier x à la file pointée par f.
• -Un appel file_defile(f) permet de supprimer et renvoyer l'entier de la file pointée par f qui a été ajouté en premier.
• -Un appel file_libere(f) permet de libérer la mémoire allouée pour la file pointée par f.

int* bfs_cout(mondeCSR* mc, int s);

typedef struct _tasMin tasMin;
tasMin* tasMin_init(void);
bool tasMin_vide(tasMin *tm);
void tasMin_empile(tasMin *tm, int salle, int priorite);
int tasMin_depile(tasMin *tm);
void tasMin_libere(tasMin *tm);

• -Un appel tasMin_init() renvoie un pointeur vers un tas vide.
• -Un appel tasMin_vide(tm) permet de vérifier si le tas pointé par tm est vide.
• -Un appel tasMin_empile(tm, salle, priorite) permet d'ajouter la salle d'indice salle au tas pointé par tm avec la priorité priorite.
• -Un appel tasMin_depile(tm) permet de supprimer et renvoyer l'indice de la salle de priorité minimale dans le tas pointé par tm.
• -Un appel tasMin_libere(tm) permet de libérer la mémoire allouée pour le tas pointé par tm.

void dijkstra(mondeCSR* mc, int s, int* dist);

3 Recherche rapide d'un chemin avec heuristique

• -une salle source d'indice s et une salle destination d'indice t;
• -pour chaque salle d'indice u, une valeur dist [u] représentant le coût actuellement connu d'un chemin allant de la salle d'indice s à la salle d'indice u;
• -une heuristique h(u) estimant le coût restant entre une salle d'indice u et la salle destination d'indice t. On suppose que h(t) = 0;
• - δ(u, t) le coût minimal réel d'un chemin allant d'une salle d'indice u à la salle d'indice t.

• -le fait que les salles sont extraites selon la valeur dist [u] + h(u);
• -le rôle de l'admissibilité de l'heuristique ;
• -un raisonnement par l'absurde.

• -de garantir qu'une salle extraite de la file de priorité possède un coût dist définitif;
• -d'éviter de ré-insérer des salles déjà traitées.

3.1 Heuristique pondérée : compromis entre rapidité et qualité

• -selon quelle valeur les salles sont extraites dans chaque algorithme;
• -en quoi l'introduction de l'heuristique modifie l'exploration du graphe par rapport à la salle destination.

• le nombre de salles explorées ;
• la qualité du chemin trouvé. Est-il toujours optimal?
  □ 32 - En vous appuyant sur les questions précédentes expliquer pourquoi cette variante est particulièrement adaptée aux moteurs de jeux vidéo anciens, cherchant un compromis entre rapidité de calcul et qualité du chemin.

/* Extrait de l'algorithme */
int u = tas_depile(t);
/* Condition : arrêt anticipé */
if (dist[u] + w * h(u) >= best) {
    break;
}

• -considérer un chemin optimal reliant la salle source d'indice s à la salle destination d'indice t, et montrer que, pour toute salle d'indice v située sur ce chemin, la valeur f(v) est majorée par w ⋅ δ(s, t);
• -en déduire que, tant qu'une telle salle d'indice v existe dans la file de priorité, la priorité minimale vérifie min f(⋅) ⩽ w ⋅ δ(s, t), puis expliquer comment la condition d'arrêt
  minf(⋅) ⩾ best
  permet de conclure que best vérifie la définition d'un chemin w-optimal.

4 Arbres BSP et dérécursivation

4.1 Dérécursivation

• -filsDevant : indice du fils gauche ou fils « devant », ou -1 s'il n'existe pas;
• -filsDerriere : indice du fils droit ou fils « derrière », ou -1 s'il n'existe pas.

struct _noeud{
    int filsDevant;
    int filsDerriere;
};
typedef struct _noeud noeud;

void visite(int n);

void infixe(int n);

• 1.parcourir le sous-arbre « devant »;
• 2.visiter le nœud n;
• 3.parcourir le sous-arbre « derrière ».

4.1.1 Parcours infixe récursif

4.1.2 Dérécursivation par déroulage explicite

• -un tableau d'entiers pile;
• -un entier sommet, représentant le nombre d'éléments actuellement empilés et tel que le sommet de la pile est en position sommet-1.

void infixe(int n) {
    /* pile : tableau d'indices, sommet : taille courante */
    while (true) {
        while (bsp[n].filsDevant != -1) {
            pile[sommet] = n;
            sommet++;
            n = bsp[n].filsDevant;
        }
        while (true) {
            visite(n);
            if (bsp[n].filsDerriere != -1) {
                n = bsp[n].filsDerriere;
                break;
            }
            if (sommet == 0) { return; }
            /* L1 */
            /* L2 */
        }
    }
}

4.2 Génération procédurale d'une carte de jeu

• une direction choisie aléatoirement (horizontale ou verticale);

• -une position de coupe choisie aléatoirement entre 30% et 70% de la dimension correspondante.

Ce procédé est répété récursivement sur les sous-salles obtenues, jusqu'à atteindre un nombre de salles égal à une puissance de deux voulue.

• -une direction de coupe représentée par 0 si elle est verticale et 1 si elle est horizontale;
• -une proportion de coupe, stockée sous forme d'un entier compris entre 300 et 700, représentant un pourcentage en %0.

• -la racine de l'arbre représente la première découpe, séparant la salle initiale A en deux sous-salles A_1 et A_2;
• -le fils gauche de la racine correspond à la découpe de A_1 en A_(11) et A_(12);
• -le fils droit correspond à la découpe de A_2 en A_(21) et A_(22);
• -et ainsi de suite pour les niveaux suivants de l'arbre.

int alea(void);

• -un entier valant 0 ou 1, indiquant la direction de la coupe (0 : verticale, 1 : horizontale);
• -un entier compris entre 300 et 700, représentant la proportion de la coupe en %o.

struct _coupe {
    int dir; // 0 ou 1
    int proportion; // entre 300 et 700 inclus
};
typedef struct _coupe coupe;

coupe* repartition(int n);

struct _region {
    int xmin;
    int xmax;
    int ymin;
    int ymax;
};
typedef struct _region region;

region* creation(int n);

• 1.Dans chaque région élémentaire correspondant à une feuille de l'arbre BSP, on place aléatoirement une salle, contenue strictement dans cette région.
• 2.Pour chaque nœud interne de l'arbre BSP, on génère un couloir traversant la ligne de séparation correspondante, de manière à assurer la connectivité entre les deux sous-régions associées.

• -deux salles situées dans des régions adjacentes;
• -une salle et un couloir déjà généré;
• -deux couloirs issus de niveaux différents de l'arbre BSP.

Fin de l'épreuve