aed3-2011-1-exercicio-5

Prévia do material em texto

Universidade Federal de Lavras
Departamento de Ciência da Computação
GCC109 – Algoritmos e Estruturas de Dados III
Professor: Denilson Alves Pereira
Lista de Exercícios 5
 Data Limite de Entrega: 05/06/11 (turma 10A) e 09/06/11 (turma 14A)
 O exercício deve ser entregue pelo Moodle (http://aluno.dcc.ufla.br). Envie arquivos somente nos 
formatos txt e pdf (não enviar .doc, .docx, .odt etc.). Arquivos compactados somente .zip e .tar.gz (não 
enviar .rar, .z etc.). Não use acentos e nem “ç” nos nomes de arquivo.
 Exercícios copiados receberão nota zero
1. (a) Crie uma estrutura de arquivo invertido para o texto abaixo:
“Teste de arquivo invertido. Teste com texto invertido. Base de teste para arquivo invertido.”
(b) Explique com fazer uma pesquisa por um token (palavra) único, com vários tokens 
conectados por uma operação lógica AND, com vários tokens conectados por uma operação 
lógica OR, e pesquisa por frase. Dê exemplo de cada caso.
2. No algoritmo de Rabin-Karp, considere uma função hash que transforma as cadeias de 
caracteres usando uma base = 3 e o código ASCII do caractere, conforme descrito nas notas de 
aula. Mostre como seriam os cálculos para comparação entre o padrão “AFED” e o texto 
“AFAFEDXYZ”, até que a primeira ocorrência seja encontrada.
3. Considerando o algoritmo de Knuth-Morris-Pratt, faça:
(a) Mostre os valores gerados pela função de prefixo pi para o padrão “ABRACADABRA”.
(b) Mostre como seriam os deslocamentos do padrão “ABRACADABRA” no texto:
“ABRCCADABRACACAABRACADABRAABRABRACADA”
4. Considerando o algoritmo de Boyer-Moore-Horspool, faça:
(a) Mostre os valores das entradas na tabela de deslocamentos para o padrão 
“ABRACADABRA”.
(b) Mostre como seriam os deslocamentos do padrão “ABRACADABRA” no texto:
“ABRCCADABRACACAABRACADABRAABRABRACADA”
5. Explique porque a complexidade de tempo de execução do algoritmo de Knuth-Morris-Pratt é 
θ(n).
6. Implemente uma função na linguagem C para o algoritmo de Rabin-Karp. Considere uma 
máquina com palavra de 32 bits e um vocabulário composto pelos 128 primeiros caracteres do 
código ASCII. Mostre também o código que você usou para testar a função.
7. Implemente uma função na linguagem C para o algoritmo de Knuth-Morris-Pratt. Mostre também 
o código que você usou para testar a função.
8. Implemente uma função na linguagem C para o algoritmo de Boyer-Moore-Horspool. Mostre 
também o código que você usou para testar a função.
	GCC109 – Algoritmos e Estruturas de Dados III
	Lista de Exercícios 5