Université Oran1

Département d’informatique
Parcours : Master2-ADSI
Matière : Programmation par contraintes (PPC)
Date : 20-11-2024

Test 1 de la matière PPC - Corrigé

Questions (0.5pt par question)

Sur la feuille de réponse, indiquez juste le n° de la question suivie du n° de la réponse. Par exemple : Q1-
a ; Q2-b, etc.
Question 1 : Qu'est-ce que la programmation par contraintes ?
a) Une méthode pour gérer des données aléatoires.
b) Une approche pour résoudre des problèmes combinatoires en imposant des restrictions
sur les variables.
c) Une technique d'apprentissage automatique supervisé.
d) Une méthode pour créer des algorithmes récursifs.
Question 2 : Dans un CSP, quelles sont les trois composantes de base ?
a) Variables, domaines, objectifs
b) Variables, domaines, contraintes
c) Variables, objectifs, contraintes
d) Contraintes, objectifs, domaines
Question 3 : Quelle est le principal but d'un CSP ?
a) La recherche de solutions optimales
b) La recherche d'une réponse binaire (oui/non)
c) La recherche de solutions en temps réel
d) La recherche de solutions à un problème complexe
Question 4 : Quelle est la différence entre une variable libre et une variable affectée dans un CSP ?
a) Une variable libre est une variable sans valeur, tandis qu'une variable affectée a une valeur.
b) Une variable libre est une variable non utilisée, tandis qu'une variable affectée est utilisée.
c) Une variable libre est une variable qui ne respecte pas les contraintes, tandis qu'une variable
affectée les respecte.
d) Il n'y a pas de différence entre une variable libre et une variable affectée.
Question 5 : Quel est le but principal de la propagation de contraintes dans la résolution de CSP ?
a) Réduire l'espace des solutions en éliminant des valeurs de domaine possibles.
b) Générer toutes les solutions possibles en respectant les contraintes.
c) Maximiser le nombre de contraintes dans un CSP.
d) Minimiser le nombre de variables dans un CSP.
Question 6 : Quelle méthode de résolution de CSP consiste à essayer systématiquement différentes
combinaisons de valeurs pour les variables jusqu'à trouver une solution ?
a) Recherche locale
b) Recherche par propagation
c) Recherche par contrainte
d) Recherche exhaustive (énumérative)
Question 7 : Quel est l'objectif principal de la programmation par contraintes ?
a) Minimiser le nombre de variables.
b) Maximiser l'espace de solution.
c) Trouver des solutions qui respectent un ensemble de contraintes.
d) Créer des contraintes en fonction des résultats souhaités.
Question 8 : Quel est l'outil de propagation des contraintes le plus courant ?
a) Recherche arborescente.
b) Algorithme de backtracking.

1/5
 c) Réseaux bayésiens.
d) AC-3 (Arc Consistency 3).
Question 9 : Dans quel domaine la programmation par contraintes est-elle particulièrement utilisée ?
a) Génie mécanique.
b) Planification et ordonnancement.
c) Informatique graphique.
d) Traitement du signal.
Question 10 : Dans un problème de satisfaction de contraintes (CSP), qu'est-ce qu'une solution ?
a) Un ensemble de variables avec une valeur nulle.
b) Une affectation de valeurs aux variables qui satisfait toutes les contraintes.
c) Une affectation de valeurs qui maximise une fonction objective.
d) Une méthode de recherche récursive.
Question 11 : Quel est le rôle du "backtracking" en programmation par contraintes ?
a) Trouver une solution optimale en réduisant l’espace de recherche.
b) Explorer toutes les solutions possibles sans exclure de valeurs.
c) Revenir en arrière lorsqu'une impasse est rencontrée dans l'espace de recherche.
d) Diviser les contraintes en sous-ensembles indépendants.
Question 12 : Quelle technique est souvent utilisée pour réduire l’espace de recherche dans les CSP ?
a) Apprentissage supervisé.
b) Heuristiques et méthodes de filtrage.
c) Modélisation graphique.
d) Clustering.
Question 13 : La programmation par contraintes est particulièrement efficace pour résoudre des
problèmes :
a) Où les contraintes sont dynamiques et changent fréquemment.
b) Où l’on souhaite minimiser une fonction objective.
c) Avec un grand nombre de variables interdépendantes et des contraintes complexes.
d) Qui n’ont pas de solution unique.

Exercice 1 (6,75 points) : Problème des carrés latins

