En informática, la suma prefija, suma acumulativa, escaneo inclusivo, o simplemente escaneo de una secuencia de números es una secuencia secundaria de números , donde las sumas de los prefijos ( totales acumulados ) de la secuencia de entrada son calculados de la siguiente forma:
...
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 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,. 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....
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...
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
Categoría:Algoritmos