Corrigé X-ENS 2026 Informatique A MP — Partie II (II.1 à II.7) : Listes à sauts et graphes hiérarchiques navigables

Sujet officiel du concours X-ENS, session 2026, épreuve Informatique A MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

Une skip list range des entiers strictement positifs ; chaque nœud a un tableau de $L$ successeurs (étages $0$ à $L - 1$ ). L'étage 0 est la liste chaînée triée usuelle ; une valeur présente à l'étage $ℓ$ l'est à tous les étages inférieurs et y a un seul prédécesseur, et les valeurs d'un étage forment une sous-liste de l'étage 0. Un nœud factice de valeur 0 commence la liste ; init_level est le plus haut étage où une valeur est présente, max_level vaut $L - 1$ . Figure 3 ( $L = 5$ , $n = 8$ valeurs ; S : Some, N : None) :


type skip_node = {
  value : int;
  mutable successors : skip_node option array;
}
type skip_list = {
  mutable init_node : skip_node;
  mutable init_level : int; (* Étage où commencer une recherche *)
  mutable max_level : int   (* Étage maximal possible en mémoire *)
}
let create_node max_level v = {
  value = v;
  successors = Array.make (max_level + 1) None
}
let random_level p max_level =
  let rec loop level =
    if level < max_level && Random.float 1. < p then (* proba. p *)
      loop (level + 1)
    else
      level
  in
  loop 0

Le chemin d'une recherche est la suite des couples (nœud, étage) traversés, complétée jusqu'à l'étage 0 ; pour 28 (ou 30) dans la figure 3 : $(0, 2), (0, 1), (11, 1), (15, 1), (15, 0), (17, 0), (28, 0)$ .

II.1. Écrire skip_length : skip_list -> int (nombre de valeurs, nœud factice exclu).
II.2. Nombre moyen de valeurs présentes à l'étage $ℓ$ (étages non bornés) ?
II.3. (a) Écrire search : skip_list -> int -> skip_node option en tirant parti des étages. (b) Correction. (c) Complexité dans le pire cas.
II.4. $C_{ℓ}$ est le nombre moyen d'étapes pour aller, en remontant un chemin de recherche, de sa dernière position à une position d'étage $ℓ$ . Montrer par une récurrence que $C_{ℓ} = ℓ / p$ .
II.5. En déduire qu'une recherche fait en moyenne $O (lo g n)$ étapes.
II.6. (a) Combien de successeurs suffit-il de modifier au plus pour insérer ? (b) Écrire insert : skip_list -> int -> unit pour une valeur absente, sans obligation de mettre à jour init_level.

Graphe hiérarchique : g.(i).(level) est la liste des voisins du nœud $i \in [n]$ à l'étage level ; la relation est symétrique, $i$ est présent à un étage si sa liste n'y est pas vide, et $[n] = V_{0} \supseteq V_{1} \supseteq \dots \supseteq V_{L - 1}$ . La recherche gloutonne part du nœud 0, se déplace vers un voisin qui réduit strictement la distance à query, descend d'étage, et renvoie un indice à l'étage 0. Figure 4 :


type vector = float array
type matrix = vector array
type hgraph = int list array array
val db : matrix
val dist : vector -> vector -> float   (* en O(d) *)

II.7. (a) Écrire closest : vector -> hgraph -> int (recherche gloutonne). (b) Complexité en fonction de $n$ , $∣ E ∣ = \sum_{ℓ} ∣ E_{ℓ} ∣$ , $L$ et $d$ . (c) Faut-il marquer les nœuds pour que l'algorithme termine ?

Corrigé

II.1. Les valeurs sont exactement les nœuds de l'étage 0 après le nœud factice : on suit les successeurs d'étage 0 en comptant.


let skip_length (skl : skip_list) : int =
  let rec compte node acc = match node.successors.(0) with
    | None -> acc
    | Some suivant -> compte suivant (acc + 1)
  in
  compte skl.init_node 0

