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

Exame de 1a Época - 2a Chamada

Data: 10 de Julho de 1998
Hora: 10:00

 
 
Dispõe de 3:00 horas para realizar este exame
 
Leia as questões com toda a atenção
e responda com calma e clareza em folha convencional

Questão 1: Alice e o País das Maravilhas

Considere o seguinte enunciado:

Quando a Alice entrou na floresta do esquecimento, ela não se esqueceu de tudo, apenas de certos factos. Frequentemente, ela esquecia-se do seu nome, mas o que ela se esquecia com mais regularidade era do dia da semana. O leão e o unicórnio são visitantes frequentes da floresta. Estes dois, são criaturas muito estranhas. O leão mente às Segundas, Terças e Quartas e diz a verdade nos restantes dias da semana. O unicórnio, por seu lado, mente às Quintas, Sextas e Sábados, mas diz a verdade nos outros dias da semana.

Um dia a Alice encontrou o leão e o unicórnio debaixo de uma árvore. Eles fizeram as seguintes declarações:

Leão:
ontem foi um dos dias em que eu menti.
Unicórnio
ontem foi um dos dias em que eu menti.

Destas afirmações, Alice, que era uma rapariga inteligente, foi capaz de deduzir o dia da semana. Qual era ele?

Pretende-se que:

a)
implemente um programa em Prolog que seja capaz de responder à pergunta acima formulada.
b)
indique o modo como se colocaria a questão ao interpretador para obter a solução por este produzida.
c)
justifique, por meio de uma Árvore de Procura, como é que o Prolog chegaria à solução.

Questão 2: Manuseamento de Listas

Sobre operações com Listas em Prolog, responda às alíneas seguintes:

a)
Nas aulas teórico-práticas, a quando da implementação do ficheiro math.pl, implementou-se o predicado inverte/2 da maneira que se segue: 
         concatena([],L,L).
         concatena([X|R],L,[X|C]) :-
           concatena(R,L,C).

         inverte([],[]).
         inverte([X|L],I) :-
           inverte(L,LI),
           concatena(LI,[X],I).

O predicado inverte devolve-nos, no segundo argumento, a lista invertida que é fornecida como primeiro parâmetro. Assim, por exemplo, 

         ?- inverte([1,2,3],L).
            L = [3,2,1]

         ?- inverte([1,[2,3],4],L).
            L = [4,[2,3],1]

Pretende-se que implemente agora um predicado inverte_tudo que faz a inversão a todos os níveis (caso a lista contenha listas de entre os seus elementos, essas listas também são invertidas). Assim, para os exemplos atrás considerados, teríamos: 

         ?- inverte_tudo([1,2,3],L).
            L = [3,2,1]

         ?- inverte_tudo([1,[2,3],4],L).
            L = [4,[3,2],1]
b)
Ainda em relação ao predicado concatena/3 da alínea anterior, mostre, usando a Árvore de Prova que o átomo 
         concatena([a,b], [c], [a,b,c]).

é verdadeiro.

c)
Ainda em relação ao predicado inverte/2 da alínea anterior, mostre, usando a Árvore de Procura que a resposta do interpretador de Prolog à questão 
         inverte([a,b,c], [c,a,b]).

é ``no''.

d)
Pretende-se que implemente agora um predicado denominado merge, que serve para fundir duas listas ordenadas produzindo uma terceira lista, também ela ordenada.
Exemplo: 
         ?- merge([2,5,6,6,8],[1,3,5,9],L).
            L = [1,2,3,5,5,6,6,8,9]

Pressuponha a existência de um predicado antes(X,Y) que resulta verdadeiro quando X vem antes de Y. Para o exemplo apresentado, pode pensar nos termos da seguinte definição: 

         antes(X,Y) :- X =< Y.

Questão 3: Árvores Binárias

Escreva um predicado equivalente(A1,A2) que permita relacionar duas representações de uma mesma árvore binária. A primeira representação é a dada nas aulas; a segunda representação é baseada em listas: uma árvore ou é vazia (símbolo v) ou é uma lista com 3 elementos -o conteúdo do vértice, a árvore esquerda e a árvore direita.
Exemplo: 

     ?- equivalente(arv(2,arv(3,arv(4,v,v),v),arv(5,arv(6,v,v),arv(7,v,v))),L).
        L = [2,[3,[4,v,v],v],[5,[6,v,v],[7,v,v]]]

