MAC-IME-USP IMRE SIMON CARLOS EDUARDO FERREIRA
SALA 290A TEL.: 3818 6142
SALA 297A TEL.: 3818 6140
EMAIL is@ime.usp.br
E-MAIL cef@ime.usp.br
MONITORA: ELIDIA Y. ITIKAWA
MONITOR: MARCIO C. CABRAL
Este exercício-programa é substitutivo. Você deve fazê-lo se deixou de entregar algum dos três EPs anteriores. Caso você tenha entregado os três primeiros e mesmo assim quer fazer este, não há problemas. Serão consideradas para efeito do cálculo da média, as três melhores notas.
Como no EP anterior, este exercício-programa será avaliado pelo código e também pelos testes que vocês fizerem para avaliar a corretude e eficiência dos algoritmos, assim como o relatório com os resultados que vocês obtiverem para o problema proposto.
Um dos problemas mais importantes e com mais aplicações em Ciência da Computação é o problema de busca de padrões. O objetivo é, dado um texto e um certo padrão, determinar eficientemente se o padrão ocorre ou não no texto, e, se ocorre, em que posição.
Neste exercício-programa vocês devem implementar, e analisar a eficiência (do ponto de vista empírico) pelo menos do algoritmo ``ingênuo'' e do KMP, vistos em sala de aula. Outros algoritmos podem ser implementados e testados. Um bom texto para o assunto é o capítulo 34 do (excelente) livro:
Introduction to Algorithms
Thomas H. Cormen, Charles E. Leiserson e Ronald L. Rivest
McGraw-Hill 1990.
Bônus: Muitas vezes buscas de padrões exatas não são suficientes para aplicações práticas. Pense a respeito, pesquise, e implemente soluções para problemas relacionados com buscas de padrões como, por exemplo:
Exemplo: Imagine que você deseja encontrar em um texto todas as palavras que começam com TR e terminam em O, tais como treino, troco, transtorno, etc. Podemos representar este conjunto de palavras por TR*O, onde o caractere * representa qualquer seqüência de caracteres.
Exemplo: Ao procurar o nome de uma pessoa em uma lista, muitas vezes não sabemos exatamente como é sua grafia correta. Assim, ao procurarmos, por exemplo, um ``Luís'', seria bom recebermos também os nomes ``Luis'', ``Luiz'', ``Luíz'', ``Louis'', etc.