Busca avançada
Ano de início
Entree

Abordagens exatas e aproximações para o problema da subsequência comum mais londa sem repetições e variantes

Processo: 07/57149-5
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de março de 2008
Vigência (Término): 28 de fevereiro de 2010
Área do 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

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 São Paulo.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.