|
Suma prefijaEn 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:
Por ejemplo, las sumas de los prefijos de los números naturales son los siguientes números triangulares :
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
|
