O problema da subsequência comum máxima sem repetições

Autor(es)

Christian Tjandraatmadja

• Tipo de documento: Dissertação de Mestrado
• Imprenta: São Paulo.
• Instituição: Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI)
• Data de defesa: 2010-07-26

Membros da banca

Carlos Eduardo Ferreira; Marie France Sagot; Yoshiko Wakabayashi

• Orientador: Carlos Eduardo Ferreira

Resumo

Exploramos o seguinte problema: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y sem 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 e 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 sequências X e Y sobre um alfabeto finito, encontre uma subsequê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. (AU)

• Processo FAPESP: 07/57149-5 - Abordagens exatas e aproximacoes para o problema da subsequencia comum mais londa sem repeticoes e variantes.
• Beneficiário: Christian Tjandraatmadja
• Modalidade de apoio: Bolsas no Brasil - Mestrado