Universidade Federal de Minas Gerais
Departamento de Ciência da Computação
Última alteração: Junho 5, 2002
Este trabalho consiste de implementar um índice remissivo em
linguagem C. A descrição do trabalho é apresentada
como o exercício 3, do cap 2 do livro Projeto de Algoritmos
de Nivio Ziviani (Pags 59-64).
O objetivo principal deste trabalho é familiarizar
o aluno com conceitos da linguagem C e do ambiente de programação
Unix. Assim, deverão ser seguidas as seguintes
diretrizes:
- 1.
- as estruturas de dados devem ser
alocadas dinamicamente com malloc.
- 2.
- as matrizes são providas em arquivos texto que devem
ser lidos pelo programa.
- 3.
- os arquivos de entrada e o arquivo de saída devem ser
informados na linha de comando utilizando a primitiva getopt.
- 4.
- o programa deve ser estruturado em três módulos
(arquivos):
principal.c, arquivo.c e matriz.c. O
módulo principal.c contém o programa principal
(main) e as rotinas de inicialização e leitura
da linha de comandos. O módulo arquivo.c contem
as funções de leitura e escrita de arquivos.
O módulo matriz.c contem as
funções para
manipulação de matrizes esparsas.
A compilação destes
módulos deve ser gerenciada usando o aplicativo make.
Todas as definições de tipos e protótipos de
funções devem constar em header files (arquivos
do tipo .h).
- 5.
- não podem ser usadas variáveis globais.
- 6.
- o programa deve tratar erros triviais como
arquivos não existentes.
- 7.
- o programa deve compilar com gcc -Wall sem qualquer
mensagem de erro ou aviso.
O programa implementado deve ser avaliado para vários
tamanhos de arquivos de entrada, utilizando as funções
getrusage e gettimeofday. Deve-se também
distinguir entre os tempos de computação e
tempos de entrada e saída. Comente sobre os
tempos de usuário e os tempos de sistema e sua
relação com os tempos de relógio.
A elaboração de arquivos de entrada para o trabalho faz parte
do mesmo.
Avaliação
Deverão ser entregues:
- listagem das rotinas;
- descrição breve dos algoritmos e das estruturas
de dados utilizadas;
- análise da complexidade das rotinas;
- análise dos resultados obtidos.
Distribuição dos pontos:
- execução
execução correta: 10%
saída legível: 10%
- estilo de programação
código bem estruturado: 15%
código legível: 15%
- documentação
comentários explicativos: 20%
análise de complexidade: 10%
análise de resultados: 20%
Nivio Ziviani
6/5/2002