[en] ON THE LOWER BOUND FOR THE MAXIMUM CONSECUTIVE SUB-SUMS PROBLEM

• Ano de defesa: 2014
• Autor(a) principal: WILFREDO BARDALES RONCALLA
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] ALGORITMO; [pt] SOMAS MAXIMAS; [pt] SUBSEQUENCIA DE SOMA MAXIMA; [pt] VETORES DE PARIKH; [pt] CASAMENTO DE PADROES MISTURADOS; [pt] CASAMENTO APROXIMADO DE PADROES; [en] ALGORITHM
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=23833&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=23833&idi=2; http://doi.org/10.17771/PUCRio.acad.23833

[pt] O Problema das Sub-somas Consecutivas Máximas (MCSP) surge em cenários de interesse teórico e prático, por exemplo, no casamento aproximado de padrões, identificação de proteínas e análise de dados estatísticos apenas para nomear alguns. Dada uma sequência de n números reais não negativos, O MCSP consiste em calcular as somas consecutivas máximas de tamanho 1 até n. Como existem implementações triviais que permitem encontrar o máximo para um comprimento fixo, existe um procedimento quadrático simples que permite resolver o MCSP. Apesar dos esforços dedicados ao problema, não é conhecido nenhum algoritmo significativamente melhor que a solução simples. Portanto, uma pergunta natural é se existe um limite inferior superlinear para o MCSP. Neste trabalho reportamos nossas pesquisas no sentido de provar tal limite.