Scribd
Importer
2 vues1 page

Travaux Dirigés Série Numéro 4: Consistance de Chemin: Exercice 1

Le document présente des travaux dirigés pour le module 'Programmation Par Contraintes' du Master 2 en Systèmes Informatiques Intelligents. Il contient deux exercices portant sur la consistance de chemin d'un problème de satisfaction de contraintes (CSP) binaire, incluant des représentations matricielles et des algorithmes pour vérifier la consistance. Les exercices demandent des implémentations de fonctions pour calculer l'intersection et la composition de contraintes sous forme de matrices.

Transféré par

Maria Lmn
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
2 vues1 page

Travaux Dirigés Série Numéro 4: Consistance de Chemin: Exercice 1

Le document présente des travaux dirigés pour le module 'Programmation Par Contraintes' du Master 2 en Systèmes Informatiques Intelligents. Il contient deux exercices portant sur la consistance de chemin d'un problème de satisfaction de contraintes (CSP) binaire, incluant des représentations matricielles et des algorithmes pour vérifier la consistance. Les exercices demandent des implémentations de fonctions pour calculer l'intersection et la composition de contraintes sous forme de matrices.

Transféré par

Maria Lmn
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

USTHB, FEI, Département d’Informatique

LMD Master 2 ‘‘Systèmes Informatiques Intelligents’’ 2019/2020

Module ‘‘Programmation Par Contraintes’’

Travaux Dirigés

Série numéro 4 : Consistance de chemin

Exercice 1 :

On considère le CSP discret binaire P=(X,D,C) suivant :


 X = {X1, X2, X3}
 D(X1)=D(X2)=D(X3)={(0,1),(2,1),(0,4),(2,4)}
 C = {c1, c2, c3} avec
o c1 : oblique(X1,X2)
o c2 : oblique(X1,X3)
o c3 : oblique(X2,X3)
Pour tous points A et B du plan, donnés par leurs coordonnées (a 1,b1) et (a2,b2), respectivement :
oblique(A,B) si et seulement si (a1a2 et b1b2)
1) Donnez une représentation matricielle de P.
2) Le CSP est-il consistant ? s’il ne l’est pas, un algorithme de consistance de chemin tel que PC2
peut-il en détecter l’inconsistance ? si oui, montrez comment ?

Exercice 2 :

Soit P un CSP binaire discret donné par sa représentation matricielle MP. Vous supposerez que P a n
variables X1,…,Xn et que toutes les variables ont le même domaine D=D(X1)=…=D(Xn), de taille m. On
notera par MP[i,j] l’élément (i,j) de la matrice MP. Le but de l’exercice est de donner un algorithme
implémentant l’opération de consistance de chemin MP[i,j]=MP[i,j]MP[i,k]MP[k,k] MP[k,j]. Pour ce
faire, il vous est demandé de procéder comme suit :

1) Donnez une fonction inters calculant l’intersection de deux contraintes représentées sous forme de matrices
2) Donnez une fonction comp calculant la composition de deux contraintes représentées sous forme de
matrices
3) Utilisez les deux fonctions inters et comp pour donner une fonction pc implémentant l’opération de
consistance de chemin

Page 1 sur 1

Vous aimerez peut-être aussi