Ensino Estrutura de Dados I Atividades 2007.1

Graduação em

<Estrutura de Dados I>

Atividades

Durante o período o aluno deverá desenvolver 3 trabalhos que consistem basicamente de implementações dos algoritmos vistos em sala de aula e que complementam a sua formação em termos de prática de programação e de aprendizado de uma linguagem de programação. Os trabalhos colaboram com as 3 avaliações escritas para compor as notas do aluno.

Passeio do Cavalo. Suponha dado um tabuleiro de xadrez n-por-n . Determine se é possível que um cavalo do jogo de xadrez parta de uma posição (x,y) qualquer do tabuleiro e complete um passeio por todas as n×n posições do tabuleiro em n×n-1 passos válidos. Por exemplo para um tabuleiro 5-por-5 uma solução do problema é

                    1  6 15 10 21
                   14  9 20  5 16
                   19  2  7 22 11
                    8 13 24 17  4
                   25 18  3 12 23

Sugestão:

Algoritmo usando Backtracking

Inicialize N e a posição inicial (x0,y0)

i:=0;

Repita

Se há posições válidas a serem alcançadas a partir de (xi,yi)

Selecione a próxima posição

Empilhe e visite a escolha; Passe para a próxima iteração i = i+1;

Se não

Cancele a escolha; Desempilhe o último estado válido

Até obter sucesso ou não haver mais candidatos a escolher

Observação: não usar recursividade nem geração de permutações

Linguagens permitidas

Os trabalhos podem ser desenvolvidos apenas nas seguintes linguagens de programação: C, Pascal, C++ e Java

Apresentação dos trabalhos

Os trabalhos devem ser entregues na data determinada em formato de documento e podem eventualmente, a critério do professor, serem apresentados em laboratório na mesma data ou data posterior à entrega.

Os documentos devem ser "zipados" contendo todos os arquivos solicitados pelo professor, tais como: fonte, executável e relatório de resultados. O arquivo zipado deve ser entregue ao professor via email ou via mídia apropriada (CD, disquete). No nome do arquivo zipado deve constar o nome e o código do aluno.

A pedido do professor, o aluno poderá ainda entregar uma cópia impressa do relatório de resultados até a data determinada.

Relatório de resultados

O relatório de resultados documenta o trabalho de implementação, apresentando desde a justificativa para a solução algorítmica empregada pelo aluno até os resultados obtidos por ele e as principais dificuldades encontradas. Ele deve ser suficientemente completo para permitir ao professor o pleno entendimento e avaliação do trabalho realizado pelo aluno. Dentre outros recursos, o aluno deve lançar mão de trechos de código fonte que expliquem determinadas rotinas, imagem de telas de execução, gráficos, impressão de arquivos de resultados, etc.

O formato do relatório de resultados pode ser baixado aqui.

Multiplicador de Inteiros Imensos. Dados dois inteiros imensos armazenados em listas encadeadas, produzir uma terceira lista encadeada contendo o resultado da multiplicação entre eles.

A multiplicação pode ser realizada da forma como aprendemos, isto é, a soma deslocada de várias multiplicações:

1 1 1 1 1 1 1 1 1 1 (lista 1)

x 1 1 1 1 1 (lista 2)

=========================

1 1 1 1 1 1 1 1 1 1

=====================

1 2 3 4 5 5 5 5 5 5 4 3 2 1

Árvore de Huffman ou Árvore de Jogos (escolher uma opção).

Objetivo Huffman: implementar um programa que leia um arquivo qualquer e gere o código de huffman (código de comprimento variável)
e calcule o percentual de compactação que seria obtido usando essa codificação.

Objetivo Jogos: implementar uma versão para o jogo da captura usando o procedimento min-max.

*** Árvore de Hufman ***

Links:

http://en.wikipedia.org/wiki/Huffman_coding

http://inf.unisinos.br/~ari/estrut/huffman/compactacao.htm

Passos básicos:

1		O usuário escolhe o arquivo a ser codificado através de uma interface gráfica ou linha de comando
2		O arquivo é lido e armazenado em uma lista ordenada pela freqüência dos bytes lidos (fila de prioridades)
3		A partir da fila de prioridades é gerada a árvore de huffman
3.1		>> separando-se a fila de prioridades da árvore de hufman
3.2		>> mantendo-se a fila de prioridades juntamente com a árvore de huffman em um única estrutura
		>>> onde cada nó possui 3 ponteiros ( 1 para a lista e 2 para a árvore)
3.3		>> outra opção de preferência do aluno
4		A partir da árvore de huffman, devem ser gerados os códigos de huffman de cada símbolo encontrado no arquivo
5		O grau de compactação a ser obtido com a codificação encontrada é apresentada como relatório

Avaliação básica:

de 0,0 a 2,5 pontos, dependendo da apresentação em laboratório, da qualidade da interface com o usuário e grau de dificuldade dos algoritmos
implementados (exemplo: implementação usando o passo 3.2 é melhor avaliada)

Avaliação opcional

de 2,5 a 4,0 pontos, dependendo da implementação de uma ou mais das seguintes etapas:

6		Gravação do arquivo codificado (compactado) em disco com extensão .SHUF
		>> usando deslocamento de bits e o que mais for necessário para realmente o arquivo HUF apresentar uma redução de
		>>> tamanho em relação ao original
7		Gravação do arquivo tabela de huffman em disco com a extensão .THUF, em separado
8		Implementação do descompactador que lê o arquivo SHUF e a tabela THUF e reconstrói o arquivo original (decodificada)
9		Empacotamento do compactador e descompactador em um único aplicativo: o WinHUF

*** Árvore de Jogos ***

Implementar uma das seguintes versões (com tabuleiro reduzido):

** Bin Laden no Paquistão (ele apenas foge)

** Bin Laden em Nova Iorque (ele ataca também)

** Bin Laden no Brasil