Exportar registro bibliográfico

O problema da subseqüência comum máxima sem repetições (2010)

  • Autores:
  • Autor USP: TJANDRAATMADJA, CHRISTIAN - IME
  • Unidade: IME
  • Sigla do Departamento: MAC
  • Assunto: OTIMIZAÇÃO COMBINATÓRIA
  • Agências de fomento:
  • Idioma: Português
  • Resumo: 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
  • Acesso à fonte
    Como citar
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      TJANDRAATMADJA, Christian; FERREIRA, Carlos Eduardo. O problema da subseqüência comum máxima sem repetições. 2010.Universidade de São Paulo, São Paulo, 2010. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13092010-093911/?&lang=pt-br >.
    • APA

      Tjandraatmadja, C., & Ferreira, C. E. (2010). O problema da subseqüência comum máxima sem repetições. Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13092010-093911/?&lang=pt-br
    • NLM

      Tjandraatmadja C, Ferreira CE. O problema da subseqüência comum máxima sem repetições [Internet]. 2010 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13092010-093911/?&lang=pt-br
    • Vancouver

      Tjandraatmadja C, Ferreira CE. O problema da subseqüência comum máxima sem repetições [Internet]. 2010 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13092010-093911/?&lang=pt-br

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

    Biblioteca Digital de Produção Intelectual da Universidade de São Paulo     2012 - 2021