Aller au contenu

Mines - Sujet 0 MPI

Sujet

Corrigé du sujet 0 (épreuve de test) de la première épreuve d'informatique de la filière MPI du concours Mines-Ponts, publié par le Concours commun Mines-Ponts (sujet sous licence CC BY-NC-ND 3.0 FR, propriété du GIP CCMP). L'énoncé n'est pas reproduit ici : seules les réponses figurent, avec les numéros de questions du sujet. Le code est en C (C99).

Dans tout ce corrigé, on utilise les déclarations du sujet :

#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <limits.h>

struct maillon {
    int donnee;
    struct maillon *suivant;
};
typedef struct maillon maillon_t;

Listes triées simplement chaînées

Autour des opérations de base

Question 1.

Corrigé 
maillon_t *init(void)
{
    maillon_t *l = malloc(sizeof(maillon_t));
    l->donnee = INT_MIN;
    l->suivant = malloc(sizeof(maillon_t));
    l->suivant->donnee = INT_MAX;
    l->suivant->suivant = NULL;
    return l;
}

Question 2.

Corrigé 
maillon_t *localise(maillon_t *t, int v)
{
    // pas d'erreur d'accès à suivant ici en raison de la
    // sentinelle finale
    while(t->suivant->donnee < v)
    {
        t = t->suivant;
    }
    return t;
}

Question 3.

Corrigé

On présente les listes sous le format usuel pour ce corrigé pour présenter les tests.

  • Test 1 : insertion de 0 dans une liste vide \([-\infty,\infty] \rightarrow [-\infty,0,\infty]\) et renvoie true.
  • Test 2 : insertion en première position de 0 dans une liste non vide : \([-\infty,1,\infty] \rightarrow [-\infty,0,1,\infty]\) et renvoie true.
  • Test 3 : insertion en dernière position de 2 dans une liste non vide : \([-\infty,1,\infty] \rightarrow [-\infty,1,2,\infty]\) et renvoie true.
  • Test 4 : insertion d'une valeur présente, ici 0 : \([-\infty, 0, 1, \infty]\) ne change pas et renvoie false.

Question 4.

Corrigé

Le problème vient du &t : comme t est un maillon_t *, on a &t qui est un maillon_t **, il n'y a pas besoin de prendre l'adresse de t. D'ailleurs, cette adresse est sur la pile même si le maillon désigné par t est sur le tas.

bool insere_errone(maillon_t *t, int v)
{
    maillon_t *p = localise(t, v);
    maillon_t *n = malloc(sizeof(maillon_t));
    n->suivant = p->suivant;
    n->donnee = v;
    p->suivant = n;
    return true;
}

Question 5.

Corrigé

Le test 4 n'est pas réussi car on va ajouter sans discernement : on obtiendra avec la version erronée \([-\infty, 0, 0, 1, \infty]\) et la valeur true.

bool insere(maillon_t *t, int v)
{
    maillon_t *p = localise(t, v);
    if (p->suivant->donnee == v)
        return false;
    maillon_t *n = malloc(sizeof(maillon_t));
    n->suivant = p->suivant;
    n->donnee = v;
    p->suivant = n;
    return true;
}

Question 6.

Corrigé 
bool supprime(maillon_t *t, int v)
{
    maillon_t *p = localise(t, v);
    if(p->suivant->donnee != v)
        return false;
    // ici on a p->suivant->donnee = v < oo donc
    // forcément ce maillon a un maillon suivant
    maillon_t *n = p->suivant->suivant;
    free(p->suivant);
    p->suivant = n;
    return true;
}

Question 7.

Corrigé

Mis à part localise, ces deux fonctions n'effectuent que des opérations élémentaires. Or, localise parcourant la liste, elle est en pire cas de complexité linéaire en la taille de la liste, en \(O(|l|)\), et ainsi insere et supprime le sont également.

Question 8.

Corrigé

On distingue trois parties :

  • les variables globales qui sont placées en mémoire en même temps que le programme ;
  • le tas qui contient la mémoire allouée dynamiquement ;
  • la pile qui se construit avec les appels de fonctions.

Ici, la variable v est définie en dehors de toute fonction, c'est une variable globale : la valeur 717 réside donc dans cette zone. Mais le passage par valeur la recopie aussi sur la pile (paramètre v de insere, puis de localise), et insere l'inscrit enfin dans le tas, dans le champ donnee du maillon alloué par malloc. La valeur 717 est donc inscrite dans les trois zones.

