Busca avançada
Ano de início
Entree

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

Processo: 05/50796-0
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de maio de 2005
Vigência (Término): 28 de fevereiro de 2006
Área do 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

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)