Структура описания свойств алгоритмов - История изменений

ASA в 10:32, 4 декабря 2024

2024-12-04T10:32:04Z

← Предыдущая версия		Версия от 10:32, 4 декабря 2024
Строка 97:		Строка 97:

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

			=== Возможные способы и особенности параллельной реализации алгоритма ===
			Раздел довольно обширный, в котором должны быть описаны основные факты и положения, формирующие параллельную программу. К их числу можно отнести:
			* представленный иерархически ресурс параллелизма, опирающийся на структуру циклических конструкций и на граф вызовов программы;
			* комбинацию (иерархию) массового параллелизма и параллелизма конечного;
			* возможные способы распределения операций между процессами/нитями;
			* возможные способы распределения данных;
			* оценку количества операций, объёма и числа пересылок данных (как общего числа, так и в пересчёте на каждый параллельный процесс);

			и другие.

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

	=== Результаты прогонов ===		=== Результаты прогонов ===

ASA в 10:28, 4 декабря 2024

2024-12-04T10:28:12Z

@@ Строка 98: / Строка 98: @@
 С этой же точки зрения, в данном разделе весьма полезны соображения по реализации алгоритма на различных параллельных вычислительных платформах. Высокопроизводительные кластеры, многоядерные узлы, возможности для векторизации или использования ускорителей - особенности этих архитектур не только опираются на разные свойства алгоритмов, но и по-разному должны быть выражены в программах, что также желательно описать в данном разделе.
-=== Локальность данных и вычислений ===
+=== Результаты прогонов ===
-Отдельно приводятся профили взаимодействия с памятью для вычислительных ядер и ключевых фрагментов. Если из-за большого числа обращений по общему профилю сложно понять реальную специфику взаимодействия программ с памятью, то проводится последовательная детализация и приводится серия профилей более мелкого масштаба.
+В данном разделе суммируются результаты прогонов всех программных реализаций данного алгоритма на различных программно-аппаратных платформах.
 === Выводы для классов архитектур ===
