| O trabalho deve ser realizado em grupo, |
| e deve ser entregue a funcionar e acompanhado dum relatório |
| até ao dia 23 de Maio. |
| *** A sua concretização é obrigatória para efeitos de avaliação *** |
| A nota prática global entrará na nota final com um peso de 50%. |
Este trabalho prático tem como principais objectivos:
Para atingir esses objectivos, esta folha contém quatro enunciados; contudo os dois
primeiros correspondem a dois trabalhos distintos que deverão ser executados por um par
de grupos de alunos. 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.
Questão 1 [Projecto Casino] O Casino Dakalecas, ponto de referência no
desenvolvimento turístico da região de Aveiro, está presentemente a diversificar o seu
leque de oferta em jogos. Nesse sentido, contratou-os para desenvolverem dois programas:
um para jogar o Jogo das Cores e outro que implemente o Jogo da Vida.
(JOGO DAS CORES)
Este jogo desenvolve-se num tabuleiro formado por buracos organizados na forma de um
quadrado ou de um rectângulo e utiliza um conjunto de peças de diversas cores. O
objectivo é colocar as peças nos buracos de forma a que nenhum par de peças da mesma
côr fique colocado de forma contígua, tanto na horizontal, como na vertival, como na
diagonal.
Pretende a gerência do casino que o programa deixe o cliente definir a dimensão do
tabuleiro, o número de cores e o número de peas de cada côr com que se jogará. O
programa deve permitir dois modos de utilização:
(AUTóMATOS CELULARES
E VIDA ARTIFICIAL)
A teoria matemática dos autómatos celulares foi criada por John von Neumann,
nos anos cinquenta. Um autómato celular é um conjunto de células -quadrados dispostos
numa grelha bidimensional, semelhante a um tabuleiro de xadrez, onde cada casa é uma
célula.
Cada célula pode estar num certo número de estados (tal como cada casa do tabuleiro pode
estar num estado branco ou num estado preto).
O autómato inteiro pode evoluir no tempo de acordo com um conjunto de regras
predefinidas; essas regras de evolução são baseadas no estado em que se encontram as
células vizinhas da célula em causa (recorde-se que em volta de cada célula existem
oito outras células). Por exemplo, uma regra podia então dizer que sempre que haja
quatro ou mais células brancas em torno de uma outra, esta célula muda de côr no passo
temporal seguinte.
Há inúmeras possibilidades de regras diferentes e cada conjunto de regras conduz a uma
evolução diferente do autómato. A ideia de um autómato celular é simples ...
decepcionalmente simples. Há, no entanto, quem veja os autómatos celulares para além de
meras curiosidades matemáticas e chegue mesmo a afirmar que o Universo é um computador e
em particular um autómato celular. Quem já brincou com autómatos celulares em ecrãs de
computadores, ficou concerteza impressionado com o facto de, com certos tipos de regras,
os autómatos poderem gerar ondas e outros tipos de movimentos observados na natureza.
Uma boa maneira de visualizar um autómato celular consiste em imaginar o ecrã de um
monitor como uma matriz -a cada elemento da matriz, chamamos pixel. Neste sistema simples
um pixel pode estar aceso, ''1'', ou apagado, ''0''. Estes pixels serão as células
componentes do autómato a representar.
Para desenvolver o jogo pretendido, os requisitos da gerência do casino são:
A definição das regras de evolução concretas a implementar e do número de
estados possível para cada célula é deixada ao critério do grupo de trabalho.
Observaão: O Casino Dakalecas considera que estes dois jogam partilham algo em
comum! De facto ambos são baseados num tabuleiro rectangular, configurável. No jogo da
vida, o facto de uma célula estar viva ou morta pode ser representado por uma côr. Se
pensarmos que uma célula pode conter vários estados de energia (que vai da energia zero,
que equivale a estar morta, a um nível de energia máximo) e representarmos esse nível
de energia por uma côr, podemos olhar para o Jogo da Vida como um Jogo das Côres com
regras específicas. Por este motivo a gerência do casino pretende ter dois grupos de
trabalho em simultâneo que possam aproveitar um interface comum, discutir várias
soluções e integrar os dois programas num só.
Questão 2 [Projecto de Apoio à Feitura de Horários] No nosso
departamento, os horários são feitos ``à mão'', havendo por vezes problemas com a
gestão dos vários recursos: disciplinas, salas e docentes. Pretende-se a implementaão
de dois programas: um de gestão de salas e disciplinas; e um outro de gestão de docentes
e disciplinas.
Tal como no projecto anterior, pretende-se que haja dois grupos de trabalho em
simultâneo que possam aproveitar uma especificação comum da base de conhecimento -as
disciplinas sob a responsabilidade do nosso departamento- e que no final sejam
capazes de discutir várias soluões e integrar os dois programas num só.
Este programa integrado de apoio à feitura de horários, deve possuir um menu de
questões pertinentes, bem como as operações de manutenão necessárias.
Descrevem-se agora detalhadamente cada um desses problemas.
(GESTãO DE SALAS E DISCIPLINAS)
Pretende-se a construção de um programa que permita manter uma base de conhecimento
com as salas existentes e as suas caractarísticas (número de alunos que comporta, se
está destinada exclusivamente a aulas com determinadas características, etc.), bem como
o horário de ocupação de cada sala, em cada tempo lectivo (8h00 as 19h00) ao longo da
semana, permitindo a realizaão de consultas pertinentes, como sejam:
Para responder a questões deste tipo, será necessário manter em simultâneo uma base de conhecimento das disciplinas, que contenha as características próprias de cada cadeira (curso a que se destina, ano de licenciatura, escolaridade da disciplina, etc) assim como o número total de alunos inscritos. Para o caso de existitem vários turnos da mesma disciplina, será também necessário indicar a distribuição dos alunos por esses turnos. Sugere-se a manutenção de três triplos para cada disciplina:
(GESTãO DE DOCENTES E DISCIPLINAS)
Este programa deve permitir manter uma base de conhecimento com as disciplinas, tal
como foi sugerido na questão anterior, e uma base de conhecimento de docentes.
Esta última deve conter atributos tais como: estatuto do docente (assistente, doutorado
ou agregado), a área científica em que se integra (Análise, Álgebra, Computaão,
Investigação Operacional, etc), uma lista com as cadeiras que tem dado em anos
anteriores, uma lista com as cadeiras que prefere dar no próximo ano, horário do
semestre corrente, horário de atendimento, etc. Estes dados devem permitir responder a
questões do género:
Questão 3 [Espectátulo de Folclore] Em trabalho desenvolvido na
UM (no contexto dum projecto de 5\bo ano), foi desenvolvido um compilador
que permite, ao Responsável por um Grupo de Danças Folclóricas, descrever os
recursos de que dispõe para efectivar um determinado espectáculo, bem como o programa
(sequência de danas) que pretende apresentar.
Esse compilador tem acesso a uma base de dados onde estão definidos todos os recursos
habituais do grupo: danças; dançadores; cantadores; tocadores.
Ao descrever a informação para planear um espectáculo, basta pois declarar: novos
recursos que se queiram acrescentar à base de dados; recursos que se queira ver
definitivamente removidos; e os membros habituais do grupo que não irão estar presentes
no espectáculo a programar.
O compilador, após validar a informação descrita gera um programa em Prolog, que é constituido por um conjunto de factos que descrevem
os 4 recursos básicos do Grupo Folclórico (acima enumerados) -correspondentes ao
predicados danca, dancador, cantador, tocador- e um outro
conjunto de factos que descrevem as danças a alocar, e os recursos humanos que não pode
ser incluídos. Além disso, o programa inclui a invocação a um predicado, aloca/0, que implementa um algoritmo standard de alocação dos
cantadores, tocadores e pares de dançadores a cada dança prevista para o programa do
espectáculo.
Este trabalho consiste, precisamente, na análise da base de conhecimento gerada pelo
compilador e no desenvolvimento do dito algoritmo de formação dos pares que irão
dançar cada dança (bem como dos tocadores e cantadores que serão usados).
A questão principal em causa, é a identificação de todas as restrições que devem ser
respeitadas na formação dos ditos pares de dançadores, de modo a satisfazer as vontades
de cada pessoa, os ideias estéticos do responsável pelo grupo e a proporcionar a todos
os elementos uma intervenção semelhante no espectáculo (não se pretende que um
dançador entre em 5 danças e um outro só dance 1).
Questão 4 [Interfaces em lingua natural] O intuito desta proposta de
trabalho é melhorar os programas desenvolvidos pelos grupos na 1\ba série de
problemas (proposta nesta disciplina), dotando-os com um processador de linguagem que
permita aos Utilizadores desses programas 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.