Etant donnée n couleurs (1, 2, …, n), un carré latin d’ordre n est un carré n x n colorié tel que :
– Toute cellule est coloriée,
– Chaque couleur apparaît exactement une fois sur chaque ligne,
– Chaque couleur apparaît exactement une fois sur chaque colonne.
Voici un exemple de carré latin d’ordre 4 :

1. Modéliser le problème du carré latin d’ordre n en un CSP(X, D, C) en définissant l’ensemble X de

ses variables, l’ensemble D des domaines des variables et l’ensemble C des contraintes.
a- (1 pt) Variables
Xij pour i,j∈{1, 2, …, n} où Xij représente la valeur dans la case de la ligne i et de la colonne j.
b- (1 pt) Domaines
Le domaine de chaque variable Xij est {1, 2, …, n}, c’est-à-dire les symboles (ici des
couleurs) qui peuvent être placés dans la case.
c- (1 pt) Contraintes
• Contrainte de ligne : Les valeurs dans chaque ligne doivent être différentes.
∀i∈{1, 2, …, n},∀j,k∈{1, 2, …, n},j≠k ⟹ Xij≠Xik

2/5
 • Contrainte de colonne : Les valeurs dans chaque colonne doivent être différentes.
∀j∈{1, 2, …, n},∀i,k∈{1, 2, …, n},i≠k ⟹ Xij≠Xkj

2. Considérons un carré latin d’ordre n=4. On suppose qu’initialement certaines cases sont coloriées
comme suit :
V
R J
B
V J

a. (0.5 pt) Ajouter ces nouvelles contraintes au modèle précédent.

X14 = ‘V’ ; X21=’R’ ; X24=’J’ ; X32=’B’ ; X41=’V’ ; X43=’J’.
Pour les autres variables Xij, D(Xij)={R, V, B, J}.
b. (0.25 pt) Ce CSP est-il arc-consistant ?
Si l’on considère ces nouvelles contraintes, le CSP n’est pas arc-consistant. Comme
X14=’V’, l’affectation X11=‘V’, par exemple, n’est pas permise.
c. (1 pt) Exécutez la consistance d’arc pour rendre le CSP arc-consistant.
Initialement, la file Q contient tous les arcs (Xij, Xkl) qui partagent une ligne ou une
colonne : Q={(Xij,Xkl) ∣ Xij et Xkl partagent une ligne ou une colonne}.
On extrait à chaque itération un arc de Q et on assure l’arc-consistance de l’arc en
excluant toute valeur inconsistante du domaine de la variable. On insère dans Q tous
les arcs affectés par la modification. On refait ce processus jusqu’à stabilisation des
domaines des variables.

Domaine des variables avant filtrage :

R,V,B,J R,V,B,J R,V,B,J V
R R,V,B,J R,V,B,J J
R,V,B,J B R,V,B,J R,V,B,J
V R,V,B,J J R,V,B,J

Domaine des variables après exécution de AC :

R,V,B,J R,V,B,J R,V,B,J V
R R,V,B,J R,V,B,J J
R,V,B,J B R,V,B,J R,V,B,J
V R,V,B,J J R,V,B,J

Ce qui donne :
B J R V
R V B J
J B V R
V R J B

3. (2 pts) Exécuter 5 itérations de l’algorithme de backtracking chronologique en démarrant des pré-

affectations suivantes. Préciser l’ordre chronologique de choix des variables et des valeurs d’une
variable :
Ordre de choix des variables : X11, X12, X13, X14, X21, ….
Ordre de choix des valeurs : R, V, B, J

3/5
 V
R B J
B
V J

R V V V B V
R B J R B J R B J
B B B
V J V J V J

B R V
R B J
B
V J

B R R V
R B J
B
V J

Exercice 2 (6,75 points)

On doit planifier 6 tâches dans un délai de 6 heures. On vous donne ci-dessous le graphe de précédence
de tâches :

Une tâche à l’origine d’un arc doit s’exécuter avant la tâche en fin de l’arc. Les valeurs sur les tâches
indiquent les durées d’exécution des tâches. Chaque tâche ne peut démarrer qu’en début d’une heure.
Les tâches T1 et T4 ne peuvent être planifiées à la même heure.

1. Modéliser ce problème en un CSP.

