Introdução à Programação em Lógica
MAC, Mat, EM (3^\bo ano)

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

Data: 12 de Junho de 1998
Hora: 10:00

Questão 1: Macaco e Bananas

Nas aulas teórico-práticas foi sugerida a seguinte solução para o problema do macaco e das bananas:

        accao(situacao(centro,cima_caixa,centro,nao_tem),
              apanhar,
              situacao(centro,cima_caixa,centro,tem)).
        accao(situacao(P,chao,P,TN),
              subir,
              situacao(P,cima_caixa,P,TN)).
        accao(situacao(P1,chao,P1,TN),
              empurrar(P1,P2),
              situacao(P2,chao,P2,TN)).
        accao(situacao(P1,chao,C,TN),
              andar(P1,P2),
              situacao(P2,chao,C,TN)).

        % cumpre_obj(S) <=> macaco pode obter banana partindo de S

        cumpre_obj(situacao(_,_,_,tem)).
        cumpre_obj(E) :-
              accao(E,A,S),
              cumpre_obj(S).

Depois de fazer o 'consult' do ficheiro, bastava perguntar ao interpretador:

        ?- cumpre_obj(situacao(porta,chao,janela,nao_tem)).
        yes

Com este exercício pretende-se que alterem o programa acima, de modo a sabermos qual a solução ``que o macaco encontra'' para apanhar a banana.

Questão 2: Jogo da Vida unidimensional

Com este exercício pretende-se que implementem um jogo da vida unidimensional com regras de evolução fixas, codificadas da seguinte maneira:

        regra(0,0,0).
        regra(0,1,1).
        regra(1,0,1).
        regra(1,1,0).

Passamos a explicar. Convencionamos que 0 representa uma célula morta enquanto 1 representa uma célula viva. Uma colónia de seres unicelulares será então representada por uma lista de zeros e uns. Por exemplo,

        [0,1,0,1,1,0,1,0,1,0,0,1,1,0]

Com as regras de evolução, vamos poder obter as gerações que se seguem à colónia inicial. As regras apresentadas acima, significam que:

• se houver um 0 (na lista) com um 0 à sua direita, não se altera o 0 (a célula continua morta na próxima geração);
• se houver um 0 com um 1 à sua direita, então o 0 passa a 1;
• se houver um 1 com um 0 à sua direita, não se altera o 1;
• se houver um 1 com um 1 à sua direita, então o 1 passa a zero.

Pretendemos:

a)

Que implementem um predicado proxima_geracao/2 que recebe no primeiro argumento uma lista de 0's e 1's e retorne no segundo argumento, de acordo com as regras descritas, a colónia de células que a sucede.
Exemplos:

         ?- proxima_geracao([1,0,0,0,1,1],L).
            L = [1,0,0,1,0,1]

         ?- proxima_geracao([1,1,1,1,0],L).
            L = [0,0,0,1,0]

b)

Que implementem um predicado jogo_vida/3 que recebe no primeiro argumento o número N de gerações seguintes que pretendemos conhecer; no segundo argumento a colónia de células ``actual''; e que retorna no último argumento a lista com as próximas N gerações (cada geração de células é uma lista de 0's e 1's). Exemplo:

         ?- jogo_vida(2,[1,0,1],L).
            L = [[1,1,1],[0,0,1]]

Questão 3: Árvores Binárias

Para árvores binárias cujos vértices contêm números, considere-se a seguinte definição:

Uma árvore diz-se boa se para qualquer vértice, excepto as folhas, o número do vértice é igual à soma dos números nos dois vértices descendentes.

Usando esta definição, e a representação de árvores binárias que foi usada nas aulas teóricas e teórico-práticas, escreva um predicado boa/1 que recebe como parâmetro uma árvore binária, e que toma o valor verdadeiro sse a árvore é boa. Exemplos:

         ?- boa(arv(7,vazio,vazio)).
            yes

         ?- boa(arv(5,arv(2,vazio,vazio),arv(2,vazio,vazio))).
            no

         ?-boa(arv(5,vazio,arv(5,arv(3,vazio,vazio),arv(2,vazio,vazio)))).
           yes

Questão 4: Arqueologia (bc+ap)

Para construir um Sistema de Informação para uma Unidade de Arqueologia, foi criada uma Base de Conhecimento (BC) com os predicados

       arqueologo/3 :- identifica cada arqueologo
       escavacao/3 :- identifica cada zona territorial onde se esta a
                      fazer uma exploracao arqueologica
       achado/4    :- identifica cada objecto encontrado
       encontrou/3 :- relaciona um arqueologo com um achado descoberto
                      numa escavacao

