2025-Inp-Info-Mpi-Corrigé

Partie I – Grammaire non contextuelle

Soit la grammaire non contextuelle {G=(\Sigma,V,P,S)}, l’ensemble des règles de production P étant défini par : {\begin{array}{l}S\to SaS\mid A,\\[8pt]A\to AbA\mid B,\\[8pt]B\to BcB\mid\varepsilon.\end{array}} où {\Sigma} (respectivement V) est l’ensemble de symboles terminaux (respectivement non terminaux),{S\in V} est le symbole initial de G et {\varepsilon} dénote le mot vide. Soit u le mot abc.

Une grammaire est dite récursive gauche directe si elle possède une règle de la forme {A\to A\alpha}, où {\alpha} est une suite de symboles terminaux et non terminaux. A est dite variable récursive gauche.

Une telle grammaire pose divers problèmes en analyse syntaxique descendante, on cherche alors à éliminer cette récursivité. Ceci est toujours possible pour les langages réguliers.

Pour éliminer la récursivité gauche, on utilise l’algorithme suivant : Soit {A\to A\alpha\mid\beta} une règle, où {\alpha} est une suite de symboles terminaux et non terminaux et {\beta} est une suite de symboles terminaux et non terminaux ne commençant pas par A.

On remplace cette règle par : (i). une règle commençant par A : {A\to\beta A'}, (ii). une règle pour une nouvelle variable {A'} : {A'\to\alpha A'\mid\varepsilon}.

Partie II – Problème de bin-packing

Cette partie comporte des questions nécessitant un code OCaml. Soient {n,k\in\mathbb N^2}. On appelle rangement de n objets dans k boîtes une fonction {R:[\![1,n]\!]\to[\![1,k]\!]}. L’ensemble {B_j=R^{-1}(j)=\{i\in[\![1,n]\!],R(i)=j\}} est le contenu de la boîte {j\in[\![1,k]\!]}.

Étant données des tailles {a=(a_1\cdots a_n)\in(\mathbb Q\cap]0,1])^n}, ai étant la taille de l’objet i, on dit qu’un rangement R de n objets dans k boîtes est valide pour les tailles a si pour tout {j\in[\![1,k]\!]} on a {\sum_{i\in B_j}a_i\le1.} On considère alors le problème de décision BIN-PACKING qui, étant donnés {n,k\in\mathbb N^2} et {a\in(\mathbb Q\cap]0,1])^n}, décide s’il existe un rangement R de n objets dans k boîtes valide pour les tailles a.

On peut décrire une solution de ce problème par un couple (k, R).

Soit le problème PARTITION suivant : Pour n entiers {c_1\cdots c_n}, existe-t-il un sous-ensemble S de {[\![1,n]\!]}, tel que {\sum\limits_{i\in S}c_i=\sum\limits_{i\notin S}c_i} ? On admet que le problème PARTITION est NP-complet.

On s’intéresse par la suite au problème MIN-BIN-PACKING qui demande de déterminer le plus petit k pour lequel il existe un rangement R de n objets de taille a dans k boîtes.

On introduit pour résoudre ce problème une heuristique dite Premier Casier Décroissant (algorithme 2), se basant sur l’heuristique Premier Casier décrite dans l’algorithme 1.

Dans cet algorithme, le rangement R est modélisé par une liste de boîtes L. Algorithme 1 – Algorithme Premier Casier Entrées : {n\in\mathbb N}, {(a_1\cdots a_n)\in(\mathbb Q\cap]0,1])^n}

Sorties : Une solution {(k,R)}

Algorithme 2 – Algorithme Premier Casier Décroissant Entrées : {n\in\mathbb N}, {(a_1\cdots a_n)\in(\mathbb Q\cap]0,1])^n}

Sorties : Une solution {(k,R)}

Nous allons montrer que l’algorithme Premier Casier Décroissant est une {\frac32}-approximation pour le problème MIN-BIN-PACKING.

On note dans la suite k le nombre de boîtes retournées par l’algorithme 2, {k^\ast} le nombre de boîtes optimal (défini comme le nombre minimal de boîtes permettant de répondre au problème MIN-BIN- PACKING) et {k_1=\lceil2k/3\rceil}, où {\lceil\cdot\rceil} désigne la partie entière supérieure. {B_{k_1}} fait référence à la boîte déduite du rangement renvoyé par l’algorithme 2.

