| dbo:abstract
|
- In der Informatik ist die Präfixsumme einer Folge von Zahlen a0, a1, a2, … die Zahlenfolge s0, s1, s2, … ihrer Partialsummen: s0 = a0s1 = a0 + a1s2 = a0 + a1+ a2… Beispielsweise ist die Präfixsumme der natürlichen Zahlen die Folge der Dreieckszahlen: Die Präfixsumme ist mit einer einfachen Schleife sequenziell berechenbar, indem mit der Formel si = si−1 + ai für i>0 jeder Summenwert sukzessive aufaddiert wird. Die Präfixsumme bildet die Grundlage für Algorithmen wie den Countingsort.Sie kann statt der Summierung als Basisoperation eine allgemeine assoziative binäre Operation verwenden, womit sie beispielsweise zur Polynominterpolation oder zur Stringbearbeitung eingesetztund in der funktionalen Programmierung auf Funktionen höherer Ordnung angewandt werden kann; in diesem Falle wird sie auch Scan genannt. Da die Präfixsumme mit dem Fork-join-Modell zudem effizient auf Mehrkernprozessorsystemen und Rechnerclustern berechnet werden kann, spielt sie in Betrachtungen zu parallelen Algorithmen eine wichtige theoretische und praktische Rolle, als zu lösendes Testproblem ebenso wie als Subroutine wichtiger paralleler Algorithmen. Mathematisch kann die Berechnung der Präfixsumme von endlichen auf unendliche Folgen verallgemeinert werden. Sie stellt dann eine Reihe dar. Die Präfixsummierung ist ein linearer Operator auf einem Vektorraum endlicher oder unendlicher Folgen. Seine Inverse ist ein Differenz-Operator. (de)
- In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers x0, x1, x2, ... is a second sequence of numbers y0, y1, y2, ..., the sums of prefixes (running totals) of the input sequence: y0 = x0y1 = x0 + x1y2 = x0 + x1+ x2... For instance, the prefix sums of the natural numbers are the triangular numbers: Prefix sums are trivial to compute in sequential models of computation, by using the formula yi = yi − 1 + xi to compute each output value in sequence order. However, despite their ease of computation, prefix sums are a useful primitive in certain algorithms such as counting sort,and they form the basis of the scan higher-order function in functional programming languages. Prefix sums have also been much studied in parallel algorithms, both as a test problem to be solved and as a useful primitive to be used as a subroutine in other parallel algorithms. Abstractly, a prefix sum requires only a binary associative operator ⊕, making it useful for many applications from calculating well-separated pair decompositions of points to string processing. Mathematically, the operation of taking prefix sums can be generalized from finite to infinite sequences; in that context, a prefix sum is known as a partial sum of a series. Prefix summation or partial summation form linear operators on the vector spaces of finite or infinite sequences; their inverses are finite difference operators. (en)
- В информатике префиксная сумма, кумулятивная сумма, инклюзивное сканирование или просто сканирование последовательности чисел x0, x1, x2, … называется последовательность чисел y0, y1, y2, …, являющаяся префиксной суммой от входной последовательности: y0 = x0y1 = x0 + x1y2 = x0 + x1+ x2… Например, префиксными суммами натуральных чисел являются треугольные числа: Префиксные суммы тривиальны для вычисления в последовательных моделях вычислений, путем применения формулы yi = yi − 1 + xi для вычисления каждого выходного значения в порядке последовательности. Тем не менее, несмотря на простоту вычислений, префиксные суммы являются полезным примитивом в некоторых алгоритмах, таких как сортировка подсчетом,и они составляют основу функции сканирования более высокого порядка в функциональных языках программирования. Суммы префиксов также широко изучались в параллельных алгоритмах, и как тестовая задача, которую нужно решить, и как полезный примитив для использования в качестве подпрограммы в других параллельных алгоритмах. Теоретически, префиксная сумма требует только , что делает ее полезной во многих алгоритмах: от вычисления точек до обработки строк. Математически, операция взятия префиксных сумм может быть обобщена от конечных до бесконечных последовательностей; в этом смысле префиксная сумма известна как частичная сумма ряда. Префиксное суммирование или частичное суммирование образует линейное отображение на векторные пространства конечных или бесконечных последовательностей; их обратные операторы являются конечными разностями. (ru)
|
| rdfs:comment
|
- In der Informatik ist die Präfixsumme einer Folge von Zahlen a0, a1, a2, … die Zahlenfolge s0, s1, s2, … ihrer Partialsummen: s0 = a0s1 = a0 + a1s2 = a0 + a1+ a2… Beispielsweise ist die Präfixsumme der natürlichen Zahlen die Folge der Dreieckszahlen: Die Präfixsumme ist mit einer einfachen Schleife sequenziell berechenbar, indem mit der Formel si = si−1 + ai (de)
- In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers x0, x1, x2, ... is a second sequence of numbers y0, y1, y2, ..., the sums of prefixes (running totals) of the input sequence: y0 = x0y1 = x0 + x1y2 = x0 + x1+ x2... For instance, the prefix sums of the natural numbers are the triangular numbers: Abstractly, a prefix sum requires only a binary associative operator ⊕, making it useful for many applications from calculating well-separated pair decompositions of points to string processing. (en)
- В информатике префиксная сумма, кумулятивная сумма, инклюзивное сканирование или просто сканирование последовательности чисел x0, x1, x2, … называется последовательность чисел y0, y1, y2, …, являющаяся префиксной суммой от входной последовательности: y0 = x0y1 = x0 + x1y2 = x0 + x1+ x2… Например, префиксными суммами натуральных чисел являются треугольные числа: Теоретически, префиксная сумма требует только , что делает ее полезной во многих алгоритмах: от вычисления точек до обработки строк. (ru)
|
