Приложение 2 - История изменений

ASA: Полностью удалено содержимое страницы

2015-09-17T08:07:14Z

Полностью удалено содержимое страницы

← Предыдущая версия		Версия от 08:07, 17 сентября 2015
Строка 1:		Строка 1:
	~~= Нахождение суммы элементов массива сдваиванием =~~

	~~== Свойства и структура алгоритма ==~~

	~~=== Общее описание алгоритма ===~~

	'''Метод сдваивания''' используется в качестве быстрого варианта вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря как наименьшей из возможных высоте алгортима, так и из-за ряда своих вычислительных характеристик, а также (в среде нечисленных алгоритмов) из-за своей рекурсивности, то есть лёгкости записи.

	~~=== Математическое описание алгоритма ===~~

	~~Исходные данные: одномерный массив <math>n</math> чисел.~~

	~~Вычисляемые данные: сумма элементов массива.~~

	Формулы метода: элементы на каждом этапе алгоритма разбиваются на пары. В каждой из пар находится сумма составляющих её элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д.

	~~=== Вычислительное ядро алгоритма ===~~

	Вычислительное ядро последовательно-параллельного метода суммирования можно составить как из элементарных бинарных (всего <math>n - 1</math>) вычислений сумм, так и (рекуррентно) из набора реализаций метода сдваивания меньших размерностей.

	~~=== Макроструктура алгоритма ===~~

	Как уже записано в описании ядра алгоритма, основную часть метода составляют рекурсивные вызовы сумм массивов меньшей размерности.

	~~=== Схема реализации последовательного алгоритма ===~~

	В своём чистом виде суммирование сдваиванием редко используют при последовательной реализации, поскольку при этом усложняется общая схема алгоритма и резко растёт потребность в памяти, нужной для хранения промежуточных данных.

	~~=== Последовательная сложность алгоритма ===~~

	Для вычисления суммы массива, состоящего из <math>N</math> элементов, при любых разложениях <math>N</math> на пары суть алгоритма сводится к простому переставлению скобок в формуле суммирования, и количество операций неизменно и равно <math>N - 1</math>. Поэтому алгоритм должен быть отнесён к алгоритмам ''линейной сложности'' по количеству последовательных операций.

	~~=== Информационный граф ===~~

	~~На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 16 элементов массива.~~
	~~Вершины, соответствующие входным данным, даны синим цветом, выходным данным - красным цветом.~~

	~~[[file:binary-tree-based summation graph.png\|center\|thumb\|500px\|Рисунок 1. Суммирование массива методом сдваивания]]~~

	~~=== Ресурс параллелизма алгоритма ===~~

	Для суммирования массива порядка <math>n</math> методом сдваивания в параллельном варианте требуется последовательно выполнить <math>\lceil \log_2 n \rceil</math> ярусов с убывающим (от <math>\frac{n}{2}</math> до <math>1</math>) количеством операций суммирования.
	При классификации по высоте ЯПФ, таким образом, метод сдваивания относится к алгоритмам с ''логарифмической сложностью''. При классификации по ширине ЯПФ его сложность будет ''линейной''.

	~~=== Входные и выходные данные алгоритма ===~~

	~~Входные данные: массив <math>x</math> (элементы <math>x_i</math>).~~

	~~Дополнительные ограничения: отсутствуют.~~

	~~Объём входных данных: <nowiki/><math>N</math>.~~

	~~Выходные данные: сумма элементов массива.~~

	~~Объём выходных данных: один скаляр.~~

	~~=== Свойства алгоритма ===~~

	Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является <math>\frac{n}{\log_2 n}</math> (отношение линейной к логарифмической). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм полностью детерминирован. Дуги информационного графа нелокальны, от яруса к ярусу наблюдается показательный рост их длины, при любом размещении вершин графа.

	~~== Литература ==~~
	~~<references />~~

ASA в 08:06, 17 сентября 2015

2015-09-17T08:06:40Z

