2024 X-ENS Info MPI C — Corrigé

Égalités et différences

Le sujet comporte 17 pages, numérotées de 1 à 17 et une annexe. Vue d’ensemble du sujet. Ce sujet traite du problème de satisfiabilité de formules construites par la conjonction de contraintes d’égalité et de différence (dis-égalité) entre expressions.

Ce problème se présente, par exemple, dans la compilation de programmes, quand on cherche à réduire des expressions complexes (nécessitant beaucoup de calculs) vers des expressions plus simples, en utilisant les propriétés des opérateurs apparaissant dans ces expressions.

Par exemple, si x est une variable entière, (x * 2)/2 == x est une contrainte d’égalité entre deux expressions écrites en C. De même, si y et z sont des variables booléennes, l’égalité (y || (y && z)) == y permet de simplifier l’expression C écrite à gauche de l’égalité.

Il est important de savoir si un ensemble donné de contraintes d’égalité ou de différence est satisfiable. Dans la suite, {P_{L}} est le problème suivant : « Étant donnée une formule F , conjonction de contraintes de la classe L, décider si F est satisfiable ».

Ce sujet propose d’étudier la complexité du problème {P_{L}} et les algorithmes pour le résoudre dans le cas de quatre classes de contraintes : La partie I considère la classe {L_{1}} où les contraintes ont la forme {x \leftrightarrow y} ou {x \leftrightarrow \neg z} avec x, y et z des variables propositionnelles (c’est-à-dire, ayant des valeurs booléennes).

La partie II concerne la classe {L_{2}} incluant les contraintes de la classe {L_{1}} et celles de la forme {x \leftrightarrow (y \wedge z)} (entre autres) avec x, y et z des variables propositionnelles. Les algorithmes des deux premières parties seront codés en OCaml.

La partie III s’intéresse à la classe {L_{3}} des contraintes de la forme x = y ou {x \ne y} avec x et y des variables entières. Enfin, la partie IV concerne les contraintes d’égalité et de différence entre les expressions construites à partir de variables entières et de fonctions à deux arguments.

Les algorithmes des deux dernières parties seront codés en C. Les parties III et IV peuvent être traitées indépendamment de parties I et II. Il est recommandé de traiter les parties I et II de manière séquentielle. De même pour les parties III et IV.

Notations Les contraintes seront construites en utilisant un ensemble X de n variables notées {X_{i}} avec {1 \leq i \leq n}. Une valeur de vérité est un élément de {B\overset{\mathrm{def}}= \{0, 1\}} où 1 représente le vrai et 0 le faux. Une valeur entière k est un élément de Z et sa valeur absolue est notée |k|.

Étant donnés {k, m \in Z} avec {k \leq m}, l’intervalle [k; m] est l’ensemble des {i \in Z} tels que {k \leq i \leq m}. Logique propositionnelle.

On utilisera les formules de la logique propositionnelle construites à partir de l’ensemble de variables propositionnelles X, les constantes propositionnelles {\bot} (faux) et {\top} (vrai), les connecteurs logiques classiques {\neg} (négation), {\wedge} (conjonction), {\vee} (disjonction).

On définit {F \to G} (implication) par {(\neg F \vee G)}, et {F \leftrightarrow G} (équivalence) par {(F \to G) \wedge (G \to F )}. Pour les connecteurs {\wedge} et {\vee}, on utilise leur forme k-aire avec {k \geq 0}. Par exemple, {X_{1}\wedge X_{2}\wedge \ldots \wedge X_{k}} est une formule utilisant une conjonction k-aire.

Par convention, une conjonction 0-aire est {\top}, et une disjonction 0-aire est {\bot} ; une conjonction (resp. disjonction) unaire est identique à son opérande. Un littéral {\ell} est soit une variable {X_{i}} soit sa négation {\neg X_{i}}.

