Mestrado/Licenciatura em Engenharia Informática - 2006/07
Programação por Restrições – 1º teste
Sem consulta
8 de Novembro de 2006
Duração: 1h e 15m
I - Restrições Booleanas
Pretende-se especificar a soma aritmética de dois números de 2 bits cada, AB e CD,
respectivamente, tendo em atenção que os números são tais que a soma pode ser
sempre representada sem erro por dois bits, XY, tal como apresentado ao lado.
AB
+CD
XY
1. Especifique as restrições booleanas que descrevem esta especificação, utilizando a sintaxe
do SICStus Prolog (módulo CLPB). Nota: Como sabe, no SICStus Prolog (módulo CLPB),
as restrições de igualdade e desigualdade têm a forma sat(E1 =:= E2) e sat(E1 =\= E2),
respectivamente, em que E1 e E2 são expressões booleanas construídas com os operadores
de negação (~), conjunção (*), disjunção (+) e disjunção exclusiva (#).
2. Indique, justificando, quais dos unificadores abaixo são soluções do problema.
a.
b.
c.
d.
e.
{X/B·D#(1#B·D)·(W#Z#W·Z), Y/B # D,
{X/B # D, Y/B·D#(1#B·D)·(W#Z#W·Z),
{X/B·D#(1#B·D)·W,
Y/B # D,
{X/B·D#(1#B·D)·(W#Z#W·Z), Y/B # D,
{X/B·D#(1#B·D)·Z,
Y/B # D,
A/(1#B·D)·W, C/(1#B·D)·(1#W)·Z}
A/(1#B·D)·W, C/(1#B·D)·(1#W)·Z}
A/(1#B·D)·W, C/0
}
A/(1#B·D)·(1#W)·Z, C/(1#B·D)·W}
A/ 0,
C/(1#B·D)·Z
}
3. Indique quais dos unificadores acima são unificadores mais gerais? Justifique.
Programação por Restrições
1º teste de 2006/07
1/2
II - Restrições sobre Racionais
A
B
7
5
a) Modele a seguinte especificação num problema de
restrições lineares em domínios reais/racionais,
8
explicitando o significado das variáveis que utilizou
9
e o significado das restrições utilizadas.
13
12
Uma empresa tem um recinto com 3 entradas, A, B
8
e C, ligadas por estradas, conforme ilustrado na
6
figura. Para além das estradas directas entre as
5
entradas, Existe ainda uma rotunda, por onde se
6
pode desviar algum tráfego. Cada sentido de cada
11
troço permite o fluxo máximo de veículos (em
8
dezenas de veículos por hora) igualmente indicado
na figura.
C
O tráfego esperado das entradas para as saídas é descrito através da seguinte tabela, em que os
valores são igualmente referidos a dezenas de veículos por hora.
X -> Y
A
B
C
A
0
10
12
B
15
0
9
C
8
15
0
Para evitar congestionamentos na rotunda, deverá garantir-se que o tráfego total entrado por
hora na rotunda não excede 23 dezenas de veículos. Adicionalmente, nenhuma entrada na
rotunda deverá ter um tráfego mais do que 3 vezes superior ao tráfego de qualquer das outras
entradas e, similarmente, nenhuma saída da rotunda deverá ter um tráfego mais do que 3 vezes
superior ao tráfego de qualquer das outras saídas.
b) A modelação de um problema de restrições lineares sobre variáveis reais/racionais conduziu ao
seguinte modelo (em que x, y, z, w ≥ 0):
2x + 2y + z
≤ 10
x + y
≥ 5
x – y + z
≥ 1
x + y
+ w ≤ 8
z + w ≥ 3
1. Mostre, convertendo estas restrições para a forma SF2, que pelo menos uma variável tem de
tomar um valor fixo. Qual (ou quais) ?
Sugestão: Utilize x, y e z como variáveis básicas.
2. Das restrições abaixo quais podem ser satisfeitas? Justifique.
• x + y ≠ 5
• z + w ≠ 2
• x + w ≠ 7
Programação por Restrições
1º teste de 2006/07
2/2