[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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:23833 |
| Date | 26 December 2014 |
| Creators | WILFREDO BARDALES RONCALLA |
| Contributors | EDUARDO SANY LABER |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | English |
| Detected Language | English |
| Type | TEXTO |
Page generated in 0.0022 seconds