Questão 4: Linguagem de Comandos

Analise atentamente a seguinte gramática escrita na notação lógica DCG 

         comando   -->  operSimp, args, [';'].
         comando   -->  operComp, [de], arg, [para], arg, [';'].
         args      -->  arg, resto.
         resto     -->  [].
         resto     -->  arg, resto.
         arg       -->  [NomeFich].
         operSimp  -->  [lista].
         operSimp  -->  [tamanho].
         operSimp  -->  [apaga].
         operSimp  -->  [renomeia].
         operComp  -->  [copia].
         operComp  -->  [move].

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

a)
Dê exemplos de 2 frases válidas da linguagem definida pela DCG acima e de 2 frases incorrectas.
b)
Modifique a gramática supra de modo a permitir que cada frase da linguagem em causa possa ter mais do que um comando.
c)
Acrescente atributos aos símbolos não-terminais (i. é, argumentos aos predicados) da gramática de modo a que a DCG force que o comando tamanho e o comando apaga tenham precisamente 1 argumento e o comando renomeia tenha sempre 2 argumentos.
d)
Junte acções semânticas à DCG (e associe atributos aos símbolos, quando achar necessário) para que o programa gerado a partir da DCG acrescente à Base de Conhecimento (BC) o predicado comando/2 que tenha como argumentos o nome e a aridade do comando reconhecido.

Questão 5: Adesão ao EURO

Analise atentamente a seguinte Base de Conhecimento que o Gabinete de Assuntos Económicos da CE criou para determinar automaticamente se um País está apto a aderir ao projecto de introdução do EURO 

       %percentagem da Divida Publica em relacao ao PIB
       percDivPub(belgica,135.0).
       percDivPub(portugal,69.6).
       ............
       
       %taxa de Inflaccao
       taxaInfl(belgica,1.4).
       taxaInfl(portugal,3.8).
       ............
       
       menorTaxaInfl(finlandia,1.0).
       
       %percentagem do Deficite Orcamental em relacao ao PIB
       percDefOrc(belgica,5.1).
       percDefOrc(portugal,2.8).
       ............


       %criterios de aptidao
       criterio1(P) :- percDivPub(P, D), D=< 75, !, 
                       write(P), write('Passou criterio1'),nl.
       criterio1(P) :- write(P), write('NAO Passou criterio1'),nl.
       criterio2(P) :- taxaInfl(P, T), menorTaxaInfl(_,M), T=< 2.5 * M.
       criterio3(P) :- percDefOrc(P, D), D=< 3.

       %verificacao da aptidao
       apto(Pais) :- criterio1(Pais), criterio2(Pais), criterio3(Pais).

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

a)
Diga por palavras suas e com base na BC acima, quais são as condições em que um País pode aderir ao projecto.
b)
Diga que alterações deveria fazer às condições que indicou na alínea anterior, se o predicado apto fosse definido da seguinte maneira: 
       %verificacao da aptidao
       apto(Pais) :- verificaDivida(Pais), verificaInflaccao(Pais).
       verificaDivida(Pais) :- criterio1(Pais), criterio3(Pais).
       verificaInflaccao(Pais) :- criterio2(Pais).
c)
Essa BC permite-lhe calcular automaticamente todos os Países aptos a aderirem, ou só serve para saber se um País está apto? Em caso afirmativo, diga como interrogava a BC para obter essa resposta.
d)
Para que será que criterio1 está definido de uma forma diferente de criterio2 e criterio3? Era mesmo necessário, ou é um complemento?
e)
Explique as razões lógicas e operacionais para se usar o predicado cut, '!' na primeira cláusula relativa a criterio1.
Que aconteceria se se retirasse o cut e o segundo critério falhasse (obviamente, depois do primeiro ter sido testado com sucesso)?

Questão 6: Autómato Comparador de Palavras

Nas aulas teóricas foi sugerido o uso de um autómato determinista para verificar se duas palavras do mesmo comprimento eram adjacentes, tendo-se definido o critério de adjacência como tendo todos os caracteres iguais à excepção de exactamente um.
Pretende-se, agora, que redesenhe esse autómato para testar a adjacência de 2 palavras, mas considerando-as adjacentes se uma estiver totalmente contida na outra (se necessário, adapte a função compara que lhe dá o valor resultante de comparar o próximo caracter de cada palavra).
Represente o autómato em causa numa BC em Prolog.