Introdução à Programação em Lógica
DM da U.Aveiro
cursos de MAC - EM

Trabalho Prático num.^o 2 (programação lógica avançada)

1998

1  Objectivos e Organização

Este trabalho prático tem como principais objectivos:

• Sedimentar os conhecimentos envolvidos no paradigma de programação lógico, expandido--os à análise/especificação de problemas mais complexos.
• Desenvolver as capacidades de programação em Prolog.

Para atingir esses objectivos, esta folha contém quatro enunciados. Esses enunciados são, propositadamente, deixados relativamente vagos por forma a respeitar a capacidade imaginativa e de organização de cada grupo e, até, para nos permitir avaliar soluções diferentes de grupo para grupo.
Quanto ao relatório a elaborar, para entregar junto com o programa, deve ser claro e sucinto e, além do respectivo enunciado e listagem do programa (apresentados em apêndice), deverá conter uma explicação dos predicados incluídos na BC, bem como exemplos de execução em que se mostrem os resultados produzidos para várias questões.
Recorde-se que uma síntese do trabalho (caracterização do problema, estratégia de resolução adoptada e resultados atingidos) deverá ser apresentada oralmente a toda a turma, na última semana de aulas.

2  Enunciados

Diagramas de Pert

Desenvolva um porgrama em Prolog para ajudar a fazer o planeamento e controlo de actividades/projectos usando uma Rede de Actividades (Diagrama de Pert).
O seu programa deverá aceitar o definição do grafo orientado que modela a dita rede e deverá calcular as actividades críticas do projecto, bem como responder a outras questões relacionadas com as actividades que se podem executar em paralelo e as que têm de ser executadas em sequência.

Árvore de Decisão

O objectivo geral deste trabalho é desenvolver um programa em Prolog capaz de simular em computador um processo de decisão com capacidade de aprendizagem. Esse tipo de programa pode ser útil para classificar objectos (físicos, ou não) de acordo com as suas características observáveis, ou para decidir da adequabilidade de uma coisa ou pessoa para determinado fim, ou para nos ajudar a tomar uma opção. Em qualquer um dos casos, o programa deve ter a capacidade de incorporar mais conhecimento, tornando-se mais esperto, se cada vez que for usado não apresentar a solução que o utilizador acha correcta.
Assim e para cumprir tal objectivo, o grupo de trabalho deverá escolher uma situação concreta -por exemplo, classificação de animais, classificação de figuras geométricas, classificação de doenças, escolha da toilete a usar em determinadas situações, etc.- à qual quer aplicar esta técnica de programação baseada numa árvore binária de decisão.
Numa 1^\ba fase, o grupo deve implementar a sua árvore de decisão e a aprendizagem, sem qualquer preocupação com a interface, ou seja, o programa será usado invocando directamente os predicados desenvolvidos, sem facilidades especiais para formatação / apresentação dos resultados calculados.
Numa 2^\ba fase, pretende-se melhorar o programa desenvolvido dotando-o com um processador de linguagem que permita aos Utilizadores dialogarem numa linguagem mais livre, próxima da nossa língua natural (português). Na verdade, na versão que foi construida na fase anterior, para que alguém possa usar os programas e coloque questões à base de conhecimento, é necessário que conheça a sintaxe exacta de cada predicado (nome preciso do predicado, número de argumentos e ordem pela qual eles devem aparecer). Para optimizar a interface desses trabalhos será desejável que o Utilizador possa construir questões numa sintaxe mais natural, com maior grau de liberdade.
Os grupos que escolherem este trabalho, terão de definir a linguagem que querem fornecer aos Utilizadores do seu programa, especificá-la usando uma gramática (segundo o formalismo DCG) e construir um tradutor que reconheça as novas frases e gere os predicados convenientes para questionar a base de conhecimento.

O dicionário marciano

``It is later than you think'' could not be expressed in Martian - nor could ``Haste makes waste'', though for a different reason: the first notion was inconceivable while the latter was an unexpressed Martian basic, as unnecessary as telling a fish to bathe. But ``As it was in the Beginning, is now and ever shall be'' was so Martian in mood that it could be translated more easily than ``two plus two makes four'' - which was not a truism on Mars.

Robert A. Heinlein, Stranger in a Strange Land

