Centrale Informatique MPI 2026Sujet

Informatique

Partie A - Base de données (SQL)

• -La colonne INSEE représente le numéro INSEE de la commune.
• -La colonne Département indique à quel département est rattachée la commune.
• -La colonne Monde indique dans quel monde l'information de cette ligne est vraie.

Partie B - Analyse lexicale et syntaxique d'une formule déontique (en OCaml)

• « ( Grand_mere_a_prepare_des_crepes et doit je_mange_les_crepes ) »

Ce qui donne finalement l'arbre :

I - Analyse lexicale

• -les opérateurs logiques décrits en texte : « non », « et », « doit »;
• -les deux symboles de parenthèses : « ( », « ) »;

• -les variables propositionnelles, par exemple « Grand_mere_a_prepare_des_crepes », décrites avec du texte sans aucun espace. On s'autorise les 26 lettres de l'alphabet (en majuscule ou minuscule) ainsi que le caractère spécial _. On impose que ce caractère spécial ne soit pas le premier caractère.

type lexeme =
    Lex_var of string
    | Lex_et
    | Lex_non
    | Lex_doit
    | Lex_PO (* parenthèse ouvrante *)
    | Lex_PF (* parenthèse fermante *)

• - E l'ensemble des caractères d'espacement : l'espace simple, la tabulation (\t) et le saut de ligne (\n);
• - A l'ensemble des 26 lettres de l'alphabet (sans accent ni cédille) en majuscule ou en minuscule (soit 52 caractères au total);
• - P l'ensemble contenant deux symboles, la parenthèse ouvrante et la parenthèse fermante.

let alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
let espaces = " \t\n"

Pour reconnaître les lexèmes, nous utilisons l'automate suivant :

L'état initial est l'état 0 . N'importe quel symbole de E permet de faire une transition de l'état 0 vers l'état 0 . Le symbole _ permet de faire une transition de l'état 1 à l'état 2.

• • -la sous chaîne de chaine, du caractère d'indice debut inclus au caractère d'indice fin_lexeme exclu est reconnue par l'automate;
  • -il n'existe pas de plus grande sous-chaîne commençant en debut qui soit reconnue;
  • -debut_lexeme est l'indice du premier caractère après l'indice debut qui n'est pas dans E.

let produit_lexeme chaine debut fin =
    match sous_chaine chaine debut (fin-debut) with
    | "et" -> Lex_et
    | "non" -> Lex_non
    | "doit" -> Lex_doit
    | "(" -> Lex_PO
    | ")" -> Lex_PF
    | x -> Lex_var x

• Q9.Écrire une fonction analyse_lexicale : string -> lexeme list qui prend en entrée une chaîne de caractères et qui renvoie en sortie sa décomposition en suite de lexèmes.
  Cette fonction doit lever l'exception Erreur_Lexicale s'il n'est pas possible de convertir la chaîne de caractères en suite de lexèmes.
  Par exemple, analyse_lexicale "non doit manger_crepe" doit renvoyer : [Lex_non; Lex_doit; Lex_var "manger_crepe"].

II - Grammaire non contextuelle

• (i) A → (E)|E
• (ii) E → n|A et A| non A| doit A

• (i) E → n|(B)|C
• (ii) B → E et E
• (iii) C → non E| doit E
• Q10.Considérons les mots m_1:=≪x doit ( y et z ) 》 et m_2:=≪x et doit ( non y et z ) ». Pour chacun de ces mots, indiquez s'il dérive :
  -de la grammaire G;
  -de la grammaire H.

