J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

Mines Informatique 1 MPI 2023

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Logo mines
🔗 Explorer
Banque
Mines
Année
2023
Filière
MPI
Matière
Info
Mines MPIMines 2023MPI InfoInfo 2023
2025_08_29_788565882374c622161cg

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

Concours Mines-Télécom

CONCOURS 2023

PREMIÈRE ÉPREUVE D'INFORMATIQUE

Durée de l'épreuve : heures

L'usage de la calculatrice et de tout dispositif électronique est interdit.
Les candidats sont priés de mentionner de façon apparente sur la première page de la copie :

INFORMATIQUE I - MPI

L'énoncé de cette épreuve comporte 9 pages de texte.
Cette épreuve concerne uniquement les candidats de la filière MPI.
Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre.

Préliminaires

Présentation du sujet

L'épreuve est composée d'un problème unique comportant 32 questions divisées en trois sections. L'objectif du problème est de construire des listes à accès direct : une liste à accès direct est un type de donnée abstrait qui permet, d'une part, d'empiler et de dépiler efficacement un élément en tête de liste et, d'autre part, d'accéder efficacement au élément de la liste, pour n'importe quel indice valide.
Dans la première section (page 1), nous étudions un système de numération : la représentation binaire gauche des entiers naturels. Dans la deuxième section (page 4), nous étudions les arbres binaires parfaits. Dans la troisième section (page 6), nous implémentons le type liste à accès direct par la structure de données concrète liste gauche, que nous construisons en exploitant les résultats obtenus dans les sections précédentes.
Dans tout l'énoncé, un même identificateur écrit dans deux polices de caractère différentes désignera la même entité, mais du point de vue mathématique avec la police en italique (par exemple ) et du point de vue informatique avec celle en romain avec espacement fixe (par exemple n).

Travail attendu

Pour répondre à une question, il est permis de réutiliser le résultat d'une question antérieure, même sans avoir réussi à établir ce résultat. Des rappels de programmation sont faits en annexe et peuvent être utilisés directement.
Selon les questions, il faudra coder des fonctions à l'aide du langage de programmation C exclusivement, en reprenant le prototype de fonction fourni par le sujet, ou en pseudo-code (c-à-d. dans une syntaxe souple mais conforme aux possibilités offertes par le langage C ). Il est inutile de rappeler que les entêtes <assert.h>, <stdbool.h>, etc. doivent être inclus.
Quand l'énoncé demande de coder une fonction, sauf indication explicite de l'énoncé, il n'est pas nécessaire de justifier que celle-ci est correcte ou de tester que des préconditions sont satisfaites. On suppose que le type int n'est jamais sujet à des débordements.
Le barème tient compte de la clarté des programmes : nous recommandons de choisir des noms de variables intelligibles ou encore de structurer de longs codes par des blocs ou par des fonctions auxiliaires dont on décrit le rôle. Lorsqu'une réponse en pseudo-code est permise, seule la logique de programmation est évaluée, même dans le cas où un code en C a été fourni en guise de réponse.

1. Représentation binaire gauche des entiers naturels

1.1. Mise en place