a. (0.75 pt) Variables : 𝑿 = {𝒔𝒊 , 𝒊 = 𝟏, . . , 𝟔 : temps de début de la tâche 𝑻𝒊}.
b. (0.75 pt) Domaines : 𝑫(𝒔𝒊 ) = {𝟎, 𝟏, . . , 𝟔 − 𝒑𝒊 }, 𝒊 = 𝟏, … , 𝟔 où 𝒑𝒊 est la durée de la tâche
𝑻𝒊.
𝑫(𝒔𝟏 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓}
𝑫(𝒔𝟐 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓}
𝑫(𝒔𝟑 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒}
𝑫(𝒔𝟒 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓}
𝑫(𝒔𝟓 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒}
𝑫(𝒔𝟔 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓}

c. (1.5 pts) Contraintes : 𝑪 = {𝑪𝟏 , 𝑪𝟐 , 𝑪𝟑 , 𝑪𝟒 , 𝑪𝟓 , 𝑪𝟔 }

Contraintes de précédence :

4/5
 𝑪𝟏 : 𝒔𝟏 + 𝟏 ≤ 𝒔𝟔
𝑪𝟐 : 𝒔𝟐 + 𝟏 ≤ 𝒔𝟒
𝑪𝟑 : 𝒔𝟑 + 𝟐 ≤ 𝒔𝟒
𝑪𝟒 : 𝒔𝟒 + 𝟏 ≤ 𝒔𝟓
𝑪𝟓 : 𝒔𝟓 + 𝟐 ≤ 𝒔𝟔
La tâche T1 ne peut pas être planifiée à la même heure que la tâche T4 :
𝑪𝟔 : 𝒔𝟏 ≠ 𝒔𝟒
2. (1 pt) Dessiner le graphe de contraintes de ce CSP. Commenté [LL1]:

S6 𝑪𝟓
𝑪𝟏
S1 S5

𝑪𝟔 𝑪𝟒

𝑪𝟐
S2 S4
𝑪𝟑
S3

3. (2,75 pts) Le CSP est-il arc consistant. S’il ne l’est pas, rendre ce CSP arc-consistant.

Le CSP n’est pas arc consistant.

Contrainte considérée Domaines (valeurs en rouges sont les valeurs supprimées)

𝑪𝟏 (𝒔𝟏 , 𝒔𝟔 ) 𝑫(𝒔𝟏 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓}, 𝑫(𝒔𝟔 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓}
𝑪𝟐 (𝒔𝟐 , 𝒔𝟒 ) 𝑫(𝒔𝟐 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓}, 𝑫(𝒔𝟒 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓}
𝑪𝟑 (𝒔𝟑 , 𝒔𝟒 ) 𝑫(𝒔𝟑 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒}, 𝑫(𝒔𝟒 ) = {𝟏, 𝟐, 𝟑, 𝟒, 𝟓}
𝑪𝟒 (𝒔𝟒 , 𝒔𝟓 ) 𝑫(𝒔𝟒 ) = { 𝟐, 𝟑, 𝟒, 𝟓}, 𝑫(𝒔𝟓 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒}
𝑪𝟓 (𝒔𝟓 , 𝒔𝟔 ) 𝑫(𝒔𝟓 ) = { 𝟑, 𝟒}, 𝑫(𝒔𝟔 ) = {𝟏, 𝟐, 𝟑, 𝟒, 𝟓}
𝑪𝟔 (𝒔𝟏 , 𝒔𝟒 ) 𝑫(𝒔𝟏 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒}, 𝑫(𝒔𝟒 ) = {𝟐, 𝟑}
𝑪𝟐 (𝒔𝟐 , 𝒔𝟒 ) 𝑫(𝒔𝟐 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒}, 𝑫(𝒔𝟒 ) = {𝟐, 𝟑}
𝑪𝟑 (𝒔𝟑 , 𝒔𝟒 ) 𝑫(𝒔𝟑 ) = {𝟎, 𝟏, 𝟐, 𝟑}, 𝑫(𝒔𝟒 ) = {𝟐, 𝟑}
𝑪𝟒 (𝒔𝟒 , 𝒔𝟓 ) 𝑫(𝒔𝟒 ) = { 𝟐, 𝟑}, 𝑫(𝒔𝟓 ) = {𝟑}
𝑪𝟐 (𝒔𝟐 , 𝒔𝟒 ) 𝑫(𝒔𝟐 ) = {𝟎, 𝟏, 𝟐}, 𝑫(𝒔𝟒 ) = {𝟐}
𝑪𝟑 (𝒔𝟑 , 𝒔𝟒 ) 𝑫(𝒔𝟑 ) = {𝟎, 𝟏}, 𝑫(𝒔𝟒 ) = {𝟐}