← Предыдущая версия	Версия от 08:06, 17 сентября 2015
Строка 1:	Строка 1:
		= Нахождение суммы элементов массива сдваиванием =

		== Свойства и структура алгоритма ==

		=== Общее описание алгоритма ===

		'''Метод сдваивания''' используется в качестве быстрого варианта вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря как наименьшей из возможных высоте алгортима, так и из-за ряда своих вычислительных характеристик, а также (в среде нечисленных алгоритмов) из-за своей рекурсивности, то есть лёгкости записи.

		=== Математическое описание алгоритма ===

		Исходные данные: одномерный массив <math>n</math> чисел.

		Вычисляемые данные: сумма элементов массива.

		Формулы метода: элементы на каждом этапе алгоритма разбиваются на пары. В каждой из пар находится сумма составляющих её элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д.

		=== Вычислительное ядро алгоритма ===

		Вычислительное ядро последовательно-параллельного метода суммирования можно составить как из элементарных бинарных (всего <math>n - 1</math>) вычислений сумм, так и (рекуррентно) из набора реализаций метода сдваивания меньших размерностей.

		=== Макроструктура алгоритма ===

		Как уже записано в описании ядра алгоритма, основную часть метода составляют рекурсивные вызовы сумм массивов меньшей размерности.

		=== Схема реализации последовательного алгоритма ===

		В своём чистом виде суммирование сдваиванием редко используют при последовательной реализации, поскольку при этом усложняется общая схема алгоритма и резко растёт потребность в памяти, нужной для хранения промежуточных данных.

		=== Последовательная сложность алгоритма ===

		Для вычисления суммы массива, состоящего из <math>N</math> элементов, при любых разложениях <math>N</math> на пары суть алгоритма сводится к простому переставлению скобок в формуле суммирования, и количество операций неизменно и равно <math>N - 1</math>. Поэтому алгоритм должен быть отнесён к алгоритмам ''линейной сложности'' по количеству последовательных операций.

		=== Информационный граф ===

		На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 16 элементов массива.
		Вершины, соответствующие входным данным, даны синим цветом, выходным данным - красным цветом.

		[[file:binary-tree-based summation graph.png\|center\|thumb\|500px\|Рисунок 1. Суммирование массива методом сдваивания]]

		=== Ресурс параллелизма алгоритма ===

		Для суммирования массива порядка <math>n</math> методом сдваивания в параллельном варианте требуется последовательно выполнить <math>\lceil \log_2 n \rceil</math> ярусов с убывающим (от <math>\frac{n}{2}</math> до <math>1</math>) количеством операций суммирования.
		При классификации по высоте ЯПФ, таким образом, метод сдваивания относится к алгоритмам с ''логарифмической сложностью''. При классификации по ширине ЯПФ его сложность будет ''линейной''.

		=== Входные и выходные данные алгоритма ===

		Входные данные: массив <math>x</math> (элементы <math>x_i</math>).

		Дополнительные ограничения: отсутствуют.

		Объём входных данных: <nowiki/><math>N</math>.

		Выходные данные: сумма элементов массива.

		Объём выходных данных: один скаляр.

		=== Свойства алгоритма ===

		Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является <math>\frac{n}{\log_2 n}</math> (отношение линейной к логарифмической). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм полностью детерминирован. Дуги информационного графа нелокальны, от яруса к ярусу наблюдается показательный рост их длины, при любом размещении вершин графа.

		== Литература ==
		<references />

ASA: Полностью удалено содержимое страницы

2015-09-16T13:56:50Z

Полностью удалено содержимое страницы

← Предыдущая версия		Версия от 13:56, 16 сентября 2015
Строка 1:		Строка 1:
	~~= Нахождение суммы элементов массива сдваиванием =~~

	~~== Свойства и структура алгоритма ==~~

	~~=== Общее описание алгоритма ===~~

	'''Метод сдваивания''' используется в качестве быстрого варианта вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря как наименьшей из возможных высоте алгортима, так и из-за ряда своих вычислительных характеристик, а также (в среде нечисленных алгоритмов) из-за своей рекурсивности, то есть лёгкости записи.

	~~=== Математическое описание алгоритма ===~~

	~~Исходные данные: одномерный массив <math>n</math> чисел.~~

	~~Вычисляемые данные: сумма элементов массива.~~

	Формулы метода: элементы на каждом этапе алгоритма разбиваются на пары. В каждой из пар находится сумма составляющих её элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д.

	~~=== Вычислительное ядро алгоритма ===~~

	Вычислительное ядро последовательно-параллельного метода суммирования можно составить как из элементарных бинарных (всего <math>n - 1</math>) вычислений сумм, так и (рекуррентно) из набора реализаций метода сдваивания меньших размерностей.

	~~=== Макроструктура алгоритма ===~~

	Как уже записано в описании ядра алгоритма, основную часть метода составляют рекурсивные вызовы сумм массивов меньшей размерности.

	~~=== Схема реализации последовательного алгоритма ===~~

	В своём чистом виде суммирование сдваиванием редко используют при последовательной реализации, поскольку при этом усложняется общая схема алгоритма и резко растёт потребность в памяти, нужной для хранения промежуточных данных.

	~~=== Последовательная сложность алгоритма ===~~

	Для вычисления суммы массива, состоящего из <math>N</math> элементов, при любых разложениях <math>N</math> на пары суть алгоритма сводится к простому переставлению скобок в формуле суммирования, и количество операций неизменно и равно <math>N - 1</math>. Поэтому алгоритм должен быть отнесён к алгоритмам ''линейной сложности'' по количеству последовательных операций.

	~~=== Информационный граф ===~~

	~~На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 16 элементов массива.~~
	~~Вершины, соответствующие входным данным, даны синим цветом, выходным данным - красным цветом.~~

	~~[[file:binary-tree-based summation graph.png\|center\|thumb\|500px\|Рисунок 1. Суммирование массива методом сдваивания]]~~

	~~=== Ресурс параллелизма алгоритма ===~~

	Для суммирования массива порядка <math>n</math> методом сдваивания в параллельном варианте требуется последовательно выполнить <math>\lceil \log_2 n \rceil</math> ярусов с убывающим (от <math>\frac{n}{2}</math> до <math>1</math>) количеством операций суммирования.
	При классификации по высоте ЯПФ, таким образом, метод сдваивания относится к алгоритмам с ''логарифмической сложностью''. При классификации по ширине ЯПФ его сложность будет ''линейной''.

	~~=== Входные и выходные данные алгоритма ===~~

	~~Входные данные: массив <math>x</math> (элементы <math>x_i</math>).~~

	~~Дополнительные ограничения: отсутствуют.~~

	~~Объём входных данных: <nowiki/><math>N</math>.~~

	~~Выходные данные: сумма элементов массива.~~

	~~Объём выходных данных: один скаляр.~~

	~~=== Свойства алгоритма ===~~

	Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является <math>\frac{n}{\log_2 n}</math> (отношение линейной к логарифмической). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм полностью детерминирован. Дуги информационного графа нелокальны, от яруса к ярусу наблюдается показательный рост их длины, при любом размещении вершин графа.

	~~== Литература ==~~
	~~<references />~~

ASA в 13:56, 16 сентября 2015

2015-09-16T13:56:06Z

← Предыдущая версия	Версия от 13:56, 16 сентября 2015
Строка 1:	Строка 1:
		= Нахождение суммы элементов массива сдваиванием =

		== Свойства и структура алгоритма ==

		=== Общее описание алгоритма ===

		'''Метод сдваивания''' используется в качестве быстрого варианта вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря как наименьшей из возможных высоте алгортима, так и из-за ряда своих вычислительных характеристик, а также (в среде нечисленных алгоритмов) из-за своей рекурсивности, то есть лёгкости записи.

		=== Математическое описание алгоритма ===

		Исходные данные: одномерный массив <math>n</math> чисел.

		Вычисляемые данные: сумма элементов массива.

		Формулы метода: элементы на каждом этапе алгоритма разбиваются на пары. В каждой из пар находится сумма составляющих её элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д.

		=== Вычислительное ядро алгоритма ===

		Вычислительное ядро последовательно-параллельного метода суммирования можно составить как из элементарных бинарных (всего <math>n - 1</math>) вычислений сумм, так и (рекуррентно) из набора реализаций метода сдваивания меньших размерностей.

		=== Макроструктура алгоритма ===

		Как уже записано в описании ядра алгоритма, основную часть метода составляют рекурсивные вызовы сумм массивов меньшей размерности.

		=== Схема реализации последовательного алгоритма ===

		В своём чистом виде суммирование сдваиванием редко используют при последовательной реализации, поскольку при этом усложняется общая схема алгоритма и резко растёт потребность в памяти, нужной для хранения промежуточных данных.

		=== Последовательная сложность алгоритма ===

		Для вычисления суммы массива, состоящего из <math>N</math> элементов, при любых разложениях <math>N</math> на пары суть алгоритма сводится к простому переставлению скобок в формуле суммирования, и количество операций неизменно и равно <math>N - 1</math>. Поэтому алгоритм должен быть отнесён к алгоритмам ''линейной сложности'' по количеству последовательных операций.

		=== Информационный граф ===

		На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 16 элементов массива.
		Вершины, соответствующие входным данным, даны синим цветом, выходным данным - красным цветом.

		[[file:binary-tree-based summation graph.png\|center\|thumb\|500px\|Рисунок 1. Суммирование массива методом сдваивания]]

		=== Ресурс параллелизма алгоритма ===

		Для суммирования массива порядка <math>n</math> методом сдваивания в параллельном варианте требуется последовательно выполнить <math>\lceil \log_2 n \rceil</math> ярусов с убывающим (от <math>\frac{n}{2}</math> до <math>1</math>) количеством операций суммирования.
		При классификации по высоте ЯПФ, таким образом, метод сдваивания относится к алгоритмам с ''логарифмической сложностью''. При классификации по ширине ЯПФ его сложность будет ''линейной''.

		=== Входные и выходные данные алгоритма ===

		Входные данные: массив <math>x</math> (элементы <math>x_i</math>).

		Дополнительные ограничения: отсутствуют.

		Объём входных данных: <nowiki/><math>N</math>.

		Выходные данные: сумма элементов массива.

		Объём выходных данных: один скаляр.

		=== Свойства алгоритма ===

		Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является <math>\frac{n}{\log_2 n}</math> (отношение линейной к логарифмической). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм полностью детерминирован. Дуги информационного графа нелокальны, от яруса к ярусу наблюдается показательный рост их длины, при любом размещении вершин графа.

		== Литература ==
		<references />

