Intodução à Programação Lógica
MAC, Mat, EM (3^o ano)

Exame de 1^a Época - 2^a Chamada

Data: 10 de Julho de 1997
Hora: 10:00

Questão 1

Para construir um Sistema de Informação para uma Biblioteca, foram identificados as seguintes Entidades e Relações:
o Livro (descrito pelo ISBN, titulo, assunto e editora) que é escrito por um Autor (caracterizado por um nome, o país de onde é natural, e o estilo principal) e o Utente (descrito por um código, o nome, a classe (docente, aluno, externo), e o telefone) que requisita um livro numa data para leitura interna, ou domiciliária.

Antes de se criar a Base de Dados Relacional, que servirá de suporte ao sistema informático final, está-se a pensar fazer um protótipo do sistema num ambiente de programação declarativo, lógico.

Responda, então, às alíneas seguintes:

a)

Escolha os predicados (indique o seu nome e todos os seus argumentos) que deve usar em Prolog para modelar as entidades e as relações entre elas (para concretizar a sua resposta, mostre como exemplo 1, ou 2, factos concretos para cada um desses predicados).

b)

De acordo com o modelo que escolheu acima, mostre como é que se podia:

b1)

escrever (imprimir no ecran) o título de todos os livros escritos por um autor;

b2)

construir uma lista com o ISBN de todos os livros requisitados para o domicílio por um utente;

b3)

escrever o título e o autor (nome) do livro mais requisitado até ao momento.

%-------------------------

Questão 2

Pretende-se a implementação em Prolog de um codificador de mensagens (e de um descodificador de mensagens encriptadas), pela substituição simples de uma letra (ou dígito), de a-z (ou 0-9), por outra, também de a-z (ou 0-9). Uma das formas mais simples de substituição é deslocar o alfabeto de uma quantidade específica (chamemos-lhe um delta).
Por exemplo, se cada letra e cada dígito fôr deslocada de 3, então

a b c d e f g h i j k l m n o p q r s t u v w x y z 0123456789

ficaria

d e f g h i j k l m n o p q r s t u v w x y z a b c 3456789012

e a mensagem 'encontra-me ao anoitecer' ficaria 'hqfrqwud-ph dr dqrlwhfhu'.

Usando o algoritmo acima descrito e o predicado pré-definido name/2 (recorde-se que este predicado transforma uma frase (1^\bo argumento) numa lista (2^\bo argumento) com os códigos ASCII dos seus caracteres), implemente o predicado code( F,FCode,Delta ) que recebe a frase F e a devolve codificada em FCode usando um deslocamento Delta para rodar as letras e os dígitos.
Exemplo:

         ?- code('encontra-me ao anoitecer',C,3).
         C = 'hqfrqwud-ph dr dqrlwhfhu'

%-------------------------

Questão 3

Considere as frases seguintes, que são estruturalmente (isto é, sintacticamente) idênticas:

• O Delfim escreveu um programa com um computador
• O Pedro encontrou um colega com um problema
• A Joana comeu uma maçã com os dentes

e responda às questões:

a)

defina um analisador sintáctico, usando o formalismo DCG do Prolog, que reconheça essas frases e outras com a mesma estrutura.

b)

Modifique a sua gramática (DCG) de modo a aceitar também frases do tipo

• um homem disse um poema

c)

Acrescente à sua gramática (DCG) os argumentos e acções necessários de modo a validar a concordância, em género e em número, entre os determinantes e os nomes.

d)

Diga que questão (átomo lógico) deve colocar ao Interpretador de Prolog para fazer o reconhecimento da 1^\ba frase acima com a DCG que desenvolveu (suponha que a DCG já foi consultada (carregada para a memória do Interpretador)).

%-------------------------

Questão 4

Observe com cuidado a seguinte Base de Factos (BC)

         % profRisco(P)  :-  a profissao P 'e de alto-risco.
         profRisco(professor) .
         profRisco(fuzileiro) .
         profRisco(bombeiro) .
         % exerceProf(S,P)  :-  a pessoa S exerce a profissao P.
         exerceProf(ana,professor) .   exerceProf(rui,professor) .
         exerceProf(to,metalurgico) .  exerceProf(xico,bombeiro) .
         exerceProf(marta,bombeiro) .  exerceProf(hugo,fuzileiro) .
         % dorme(S,H)  :- a pessoa S dorme em media H horas por noite.
         dorme(tita,7) .                    dorme(pedro,5) .
         dorme(joao,4) .                    dorme(ze,5) .
         dorme(sofia,6) .                   dorme(mariana,8) .