que descrevem as Entidades e Relações entre elas, identificados durante a fase de análise.
De momento a Base contém os seguintes factos:

       arqueologo( cod(1), nome(nuno), institut(um) ).
       arqueologo( cod(2), nome(ana), institut(um) ).
       arqueologo( cod(3), nome(luis), institut(ua) ).
       arqueologo( cod(4), nome(olga), institut(uc) ).
       arqueologo( cod(5), nome(rui), institut(uc) ).

       escavacao( nome(carvalheiras), loc(braga), sector(A13) ).
       escavacao( nome(conimbriga), loc(condeixa), sector(B44) ).
       escavacao( nome(citaniabriteiros), loc(braga), sector(H54) ).
                     
       achado( ident(o1), classe(prato), mat(barro), estado(partido) ).
       achado( ident(o2), classe(prato), mat(metal), estado(intacto) ).
       achado( ident(o3), classe(prato), mat(barro), estado(fragmento) ).
       achado( ident(o4), classe(moeda), mat(ouro),  estado(intacto) ).
       achado( ident(o5), classe(moeda), mat(bronze), estado(razoavel) ).
       achado( ident(o6), classe(anel),  mat(ouro),  estado(razoavel) ).
       achado( ident(o7), classe(anel),  mat(prata),  estado(torcido) ).

       encontrou( arq(1), obj(o1), escav(carvalheiras) ).
       encontrou( arq(1), obj(o2), escav(carvalheiras) ).
       encontrou( arq(4), obj(o6), escav(conimbriga) ).
       encontrou( arq(3), obj(o5), escav(conimbriga) ).
       encontrou( arq(4), obj(o4), escav(citaniabriteiros) ).
       encontrou( arq(1), obj(o3), escav(citaniabriteiros) ).

Suponha ainda que se definiram algumas regras de inferência, tais como:

       encObj( Pessoa, Objecto ) :- arqueologo( cod(C), nome(Pessoa), _),
                                    encontrou( arq(C), obj(CObj), _),
                                    achado(ident(CObj),classe(Objecto),_,_).

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

a)

escreva um predicado que lhe permita contar quantos arqueólogos existem de uma dada instituição.

b)

escreva um predicado que lhe permita determinar o nome de todos os achados encontrados em qualquer escavação de uma determinada localidade e mostre como o usava para os Achados de Braga.

c)

escreva um predicado que lhe permita construir uma lista com o nome de todas as escavações exploradas pelos arqueólogos pertencentes a uma determinada instituição.

d)

usando o conceito de Árvore de Prova, mostre que o interpretador de Prolog responde afirmativamente à questão:

       encObj( olga, moeda ).

e)

recorrendo ao conceito de Árvore de Procura, indique todas as respostas que o interpretador de Prolog encontraria para a questão:

       encObj( nuno, OQue ).

indicando qual seria a primeira resposta automática e quais seriam obtidas após pedido explícito do utilizador.

f)

mostre que o processo de prova usado pelo interpretador de Prolog para provar a veracidade de

       encObj( Quem, anel ).

se altera se o predicado encObj/2 for reescrito trocando a última linha com a penúltima.

g)

diga que informação (novos predicados) tinha que acrescentar à BC se quizesse validar o predicado arqueologo, garantindo que o nome é um nome de pessoa e a instituição faz parte das instituições de ensino reconhecidas como tal.
Assumindo que a BC continha esses factos extra, escreva o predicado valida que iria percorrer a BC e identificar todos os arqueólogos inválidos.

Questão 5: Arqueologia (linguagem)

Ainda no contexto do problema anterior, pretende-se criar uma linguagem que permita identificar um Arqueólogo (indicando o código, nome e instituição e indicar todos os Objectos (referidos pelo respectivo identificador) por ele encontrados numa determinada escavação (que também terá de ser identificada).
O que se lhe pede é que escreva uma DCG para definir a dita linguagem, começando por dar exemplos de frases válidas da linguagem que vai desenvolver.
Enriqueça posteriormente a sua DCG com atributos (argumentos dos símbolos gramaticais) para retirar de cada frase, reconhecida pelo programa derivado da DCG, os dados relativos ao arqueólogo descrito.

Questão 6: Autómato Telefónico

Os modernos telefones prestam já serviços diversos, para além da simples ligação a outro telefone. Esses serviços atingem-se começando por digitar o símbolo "*", ou "#", seguido do código do serviço.
Supondo que de momento o Operador telefónico nacional disponibiliza:

• a ligação a outro posto, quando for escrito um número telefónico (começa e só contém digitos);
• informações referentes aos resultados do totoloto, através do código "*10";
• informações referentes ao gravador de chamadas, usando o código "*20" seguido de 3 dígitos que correspondem à senha;
• teste do sinal de toque, usando o símbolo ``#''

pretende-se que modele o funcionamento do telefone usando um Autómato Determinista Reactivo.
Represente o autómato em causa numa BC em Prolog.