Documents autorisés : une feuille A4 recto-verso pour chacune de parties A, B, C, D, manuscrite ou imprimée.

Partie A

A1 (1 point)

Donnez les solutions, si applicable, du réseau de contraintes suivant :

Variables : \(A, C\) de domaine \(\{1,2,3\}\), \(B,D\) de domaine \(\{4,5,6\}\).

Contraintes :

• Sur \(A,B\) : \(\{(1,5),(2,6),(3,4)\}\).
• Sur \(B,C\) : \(\{(4,2),(5,3),(6,1)\}\).
• Sur \(C,D\) : \(\{(1,5),(2,6),(3,4),(3,6)\}\).
• Sur \(A,D\) : \(\{(1,6),(2,4),(3,5)\}\).

A2 (1 point)

Donnez la spécification en extension de la contrainte logique \(A\vee \neg B \vee C\).

Partie B

Soit \(V\) un ensemble de variables, \(q\) une contrainte reliant les variables de \(V\) et un ensemble \(Q\) de contraintes tel que les variables reliées par chaque contrainte de \(Q\) appartiennent à \(V\).

On dit que \(Q\) est équivalent à \(q\) si et seulement si toute assignation complète des variables de \(V\) satisfait toutes les contraintes de \(Q\) si et seulement si elle satisfait \(q\).

Par exemple, l’ensemble de contraintes \(Q = \{A\neq B, A\neq C, B\neq C\}\) est équivalent à la contrainte \(q = \text{allDiff}(A,B,C)\).

On appelle contrainte logique toute contrainte spécifiée en compréhension uniquement à l’aide des opérateurs \(\vee, \wedge, \neg\).

Dans les questions suivantes, il sera uniquement question de variables Booléennes, donc à domaine \(\{0,1\}\).

B1 (1 point)

Donnez un ensemble de contraintes logiques équivalent à la contrainte \(X_1+…+X_N \neq 0\). Cet ensemble peut ne contenir qu’une seule contrainte.

B2 (1 point)

Donnez un ensemble de contraintes logiques aussi petit que possible équivalent à la contrainte \(A+B+C+D \leq 2\).

B3 (2 points)

Donnez un ensemble de contraintes logiques aussi petit que possible équivalent à la contrainte \(X_1+…+X_N \leq 1\), pour tout entier \(N\) supérieur à 1.

Partie C

Pour chacune des questions, vous devez répondre en donnant, dans un ordre plausible, les valeurs retirées lors de la restauration de la cohérence de domaines du réseau de contraintes ou de la contrainte donnée dans l’énoncé. Aucune justification n’est demandée. Vous devez juste donner, à raison d’une ligne par visite d’une contrainte, la liste des valeurs retirées en utilisant la notation \(V\neq x\) pour dire que la valeur \(x\) est retirée du domaine de \(V\).

Par exemple pour décrire le filtrage du réseau \(q_1 : A<B\), \(q_2 : B<C\) où \(A, B, C\) ont pour domaine \(\{1,2,3\}\), vous devez adopter la présentation suivante :

• \(q_1\) : \(A\neq 3, B\neq 1\)
• \(q_2\) : \(B\neq 3, C\neq 1, C\neq 2\)
• \(q_1\) : \(A\neq 2\)

C1 (2points)

Restaurez la cohérence de domaine du réseau de contraintes suivant :

Variables : \(A\) de domaine \(\{1,2,3\}\), \(B\) de domaine \(\{4,5,6\}\), \(C\) de domaine \(\{7,8,9\}\).

Contraintes :

• \(q_1\) sur \(A,B\) : \(\{(1,5),(2,4),(3,6)\}\)
• \(q_2\) sur \(B,C\) : \(\{(4,8),(5,7),(6,8)\}\)
• \(q_3\) sur \(A,C\) : \(\{(1,7),(2,8),(3,9)\}\)

C2 (2 points)

Restaurez la cohérence de domaine du réseau de contraintes suivant :

Variables : \(A,B,C\) de domaine \(\{1,2,3\}\).

Contraintes :

• \(q_1\) : \(A+B+C=6\)
• \(q_2\) : \(A+2B+C=9\)
• \(q_3\) : \(2A+B+3C=10\)

Partie D

D1 (2 points)

Soit le réseau de contraintes suivant :

Variables : \(A,B,C,D\) ayant toutes pour domaine \(\{3,7,11\}\).

Contraintes :

• \(A+B+C+D \leq 17\)
• \(A+B+C+D \geq 17\)

Donnez l’arbre de recherche illustrant le déroulement de l’algorithme MAC sur ce réseau de contraintes. Précisez à chaque nœud les domaines des variables en barrant celles qui sont filtrées.