Última alteração: Marco 21, 2002

ENGENHARIA DE CONTROLE E AUTOMAÇÃO

ALGORITMOS E ESTRUTURAS DE DADOS II

Prof. Nivio Ziviani

Monitora: Claudine Santos Badue

Trabalho Prático 4

Data de Entrega: 09-abril-2002


Comentários Gerais

1.
Comece a fazer este trabalho logo, enquanto o problema está fresco na memória e o prazo para terminá-lo está tão longe quanto jamais poderá estar.
2.
Penalização por atraso: vide texto apresentação da disciplina.
3.
O objetivo deste trabalho é o de projetar e implementar um sistema de programas, incluindo as estruturas de dados e os algoritmos. Neste trabalho, o aluno terá a oportunidade de exercitar parcialmente o conceito de independência de implementação, através da utilização de duas estruturas de dados distintas para implementar o mesmo problema. Neste caso, o módulo que implementa cada uma das estruturas de dados deverá permitir o intercâmbio entre uma estrutura e outra, causando o menor impacto possível em outras partes do programa.


O que deve ser apresentado:

1.
Listagem do programa em Pascal.
2.
Listagem dos testes executados.
3.
Descrição sucinta (por exemplo, desenho), das estruturas de dados e as decisões tomadas relativas aos casos e detalhes de especificação que porventura estejam omissos no enunciado.
4.
Estudo da complexidade do tempo de execução dos procedimentos implementados e do programa como um todo (notação O).


Avaliação:

1.
Execução
(a)
Execução correta: 20%
(b)
Saída legível: 10%
2.
Estilo de programação
(a)
Código bem estruturado: 10%
(b)
Código legível: 10%
3.
Documentação
(a)
Descrição das estruturas de dados e principais decisões: 35%
(b)
Estudo da complexidade do tempo: 15%


Problema: Criação de índice remissivo


Várias aplicações necessitam de um relatório de referências cruzadas. Por exemplo, a maioria dos livros apresentam um índice remissivo que corresponde a uma lista alfabética de palavras chave ou palavras relevantes do texto com a indicação dos locais no texto onde cada palavra chave ocorre.

Como exemplo, suponha um arquivo contendo um texto constituído como abaixo: 


		 Linha 1:  Good programming is not learned from
		 Linha 2:  generalities, but by seeing how significant
		 Linha 3:  programs can be made clean, easy to
		 Linha 4:  read, easy to maintain and modify,
		 Linha 5:  human-engineered, efficient, and reliable,
		 Linha 6:  by the application of common sense and
		 Linha 7:  by the use of good programming practices.

Assumindo que o índice remissivo seja constituído das palavras chave: 


		 programming,   programs,  easy,  by,  human-engineered,  and, be, to,

o programa para criação do índice deve produzir a seguinte saída: 


		 and 		 4 		 5 		 6
		 be 		  3
		 by 		 2 		 6 		 7
		 easy 		 3 		 4
		 human-engineered 		 5
		 programming 		 1 		 7
		 programs 		 3
		 to 		 3 		 4

Note que a lista de palavras chave está em ordem alfabética. Adjacente a cada palavra está uma lista de números de linhas, um para cada vez que a palavra ocorre no texto.

Projete um sistema para produzir um índice remissivo. O sistema deverá ler um número arbitrário de palavras chave que deverão constituir o índice remissivo, seguido da leitura de um texto de tamanho arbitrário, o qual deverá ser esquadrinhado à procura de palavras que pertençam ao índice remissivo.

Cabe ressaltar que:

Utilize um método eficiente para verificar se uma palavra lida do texto pertence ao índice. Para resolver este problema, você deve utilizar duas estruturas de dados distintas:

Observe que, apesar do hashing ser mais eficiente do que árvores de pesquisa, existe uma desvantagem na sua utilização: após atualizado todo o índice remissivo, é necessário imprimir suas palavras em ordem alfabética. Isto é imediato em árvores de pesquisa, mas, quando se usa hashing, isto é problemático, sendo necessário ordenar a tabela hash que contém o índice remissivo.

Comece a pensar tão logo seja possível, enquanto o problema está fresco na memória e o prazo para terminá-lo está tão longe quanto jamais poderá estar.

Utilize o código Pascal abaixo, bem como os dois arquivos de entrada, a saber:

Utilize o seguinte makefile .


Nivio Ziviani
3/21/2002