Note : il y a une distinction entre variables globales constantes et non constantes, les premières sont dans une zone marquée en lecture seule. Mais, comme const n'est pas au programme, je pense que c'est la réponse raisonnable de ne pas en parler.

Extensions des opérations de base

Question 9.

Corrigé

Un arbre binaire de recherche est un arbre binaire permettant de stocker un ensemble ordonné de valeurs. Dans un tel arbre, la valeur d'un nœud est toujours supérieure ou égale à toutes les valeurs de son sous-arbre gauche et inférieure ou égale à toutes les valeurs de son sous-arbre droit. Cela permet ainsi d'effectuer une recherche le long d'une branche et donc, avec une complexité linéaire en la hauteur de l'arbre.

Pour que cette complexité soit logarithmique dans le nombre de nœuds, il faut que l'arbre soit compact, de hauteur logarithmique : on parle d'arbre équilibré. On a vu que les arbres binaires de recherche rouges et noirs garantissaient cette propriété.

Question 10.

Corrigé

On effectue un parcours infixe de l'arbre binaire de recherche. Ici, l'enjeu est d'être capable de rajouter des maillons, en tête pour avoir une faible complexité.

On va donc faire en sorte que les insertions s'effectuent de droite à gauche dans l'arbre :

  • on initialise une liste vide avant de réaliser un parcours récursif ;
  • quand on est sur un nœud (g,x,d) :
    • on effectue un appel récursif sur d (important) ;
    • on insère x juste après la sentinelle de tête ;
    • on effectue un appel récursif sur g ;
  • quand on est sur une feuille, on ne fait rien.

Chaque insertion se fait en temps constant, puisque x est plus petit que toutes les valeurs déjà insérées. On construit alors la liste triée en \(O(|t|)\) où \(|t|\) est le nombre de nœuds de l'arbre binaire de recherche t. L'espace utilisé est celui de la pile d'appels, borné par la hauteur de l'arbre, et la liste construite. On a donc dans tous les cas une complexité en espace également en \(O(|t|)\).

Question 11.

Corrigé

On considère ici par \(i\)-ième qu'on commence à compter à 1. Comme il y a \(n\) éléments en tout, il y en a \(i-1\) avant le \(i\)-ième et \(n-i\) après.

Pour \(i \ge 2\), pour que le \(i\)-ième élément soit renvoyé, il faut avoir obtenu un résultat non nul au test effectué sur le \(i\)-ième élément et 0 aux \(n-i\) tests suivants, on a donc

\[ \mathbb{P}(i\text{-ième renvoyé}) = \frac{1}{2^{n-i+1}}. \]

Le premier élément est la valeur initiale de ret : il n'y a pas de test le concernant, et il est renvoyé si les \(n-1\) tests suivants donnent 0, avec probabilité \(\frac{1}{2^{n-1}}\). On vérifie que la somme vaut bien 1 : \(\frac{1}{2^{n-1}} + \sum_{i=2}^{n} \frac{1}{2^{n-i+1}} = \frac{1}{2^{n-1}} + 1 - \frac{1}{2^{n-1}} = 1\).

Question 12.

Corrigé

On va choisir ici de générer uniformément un indice d'un maillon puis de le chercher.

int random_elt(maillon_t *t)
{
    maillon_t *c = t->suivant;
    int ret = c->donnee;
    assert(ret != INT_MAX);
    int n = 0;
    maillon_t *p = c;
    while(p->donnee != INT_MAX)
    {
        n = n+1;
        p = p->suivant;
    }
    int k = random() % n;

    for(int i = 0; i < k; i++)
    {
        c = c->suivant;
    }

    return c->donnee;
}

Question 13.

Corrigé

Se pose le problème de la précision pour les tests d'égalité dans les insertions et suppressions. Doit-on considérer qu'il faut insérer une valeur très proche de 0 quand 0 est déjà présent dans la liste ?

Une manière de résoudre ce problème serait d'introduire une notion de seuil ou précision \(\epsilon\) et de remplacer le test d'égalité entre \(x\) et \(y\) par \(|x-y|\le \epsilon\).