ASA: Полностью удалено содержимое страницы

2015-09-11T07:58:37Z

Полностью удалено содержимое страницы

← Предыдущая версия		Версия от 07:58, 11 сентября 2015
Строка 1:		Строка 1:
	~~= Нахождение суммы элементов массива сдваиванием =~~

	~~== Свойства и структура алгоритма ==~~

	~~=== Общее описание алгоритма ===~~

	'''Метод сдваивания''' используется в качестве быстрого варианта вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря как наименьшей из возможных высоте алгортима, так и из-за ряда своих вычислительных характеристик, а также (в среде нечисленных алгоритмов) из-за своей рекурсивности, то есть лёгкости записи.

	~~=== Математическое описание алгоритма ===~~

	~~Исходные данные: одномерный массив <math>n</math> чисел.~~

	~~Вычисляемые данные: сумма элементов массива.~~

	Формулы метода: элементы на каждом этапе алгоритма разбиваются на пары. В каждой из пар находится сумма составляющих её элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д.

	~~=== Вычислительное ядро алгоритма ===~~

	Вычислительное ядро последовательно-параллельного метода суммирования можно составить как из элементарных бинарных (всего <math>n - 1</math>) вычислений сумм, так и (рекуррентно) из набора реализаций метода сдваивания меньших размерностей.

	~~=== Макроструктура алгоритма ===~~

	Как уже записано в описании ядра алгоритма, основную часть метода составляют рекурсивные вызовы сумм массивов меньшей размерности.

	~~=== Схема реализации последовательного алгоритма ===~~

	В своём чистом виде суммирование сдваиванием редко используют при последовательной реализации, поскольку при этом усложняется общая схема алгоритма и резко растёт потребность в памяти, нужной для хранения промежуточных данных.

	~~=== Последовательная сложность алгоритма ===~~

	Для вычисления суммы массива, состоящего из <math>N</math> элементов, при любых разложениях <math>N</math> на пары суть алгоритма сводится к простому переставлению скобок в формуле суммирования, и количество операций неизменно и равно <math>N - 1</math>. Поэтому алгоритм должен быть отнесён к алгоритмам ''линейной сложности'' по количеству последовательных операций.

	~~=== Информационный граф ===~~

	~~На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 16 элементов массива.~~
	~~Вершины, соответствующие входным данным, даны синим цветом, выходным данным - красным цветом.~~

	~~[[file:binary-tree-based summation graph.png\|center\|thumb\|500px\|Рисунок 1. Суммирование массива методом сдваивания]]~~

	~~=== Ресурс параллелизма алгоритма ===~~

	Для суммирования массива порядка <math>n</math> методом сдваивания в параллельном варианте требуется последовательно выполнить <math>\lceil \log_2 n \rceil</math> ярусов с убывающим (от <math>\frac{n}{2}</math> до <math>1</math>) количеством операций суммирования.
	При классификации по высоте ЯПФ, таким образом, метод сдваивания относится к алгоритмам с ''логарифмической сложностью''. При классификации по ширине ЯПФ его сложность будет ''линейной''.

	~~=== Входные и выходные данные алгоритма ===~~

	~~Входные данные: массив <math>x</math> (элементы <math>x_i</math>).~~

	~~Дополнительные ограничения: отсутствуют.~~

	~~Объём входных данных: <nowiki/><math>N</math>.~~

	~~Выходные данные: сумма элементов массива.~~

	~~Объём выходных данных: один скаляр.~~

	~~=== Свойства алгоритма ===~~

	Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является <math>\frac{n}{\log_2 n}</math> (отношение линейной к логарифмической). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм полностью детерминирован. Дуги информационного графа нелокальны, от яруса к ярусу наблюдается показательный рост их длины, при любом размещении вершин графа.

	~~== Литература ==~~
	~~<references />~~