Responda, então, às alíneas seguintes:

a)

Defina o predicado exerceProfRisco(P) que é verdadeiro sempre que a pessoa P praticar uma actividade profissional considerada de alto-risco.

b)

Escreva as cláusulas que deveriam ser acrescentadas à BC para se poder validar que todos os factos exerceProf/2 (acima exemplificados) estavam aplicados consistentemente, isto é relacionavam uma pessoa (1^\bo argumento) com uma profissão (2^\bo argumento).

c)

Defina o predicado novaProfRisco(P,Pos) que acrescenta à BC uma nova profissão de alto-risco se e só se esse facto ainda não existir na base; o predicado a definir deve juntar o novo facto no início, ou no fim, conforme o 2^\bo argumento (Pos) tenha o valor 'p' ou 'u', respectivamente.

d)

Usando a Árvore de Procura, indique qual seria a 1^\ba e quais seriam as restantes respostas calculadas por um Interpretador de Prolog (IP) face à questão: razões diferentes

         exerceProf( QUEM,professor ) .

e)

Usando a Árvore de Procura, mostre que um IP responderia negativamente, "no", às questões abaixo, mas por razões diferentes

         dormeDemais(tita) .
         dormeDemais(joana) .

admitindo que existia na BC um predicado dormeDemais/1 assim definido

         dormeDemais(P) :-  dorme(P,H),  H > 9.

%-------------------------

Questão 5

No livro 100 Jogos Lógicos da colecção O Prazer da Matemática da Gradiva, pode ser encontrado o jogo que se segue.

Um motorista exprime as suas impressões sobre automóveis da seguinte forma:

• Uma tracção à frente dá boa estabilidade;
• Uma viatura pesada deve ter bons travões;
• Todas as viaturas de motor muito potente são caras;
• As viaturas ligeiras não têm boa estabilidade;
• Uma viatura de motor pouco potente não pode ter bons travões.

Admitirá ele a existência de uma viatura de tracção à frente que seja cara?

Responda, então, às alíneas seguintes:

a)

Escreva cláusulas em Prolog que lhe permitam classificar viaturas de acordo com os seguintes parâmetros: tracção (à frente, ou a trás); potência (muita, média, pouca); classe (`ligeiro, ou pesado, ...).

b)

Recorrendo aos predicados que criou na alínea anterior, acrescente à BC mais cláusulas Prolog para traduzir as afirmações do motorista acima apresentadas, de tal modo que seja possível, posteriormente, fazer inferências sobre a estabilidade, preço, ou travões de uma viatura.

c)

Tomando em consideração a Base de Conhecimento criada nas alíneas anteriores, diga, justificando, se seria possível responder à questão formulada no jogo acima.

%-------------------------

Questão 6

Escreva em Prolog cláusulas adequadas (podendo recorrer, se necessário a predicados pré-definidos) para definir:

a)

O predicado profundidade( E,L,N ) que, dado um elemento E e uma lista L que pode conter elementos que são novamente listas, determina a profundidade N da primeira ocorrência desse elemento na lista (supõe-se que o nível da lista mais externa é 1). Exemplo:

         ? profundidade(7,[3,[5,7],[4,[7,0]]],N).
         N = 2

b)

O predicado dobra( L,LL ), sendo L e LL listas, em que LL contém todos os elementos de L duplicados. Por exemplo:

         ?- dobra([1,2,3],[1,1,2,2,3,3])
         yes

c)

O predicado separa( L1,(Ln,Ll) ) que recebe como entrada uma lista L1 formada por números e letras, contendo eventualmente repetições, e devolve como saída um par em que o primeiro elemento Ln é a lista apenas dos números e o segundo elemento Ll é a lista apenas das letras. No resultado não podem aparecer repetições, podendo recorrer a predicados de Prolog pré-definidos. Exemplo:

         ?- separa([b,d,2,a,5,b],R).
         R = ([2,5],[d,a,b])
         ?- separa([4,d,5,4,q],R).
         R = ([5,4],[d,q])

%-------------------------