O problema da subseqüência comum máxima sem repetições (2010)
- Authors:
- Autor USP: TJANDRAATMADJA, CHRISTIAN - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: OTIMIZAÇÃO COMBINATÓRIA
- Agências de fomento:
- Language: Português
- Abstract: 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. O problema da subseqüência comum máxima sem repetições. 2010. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2010. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13092010-093911/. Acesso em: 19 set. 2024. -
APA
Tjandraatmadja, C. (2010). O problema da subseqüência comum máxima sem repetições (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13092010-093911/ -
NLM
Tjandraatmadja C. O problema da subseqüência comum máxima sem repetições [Internet]. 2010 ;[citado 2024 set. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13092010-093911/ -
Vancouver
Tjandraatmadja C. O problema da subseqüência comum máxima sem repetições [Internet]. 2010 ;[citado 2024 set. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13092010-093911/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
