Introdução à Programação em Lógica
MAC (3^o ano)

Exame de 2^aÉpoca

Data: 14 de Setembro de 1998
Hora: 10:00

Questão 1: O Homem e os seus fantasmas (ou os fantasmas da recursividade)

Em resposta ao conhecimento expresso nas frases

• Se um homem é incompetente, não é prudente;
• Se um homem é ignorante, não tem esperança;
• Se um homem é violento, é incompetente;
• Se um homem não é prudente, é ignorante:

resolveu-se considerar a seguinte BC:

         homem(incompetente,nao_prudente).
         homem(ignorante,sem_esperanca).
         homem(violento,incompetente).
         homem(nao_prudente,ignorante).

         homem(X,Y) :- homem(X,Z),
                       homem(Z,Y).

Supondo que forçamos sempre o backtracking (digitando ;), cada vez que obtemos uma resposta do interpretador de Prolog, descreva, justificando por meio da árvore de procura, o que se obteria colocando a seguinte questão:

         ?- homem(nao_prudente,X).

Questão 2: Manuseamento de Listas

Implemente em Prolog o predicado separa/4, que recebe no primeiro argumento um objecto, no segundo uma lista, e nos devolve no terceiro argumento todos os elementos da lista antes da primeira ocorrência do objecto e no último parâmetro os elementos que sucedem na lista ao objecto em questão.
Exemplo:

         ?- separa(*,[1,2,3,4,*,a,b,c,d],A,D).
            A = [1,2,3,4]
            D = [a,b,c,d]

Questão 3: Árvores Binárias

Recordando o que sabe sobre árvores binárias e seu manuseamento, responda às alineas seguintes.

a)

Defina o predicado altura/2 que devolva no segundo argumento a altura da árvore binária, representada da forma dada nas aulas, passada no primeiro parâmetro do predicado. Assuma que a altura da árvore vazia é 0 e que a altura de uma árvore com apenas um vértice é 1.
Exemplos:

         ?- altura(arv(1,arv(2,v,v),v),N).
            N = 2
         ?- altura(arv(1,arv(2,v,v),arv(1,v,arv(8,v,arv(8,v,v)))),N).
            N = 4

b)

Atente agora à seguinte definição:

A árvore vazia é balanceada. Se não for vazia, uma árvore diz-se balanceada quando a altura da sua árvore esquerda não diferir da altura da sua árvore direita por mais de 1 unidade e as suas árvores esquerda e direita forem também balanceadas.

Implemente em Prolog o predicado balanceada/1 que receba uma árvore binária e retorne yes caso a árvore binária seja balanceada e no na situação contrária.
Exemplos:

         ?- balanceada(arv(1,v,arv(2,arv(2,v,v),v))).
            no
         ?- balanceada(arv(1,v,arv(2,v,v))).
            yes

Questão 4: Demografia ...

Para estudos na área da demografia das populações, construiu-se uma base de conhecimento (BC) com os dados que se poderam recolher sobre cada individuo, sobre os casais e sobre os descendentes (note-se que tanto os membros dos casais, como os filhos, têm de ser individuos). Para manipular essa BC foram, também, desenvolvidos alguns predicados operacionais, tais como validaFam/1 e filho/2.
O extracto de Prolog seguinte mostra essa BC.

       %indiv( C,N,LNasc,DNasc ) :- C 'e o codigo do individuo de nome N,
       %                            nascido no local LNasc na data DNasc.
       indiv( p001,joao,porto,1983 ).
       indiv( p002,nuno,lisboa,1955 ).
       indiv( p003,maria,braga,1956 ).
       indiv( p004,joana,aveiro,1986 ).

       %casal( C,CMu,CMa,D ) :- C 'e o codigo que identifica o casal cuja mulher
       %                        'e o individuo de codigo CMu, o marido 'e o individuo
       %                        de codigo CMa, casados na data D
       casal( cp001,p003,p002,1980 ).

       %descendente( CC,CI)  :- CI 'e o codigo de um individuo que 'e filho do casal CC
       descendente( cp001,p001 ).
       descendente( cp001,p004 ).

       validaFam(Cod) :- casal(Cod, Mu, Ma, DC),
                         indiv(Mu, _, DNMu, _),
                         TolMu is DNMu+15, DC >= TolMu,
                         indiv(Ma, _, DNMa, _),
                         TolMa is DNMa+15, DC >= TolMa.

       filho(F,Prog)  :- indiv(CodF, F, _, _), indiv(CodP, Prog, _, _),
                         descendente(CodFam, CodF),
                         ( casal(CodFam, CodP, _, _); casal(CodFam, _, CodP, _)).

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

a)

Defina o predicado descendeDe/1, que recebe como argumento o nome de um individuo e escreve os dados conhecidos sobre o casal de quem ele é filho(a).

b)

Defina o predicado numeroFilhos/2, que dá no segundo argumento o número total de filhos do casal cujo código é passado no primeiro argumento.

c)

Defina o predicado nascidosEmEntre/4, que recebe o nome de um local e duas datas (nos 3 primeiros argumentos) e dá no quarto argumento a lista de todos os individuos nascidos nesse local, no periodo compreendido entre as duas datas especificadas.

d)

Interprete o predicado validaFam/1, dizendo que lógica é que ele exprime e indicando para que serve e como se utiliza.

e)

Extenda o predicado anterior, validaFam/1, para um novo predicado validaFams/0, que aplica o primeiro a todas as famílias.

f)

Usando a árvore de procura, mostre a diferença entre a prova dos objectivos validaFam(cp001) e validaFam(X).

g)

Recorrendo à árvore de prova, mostre que filho(joao,maria) é verdadeiro.

h)

Crie uma DCG para definir uma linguagem que sirva para descrever famílias de modo a carregar automaticamente a BC a partir das frases dessa linguagem, que deverão ser do género:

         CASAL <cod> (Codmul,Codmar,data)
         FILHOS <(CodF1,Data1),...>

i)

Acrescente à DCG da alínea os atributos e as acções semanticas necessários para verifcar que os códigos, tanto da mulher como do marido, existam na BC como individuos.

j)

Com a linguagem que se lhe pediu atás só é possível extrair informação para juntar à BC factos casal e descendente, mas não pode retirar dados para juntar factos indiv.
Estenda, então, a gramática para que junto com a descrição dos filhos se incluam dados suficientes para acrescentar os ditos factos indiv à BC. Acrescente acções semanticas a essa extensão de modo a produzir mesmo esse resultado, durante o reconhecimento das novas frases.

Questão 5: Autómato para Sinónimos

Pretende-se construir um programa que seja capaz de ler palavras (sequências de letras separadas por 1 ou mais espaços, ou new-line (NL)) e reconhecer conceitos, que podem ser expressos por palavras diferentes.
Considere-se por exemplo a seguinte lista (reduzida):

        giro = lindo = belo --> conceito(bonito)
        bera = fraco        --> conceito(mau)
        ricaco = riquinho   --> conceito(rico)

Uma forma fácil e eficiente de implementar tal programa é concebê-lo como um ciclo standard guiado por um autómato determinista, que vá lendo caracteres e transitando de estado por cada caracter lido, até chegar ao fim duma palavra (nessa altu Assim sendo, pede-se-lhe que desenhe o referido autómato determinista para reconhecer os conceitos e as palavras indicadas acima (todas as outras palavras devem ser rejeitadas, como erro).
Represente o autómato em causa numa BC em Prolog.