On définit des types record pour représenter les objets et les boîtes en OCaml :

Partie III – Algorithmes de couplage

Cette partie comporte des questions nécessitant un code en C. On s’intéresse ici à un problème d’appariement entre deux groupes d’individus U et V, que l’on suppose de même cardinalité n.

On cherche à apparier les éléments de V aux éléments de U, chaque élément devant être apparié à exactement un élément de l’autre ensemble. Chaque élément de V (respectivement de U) a, de plus, un ordre de préférence total entre tous les éléments de U (respectivement de V).

Définition 1 (Couplage, couplage parfait)

Un ensemble de paires {A\subseteq V\times U} est un couplage si tout {x\in V} et tout {y\in U} apparaissent dans au plus un élément de A. Le couplage est dit parfait si tout {x\in V} et tout {y\in U} apparaissent dans un et un seul élément de A.

Notations

Dans toute la suite on notera : – {|E|} le cardinal de l’ensemble E,

– {>_x} l’ordre associé à l’élément x ∈ {V\cup U} : si {u_1\in U} préfère strictement {v_1\in V} à {v_2\in V} alors {v_1>_{u_1}v_2}. Par extension, on définit de même la notion de préférence {\ge_x}.

– {m_A(x)} le partenaire de x ∈ {V\cup U} dans le couplage parfait A.

Définition 2 (Couplage parfait stable)

Un couplage parfait A est dit stable si, pour tous couples (v1, u1) et (v2, u2) de A, il est impossible que l’on ait {u_2>_{v_1}u_1} et {v_1>_{u_2}v_2}.

Définition 3 (Pareto-optimalité)

Soient A et {A'} deux couplages parfaits stables et E ⊆ {V\cup U}. On dit que A Pareto-domine {A'} sur E si et seulement si pour tout x ∈ E, {m_A(x)} {\ge_x} m {A'} (x) et il existe x ∈ E tel que {m_A(x)} {>_x} m {A'} (x) . Un couplage est Pareto-optimal s’il est stable et n’est pas Pareto dominé sur {V\cup U}.

En économie, la Pareto-optimalité d’un système exprime le fait que l’on ne peut améliorer la satisfaction d’un individu du système sans diminuer la satisfaction d’un autre.

III.1 – Recherche de couplages stables

L’algorithme de Gale–Shapley (algorithme 3) permet de montrer qu’il existe toujours au moins un couplage parfait stable et d’en trouver un de façon efficace. L’idée de l’algorithme est tout d’abord de choisir un des deux ensembles (ici pour illustration V).

Les éléments de V font des propositions aux éléments de U. Quand un élément de V fait une proposition à un élément de U, celui-ci peut soit la refuser définitivement, soit l’accepter provisoirement en attendant une éventuelle meilleure offre.

Toute nouvelle acceptation vaut rejet définitif des propositions précédemment acceptées. Algorithme 3 – Algorithme de Gale-Shapley Entrées : {n=|V|=|U|}, les listes de préférences des éléments de {V} et {U}

Sorties : Un couplage parfait stable {A}

Soit le jeu de données D suivant : {V=\{v_1,v_2,v_3\}}, {U=\{u_1,u_2,u_3\}} et : {\begin{array}{c|c}V&U\\[8pt]u_2>_{v_1}u_1>_{v_1}u_3&v_1>_{u_1}v_3>_{u_1}v_2\\[8pt]u_1>_{v_2}u_2>_{v_2}u_3&v_2>_{u_2}v_1>_{u_1}v_3\\[8pt]u_1>_{v_3}u_2>_{v_3}u_3&v_2>_{u_3}v_1>_{u_3}v_3\end{array}}

