UNIVERSIDADE FEDERAL DE MINAS GERAIS

INSTITUTO DE CIÊNCIAS EXATAS

DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO

ALGORITMOS E ESTRUTURAS DE DADOS II

Prof. Raquel O. Prates 01 de junho de 2006

Trabalho Prático 4 – Pesquisa

Data de entrega: 26 de junho de 2006 (SEM possibilidade de adiamento)

Penalidade por atraso: 10% do total do trabalho por dia de atraso

Objetivo do trabalho: O objetivo deste trabalho é permitir aos alunos implementar alguns dos algoritmos de pesquisa.

Descrição do Trabalho:

O trabalho consiste em implementar e 2 algoritmos de pesquisa vistos em sala: Árvore Binária de Pesquisa e Hash com listas encadeadas. A árvore deve ter como chave números inteiros, e a tabela hash deve ter como chave strings. Os usuários deverão ser capazes de inserir, retirar, reinicializar e pesquisar uma chave. A árvore ou tabela não precisa estar visível durante todo o tempo, mas deve ter disponível uma função para visualizá-la. A visualização pode ser feita por meio de texto, mas deve ficar claro para o usuário a estrutura da árvore ou hash. Pontos extras serão dados para a visualização gráfica da árvore (veja abaixo). Além de executar as funções, o programa deve narrar para o usuário de forma didática os passos necessários para se atingir o objetivo. Não interessa narrar questões específicas sobre a implementação, mas sobre a idéia geral do algoritmo. A idéia é que o sistema possa auxiliar um aluno que esteja aprendendo sobre estas estruturas.

Por exemplo, se o usuário escolher insere (7) na árvore, poderia se ter:

Visualização antes	Narrativa dos passos	Visualização depois
5 / \ 3 8 / \ 1 4	Insere (7) Compara com o nó de chave 5 Vai para a sub-árvore da direita Compara com o nó de chave 8 Vai para a sub-árvore da esquerda Encontra posição Insere nó com chave 7	5 / \ 3 8 / \ / 1 4 7

Além disso, o sistema deve oferecer as seguintes facilidades:

· Inicializar árvore ou tabela com valores aleatórios iniciais. A quantidade de chaves da inicialização deve ser fornecida pelo usuário. (As strings para inicializar a tabela hash, não precisam ser palavras).

· Opção de executar a função de uma vez ou passo a passo (em ambos os casos a narrativa é mostrada). No passo a passo o usuário controla quando passar para o próximo passo. Na execução direta o usuário deve ser capaz de ler a narrativa, se necessário pode-se incluir um atraso entre os passos.

Incrementando o trabalho:

O aluno poderá incrementar o trabalho para ganhar pontos extras. O que pode ser feito é:

· Mostrar na tela sempre a estrutura da árvore e hash (textual), além da narrativa e o menu, de forma que a visualização seja atualizada automaticamente sempre (pelo menos no fim da execução da ação solicitada). Vale 10%.

· Interface gráfica, na qual a estrutura é desenhada (não textual) e deve estar disponível, além da narrativa e menu. Vale 20%.

· Interface gráfica, mostrando a animação, ou seja a narrativa é acompanhada por uma indicação na visualização. Menu, narrativa e visualização devem estar sempre presentes. Vale 40%.

Observações:

· As opções de interface gráfica devem garantir a não sobreposição de nós da árvore até o nível 4 ou 5.

· Os pontos extras de cada opção não são cumulativos.

Exemplo e inspiração:

Animações de algoritmos que acompanham o livro "Data Structures and Algorithms in Java," Second Edition. Robert Lafore, 2002 podem ser usadas como exemplo e inspiração. Outras animações dos algoritmos vistos em sala estão disponíveis no site do curso.

Considerações sobre o trabalho:

· O trabalho deverá ser feito individualmente.

· O trabalho poderá ser feito em C ou PASCAL

· O aluno deve se preocupar com a qualidade do código sendo gerado, assim, o programa deve estar dividido em subrotinas, deve-se usar constantes sempre que apropriado, selecionar nomes mnemônicos para variáveis, o programa não deve fazer uso de variáveis globais ou de comandos GOTO.

O que deve ser entregue:

1. O código do programa (eletrônico e impresso)

2. O programa executável

3. A documentação do programa, contendo:

a) Introdução: descrição do problema a ser resolvido e visão geral sobre o funcionamento do programa, explicando aspectos relacionados ao uso e apresentação das estruturas solicitadas.

b) Plataforma: Deve estar descrito a linguagem e compilador usados, assim como a justificativa da escolha pela linguagem. Caso uso algum toolkit para interface, deve apresentá-lo também.

c) Implementação: descrição sobre a implementação do programa. Deve ser detalhada a estrutura de dados utilizada (diagramas ilustrativos podem auxiliar a explicação da estrutura), o funcionamento das principais funções e procedimentos utilizados, o formato de entrada e saída de dados, bem como decisões tomadas relativas aos casos e detalhes de especificação que porventura estejam omissos no enunciado.

d) Estudo de Complexidade: estudo da ordem de complexidade do tempo de execução dos procedimentos implementados e do programa como um todo (notação O).

e) Conclusão: comentários gerais sobre o trabalho e as principais dificuldades encontradas em sua implementação.

f) Bibliografia: bibliografia que porventura tenha sido utilizada para o desenvolvimento do trabalho, incluindo sites da Internet se for o caso

Será marcada uma entrevista com cada aluno para apresentação dos trabalhos. O aluno deverá saber responder a todas as perguntas, sob pena de ser descontados nos itens em que não souber responder, ou mesmo no trabalho como um todo.