Abordagens exatas e aproximacoes para o problema da subsequencia comum mais londa sem repeticoes e variantes.

• Processo: 07/57149-5
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de março de 2008
• Data de Término da vigência: 28 de fevereiro de 2010
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
• Pesquisador responsável: Carlos Eduardo Ferreira
• Beneficiário: Christian Tjandraatmadja
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Vinculado ao auxílio: 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas, AP.PRNX.TEM
• Assunto(s): Otimização combinatória Algoritmos de aproximação Biologia computacional
• Palavra(s)-Chave do Pesquisador: Algoritmos De Aproximacao | Biologia Computacional | Combinatorio Poliedrica | Otimizacao Combinatoria

Resumo

O problema da subseqüência comum de comprimento máximo é um problema bastante estudado com várias aplicações em computação. Neste problema, dadas duas seqüências de entrada, busca-se encontrar uma subseqüência comum de comprimento máximo delas. Na variante que estudaremos neste projeto estamos interessados em obter uma subseqüência de comprimento máximo em que cada símbolo do alfabeto pode aparecer no máximo uma vez. Esta variante surge naturalmente em problemas de Biologia Computacional. O aluno vem trabalhando no problema em sua iniciação científica, com bolsa da FAPESP (Proc. 2007/54282-6), em que implementou alguns algoritmos simples de aproximação para o problema, e fez um estudo empírico de suas performances quando aplicados a instâncias geradas aleatoriamente. No mestrado pretendemos dar continuidade a esse estudo, buscando outros algoritmos de aproximação para o problema e melhorando os resultados que obtivemos no estudo de um poliedro relacionado com o problema. Pretendemos ainda abordar outras variantes do problema, em que reversões nas seqüências são permitidas. (AU)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

TJANDRAATMADJA, Christian. O problema da subsequência comum máxima sem repetições. 2010. Dissertação de Mestrado - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.