Corrigé Mines-Ponts 2025 Informatique I MPI — Partie 3 (Q19 à Q29) : Skip lists : implémentation et complexité en moyenne

Conventions. Un nœud « de niveau $\ell$ » possède les pointeurs d'indices $0$ à $\ell$ (comme la sentinelle, de niveau MAX_NIVEAU) ; il appartient aux listes des niveaux $0,\dots ,\ell$. Le champ niveau_actuel est le plus haut niveau utilisé (il vaut $0$ pour une liste vide) et la sentinelle pointe sur NULL à tous les niveaux supérieurs. On note $S_i$ l'ensemble des éléments présents au niveau $i$ : chaque $S_i$ est chaîné par ordre croissant de clef, et $S_0\supseteq S_1\supseteq \cdots$. Ces conventions sont celles du sujet : la sentinelle a MAX_NIVEAU$+1$ pointeurs, le tableau noeuds_a_mettre_a_jour a MAX_NIVEAU$+1$ cases, sl_mystere renvoie un niveau entre $0$ et MAX_NIVEAU, et le test niveau > liste->niveau_actuel de sl_ajoute_valeur suppose un niveau courant déjà défini, $0$, pour une liste encore vide.

Q19.

int sl_rechercher(slListe* liste, char* clef) {
  assert(liste != NULL && clef != NULL);
  slNoeud* courant = liste->sentinelle;
  for (int i = liste->niveau_actuel; i >= 0; i = i - 1) {
    while (courant->suivant_par_niveau[i] != NULL
           && strcmp(courant->suivant_par_niveau[i]->clef, clef) < 0) {
      courant = courant->suivant_par_niveau[i];
    }
  }
  slNoeud* candidat = courant->suivant_par_niveau[0];
  if (candidat != NULL && strcmp(candidat->clef, clef) == 0) {
    return candidat->valeur;
  }
  return -1;
}

Invariant : à la fin du traitement du niveau $i$, courant est le dernier élément de $S_i$ de clef strictement inférieure à clef, ou la sentinelle s'il n'y en a pas. Au départ du niveau $i$, courant est ce nœud pour le niveau $i+1$ (ou la sentinelle au niveau le plus haut) ; il appartient aussi à $S_i$, et aucun élément de $S_i$ situé avant lui ne peut être « le dernier de clef inférieure », puisque lui-même convient ; la boucle avance tant que le suivant au niveau $i$ a une clef inférieure, et s'arrête sur un suivant nul ou de clef $⩾$ clef : l'invariant est rétabli. Au niveau $0$, qui contient tous les éléments triés, le seul élément qui puisse porter la clef est donc le suivant de courant : on le teste par strcmp. La sentinelle, dont la clef vide n'a pas de sens, n'est jamais comparée. Chaque boucle while termine, car elle avance dans une liste finie.

Exécuté sur la figure 2 reconstruite : les sept clefs donnent leurs valeurs, la recherche de "g" fait exactement les trois comparaisons de la descente de la figure 3 ($d<g$, $f<g$, puis $g\nless g$) suivies du test d'égalité final, et "h", "aa", la clef vide, une liste vide donnent $-1$.

Ce que le correcteur attend : descendre par niveaux en repartant du nœud atteint ; un code qui repart de la sentinelle à chaque niveau, ou qui ne parcourt que le niveau $0$, n'exploite pas la structure et n'est pas meilleur qu'une liste chaînée.

Q20. sl_mystere compte les « succès » consécutifs d'un tirage à pile ou face (rand() % 2 == 1), en s'arrêtant au premier échec ou à MAX_NIVEAU. En supposant les tirages indépendants et rand() % 2 égal à $1$ avec probabilité $\frac{1}{2}$ (c'est exact si rand est uniforme et RAND_MAX$+1$ pair, par exemple $2^{31}$), la valeur renvoyée $X$ vérifie :

• $0⩽X⩽$ MAX_NIVEAU ;
• $P(X⩾k)=2^{-k}$ pour $0⩽k⩽$ MAX_NIVEAU ;
• $P(X=k)=2^{-(k+1)}$ pour $0⩽k<$ MAX_NIVEAU, et $P(X=\text{MAX\_NIVEAU})=2^{-\text{MAX\_NIVEAU}}$.

$X+1$ suit donc une loi géométrique de paramètre $\frac{1}{2}$ tronquée en MAX_NIVEAU$+1$ ; ce n'est pas exactement une loi géométrique, puisque $0$ est possible et que la valeur est plafonnée. $E(X)={\sum }_{k=1}^{\text{MAX\_NIVEAU}}P(X⩾k)=1-2^{-\text{MAX\_NIVEAU}}$. C'est exactement le tirage voulu : un nœud est au niveau $k$ avec probabilité $2^{-k}$, et monte au niveau supérieur avec probabilité $\frac{1}{2}$. Exécuté ($4\cdot 10^6$ tirages) : fréquences $0,500$ ; $0,250$ ; $0,125$ ; $0,063$ et moyenne $1,000$.