Busca avançada
Ano de início
Entree


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

Texto completo
Autor(es):
Christian Tjandraatmadja
Número total de Autores: 1
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
Data de defesa:
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 aproximações para o problema da subsequência comum mais londa sem repetições e variantes
Beneficiário:Christian Tjandraatmadja
Linha de fomento: Bolsas no Brasil - Mestrado