O problema da subseqüência comum máxima sem repetições (2010)
- Autores:
- Autor USP: TJANDRAATMADJA, CHRISTIAN - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: OTIMIZAÇÃO COMBINATÓRIA
- Agências de fomento:
- Idioma: Português
- Resumo: Exploramos o seguinte problema: dadas duas seqüências X e Y sobre um alfabeto finito, encontre uma subseqüência comum máxima de X e Y se, símbolos repetidos. Estudamos a estrutura deste problema, particularmente do ponto de vista de grafos e de combinatória poliédrica. Desenvolvemos algoritmos de aproximação e heurísticas para este problema. O enfoque deste trabalho está na construção de um algoritmo baseado na técnica branch-and-cut, aproveitando-nos de um algoritmo de separação eficiente de heurísticas e técnicas para encontrarmos uma solução ótima mais cedo. Também estudamos um problema mais fácil no qual este problema é baseado: dadas duas seqüências X e Y sobre um alfabeto finito, encontre uma subseqüência comum máxima de X e Y. Exploramos este problema do ponto de vista de combinatória poliédrica e descrevemos vários algoritmos conhecidos para resolvê-lo.
- Imprenta:
- Data da defesa: 26.07.2010
-
ABNT
TJANDRAATMADJA, Christian; FERREIRA, Carlos Eduardo. O problema da subseqüência comum máxima sem repetições. 2010.Universidade de São Paulo, São Paulo, 2010. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13092010-093911/?&lang=pt-br >. -
APA
Tjandraatmadja, C., & Ferreira, C. E. (2010). O problema da subseqüência comum máxima sem repetições. Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13092010-093911/?&lang=pt-br -
NLM
Tjandraatmadja C, Ferreira CE. O problema da subseqüência comum máxima sem repetições [Internet]. 2010 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13092010-093911/?&lang=pt-br -
Vancouver
Tjandraatmadja C, Ferreira CE. O problema da subseqüência comum máxima sem repetições [Internet]. 2010 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13092010-093911/?&lang=pt-br
Como citar
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