Une formule est en forme normale conjonctive (CNF) si c’est une conjonction de disjonctions de littéraux. Une formule est en forme k-CNF avec k > 0, si elle est en forme CNF et le nombre de littéraux différents dans chaque disjonction est au plus k. Par exemple, la formule {(X_{2} \vee X_{3} \vee \neg X_{4}) \wedge (\neg X_{3} \vee X_{4}) \wedge X_{1}} est en forme 3-CNF.

On rappelle qu’une formule propositionnelle F peut être satisfaite ou non par une valuation {v : X \to B}, qui assigne une valeur de vérité à chaque variable. On note v |= F la relation de satisfaction.

Une formule {F^{'}} est conséquence logique de F , noté {F \models F^{'}}, quand, pour toute valuation v telle que v |= F , on a aussi {v \models F^{'}}.

Deux formules sont logiquement équivalentes lorsque chacune est conséquence logique de l’autre (ou, de façon équivalente, quand elles sont satisfaites par les mêmes valuations). Une formule est une tautologie si elle est satisfaite par toutes les valuations.

Une formule est une contradiction (antilogie) ou contradictoire si elle n’est satisfaite par aucune valuation. Une formule F est satisfiable s’il existe une valuation v telle que v |= F . L’annexe rappelle certaines règles de la déduction naturelle. Complexité.

Par la complexité d’un algorithme A on entend le nombre d’opérations élémentaires (comparaison, addition, soustraction, multiplication, division, affectation, test, etc.) nécessaires à l’exécution de A dans le pire cas.

Lorsque la complexité dépend d’un ou plusieurs paramètres {k_{0}, \ldots , k_{r}}, on dit que A a une complexité en {O(f(k_{0}, \ldots , k_{r}))} s’il existe une constante C > 0 telle que, pour toutes les valeurs de {k_{0}, \ldots , k_{r}} suffisamment grandes (c’est-à-dire plus grandes qu’un certain seuil), pour toute instance du problème de paramètres {k_{0}, \ldots , k_{r}} la complexité est au plus {C \times f(k_{0}, \ldots , k_{r})}.

De même, on dit que A a une complexité en {\Theta (f(k_{0}, \ldots , k_{r}))} s’il existe deux constantes {C_{1} > 0} et {C_{2} > 0} telles que, pour toutes les valeurs de {k_{0}, \ldots , k_{r}} suffisamment grandes, la complexité de A est au moins {C_{1} \times f(k_{0}, \ldots , k_{r})} et au plus {C_{2} \times f(k_{0}, \ldots , k_{r})}.

Dans tout ce sujet, on note « log » le logarithme à base 2, et on utilisera exclusivement ce logarithme. Programmation. Dans les questions de programmation en C et OCaml, on n’utilise que les fonctions qui sont incluses dans la bibliothèque standard du langage.

Pour le code écrit en C, on suppose que les en-têtes stdbool.h, stdio.h, stdlib.h et assert.h ont été inclus.

On rappelle quelques opérations sur les listes en OCaml.

— List.iter f lst applique la fonction f: 'a -> unit à chaque élément de la liste lst de type 'a list.

Si la complexité de f est en O(1), alors la complexité de List.iter est en O(k), où k est la longueur de lst.

— List.map f lst renvoie la liste de type 'b list obtenue en appliquant la fonction f: 'a -> 'b à chaque élément de la liste lst de type 'a list.

Si la complexité de f est en O(1), alors la complexité de List.map est en O(k), où k est la longueur de lst.

— List.mem e lst renvoie true si et seulement si e est un élément de lst.

Si la complexité du test d’égalité est en O(1), la complexité de List.mem est en O(k), où k est la longueur de lst.

— List.exists f lst renvoie true si et seulement s’il existe au moins un élément e de lst (liste de type 'a list) tel que f e renvoie true avec f: 'a -> bool.

Si la complexité de f est en O(1), alors la complexité de List.exists est en O(k), où k est la longueur de lst.

— List.for_all f lst renvoie true si et seulement si tous les éléments de lst (de type 'a list) satisfont le prédicat f: 'a -> bool.

Si la complexité de f est en O(1), alors la complexité de List.for_all est en O(k), où k est la longueur de lst.

— List.filter f lst renvoie la liste de tous les éléments de lst (de type 'a list) qui satisfont le prédicat f: 'a -> bool.

Si la complexité de f est en O(1), alors la complexité de List.filter est en O(k), où k est la longueur de lst.

On rappelle quelques opérations sur les tableaux en OCaml.

  • Array.length tab renvoie la longueur du tableau tab en temps O(1).

  • Array.make k v crée un tableau de k éléments, tous initialisés à v, en temps O(k).

  • La valeur à la case numéro i du tableau tab est tab.(i).

Les cases sont numérotées à partir de zéro et l’accès est fait en temps O(1).

  • L’affectation de la case i du tableau tab avec la valeur v s’écrit tab.(i) <- v ; sa complexité est en O(1).

  • Array.copy tab crée une copie du tableau tab en temps O(k) avec k la longueur du tableau en argument.

Partie I. Équivalences de littéraux

Dans cette partie, on se place dans le cadre de la logique propositionnelle. On définit {L_{1}} comme la classe des contraintes de la forme {\ell \leftrightarrow \ell ^{'}} avec {\ell} et {\ell ^{'}} des littéraux. Une formule F est dite construite sur {L_{1}}, notation {F \in F(L_{1})}, si elle est une conjonction de contraintes de {L_{1}}.

Dans cette partie, on considère que la variable {X_{1}} est toujours interprétée à 1, donc qu’elle représente la valeur de vérité vrai. La formule {F_{0}} définie ci-dessous est dans {F(L_{1})} : {\begin{array}{l}F_{0}\overset{\mathrm{def}}= (X_{3} \leftrightarrow \neg X_{2})\wedge(X_{4} \leftrightarrow X_{3})\\[8pt]\wedge(X_{3} \leftrightarrow X_{4})\wedge(X_{1} \leftrightarrow \neg X_{5})\end{array}}

Question 1. Donner une formule logiquement équivalente à {F_{0}} en forme 2-CNF.
Question 2. Donner une réduction en temps linéaire du problème {P_{L_1}} au problème de satisfiabilité des formules en 2-CNF.

Mise en œuvre en OCaml. Une contrainte de {L_{1}} est représentée par un couple d’entiers (i, j) avec {i, j \in [1; 2n]}. Pour tout {i \in [1; 2n]}, le littéral représenté par i, noté lit(i), est {X_{i}} si {i \in [1; n]} et {\neg X_{i-n}} si {i \in [n + 1; 2n]}.

Par la convention sur l’interprétation de {X_{1}}, l’entier i = 1 (resp. i = n + 1) représente la valeur de vérité 1 (resp. 0). Enfin, une formule dans {F(L_{1})} est représentée par la liste des couples correspondant aux contraintes dont la formule est conjonction.

Par convention, la liste vide représente {\top}. Le nombre de variables, n, est une variable globale entière. Ce codage est donné par les déclarations OCaml ci-dessous :

Les exceptions déclarées ci-dessus seront utilisées dans les fonctions de cette partie et de la partie suivante.

Question 3. Écrire les fonctions suivantes :

— var_of_lit: int -> int renvoie l’index de la variable apparaissant dans le littéral représenté par l’argument i. Par exemple, pour n = 5, la fonction renvoie 3 si l’argument est 3, et 2 si l’argument est 7.

Si {i \notin [1; 2n]} alors la fonction exécute raise (Bad_literal i).

  • neg_lit: int -> int renvoie, pour un argument i, l’entier j tel que lit(j) est logiquement équivalent à {\neg lit(i)} ; si {i \notin [1; 2n]} alors la fonction exécute raise (Bad_literal i).

  • eform1_is_wf: eform1 -> bool renvoie true si et seulement si l’argument est « bien formé », c’est-à-dire qu’il contient uniquement des entiers qui représentent des littéraux sur l’ensemble de variables X.

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :