Problemas de Corte e Empacotamento: Abordagens Práticas e Teóricas
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 | |
TITULO | |
Matéria(s) publicada(s) em Outras Mídias ( ): | |
Mais itensMenos itens | |
VEICULO: TITULO (DATA) | |
VEICULO: TITULO (DATA) | |