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 (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 |