5/5
Université Oran1 Date : 10-12-2023
Département d’informatique
Parcours : Master2-ADSI
Matière : Programmation par contraintes (PPC)

Test 2 de la matière PPC - Durée : 01h00

Exercice 1 (8 points)
Soit le réseau de contraintes suivant. Déroulez AC3 pour atteindre le point fixe.

Contrainte considérée X1 X2 X3 X4
Domaines initiaux → {2} {1,2,3,4} {1,2,3,4} {3}
X1 >= X2 {2} {1,2,3,4} {1,2,3,4} {3}
X2 < X3 {2} {1,2} {1,2,3,4} {3}
X3  X4 {2} {1,2} {2,3,4} {3}
X2 < X3 {2} {1,2} {2,4} {3}

Exercice 2 (7 points)
Le problème des n-reines (n-Queens) est de placer n reines d’un jeu d’échecs sur un échiquier de n × n
cases sans que les dames ne puissent se menacer mutuellement, i. e. deux reines ne devraient jamais
partager la même ligne, colonne, ou diagonale.
X1 X2 X3 X4
1
2
3
4

1. (2 pts) Donner un modèle CSP du problème.

a. Variables : 𝑿 = {𝑿𝟏 , 𝑿𝟐 , 𝑿𝟑 , 𝑿𝟒 }
b. Domaines : 𝑫(𝑿𝟏 ) = 𝑫(𝑿𝟐 ) = 𝑫(𝑿𝟑 ) = 𝑫(𝑿𝟒 ) = {𝟏, 𝟐, 𝟑, 𝟒}
c. Contraintes : 𝑪 = {𝑪𝟏 , 𝑪𝟐 }
𝑪𝟏 : les 4 reines doivent être sur des colonnes différentes :
𝑪𝟏 = {𝑿𝒊 ≠ 𝑿𝒋 , 𝒊 ≠ 𝒋; 𝒊, 𝒋 = 𝟏, . . , 𝟒}
𝑪𝟐 : les reines ne doivent pas être sur la même diagonale :
𝑪𝟐 = {|𝑿𝒊 − 𝑿𝒋 | ≠ |𝒊 − 𝒋|, 𝟏 ≤ 𝒊 < 𝒋 ≤ 𝟒}

2. (2 pts) Dérouler l’algorithme de backtrack (BT) à partir de l’instanciation 𝐼1 .

1/3
Université Oran1 Date : 10-12-2023
Département d’informatique
Parcours : Master2-ADSI
Matière : Programmation par contraintes (PPC)

Test 2 de la matière PPC - Durée : 01h00

X X X

X X X X
3. (2 pts) Calculez la fermeture AC3 du sous-réseau 𝐼1 .
Contrainte considérée X1 X2 X3 X4
Domaines initiaux → {4} {1} {1,2,3,4} {1,2,3,4}
C1 {4} {1} {1,2,3,4} {1,2,3,4}
C2 {4} {1} {3} {2}
C1 {4} {1} {3} {2}

4. (1 pt) Dérouler encore une fois l’algorithme du BT après le calcul du point fixe.
L’instanciation 𝑰𝟏 n’est pas consistante. AC3 a produit une variable (X4) de domaine vide .

Exercice 3 (5 points)
On doit planifier six tâches dans un délai de 6 heures :

Une tâche en début de flèche doit s’effectuer avant la tâche en fin de flèche. Par exemple, T2 doit
s’effectuer avant T4, T4 avant T5 et T5 avant T6. Les durées des tâches sont indiquées au-dessus des
tâches. Chaque tâche ne peut commencer qu’en début d’une heure. De plus, la tâche T1 ne peut pas être
planifiée à la même heure que la tâche T4.

- Question 1 : Modélisez ce problème comme un CSP.

2/3
Université Oran1 Date : 10-12-2023
Département d’informatique
Parcours : Master2-ADSI
Matière : Programmation par contraintes (PPC)

Test 2 de la matière PPC - Durée : 01h00

