(estruturas de dados não lineares)
21 de Outubro de 1998

 
 O trabalho deve ser executado em grupos de 2 ou  3 alunos,
 e deve ser entregue em data a combinar na semana de 14 de Dezembro.
 **** A sua concretização é obrigatória para efeitos de avaliação *** 
 A nota prática global entrará na nota final com um peso de 40%.

1 Objectivos e Organização
 

Este trabalho prático tem como objectivos levar os alunos, através da resolução de problemas reais, a:

• aplicar os conhecimentos adquiridos sobre representação e manipulação de grafos e outras estruturas de dados não-lineares, como tabelas de dispersão;
• praticar a programação na linguagem C;
• usar convenientemente as facilidades do sistema Unix como ambiente de desenvolvimento de programas.

Quanto ao relatório a elaborar, para entregar na altura da apresentação do trabalho, deve ser claro e sucinto e, além do enunciado, deverá conter exemplos de utilização com os respectivos resultados.  O relatório deverá indicar claramente a representação interna escolhida para o grafo.
 

2 Enunciados
 

Questao 1 (Palavras) 

Um passatempo engraçado consiste em verificar se é possível transformar 2 palavras dadas, com o mesmo omprimento, mudando em cada passo 1 só caracter mas passando sempre por palavras válidas, isto é, existentes num dicionário da lingua em causa.

Por exemplo, "bom" pode transformar-se em "mal" através da seguinte sequencia de passos: "som", "sol", "sal".

Pretende-se que desenvolva um programa para verificar se, dadas 2 palavras, a primeira \emph{é transformável} na segunda, de acordo com o critério de conversão em passos sucessivos, acima enunciado.  Caso a transformação seja possível, o seu programa deve imprimir a lista de palavras em causa.

Para isso o seu programa deve começar por ler um dicionário ---conjunto de palavras válidas--- e  guardá-lo na forma de um grafo, considerando que 2 palavras são adjacentes se tiverem o mesmo comprimento e diferirem apenas em 1 caracter.
 
 

Questao 2 (Orientação)

Um dos objectivos das provas de orientação é percorrer no mínimo tempo uma determinada região (montanhosa, ou mista) passando por todas as balizas colocadas em vários pontos dessa região e assinalados na respectiva carta geográfica.
 
Assuma que lhe são fornecidas todas as balizas, univocamente identificadas por um código alfanumérico, e a distancia entre as balizas vizinhas (aquelas entre as quais há passagem directa).

Desenvolva, então, um programa baseado na teoria dos grafos, que seja  capaz de lhe indicar o caminho mais curto entre 2 balizas dadas.
 

Questao 3 (Labirinto)

Um labirinto pode ser pensado como um tabuleiro de xadrez rectangular  ---uma matriz de `n' linhas por `m' colunas--- em que se definem os pares de quadrículas ("casas" do tabuleiro, ou componentes da matriz)  entre as quais há uma passagem directa.  As quadrículas serão identificadas pelas suas coordenadas (numeros de linha e de coluna).

Modelando o labirinto através dum grafo não-orientado e não-pesado, desenvolva um programa que seja capaz de calcular todos os caminhos entre 2 quadrículas dadas.
 

Questao 4 (Disciplinas)

Para se obter um determinado grau de formação profissional numa área de conhecimento foram organizados cursos constituidos por módulos, ou unidades de ensino.  Algumas dessas unidades fornecem as bases de conhecimento necessárias para o estudo de outras unidades.  Assim, a ordem, pela qual os módulos referidos podem ser estudados, não é totalmente livre, ou arbitrária.
 

Usando a teoria dos grafos, desenvolva um programa que, após ler o nome das unidades de ensino e as precedencias entre elas, seja capaz de:

• sugerir uma sequencia de estudo dos módulos, possível para completar o curso
• identificar todas as unidades das quais uma dada unidade de ensino depende.