Toute valeur est présente à l'étage 0 (une valeur présente à un étage l'est aux étages inférieurs), et l'étage 0 est une liste chaînée finie : la récursion (terminale) visite chaque nœud une fois et compte tous les nœuds sauf le factice, en $O (n)$ . Sur la figure 3, on obtient 8 ; sur une liste vide, 0.

II.2. Une valeur est présente à l'étage $ℓ$ si et seulement si l'étage tiré à son insertion est au moins $ℓ$ . Sans borne sur les étages, random_level renvoie un résultat $\geq ℓ$ si et seulement si ses $ℓ$ premiers tirages sont des succès, chacun de probabilité $p$ , indépendants : la probabilité est $p^{ℓ}$ . Notons $X_{v}$ l'indicatrice de « $v$ présente à l'étage $ℓ$ » ; par linéarité de l'espérance, le nombre moyen de valeurs présentes à l'étage $ℓ$ est

$E [v \sum X_{v}] = v \sum Pr (X_{v} = 1) = n p^{ℓ} .$

Contrôle expérimental ( $n = 20000$ insertions, $p = 1/2$ ) : 20 000, 10 084, 5 011, 2 517, 1 236 valeurs aux étages 0 à 4, pour $n p^{ℓ} = 20000, 10000, 5000, 2500, 1250$ .

II.3. (a) On part du nœud factice à l'étage init_level. À chaque étape, on avance à l'étage courant tant que le successeur a une valeur $< v$ ; s'il vaut $v$ , on l'a trouvé ; sinon (successeur $> v$ ou absent), on descend d'un étage, et à l'étage 0 on conclut à l'absence.


let search (skl : skip_list) (v : int) : skip_node option =
  let rec descend node level =
    match node.successors.(level) with
    | Some suivant when suivant.value < v -> descend suivant level
    | Some suivant when suivant.value = v -> Some suivant
    | _ -> if level = 0 then None else descend node (level - 1)
  in
  descend skl.init_node skl.init_level

Exécutée sur la skip list de la figure 3 : elle trouve chacune des 8 valeurs et renvoie None pour 1, 30 et 62, en suivant exactement le chemin donné par le sujet pour 28 et 30.

(b) Invariant : node.value $< v$ (vrai au départ, le factice valant $0 < v$ , et conservé puisqu'on n'avance que vers un successeur de valeur $< v$ ). Si $v$ est présente, son nœud est après node à l'étage 0. Lorsque le successeur de node à l'étage $ℓ$ est absent ou de valeur $w > v$ , aucune valeur de $] node.value, w [$ n'est présente à l'étage $ℓ$ (les valeurs de l'étage sont triées), mais $v$ peut l'être à un étage inférieur : on descend sans rien perdre. À l'étage 0, qui contient toutes les valeurs triées, un successeur absent ou de valeur $> v$ prouve que $v$ n'est pas dans la liste ; un successeur égal à $v$ est le nœud cherché (un même nœud représente $v$ à tous ses étages). Terminaison : le couple (étage, nombre de nœuds après node à l'étage 0) décroît strictement pour l'ordre lexicographique : soit on avance à étage constant, soit on descend.

(c) Chaque pas de côté va vers une valeur strictement plus grande : il y en a au plus $n$ au total, quel que soit l'étage. Il y a au plus init_level $\leq L - 1$ descentes. La complexité dans le pire cas est donc $O (n + L)$ , et elle est atteinte : si toutes les valeurs ne sont présentes qu'à l'étage 0 (tirage défavorable, de probabilité non nulle), chercher une valeur plus grande que toutes les autres parcourt les $n$ nœuds. Les étages n'améliorent que la complexité moyenne (II.5).

II.4. Lisons le chemin à l'envers, depuis sa dernière position (à l'étage 0). Soit $(x, ℓ)$ une position du chemin, $x$ n'étant pas le nœud factice.

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 →