Programação em Lógica, 2004/05
2º Teste
DI-FCT/UNL
9 de Junho de 2005
Programação em Lógica
2º Teste
Sem consulta - Duração: 2 horas
Grupo 1
1 a)
Suponha que as notas de alunos em Programação em Lógica estão guardadas através de
factos Prolog com a forma nota(Nome,Teste,Nota), onde Nome tem o nome do
aluno em causa, Teste é igual a t1 ou t2, e onde Nota é um número entre 0 e 20.
Usando o setof/3, implemente um predicado melhorAluno(-Nome) que devolve o
Nome do aluno com melhor média final na disciplina. Havendo vários, basta que o seu
predicado devolva um qualquer.
1 b)
Sem usar o predicado de sistema name/2 e usando DCGs, implemente um predicado
inteiro(+S,-N) que dada uma string S sucede se e só se esta corresponder a um
número inteiro (positivo ou negativo), devolvendo em N esse numero. Por exemplo:
?- inteiro(“124”,N). ?- inteiro(“a1”,N).
N = 124;
no
no
?- inteiro([45,54,55],N).
N = -67;
no
Grupo 2 (Trabalho)
Considere uma versão simplificada da construção de horários, na qual não se tem em conta a
sobreposição de aulas para docentes e alunos. Dito de outra forma, nesta versão a única coisa que é
necessário ter em conta é que não pode haver duas aulas sobrepostas numa mesma sala. Para esta
versão, implemente os seguintes predicados:
2 a)
fazHorario(+ListaTurnos,+HorAnt,-Horario) que, dada uma lista de turnos
ListaTurnos sem sala, dia e hora atribuída e uma lista de turnos HorAnt já com sala,
dia e hora atribuída, devolve em Horario uma lista com todos os turnos com sala, dia e
hora atribuídas e em que não haja nenhum conflito de aulas sobrepostas numa mesma sala.
Todas essas listas são listas de termos da forma:
turno(Cadeira,Turno,Tipo,Dia,Hora,Sala)
sendo que na primeira lista os 3 últimos argumentos destes termos estão por instanciar.
Para fazer este predicado assuma que dispõe já dos predicados:
• geraDiaHora(-Dia,-Hora) que devolve um Dia e Hora em que pode
haver aulas (e em backtracking devolve todas as hipóteses);
• sala(-Sala) que devolve uma Sala onde pode haver aulas (e em backtracking
devolve todas as hipóteses);
• sobrepostos(T1,T2) se os turnos T1 e T2 decorrem na mesma sala, no
mesmo dia e em horas sobrepostas.
2 b)
Usando listas de diferença, implemente o predicado:
separa(+TurnosMisturados,-TurnosSeparados)
que separa os turnos TurnosMisturados de maneira a que, em TurnosSeparados,
primeiro apareçam os turnos teóricos, depois os teórico-práticos, e por fim os práticos.
Isto poderá ser útil num caso em que, usando o predicado da alínea anterior, se pretenda
começar por atribuir horário (sala, dia e hora) a todos os turnos teóricos, depois aos teóricopráticos, e só depois aos práticos.
Página 1 de 2
Programação em Lógica, 2004/05
2º Teste
Grupo 3
Tenho que fazer as tarefas A, B, C, D e E. Mas cuidado! Quer a tarefa C quer a D têm que ser feitas
antes da E, a tarefa B tem que ser antes da D, e a tarefa A tem que ser feita antes quer da B quer da C.
Por que ordem devo fazer as tarefas? Neste caso é fácil: posso começar por fazer a A, depois a B,
depois a C, depois a D e por fim a E; ou começar pela A, depois a C, depois a B, depois D e depois a
E; ou etc.
O que se pretende neste grupo é que faça um predicado em Prolog que dada uma lista de tarefas, e
tendo a descrição de uma série de restrições da forma Tarefa1 antes_de Tarefa2, sob a forma
de um conjunto de factos, devolva uma a uma todas as ordens possíveis para as tarefas.
Para o exemplo acima, os factos deveriam ser:
c antes_de e.
a antes_de b.
d antes_de e.
a antes_de c.
b antes_de d.
Mas vamos fazer isso aos poucos…
3 a)
Comece por definir o operador “antes_de” que lhe permite escrever os factos como
acima exemplificado.
3 b)
Implemente o predicado antes(T1,T2) que sucede se T1 tiver que ser feita antes de T2.
Note que T1 pode ter que ser feito antes de T2, sem que haja directamente um facto
afirmando-o. Por exemplo, com os factos acima a A tem que ser antes da E.
3 c)
Implemente um predicado pode_inicio(+Tarefa,+ListaTar) que verifica se a
tarefa Tarefa pode ser executada antes de todas as tarefas em ListaTar. Dito de outra
forma, que sucede se não existir nenhuma tarefa em ListaTar que tenha que ser
executada antes de Tarefa. Por exemplo, com os factos acima:
?- pode_inicio(b,[c,d,e]).
Yes
?- pode_inicio(e,[a,b]).
No
No caso da direita falha porque a tarefa a tem que ser executada antes de e.
3 d)
Implemente agora o predicado ordemTarefas(+Tarefas,-Ordem), que devolve uma
Ordem possível para as Tarefas. Por exemplo, considerando os factos acima:
?- ordemTarefas([a,b,c,d,e],L)
L = [a, b, d, c, e] ;
L = [a, c, b, d, e] ;
L = [a, b, c, d, e] ;
L = [a, b, d, c, e] ;
L = [a, c, b, d, e] ;
L = [a, b, c, d, e] ;
No
Página 2 de 2