Ficha de Exercícios de Prolog 2

Grupo 1

A linguagem Prolog não tem como tipo básico os conjuntos. É no entanto possível, usando uma representação adequada, fazer em Prolog predicados que manipulem conjuntos via essa representação. Considere então que os conjuntos são representados por listas ordenadas sem repetições.
Com base nessa representação, implemente em Prolog os seguintes predicados:

1a)    insere(Elem,Conj, Res) que dado um elemento Elem e um conjunto Conj devolve em Res o conjunto resultado da união de Conj com {Elem}.

1b)    lista2conj(Lista,Conj) que transforma a lista Lista no conjunto Conj dos seus elementos.
        Sugestão: Use o predicado definido na alínea anterior.

1c)    intersecção(C1,C2,C) que devolve em C o resultado da intersecção de C1 com C2.

1d)    subconjunto(Sub,Conj) que verifica se Sub é subconjunto de Conj. Mais, se o predicado for chamado com a variável Sub não instanciada, deverão ser devolvidos, em backtracking, todos os subconjuntos de Conj, sem repetições

 

Grupo 2

Implemente em Prolog os seguintes predicados sem recursividade terminal e com com recursividade terminal:

2a)    somaLista(+Lista,-Soma) que dada uma lista de inteiros, devolve em Soma a soma de todos os inteiros.

2b)    prodInter(+X,+Y,-PI) que calcula o produto interno dos vectores X e Y.

2c)    contaElems(+Lista,+Elem,-C) que devolve em C o nº de ocorrências do elemento Elem na lista Lista.

Grupo 3

Para cada um dos predicados abaixo apresente uma implementação em Prolog que não use cuts, uma outra que use apenas “cuts verdes”, e uma outra que use “cuts vermelhos”:

3a) uniao(+Lista1,+Lista2,-Lista) que dadas duas listas ordenadas devolve a lista ordenada com a união dos elementos das listas dadas.
3b) naoMembro(+E,+L) que sucede se E não é um elemento da lista L.
3c) semDupl(+Ldupl,-Lista) que dada uma lista possivelmente com elementos duplicados devolve a lista resultado de eliminar todos esses elementos duplicados.

Grupo 4

“À entrada da casa do Miguel há uma escada com 10 degraus. Cada vez que entra em casa, o Miguel avança pelas escadas subindo um ou dois degraus em cada passada. De quantas maneiras diferentes pode o Miguel subir as escadas?”

Faça em Prolog um predicado jogo_degraus(+Degraus,-N,-L) que dado o número de degraus Degraus da escada (que pode ser diferente de 10) devolve em N o número de maneiras diferentes de subir a escada, e em L a lista das possibilidades (cada possibilidade será também uma lista com uma sequência de 1s e 2s). Por exemplo:
    ?- jogo_degraus(3,N,L).            ?- jogo_degraus(10,N,_)
    N = 3                              N = 89;
    L = [[1,1,1],[1,2],[2,1]];         no
    no

Se o predicado que fez não tem recursividade terminal, faça uma nova versão, desta vez com recursividade terminal. Verificará que assim o predicado funciona para valores maiores de Degraus.

 

Grupo 5

Implemente em Prolog cada um dos predicados abaixo:

5a)    map(+ListaIn,+Pred,-ListaOut) que dado um nome, Pred, de um predicado de aridade 2 que represente uma função (em que, por exemplo, f(X,Y) significa que y=f(x)) devolve em ListaOut a lista resultado de aplicar a função aos elementos de ListaIn.
5b)    separa(+L,+Pred,-LV,-LF) que dada uma lista L e um nome de um predicado de aridade 1, devolve duas listas LV e LF em que na primeira aparecem todos os elementos de L que tornam verdadeiro o predicado e na segunda aparecem todos os outros.

 

Grupo 6

Usando o setof/3 implemente os predicados abaixo:

6a)     mais_curto(+A,+B,-Percurso) que dado um grafo dirigido acíclico, através de factos arco(N1,N2,Distância), e dois nós A e B, devolve um menor percurso entre esses nós.
Nota: Esta não será certamente a forma mais eficiente de implementar este predicado, servindo aqui apenas para exercitar o uso do predicado setof/3.

6b)     ondas(+Nó,+N,-Ondas) que dado um nó do grafo e um número N, devolve em Ondas uma lista com N listas, tendo a primeira todos os nós do grafo que se encontram a distância 1 de Nó, a segunda todos os que se encontram a distância 2, etc. Generalize o predicado para que passe a tratar também grafos com ciclos.

Para testar os predicados deste grupo use o grafo representado pelos seguintes factos:

     arco(oradeo,zerind,71).
     arco(oradeo,sibiu,151).
     arco(zerind,arad,75).
     arco(arad,sibiu,140).
     arco(arad,timisoara,118).
     arco(timisoara,lugoj,111).
     arco(lugoj,mehadia,70).
     arco(mehadia,dobreta,75).
     arco(dobreta,craiova,120).
     arco(craiova,vilcea,146).
     arco(craiova,pitesti,138).
     arco(sibiu,vilcea,80).
     arco(vilcea,pitesti,97).
     arco(sibiu,fagaras,99).
     arco(fagaras,bucharest,211).
     arco(pitesti,bucharest,101).
     arco(bucharest,giurgiu,90).
     arco(bucharest,urziceni,85).
     arco(urziceni,hirsova,98).
     arco(hirsova,eforie,86).
     arco(urziceni,vaslui,142).
     arco(vaslui,iasi,92).
     arco(iasi,neamt,87).