• Q12.La grammaire G est-elle ambiguë? La grammaire H est-elle ambiguë? Justifiez votre réponse (on ne demande pas de preuve formelle dans le cas d'une non-ambiguïté, mais une brève justification).

III - Analyse syntaxique

type formule =
    Var of string
| Et of formule * formule
| Non of formule
| Doit of formule

• -f est un arbre syntaxique correspondant à un préfixe prefixe de la liste lexemes.
• -reste est une liste telle que prefixe @ reste = lexemes; ainsi reste est la liste lexemes à laquelle on a retiré la partie prefixe qui a servi à générer f.

exception Erreur_Syntaxique (* ceci définit une nouvelle exception *)
let rec derive_E lexemes = match lexemes with
    | Lex_var x :: q -> (Var x, q); (* E -> n *)
    | Lex_PO :: q -> (* E-> ( B ) *)
        begin
            match derive_B q with
                | f , Lex_PF :: q2 -> (f, q2)
                | _ -> raise Erreur_Syntaxique
        end
    | _ -> derive_C lexemes (* E -> C *)
and derive_B lexemes = match derive_E lexemes with
        | f1, Lex_et : : q -> (* B -> E et E *)
            begin
                (* bloc de code 1 *)
            end
        | _ -> raise Erreur_Syntaxique
and derive_C lexemes = match lexemes with
    (* bloc de code 2 *)

(Non (Var "manger_crepe"), [Lex_et; Lex_doit; Lex_var "remercier_mamie"; Lex_PF]).

• Q13.Compléter le « bloc de code 1 » situé à la ligne 16 du code ci-dessus.

Partie C - Univers de Kripke (en C)

I - Formules déontiques

• (i)Si P est une variable propositionnelle, alors P est une formule déontique.
• (ii)Si φ et ψ sont des formules déontiques alors (φ ∧ ψ) et (φ ∨ ψ) et (φ → ψ) sont des formules déontiques.
• (iii)Si φ est une formule déontique alors ¬φ, ◻φ et ⋄φ sont des formules déontiques.

const int ET = 0;
const int OU = 1;
const int NON = 2;
const int VARIABLE = 3;
const int DOIT = 4;
const int PEUT = 5;
const int IMPLIQUE = 6;

struct formule_s {
    int op;
    struct formule_s *gauche;
    struct formule_s *droite;
    int variable;
};
typedef struct formule_s formule ;

Le champ opérateur indique de quel opérateur il s'agit.
Si c'est un opérateur binaire (∧, ∨, →), les champs gauche et droite indiquent les deux sous-formules tandis que le champ variable est affecté d'une valeur entière arbitraire (par exemple -1).
Si c'est un opérateur unaire, le champ gauche indique la sous-formule, le champ droite vaut NULL et le champ variable est affecté d'une valeur entière arbitraire (par exemple -1).
Si c'est une variable, gauche et droite valent NULL, et variable indique le numéro de la variable. Par exemple, si ce champ vaut 42, alors la variable est X_(42).
Par exemple, la formule X_1 ∨ ⋄X_2 sera représentée par la structure suivante.

• Q16.Écrire une fonction formule *cree_formule(int op, int variable, formule *fg, formule *fd) qui alloue sur le tas et renvoie une valeur du type formule avec les valeurs spécifiées pour ses champs.
• Q17.Écrire une fonction int compter_peut (formule *f) qui prend en entrée une formule f et qui renvoie le nombre d'occurrences de l'opérateur ◇ dans cette formule.
  Par exemple, sur la formule X_1 ∨ ⋄X_2 décrite précédemment, cette fonction doit renvoyer 1.
• Q18.Écrire une fonction void free_formule(formule *f) qui prend en entrée une forme f et qui libère la mémoire occupée par cette formule. La fonction free_formule doit libérer la mémoire de toutes les sous-formules.

• -g est obtenue en remplaçant toutes les implications → de f ;
• -la formule f n'a pas été modifiée ;
• -aucune des sous-formules de f et de g ne partagent un même emplacement en mémoire.

II - Modèles d'une formule déontique

struct monde_s {
    int taille;
    bool *valuation;
};
typedef struct monde_s monde ;

• - S_𝕌 est un ensemble fini non vide de mondes, c'est l'ensemble des sommets du graphe.
• - R_𝕌 est une relation binaire. R_𝕌(m_1, m_2) signifie que dans l'univers 𝕌 il existe un arc du monde m_1 vers le monde m_2. On impose que, pour tout monde m_1 ∈ S_𝕌, il existe un monde m_2 ∈ S_𝕌 tel que R_𝕌(m_1, m_2).

• - 𝕌⊨_i A si A est une variable propositionnelle associée à la valeur de vérité vraie dans le monde i.
• - 𝕌⊨_i φ ∧ ψ si 𝕌⊨_i φ et 𝕌⊨_i ψ.

• - 𝕌⊨_i φ ∨ ψ si 𝕌⊨_i φ ou 𝕌⊨_i ψ.
• − 𝕌⊨_i φ → ψ si 𝕌⊨_i¬φ ∨ ψ.
• - 𝕌⊨_i¬φ si 𝕌⊨_i φ est faux.
• - 𝕌⊨_i◻φ si pour tout monde j ∈ S_𝕌 tel que R_𝕌(i, j) on a 𝕌⊨_j φ.
• - 𝕌⊨_i⋄φ s'il existe un monde j ∈ S_𝕌 tel que R_𝕌(i, j) on a 𝕌⊨_j φ.

Voici un exemple d'univers 𝔼 qui satisfait la propriété ¬Q ∧ ◻Q (« Q est faux mais Q devrait être vrai ») dans le monde i. Par souci de lisibilité du dessin, un monde (c'est-à-dire une interprétation) associant P à true, Q à false, etc sera codé par : P, ¬Q, etc. Par exemple, P est faux et Q est vrai dans le monde j, tandis que P et Q sont tous les deux vrais dans le monde k.