¹Ninguém sabe como ou por que desapareceu a civilização marciana, mas uma caverna no sopé do monte Olimpo guarda uma triste recordação desta cultura antiga e fabulosa. No interior da caverna existe uma placa, reminiscente da famosa pedra de Roseta, coberta por um tecido empoeirado de composição desconhecida. Afastando este tecido, surge o que parece ser uma espécie de dicionário: uma lista de palavras na metade esquerda da placa está associada a uma lista à direita. Duas frases aparecem gravadas no fundo da placa. Essas frases estão relacionadas de uma forma peculiar. A primeira pode ser transformada na segunda por substituição repetida de palavras contidas no dicionário: cada palavra da frase no lado esquerdo do dicionário pode ser substituída pela correspondente palavra no lado direito. Os sábios do Marte antigo defendiam que qualquer informação que valesse a pena aprender, podia ser obtida começando com uma frase básica e substituindo palavras de acordo com o dicionário da sabedoria, cujo único fragmento se encontra na caverna. Em geral, um computador não poderá verificar se uma dada frase pode ser derivada da frase básica. Por outras palavras, não existe qualquer possibilidade de escrever um programa de computador (não importa quão extenso ou rápido) que seja capaz de decidir correctamente, para cada dicionário e duas palavras (ou frases) de entrada, se é possível a tradução da primeira para a segunda palavra. A demonstração decorre da insolubilidade do chamado problema de paragem e do facto de que o problema da paragem pode ser convertido no problema da tradução marciana.

O problema da tradução marciana é um exemplo de uma família de puzzles que requerem a transformação de palavras, frases e até parágrafos inteiros em outras palavras, frases e parágrafos. Entre muitos passatempos matemáticos e simbólicos destaca-se uma transformação chamada ``escada de palavras''. Numa escada de palavras começamos com duas palavras específicas. A primeira palavra chama-se origem e a segunda destino. Poderemos transformar a palavra origem na palavra destino alterando uma letra de cada vez? Se as duas palavras têm o mesmo número de letras, a tarefa é trivial. Mas poderemos garantir que todas as cadeias de caracteres intermédias são também palavras? Podemos, de facto, partir de ``gato'' para ilustrar o processo. Num passo, a palavra pode ser alterada para ``pato''; noutro passo, para ``rato''. Com esta alquimia até parece possível que ``gato'' pode ser facilmente modificado para qualquer nome com quatro letras. Será isto possível?

Algumas ideias para o trabalho - ``achas para a fogueira''

• Arranje-se um dicionário e construa-se em Prolog um programa que pesquise o dicionário para encontrar palavras relacionadas. O utilizador especifica uma dada palavra e um predicado será o responsável pela formação da tal ``teia de palavras'', satisfazendo os requerimentos da escada de palavras.
• Para sabermos se a palavra destino pode ser encontrada a partir da palavra origem, poderíamos percorrer apenas a ``teia de palavras'' a partir de origem e ver se nesta viagem encontramos destino.
• Tentem transformar bom em mau. Melhor ainda, podem tentar converter amor em ódio, ganhando uma visão moral e lógica do processo...
• Considerem uma variação interessante das escadas de palavras: Para além da substituição de letras individuais, deixar as letras rastejarem, como lagartas, para fora da palavra, aumentando ou diminuindo as palavras de uma letra no início ou no fim.
• Que tal complementar o dicionário de palavras com regras simples que permitam ``baralhar'' os caracteres? Por exemplo, uma regra da forma aba baa significa que o símbolo b pode ser deslocado uma posição à esquerda quando rodeado de a's.

``Package de matemática''

No âmbito das aulas práticas, foi implementado um ``package de matemática'' -ficheiro math.pl - que permite o cálculo do valor numérico de expressões matemáticas na notação usual. Com este trabalho pretende-se que aumentem a funcionalidade deste ``package'', principalmente no que diz respeito aos seguintes pontos:

• Tratamento de erros de sintaxe (dá jeito uma DCG)).
• Manejo de expressões que envolvam variáveis (com ou sem atribuição de valores).
• Permitir derivação simbólica² de funcões reais em relação a uma variável. Salientamos alguns aspectos a ter em consideração:
  • Simplificação das expressões: não permitir respostas em que apareçam termos como  x+x ou x +1+x quando pode escrever   2*x e  2*x+1.
  • Naturalidade na forma como as expressões podem ser escritas:
    • 2 a x em vez de  2*a*x
    • d( x\symbol942) /dx em vez de algo como  deriva( x\symbol942,x)

Exemplo (esta ou outra sintaxe amigável):

         ?-calcula('{X=2+3!; y=2}, d(X^3+y)/dX * (3^2+1)+6-Z^y', R).
           R = 1926 - Z^2
 

Footnotes:

¹ O que se segue pode ser encontrado (com mais detalhe...) em ``A. K. Dewdney, A Máquina Mágica -Um manual de Magia Computacional, Ciência Aberta, 68, Gradiva, 1994, Cap. 21.''

² As regras de derivação básicas, implementadas em Prolog, podem ser encontradas em ``Domingos Moreira Cardoso, Programação em Lógica e Demonstração Automática de Teoremas, Cadernos de Matemática  CM/D-03, pág. 54-56''