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.