o Variables : 𝑿 = {𝒔𝒊 , 𝒊 = 𝟏, . . , 𝟔 : temps de début de la tâche 𝒊}.
o Domaines : 𝑫(𝒔𝒊 ) = {𝟎, 𝟏, . . , 𝟔 − 𝒑𝒊 }, 𝒊 = 𝟏, … , 𝟔 où 𝒑𝒊 est la durée de la tâche 𝑻𝒊.
𝑫(𝒔𝟏 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓}
𝑫(𝒔𝟐 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓}
𝑫(𝒔𝟑 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒}
𝑫(𝒔𝟒 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓}
𝑫(𝒔𝟓 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒}
𝑫(𝒔𝟔 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓}

o Contraintes : 𝑪 = {𝑪𝟏 , 𝑪𝟐 , 𝑪𝟑 , 𝑪𝟒 , 𝑪𝟓 , 𝑪𝟔 }
Contraintes de précédence :
𝑪𝟏 : 𝒔𝟏 + 𝟏 ≤ 𝒔𝟔
𝑪𝟐 : 𝒔𝟐 + 𝟏 ≤ 𝒔𝟒
𝑪𝟑 : 𝒔𝟑 + 𝟐 ≤ 𝒔𝟒
𝑪𝟒 : 𝒔𝟒 + 𝟏 ≤ 𝒔𝟓
𝑪𝟓 : 𝒔𝟓 + 𝟐 ≤ 𝒔𝟔

La tâche T1 ne peut pas être planifiée à la même heure que la tâche T4 :

𝑪𝟔 : 𝒔𝟏 ≠ 𝒔𝟒

- Question 2 : Rendez ce CSP arc-consistant.

Contrainte considérée Domaines (valeurs en rouges sont les valeurs supprimées)
𝑪𝟏 𝑫(𝒔𝟏 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓}, 𝑫(𝒔𝟔 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓}
𝑪𝟐 𝑫(𝒔𝟐 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓}, 𝑫(𝒔𝟒 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓}
𝑪𝟑 𝑫(𝒔𝟑 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒}, 𝑫(𝒔𝟒 ) = {𝟏, 𝟐, 𝟑, 𝟒, 𝟓}
𝑪𝟒 𝑫(𝒔𝟒 ) = { 𝟐, 𝟑, 𝟒, 𝟓}, 𝑫(𝒔𝟓 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒}
𝑪𝟓 𝑫(𝒔𝟓 ) = { 𝟑, 𝟒}, 𝑫(𝒔𝟔 ) = {𝟏, 𝟐, 𝟑, 𝟒, 𝟓}
𝑪𝟔 𝑫(𝒔𝟏 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒}, 𝑫(𝒔𝟒 ) = {𝟐, 𝟑}
𝑪𝟐 𝑫(𝒔𝟐 ) = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒}, 𝑫(𝒔𝟒 ) = {𝟐, 𝟑}
𝑪𝟑 𝑫(𝒔𝟑 ) = {𝟎, 𝟏, 𝟐, 𝟑}, 𝑫(𝒔𝟒 ) = {𝟐, 𝟑}
𝑪𝟒 𝑫(𝒔𝟒 ) = { 𝟐, 𝟑}, 𝑫(𝒔𝟓 ) = {𝟑}
𝑪𝟐 𝑫(𝒔𝟐 ) = {𝟎, 𝟏, 𝟐}, 𝑫(𝒔𝟒 ) = {𝟐}
𝑪𝟑 𝑫(𝒔𝟑 ) = {𝟎, 𝟏}, 𝑫(𝒔𝟒 ) = {𝟐}

3/3
Université Oran1
Département d’informatique
Parcours : Master2-ADSI
Matière : Programmation par contraintes (PPC)
Date : 22-10-2023

Test 1 de la matière PPC

Exercice 1 (8 points : 1pt par question)

