Corrigé Centrale 2026 Informatique MPI — Partie C, I et II (Q16 à Q25) : Formules déontiques en C, univers de Kripke

Sujet officiel du concours Centrale, session 2026, épreuve Informatique MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Formules déontiques sur des variables $X_{0}, X_{1}, \dots$ : variables, $(φ \land ψ)$ , $(φ \lor ψ)$ , $(φ \to ψ)$ , $\neg φ$ , $□ φ$ (« $φ$ est obligatoire ») et $◊ φ$ (« $φ$ est autorisée »). Représentation en C (pour un opérateur unaire, droite vaut NULL ; pour une variable, les deux fils valent NULL ; hors variable, variable est arbitraire, par exemple $- 1$ ) :


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 ;

La formule $X_{1} \lor ◊ X_{2}$ :

Q16. formule *cree_formule(int op, int variable, formule *fg, formule *fd), allocation sur le tas.
Q17. int compter_peut(formule *f) : nombre de $◊$ ( $1$ sur l'exemple).
Q18. void free_formule(formule *f) : libère toutes les sous-formules ( $4$ structures sur l'exemple).
Q19. formule *retirer_implications(formule *f) : renvoie $g$ où chaque $φ \to ψ$ devient $\neg φ \lor ψ$ , sans modifier $f$ ni partager de mémoire avec $f$ .

II. Un monde est une valuation des variables ; en C, valuation[i] est la valeur de $X_{i}$ pour $0 ⩽ i <$ taille.


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

typedef struct monde_s monde ;

Q20. bool satisfaction(monde *m, formule *f) pour une formule faite de variables, de $\land$ et de $\neg$ .

Un univers $U = (S_{U}, R_{U})$ est un graphe fini non vide de mondes où tout monde a au moins un successeur ; $R_{U} (i, j)$ se lit « $j$ est idéal pour $i$ ». On définit $U ⊨_{i} φ$ par induction : une variable est satisfaite en $i$ si elle y est vraie ; $\land$ , $\lor$ , $\neg$ s'interprètent au monde $i$ et $φ \to ψ$ comme $\neg φ \lor ψ$ ; $U ⊨_{i} □ φ$ si $U ⊨_{j} φ$ pour tout $j$ tel que $R_{U} (i, j)$ , et $U ⊨_{i} ◊ φ$ s'il existe un tel $j$ avec $U ⊨_{j} φ$ . Univers $E$ (un monde est noté par ses littéraux vrais) :

Q21. A-t-on $E ⊨_{i} □□ Q$ ?
Q22. A-t-on $E ⊨_{i} ◊ (P \land □ \neg P)$ ?

$φ$ est satisfiable s'il existe $(U, m)$ , un modèle de $φ$ , tel que $U ⊨_{m} φ$ ; $φ$ est conséquence logique de $ψ$ si tout modèle de $ψ$ est modèle de $φ$ . $□$ est prioritaire sur $\to$ ; $θ_{1} = □□ P \to □ P$ et $θ_{2} = □ (□ P \to P)$ .
Q23. $θ_{1}$ et $\neg θ_{1}$ sont satisfiables.
Q24. $θ_{2}$ et $\neg θ_{2}$ sont satisfiables.
Q25. $θ_{1}$ est conséquence logique de $θ_{2}$ , mais pas l'inverse.

Corrigé

Toutes les fonctions C ci-dessous ont été compilées (gcc -std=c11 -Wall -Wextra, sans avertissement, avec -fsanitize=undefined) et exécutées sur la formule $X_{1} \lor ◊ X_{2}$ du sujet et sur une formule à trois implications ; les réponses de Q21 à Q25 ont été vérifiées par un évaluateur de formules écrit en Python. Les en-têtes nécessaires sont <stdlib.h>, <stdbool.h> et <assert.h>.

Ce que le correcteur attend : les constantes du sujet sont des const int, qui ne sont pas des expressions constantes au sens du C : elles ne peuvent pas servir d'étiquettes case d'un switch. On teste donc f->op par une suite de if.

Q16.


formule *cree_formule(int op, int variable, formule *fg, formule *fd) {
  formule *f = malloc(sizeof(formule));
  assert(f != NULL);                 /* malloc peut échouer */
  f->op = op;
  f->variable = variable;
  f->gauche = fg;
  f->droite = fd;
  return f;
}

La structure est allouée sur le tas, donc survit à l'appel (une variable locale serait détruite au retour et le pointeur renvoyé serait invalide). Coût $O (1)$ .

Q17. Une formule est un arbre binaire dont les fils absents valent NULL ; on compte récursivement, en traitant NULL comme la formule vide.


int compter_peut(formule *f) {
  if (f == NULL) return 0;
  int ici = (f->op == PEUT) ? 1 : 0;
  return ici + compter_peut(f->gauche) + compter_peut(f->droite);
}

Par induction structurelle : le nombre de $◊$ d'une formule est celui de sa racine ( $0$ ou $1$ ) plus ceux de ses sous-formules, et il est nul pour l'arbre vide. Un appel par nœud et un par fils NULL, soit au plus $2∣ f ∣ + 1$ appels en $O (1)$ : coût $O (∣ f ∣)$ . Exécuté : $1$ sur $X_{1} \lor ◊ X_{2}$ .

Q18. On libère les deux sous-formules avant la racine : après free(f), lire f->gauche serait un accès à une mémoire libérée.


void free_formule(formule *f) {
  if (f == NULL) return;
  free_formule(f->gauche);
  free_formule(f->droite);
  free(f);
}

Parcours postfixe : chaque nœud est libéré exactement une fois, à condition que la formule soit un arbre (aucune sous-formule partagée, sinon on la libérerait deux fois — c'est la raison de la troisième exigence de Q19). Exécuté avec un compteur d'appels à free : $4$ libérations sur $X_{1} \lor ◊ X_{2}$ .

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →