O problema da subseqüência comum máxima sem repetições (2010)
- Authors:
- Autor USP: TJANDRAATMADJA, CHRISTIAN - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2010.tde-13092010-093911
- 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
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
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: https://teses.usp.br/teses/disponiveis/45/45134/tde-13092010-093911/. Acesso em: 09 abr. 2026. -
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 https://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 2026 abr. 09 ] Available from: https://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 2026 abr. 09 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-13092010-093911/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