@@ Строка 139: / Строка 106: @@
 На практике это сделать можно по-разному: либо все свести в один текущий раздел, либо же соответствующие факты сразу включать в предшествующие разделы, где они обсуждаются и необходимы по смыслу. В некоторых случаях, имеет смысл делать отдельные варианты всей [[#ЧАСТЬ. Программная реализация алгоритмов|части II]] AlgoWiki применительно к отдельным классам архитектур, оставляя общей машинно-независимую [[#ЧАСТЬ. Свойства и структура алгоритмов|часть I]]. В любом случае, важно указать и позитивные, и негативные факты по отношению к конкретным классам. Можно говорить о возможных вариантах оптимизации или даже о "трюках" в написании программ, ориентированных на целевые классы архитектур.
 == Литература ==

ASA в 15:08, 24 октября 2017

2017-10-24T15:08:55Z

← Предыдущая версия		Версия от 15:08, 24 октября 2017
Строка 1:		Строка 1:
			Данный документ содержит описание схемы, по которой предлагается описывать свойства и структуру каждого алгоритма. Описание состоит из двух частей. В [[#ЧАСТЬ. Свойства и структура алгоритмов\|первой части]] описываются собственно алгоритмы и их свойства, а [[#ЧАСТЬ. Программная реализация алгоритмов\|вторая]] посвящена описанию особенностей их программной реализации с учетом конкретных программно-аппаратных платформ. Такое деление на части сделано для того, чтобы машинно-независимые свойства алгоритмов, которые определяют качество их реализации на параллельных вычислительных системах, были бы выделены и описаны отдельно от множества вопросов, связанных с последующими этапами программирования алгоритмов и исполнения результирующих программ.

			Общая схема описания алгоритмов имеет следующий вид:

	== Свойства и структура алгоритмов ==		== Свойства и структура алгоритмов ==
			Свойства алгоритмов никак не зависят от вычислительных систем, и с этой точки зрения данная часть AlgoWiki имеет безусловную собственную ценность. Описание алгоритма делается один раз, после чего многократно используется для его реализации в различных программно-аппаратных средах. Несмотря на то, что в данной части мы рассматриваем лишь машинно-независимые свойства алгоритмов, соображения, важные на этапе реализации, или же ссылки на соответствующие пункты [[#ЧАСТЬ. Программная реализация алгоритмов\|части II AlgoWiki]], здесь также вполне уместны.

	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
	~~EM-алгоритм~~ (~~англ. expectation-maximization~~) ~~- алгоритм итерационного типа~~ для ~~численного~~ решения ~~задачи поиска экстремума целевой функции в разнообразных задачах оптимизации~~. В ~~частности~~, алгоритм используется в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, ~~в случае, когда модель зависит от некоторых скрытых переменных~~. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, ~~вычисляемое на E-шаге. Затем~~ это ~~значение используется для E-шага на следующей итерации~~. ~~Алгоритм выполняется до сходимости.~~		В данном разделе представляется самый первый вариант описания тех задач (или классов задач), для решения которых предназначен алгоритм. В описании поясняются особенности как алгоритма, так и объектов, с которыми он работает. Если описание соответствует целому классу схожих по структуре алгоритмов, либо же посвящено описанию отдельного представителя некоторого класса, то это здесь указывается явно. Описываются базовые математические свойства и структура входных данных. При необходимости, в описании могут присутствовать формулы, а также даваться ссылки на описания других используемых алгоритмов. Данное описание должно быть достаточным для однозначного понимания сути решаемой задачи.


	~~Как правило, ЕМ-алгоритм применяется для решения задач двух типов.~~

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

	2. ~~Ко второму типу задач можно отнести статистические задачи~~, в ~~которых функция правдоподобия имеет вид~~, не допускающий удобных аналитических методов исследования, но допускающий серьезные упрощения, если в задачу ввести дополнительные «ненаблюдаемые» (скрытые, латентные) переменные. Примерами прикладных задач второго типа являются задачи распознавания образов, реконструкции изображений. Математическую суть данных задач составляют задачи ~~кластерного анализа, классификации и разделения смесей вероятностных распределений~~.

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===
	Задача отыскания наиболее правдоподобных оценок параметров смесей вероятностных распределений одно из самых популярных приложений ЕМ-алгоритма.		Приводится математическое описание решаемой задачи в виде совокупности формул и соотношений, как это принято в книгах и учебниках. По возможности, используются общепринятые обозначения и способы записи. Должны быть явно определены все использованные обозначения и описаны свойства входных данных. Представленное описание должно быть достаточным для однозначного понимания постановки решаемой задачи для человека, знающего математику.

	~~Базовым предположением в рамках данной~~ задачи ~~является то~~, ~~что плотность наблюдаемой случайной величины <math>X</math> имеет вид:~~
	~~$f^{X}_{\teta} = $~~

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

Victoria Evstefeeva: /* Математическое описание алгоритма */

2017-10-24T15:08:11Z

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

← Предыдущая версия		Версия от 15:08, 24 октября 2017
Строка 14:		Строка 14:
	Задача отыскания наиболее правдоподобных оценок параметров смесей вероятностных распределений одно из самых популярных приложений ЕМ-алгоритма.		Задача отыскания наиболее правдоподобных оценок параметров смесей вероятностных распределений одно из самых популярных приложений ЕМ-алгоритма.

	Базовым предположением в рамках данной задачи является то, что плотность наблюдаемой случайной величины $X$ имеет вид:		Базовым предположением в рамках данной задачи является то, что плотность наблюдаемой случайной величины <math>X</math> имеет вид:
	$f^{X}_{\teta} = $		$f^{X}_{\teta} = $

Victoria Evstefeeva: /* Математическое описание алгоритма */

2017-10-24T15:06:44Z

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

← Предыдущая версия		Версия от 15:06, 24 октября 2017
Строка 12:		Строка 12:

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===
	~~Приводится математическое описание решаемой задачи~~ в виде совокупности формул и соотношений, как это принято в книгах и учебниках. По возможности, используются общепринятые обозначения и способы записи. Должны быть явно определены все использованные обозначения и описаны свойства входных данных. Представленное описание должно быть достаточным для однозначного понимания постановки решаемой задачи ~~для человека~~, ~~знающего математику.~~		Задача отыскания наиболее правдоподобных оценок параметров смесей вероятностных распределений одно из самых популярных приложений ЕМ-алгоритма.

			Базовым предположением в рамках данной задачи является то, что плотность наблюдаемой случайной величины $X$ имеет вид:
			$f^{X}_{\teta} = $

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

Victoria Evstefeeva: /* Общее описание алгоритма */

2017-10-24T15:03:10Z

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

← Предыдущая версия		Версия от 15:03, 24 октября 2017
Строка 3:		Строка 3:
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
	EM-алгоритм (англ. expectation-maximization) - алгоритм итерационного типа для численного решения задачи поиска экстремума целевой функции в разнообразных задачах оптимизации. В частности, алгоритм используется в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости.		EM-алгоритм (англ. expectation-maximization) - алгоритм итерационного типа для численного решения задачи поиска экстремума целевой функции в разнообразных задачах оптимизации. В частности, алгоритм используется в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости.


	Как правило, ЕМ-алгоритм применяется для решения задач двух типов.		Как правило, ЕМ-алгоритм применяется для решения задач двух типов.

Victoria Evstefeeva: /* Общее описание алгоритма */

2017-10-24T15:02:34Z

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

← Предыдущая версия		Версия от 15:02, 24 октября 2017
Строка 5:		Строка 5:

	Как правило, ЕМ-алгоритм применяется для решения задач двух типов.		Как правило, ЕМ-алгоритм применяется для решения задач двух типов.

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

	2. Ко второму типу задач можно отнести статистические задачи, в которых функция правдоподобия имеет вид, не допускающий удобных аналитических методов исследования, но допускающий серьезные упрощения, если в задачу ввести дополнительные «ненаблюдаемые» (скрытые, латентные) переменные. Примерами прикладных задач второго типа являются задачи распознавания образов, реконструкции изображений. Математическую суть данных задач составляют задачи кластерного анализа, классификации и разделения смесей вероятностных распределений.		2. Ко второму типу задач можно отнести статистические задачи, в которых функция правдоподобия имеет вид, не допускающий удобных аналитических методов исследования, но допускающий серьезные упрощения, если в задачу ввести дополнительные «ненаблюдаемые» (скрытые, латентные) переменные. Примерами прикладных задач второго типа являются задачи распознавания образов, реконструкции изображений. Математическую суть данных задач составляют задачи кластерного анализа, классификации и разделения смесей вероятностных распределений.

Victoria Evstefeeva: /* Общее описание алгоритма */

2017-10-24T15:02:13Z

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

← Предыдущая версия		Версия от 15:02, 24 октября 2017
Строка 2:		Строка 2:

	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
	~~Общее описание алгоритма[[[править]]]~~ EM-алгоритм (англ. expectation-maximization) - алгоритм итерационного типа для численного решения задачи поиска экстремума целевой функции в разнообразных задачах оптимизации. В частности, алгоритм используется в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости.		EM-алгоритм (англ. expectation-maximization) - алгоритм итерационного типа для численного решения задачи поиска экстремума целевой функции в разнообразных задачах оптимизации. В частности, алгоритм используется в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости.

	Как правило, ЕМ-алгоритм применяется для решения задач двух типов. 1. К первому типу можно отнести задачи, связанные с анализом действительно неполных данных, когда некоторые статистические данные отсутствуют в силу каких-либо причин. 2. Ко второму типу задач можно отнести статистические задачи, в которых функция правдоподобия имеет вид, не допускающий удобных аналитических методов исследования, но допускающий серьезные упрощения, если в задачу ввести дополнительные «ненаблюдаемые» (скрытые, латентные) переменные. Примерами прикладных задач второго типа являются задачи распознавания образов, реконструкции изображений. Математическую суть данных задач составляют задачи кластерного анализа, классификации и разделения смесей вероятностных распределений.		Как правило, ЕМ-алгоритм применяется для решения задач двух типов.
			1. К первому типу можно отнести задачи, связанные с анализом действительно неполных данных, когда некоторые статистические данные отсутствуют в силу каких-либо причин.
			2. Ко второму типу задач можно отнести статистические задачи, в которых функция правдоподобия имеет вид, не допускающий удобных аналитических методов исследования, но допускающий серьезные упрощения, если в задачу ввести дополнительные «ненаблюдаемые» (скрытые, латентные) переменные. Примерами прикладных задач второго типа являются задачи распознавания образов, реконструкции изображений. Математическую суть данных задач составляют задачи кластерного анализа, классификации и разделения смесей вероятностных распределений.

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

Victoria Evstefeeva в 15:01, 24 октября 2017

2017-10-24T15:01:38Z

← Предыдущая версия		Версия от 15:01, 24 октября 2017
Строка 1:		Строка 1:
	== Свойства и структура алгоритмов ==		== Свойства и структура алгоритмов ==
	Свойства алгоритмов никак не зависят от вычислительных систем, и с этой точки зрения данная часть AlgoWiki имеет безусловную собственную ценность. Описание алгоритма делается один раз, после чего многократно используется для его реализации в различных программно-аппаратных средах. Несмотря на то, что в данной части мы рассматриваем лишь машинно-независимые свойства алгоритмов, соображения, важные на этапе реализации, или же ссылки на соответствующие пункты [[#ЧАСТЬ. Программная реализация алгоритмов\|части II AlgoWiki]], здесь также вполне уместны.

	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
	~~В данном разделе представляется самый первый вариант описания тех задач~~ (~~или классов задач~~), для решения ~~которых предназначен~~ алгоритм. ~~В описании поясняются особенности как~~ алгоритма, ~~так и объектов, с которыми он работает~~. ~~Если описание соответствует целому классу схожих по структуре алгоритмов~~, ~~либо же посвящено описанию отдельного представителя некоторого класса~~, то это ~~здесь указывается явно~~. ~~Описываются базовые математические свойства и структура входных~~ данных. ~~При необходимости~~, в ~~описании могут присутствовать формулы~~, ~~а также даваться ссылки на описания других используемых алгоритмов~~. ~~Данное описание должно быть достаточным для однозначного понимания сути решаемой~~ задачи.		Общее описание алгоритма[[[править]]] EM-алгоритм (англ. expectation-maximization) - алгоритм итерационного типа для численного решения задачи поиска экстремума целевой функции в разнообразных задачах оптимизации. В частности, алгоритм используется в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости.

			Как правило, ЕМ-алгоритм применяется для решения задач двух типов. 1. К первому типу можно отнести задачи, связанные с анализом действительно неполных данных, когда некоторые статистические данные отсутствуют в силу каких-либо причин. 2. Ко второму типу задач можно отнести статистические задачи, в которых функция правдоподобия имеет вид, не допускающий удобных аналитических методов исследования, но допускающий серьезные упрощения, если в задачу ввести дополнительные «ненаблюдаемые» (скрытые, латентные) переменные. Примерами прикладных задач второго типа являются задачи распознавания образов, реконструкции изображений. Математическую суть данных задач составляют задачи кластерного анализа, классификации и разделения смесей вероятностных распределений.

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

Victoria Evstefeeva в 15:00, 24 октября 2017

2017-10-24T15:00:58Z

← Предыдущая версия		Версия от 15:00, 24 октября 2017
Строка 1:		Строка 1:
	Данный документ содержит описание схемы, по которой предлагается описывать свойства и структуру каждого алгоритма. Описание состоит из двух частей. В [[#ЧАСТЬ. Свойства и структура алгоритмов\|первой части]] описываются собственно алгоритмы и их свойства, а [[#ЧАСТЬ. Программная реализация алгоритмов\|вторая]] посвящена описанию особенностей их программной реализации с учетом конкретных программно-аппаратных платформ. Такое деление на части сделано для того, чтобы машинно-независимые свойства алгоритмов, которые определяют качество их реализации на параллельных вычислительных системах, были бы выделены и описаны отдельно от множества вопросов, связанных с последующими этапами программирования алгоритмов и исполнения результирующих программ.

	~~Общая схема описания алгоритмов имеет следующий вид:~~

	== Свойства и структура алгоритмов ==		== Свойства и структура алгоритмов ==
	Свойства алгоритмов никак не зависят от вычислительных систем, и с этой точки зрения данная часть AlgoWiki имеет безусловную собственную ценность. Описание алгоритма делается один раз, после чего многократно используется для его реализации в различных программно-аппаратных средах. Несмотря на то, что в данной части мы рассматриваем лишь машинно-независимые свойства алгоритмов, соображения, важные на этапе реализации, или же ссылки на соответствующие пункты [[#ЧАСТЬ. Программная реализация алгоритмов\|части II AlgoWiki]], здесь также вполне уместны.		Свойства алгоритмов никак не зависят от вычислительных систем, и с этой точки зрения данная часть AlgoWiki имеет безусловную собственную ценность. Описание алгоритма делается один раз, после чего многократно используется для его реализации в различных программно-аппаратных средах. Несмотря на то, что в данной части мы рассматриваем лишь машинно-независимые свойства алгоритмов, соображения, важные на этапе реализации, или же ссылки на соответствующие пункты [[#ЧАСТЬ. Программная реализация алгоритмов\|части II AlgoWiki]], здесь также вполне уместны.