Soient un entier naturel et un entier naturel non nul. Il est classique d'appeler représentation binaire standard de l'entier sur chiffres, ou plus simplement représentation standard, toute suite finie de longueur telle que, pour tout indice compris entre 0 et , le chiffre appartient à et l'égalité suivante est vérifiée
Définition : Nous appelons représentation binaire gauche de l'entier sur chiffres toute suite finie de longueur telle que,
(i) pour tout indice compris entre 0 et , le chiffre appartient à ,
(ii) l'égalité suivante est satisfaite
(iii) le chiffre « 2 » n'apparaît qu'au plus une fois parmi les chiffres ,
(iv) s'il existe une position tel que le chiffre est 2 , alors, pour tout indice compris entre 0 et , le chiffre est nul.
De manière plus courte, nous parlons simplement de représentation gauche.
La figure 1 ci-dessous donne une représentation standard et une représentation gauche sur quatre chiffres des seize premiers entiers. Conformément à l'usage habituel, nous écrivons toute représentation, qu'elle soit standard ou gauche, sous la forme d'un mot ou dans lequel les chiffres de poids faibles sont écrits à droite.
Entier Repr. standard Repr. gauche
0 0000 0000
1 0001 0001
2 0010 0002
3 0011 0010
4 0100 0011
5 0101 0012
6 0110 0020
7 0111 0100
Figure 1 - Représentations standard et gauche des seize premiers entiers
Entier Repr. standard Repr. gauche
8 1000 0101
9 1001 0102
10 1010 0110
11 1011 0111
12 1100 0112
13 1101 0120
14 1110 0200
15 1111 1000
Figure 1 - Représentations standard et gauche des seize premiers entiers
1 - Soit un entier. Donner la représentation standard de l'entier dont une représentation gauche est (avec chiffres nuls) en justifiant sommairement. Faire de même avec l'entier dont une représentation gauche est (avec chiffres nuls).
- Déterminer, en justifiant, le plus grand entier naturel qui admet une représentation gauche sur chiffres. Préciser la représentation gauche de cet entier.
Définition : Soit un indice compris entre 0 et . On dit que l'indice est la position du chiffre de plus fort poids d'une représentation si l'indice est le plus petit entier tel que, pour tout indice , le chiffre est nul. On appelle le chiffre le chiffre de plus fort poids.
- Soient un entier naturel non nul, et deux représentations gauches d'un même entier . Démontrer que les chiffres de plus fort poids de et de sont de même valeur et à la même position.
- Démontrer que tout entier appartenant à l'intervalle , où l'entier a été introduit à la question 2, ne possède au plus qu'une seule représentation gauche sur chiffres.
Indication C : L'entier est déclaré comme constante globale. Nous utilisons la structure C déclarée comme suit pour écrire la représentation gauche sur chiffres d'un entier :
const int N = 8;
struct RepGauche {
    int position;
    bool chiffres[N];
};
typedef struct RepGauche rg;
Le champ position repère la position éventuelle du chiffre 2 ; il vaut -1 au cas où le chiffre 2 n'apparaît pas. Pour tout indice compris entre 0 et , la case du champ chiffres vaut true si le chiffre est non-nul et vaut false sinon.
Par exemple, les entiers 15 et 21 ont pour représentation gauche les variables entier_15 et entier_21 suivantes :
rg entier_15 = { .position = -1,
    .chiffres = { 0, 0, 0, 1, 0, 0, 0, 0 } };
rg entier_21 = { .position = 1,
    .chiffres = { 0, 1, 0, 1, 0, 0, 0, 0 } };
5 - Formaliser sous la forme d'un ou de plusieurs invariants le fait qu'une valeur C de type rg est la représentation gauche d'un entier.
6 - Écrire une fonction C int rg_to_int (rg g), qui renvoie l'entier dont est la représentation gauche. On supposera que l'invariant de la question 5 est satisfait.

1.2. Incrémentation et décrémentation

Nous proposons l'algorithme suivant :

Algorithme mystère :

Entrée : Représentation gauche d'un certain entier .
Effet :
  • Si aucun des chiffres ne vaut 2 , changer le chiffre en .
  • Sinon, en notant la position du chiffre 2 , changer le chiffre en 0 et le chiffre en .
    Nous notons l'entier dont la représentation gauche est après exécution de l'algorithme.
