Suma prefija
En informática, la suma prefija, suma acumulativa, escaneo inclusivo, o simplemente escaneo de una secuencia de números x0, x1, x2, ... es una secuencia secundaria de números y0, y1, y2, ..., donde las sumas de los prefijos ( totales acumulados ) de la secuencia de entrada son calculados de la siguiente forma:
- y0 = x0
- y1 = x0 + x1
- y2 = x0 + x1+ x2
- ...
Por ejemplo, las sumas de los prefijos de los números naturales son los siguientes números triangulares :
| números | 1 | 2 | 3 | 4 | 5 | 6 | ... |
|---|---|---|---|---|---|---|---|
| suma prefija | 1 | 3 | 6 | 10 | 15 | 21 | ... |
El cálculo de sumas prefijas es trivial en modelos secuenciales de computación, usando la fórmula yi = yi − 1 + xi para calcular cada valor de salida en orden secuencial. Sin embargo, a pesar de su facilidad de cálculo, las sumas prefijas son una primitiva útil en ciertos algoritmos como el ordenamiento por cuenta,[1][2] y forman la base de la función de orden superior de escaneo en lenguajes de programación funcional . Las sumas prefijas también se han estudiado mucho en algoritmos paralelos, usándolo como un problema de prueba o como una primitiva útil como subrutina en otros algoritmos paralelos.[3][4][5]
En resumen, una suma prefija requiere solo un operador asociativo binario ⊕, aportando muchas aplicaciones, desde el cálculo de descomposiciones de pares bien separados de puntos hasta el procesamiento de cadenas.[6][7]
Matemáticamente, la operación de cálculo de sumas prefijas se puede generalizar desde secuencias finitas a infinitas; en ese contexto, una suma de prefijo se define como una suma parcial de una serie . La suma prefija o la suma parcial forman operadores lineales en los espacios vectoriales de secuencias finitas o infinitas; sus inversos son operadores de diferencias finitas .
Referencias[editar]
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), «8.2 Counting Sort», Introduction to Algorithms (2nd edición), MIT Press and McGraw-Hill, pp. 168-170, ISBN 0-262-03293-7..
- ↑ Cole, Richard; Vishkin, Uzi (1986), «Deterministic coin tossing with applications to optimal parallel list ranking», Information and Control 70 (1): 32-53, doi:10.1016/S0019-9958(86)80023-7.
- ↑ Ladner, R. E.; Fischer, M. J. (1980), «Parallel Prefix Computation», Journal of the ACM 27 (4): 831-838, doi:10.1145/322217.322232..
- ↑ Tarjan, Robert E.; Vishkin, Uzi (1985), «An efficient parallel biconnectivity algorithm», SIAM Journal on Computing 14 (4): 862-874, doi:10.1137/0214061..
- ↑ Lakshmivarahan, S.; Dhall, S.K. (1994), Parallelism in the Prefix Problem, Oxford University Press, ISBN 0-19508849-2..
- ↑ Blelloch, Guy (2011), Prefix Sums and Their Applications (Lecture Notes), Carnegie Mellon University..
- ↑ Callahan, Paul; Kosaraju, S. Rao (1995), «A Decomposition of Multi-Dimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields», Journal of the ACM 42 (1): 67-90, doi:10.1145/200836.200853..