Sur la feuille de réponse, indiquez le n° de la question suivie du n° de la réponse. Par exemple : Q1-a ; Q2-
a, etc.
Question 1 : Dans un CSP, quelles sont les trois composantes de base ?
a) Variables, domaines, objectifs
b) Variables, domaines, contraintes
c) Variables, objectifs, contraintes
d) Contraintes, objectifs, domaines
Question 2 : Quelle est le principal but d'un CSP ?
a) La recherche de solutions optimales
b) La recherche d'une réponse binaire (oui/non)
c) La recherche de solutions en temps réel
d) La recherche de solutions à un problème complexe
Question 3 : Quelle est la différence entre une variable libre et une variable affectée dans un CSP ?
a) Une variable libre est une variable sans valeur, tandis qu'une variable affectée a une valeur.
b) Une variable libre est une variable non utilisée, tandis qu'une variable affectée est utilisée.
c) Une variable libre est une variable qui ne respecte pas les contraintes, tandis qu'une variable
affectée les respecte.
d) Il n'y a pas de différence entre une variable libre et une variable affectée.
Question 4 : Quel est le but principal de la propagation de contraintes dans la résolution de CSP ?
a) Réduire l'espace des solutions en éliminant des valeurs de domaine possibles.
b) Générer toutes les solutions possibles en respectant les contraintes.
c) Maximiser le nombre de contraintes dans un CSP.
d) Minimiser le nombre de variables dans un CSP.
Question 5 : Quelle méthode de résolution de CSP consiste à essayer systématiquement différentes
combinaisons de valeurs pour les variables jusqu'à trouver une solution ?
a) Recherche locale
b) Recherche par propagation
c) Recherche par contrainte
d) Recherche exhaustive (énumérative)
Question 6 : Quelle est la complexité du pire cas de la résolution d'un CSP en utilisant une recherche
exhaustive ?
a) Linéaire
b) Quadratique
c) Exponentielle
d) Constante
Question 7 : Dans un CSP, qu'est-ce qu'une contrainte unaire ?
a) Une contrainte qui relie deux variables.
b) Une contrainte qui n'affecte qu'une seule variable.
c) Une contrainte qui s'applique à toutes les variables.
d) Une contrainte qui est impossible à satisfaire.
Question 8 : Quelle est l'étape initiale dans la modélisation d'un CSP à l'aide d'un algorithme de
recherche ?
a) Propagation de contraintes

1/3
 b) Définition des variables
c) Définition des domaines
d) Énumération des solutions

Exercice 2 (12 points)

La sous-direction de la pédagogie du département d’informatique est chargée de planifier 5 cours
d'informatique qui doivent avoir lieu le dimanche, mardi et jeudi de chaque semaine. Les 5 cours sont
assurés par 3 professeurs. Les cours sont :
- Cours 1 (C1) - Introduction à la programmation : se déroule de 8h00 à 9h00.
- Cours 2 (C2) - Intro à l'intelligence artificielle : se déroule de 8h30 à 9h30.
- Cours 3 (C3) - Traitement du langage naturel : se déroule de 9h00 à 10h00
- Cours 4 (C4) - Vision par ordinateur : se déroule de 9h00 à 10h00
- Cours 5 (C5) - Apprentissage automatique : se déroule de 9h30 à 10h30.

Chaque professeur ne peut enseigner qu'un seul cours à la fois dans un créneau donné. Les disponibilités
des professeurs sont comme suit :
- A qui est disponible pour enseigner les cours 3 et 4.
- Le professeur B qui est disponible pour enseigner les cours 2, 3, 4 et 5.
- Le professeur C qui est disponible pour enseigner les cours 1, 2, 3, 4 et 5.
1. Formulez ce problème en un CSP P(X, D, C) dans lequel les variables représentent les cours.
Définir clairement les domaines des variables et les contraintes du problème.
(1.5 pt)
Variables Domaines
C1 C
C2 B, C
C3 A, B, C
C4 A, B, C
C5 B, C

(2 pts) Contraintes binaires :

C1  C2
C2  C3
C3  C4
C4  C5
C2  C4
C3  C5
2. Citez un exemple de :
a. (1 pt) Instanciation partielle
Instanciation d’un sous-ensemble de variables du problème. Par exemple : C2 = B, C4 =
A
b. (1 pt) Instanciation totale (complète)
Instanciation de toutes les variables du CSP, pas obligatoirement consistante. Par
exemple : C1 = C, C2 = C, C3 = A, C4 = A, C5 = B.
c. (1 pt) Instanciation localement consistante
Instanciation d’un ensemble de variables du CSP qui vérifie toutes les contraintes
portant sur ces variables. Par exemple : C2 = B, C3 = A, C5 = C
d. (1 pt) Instanciation partielle globalement consistante
Instanciation partielle qui peut être étendue à une solution. Par exemple : C2 = B, C4 =
A, C5 = B.
e. (1 pt) Instanciation complète globalement consistante
Une instanciation complète globalement consistante correspond à une solution du CSP. En voici
2 exemples de solutions :
C1 = C, C2 = B, C3 = C, C4 = A, C5 = B.

2/3
 C1 = C, C2 = B, C3 = A, C4 = C, C5 = B.