ASA: Новая страница: «= Нахождение суммы элементов массива сдваиванием = == Свойства и структура алгоритма == ===…»

2015-09-11T07:57:24Z

Новая страница: «= Нахождение суммы элементов массива сдваиванием = == Свойства и структура алгоритма == ===…»

Новая страница

= Нахождение суммы элементов массива сдваиванием =

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

'''Метод сдваивания''' используется в качестве быстрого варианта вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря как наименьшей из возможных высоте алгортима, так и из-за ряда своих вычислительных характеристик, а также (в среде нечисленных алгоритмов) из-за своей рекурсивности, то есть лёгкости записи.

=== Математическое описание алгоритма ===

Исходные данные: одномерный массив <math>n</math> чисел.

Вычисляемые данные: сумма элементов массива.

Формулы метода: элементы на каждом этапе алгоритма разбиваются на пары. В каждой из пар находится сумма составляющих её элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д.

=== Вычислительное ядро алгоритма ===

Вычислительное ядро последовательно-параллельного метода суммирования можно составить как из элементарных бинарных (всего <math>n - 1</math>) вычислений сумм, так и (рекуррентно) из набора реализаций метода сдваивания меньших размерностей.

=== Макроструктура алгоритма ===

Как уже записано в описании ядра алгоритма, основную часть метода составляют рекурсивные вызовы сумм массивов меньшей размерности.

=== Схема реализации последовательного алгоритма ===

В своём чистом виде суммирование сдваиванием редко используют при последовательной реализации, поскольку при этом усложняется общая схема алгоритма и резко растёт потребность в памяти, нужной для хранения промежуточных данных.

=== Последовательная сложность алгоритма ===

Для вычисления суммы массива, состоящего из <math>N</math> элементов, при любых разложениях <math>N</math> на пары суть алгоритма сводится к простому переставлению скобок в формуле суммирования, и количество операций неизменно и равно <math>N - 1</math>. Поэтому алгоритм должен быть отнесён к алгоритмам ''линейной сложности'' по количеству последовательных операций.

=== Информационный граф ===

На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 16 элементов массива.
Вершины, соответствующие входным данным, даны синим цветом, выходным данным - красным цветом.

[[file:binary-tree-based summation graph.png|center|thumb|500px|Рисунок 1. Суммирование массива методом сдваивания]]

=== Ресурс параллелизма алгоритма ===

Для суммирования массива порядка <math>n</math> методом сдваивания в параллельном варианте требуется последовательно выполнить <math>\lceil \log_2 n \rceil</math> ярусов с убывающим (от <math>\frac{n}{2}</math> до <math>1</math>) количеством операций суммирования.
При классификации по высоте ЯПФ, таким образом, метод сдваивания относится к алгоритмам с ''логарифмической сложностью''. При классификации по ширине ЯПФ его сложность будет ''линейной''.

=== Входные и выходные данные алгоритма ===

Входные данные: массив <math>x</math> (элементы <math>x_i</math>).

Дополнительные ограничения: отсутствуют.

Объём входных данных: <nowiki/><math>N</math>.

Выходные данные: сумма элементов массива.

Объём выходных данных: один скаляр.

=== Свойства алгоритма ===

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является <math>\frac{n}{\log_2 n}</math> (отношение линейной к логарифмической). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм полностью детерминирован. Дуги информационного графа нелокальны, от яруса к ярусу наблюдается показательный рост их длины, при любом размещении вершин графа.

== Литература ==
<references />