Il faut aussi choisir de nouvelles sentinelles : INT_MIN et INT_MAX n'ont plus de sens, on peut utiliser \(-\infty\) et \(+\infty\) (-INFINITY et INFINITY de math.h), en excluant la valeur NAN qui n'est comparable à rien.

Listes à enjambement

Note : on parle de skip-list en anglais.

Question 14.

Corrigé

Las Vegas.

Question 15.

Corrigé

On utilise la déclaration du sujet :

struct chainon {
    int donnee;
    int hauteur;
    struct chainon **suivants;
};
typedef struct chainon chainon_t;

chainon_t *enjmb_init(void)
{
    chainon_t *l = malloc(sizeof(chainon_t));
    l->donnee = INT_MIN;
    l->hauteur = 1;
    l->suivants = malloc(sizeof(chainon_t *));

    chainon_t *p = malloc(sizeof(chainon_t));
    p->donnee = INT_MAX;
    p->hauteur = 1;
    p->suivants = malloc(sizeof(chainon_t *));
    p->suivants[0] = NULL;

    l->suivants[0] = p;

    return l;
}

Question 16.

Corrigé

Ici, il suffit de faire une libération normale de liste chaînée grâce au niveau 0. On doit juste faire attention à ne pas oublier la libération des tableaux de suivants, ni celle de la sentinelle de fin.

void enjmb_detruit(chainon_t *t)
{
    while(t != NULL)
    {
        chainon_t *temp = t->suivants[0];
        free(t->suivants);
        free(t);
        t = temp;
    }
}

Question 17.

Corrigé

Note : question de maths et pas d'informatique.

Comme \(H_i\) suit une loi géométrique de paramètre \(\frac{1}{2}\), on a \(\mathbb{P}(H_i = k) = (1-\frac{1}{2})^{k-1} \frac{1}{2} = \frac{1}{2^k}\).

Notons \(a_n = 3 \log_2 n\), de sorte que \(2^{a_n} = n^3\), et \(b_n\) le plus petit entier strictement supérieur à \(a_n\) : on a \(a_n < b_n \le a_n + 1\). Comme \(A_n\) est l'événement \(H_{max} > a_n\), c'est-à-dire \(H_{max} \ge b_n\), on a

\[ \begin{array}{rcl} \mathbb{E}(H_{max} \cdot 1_{A_n}) & = & \sum_{k=b_n}^{+\infty} k \mathbb{P}(H_{max} = k) \\ & \le & \sum_{k=b_n}^{+\infty} \sum_{i=1}^n k \mathbb{P}(H_i = k) \\ & = & \sum_{k=b_n}^{+\infty} n \frac{k}{2^k} \\ & = & n \frac{2(b_n+1)}{2^{b_n}} \\ & \le & n \frac{2(a_n+2)}{2^{a_n}} = \frac{2 n (3 \log_2 n + 2)}{n^3} \end{array} \]

Or \(\frac{2(3 \log_2 n + 2)}{n^2 \log_2 n} \sim \frac{6}{n^2} \rightarrow 0\), donc cette dernière majoration est un \(o(\log_2 n)\) et par majoration, on a \(\mathbb{E}(H_{max} \cdot 1_{A_n}) = o(\log_2 n)\).

Comme \(1 = 1_{A_n} + 1_{A_n^c}\), on a \(\mathbb{E}(H_{max}) = o(\log_2 n) + \mathbb{E}(H_{max} \cdot 1_{A_n^c})\).

Or, sur \(A_n^c\), \(H_{max} \le a_n\), donc

\[ \mathbb{E}(H_{max} \cdot 1_{A_n^c}) = \sum_{1 \le k \le a_n} k \mathbb{P}(H_{max} = k) \le a_n \sum_{1 \le k \le a_n} \mathbb{P}(H_{max} = k) \le a_n \]

Donc \(\mathbb{E}(H_{max} \cdot 1_{A_n^c}) = O(\log_2 n)\) et par additivité des \(O\), on a

\[ \mathbb{E}(H_{max}) = O(\log_2 n) \]

Question 18.

Corrigé

Note : question de maths et pas d'informatique.

