Universidade de São Paulo

Instituto de Ciências Matemáticas e de Computação

Departamento de Ciências da Computação e Estatística

Primeiro Semestre de 1999

1. Adventure Game. Um AG é a simulação de um ambiente, real ou imaginário, que o usuário explora , geralmente com uma meta na mente. Explore Duck World e Nanisrch que acompanham AMZI e faça o seu próprio. Tela inicial do Nanisrch:

?- main.

NANI SEARCH - A Sample Adventure Game

Copyright (C) Amzi! inc. 1990-1995

No rights reserved, use it as you wish

 

Nani Search is designed to illustrate Prolog programming.

As such, it might be the simplest adventure game. The game

is the primary example used in APT - The Active Prolog Tutor.

Full source is included as well.

 

Your persona as the adventurer is that of a three year

old. The Nani is your security blanket. It is getting

late and you're tired, but you can't go to sleep

without your Nani. Your mission is to find the Nani.

 

You control the game by using simple English commands

expressing the action you wish to take. You can go to

other rooms, look at your surroundings, look in things

take things, drop things, eat things, inventory the

things you have, and turn things on and off.

Hit any key to continue.

2. Problema da coloração de mapas. Atribuir a cada país em um dado mapa planar uma de 4 cores de tal forma que nenhum dos vizinhos sejam pintados com a mesma cor. O teorema das 4 cores foi provado em 1976 por Appel e Haken e garante que é possível solucionar este problema usando somente 4 cores. Por exemplo:

3. Formular definições para uma família representada usando estrutura de árvore e operadores. Tome as relações masculino, feminino e pais como básicas e defina as outras com base nestas. Defina um predicado de localização de um nó na árvore. Suponha a base de dados abaixo.

 



:- op(500,xfx,'e_um_dos_pais_de').

 

a e_um_dos_pais_de b.

a e_um_dos_pais_de c. ...

 

?- localize(n).

a --> c --> h --> n

 

4. Animal Game. Implemente o jogo em que o computador deve descobrir o animal que você imaginou através de perguntas/respostas.

 

 

 

 

?- go.

Does the animal have the following attribute: has_hair? yes.

 

Does the animal have the following attribute: eats_meat? yes.

 

Does the animal have the following attribute: has_tawny_color? yes.

 

Does the animal have the following attribute: has_dark_spots? no.

 

Does the animal have the following attribute: has_black_stripes? no.

 

Does the animal have the following attribute: has_hooves? yes.

 

Does the animal have the following attribute: has_long_neck? yes.

 

Does the animal have the following attribute: has_long_legs? yes.

 

I guess that the animal is: giraffe

 

yes

 

5. Gerador de tabelas Verdade.Desenvolva um programa para calcular e mostrar tabelas verdade para expressões booleanas envolvendo and, or e not. O programa deverá: reconhecer expressões infixas envolvendo and, or, e not; encontrar as variáveis na expressão booleana; gerar valores iniciais para cada variável; avaliar a expressão para aqueles valores iniciais; gerar o próximo valor para as variáveis. O programa deve ter o comportamento seguinte:

 

?- gerador_tabelas(x or (not y and z)).

 

[x,y,z] x or (not y and z)

-----------------------------------

[0,0,0] 0

[0,0,1] 1

[0,1,0] 0

[0,1,1] 0

[1,0,0] 1

[1,0,1] 1

[1,1,0] 1

[1,1,1] 1

-----------------------------------

6. Escreva um programa que entenda sentenças simples do inglês. O programa deve dar respostas apropriadas (yes, no, unknow), com base nas sentenças fornecidas previamente. A forma delas é a seguinte:

 

-------is a -------.

A ----- is a ------.

Is ------a---------?

 

7. Planejador de rotas. Dado um mapa que descreve estradas que conectam cidades, escreva um programa que planeja uma rota entre 2 cidades, fornecendo horários de duração das viagens. O mapa deve incluir kilometragem, condições das estradas, disponibilidade de postos de gasolinas.

 

8. ELIZA2. Escreva um programa que simule uma psiquiatra.

 

 

9. Vinte_e_um. Dada uma lista não vazia de números naturais, gere uma expressão aritmética que dê um resultado pré estabelecido S. Por exemplo, sejam os números naturais 3 e 7, qual seria(m) a(s) expressões geradoras do valor 21?

 

?- vinte_e_um([3,7],T,21).

 

T = 3 * 7 ;

 

T = (- 3) * (- 7) ;

no

 

Ou ainda:

 

?- vinte_e_um([1,5,6,7],T,18).

 

T = 7 + (6 + 1 * 5) ;

 

T = 7 + (6 + (- 1) * (- 5)) ;

no

 

Utilize parênteses e as operações básicas de adição, negação (que pode substituir a subtração), multiplicação, e divisão somente.

 

 

10. Tradução em Prolog. Traduza as seguintes regras em um programa Prolog. Teste com uma base de dados com vários aplicantes.

 

These are the rules for membership of a very snobbish club.

 

A person applying for membership of the Ballymucknacreevy Jetsetter's Club