III - Formules réduites

• (i)Si P est une variable propositionnelle alors P et ¬P sont des formules réduites.
• (ii)Si φ et ψ sont des formules réduites alors (φ ∧ ψ) et (φ ∨ ψ) sont des formules réduites.
• (iii)Si φ est une formule réduite alors ◻φ et ⋄φ sont des formules réduites.

struct univers_s {
    int nb_mondes;
    bool **matrice;
    monde *mondes;
};
typedef struct univers_s univers;

IV - Décidabilité de la satisfiabilité d'une formule déontique

• -Un univers arborescent de profondeur 0 est constitué d'un unique monde, et d'un unique arc de ce monde vers lui-même. Ce monde est la racine.
• -Si 𝕌_1, …, 𝕌_k sont des univers arborescents deux à deux disjoints de profondeur n, de racines respectives r_1, …, r_k et que r est un monde qui n'appartient à aucun de ces univers, alors l'univers 𝕌 défini comme suit est un univers arborescent de profondeur n + 1 :
  • -les sommets de 𝕌 sont la réunion des sommets de 𝕌_1, …, 𝕌_k à laquelle on ajoute le sommet r;
  • -les arcs de 𝕌 est la réunion des arcs de 𝕌_1, …, 𝕌_k à laquelle on ajoute les arcs(r, r_1), (r, r_2), …, (r, r_k).

• -arborescent(U, 0, i) :
  • -Créer une nouvelle copie nommée r de i.
  • -Créer un arc de r vers r.
  • -Renvoyer le graphe ainsi obtenu.
• - arborescent(U, N, i) :
  • -Créer une nouvelle copie nommée r de i.
  • -Pour chaque arc sortant (i, j) de i, créer A_j = arborescent(U, N − 1, j).
  • -Faire l'union des A_j puis rajouter le monde r puis, pour chaque racine r_j des A_j, créer un arc (r, r_j).
• Q30.Écrire une fonction int taille(univers *u, int i, int N) qui prend en entrée un univers u, un numéro de monde i dans cet univers ainsi qu'un entier N et qui renvoie la taille, en nombre de mondes, qu'aurait un univers arborescent créé par l'algorithme précédent.
• Q31.Écrire une fonction univers *arborescent(univers *u, int i, int N) qui implémente l'algorithme précédent. La racine du résultat doit être le monde numéro zéro.
• Q32.Soient φ une formule réduite, N est le nombre de symboles ⋄ et ◻ de la formule φ, 𝕌 un univers, i un monde de 𝕌 et 𝔸 l'univers arborescent de racine r créé par l'algorithme précédent (autrement dit 𝔸 = arborescent(𝕌, N, i) ). Montrer que si 𝕌⊨_i φ alors 𝔸⊨_r φ.
• Q33.Montrer que la proposition précédente reste vraie si on modifie l'algorithme et qu'on ne garde pas dans les 𝕌_i deux univers identiques lors de la construction.
• Q34.Montrer que le problème de la satisfiabilité d'une formule déontique est décidable.

V - NP-complétude

• - 𝕋 est un sous-graphe de 𝕌;
• - 𝕋 est total;
• -pour toute sous-formule ⋄ψ de φ, s'il existe un ou plusieurs mondes k tels que 𝕌⊨_k ψ, alors au moins un de ces mondes est dans 𝕋.

Partie D - Déduction naturelle pour la logique déontique

Figure 1 - Règles de la déduction naturelle classique