Programação em Lógica com Restrições, 2011/12
Exame de Época Normal
DI-FCT/UNL
21 de Janeiro de 2012
Programação em Lógica com Restrições
Exame sem consulta - Duração: 3 horas
Nº:
Nome:
Grupo 1 (4 valores)
1 a)
Para cada um dos seguintes golos, indique se sucede (com V, de Verdadeiro) ou se falha
(com F, de Falso).
Nota: Nesta alínea cada resposta certa vale 0,1 valores, e cada resposta errada vale –0,1 valores (negativo,
portanto). Se não sabe a resposta, não responda.
fail, !
[x,y|T]-T = [X|L]
0=1 ; 1=Zero
assertz(f), \+ var(f)
X+(Y*Y) = 3+4
repeat, !, write(W)
t(X,Y) == t(Y,X)
member(X,[0,1,2]), X*2=:=3-X
[a,b|[a|[]]]=[X,Y,Z|_]
1*2+3/2 =.. [A,B,C]
1 b)
Preencha corretamente os quadrados em branco abaixo, relativos ao predicado
divide(+Lista,-Div) que dada uma lista de termos X+Y ou X-Y, devolve uma lista em que
primeiro aparecem todos os elementos da forma X+Y, e depois todos os da forma X-Y.
Exemplo:
?- divide([3-1,4+1,1+2,a-b,3+3], Div).
Div = [4+1,1+2,3+3,3-1,a-b]
divide(L, SomaSub) :- divLD(L,
).
divLD([], X-X, Y-Y).
divLD([
divLD(
|L], [A+B|X]-DX,
, X,
) :- divLD(L,
,Y).
) :- divLD(L, X, Y-DY).
Página 1 de 10
1 c)
Considere o seguinte programa no ficheiro c.pl:
:- dynamic p/1.
p(1). p(2). p(3).
r(X):- p(X), X>1, !, assert(p(2*X)).
r(4):- !.
r(X):- r(2*X).
s(Z):- !, clause(p(X), _), Z is 2*X, retract(p(Z)).
s(4):- abolish(p/1).
Indique a (primeira) solução dos seguintes golos (caso não tenha solução, escreva ‘no’).
(Recorda-se que o golo ‘[c]’ compila o ficheiro c.pl)
Exemplos:
?- [c], p(X).
X=1
?- [c], r(R).
?- [c], 4=R, r(R), p(R).
?- [c], s(R), s(R).
?- [c], 2=X, s(X), p(X).
1 d)
?- [c], X=2, p(X).
X=2
?- R=4, [c], r(R).
?- [c], s(R).
?- [c], P=2*1, p(P).
?- [c], S=4, s(S).
Num golo, defina o operador € de modo a poder trabalhar com termos como 4€ e 3€5
(representando respetivamente, 4 euros, e 3 euros e 50 cêntimos), e até como 2€ + 3€ ou
4*12€30 (representando 5, e 49,20 euros, resp.).
Nota:
?- current_op(1200, _, :-).
yes
?- current_op(Prec, _Assoc, ’,’).
Prec = 1000
?- current_op(P, _, +).
P = 500 ; P = 200 ; no
?- current_op(400, _, *).
yes
?-
Página 2 de 10
Programação em Lógica com Restrições, 2011/12
Exame de Época Normal
Nº:
Grupo 2 (3 valores)
Consistência de Restrições.
2 a)
Com as variáveis X::0..9, Y::2..7, Z::1..6, e as restrições X#=Z, X#<Y e Y#<X, indique na
tabela seguinte em colunas sucessivas (até um ponto fixo) como vão evoluindo os domínios
de X e Y com o acordar/uso duma das restrições, se se aplicar Consistência de Intervalo.
Restrição
X#=Z
Dom(X)
1..6
Dom(Y)
2..7
2 b)
Preencha as diagonais principais (8 células) de dois sudokus 4x4 (onde cada linha, cada
coluna, e os 4 sub-quadrados 2x2 devem ter os números 1 a 4), S1 e S2, de modo a que, aplicando
Consistência de Nó, S1 não necessite de enumeração para se encontrar a sua (única) solução, e S2
fique apenas com esses 8 valores instanciados (sem falhar). Nota: só há restrições binárias de diferença.
S1: Suficiente para ficar resolvido
1
S2: Sem mais instanciações
1
Com esses 8 valores preenchidos, com quantas soluções fica S2?
2 c)
Aplicando Consistência de Arco, qual a resposta a um golo como X,Y,Z::0,1, X#\=Y, X#\=Z,
Y#\=Z, e porquê?
Resposta
Prolog:
Porquê:
Página 3 de 10
Grupo 3 (10 valores)
Implemente em Prolog os seguintes predicados, procurando sempre uma solução simples, eficiente, e
legível:
3 a)
Imagine uma estrutura de dados num termo cidade(Rua1,..,Ruar), com informação sobre as r
ruas duma cidade, onde Ruai é um termo rua(Predio1,…,Prediop), representando os p prédios da rua i,
onde Predioj é uma lista aberta com o número de habitantes de cada andar do prédio situado no número
j dessa rua. Por exemplo:
cidade(rua([2,3,2|_],_,[0,5|_]), rua([6,6,8,3|_],[3,4|_]), rua(_,_,[5,6,7,6,7|_],[1,1,0,0|_],[4|_]))
São usadas listas abertas para mais facilmente considerar a eventual construção de andares extra no
topo dos prédios. Uma lista aberta vazia significa que o local está livre (por exemplo, o prédio foi
demolido).
Implemente então andares(+Cidade, +RuaN, +Num, -Habitantes, -Andares) que dada uma tal
Cidade, um número de rua (RuaN) e um número de porta/prédio Num, devolve não só a quantidade de
Andares desse prédio, mas também o total dos seus Habitantes. Para o exemplo da cidade acima,
temos os seguintes valores de Habitantes/Andares:
Rua \ Prédio
1
2
3
Página 4 de 10
1
7/3
23/4
0/0
2
0/0
7/2
0/0
3
5/2
31/5
4
2/4
5
4/1
Programação em Lógica com Restrições, 2011/12
Exame de Época Normal
Nº:
3 b)
predios(+Cidade, -NPredios), que dada uma Cidade como na alínea anterior, devolve o seu
número total de prédios efetivos (aqueles que têm andares). Em cada rua, use o findall/3 para encontrar
os seus prédios (não use andares/5). No exemplo anterior, o total de prédios é 7.
3 c)
arestas(+Pontos, -PontosEArestas), que dada uma lista, Pontos, de coordenadas
bidimensionais (ora abcissas X, ora ordenadas, Y), devolve a lista, PontosEArestas, com esses pontos
na forma p(X,Y) pela mesma ordem, entremeados pela distância entre os respetivos pontos. Recorda-se
o teorema de Pitágoras: “O quadrado da hipotenusa é igual à soma dos quadrados dos catetos.”
E.g. ?- arestas([0,0, 1,1, 1,1, 1,4, 0,4], R).
R = [p(0,0), 1.4142, p(1,1), 0, p(1,1), 3, p(1,4), 1, p(0,4)]
Página 5 de 10
3 d)
bipartido(+Nos1, +Nos2), que dados 2 conjuntos (listas) de Nós, verifica se correspondem às
2 partes dum grafo bipartido, considerando que estão definidos os arcos entre 2 nós no predicado
arco/2. Recorda-se que um grafo bipartido é um par de conjuntos disjuntos de nós, onde os arcos
envolvendo esses nós ligam sempre os 2 conjuntos (i.e. não há arcos dentro dum conjunto).
E.g.
arco(a,b). arco(a,c). arco(a,d). arco(b,c). arco(b,e). arco(c,d).
?- bipartido([a,e,f],[b,d]).
?- bipartido([b,d,e],[a]).
yes
no
?- bipartido([b],[e,c]).
?- bipartido([c,e],[a,e]).
yes
no
Página 6 de 10
Programação em Lógica com Restrições, 2011/12
Exame de Época Normal
Nº:
3 e)
avalia(?Exp, ?Val) que dada uma expressão boleana, Exp, com os operadores + e *
representando a disjunção e a conjunção, respetivamente, devolve o seu valor Val (0 ou 1).
Adicionalmente, permita que o predicado funcione nos 2 sentidos: se dado o valor, devolve ou
completa uma expressão possível. Exemplos:
?- avalia(0+0+1+0+1, V).
V = 1 ; no
?- avalia((0+(0*1)+1)*0+0, V).
V = 0 ; no
?- avalia(Exp, 1).
Exp = 1 ; Exp = 1+0
?- avalia(X+(Y*Z), 1).
X=1, Y=0, Z=0 ; …
;
…
Página 7 de 10
3 f)
num(+Bin, -Num, -Uns), que dada uma string Bin, reconhece que corresponde a um número
binário, e devolve o respetivo valor Num em decimal, bem como o total de 1s (Uns).
Utilize DCGs (Gramáticas).
E.g. ?- num(“1101”, N, Uns).
N = 13, Uns = 3 ; no
?- num(“011”, N, Uns).
N = 3, Uns = 2 ; no
Página 8 de 10
Programação em Lógica com Restrições, 2011/12
Exame de Época Normal
Nº:
Grupo 4 (3 valores)
O problema das n rainhas pode ser modelado com n variáveis de domínio finito, da seguinte forma:
Variáveis:
Ri :: 1..n (i  1..n)
Restrições:
i,j: ij (Ri  Rj  Ri  Rj+i-j  Ri  Rj+j-i)
(Ri indica a coluna da rainha que está na linha i)
Nota: a simetria referente ao eixo vertical podia ser removida simplesmente com R1  (n+1)/2
Considere agora o problema dos triplos de Steiner de ordem n, que consiste em encontrar n.(n-1)/6
triplos de elementos diferentes (inteiros de 1 a n), tais que cada 2 triplos tenham no máximo um
elemento em comum. E.g. {{1, 2, 3}, {1, 4, 5}, {1, 6, 7}, {2, 4, 6}, {2, 5, 7}, {3, 4, 7}, {3, 5, 6}} é
solução para n=7 (tem 7*(7-1)/6 = 7 triplos. Para n=9 há 12 triplos.)
Pretende-se modelar e resolver este problema em domínios finitos.
4 a) Indique as variáveis (e seu significado), e seu domínio, a usar nesta modelação do problema de
Steiner(n) (lógica e matemática; não é programação).
4 b) Indique agora as restrições a que essas variáveis estão sujeitas (modelação; pode usar álgebra de
conjuntos, se conveniente).
4 c) Neste modelo, remova pelo menos uma simetria, com a adição de restrições (ainda sem código).
4 d) Que restrição global do SICStus poderia usar para ajudar a resolver o problema original (mesmo
com simetrias), e aplicada a que variáveis?
Página 9 de 10
4 e) Mostre a parte do código que usaria para enumeração eficiente em SICStus, considerando que
queria maximizar a diferença entre os 3os elementos do 2º e 3º triplo (pode assumir que as variáveis já
estão na lista Vars):
Página 10 de 10