Informatique — MPI · 2025
Grammaires non contextuelles, NP-complétude (bin-packing) et algorithmes de couplage. Trois parties : (I) grammaires non contextuelles G avec récursivité gauche directe — élimination de la récursivité gauche, ambiguïté, langage reconnu {a,b,c}∗ ; (II) bin-packing — preuve NP par certificat polynomial, NP-complétude par réduction depuis PARTITION, heuristique Premier Casier Décroissant (3/2-approximation), implémentation OCaml complète (boîtes, objets, tri décroissant) ; (III) algorithmes de couplage — Gale-Shapley (terminaison, stabilité, complexité O(n2), V-Pareto-optimalité par caractérisation A∗={(v,M(v))}), couplages Pareto-optimaux par graphe orienté avec circuits, P-stabilité, implémentation C complète (rang, matrices, listes d'adjacence).
Grammaire non contextuelle — récursivité gaucheAmbiguïté et arbres de dérivationNP, NP-complétude — réductions+7
3 parties · 38 questions4 heures