En comptant une case par donnée et par pointeur de suivant, chaque sentinelle occupe \(H_{max} + 1\) cases et le chaînon contenant \(u_i\) en occupe \(1 + H_i\) (à une constante multiplicative près si on compte aussi le champ hauteur et le pointeur vers le tableau). On a donc \(S = 2 (H_{max}+1) + \sum_{i=1}^n (1 + H_i) = 2 H_{max} + n + 2 + \sum_{i=1}^n H_i\) donc

\[ \mathbb{E}(S) = 2 \mathbb{E}(H_{max}) + n + 2 + \sum_{i=1}^n \mathbb{E}(H_i) = 2 \mathbb{E}(H_{max}) + n + 2 + 2 n = O(\log_2 n + n) = O(n) \]

Comme de plus \(S \ge n\), l'espérance de \(S\) est bien linéaire en \(n\).

Question 19.

Corrigé

Notons qu'on a plusieurs possibilités pour implémenter cette fonction. Le choix que je fais ici ne semble pas être celui qu'avait en tête le concepteur du sujet mais cela me semble plus simple.

bool enjmb_contient(chainon_t *t, int v)
{
    int k = t->hauteur - 1;

    while(t->donnee < v)
    {
        if(k > 0 && t->suivants[k]->donnee > v) {
            k = k-1;
        } else {
            t = t->suivants[k];
        }
    }

    return t->donnee == v;
}

Question 20.

Corrigé

Note : question de maths avec un peu d'informatique.

La première partie de la question n'est pas si facile à justifier. On remarque que les maillons du niveau \(h\) sont aussi dans le niveau \(h+1\) avec probabilité \(\frac{1}{2}\). Pour compter \(R_h\), il faut compter le nombre de maillons de niveau \(h\) entre deux maillons du niveau \(h+1\), or cela revient effectivement à effectuer une loi géométrique tronquée de paramètre \(\frac{1}{2}\) avec \(Y\) indiquant ici le nombre maximum de maillons induit par le niveau supérieur. On a alors \(\mathbb{E}(R_h) \le 1\).

On avance dans les maillons en suivant les pointeurs, comme il y a \(n\) maillons, on a au maximum \(R' \le n\).

Sur \(A_n^c\), il y a au plus \(3 \log_2 n\) niveaux, donc \(\mathbb{E}(R' \cdot 1_{A_n^c}) \le \sum_{0 \le h < 3 \log_2 n} \mathbb{E}(R_h) \le 3 \log_2 n\). Ainsi,

\[ \mathbb{E}(R) \le \mathbb{E}(H_{max}) + 1 + \mathbb{E}(R' \cdot 1_{A_n^c}) + \mathbb{E}(R' \cdot 1_{A_n}) \le O(\log_2 n) + 1 + 3 \log_2 n + n \mathbb{P}(A_n) \]

Or

\[ n\mathbb{P}(A_n) = n\sum_{k > 3 \log_2 n} \mathbb{P}(H_{max}=k) \le n\sum_{k > 3 \log_2 n} \frac{n}{2^k} \le \frac{2n^2}{2^{3 \log_2 n}} = \frac{2n^2}{n^3} = \frac{2}{n} \rightarrow 0 \]

donc ce dernier terme est négligeable devant \(O(\log_2 n)\) et on a bien \(\mathbb{E}(R) = O(\log_2 n)\).

Note : ce choix du \(3 \log_2 n\) pour avoir une limite nulle ici ne semble pas très important. Avec \(2 \log_2 n\), on avait un \(O(1)\) qui était suffisant. C'est d'ailleurs ce choix qui est fait dans la preuve de Randomized Algorithms.

Question 21.

Corrigé

Dans le cas des arbres binaires de recherche, on a une complexité en pire cas en \(O(n)\), mais avec des ABR équilibrés, elle passe en \(O(\log_2 n)\) de manière déterministe. Ici, on a une complexité aléatoire, en \(O(\log_2 n)\) en moyenne.

Note : difficile d'en dire plus ici, on ne compare vraiment pas les mêmes choses.

Utilisation concurrente de listes chaînées

Question 22.

Corrigé

Si deux fils distincts exécutent insere en même temps au même endroit, on peut trouver des scénarios invalidant l'invariant 1 ou l'invariant 3.

  • Invariant 1 : si les deux fils insèrent la même valeur \(v\) absente, qu'ils localisent le même maillon p et effectuent tous deux le test p->suivant->donnee == v (qui échoue), puis que le premier fil finit de rajouter son maillon avant que le second ne lise p->suivant, le pointeur p->suivant auquel accédera le second fil sera le maillon nouvellement ajouté : on obtient deux maillons consécutifs de valeur \(v\), ce qui fait doublon.
  • Invariant 3 : si on ajoute deux maillons a et b après le maillon m qui était suivi de m', on peut avoir dans l'ordre : a->suivant = m'; b->suivant = m'; m->suivant = b; m->suivant = a. On obtient alors m->a->m' et le maillon b, qui pointe vers m', n'est plus accessible depuis la tête : sa valeur n'est pas dans la liste alors que l'insertion a renvoyé true.

L'invariant 2, lui, est préservé : les sentinelles ne sont jamais modifiées ni déplacées par insere.

Exclusion mutuelle à gros grains

Question 23.

Corrigé

Attention à bien lire le type ici et à ne pas tout recoder. On utilise la déclaration du sujet :

#include <pthread.h>

struct liste_grosgrain {
    maillon_t *tete;
    pthread_mutex_t verrou;
};
typedef struct liste_grosgrain liste_grosgrain_t;

bool grosgrain_insere(liste_grosgrain_t *l, int v)
{
    pthread_mutex_lock(&l->verrou);
    bool res = insere(l->tete, v);
    pthread_mutex_unlock(&l->verrou);
    return res;
}

Question 24.

Corrigé

Comme la structure liste_grosgrain contient un pthread_mutex_t directement, celui-ci sera copié en même temps que la liste sur la pile d'appels en cas de passage par valeur. Chaque fil aura alors sa propre copie du mutex sans aucune garantie de synchronisation entre les deux copies.

En passant la liste par pointeur, on s'assure que les deux fils utilisent le même mutex. Notons qu'on aurait pu mettre un pthread_mutex_t * dans la liste pour ne pas avoir ce problème.

Question 25.

Corrigé

Note : attention, le cast de la ligne 50 est hors programme et inutile en C.

Il n'y a qu'un seul verrou et aucun fil n'attend autre chose que ce verrou, qui est toujours relâché à la fin de chaque opération : il ne peut pas y avoir d'interblocage, chaque fil va ainsi terminer et le programme lui-même termine.

Chaque entier \(i\) est inséré une seule fois (par le fil \(i\)) et on tente de le supprimer une seule fois (par le fil \(i-1 \bmod n\)). Il est donc présent à la fin si et seulement si la tentative de suppression a eu lieu avant l'insertion.

Le cas \(\ell = n\) est impossible. Sinon, pour tout \(i\), la suppression de \(i\) par le fil \(i-1\) précède l'insertion de \(i\) par le fil \(i\), qui précède elle-même (ordre du programme) la suppression de \(i+1\) par le fil \(i\). En faisant le tour des indices modulo \(n\), on obtiendrait que la suppression de \(0\) par le fil \(n-1\) se précède strictement elle-même, ce qui est absurde.

Le cas \(\ell = 0\). Si chaque fil effectue son insertion, puis que chaque fil effectue sa suppression, toutes les suppressions réussissent et la liste est vide.

Les cas \(\ell \in \range{1}{n-1}\). Pour que la liste contienne \(\ell\) éléments à la sortie, il faut avoir échoué sur \(\ell\) suppressions. En considérant une exécution séquentielle des fils, les \(\ell\) premiers fils (de \(0\) à \(\ell-1\)) peuvent, dans cet ordre, insérer leur valeur puis échouer à supprimer la suivante, qui n'est pas encore présente. Ensuite, les fils suivants font la même chose mais en partant du dernier (\(n-1\)) jusqu'au fil \(\ell\), ce qui garantit le succès de leurs suppressions (le fil \(n-1\) supprime \(0\), inséré par le fil \(0\)). À la fin, la liste contient exactement \(1, \dots, \ell\).

Question 26.

Corrigé

Chaque fil peut supprimer son premier entier et il est donc possible qu'ils se retrouvent tous simultanément dans la deuxième boucle while, chacun attendant de pouvoir supprimer l'entier qu'un autre fil a déjà supprimé et ne réinsérera qu'après être lui-même sorti de cette boucle : il y a ainsi interblocage (une attente active infinie) et le programme ne termine pas.

Lorsque l'exécution termine, en revanche, la liste contient forcément les \(n\) entiers : pour chaque entier \(i\), chacune des deux suppressions effectives de \(i\) (par les fils \(i\) et \(i-1\)) est suivie, dans le même fil, d'une insertion de \(i\). La dernière opération sur \(i\) est donc une insertion, et \(i\) est présent à la fin. Seul \(\ell = n\) est donc possible.

Exclusion mutuelle à grains fins

Question 27.

Corrigé

On utilise la déclaration du sujet :

struct maillon_protege {
    int donnee;
    struct maillon_protege *suivant;
    pthread_mutex_t verrou;
};
typedef struct maillon_protege maillon_protege_t;

maillon_protege_t *grainfin_localise(maillon_protege_t *t, int v)
{
    pthread_mutex_lock(&t->verrou);

    // attention à le faire avant le
    // test, sinon il a pu changer

    pthread_mutex_lock(&t->suivant->verrou);
    while(t->suivant->donnee < v)
    {
        pthread_mutex_unlock(&t->verrou);
        t = t->suivant;
        pthread_mutex_lock(&t->suivant->verrou);
    }
    pthread_mutex_unlock(&t->suivant->verrou);
    return t;
}

Question 28.

Corrigé

Si un fil A attend un verrou acquis par le fil B, c'est forcément que B est plus loin dans localise, donc il ne peut dépendre de maillons acquis par A. Notons que cet argument ne fonctionnerait plus avec une liste circulaire.

Remarque : on peut facilement prouver le cas général.

Pour qu'il y ait interblocage, comme les verrous ont de bonnes propriétés, c'est nécessairement qu'il y a un fil A qui attend un verrou possédé par un fil B qui lui-même attend un autre verrou pour le déverrouiller.

Cela signifierait qu'on ait une chaîne \(m_1 \rightarrow m_2 \rightarrow m_3\) avec \(m_1\) acquis par A et \(m_2\) acquis par B, A qui attend \(m_2\) et B qui attend \(m_3\). B lui-même, pour être bloqué, a besoin d'un fil C qui a acquis \(m_3\) et attend le maillon suivant...

Comme la liste est finie, cette situation ne peut perdurer, il y a forcément un fil qui rompt la chaîne de blocage car il ne veut pas attendre le maillon suivant car la condition du while n'est plus vérifiée (elle l'est au plus tard sur la sentinelle de fin, de valeur INT_MAX \(> v\)).

Question 29.

Corrigé
  • Invariant 1 : si on insère la même valeur, les deux fils ne peuvent sortir de localise avec le même maillon en même temps, car un des deux fils l'aura verrouillé avant de faire l'insertion puis de le libérer. Suite à cela, l'autre fil, qui est encore dans le while, va voir le maillon nouvellement inséré comme suivant du maillon renvoyé. Cela va alors placer le fil dans le cas de non insertion.
  • Invariant 3 : on rajoute un nouveau maillon en verrouillant le maillon précédent, ce qui oblige à ce que les deux raccords soient valides et à ce que la structure de la liste soit préservée.

Question 30.

Corrigé

Tout d'abord, on remarque que l'utilisation d'une liste à gros grains revient à supprimer toute possibilité de concurrence dans les parcours : cela revient à réaliser une file de valeurs à traiter dont on doit barrer les multiples.

Avec une liste à grains fins, plusieurs fils peuvent supprimer des nombres en même temps : pendant que le fil supprime le multiple 9 de 3, un autre fil peut supprimer le multiple 12 de 2. Quand le fil des multiples de 3 avancera, il ne trouvera pas 12 à supprimer. Le désavantage ici va être la synchronisation forcée entre deux fils n'ayant aucun multiple en commun, qui doivent se suivre maillon par maillon.

Pour que le fil principal ne rencontre que des nombres premiers, il doit réaliser une attente du thread barrant les multiples de \(p\) avant de rencontrer \(p^2\) (les autres multiples ayant déjà été barrés si on procède ainsi).

Les suppressions effectives ne vont pas être réparties équitablement car un nombre composé avec un petit diviseur premier sera barré très tôt. Or, il y a une moitié de multiples de 2, un tiers de multiples de 3... Les threads barrant les multiples de grands premiers pourraient n'avoir que très peu de travail effectif de suppression.