Pour des préférences données, il peut exister plus d’un couplage parfait stable. Soient A et {A'} deux tels couplages pour un problème donné. On dira qu’un élément de {V\cup U} préfère A à {A'} s’il n’a pas le même partenaire dans les deux couplages et s’il préfère celui de A à celui de {A'}.

On peut montrer qu’en même temps le partenaire u′ de v dans {A'} préfère A. La correction de l’algorithme de Gale-Shapley ne dépend pas de l’élément {v\in V} qui fait sa proposition à chaque tour.

En fait, on montre dans la suite que, quel que soit l’élément {v\in V} non encore apparié qui fait une proposition à chaque tour, l’algorithme calcule toujours le même couplage parfait stable.

Dans la suite, on dira qu’un élément {u\in U} est réalisable pour un élément {v\in V} s’il existe un couplage parfait stable qui contient (v, u).

Soit M(v) ∈ U l’élément réalisable le mieux classé sur la liste des préférences dev et P(u) ∈ V l’élément réalisable le moins bien classé sur la liste des préférences de u. On note enfin {A^\ast} = {(v, M(v)), {v\in V}}.

Ainsi, l’algorithme calcule le meilleur couplage parfait stable possible du point de vue des éléments de V. Il s’avère également que l’algorithme de Gale-Shapley fait correspondre u avec P(u), pour tout {u\in U}.

L’algorithme avantage donc de manière claire le groupe ayant l’initiative (ici V) : le couplage stable produit est dit Pareto-V-optimal en ce sens qu’il n’est pas Pareto-dominé sur V.

III.2 – Couplages Pareto-optimaux

Dans cette sous-partie, on utilise également le jeu de données D. L’algorithme de Gale-Shapley ne retourne pas nécessairement un couplage Pareto-optimal. On s’intéresse ici à un algorithme susceptible de produire cette propriété.

Pour construire un couplage Pareto-optimal, on représente les données à l’aide d’un graphe orienté G = (S , E) où :

– les sommets S sont les éléments de {V\cup U},

– les arcs E représentent les premiers choix : (v, u) ∈ E si et seulement si u est le premier choix de v dans sa liste de préférences et (u, v) ∈ E si et seulement si v est le premier choix de u.

On propose alors l’algorithme 4 pour calculer un couplage, dont on admettra qu’il est Pareto-optimal pour V. Algorithme 4 – Algorithme de couplage par graphe orienté Entrées : {n=|V|=|U|}, les listes de préférences des éléments de {V} et {U}

Sorties : Un couplage {A}

On s’intéresse alors à une autre forme de stabilité pour assurer à la fois une propriété de Pareto et une stabilité dans les couplages.

Définition 4 (P-stabilité)

Un couplage A est P-stable s’il n’existe aucune paire(v, v′) ∈ {V^2} telle que v préfère {m_A(v')} et v′ préfère {m_A(v)}.

III.3 – Implémentation

Dans la suite, les individus sont numérotés de 0 à {n-1}. Ainsi {V=\{0,\ldots,n-1\}} et {U=\{0,\ldots,n-1\}}. On suppose disposer de deux matrices de taille {n\times n} Lv et Lu donnant respectivement les listes de préférences des éléments de V et U : ainsi, Lu[i][j] est le j-ème élément de V préféré par l’élément i ∈ U.

On définit ces tableaux en C par l’intermédiaire du code suivant :

III.3 .1 – Algorithme de Gale-Shapley

Pour connaître rapidement le classement des éléments de V dans les listes de préférences des élements de U, on définit un tableau Rang de taille {n\times n}, tel que Rang[i][j] donne le rang de j ∈ V dans la liste de préférences de l’élément i ∈ U. Par convention, les rangs commencent à 0.

Afin de pouvoir ajouter ou supprimer rapidement des couples (v, u) au couplage parfait stable A, on définit deux tableaux CoupleV et CoupleU tels que CoupleV[i] ou CoupleU[i] est le partenaire actuel de i.

On définit enfin un dernier tableau USuiv de taille n stockant pour chaque élément de V le rang du prochain élément de U à qui il peut faire une proposition.

III.3 .2 – Algorithme de couplage par graphe orienté

Sans explicitement coder tout l’algorithme 4 qui requiert de rechercher les circuits dans G, on se propose de coder quelques fonctions utiles à la réalisation de l’algorithme.

Pour pouvoir numéroter les sommets du graphe de manière continue, les individus sont maintenant numérotés de 0 à {2n-1} de la manière suivante : {V=\{0,\ldots,n-1\}} et {U=\{n,\ldots,2n-1\}}. On code le graphe orienté G par listes d’adjacence. On propose les types suivants :