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

[pt] SOBRE O LIMITE INFERIOR PARA O PROBLEMA DAS SUB-SOMAS CONSECUTIVAS MÁXIMAS

[pt] WILFREDO BARDALES RONCALLA

[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

[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.

[en] The Maximum Consecutive Subsums Problem (MCSP) arises in scenarios of both theoretical and practical interest, for example, approximate pattern matching, protein identification and analysis of statistical data to cite a few. Given a sequence of n non-negative real numbers, The MCSP asks for the computation of the maximum consecutive sums of lengths 1 through n. Since trivial implementations allow to compute the maximum for a fixed length value, it follows that there exists a naive quadratic procedure to solve the MCSP. Notwithstanding the effort devoted to the problem, no algorithm is known which is significantly better than the naive solution. Therefore, a natural question is whether there exists a superlinear lower bound for the MCSP. In this work we report our research in the direction of proving such a ower bound.

EDUARDO SANY LABER

MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO

EDUARDO SANY LABER

DAVID SOTELO PINHEIRO DA SILVA

2014-12-26

2013-08-29

[pt] TEXTO

application/pdf

INGLÊS

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=23833@1

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=23833@2

https://doi.org/10.17771/PUCRio.acad.23833