3. (1,5 pt) Dessinez le graphe de contraintes associé à ce CSP. Indiquez sur le graphe les domaines
des variables et les contraintes.

C1  C2

 

C3  C4


C5

4. (2 pt) Donnez les domaines des variables après avoir exécuté la consistance d’arc sur ce graphe
initial.

{C} {B,C}

C1  C2

 

C3  C4


{A,B,C}  {A,B,C}
C5

{B,C}

Domaine des variables après l’exécution de la consistance d’arc :

Variables Domaines
C1 C
C2 B
C3 A, C
C4 A, B, C
C5 B, C

3/3
Université Oran1
Département d’informatique
Parcours : Master2-ADSI
Année universitaire : 2022-2023
04-12-2022

Test de la matière PPC (durée : 01h)

Exercice 1 : Cryptarithmétique
On considère l’équation suivante :

TWO
+
TWO
------------
= FOUR

où chaque lettre doit prendre un chiffre différent entre 0 et 9, et la première lettre de chaque mot
représente un chiffre différent de 0. On souhaite affecter une valeur à chacune des lettres de sorte que
l’addition soit correcte.

Question : Formulez ce problème sous forme d'un problème de satisfaction de contraintes 𝑃 = (𝑋, 𝐷, 𝐶).
Donnez 2 formulations différentes pour ce problème

Exercice 2 : Coloration de carte

Soit la carte suivante décrivant les frontières entre quatre villes (V1, V2, V3, V4). On souhaite colorier la carte
en utilisant 3 couleurs rouge, bleu et vert (notées R, B, V), de sorte que V1 soient en rouge ou en bleu; V2
et V3 soient en bleu ou en vert; et V4 soit en rouge. Toutefois, deux villes adjacentes ne peuvent avoir la
même couleur.

1. Modéliser ce problème sous la forme d'un problème de satisfaction de contraintes (CSP). Vous devez
clairement indiquer les variables, les domaines des variables et les contraintes entre ces dernières.
2. Donner le graphe de contraintes.
Remarque : Un graphe de contraintes est un graphe dont les nœuds sont des variables (un nœud par
variable) et les arcs sont des contraintes entre les deux variables.

3. Dérouler l’algorithme d’arc-consistance-3 sur ce problème. Le problème a-t-il une solution ? Justifiez.

1/4
 Corrigé type

Exercice 1 : Cryptarithmétique

Formulation 1 :

X = {T,W,O,F,U,R}

D(F) = D(T) = [1,9] // = {1,2,3,4,5,6,7,8,9}

D(W) = D(O) = D(U) = D(R) = [0,9] // = {0,1,2,3,4,5,6,7,8,9}

Contraintes :

C1 : 100*T + 10*W + O

+ 100*T + 10*W + O

= 1000*F + 100*O + 10*U + R

C2 : all-different({T,W,O,F,U,R })

Formulation 2 :

X = {T,W,O,F,U,R,r1,r2,r3}

D(F) = D(T) = [1,9] // = {1,2,3,4,5,6,7,8,9}

D(W) = D(O) = D(U) = D(R) = [0,9] // = {0,1,2,3,4,5,6,7,8,9}

D(r1) = D(r2) = D(r3) = [0,1] // = {0,1}

C1 : O + O = R + 10*r1

C2 : W + W + r1 = U + 10*r2

C3 : T + T + r2 = O + 10*r3

C4: F = r3

C5 = all-different({T,W,O,F,U,R })

Exercice 2 : Problème de coloration de graphe

1- Modèle CSP (X, D, C):
- Variables X : on associe une variable à chaque ville : X = {V1, V2, V3, V4}

- Domaines D : On note les trois couleurs possibles (rouge, bleu et vert) par {R, B, V}
D(V1) = {R, B}
D(V2) = {B, V}
D(V3) = {B, V}
D(V4) = {R}

2/4
 - Contraintes C : Les villes frontalières doivent avoir des couleurs différentes (le nombre de
contraintes = nombre d’arêtes) :
C = {V1 ≠ V2, V1 ≠ V3, V1 ≠ V4, V2 ≠ V3, V3 ≠ V4}

2- Le graphe des contraintes.