Figure 2 - Un algorithme
7 - Vérifier que l'invariant de la question 5 n'est pas rompu par l'algorithme mystère (cf. figure 2). Avec les notations et de la figure 2, caractériser, en fonction de l'entier , la valeur de l'entier .
- Écrire une fonction C bool rg_incr( ) dont la spécification suit :
Précondition : La variable est un pointeur vers la représentation gauche d'un entier .
Effet : La valeur pointée par est modifiée afin de représenter l'entier .
Valeur de retour : Booléen true si l'incrémentation de peut avoir lieu et false si un débordement se produit car n'est pas représentable sur le même nombre de chiffres.
- Calculer la complexité en temps dans le pire des cas de la fonction rg_incr en fonction de . Comparer avec la complexité de la même opération sur la représentation standard.
10 - Écrire une fonction C bool rg_decr(rg *s) dont la spécification suit :
Précondition : Le pointeur désigne la représentation gauche d'un entier .
Effet : La valeur pointée par est modifiée afin de représenter l'entier .
Valeur de retour : Booléen true si la décrémentation de peut avoir lieu et false si un débordement se produit car est nul.
Il est recommandé d'expliquer son intention avant de donner son code.

2. Arbres binaires parfaits

2.1. Opérations sur les arbres binaires

Indication C: Nous représentons des arbres binaires à valeurs entières au moyen du type C arb suivant, qui est un pointeur vers une structure contenant la valeur entière dans le champ valeur et les deux fils dans les champs fils_g et fils_d. L'arbre vide se représente par le pointeur NULL.
typedef struct Noeud *arb;
struct Noeud {
    int valeur;
    arb fils_g;
    arb fils_d;
};
L'arbre vide est, par convention, de hauteur -1 .
- Écrire une fonction C int hauteur (arb a) qui calcule la hauteur de l'arbre .
- Écrire une fonction C arb noeud(int v , arb ag, arb ad) qui construit un arbre dont la racine a pour étiquette , dont le fils gauche est et le fils droit est . Dans cette question, il est demandé de se défendre, par le truchement d'une assertion, de toute erreur liée à un échec d'allocation dynamique de mémoire.

Figure 3 - Arbres binaires parfaits de hauteur 2 et de hauteur 3.

2.2. Arbres parfaits

Définition : Un arbre binaire parfait, ou simplement arbre parfait, est un arbre binaire dont tous les nœuds internes ont exactement deux fils, dont toutes les feuilles sont à la même profondeur et dont les nœuds sont étiquetés par des valeurs entières.
Des exemples d'arbres binaires parfaits sont donnés figure 3.
13 - Démontrer que tout arbre binaire parfait de hauteur possède nœuds.
14 - Écrire une fonction C bool est_parfait(arb a, int n) dont la spécification suit : Précondition : Le pointeur désigne la racine d'un arbre binaire (dont les nœuds sont bien tous distincts).
Valeur de retour : Booléen true si l'arbre pointé est parfait de hauteur et false sinon.
15 - Calculer la complexité en temps dans le pire des cas de l'exécution de est_parfait(a, n) en fonction de l'entier .

2.3. Opérations sur les arbres parfaits

Définition : Soient une structure de données qui permet de stocker une collection d'entiers et le cardinal de . Nous disons que la structure de données est à accès direct s'il existe une manière systématique de numéroter chaque élément de entre 0 et et s'il existe deux primitives, acces et modif, qui permettent respectivement de consulter et de modifier n'importe quel élément de en temps logarithmique en à partir seulement de son numéro.
Nous souhaitons vérifier qu'un arbre parfait est une structure de données à accès direct. Nous numérotons les éléments d'un arbre parfait en utilisant l'ordre préfixe de gauche à droite de l'arbre (comme illustré dans la figure 3).
- Écrire une fonction C arb arb_trouve (arb a, int n , int k ) ainsi spécifiée :
Précondition : Le pointeur a désigne la racine d'un arbre binaire parfait de hauteur .
L'entier satisfait les inégalités .
Valeur de retour : Pointeur vers le nœud de l'arbre dans l'ordre préfixe.
Il est rappelé que la racine d'un arbre est à profondeur 0 . Nous donnons la formule de sommation, valable pour tout réel et tout entier ,
17 - Nous appelons la profondeur d'un nœud choisi aléatoirement et uniformément parmi les nœuds d'un arbre binaire parfait de hauteur . Calculer l'espérance de la variable aléatoire .
- Déterminer la complexité moyenne en temps de l'instruction arb_trouve(a, n, k) lorsque la hauteur et l'arbre sont fixés et le numéro est choisi aléatoirement et uniformément dans l'intervalle .
- Écrire une fonction int arb_acces(arb a, int , int ) qui renvoie la valeur de l'arbre de hauteur ainsi qu'une fonction C void arb_modif (arb a, int n , int k , int v ) qui remplace la valeur de l'arbre de hauteur par la valeur . Dire finalement si la structure de données arbre binaire parfait est à accès direct.

