Proposta de Trabalho
Aluno: Leo Kazuhiro Ueda
Supervisora: Nami Kobayashi
Este documento é a proposta de trabalho para a disciplina MAC 499 - Trabalho de Formatura Supervisionado do ano de 2001 do BCC do IME-USP.Para este trabalho pretendo utilizar o meu projeto de Iniciação Científica:
Título do projeto: Autômatos Finitos: Algoritmos e Estruturas de Dados Orientadora: profa. Nami Kobayashi Período: março/2001 a dezembro/2001 Bolsas: PIBIC/CNPq - março/2001 a julho/2001, agosto/2001 a julho/2002
| O Projeto |
O objetivo do projeto é conhecer os principais algoritmos e as estruturas de dados fundamentais que se utilizam de autômatos finitos de forma eficiente, a fim de permitir o estudo de suas inúmeras aplicações.
Os tópicos principais do projeto são:
Muitos textos básicos sobre autômatos finitos apresentam
algoritmos para minimizar o número de estados de um autômato
finito determinístico. Entretanto, a complexidade de tempo no pior
caso destes algoritmos é O(|A|n2), ou pior,
onde A é o alfabeto de entrada e n é o
número de estados do autômato que se deseja minimizar. A proposta
é estudar:
O problema da busca de um padrão num texto consiste em localizar uma ou todas as ocorrências do padrão do texto. O texto é simplesmente uma seqüência de símbolos, mas o padrão pode ser especificado ou por uma palavra, ou por um conjunto finito de palavras, ou por uma expressão regular.
O plano é estudar o caso em que o padrão representa um
conjunto finito L de palavras. A solução clássica
para este problema foi desenvolvida por Aho e Corasick. O algoritmo deles
é uma extensão do algoritmo de Knuth, Morris e Pratt, e implementa
um autômato determinístico reconhecendo a linguagem
A*L.
Fixado o alfabeto A, a complexidade de tempo para a construção
desse autômato e o espaço utilizado são O(m),
onde m é a soma dos comprimentos das palavras no dicionário
L.
A complexidade de tempo para a busca é O(n), onde n
é o comprimento do texto.
O autômato dos sufixos de uma palavra x é o autômato finito determinístico mínimo que reconhece o conjunto de todos os sufixos de x.
Quando o problema da busca de padrões é aplicado a textos fixos, as soluções existentes costumam construir um índice sobre o texto, o que torna mais eficiente as buscas subseqüentes. Em geral, um índice é uma estrutura de dados que contém todos os sufixos de uma palavra e, portanto, todos os seus fatores. As duas estruturas mais utilizadas para armazenar os sufixos de uma palavra são o autômato dos sufixos e a árvore de sufixos. Ambas as representações são compactas no sentido que seus tamanhos são lineares no comprimento da palavra, embora a soma dos comprimentos de todos os sufixos de uma palavra seja quadrática no comprimento da palavra. Além disso, ambos podem ser construídos em tempo linear sobre alfabetos fixos.
O autômato dos sufixos pode ser utilizado no problema da busca de padrões, seja diretamente, seja de forma mais elaborada, incluindo busca com erros. Também pode ser aplicado no cálculo eficiente de uma série de estatísticas sobre uma palavra, algumas delas úteis em Biologia Molecular.
Estudaremos o autômato dos sufixos principalmente nos seguintes
aspectos:
| Atividades realizadas |
Estudo e implementação dos algoritmos de Hopcroft (a partir da descrição de David Gries), de Revuz, e de Aho e Corasick.
Para cada algoritmo, estudamos também as provas de corretude e complexidades de tempo e de espaço. Os principais artigos pesquisados foram:
| Cronograma |
Não temos uma definição precisa de datas para o estudo de cada um dos itens restantes já mencionados. Pretendemos estudar todos os tópicos propostos até dezembro de 2001, continuando com as reuniões semanais.
| Estrutura do Trabalho |
Pretendo estruturar a monografia da seguinte forma: