O problema do menor ancestral comum: revisao, melhorias e implementacao.

• Processo: 05/50796-0
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de maio de 2005
• Data de Término da vigência: 28 de fevereiro de 2006
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Alair Pereira Do Lago
• Beneficiário: Daniel Noel Ribeiro
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Assunto(s): Otimização combinatória Teoria dos grafos Biologia computacional Análise de algoritmos
• Palavra(s)-Chave do Pesquisador: Algoritmos Em Grafos | Analise De Algoritmos | Biologia Computacional | Combinatoria Das Palavras | Otimizacao Combinatoria

Resumo

Algoritmos sobre textos é uma classe muito ampla de algoritmos com aplicações de grande relevância para diversas áreas como Biologia Molecular Computacional e o desenvolvimento de ferramentas de buscas na Internet Devido ao volume gigantesco de dados envolvidos, soluções lineares são muito procuradas, pois podem tornar solúvel um problema antes intratável. Duas das estruturas de dados mais avançadas que permitem algoritmos extremamente eficientes são as Árvores dos Sufixos e as Tabelas que permitem a resolução do problema do Menor Ancestral Comum em tempo constante após um pré-processamento linear. O projeto se concentra em estudar o problema do Menor Ancestral Comum, algumas de suas soluções algorítmicas, propor também melhorias (tanto no quesito de utilização de memória quanto no de tempo de processamento) a estas soluções, formalizar e escrever estas melhorias, implementá-las e realizar benchmarks. Ademais, deseja-se estudar algumas de suas aplicações, em particular, envolvendo árvores dos sufixos. (AU)