3. Listes gauches

Les arbres binaires parfaits seuls ne permettent de représenter que des collections d'entiers dont le cardinal est de la forme où est entier naturel. Afin de représenter des collections de cardinal quelconque, nous introduisons des suites d'arbres parfaits, aux hauteurs strictement croissantes et savamment choisies.
Définition : Nous appelons liste binaire gauche de cardinal sur arbres la structure de données constituée de arbres binaires parfaits comme suit. Nous décomposons l'entier selon sa représentation binaire gauche sur chiffres : . Pour tout indice compris entre 0 et , si le chiffre n'est pas nul, l'arbre binaire parfait est un arbre de hauteur , sinon il s'agit de l'arbre vide. Si le chiffre 2 apparaît parmi les chiffres de la représentation gauche de et si l'indice est sa position, alors l'arbre est un arbre binaire parfait de hauteur , sinon l'arbre est l'arbre vide. De manière plus courte, nous parlons simplement de liste gauche.
Une liste binaire gauche de cardinal sur arbres permet de stocker une collection de éléments entiers. Il apparaît qu'avec arbres, une liste binaire gauche peut stocker jusqu'à entiers (où l'entier a été introduit à la question 2) et que est inférieur à .
Indication C : Nous adoptons le type C suivant
struct ListeGauche {
    int hauteur_e;
    arb extra;
    int nb_arbres;
    arb *arbres;
};
typedef struct ListeGauche lg;
Le champ hauteur_e contient la hauteur de l'arbre exceptionnel . Le champ extra désigne la racine de l'arbre exceptionnel . Le champ nb_arbres contient l'entier . Enfin, le champ arbres désigne un tableau de pointeurs vers les arbres qui a été alloué dynamiquement.

3.1. Opérations simples sur les listes gauches

20 - Écrire une fonction C lg init (int N) qui renvoie une liste gauche de cardinal nul sur arbres.
21 - Écrire une fonction C int card qui calcule le cardinal de la liste gauche .
Définition : Afin de numéroter l'ensemble des éléments d'une liste gauche , nous parcourons d'abord les éléments de l'arbre exceptionnel dans l'ordre préfixe, puis nous parcourons les éléments des arbres dans l'ordre préfixe. Les numéros sont attribués aux valeurs rencontrées par ordre de première rencontre.
22 - Écrire une fonction C arb trouve ( , int k ) qui renvoie le nœud de la liste gauche . On supposera que est un indice valide .
23 - Calculer la complexité en temps dans le pire des cas de lg_trouve 1 en fonction de la capacité maximale de la liste gauche .
24 - Écrire une fonction C int acces qui renvoie la valeur de la liste gauche ainsi qu'une fonction C void modif , int k , int v qui remplace la valeur de la liste gauche par la valeur .

3.2. Ajout et suppression en tête de liste gauche

25 - Soient une valeur entière et une liste gauche de cardinal , avec , qui contient les éléments dans cet ordre. Décrire, en fonction de la liste gauche , la liste gauche de cardinal dont les éléments sont , dans cet ordre. En déduire le principe d'une fonction C bool empile int l) réalisant l'insertion de la valeur en tête de la liste gauche où le booléen résultat vaut true si l'ajout a eu lieu et vaut false si un débordement de capacité de la liste se produit. On ne demande pas le code complet de cette fonction.
26 - Déterminer la complexité en temps dans le pire des cas de la fonction lg_empile.
27 - Donner le principe d'une fonction C bool lg_depile(int *w, lg l) réalisant le retrait de l'élément de tête de la liste gauche et son affectation à l'adresse . Le booléen résultat vaut true si le retrait a eu lieu et vaut false si l'opération a échoué en raison d'une liste vide. On ne demande pas le code complet.
28 - Donner la complexité en temps dans le pire des cas de la fonction lg_depile.
29 - Discuter la possibilité d'obtenir une complexité plus faible à la question 28, quitte à modifier légèrement la définition du type lg .
- Soit un entier et une liste gauche. Discuter la possibilité de modifier en place et avec une faible complexité en temps la liste gauche de sorte que le nombre d'arbres devienne et que les mêmes éléments demeurent dans la liste.

3.3. Utilisation concurrente des listes gauches

Dans cette sous-section, on raisonne sur les algorithmes en supposant que les fils d'exécution peuvent s'entrelacer mais que les instructions d'un même fil s'exécutent dans l'ordre du programme. L'entête #include <pthread.h> a été déclarée; la syntaxe de certaines fonctions s'y rattachant est rappelée en annexe.
- Deux fils d'exécution distincts exécutent la fonction lg_empile sur la même liste gauche. Montrer qu'une course critique advient de leur exécution concurrente et que la cohérence de ladite liste gauche n'est pas garantie, autrement dit que certains invariants qui caractérisent la bonne formation d'une liste gauche peuvent être violés à l'issue des exécutions.
Nous nous intéressons finalement au problème des producteurs et des consommateurs qui s'échangent des entiers au travers d'un tampon, ici constitué par une unique liste gauche à arbres, l'entier étant fixé à l'avance. Les producteurs écrivent dans la liste gauche en empilant un entier à la fois en tête, à condition que la liste gauche ne soit pas pleine; les consommateurs vident la liste gauche en dépilant l'entier en tête de la liste, à condition que la liste gauche ne soit pas vide.
Un seul agent peut accéder au tampon à la fois. Lorsqu'un consommateur souhaite supprimer une donnée alors que le tampon est vide, il est mis en attente ; lorsqu'un producteur souhaite écrire une donnée alors que le tampon est plein, il est mis en attente.
- Décrire une solution au problème des producteurs et des consommateurs en s'appuyant sur un verrou et sur deux sémaphores. Détailler sous la forme de code C ou bien de pseudo-code ce que font les producteurs et les consommateurs.
Les listes binaires gauches, ou skew binary lists, ont été inventées par Eugene Myers en 1983.

A. Rappels de programmation en C

L'expression représente le décalage de la valeur 1 sur bits : elle a pour valeur l'entier .
Le type pthread_t désigne des fils d'exécution.
L'instruction pthread_create(pthread_t *th_id, NULL, &ma_fonction, void *args) crée un nouveau fil d'exécution qui appelle la fonction ma_fonction sur le ou les arguments désignés par args et qui s'exécute simultanément avec le fil d'exécution appelant.
L'instruction pthread_join(th_id, NULL) suspend l'exécution du fil d'exécution appelant jusqu'à ce que le fil d'exécution identifié par th_id achève son exécution.
Le type pthread_mutex_t désigne des verrous.
L'instruction pthread_mutex_lock(&v) verrouille le verrou v.
L'instruction pthread_mutex_unlock(&v) déverrouille le verrou v.
Le type sem_t désigne des sémaphores.
L'instruction sem_init(&s, 0, v) initialise le sémaphore s à la valeur avec .
L'instruction sem_wait(&s) décrémente le compteur du sémaphore s : si le compteur est toujours positif, l'appel se termine; sinon le fil d'exécution appelant est bloqué.
L'instruction sem_post(&s) incrémente le compteur du sémaphore s et, si le compteur redevient strictement positif, réveille un fil d'exécution bloqué sur .
Fin de l'épreuve
Mines Informatique 1 MPI 2023 - Version Web LaTeX | WikiPrépa | WikiPrépa