Участница:Александра/Метод встречи посередине - История изменений

ASA в 14:24, 19 декабря 2016

2016-12-19T14:24:30Z

← Предыдущая версия		Версия от 14:24, 19 декабря 2016
Строка 1:		Строка 1:
	~~{{Assignment\|Algoman}}~~
	{{Assignment\|Algoman\|Konshin}}		{{Assignment\|Algoman\|Konshin}}

Konshin в 14:33, 9 декабря 2016

2016-12-09T14:33:09Z

← Предыдущая версия		Версия от 14:33, 9 декабря 2016
Строка 1:		Строка 1:
	{{Assignment\|Algoman}}		{{Assignment\|Algoman}}
			{{Assignment\|Algoman\|Konshin}}


	{{algorithm		{{algorithm
	\| name = Метод встречи посередине		\| name = Метод встречи посередине

Александра: /* Масштабируемость алгоритма и его реализации */

2016-12-07T18:55:26Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 18:55, 7 декабря 2016
Строка 144:		Строка 144:
	[[File:Масштабируемость.jpg\|thumb\|center\|900px\|Рисунок 2. Масштабируемость реализации алгоритма]]		[[File:Масштабируемость.jpg\|thumb\|center\|900px\|Рисунок 2. Масштабируемость реализации алгоритма]]

	Как видно из графика, производительность почти не изменяется в зависимости от размера задачи, в ~~то время как зависимость производительности~~ от числа ядер ~~визуально близка к линейной~~. ~~Это связано с тем~~, что алгоритм содержит большое количество независимых операций опробования ключа, синхронизация между параллельно выполняющимися опробованиями не требуется.		Как видно из графика, производительность почти не изменяется в зависимости от размера задачи и возрастает в зависимости от числа ядер. Росту производительности способствует то, что алгоритм содержит большое количество независимых операций опробования ключа, синхронизация между параллельно выполняющимися опробованиями не требуется.

	[https://github.com/AlBatarina/Super2016/blob/master/meet_in_the_middle/meet.c Исследованная параллельная реализация на языке C]		[https://github.com/AlBatarina/Super2016/blob/master/meet_in_the_middle/meet.c Исследованная параллельная реализация на языке C]

Александра в 18:50, 7 декабря 2016

2016-12-07T18:50:11Z

← Предыдущая версия		Версия от 18:50, 7 декабря 2016
Строка 82:		Строка 82:
	2. Объединение таблиц и их сортировка будет иметь сложность <math>O((\|K_1\|+\|K_2\|)\log(\|K_1\|+\|K_2\|))</math> (например, при сортировке слиянием).		2. Объединение таблиц и их сортировка будет иметь сложность <math>O((\|K_1\|+\|K_2\|)\log(\|K_1\|+\|K_2\|))</math> (например, при сортировке слиянием).

	3. Сложность бинарного поиска в отсортированном массиве — <math>O(log_2(\|K_1\|))</math> для каждого поиска		3. Сложность бинарного поиска в отсортированном массиве — <math>O(\log_2(\|K_1\|))</math> для каждого поиска

	4. Сложность поиска в достаточно большой хэш-таблице составит <math>O(1)</math> для каждого поиска		4. Сложность поиска в достаточно большой хэш-таблице составит <math>O(1)</math> для каждого поиска
Строка 90:		Строка 90:
	1. С генерацией двух таблиц — <math>O(\|K_1\|+\|K_2\|) + O((\|K_1\|+\|K_2\|)\log(\|K_1\|+\|K_2\|)) + O(\|K_1\|+\|K_2\|)=O((\|K_1\|+\|K_2\|)\log(\|K_1\|+\|K_2\|))</math>		1. С генерацией двух таблиц — <math>O(\|K_1\|+\|K_2\|) + O((\|K_1\|+\|K_2\|)\log(\|K_1\|+\|K_2\|)) + O(\|K_1\|+\|K_2\|)=O((\|K_1\|+\|K_2\|)\log(\|K_1\|+\|K_2\|))</math>

	2. C генерацией одной таблицы, сортировкой и бинарным поиском — <math>O(\|K_1\|) + O((\|K_1\|)\log(\|K_1\|)) + O(\|K_2\|\log_2(\|K_1\|))=O(max(\|K_1\|,\|K_2\|)\log(\|K_1\|))</math>		2. C генерацией одной таблицы, сортировкой и бинарным поиском — <math>O(\|K_1\|) + O((\|K_1\|)\log(\|K_1\|)) + O(\|K_2\|\log_2(\|K_1\|))=O(\max(\|K_1\|,\|K_2\|)\log(\|K_1\|))</math>

	3. C генерацией одной (достаточно большой) хэш-таблицы — <math>O(\|K_1\|) + O(\|K_2\|)=O(\|K_1\|+\|K_2\|)</math>		3. C генерацией одной (достаточно большой) хэш-таблицы — <math>O(\|K_1\|) + O(\|K_2\|)=O(\|K_1\|+\|K_2\|)</math>

Algoman в 11:54, 22 ноября 2016

2016-11-22T11:54:07Z

← Предыдущая версия		Версия от 11:54, 22 ноября 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment\|Algoman}}
	{{algorithm		{{algorithm
	\| name = Метод встречи посередине		\| name = Метод встречи посередине
Строка 138:		Строка 138:

	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	~~==== Масштабируемость алгоритма ====~~
	~~==== Масштабируемость реализации алгоритма ====~~
	Исследование масштабируемости реализации алгоритма проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета]. Изменяемые параметры запуска:		Исследование масштабируемости реализации алгоритма проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета]. Изменяемые параметры запуска:
	* Размер ключа – от 8 до 20 бит с шагом 1		* Размер ключа – от 8 до 20 бит с шагом 1

Александра в 19:43, 21 ноября 2016

2016-11-21T19:43:38Z

← Предыдущая версия		Версия от 19:43, 21 ноября 2016
Строка 1:		Строка 1:
			{{Assignment}}
	{{algorithm		{{algorithm
	\| name = Метод встречи посередине		\| name = Метод встречи посередине

Александра: /* Масштабируемость реализации алгоритма */

2016-11-21T19:33:45Z

Масштабируемость реализации алгоритма

← Предыдущая версия		Версия от 19:33, 21 ноября 2016
Строка 142:		Строка 142:
	* Размер ключа – от 8 до 20 бит с шагом 1		* Размер ключа – от 8 до 20 бит с шагом 1
	* Число ядер – от 1 до 8 (значения являются степенью числа 2)		* Число ядер – от 1 до 8 (значения являются степенью числа 2)
	Ниже представлен график зависимости [[Глоссарий#Производительность\|производительности]] от числа ядер и размера ключа (размер задачи – экспоненциальная функция от размера ключа). Для измерения производительности качестве базовой операции используется операция опробования ключа и время в секундах. Количество арифметических операций, содержащихся в операции опробования, может быть разным в зависимости от используемого алгоритма шифрования.		Ниже представлен график зависимости [[Глоссарий#Производительность\|производительности]] от числа ядер и размера ключа (размер задачи – экспоненциальная функция от размера ключа). Для измерения производительности в качестве базовой операции используется операция опробования ключа и время в секундах. Количество арифметических операций, содержащихся в операции опробования, может быть разным в зависимости от используемого алгоритма шифрования.
	[[File:Масштабируемость.jpg\|thumb\|center\|900px\|Рисунок 2. Масштабируемость реализации алгоритма]]		[[File:Масштабируемость.jpg\|thumb\|center\|900px\|Рисунок 2. Масштабируемость реализации алгоритма]]

Александра: /* Масштабируемость реализации алгоритма */

2016-11-21T19:33:09Z

Масштабируемость реализации алгоритма

← Предыдущая версия		Версия от 19:33, 21 ноября 2016
Строка 142:		Строка 142:
	* Размер ключа – от 8 до 20 бит с шагом 1		* Размер ключа – от 8 до 20 бит с шагом 1
	* Число ядер – от 1 до 8 (значения являются степенью числа 2)		* Число ядер – от 1 до 8 (значения являются степенью числа 2)
	Ниже представлен график зависимости [[Глоссарий#Производительность\|производительности]] от числа ядер и размера ключа (размер задачи – экспоненциальная функция от размера ключа).		Ниже представлен график зависимости [[Глоссарий#Производительность\|производительности]] от числа ядер и размера ключа (размер задачи – экспоненциальная функция от размера ключа). Для измерения производительности качестве базовой операции используется операция опробования ключа и время в секундах. Количество арифметических операций, содержащихся в операции опробования, может быть разным в зависимости от используемого алгоритма шифрования.
	[[File:Масштабируемость.jpg\|thumb\|center\|900px\|Рисунок 2. Масштабируемость реализации алгоритма]]		[[File:Масштабируемость.jpg\|thumb\|center\|900px\|Рисунок 2. Масштабируемость реализации алгоритма]]

Algoman в 13:24, 16 ноября 2016

2016-11-16T13:24:17Z

← Предыдущая версия		Версия от 13:24, 16 ноября 2016
Строка 1:		Строка 1:
	~~{{Assignment\|Algoman}}~~

	{{algorithm		{{algorithm
	\| name = Метод встречи посередине		\| name = Метод встречи посередине

Александра: Исправила опечатку

2016-11-06T17:55:39Z

Исправила опечатку

← Предыдущая версия		Версия от 17:55, 6 ноября 2016
Строка 6:		Строка 6:
	\| pf_height = <math>O(1)</math>		\| pf_height = <math>O(1)</math>
	\| pf_width = <math>O(n)</math>		\| pf_width = <math>O(n)</math>
	\| input_data = <math>O(n)</math>		\| input_data = <math>O(\log(n))</math>
	\| output_data = <math>n</math>		\| output_data = <math>\log(n)</math>
	}}		}}

← Предыдущая версия		Версия от 18:50, 7 декабря 2016
Строка 82:		Строка 82:
	2. Объединение таблиц и их сортировка будет иметь сложность <math>O((\|K_1\|+\|K_2\|)\log(\|K_1\|+\|K_2\|))</math> (например, при сортировке слиянием).		2. Объединение таблиц и их сортировка будет иметь сложность <math>O((\|K_1\|+\|K_2\|)\log(\|K_1\|+\|K_2\|))</math> (например, при сортировке слиянием).

	3. Сложность бинарного поиска в отсортированном массиве — <math>O(log_2(\|K_1\|))</math> для каждого поиска		3. Сложность бинарного поиска в отсортированном массиве — <math>O(\log_2(\|K_1\|))</math> для каждого поиска

	4. Сложность поиска в достаточно большой хэш-таблице составит <math>O(1)</math> для каждого поиска		4. Сложность поиска в достаточно большой хэш-таблице составит <math>O(1)</math> для каждого поиска
Строка 90:		Строка 90:
	1. С генерацией двух таблиц — <math>O(\|K_1\|+\|K_2\|) + O((\|K_1\|+\|K_2\|)\log(\|K_1\|+\|K_2\|)) + O(\|K_1\|+\|K_2\|)=O((\|K_1\|+\|K_2\|)\log(\|K_1\|+\|K_2\|))</math>		1. С генерацией двух таблиц — <math>O(\|K_1\|+\|K_2\|) + O((\|K_1\|+\|K_2\|)\log(\|K_1\|+\|K_2\|)) + O(\|K_1\|+\|K_2\|)=O((\|K_1\|+\|K_2\|)\log(\|K_1\|+\|K_2\|))</math>

	2. C генерацией одной таблицы, сортировкой и бинарным поиском — <math>O(\|K_1\|) + O((\|K_1\|)\log(\|K_1\|)) + O(\|K_2\|\log_2(\|K_1\|))=O(max(\|K_1\|,\|K_2\|)\log(\|K_1\|))</math>		2. C генерацией одной таблицы, сортировкой и бинарным поиском — <math>O(\|K_1\|) + O((\|K_1\|)\log(\|K_1\|)) + O(\|K_2\|\log_2(\|K_1\|))=O(\max(\|K_1\|,\|K_2\|)\log(\|K_1\|))</math>

	3. C генерацией одной (достаточно большой) хэш-таблицы — <math>O(\|K_1\|) + O(\|K_2\|)=O(\|K_1\|+\|K_2\|)</math>		3. C генерацией одной (достаточно большой) хэш-таблицы — <math>O(\|K_1\|) + O(\|K_2\|)=O(\|K_1\|+\|K_2\|)</math>