(hereinafter referred to as the applicant) will be deemed acceptable for

membership provided the applicant has been proposed by two other persons

(hereinafter referred to as the proposers), each of whom is qualified to

propose the aforementioned applicant and provided the applicant is eligible

for membership under the terms below.

 

The applicant must be less than 40 years of age.

 

A proposer is not qualified to propose a potential applicant if he or

she earns less than $40,000 or of he or she has been a member of the

Club for less than two years.

 

A proposer may not be a parent of the applicant.

 

An applicant is eligible for membership if his or her annual salary

is not less than $50,000. Alternatively, an applicant earning not

less than $30,000 will be eligible provided a parent of the applicant

would be eligible for membership under the above rules.

 

11. Mundo_dos_blocos. Considere o domínio do mundo dos blocos em que existe uma mesa que suporta 3 blocos nos quais podem ser empilhados outros blocos, e que a pilha possa ter qualquer altura. Estados neste domínio podem ser representados por uma lista de 3 listas. Por exemplo:

 

estado = [[a,b,c],[d],[e,f]] ==> a

b e

c d f

----------

Escreva um programa imprime(estado) que imprime um dado Estado na forma visual acima.

 

12. Tradução em Prolog2.

 

Tweety é um pássaro. Goldie é um peixe. Squiggly é uma minhoca. Pássaros gostam de minhoca. Gatos gostam de peixe. Gatos gostam de pássaros. Amigos se gostam. Meu gato é meu amigo. Meu gato come tudo o que ele gosta.

 

Pergunta: O que come meu gato?

 

Crie outra descrição similar, traduza para PROLOG e faça perguntas pertinentes.

 

13. Alice.

 

Quando Alice entrou na "Floresta Encantada", ela não se esqueceu de tudo, somente de algumas coisas. Uma das coisas que ela mais facilmente esquece é o dia da semana.

O leão e o unicórnio são duas criaturas bastante estranhas, que também freqüentam a Floresta Encantada. É sabido que o leão mente nas segundas, terças e quartas e fala a verdade nos outros dias da semana, enquanto que o unicórnio mente nas quintas, sextas e sábados, mas fala a verdade nos outros dias da semana.

 

Um dia Alice encontrou o leão e o unicórnio descansando sob uma árvore, e pergunta a ambos qual o dia da semana e recebe as seguintes respostas:

 

Leão: Ontem foi meu dia de mentir.

Unicórnio: Ontem foi meu dia de mentir.

Diante destas declarações, Alice, que era uma garota inteligente , verificou que poderia deduzir o dia da semana. Qual é o dia?

 

Desenvolva em Prolog o programa correspondente.

 

14. Grafos e caminhos . Considere grafos, por exemplo:


Represente grafos em Prolog, considerando que eles tenham comprimento. Escreva um programa para calcular os caminhos mais curtos entre 2 pontos.

 

15. Crypto-arithmetic Puzzles. Implemente um resolvedor genérico de puzzles aritméticos como o clássico:

** S E N D

** + M O R E

** ---------

** M O N E Y

O objetivo deste jogo é atribuir um digito a cada letra em SEND e MORE e então adicionar aqueles valores como um problema matemático normal e obter MONEY como uma resposta. Faça um programa genérico, com a restrição de que 2 números para serem adicionados tenham o mesmo número de dígitos e a solução um digito a mais (veja que send e more tem 4 dígitos e money 5). Outra entrada:

 

[C,R,O,S,S] + [R,O,A,D,S] = [D,A,N,G,E,R].

 

16. Mundo dos Blocos 2. A seguinte figura representa três pilhas de blocos sobre uma mesa:

Represente em Prolog os fatos que descrevem as relações entre os blocos. Use dois predicados: um deles para indicar que um bloco está sobre outro bloco e outro para indicar que um bloco está imediatamente à esquerda de outro bloco. Para os blocos que estão sobre a mesa, defina somente fatos do segundo tipo.

Faça as seguintes perguntas:

1. Qual bloco está sobre o bloco B?
2. Quais são os blocos tal que A está embaixo?
3. Quais blocos estão sobre outros blocos?
4. Quais blocos estão sobre blocos que estão imediatamente à esquerda de outro bloco?

Defina o predicado acima(X,Y) e pilha_esquerda(X,Y) recursivos. Gere perguntas pertinentes.

17) Troco para um dolar. Faça um programa para gerar ou checar troco para um dólar consistindo de half-dollars, quarters, dimes, nickels, e pennies. Faça perguntas como:

?- troco([H,Q,D,N,P]).

para listar todos os possíveis meios de dar o troco.

18. Oito_rainhas. Resolva o problema das oito rainhas: como posicionar oito rainhas em um tabuleiro de xadrez, de tal forma que não haja ataque entre elas. Experimente diferentes posições iniciais para estudar a eficiência da execução do programa.

 

19. Cálculo proposicional. Escreva um programa para produzir a negação de uma expressão proposicional. Elas são construídas de átomos e operadores not, and, or e -->. Use operadores. A expressão negada deve estar na sua forma mais simples, onde not é aplicado somente a átomos. Por exemplo, a negação de