Busca avançada
Ano de início
Entree

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)

Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa:
Mais itensMenos itens
Matéria(s) publicada(s) em Outras Mídias ( ):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

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.