3- Déroulement de l’AC-3
V1 V2 V3 V4 Arc-consistency Ensemble des arcs
{R, B} {B,V} {B,V} {R} S={V1→V2, V2→V1, V1→V3, V3→V1, V1→V4,
V4→V1, V2→V3, V3→V2, V3→V4, V4→V3}
{R,B} {B,V} {B,V} {R} V1→V2 S={V1→V2, V2→V1, V1→V3, V3→V1, V1→V4,
V4→V1, V2→V3, V3→V2, V3→V4, V4→V3}
{R,B} {B,V} {B,V} {R} V2→V1 S={V1→V2, V2→V1, V1→V3, V3→V1, V1→V4,
V4→V1, V2→V3, V3→V2, V3→V4, V4→V3}
{R,B} {B,V} {B,V} {R} V1→V3 S={V1→V2, V2→V1, V1→V3, V3→V1, V1→V4,
V4→V1, V2→V3, V3→V2, V3→V4, V4→V3}
{R,B} {B,V} {B,V} {R} V3→V1 S={V1→V2, V2→V1, V1→V3, V3→V1, V1→V4,
V4→V1, V2→V3, V3→V2, V3→V4, V4→V3}
{R,B} {B,V} {B,V} {R} V1→V4 S={V1→V2, V2→V1, V1→V3, V3→V1, V1→V4,
V4→V1, V2→V3, V3→V2, V3→V4, V4→V3,
V2→V1, V3→V1, V4→V1}
{R,B} {B,V} {B,V} {R} V4→V1 S={V1→V2, V2→V1, V1→V3, V3→V1, V1→V4,
V4→V1, V2→V3, V3→V2, V3→V4, V4→V3,
V2→V1, V3→V1, V4→V1}
{R,B} {B,V} {B,V} {R} V2→V3 S={V1→V2, V2→V1, V1→V3, V3→V1, V1→V4,
V4→V1, V2→V3, V3→V2, V3→V4, V4→V3,
V2→V1, V3→V1, V4→V1}
{R,B} {B,V} {B,V} {R} V3→V2 S={V1→V2, V2→V1, V1→V3, V3→V1, V1→V4,
V4→V1, V2→V3, V3→V2, V3→V4, V4→V3,
V2→V1, V3→V1, V4→V1}
{R,B} {B,V} {B,V} {R} V3→V4 S={V1→V2, V2→V1, V1→V3, V3→V1, V1→V4,
V4→V1, V2→V3, V3→V2, V3→V4, V4→V3,
V2→V1, V3→V1, V4→V1}
{R,B} {B,V} {B,V} {R} V4→V3 S={V1→V2, V2→V1, V1→V3, V3→V1, V1→V4,
V4→V1, V2→V3, V3→V2, V3→V4, V4→V3,
V2→V1, V3→V1, V4→V1}

3/4
 {R,B} {B,V} {B,V} {R} V2→V1 S={V1→V2, V2→V1, V1→V3, V3→V1, V1→V4,
V4→V1, V2→V3, V3→V2, V3→V4, V4→V3,
V2→V1, V3→V1, V4→V1, V1→V2, V3→V2}
{R,B} {B,V} {B,V} {R} V3→V1 S={V1→V2, V2→V1, V1→V3, V3→V1, V1→V4,
V4→V1, V2→V3, V3→V2, V3→V4, V4→V3,
V2→V1, V3→V1, V4→V1, V1→V2, V3→V2,
V1→V3, V2→V3, V4→V3}
{R,B} {B,V} {B,V} {R} V4→V1 S={V1→V2, V2→V1, V1→V3, V3→V1, V1→V4,
V4→V1, V2→V3, V3→V2, V3→V4, V4→V3,
V2→V1, V3→V1, V4→V1, V1→V2, V3→V2,
V1→V3, V2→V3, V4→V3}
{R,B} {B,V} {B,V} {R} V1→V2 S={V1→V2, V2→V1, V1→V3, V3→V1, V1→V4,
V4→V1, V2→V3, V3→V2, V3→V4, V4→V3,
V2→V1, V3→V1, V4→V1, V1→V2, V3→V2,
V1→V3, V2→V3, V4→V3}
{R,B} {B,V} {B,V} {R} V3→V2 S={V1→V2, V2→V1, V1→V3, V3→V1, V1→V4,
V4→V1, V2→V3, V3→V2, V3→V4, V4→V3,
V2→V1, V3→V1, V4→V1, V1→V2, V3→V2,
V1→V3, V2→V3, V4→V3}

Le domaine de la variable V3 devient vide. Il n’y a donc pas de solution.

4/4