Алговики - Вклад [ru]

Участник:Nkrivenko/Алгоритм кластеризации категориальных данных

2016-10-16T12:20:48Z

Nkrivenko:

{{Assignment}}

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Данный алгоритм предназначен для кластеризации очень больших объемов данных. К особенностям алгоритма относятся использование глобального критерия оптимизации на основе максимизации коэффициента высоты гистограммы кластера и минимальное число сканирований наборов данных. Количество кластеров подбирается автоматически, что регулируется единственным параметром - коэффициентом отталкивания.
=== Математическое описание алгоритма ===
Пусть имеется база транзакций <math>D</math>, которая состоит из множества транзакций <math>\{t_1, ..., t_n\}</math>. Каждая из транзакций суть набор объектов <math>\{i_1, ..., i_n\}</math>. Множество кластеров <math>\{C_1, ..., C_m\}</math> есть разбиение множества транзакций таким образом, что <math>C_1 \oplus ... \oplus C_m = D</math>. У каждого кластера есть следующие характеристики:

1. Множество уникальных объектов <math>D(C)</math>.

2. <math>Occ(i, C)</math> - количество вхождений объекта <math>i</math> в кластер <math>C</math>

3. <math>S(C) = \sum_{i \in D(C)}{Occ(i,c)} = \sum_{i=1}^{m}{|t_i|}</math> - площадь кластера

4. <math>W(C) = |D(C)|</math> - ширина кластера,

5. <math>H(C) = S(C) / W(C)</math> - высота кластера.

Функция стоимости:

<math>Profit(C, r) = \frac{\sum_{i=1}^{k}{\frac{S(C_i)}{W^r (C_i)}|C_i|}}{\sum_{i=1}^{k}{|C_i|}}</math>,

где <math>r, 0 < r \leq 1</math> - коэффициент отталкивания.

С помощью параметра <math>r</math> регулируется уровень сходства
транзакций внутри кластера, и, как следствие, финальное количество кластеров.
Этот коэффициент подбирается пользователем.
Чем больше <math>r</math>, тем ниже уровень сходства и тем больше кластеров будет сгенерировано.

Формальная постановка задачи кластеризации выглядит следующим образом:

<math> Profit(C, r) \to max </math>

=== Вычислительное ядро алгоритма ===
Вычислительным ядром алгоритма является оптимизация функции стоимости.

<math> Profit(C, r) \to max </math>

=== Макроструктура алгоритма ===
Как указано выше, основную часть метода составляет вычисление максимума функции стоимости.

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

Реализация алгоритма требует первого прохода по таблице транзакций для построения начального разбиения, определяемого функцией <math>Profit(C,r)</math>. После этого требуется некоторое количество дополнительных сканирований таблицы для повышения качества кластеризации и оптимизации функции стоимости. Если в текущем проходе по таблице изменений не произошло, то алгоритм прекращает свою работу

1. Пока не конец

1.1 прочитать из таблицы следующую транзакцию [t, -];

1.2 положить t в существующий либо в новый кластер <math>C_i</math>, который дает максимум <math>Profit(C,r)</math>;

1.3 записать [t,i] в таблицу (номер кластера);

2. Повторять

2.1 перейти в начало таблицы;

2.2 moved = false;

2.3 пока не конец таблицы

2.3.1 читать [t,i];

2.3.2 положить t в существующий либо в новый кластер <math>C_j</math>, который максимизирует <math>Profit(C,r)</math>;

2.3.3 если <math>C_i \neq C_j</math> тогда

2.3.3.1 записать [t,i];

2.3.4 moved = true;

2.4 пока (not moved).

3. удалить все пустые кластеры;

=== Последовательная сложность алгоритма ===
Пусть средняя длина транзакции равна <math>A</math>, общее число транзакций <math>N</math>, максимально возможное число кластеров <math>K</math>. Временная сложность одной итерации равна <math>O(N*K*A)</math>, показывающая, что скорость работы алгоритма растет линейно с ростом кластеров и размера таблицы. Это делает алгоритм быстрым и эффективным на больших объемах.

=== Информационный граф алгоритма ===
[[Файл:CLOPEGraph.png]]
Здесь вершина Read - чтение транзакции из таблицы, PutIntoCluster - положить t в существующий либо в новый кластер, который дает максимум Profit(C,r), WriteIfINotEqualsJ соответствует шагам 2.3.3 и 2.3.3.1 пункта 1.5.

=== Ресурс параллелизма алгоритма ===
Алгоритм CLOPE является масштабируемым, поскольку можно читать данные из таблицы и распределять их по кластерам с подсчетом функции стоимости параллельно.

=== Входные и выходные данные алгоритма ===
Входные данные - таблица транзакций <math>D = \{t_1, ..., t_n\}</math>.
Выходные данные - множество кластеров <math>\{C_1, ... , C_k\}</math>

=== Свойства алгоритма ===
Соотношение последовательной и параллельной сложностей является квадратичным при том, что вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных является линейной.

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
Алгоритм CLOPE имеет множество приложений в базах данных, в частности для MySQL: https://github.com/infozor/php_mysql_clustering_clope

Также есть реализация на языке Go: https://github.com/realb0t/go-clope

Участник:Nkrivenko/Алгоритм кластеризации категориальных данных

2016-10-15T21:56:18Z

Nkrivenko: /* Информационный граф алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Данный алгоритм предназначен для кластеризации очень больших объемов данных. К особенностям алгоритма относятся использование глобального критерия оптимизации на основе максимизации коэффициента высоты гистограммы кластера и минимальное число сканирований наборов данных. Количество кластеров подбирается автоматически, что регулируется единственным параметром - коэффициентом отталкивания.
=== Математическое описание алгоритма ===
Пусть имеется база транзакций <math>D</math>, которая состоит из множества транзакций <math>\{t_1, ..., t_n\}</math>. Каждая из транзакций суть набор объектов <math>\{i_1, ..., i_n\}</math>. Множество кластеров <math>\{C_1, ..., C_m\}</math> есть разбиение множества транзакций таким образом, что <math>C_1 \oplus ... \oplus C_m = D</math>. У каждого кластера есть следующие характеристики:

1. Множество уникальных объектов <math>D(C)</math>.

2. <math>Occ(i, C)</math> - количество вхождений объекта <math>i</math> в кластер <math>C</math>

3. <math>S(C) = \sum_{i \in D(C)}{Occ(i,c)} = \sum_{i=1}^{m}{|t_i|}</math> - площадь кластера

4. <math>W(C) = |D(C)|</math> - ширина кластера,

5. <math>H(C) = S(C) / W(C)</math> - высота кластера.

Функция стоимости:

<math>Profit(C, r) = \frac{\sum_{i=1}^{k}{\frac{S(C_i)}{W^r (C_i)}|C_i|}}{\sum_{i=1}^{k}{|C_i|}}</math>,

где <math>r, 0 < r \leq 1</math> - коэффициент отталкивания.

С помощью параметра <math>r</math> регулируется уровень сходства
транзакций внутри кластера, и, как следствие, финальное количество кластеров.
Этот коэффициент подбирается пользователем.
Чем больше <math>r</math>, тем ниже уровень сходства и тем больше кластеров будет сгенерировано.

Формальная постановка задачи кластеризации выглядит следующим образом:

<math> Profit(C, r) \to max </math>

=== Вычислительное ядро алгоритма ===
Вычислительным ядром алгоритма является оптимизация функции стоимости.

<math> Profit(C, r) \to max </math>

=== Макроструктура алгоритма ===
Как указано выше, основную часть метода составляет вычисление максимума функции стоимости.

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

Реализация алгоритма требует первого прохода по таблице транзакций для построения начального разбиения, определяемого функцией <math>Profit(C,r)</math>. После этого требуется некоторое количество дополнительных сканирований таблицы для повышения качества кластеризации и оптимизации функции стоимости. Если в текущем проходе по таблице изменений не произошло, то алгоритм прекращает свою работу

1. Пока не конец

1.1 прочитать из таблицы следующую транзакцию [t, -];

1.2 положить t в существующий либо в новый кластер <math>C_i</math>, который дает максимум <math>Profit(C,r)</math>;

1.3 записать [t,i] в таблицу (номер кластера);

2. Повторять

2.1 перейти в начало таблицы;

2.2 moved = false;

2.3 пока не конец таблицы

2.3.1 читать [t,i];

2.3.2 положить t в существующий либо в новый кластер <math>C_j</math>, который максимизирует <math>Profit(C,r)</math>;

2.3.3 если <math>C_i \neq C_j</math> тогда

2.3.3.1 записать [t,i];

2.3.4 moved = true;

2.4 пока (not moved).

3. удалить все пустые кластеры;

=== Последовательная сложность алгоритма ===
Пусть средняя длина транзакции равна <math>A</math>, общее число транзакций <math>N</math>, максимально возможное число кластеров <math>K</math>. Временная сложность одной итерации равна <math>O(N*K*A)</math>, показывающая, что скорость работы алгоритма растет линейно с ростом кластеров и размера таблицы. Это делает алгоритм быстрым и эффективным на больших объемах.

=== Информационный граф алгоритма ===
[[Файл:CLOPEGraph.png]]
Здесь вершина Read - чтение транзакции из таблицы, PutIntoCluster - положить t в существующий либо в новый кластер, который дает максимум Profit(C,r), WriteIfINotEqualsJ соответствует шагам 2.3.3 и 2.3.3.1 пункта 1.5.

=== Ресурс параллелизма алгоритма ===
Алгоритм CLOPE является масштабируемым, поскольку можно читать данные из таблицы и распределять их по кластерам с подсчетом функции стоимости параллельно.

=== Входные и выходные данные алгоритма ===
Входные данные - таблица транзакций <math>D = \{t_1, ..., t_n\}</math>.
Выходные данные - множество кластеров <math>\{C_1, ... , C_k\}</math>

=== Свойства алгоритма ===
Соотношение последовательной и параллельной сложностей является квадратичным при том, что вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных является линейной.

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
Алгоритм CLOPE имеет множество приложений в базах данных, в частности для MySQL: https://github.com/infozor/php_mysql_clustering_clope

Также есть реализация на языке Go: https://github.com/realb0t/go-clope

Участник:Nkrivenko/Алгоритм кластеризации категориальных данных

2016-10-15T21:50:54Z

Nkrivenko: /* Информационный граф алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Данный алгоритм предназначен для кластеризации очень больших объемов данных. К особенностям алгоритма относятся использование глобального критерия оптимизации на основе максимизации коэффициента высоты гистограммы кластера и минимальное число сканирований наборов данных. Количество кластеров подбирается автоматически, что регулируется единственным параметром - коэффициентом отталкивания.
=== Математическое описание алгоритма ===
Пусть имеется база транзакций <math>D</math>, которая состоит из множества транзакций <math>\{t_1, ..., t_n\}</math>. Каждая из транзакций суть набор объектов <math>\{i_1, ..., i_n\}</math>. Множество кластеров <math>\{C_1, ..., C_m\}</math> есть разбиение множества транзакций таким образом, что <math>C_1 \oplus ... \oplus C_m = D</math>. У каждого кластера есть следующие характеристики:

1. Множество уникальных объектов <math>D(C)</math>.

2. <math>Occ(i, C)</math> - количество вхождений объекта <math>i</math> в кластер <math>C</math>

3. <math>S(C) = \sum_{i \in D(C)}{Occ(i,c)} = \sum_{i=1}^{m}{|t_i|}</math> - площадь кластера

4. <math>W(C) = |D(C)|</math> - ширина кластера,

5. <math>H(C) = S(C) / W(C)</math> - высота кластера.

Функция стоимости:

<math>Profit(C, r) = \frac{\sum_{i=1}^{k}{\frac{S(C_i)}{W^r (C_i)}|C_i|}}{\sum_{i=1}^{k}{|C_i|}}</math>,

где <math>r, 0 < r \leq 1</math> - коэффициент отталкивания.

С помощью параметра <math>r</math> регулируется уровень сходства
транзакций внутри кластера, и, как следствие, финальное количество кластеров.
Этот коэффициент подбирается пользователем.
Чем больше <math>r</math>, тем ниже уровень сходства и тем больше кластеров будет сгенерировано.

Формальная постановка задачи кластеризации выглядит следующим образом:

<math> Profit(C, r) \to max </math>

=== Вычислительное ядро алгоритма ===
Вычислительным ядром алгоритма является оптимизация функции стоимости.

<math> Profit(C, r) \to max </math>

=== Макроструктура алгоритма ===
Как указано выше, основную часть метода составляет вычисление максимума функции стоимости.

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

Реализация алгоритма требует первого прохода по таблице транзакций для построения начального разбиения, определяемого функцией <math>Profit(C,r)</math>. После этого требуется некоторое количество дополнительных сканирований таблицы для повышения качества кластеризации и оптимизации функции стоимости. Если в текущем проходе по таблице изменений не произошло, то алгоритм прекращает свою работу

1. Пока не конец

1.1 прочитать из таблицы следующую транзакцию [t, -];

1.2 положить t в существующий либо в новый кластер <math>C_i</math>, который дает максимум <math>Profit(C,r)</math>;

1.3 записать [t,i] в таблицу (номер кластера);

2. Повторять

2.1 перейти в начало таблицы;

2.2 moved = false;

2.3 пока не конец таблицы

2.3.1 читать [t,i];

2.3.2 положить t в существующий либо в новый кластер <math>C_j</math>, который максимизирует <math>Profit(C,r)</math>;

2.3.3 если <math>C_i \neq C_j</math> тогда

2.3.3.1 записать [t,i];

2.3.4 moved = true;

2.4 пока (not moved).

3. удалить все пустые кластеры;

=== Последовательная сложность алгоритма ===
Пусть средняя длина транзакции равна <math>A</math>, общее число транзакций <math>N</math>, максимально возможное число кластеров <math>K</math>. Временная сложность одной итерации равна <math>O(N*K*A)</math>, показывающая, что скорость работы алгоритма растет линейно с ростом кластеров и размера таблицы. Это делает алгоритм быстрым и эффективным на больших объемах.

=== Информационный граф алгоритма ===
[[Файл:CLOPEGraph.png]]

=== Ресурс параллелизма алгоритма ===
Алгоритм CLOPE является масштабируемым, поскольку можно читать данные из таблицы и распределять их по кластерам с подсчетом функции стоимости параллельно.

=== Входные и выходные данные алгоритма ===
Входные данные - таблица транзакций <math>D = \{t_1, ..., t_n\}</math>.
Выходные данные - множество кластеров <math>\{C_1, ... , C_k\}</math>

=== Свойства алгоритма ===
Соотношение последовательной и параллельной сложностей является квадратичным при том, что вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных является линейной.

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
Алгоритм CLOPE имеет множество приложений в базах данных, в частности для MySQL: https://github.com/infozor/php_mysql_clustering_clope

Также есть реализация на языке Go: https://github.com/realb0t/go-clope

Участник:Nkrivenko/Алгоритм кластеризации категориальных данных

2016-10-15T21:22:35Z

Nkrivenko: /* Вычислительное ядро алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Данный алгоритм предназначен для кластеризации очень больших объемов данных. К особенностям алгоритма относятся использование глобального критерия оптимизации на основе максимизации коэффициента высоты гистограммы кластера и минимальное число сканирований наборов данных. Количество кластеров подбирается автоматически, что регулируется единственным параметром - коэффициентом отталкивания.
=== Математическое описание алгоритма ===
Пусть имеется база транзакций <math>D</math>, которая состоит из множества транзакций <math>\{t_1, ..., t_n\}</math>. Каждая из транзакций суть набор объектов <math>\{i_1, ..., i_n\}</math>. Множество кластеров <math>\{C_1, ..., C_m\}</math> есть разбиение множества транзакций таким образом, что <math>C_1 \oplus ... \oplus C_m = D</math>. У каждого кластера есть следующие характеристики:

1. Множество уникальных объектов <math>D(C)</math>.

2. <math>Occ(i, C)</math> - количество вхождений объекта <math>i</math> в кластер <math>C</math>

3. <math>S(C) = \sum_{i \in D(C)}{Occ(i,c)} = \sum_{i=1}^{m}{|t_i|}</math> - площадь кластера

4. <math>W(C) = |D(C)|</math> - ширина кластера,

5. <math>H(C) = S(C) / W(C)</math> - высота кластера.

Функция стоимости:

<math>Profit(C, r) = \frac{\sum_{i=1}^{k}{\frac{S(C_i)}{W^r (C_i)}|C_i|}}{\sum_{i=1}^{k}{|C_i|}}</math>,

где <math>r, 0 < r \leq 1</math> - коэффициент отталкивания.

С помощью параметра <math>r</math> регулируется уровень сходства
транзакций внутри кластера, и, как следствие, финальное количество кластеров.
Этот коэффициент подбирается пользователем.
Чем больше <math>r</math>, тем ниже уровень сходства и тем больше кластеров будет сгенерировано.

Формальная постановка задачи кластеризации выглядит следующим образом:

<math> Profit(C, r) \to max </math>

=== Вычислительное ядро алгоритма ===
Вычислительным ядром алгоритма является оптимизация функции стоимости.

<math> Profit(C, r) \to max </math>

=== Макроструктура алгоритма ===
Как указано выше, основную часть метода составляет вычисление максимума функции стоимости.

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

Реализация алгоритма требует первого прохода по таблице транзакций для построения начального разбиения, определяемого функцией <math>Profit(C,r)</math>. После этого требуется некоторое количество дополнительных сканирований таблицы для повышения качества кластеризации и оптимизации функции стоимости. Если в текущем проходе по таблице изменений не произошло, то алгоритм прекращает свою работу

1. Пока не конец

1.1 прочитать из таблицы следующую транзакцию [t, -];

1.2 положить t в существующий либо в новый кластер <math>C_i</math>, который дает максимум <math>Profit(C,r)</math>;

1.3 записать [t,i] в таблицу (номер кластера);

2. Повторять

2.1 перейти в начало таблицы;

2.2 moved = false;

2.3 пока не конец таблицы

2.3.1 читать [t,i];

2.3.2 положить t в существующий либо в новый кластер <math>C_j</math>, который максимизирует <math>Profit(C,r)</math>;

2.3.3 если <math>C_i \neq C_j</math> тогда

2.3.3.1 записать [t,i];

2.3.4 moved = true;

2.4 пока (not moved).

3. удалить все пустые кластеры;

=== Последовательная сложность алгоритма ===
Пусть средняя длина транзакции равна <math>A</math>, общее число транзакций <math>N</math>, максимально возможное число кластеров <math>K</math>. Временная сложность одной итерации равна <math>O(N*K*A)</math>, показывающая, что скорость работы алгоритма растет линейно с ростом кластеров и размера таблицы. Это делает алгоритм быстрым и эффективным на больших объемах.

=== Информационный граф алгоритма ===
=== Ресурс параллелизма алгоритма ===
Алгоритм CLOPE является масштабируемым, поскольку можно читать данные из таблицы и распределять их по кластерам с подсчетом функции стоимости параллельно.

=== Входные и выходные данные алгоритма ===
Входные данные - таблица транзакций <math>D = \{t_1, ..., t_n\}</math>.
Выходные данные - множество кластеров <math>\{C_1, ... , C_k\}</math>

=== Свойства алгоритма ===
Соотношение последовательной и параллельной сложностей является квадратичным при том, что вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных является линейной.

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
Алгоритм CLOPE имеет множество приложений в базах данных, в частности для MySQL: https://github.com/infozor/php_mysql_clustering_clope

Также есть реализация на языке Go: https://github.com/realb0t/go-clope

Участник:Nkrivenko/Алгоритм кластеризации категориальных данных

2016-10-15T21:21:13Z

Nkrivenko: /* Существующие реализации алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Данный алгоритм предназначен для кластеризации очень больших объемов данных. К особенностям алгоритма относятся использование глобального критерия оптимизации на основе максимизации коэффициента высоты гистограммы кластера и минимальное число сканирований наборов данных. Количество кластеров подбирается автоматически, что регулируется единственным параметром - коэффициентом отталкивания.
=== Математическое описание алгоритма ===
Пусть имеется база транзакций <math>D</math>, которая состоит из множества транзакций <math>\{t_1, ..., t_n\}</math>. Каждая из транзакций суть набор объектов <math>\{i_1, ..., i_n\}</math>. Множество кластеров <math>\{C_1, ..., C_m\}</math> есть разбиение множества транзакций таким образом, что <math>C_1 \oplus ... \oplus C_m = D</math>. У каждого кластера есть следующие характеристики:

1. Множество уникальных объектов <math>D(C)</math>.

2. <math>Occ(i, C)</math> - количество вхождений объекта <math>i</math> в кластер <math>C</math>

3. <math>S(C) = \sum_{i \in D(C)}{Occ(i,c)} = \sum_{i=1}^{m}{|t_i|}</math> - площадь кластера

4. <math>W(C) = |D(C)|</math> - ширина кластера,

5. <math>H(C) = S(C) / W(C)</math> - высота кластера.

Функция стоимости:

<math>Profit(C, r) = \frac{\sum_{i=1}^{k}{\frac{S(C_i)}{W^r (C_i)}|C_i|}}{\sum_{i=1}^{k}{|C_i|}}</math>,

где <math>r, 0 < r \leq 1</math> - коэффициент отталкивания.

С помощью параметра <math>r</math> регулируется уровень сходства
транзакций внутри кластера, и, как следствие, финальное количество кластеров.
Этот коэффициент подбирается пользователем.
Чем больше <math>r</math>, тем ниже уровень сходства и тем больше кластеров будет сгенерировано.

Формальная постановка задачи кластеризации выглядит следующим образом:

<math> Profit(C, r) \to max </math>

=== Вычислительное ядро алгоритма ===
Вычислительным ядром алгоритма является оптимизация функции стоимости.

<math> Profit(C, r) \to max </math>

Оптимизация функции может проводиться любым известным методом, например, градиентными методами.

=== Макроструктура алгоритма ===
Как указано выше, основную часть метода составляет вычисление максимума функции стоимости.

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

Реализация алгоритма требует первого прохода по таблице транзакций для построения начального разбиения, определяемого функцией <math>Profit(C,r)</math>. После этого требуется некоторое количество дополнительных сканирований таблицы для повышения качества кластеризации и оптимизации функции стоимости. Если в текущем проходе по таблице изменений не произошло, то алгоритм прекращает свою работу

1. Пока не конец

1.1 прочитать из таблицы следующую транзакцию [t, -];

1.2 положить t в существующий либо в новый кластер <math>C_i</math>, который дает максимум <math>Profit(C,r)</math>;

1.3 записать [t,i] в таблицу (номер кластера);

2. Повторять

2.1 перейти в начало таблицы;

2.2 moved = false;

2.3 пока не конец таблицы

2.3.1 читать [t,i];

2.3.2 положить t в существующий либо в новый кластер <math>C_j</math>, который максимизирует <math>Profit(C,r)</math>;

2.3.3 если <math>C_i \neq C_j</math> тогда

2.3.3.1 записать [t,i];

2.3.4 moved = true;

2.4 пока (not moved).

3. удалить все пустые кластеры;

=== Последовательная сложность алгоритма ===
Пусть средняя длина транзакции равна <math>A</math>, общее число транзакций <math>N</math>, максимально возможное число кластеров <math>K</math>. Временная сложность одной итерации равна <math>O(N*K*A)</math>, показывающая, что скорость работы алгоритма растет линейно с ростом кластеров и размера таблицы. Это делает алгоритм быстрым и эффективным на больших объемах.

=== Информационный граф алгоритма ===
=== Ресурс параллелизма алгоритма ===
Алгоритм CLOPE является масштабируемым, поскольку можно читать данные из таблицы и распределять их по кластерам с подсчетом функции стоимости параллельно.

=== Входные и выходные данные алгоритма ===
Входные данные - таблица транзакций <math>D = \{t_1, ..., t_n\}</math>.
Выходные данные - множество кластеров <math>\{C_1, ... , C_k\}</math>

=== Свойства алгоритма ===
Соотношение последовательной и параллельной сложностей является квадратичным при том, что вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных является линейной.

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
Алгоритм CLOPE имеет множество приложений в базах данных, в частности для MySQL: https://github.com/infozor/php_mysql_clustering_clope

Также есть реализация на языке Go: https://github.com/realb0t/go-clope

Участник:Nkrivenko/Алгоритм кластеризации категориальных данных

2016-10-15T21:07:33Z

Nkrivenko: /* Свойства алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Данный алгоритм предназначен для кластеризации очень больших объемов данных. К особенностям алгоритма относятся использование глобального критерия оптимизации на основе максимизации коэффициента высоты гистограммы кластера и минимальное число сканирований наборов данных. Количество кластеров подбирается автоматически, что регулируется единственным параметром - коэффициентом отталкивания.
=== Математическое описание алгоритма ===
Пусть имеется база транзакций <math>D</math>, которая состоит из множества транзакций <math>\{t_1, ..., t_n\}</math>. Каждая из транзакций суть набор объектов <math>\{i_1, ..., i_n\}</math>. Множество кластеров <math>\{C_1, ..., C_m\}</math> есть разбиение множества транзакций таким образом, что <math>C_1 \oplus ... \oplus C_m = D</math>. У каждого кластера есть следующие характеристики:

1. Множество уникальных объектов <math>D(C)</math>.

2. <math>Occ(i, C)</math> - количество вхождений объекта <math>i</math> в кластер <math>C</math>

3. <math>S(C) = \sum_{i \in D(C)}{Occ(i,c)} = \sum_{i=1}^{m}{|t_i|}</math> - площадь кластера

4. <math>W(C) = |D(C)|</math> - ширина кластера,

5. <math>H(C) = S(C) / W(C)</math> - высота кластера.

Функция стоимости:

<math>Profit(C, r) = \frac{\sum_{i=1}^{k}{\frac{S(C_i)}{W^r (C_i)}|C_i|}}{\sum_{i=1}^{k}{|C_i|}}</math>,

где <math>r, 0 < r \leq 1</math> - коэффициент отталкивания.

С помощью параметра <math>r</math> регулируется уровень сходства
транзакций внутри кластера, и, как следствие, финальное количество кластеров.
Этот коэффициент подбирается пользователем.
Чем больше <math>r</math>, тем ниже уровень сходства и тем больше кластеров будет сгенерировано.

Формальная постановка задачи кластеризации выглядит следующим образом:

<math> Profit(C, r) \to max </math>

=== Вычислительное ядро алгоритма ===
Вычислительным ядром алгоритма является оптимизация функции стоимости.

<math> Profit(C, r) \to max </math>

Оптимизация функции может проводиться любым известным методом, например, градиентными методами.

=== Макроструктура алгоритма ===
Как указано выше, основную часть метода составляет вычисление максимума функции стоимости.

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

Реализация алгоритма требует первого прохода по таблице транзакций для построения начального разбиения, определяемого функцией <math>Profit(C,r)</math>. После этого требуется некоторое количество дополнительных сканирований таблицы для повышения качества кластеризации и оптимизации функции стоимости. Если в текущем проходе по таблице изменений не произошло, то алгоритм прекращает свою работу

1. Пока не конец

1.1 прочитать из таблицы следующую транзакцию [t, -];

1.2 положить t в существующий либо в новый кластер <math>C_i</math>, который дает максимум <math>Profit(C,r)</math>;

1.3 записать [t,i] в таблицу (номер кластера);

2. Повторять

2.1 перейти в начало таблицы;

2.2 moved = false;

2.3 пока не конец таблицы

2.3.1 читать [t,i];

2.3.2 положить t в существующий либо в новый кластер <math>C_j</math>, который максимизирует <math>Profit(C,r)</math>;

2.3.3 если <math>C_i \neq C_j</math> тогда

2.3.3.1 записать [t,i];

2.3.4 moved = true;

2.4 пока (not moved).

3. удалить все пустые кластеры;

=== Последовательная сложность алгоритма ===
Пусть средняя длина транзакции равна <math>A</math>, общее число транзакций <math>N</math>, максимально возможное число кластеров <math>K</math>. Временная сложность одной итерации равна <math>O(N*K*A)</math>, показывающая, что скорость работы алгоритма растет линейно с ростом кластеров и размера таблицы. Это делает алгоритм быстрым и эффективным на больших объемах.

=== Информационный граф алгоритма ===
=== Ресурс параллелизма алгоритма ===
Алгоритм CLOPE является масштабируемым, поскольку можно читать данные из таблицы и распределять их по кластерам с подсчетом функции стоимости параллельно.

=== Входные и выходные данные алгоритма ===
Входные данные - таблица транзакций <math>D = \{t_1, ..., t_n\}</math>.
Выходные данные - множество кластеров <math>\{C_1, ... , C_k\}</math>

=== Свойства алгоритма ===
Соотношение последовательной и параллельной сложностей является квадратичным при том, что вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных является линейной.

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

Участник:Nkrivenko/Алгоритм кластеризации категориальных данных

2016-10-15T20:58:16Z

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

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Данный алгоритм предназначен для кластеризации очень больших объемов данных. К особенностям алгоритма относятся использование глобального критерия оптимизации на основе максимизации коэффициента высоты гистограммы кластера и минимальное число сканирований наборов данных. Количество кластеров подбирается автоматически, что регулируется единственным параметром - коэффициентом отталкивания.
=== Математическое описание алгоритма ===
Пусть имеется база транзакций <math>D</math>, которая состоит из множества транзакций <math>\{t_1, ..., t_n\}</math>. Каждая из транзакций суть набор объектов <math>\{i_1, ..., i_n\}</math>. Множество кластеров <math>\{C_1, ..., C_m\}</math> есть разбиение множества транзакций таким образом, что <math>C_1 \oplus ... \oplus C_m = D</math>. У каждого кластера есть следующие характеристики:

1. Множество уникальных объектов <math>D(C)</math>.

2. <math>Occ(i, C)</math> - количество вхождений объекта <math>i</math> в кластер <math>C</math>

3. <math>S(C) = \sum_{i \in D(C)}{Occ(i,c)} = \sum_{i=1}^{m}{|t_i|}</math> - площадь кластера

4. <math>W(C) = |D(C)|</math> - ширина кластера,

5. <math>H(C) = S(C) / W(C)</math> - высота кластера.

Функция стоимости:

<math>Profit(C, r) = \frac{\sum_{i=1}^{k}{\frac{S(C_i)}{W^r (C_i)}|C_i|}}{\sum_{i=1}^{k}{|C_i|}}</math>,

где <math>r, 0 < r \leq 1</math> - коэффициент отталкивания.

С помощью параметра <math>r</math> регулируется уровень сходства
транзакций внутри кластера, и, как следствие, финальное количество кластеров.
Этот коэффициент подбирается пользователем.
Чем больше <math>r</math>, тем ниже уровень сходства и тем больше кластеров будет сгенерировано.

Формальная постановка задачи кластеризации выглядит следующим образом:

<math> Profit(C, r) \to max </math>

=== Вычислительное ядро алгоритма ===
Вычислительным ядром алгоритма является оптимизация функции стоимости.

<math> Profit(C, r) \to max </math>

Оптимизация функции может проводиться любым известным методом, например, градиентными методами.

=== Макроструктура алгоритма ===
Как указано выше, основную часть метода составляет вычисление максимума функции стоимости.

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

Реализация алгоритма требует первого прохода по таблице транзакций для построения начального разбиения, определяемого функцией <math>Profit(C,r)</math>. После этого требуется некоторое количество дополнительных сканирований таблицы для повышения качества кластеризации и оптимизации функции стоимости. Если в текущем проходе по таблице изменений не произошло, то алгоритм прекращает свою работу

1. Пока не конец

1.1 прочитать из таблицы следующую транзакцию [t, -];

1.2 положить t в существующий либо в новый кластер <math>C_i</math>, который дает максимум <math>Profit(C,r)</math>;

1.3 записать [t,i] в таблицу (номер кластера);

2. Повторять

2.1 перейти в начало таблицы;

2.2 moved = false;

2.3 пока не конец таблицы

2.3.1 читать [t,i];

2.3.2 положить t в существующий либо в новый кластер <math>C_j</math>, который максимизирует <math>Profit(C,r)</math>;

2.3.3 если <math>C_i \neq C_j</math> тогда

2.3.3.1 записать [t,i];

2.3.4 moved = true;

2.4 пока (not moved).

3. удалить все пустые кластеры;

=== Последовательная сложность алгоритма ===
Пусть средняя длина транзакции равна <math>A</math>, общее число транзакций <math>N</math>, максимально возможное число кластеров <math>K</math>. Временная сложность одной итерации равна <math>O(N*K*A)</math>, показывающая, что скорость работы алгоритма растет линейно с ростом кластеров и размера таблицы. Это делает алгоритм быстрым и эффективным на больших объемах.

=== Информационный граф алгоритма ===
=== Ресурс параллелизма алгоритма ===
Алгоритм CLOPE является масштабируемым, поскольку можно читать данные из таблицы и распределять их по кластерам с подсчетом функции стоимости параллельно.

=== Входные и выходные данные алгоритма ===
Входные данные - таблица транзакций <math>D = \{t_1, ..., t_n\}</math>.
Выходные данные - множество кластеров <math>\{C_1, ... , C_k\}</math>

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

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

Участник:Nkrivenko/Алгоритм кластеризации категориальных данных

2016-10-15T20:52:43Z

Nkrivenko: /* Входные и выходные данные алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Данный алгоритм предназначен для кластеризации очень больших объемов данных. К особенностям алгоритма относятся использование глобального критерия оптимизации на основе максимизации коэффициента высоты гистограммы кластера и минимальное число сканирований наборов данных. Количество кластеров подбирается автоматически, что регулируется единственным параметром - коэффициентом отталкивания.
=== Математическое описание алгоритма ===
Пусть имеется база транзакций <math>D</math>, которая состоит из множества транзакций <math>\{t_1, ..., t_n\}</math>. Каждая из транзакций суть набор объектов <math>\{i_1, ..., i_n\}</math>. Множество кластеров <math>\{C_1, ..., C_m\}</math> есть разбиение множества транзакций таким образом, что <math>C_1 \oplus ... \oplus C_m = D</math>. У каждого кластера есть следующие характеристики:

1. Множество уникальных объектов <math>D(C)</math>.

2. <math>Occ(i, C)</math> - количество вхождений объекта <math>i</math> в кластер <math>C</math>

3. <math>S(C) = \sum_{i \in D(C)}{Occ(i,c)} = \sum_{i=1}^{m}{|t_i|}</math> - площадь кластера

4. <math>W(C) = |D(C)|</math> - ширина кластера,

5. <math>H(C) = S(C) / W(C)</math> - уровень сходства.

Функция стоимости:

<math>Profit(C, r) = \frac{\sum_{i=1}^{k}{\frac{S(C_i)}{W^r (C_i)}|C_i|}}{\sum_{i=1}^{k}{|C_i|}}</math>,

где <math>r, 0 < r \leq 1</math> - коэффициент отталкивания.

С помощью параметра <math>r</math> регулируется уровень сходства
транзакций внутри кластера, и, как следствие, финальное количество кластеров.
Этот коэффициент подбирается пользователем.
Чем больше <math>r</math>, тем ниже уровень сходства и тем больше кластеров будет сгенерировано.

Формальная постановка задачи кластеризации выглядит следующим образом:

<math> Profit(C, r) \to max </math>

=== Вычислительное ядро алгоритма ===
Вычислительным ядром алгоритма является оптимизация функции стоимости.

<math> Profit(C, r) \to max </math>

Оптимизация функции может проводиться любым известным методом, например, градиентными методами.

=== Макроструктура алгоритма ===
Как указано выше, основную часть метода составляет вычисление максимума функции стоимости.

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

Реализация алгоритма требует первого прохода по таблице транзакций для построения начального разбиения, определяемого функцией <math>Profit(C,r)</math>. После этого требуется некоторое количество дополнительных сканирований таблицы для повышения качества кластеризации и оптимизации функции стоимости. Если в текущем проходе по таблице изменений не произошло, то алгоритм прекращает свою работу

1. Пока не конец

1.1 прочитать из таблицы следующую транзакцию [t, -];

1.2 положить t в существующий либо в новый кластер <math>C_i</math>, который дает максимум <math>Profit(C,r)</math>;

1.3 записать [t,i] в таблицу (номер кластера);

2. Повторять

2.1 перейти в начало таблицы;

2.2 moved = false;

2.3 пока не конец таблицы

2.3.1 читать [t,i];

2.3.2 положить t в существующий либо в новый кластер <math>C_j</math>, который максимизирует <math>Profit(C,r)</math>;

2.3.3 если <math>C_i \neq C_j</math> тогда

2.3.3.1 записать [t,i];

2.3.4 moved = true;

2.4 пока (not moved).

3. удалить все пустые кластеры;

=== Последовательная сложность алгоритма ===
Пусть средняя длина транзакции равна <math>A</math>, общее число транзакций <math>N</math>, максимально возможное число кластеров <math>K</math>. Временная сложность одной итерации равна <math>O(N*K*A)</math>, показывающая, что скорость работы алгоритма растет линейно с ростом кластеров и размера таблицы. Это делает алгоритм быстрым и эффективным на больших объемах.

=== Информационный граф алгоритма ===
=== Ресурс параллелизма алгоритма ===
Алгоритм CLOPE является масштабируемым, поскольку можно читать данные из таблицы и распределять их по кластерам с подсчетом функции стоимости параллельно.

=== Входные и выходные данные алгоритма ===
Входные данные - таблица транзакций <math>D = \{t_1, ..., t_n\}</math>.
Выходные данные - множество кластеров <math>\{C_1, ... , C_k\}</math>

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

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

Участник:Nkrivenko/Алгоритм кластеризации категориальных данных

2016-10-15T20:47:16Z

Nkrivenko: /* Ресурс параллелизма алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Данный алгоритм предназначен для кластеризации очень больших объемов данных. К особенностям алгоритма относятся использование глобального критерия оптимизации на основе максимизации коэффициента высоты гистограммы кластера и минимальное число сканирований наборов данных. Количество кластеров подбирается автоматически, что регулируется единственным параметром - коэффициентом отталкивания.
=== Математическое описание алгоритма ===
Пусть имеется база транзакций <math>D</math>, которая состоит из множества транзакций <math>\{t_1, ..., t_n\}</math>. Каждая из транзакций суть набор объектов <math>\{i_1, ..., i_n\}</math>. Множество кластеров <math>\{C_1, ..., C_m\}</math> есть разбиение множества транзакций таким образом, что <math>C_1 \oplus ... \oplus C_m = D</math>. У каждого кластера есть следующие характеристики:

1. Множество уникальных объектов <math>D(C)</math>.

2. <math>Occ(i, C)</math> - количество вхождений объекта <math>i</math> в кластер <math>C</math>

3. <math>S(C) = \sum_{i \in D(C)}{Occ(i,c)} = \sum_{i=1}^{m}{|t_i|}</math> - площадь кластера

4. <math>W(C) = |D(C)|</math> - ширина кластера,

5. <math>H(C) = S(C) / W(C)</math> - уровень сходства.

Функция стоимости:

<math>Profit(C, r) = \frac{\sum_{i=1}^{k}{\frac{S(C_i)}{W^r (C_i)}|C_i|}}{\sum_{i=1}^{k}{|C_i|}}</math>,

где <math>r, 0 < r \leq 1</math> - коэффициент отталкивания.

С помощью параметра <math>r</math> регулируется уровень сходства
транзакций внутри кластера, и, как следствие, финальное количество кластеров.
Этот коэффициент подбирается пользователем.
Чем больше <math>r</math>, тем ниже уровень сходства и тем больше кластеров будет сгенерировано.

Формальная постановка задачи кластеризации выглядит следующим образом:

<math> Profit(C, r) \to max </math>

=== Вычислительное ядро алгоритма ===
Вычислительным ядром алгоритма является оптимизация функции стоимости.

<math> Profit(C, r) \to max </math>

Оптимизация функции может проводиться любым известным методом, например, градиентными методами.

=== Макроструктура алгоритма ===
Как указано выше, основную часть метода составляет вычисление максимума функции стоимости.

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

Реализация алгоритма требует первого прохода по таблице транзакций для построения начального разбиения, определяемого функцией <math>Profit(C,r)</math>. После этого требуется некоторое количество дополнительных сканирований таблицы для повышения качества кластеризации и оптимизации функции стоимости. Если в текущем проходе по таблице изменений не произошло, то алгоритм прекращает свою работу

1. Пока не конец

1.1 прочитать из таблицы следующую транзакцию [t, -];

1.2 положить t в существующий либо в новый кластер <math>C_i</math>, который дает максимум <math>Profit(C,r)</math>;

1.3 записать [t,i] в таблицу (номер кластера);

2. Повторять

2.1 перейти в начало таблицы;

2.2 moved = false;

2.3 пока не конец таблицы

2.3.1 читать [t,i];

2.3.2 положить t в существующий либо в новый кластер <math>C_j</math>, который максимизирует <math>Profit(C,r)</math>;

2.3.3 если <math>C_i \neq C_j</math> тогда

2.3.3.1 записать [t,i];

2.3.4 moved = true;

2.4 пока (not moved).

3. удалить все пустые кластеры;

=== Последовательная сложность алгоритма ===
Пусть средняя длина транзакции равна <math>A</math>, общее число транзакций <math>N</math>, максимально возможное число кластеров <math>K</math>. Временная сложность одной итерации равна <math>O(N*K*A)</math>, показывающая, что скорость работы алгоритма растет линейно с ростом кластеров и размера таблицы. Это делает алгоритм быстрым и эффективным на больших объемах.

=== Информационный граф алгоритма ===
=== Ресурс параллелизма алгоритма ===
Алгоритм CLOPE является масштабируемым, поскольку можно читать данные из таблицы и распределять их по кластерам с подсчетом функции стоимости параллельно.

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

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

Участник:Nkrivenko/Алгоритм кластеризации категориальных данных

2016-10-15T20:37:44Z

Nkrivenko:

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Данный алгоритм предназначен для кластеризации очень больших объемов данных. К особенностям алгоритма относятся использование глобального критерия оптимизации на основе максимизации коэффициента высоты гистограммы кластера и минимальное число сканирований наборов данных. Количество кластеров подбирается автоматически, что регулируется единственным параметром - коэффициентом отталкивания.
=== Математическое описание алгоритма ===
Пусть имеется база транзакций <math>D</math>, которая состоит из множества транзакций <math>\{t_1, ..., t_n\}</math>. Каждая из транзакций суть набор объектов <math>\{i_1, ..., i_n\}</math>. Множество кластеров <math>\{C_1, ..., C_m\}</math> есть разбиение множества транзакций таким образом, что <math>C_1 \oplus ... \oplus C_m = D</math>. У каждого кластера есть следующие характеристики:

1. Множество уникальных объектов <math>D(C)</math>.

2. <math>Occ(i, C)</math> - количество вхождений объекта <math>i</math> в кластер <math>C</math>

3. <math>S(C) = \sum_{i \in D(C)}{Occ(i,c)} = \sum_{i=1}^{m}{|t_i|}</math> - площадь кластера

4. <math>W(C) = |D(C)|</math> - ширина кластера,

5. <math>H(C) = S(C) / W(C)</math> - уровень сходства.

Функция стоимости:

<math>Profit(C, r) = \frac{\sum_{i=1}^{k}{\frac{S(C_i)}{W^r (C_i)}|C_i|}}{\sum_{i=1}^{k}{|C_i|}}</math>,

где <math>r, 0 < r \leq 1</math> - коэффициент отталкивания.

С помощью параметра <math>r</math> регулируется уровень сходства
транзакций внутри кластера, и, как следствие, финальное количество кластеров.
Этот коэффициент подбирается пользователем.
Чем больше <math>r</math>, тем ниже уровень сходства и тем больше кластеров будет сгенерировано.

Формальная постановка задачи кластеризации выглядит следующим образом:

<math> Profit(C, r) \to max </math>

=== Вычислительное ядро алгоритма ===
Вычислительным ядром алгоритма является оптимизация функции стоимости.

<math> Profit(C, r) \to max </math>

Оптимизация функции может проводиться любым известным методом, например, градиентными методами.

=== Макроструктура алгоритма ===
Как указано выше, основную часть метода составляет вычисление максимума функции стоимости.

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

Реализация алгоритма требует первого прохода по таблице транзакций для построения начального разбиения, определяемого функцией <math>Profit(C,r)</math>. После этого требуется некоторое количество дополнительных сканирований таблицы для повышения качества кластеризации и оптимизации функции стоимости. Если в текущем проходе по таблице изменений не произошло, то алгоритм прекращает свою работу

1. Пока не конец

1.1 прочитать из таблицы следующую транзакцию [t, -];

1.2 положить t в существующий либо в новый кластер <math>C_i</math>, который дает максимум <math>Profit(C,r)</math>;

1.3 записать [t,i] в таблицу (номер кластера);

2. Повторять

2.1 перейти в начало таблицы;

2.2 moved = false;

2.3 пока не конец таблицы

2.3.1 читать [t,i];

2.3.2 положить t в существующий либо в новый кластер <math>C_j</math>, который максимизирует <math>Profit(C,r)</math>;

2.3.3 если <math>C_i \neq C_j</math> тогда

2.3.3.1 записать [t,i];

2.3.4 moved = true;

2.4 пока (not moved).

3. удалить все пустые кластеры;

=== Последовательная сложность алгоритма ===
Пусть средняя длина транзакции равна <math>A</math>, общее число транзакций <math>N</math>, максимально возможное число кластеров <math>K</math>. Временная сложность одной итерации равна <math>O(N*K*A)</math>, показывающая, что скорость работы алгоритма растет линейно с ростом кластеров и размера таблицы. Это делает алгоритм быстрым и эффективным на больших объемах.

=== Информационный граф алгоритма ===
=== Ресурс параллелизма алгоритма ===
=== Входные и выходные данные алгоритма ===
=== Свойства алгоритма ===

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

Участник:Nkrivenko/Алгоритм кластеризации категориальных данных

2016-10-15T14:53:22Z

Nkrivenko: Новая страница: «== Свойства и структура алгоритма == === Общее описание алгоритма === Данный алгоритм предна…»

Биномиальная модель оценки опционов

2016-05-16T11:20:09Z

Nkrivenko: /* Локальность данных и вычислений */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Биномиальная модель оценки опциона – итерационный метод, моделирующий цену опциона на временном отрезке, когда опцион действителен. Для некоторых типов опционов, например, американского, это единственный способ оценки, так как точное решение, позволяющее предсказать цену на всем временном отрезке, неизвестно.

Если быть точнее, биномиальная модель представляет эволюцию цены базового актива опциона как двоичное дерево всех возможных цен при равномерном разбиении временного отрезка с сегодняшнего дня, с предположением, что на каждом шаге цена может только расти либо падать на фиксированное число с соответствующими вероятностями <math>p_u</math> и <math>p_d</math>. Другими словами, корнем дерева является сегодняшняя цена базового актива, каждый уровень представляет собой все возможные цены в данный момент времени. У каждого узла со значением <math>S</math> есть два дочерних со значениями <math>Su</math> и <math>Sd, u,d</math> – множители движения цены вверх и вниз соответственно за один шаг по времени <math>dT</math>. <math>u</math> и <math>d</math> зависят от волатильности <math>\sigma</math>:

<math>u = e^{\sigma\sqrt{dT}}, d = e^{-\sigma\sqrt{dT}}, ud = 1.</math>

<math>p_d = 1 - p_u, p_u</math> ищется в предположении, что за <math>dT</math> доходность базового актива в среднем такая же, как и при отсутствии риска, то есть если в момент времени <math>t</math> стоимость базового актива <math>S</math>, то в момент времени <math>t + dT</math> она будет равна <math>Se^{rdT}</math>, где <math>r</math> - процентная ставка. Получается следующее уравнение:

<math>Se^{rdT} = (Su p_u + Sd p_d)</math>,

откуда <math>p_u = \frac{e^{rdT} - d}{u - d}.</math>

С помощью такого представления, можно получить цену в любом узле дерева. Для опциона "колл" она равна <math>V_{call} = max\{S - K, 0\}</math>, для "пут" <math>V_{put} = max\{K - S, 0\}</math>, <math>K</math> - страйк опциона. После расчета всех возможных цен опциона, начинается движение от листьев к корню по формуле

<math>V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT} (1)</math>,

где <math>V_t</math> - цена опциона в некотором узле, <math>V_{u, t+1}, V_{d, t+1}</math> - цены опциона в дочерних узлах.

=== Математическое описание алгоритма ===
Для реализации алгоритма потребуются две формулы:

1) <math>V_{T_i} = max\{Se^{V_sdT * 2i - N} - K, 0\}</math> - для расчета стоимости опциона в i-м листе дерева

2) <math>V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT}</math> - для расчета справедливой стоимости опциона

=== Вычислительное ядро алгоритма ===
Вычислительным ядром алгоритма является вычисление справедливой стоимости опциона. Для этого действия потребуется <math>\frac{N(N-1)}{2}</math> операций, где <math>N</math> - число шагов по времени.

=== Макроструктура алгоритма ===
Алгоритм состоит из двух шагов:

1. Генерация цен опциона в листьях.

2. Вычисление справедливой стоимости опциона по формуле <math>(1)</math>

=== Схема реализации последовательного алгоритма ===
На вход: количество этапов N, страйк K, цена базового актива на <math>t_0</math> S, волатильность базового актива sigma, шаг по времени dT, процентная ставка r.

1. Для i = 0, N:

1.1 price = S * exp(v * dT * (2 - i * N))

1.2 steps[i] = max(price - K, 0)

2. pu = (exp(r * dT) - exp(-sigma * sqrt(dT))) / (exp(sigma * sqrt(dT)) - exp(-sigma * sqrt(dT)))

3. pd = 1 - pu

4. Для i = N, 1

4.1 Для j = 0, i - 1

4.1.1 steps[j] = pu * steps[j + 1] + pd * steps[j]

=== Последовательная сложность алгоритма ===
Алгоритм требует <math>4N + 4 + N^2 - N = N^2 + 3N + 4</math> операций умножения, <math>N^2 + 2N + 3</math> операций вычитания, <math>N + 4</math> вычислений экспоненты, <math>N</math> вычислений максимума и 3 операции вычисления квадратного корня. В итоге, последовательная сложность алгоритма равна <math>2N^2 + 7N + 14</math> элементарных операций.

=== Информационный граф алгоритма ===
Информационный граф алгоритма изображен на рисунке 1

[[Файл:BOPM.png]]

=== Ресурс параллелизма алгоритма ===
Для вычисления значений справедливой стоимости опциона в листьях необходимо выполнить последовательно следующие ярусы:

1. Вычисление экспоненты

2. Умножение экспоненты на стоимость базового актива в момент времени <math>t_0</math>

При классификации по ширине ярусно-параллельной формы алгоритм имеет сложность <math>O(N)</math>. При классификации по высоте ЯПФ - <math>O(N)</math>

=== Входные и выходные данные алгоритма ===
Входные данные алгоритма, как было указано ранее, количество этапов <math>N</math>, страйк <math>K</math>, цена базового актива на <math>t_0</math> <math>S</math>, волатильность базового актива <math>\sigma</math>, шаг по времени <math>\Delta T</math>, процентная ставка <math>r</math>. На выходе получается справедливая стоимость опциона <math>C</math>.

=== Свойства алгоритма ===
Отношение последовательной и параллельной сложностей алгоритма в случае неограниченных ресурсов является линейным.

== Программная реализация алгоритма ==
=== Особенности последовательной реализации алгоритма ===
Код последовательной реализации на языке C может выглядеть так:
<pre>
#include <stdlib.h>
#include <float.h>
#include <math.h>

double price(int N, double K, double S, double vol, double dT, double r) {
double *steps = malloc(sizeof(double) * (N + 1));
for(int i = 0; i <= N; i++) {
double price = S * expf(vol * dT * (2. * i - N));
steps[i] = fmaxf(price - K, .0);
}

double pu = (expf(r * dT) - expf(-vol * sqrt(dT))) / (expf(vol * sqrt(dT)) - expf(-vol * sqrt(dT))), pd = 1 - pu;

for(int i = N; i > 0; i--)
for(int j = 0; j <= i - 1; j++)
steps[j] = pu * steps[j + 1] + pd * steps[j];

double C = steps[0];

free(steps);
steps = 0x0;

return C;
}
</pre>

=== Локальность данных и вычислений ===
Алгоритм обладает хорошей локальностью данных, так как при вычислении справедливой цены опциона используются соседние элементы массива.

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

=== Существующие реализации ===
Существует множество реализаций этой модели. [http://developer.download.nvidia.com/compute/cuda/1.1-Beta/x86_website/Computational_Finance.html#binomialOptions Одно из них] представлено в качестве примера для NVIDIA CUDA SDK. Оно используется здесь для исследований.

Реализацию алгоритма можно найти здесь: [https://github.com/warm35/binomial/tree/master/NVIDIA_CUDA_SDK]

Биномиальная модель оценки опционов

2016-05-16T11:17:19Z

Nkrivenko: /* Схема реализации последовательного алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Биномиальная модель оценки опциона – итерационный метод, моделирующий цену опциона на временном отрезке, когда опцион действителен. Для некоторых типов опционов, например, американского, это единственный способ оценки, так как точное решение, позволяющее предсказать цену на всем временном отрезке, неизвестно.

Если быть точнее, биномиальная модель представляет эволюцию цены базового актива опциона как двоичное дерево всех возможных цен при равномерном разбиении временного отрезка с сегодняшнего дня, с предположением, что на каждом шаге цена может только расти либо падать на фиксированное число с соответствующими вероятностями <math>p_u</math> и <math>p_d</math>. Другими словами, корнем дерева является сегодняшняя цена базового актива, каждый уровень представляет собой все возможные цены в данный момент времени. У каждого узла со значением <math>S</math> есть два дочерних со значениями <math>Su</math> и <math>Sd, u,d</math> – множители движения цены вверх и вниз соответственно за один шаг по времени <math>dT</math>. <math>u</math> и <math>d</math> зависят от волатильности <math>\sigma</math>:

<math>u = e^{\sigma\sqrt{dT}}, d = e^{-\sigma\sqrt{dT}}, ud = 1.</math>

<math>p_d = 1 - p_u, p_u</math> ищется в предположении, что за <math>dT</math> доходность базового актива в среднем такая же, как и при отсутствии риска, то есть если в момент времени <math>t</math> стоимость базового актива <math>S</math>, то в момент времени <math>t + dT</math> она будет равна <math>Se^{rdT}</math>, где <math>r</math> - процентная ставка. Получается следующее уравнение:

<math>Se^{rdT} = (Su p_u + Sd p_d)</math>,

откуда <math>p_u = \frac{e^{rdT} - d}{u - d}.</math>

С помощью такого представления, можно получить цену в любом узле дерева. Для опциона "колл" она равна <math>V_{call} = max\{S - K, 0\}</math>, для "пут" <math>V_{put} = max\{K - S, 0\}</math>, <math>K</math> - страйк опциона. После расчета всех возможных цен опциона, начинается движение от листьев к корню по формуле

<math>V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT} (1)</math>,

где <math>V_t</math> - цена опциона в некотором узле, <math>V_{u, t+1}, V_{d, t+1}</math> - цены опциона в дочерних узлах.

=== Математическое описание алгоритма ===
Для реализации алгоритма потребуются две формулы:

1) <math>V_{T_i} = max\{Se^{V_sdT * 2i - N} - K, 0\}</math> - для расчета стоимости опциона в i-м листе дерева

2) <math>V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT}</math> - для расчета справедливой стоимости опциона

=== Вычислительное ядро алгоритма ===
Вычислительным ядром алгоритма является вычисление справедливой стоимости опциона. Для этого действия потребуется <math>\frac{N(N-1)}{2}</math> операций, где <math>N</math> - число шагов по времени.

=== Макроструктура алгоритма ===
Алгоритм состоит из двух шагов:

1. Генерация цен опциона в листьях.

2. Вычисление справедливой стоимости опциона по формуле <math>(1)</math>

=== Схема реализации последовательного алгоритма ===
На вход: количество этапов N, страйк K, цена базового актива на <math>t_0</math> S, волатильность базового актива sigma, шаг по времени dT, процентная ставка r.

1. Для i = 0, N:

1.1 price = S * exp(v * dT * (2 - i * N))

1.2 steps[i] = max(price - K, 0)

2. pu = (exp(r * dT) - exp(-sigma * sqrt(dT))) / (exp(sigma * sqrt(dT)) - exp(-sigma * sqrt(dT)))

3. pd = 1 - pu

4. Для i = N, 1

4.1 Для j = 0, i - 1

4.1.1 steps[j] = pu * steps[j + 1] + pd * steps[j]

=== Последовательная сложность алгоритма ===
Алгоритм требует <math>4N + 4 + N^2 - N = N^2 + 3N + 4</math> операций умножения, <math>N^2 + 2N + 3</math> операций вычитания, <math>N + 4</math> вычислений экспоненты, <math>N</math> вычислений максимума и 3 операции вычисления квадратного корня. В итоге, последовательная сложность алгоритма равна <math>2N^2 + 7N + 14</math> элементарных операций.

=== Информационный граф алгоритма ===
Информационный граф алгоритма изображен на рисунке 1

[[Файл:BOPM.png]]

=== Ресурс параллелизма алгоритма ===
Для вычисления значений справедливой стоимости опциона в листьях необходимо выполнить последовательно следующие ярусы:

1. Вычисление экспоненты

2. Умножение экспоненты на стоимость базового актива в момент времени <math>t_0</math>

При классификации по ширине ярусно-параллельной формы алгоритм имеет сложность <math>O(N)</math>. При классификации по высоте ЯПФ - <math>O(N)</math>

=== Входные и выходные данные алгоритма ===
Входные данные алгоритма, как было указано ранее, количество этапов <math>N</math>, страйк <math>K</math>, цена базового актива на <math>t_0</math> <math>S</math>, волатильность базового актива <math>\sigma</math>, шаг по времени <math>\Delta T</math>, процентная ставка <math>r</math>. На выходе получается справедливая стоимость опциона <math>C</math>.

=== Свойства алгоритма ===
Отношение последовательной и параллельной сложностей алгоритма в случае неограниченных ресурсов является линейным.

== Программная реализация алгоритма ==
=== Особенности последовательной реализации алгоритма ===
Код последовательной реализации на языке C может выглядеть так:
<pre>
#include <stdlib.h>
#include <float.h>
#include <math.h>

double price(int N, double K, double S, double vol, double dT, double r) {
double *steps = malloc(sizeof(double) * (N + 1));
for(int i = 0; i <= N; i++) {
double price = S * expf(vol * dT * (2. * i - N));
steps[i] = fmaxf(price - K, .0);
}

double pu = (expf(r * dT) - expf(-vol * sqrt(dT))) / (expf(vol * sqrt(dT)) - expf(-vol * sqrt(dT))), pd = 1 - pu;

for(int i = N; i > 0; i--)
for(int j = 0; j <= i - 1; j++)
steps[j] = pu * steps[j + 1] + pd * steps[j];

double C = steps[0];

free(steps);
steps = 0x0;

return C;
}
</pre>

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

=== Существующие реализации ===
Существует множество реализаций этой модели. [http://developer.download.nvidia.com/compute/cuda/1.1-Beta/x86_website/Computational_Finance.html#binomialOptions Одно из них] представлено в качестве примера для NVIDIA CUDA SDK. Оно используется здесь для исследований.

Реализацию алгоритма можно найти здесь: [https://github.com/warm35/binomial/tree/master/NVIDIA_CUDA_SDK]

Биномиальная модель оценки опционов

2016-05-16T11:15:19Z

Nkrivenko: /* Существующие реализации */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Биномиальная модель оценки опциона – итерационный метод, моделирующий цену опциона на временном отрезке, когда опцион действителен. Для некоторых типов опционов, например, американского, это единственный способ оценки, так как точное решение, позволяющее предсказать цену на всем временном отрезке, неизвестно.

Если быть точнее, биномиальная модель представляет эволюцию цены базового актива опциона как двоичное дерево всех возможных цен при равномерном разбиении временного отрезка с сегодняшнего дня, с предположением, что на каждом шаге цена может только расти либо падать на фиксированное число с соответствующими вероятностями <math>p_u</math> и <math>p_d</math>. Другими словами, корнем дерева является сегодняшняя цена базового актива, каждый уровень представляет собой все возможные цены в данный момент времени. У каждого узла со значением <math>S</math> есть два дочерних со значениями <math>Su</math> и <math>Sd, u,d</math> – множители движения цены вверх и вниз соответственно за один шаг по времени <math>dT</math>. <math>u</math> и <math>d</math> зависят от волатильности <math>\sigma</math>:

<math>u = e^{\sigma\sqrt{dT}}, d = e^{-\sigma\sqrt{dT}}, ud = 1.</math>

<math>p_d = 1 - p_u, p_u</math> ищется в предположении, что за <math>dT</math> доходность базового актива в среднем такая же, как и при отсутствии риска, то есть если в момент времени <math>t</math> стоимость базового актива <math>S</math>, то в момент времени <math>t + dT</math> она будет равна <math>Se^{rdT}</math>, где <math>r</math> - процентная ставка. Получается следующее уравнение:

<math>Se^{rdT} = (Su p_u + Sd p_d)</math>,

откуда <math>p_u = \frac{e^{rdT} - d}{u - d}.</math>

С помощью такого представления, можно получить цену в любом узле дерева. Для опциона "колл" она равна <math>V_{call} = max\{S - K, 0\}</math>, для "пут" <math>V_{put} = max\{K - S, 0\}</math>, <math>K</math> - страйк опциона. После расчета всех возможных цен опциона, начинается движение от листьев к корню по формуле

<math>V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT} (1)</math>,

где <math>V_t</math> - цена опциона в некотором узле, <math>V_{u, t+1}, V_{d, t+1}</math> - цены опциона в дочерних узлах.

=== Математическое описание алгоритма ===
Для реализации алгоритма потребуются две формулы:

1) <math>V_{T_i} = max\{Se^{V_sdT * 2i - N} - K, 0\}</math> - для расчета стоимости опциона в i-м листе дерева

2) <math>V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT}</math> - для расчета справедливой стоимости опциона

=== Вычислительное ядро алгоритма ===
Вычислительным ядром алгоритма является вычисление справедливой стоимости опциона. Для этого действия потребуется <math>\frac{N(N-1)}{2}</math> операций, где <math>N</math> - число шагов по времени.

=== Макроструктура алгоритма ===
Алгоритм состоит из двух шагов:

1. Генерация цен опциона в листьях.

2. Вычисление справедливой стоимости опциона по формуле <math>(1)</math>

=== Схема реализации последовательного алгоритма ===
На вход: количество этапов N, страйк K, цена базового актива на <math>t_0</math> S, волатильность базового актива v, шаг по времени dT, процентная ставка r.

1. Для i = 0, N:

1.1 price = S * exp(v * dT * (2 - i * N))

1.2 steps[i] = max(price - K, 0)

2. pu = (exp(r * dT) - exp(-sigma * sqrt(dT))) / (exp(sigma * sqrt(dT)) - exp(-sigma * sqrt(dT)))

3. pd = 1 - pu

4. Для i = N, 1

4.1 Для j = 0, i - 1

4.1.1 steps[j] = pu * steps[j + 1] + pd * steps[j]

=== Последовательная сложность алгоритма ===
Алгоритм требует <math>4N + 4 + N^2 - N = N^2 + 3N + 4</math> операций умножения, <math>N^2 + 2N + 3</math> операций вычитания, <math>N + 4</math> вычислений экспоненты, <math>N</math> вычислений максимума и 3 операции вычисления квадратного корня. В итоге, последовательная сложность алгоритма равна <math>2N^2 + 7N + 14</math> элементарных операций.

=== Информационный граф алгоритма ===
Информационный граф алгоритма изображен на рисунке 1

[[Файл:BOPM.png]]

=== Ресурс параллелизма алгоритма ===
Для вычисления значений справедливой стоимости опциона в листьях необходимо выполнить последовательно следующие ярусы:

1. Вычисление экспоненты

2. Умножение экспоненты на стоимость базового актива в момент времени <math>t_0</math>

При классификации по ширине ярусно-параллельной формы алгоритм имеет сложность <math>O(N)</math>. При классификации по высоте ЯПФ - <math>O(N)</math>

=== Входные и выходные данные алгоритма ===
Входные данные алгоритма, как было указано ранее, количество этапов <math>N</math>, страйк <math>K</math>, цена базового актива на <math>t_0</math> <math>S</math>, волатильность базового актива <math>\sigma</math>, шаг по времени <math>\Delta T</math>, процентная ставка <math>r</math>. На выходе получается справедливая стоимость опциона <math>C</math>.

=== Свойства алгоритма ===
Отношение последовательной и параллельной сложностей алгоритма в случае неограниченных ресурсов является линейным.

== Программная реализация алгоритма ==
=== Особенности последовательной реализации алгоритма ===
Код последовательной реализации на языке C может выглядеть так:
<pre>
#include <stdlib.h>
#include <float.h>
#include <math.h>

double price(int N, double K, double S, double vol, double dT, double r) {
double *steps = malloc(sizeof(double) * (N + 1));
for(int i = 0; i <= N; i++) {
double price = S * expf(vol * dT * (2. * i - N));
steps[i] = fmaxf(price - K, .0);
}

double pu = (expf(r * dT) - expf(-vol * sqrt(dT))) / (expf(vol * sqrt(dT)) - expf(-vol * sqrt(dT))), pd = 1 - pu;

for(int i = N; i > 0; i--)
for(int j = 0; j <= i - 1; j++)
steps[j] = pu * steps[j + 1] + pd * steps[j];

double C = steps[0];

free(steps);
steps = 0x0;

return C;
}
</pre>

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

=== Существующие реализации ===
Существует множество реализаций этой модели. [http://developer.download.nvidia.com/compute/cuda/1.1-Beta/x86_website/Computational_Finance.html#binomialOptions Одно из них] представлено в качестве примера для NVIDIA CUDA SDK. Оно используется здесь для исследований.

Реализацию алгоритма можно найти здесь: [https://github.com/warm35/binomial/tree/master/NVIDIA_CUDA_SDK]

Применение методов Монте-Карло для оценки опционов европейского типа

2016-05-16T11:01:38Z

Nkrivenko: /* Существующие реализации */

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

Рассмотрим эволюционирующий в непрерывном времени финансовый рынок, состоящий из двух типов активов: акции (рисковые активы, S) и облигации (безрисковые активы, B). Для моделирования рынка будем использовать модель Блэка–Шоулса. Данная модель после ряда преобразований представляет собой систему стохастических дифференциальных уравнений следующего вида:

<math>dB_t = rB_tdt, B_0 > 0, (1)</math>

<math>dS_t = S_t((r-\delta)dt - \sigma dW_t), S_0 > 0. (2)</math>

Здесь первое уравнение представляет собой обыкновенное дифференциальное уравнение, описывающее поведение цены облигации <math>B_t</math>, на изменение которой влияет процентная ставка <math>r</math>. Уравнение (2) является стохастическим дифференциальным уравнением, описывающим эволюцию цены акции <math>S_t</math>. В этом уравнении: <math>\sigma</math> - волатильность акции, <math>\delta</math> - ставка дивиденда, <math>W_t</math> - винеровский случайный процесс.

Сделаем несколько предположений касательно рынка:

1. пусть модель будет без дивидендов: <math>\delta = 0</math>;

2. процентные ставки постоянны;

3. если время измеряется в годах, то все рассмотренные процентные ставки участвуют в уравнениях как числа от 0 до 1 и выражают проценты годовых, измеренные в долях.

При этих предположениях рассмотренная система имеет аналитическое решение:

<math>S_t = S_0 e^{(r - \sigma^2/2)t + \sigma W_t}</math>.

Опцион, как производный финансовый инструмент, представляет собой контракт между сторонами <math>P_1</math> и <math>P_2</math>, который дает право стороне <math>P_2</math> в некоторый момент времени <math>t</math> в будущем купить у стороны <math>P_1</math> или продать стороне <math>P_1</math> акции по зафиксированной в контракте цене <math>K</math>. За это право сторона <math>P_2</math> выплачивает фиксированную сумму (премию) <math>C</math> стороне <math>P_1</math>. При этом K называется ценой исполнения опциона (страйк, strike price), а <math>C</math> – ценой опциона.

Основная идея заключения контракта состоит в игре двух лиц – <math>P_1</math> и <math>P_2</math>. Вторая сторона выплачивает некоторую сумму <math>C</math> и в некоторый момент времени <math>T</math> (срок выплаты, зафиксированный в контракте) принимает решение: покупать акции по цене <math>K</math> у первой стороны или нет. Решение принимается в зависимости от соотношения цены <math>S_T</math> и <math>K</math>. Если <math>S_T < K</math>, покупать акции не выгодно, сторона <math>P_1</math> получила прибыль <math>C</math>, а <math>P_2</math> – убыток <math>C</math>. В случае, если <math>S_T > K</math>, сторона <math>P_2</math> покупает у первой акции по цене <math>K</math>, в ряде случаев получая прибыль.

Справедливая цена опциона – цена, при которой наблюдается баланс выигрыша/проигрыша каждой из сторон. Определяется она как средний выигрыш стороны <math>P_2</math>:

<math>C = \mathop{\mathbb{E}}(e^{-rT} max\{S_T - K, 0\})</math>.

Точное решение этой системы уравнений известно:

<math>C = S_0N(d_1) - Ke^{-rT}N(d_2),</math>

<math>d_1 = ln{\frac{S_0}{K}} + \frac{(r + \sigma^2 / 2)T}{\sigma\sqrt{T}},</math>

<math>d_2 = d_1 - \sigma\sqrt{T}.</math>

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

=== Математическое описание алгоритма ===
Решаемая задача имеет следующий вид:

<math>C = e^{-rT}\int^{+\infty}_{-\infty}{f(z)\varphi(z)dz}, (3)</math>

<math>f(z) = max\{S_0 e^{(r - \sigma^2/2)T + \sigma\sqrt{T}z} - K, 0\}, (4)</math>

<math>\varphi(z) = \frac{1}{\sqrt{2\pi}} e^{-z^2/2}.</math>

Для вычисления этого интеграла будем использовать метод Монте-Карло. Если мы рассмотрим случайную величину <math>X = f(z)</math>, то математическое ожидание этой случайной величины будет совпадать с формулой (3) с точностью до коэффициента дисконтирования. Формула для вычисления искомого интеграла имеет вид:

<math>\hat{C} = \frac{e^{-rT}}{N} \sum^{N}_{i=1}{f(z_i)},</math>

<math>f(z_i) = max\{S_0 e^{(r - \sigma^2/2)T + \sigma\sqrt{T}z} - K, 0\}, z_i \sim N_{0,1}.</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма составляет вычисление следующей суммы:

<math>\sum^{N}_{i=1}{f(z_i)}.</math>

Поскольку время, требуемое на операцию сложения в реальных примерах мало по сравнению с временем, затрачиваемом на вычисление функции <math>f(z_i)</math>, для производительности вычислений становится маловажным, каким конкретным образом осуществлять сложение и умножение.

=== Макроструктура алгоритма ===
Алгоритм представляет собой сумму значений функции от случайной величины.
=== Схема последовательной реализации алгоритма ===
Формулы для реализации алгоритма приведены выше <math>(1)</math>. С помощью генератора случайных чисел в цикле получаются точки, и в них вычисляется соответствующая функция. Результаты складываются, полученная сумма умножается на коэффициент. При последовательной реализации для экономии памяти можно сразу не генерировать массив всех точек, в которых должна быть вычислена функция, а получать их последовательно.
=== Последовательная сложность алгоритма ===
Время, затраченное на вычисление интеграла растет как <math>Nt</math>, где <math>N</math> – количество случайных точек, <math>t</math> – время, необходимое для вычисления функции.
=== Информационный граф алгоритма ===
Информационный граф алгоритма представлен на рисунке 1,

[[Файл: MCG.png]]

Рисунок 1 – Информационный граф алгоритма

где вершина <math>f</math> – вычисление функции <math>f(z)</math>, <math>rnd</math> – генерация случайного числа. Анализ этого графа производится в последующих разделах описания алгоритма.

=== Ресурс параллелизма алгоритма ===
Для вычисления интеграла <math>(3)</math> методом Монте-Карло требуется последовательно выполнить следующие ярусы:

1) вычисление случайного числа <math>z</math>,

2) вычисление функции <math>f</math> на основании полученного случайного числа,

3) сложение полученных результатов.

В общем случае, все вычисления функции <math>f</math> могут производиться на разных узлах, следовательно, алгоритм идеально поддается распараллеливанию.
При классификации по высоте ярусно-параллельной формы этот алгоритм имеет сложность 3. При классификации по ширине – <math>O(N)</math>.

=== Входные и выходные данные алгоритма ===
Входные данные для вычисления алгоритма: число точек <math>N</math>, волатильность акции <math>\sigma</math>, время жизни опциона <math>T</math>, страйк <math>K</math>, процентная ставка <math>r</math>, стоимость акции в начальный момент времени <math>S_0</math>.
Выходные данные: справедливая цена опциона <math>C</math>.

=== Свойства алгоритма ===
Соотношение последовательной и параллельной сложностей в случае неограниченных ресурсов является линейным.

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

== Программная реализация алгоритма ==
=== Особенности последовательной реализации алгоритма ===
Код последовательной реализации на языке C может выглядеть так:
<pre>
double price(int N, double sigma, double T, double K, double S0, double r) {
coeff = exp(-r*T) / N, result = .0, sigma_coeff = (r - sigma * sigma / 2) * T, sigma_T_coeff = sigma * sqrt(T);
for (int i = 0; i < N; i++) {
result += max(0, S0 * exp(sigma_coeff + sigma_T_coeff * normalrand(i)) - K);
}
return coeff * result;
}
</pre>

Представленный алгоритм не является полностью детерминированным, так как он основан на использовании последовательностей случайных чисел.
=== Локальность данных и вычислений ===
Данные в представленном алгоритме обладают хорошей локальностью, так как на каждом шаге алгоритма приходится использовать значения переменных sigma_coeff и sigma_T_coeff, что повышает вероятность попадания этих значений в кэш.
=== Возможные способы и особенности реализации параллельного алгоритма ===
Один из возможных вариантов реализации алгоритма – независимое вычисление значений функции <math>f(z)</math> на различных вычислительных узлах, например, с помощью технологии MPI. «Подводным камнем» такой реализации может стать генерация случайных чисел, которая должна быть независимой на каждом вычислительном узле. Желательно использовать генератор случайных чисел с достаточно большим периодом.
=== Масштабируемость алгоритма и его реализации ===
Теоретические оценки показывают, что алгоритм должен быть хорошо масштабируем.
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
При достаточно большом числе точек N возможна реализация алгоритма на GPU для достижения большей скорости выполнения, чем на обычных процессорах.
=== Существующие реализации ===
Есть открытая реализация методов Монте-Карло, являющаяся частью GSL (GNU Scientific Library). Данная библиотека включает в себя как классический алгоритм, так и два адаптивных: «Vegas» и «Miser».

Реализация алгоритма доступна тут: [https://github.com/warm35/montecarlosingle/tree/master/NVIDIA_CUDA_SDK], в многокарточном варианте - тут: [https://github.com/warm35/montecarlomultigpu/tree/master/NVIDIA_CUDA_SDK]

Применение методов Монте-Карло для оценки опционов европейского типа

2016-05-16T10:05:11Z

Nkrivenko: /* Существующие реализации */

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

Рассмотрим эволюционирующий в непрерывном времени финансовый рынок, состоящий из двух типов активов: акции (рисковые активы, S) и облигации (безрисковые активы, B). Для моделирования рынка будем использовать модель Блэка–Шоулса. Данная модель после ряда преобразований представляет собой систему стохастических дифференциальных уравнений следующего вида:

<math>dB_t = rB_tdt, B_0 > 0, (1)</math>

<math>dS_t = S_t((r-\delta)dt - \sigma dW_t), S_0 > 0. (2)</math>

Здесь первое уравнение представляет собой обыкновенное дифференциальное уравнение, описывающее поведение цены облигации <math>B_t</math>, на изменение которой влияет процентная ставка <math>r</math>. Уравнение (2) является стохастическим дифференциальным уравнением, описывающим эволюцию цены акции <math>S_t</math>. В этом уравнении: <math>\sigma</math> - волатильность акции, <math>\delta</math> - ставка дивиденда, <math>W_t</math> - винеровский случайный процесс.

Сделаем несколько предположений касательно рынка:

1. пусть модель будет без дивидендов: <math>\delta = 0</math>;

2. процентные ставки постоянны;

3. если время измеряется в годах, то все рассмотренные процентные ставки участвуют в уравнениях как числа от 0 до 1 и выражают проценты годовых, измеренные в долях.

При этих предположениях рассмотренная система имеет аналитическое решение:

<math>S_t = S_0 e^{(r - \sigma^2/2)t + \sigma W_t}</math>.

Опцион, как производный финансовый инструмент, представляет собой контракт между сторонами <math>P_1</math> и <math>P_2</math>, который дает право стороне <math>P_2</math> в некоторый момент времени <math>t</math> в будущем купить у стороны <math>P_1</math> или продать стороне <math>P_1</math> акции по зафиксированной в контракте цене <math>K</math>. За это право сторона <math>P_2</math> выплачивает фиксированную сумму (премию) <math>C</math> стороне <math>P_1</math>. При этом K называется ценой исполнения опциона (страйк, strike price), а <math>C</math> – ценой опциона.

Основная идея заключения контракта состоит в игре двух лиц – <math>P_1</math> и <math>P_2</math>. Вторая сторона выплачивает некоторую сумму <math>C</math> и в некоторый момент времени <math>T</math> (срок выплаты, зафиксированный в контракте) принимает решение: покупать акции по цене <math>K</math> у первой стороны или нет. Решение принимается в зависимости от соотношения цены <math>S_T</math> и <math>K</math>. Если <math>S_T < K</math>, покупать акции не выгодно, сторона <math>P_1</math> получила прибыль <math>C</math>, а <math>P_2</math> – убыток <math>C</math>. В случае, если <math>S_T > K</math>, сторона <math>P_2</math> покупает у первой акции по цене <math>K</math>, в ряде случаев получая прибыль.

Справедливая цена опциона – цена, при которой наблюдается баланс выигрыша/проигрыша каждой из сторон. Определяется она как средний выигрыш стороны <math>P_2</math>:

<math>C = \mathop{\mathbb{E}}(e^{-rT} max\{S_T - K, 0\})</math>.

Точное решение этой системы уравнений известно:

<math>C = S_0N(d_1) - Ke^{-rT}N(d_2),</math>

<math>d_1 = ln{\frac{S_0}{K}} + \frac{(r + \sigma^2 / 2)T}{\sigma\sqrt{T}},</math>

<math>d_2 = d_1 - \sigma\sqrt{T}.</math>

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

=== Математическое описание алгоритма ===
Решаемая задача имеет следующий вид:

<math>C = e^{-rT}\int^{+\infty}_{-\infty}{f(z)\varphi(z)dz}, (3)</math>

<math>f(z) = max\{S_0 e^{(r - \sigma^2/2)T + \sigma\sqrt{T}z} - K, 0\}, (4)</math>

<math>\varphi(z) = \frac{1}{\sqrt{2\pi}} e^{-z^2/2}.</math>

Для вычисления этого интеграла будем использовать метод Монте-Карло. Если мы рассмотрим случайную величину <math>X = f(z)</math>, то математическое ожидание этой случайной величины будет совпадать с формулой (3) с точностью до коэффициента дисконтирования. Формула для вычисления искомого интеграла имеет вид:

<math>\hat{C} = \frac{e^{-rT}}{N} \sum^{N}_{i=1}{f(z_i)},</math>

<math>f(z_i) = max\{S_0 e^{(r - \sigma^2/2)T + \sigma\sqrt{T}z} - K, 0\}, z_i \sim N_{0,1}.</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма составляет вычисление следующей суммы:

<math>\sum^{N}_{i=1}{f(z_i)}.</math>

Поскольку время, требуемое на операцию сложения в реальных примерах мало по сравнению с временем, затрачиваемом на вычисление функции <math>f(z_i)</math>, для производительности вычислений становится маловажным, каким конкретным образом осуществлять сложение и умножение.

=== Макроструктура алгоритма ===
Алгоритм представляет собой сумму значений функции от случайной величины.
=== Схема последовательной реализации алгоритма ===
Формулы для реализации алгоритма приведены выше <math>(1)</math>. С помощью генератора случайных чисел в цикле получаются точки, и в них вычисляется соответствующая функция. Результаты складываются, полученная сумма умножается на коэффициент. При последовательной реализации для экономии памяти можно сразу не генерировать массив всех точек, в которых должна быть вычислена функция, а получать их последовательно.
=== Последовательная сложность алгоритма ===
Время, затраченное на вычисление интеграла растет как <math>Nt</math>, где <math>N</math> – количество случайных точек, <math>t</math> – время, необходимое для вычисления функции.
=== Информационный граф алгоритма ===
Информационный граф алгоритма представлен на рисунке 1,

[[Файл: MCG.png]]

Рисунок 1 – Информационный граф алгоритма

где вершина <math>f</math> – вычисление функции <math>f(z)</math>, <math>rnd</math> – генерация случайного числа. Анализ этого графа производится в последующих разделах описания алгоритма.

=== Ресурс параллелизма алгоритма ===
Для вычисления интеграла <math>(3)</math> методом Монте-Карло требуется последовательно выполнить следующие ярусы:

1) вычисление случайного числа <math>z</math>,

2) вычисление функции <math>f</math> на основании полученного случайного числа,

3) сложение полученных результатов.

В общем случае, все вычисления функции <math>f</math> могут производиться на разных узлах, следовательно, алгоритм идеально поддается распараллеливанию.
При классификации по высоте ярусно-параллельной формы этот алгоритм имеет сложность 3. При классификации по ширине – <math>O(N)</math>.

=== Входные и выходные данные алгоритма ===
Входные данные для вычисления алгоритма: число точек <math>N</math>, волатильность акции <math>\sigma</math>, время жизни опциона <math>T</math>, страйк <math>K</math>, процентная ставка <math>r</math>, стоимость акции в начальный момент времени <math>S_0</math>.
Выходные данные: справедливая цена опциона <math>C</math>.

=== Свойства алгоритма ===
Соотношение последовательной и параллельной сложностей в случае неограниченных ресурсов является линейным.

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

== Программная реализация алгоритма ==
=== Особенности последовательной реализации алгоритма ===
Код последовательной реализации на языке C может выглядеть так:
<pre>
double price(int N, double sigma, double T, double K, double S0, double r) {
coeff = exp(-r*T) / N, result = .0, sigma_coeff = (r - sigma * sigma / 2) * T, sigma_T_coeff = sigma * sqrt(T);
for (int i = 0; i < N; i++) {
result += max(0, S0 * exp(sigma_coeff + sigma_T_coeff * normalrand(i)) - K);
}
return coeff * result;
}
</pre>

Представленный алгоритм не является полностью детерминированным, так как он основан на использовании последовательностей случайных чисел.
=== Локальность данных и вычислений ===
Данные в представленном алгоритме обладают хорошей локальностью, так как на каждом шаге алгоритма приходится использовать значения переменных sigma_coeff и sigma_T_coeff, что повышает вероятность попадания этих значений в кэш.
=== Возможные способы и особенности реализации параллельного алгоритма ===
Один из возможных вариантов реализации алгоритма – независимое вычисление значений функции <math>f(z)</math> на различных вычислительных узлах, например, с помощью технологии MPI. «Подводным камнем» такой реализации может стать генерация случайных чисел, которая должна быть независимой на каждом вычислительном узле. Желательно использовать генератор случайных чисел с достаточно большим периодом.
=== Масштабируемость алгоритма и его реализации ===
Теоретические оценки показывают, что алгоритм должен быть хорошо масштабируем.
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
При достаточно большом числе точек N возможна реализация алгоритма на GPU для достижения большей скорости выполнения, чем на обычных процессорах.
=== Существующие реализации ===
Есть открытая реализация методов Монте-Карло, являющаяся частью GSL (GNU Scientific Library). Данная библиотека включает в себя как классический алгоритм, так и два адаптивных: «Vegas» и «Miser».

Реализация алгоритма доступна по адресу: [https://github.com/warm35/montecarlosingle/tree/master/NVIDIA_CUDA_SDK]

Биномиальная модель оценки опционов

2016-05-13T05:13:25Z

Nkrivenko: /* Существующие реализации */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Биномиальная модель оценки опциона – итерационный метод, моделирующий цену опциона на временном отрезке, когда опцион действителен. Для некоторых типов опционов, например, американского, это единственный способ оценки, так как точное решение, позволяющее предсказать цену на всем временном отрезке, неизвестно.

Если быть точнее, биномиальная модель представляет эволюцию цены базового актива опциона как двоичное дерево всех возможных цен при равномерном разбиении временного отрезка с сегодняшнего дня, с предположением, что на каждом шаге цена может только расти либо падать на фиксированное число с соответствующими вероятностями <math>p_u</math> и <math>p_d</math>. Другими словами, корнем дерева является сегодняшняя цена базового актива, каждый уровень представляет собой все возможные цены в данный момент времени. У каждого узла со значением <math>S</math> есть два дочерних со значениями <math>Su</math> и <math>Sd, u,d</math> – множители движения цены вверх и вниз соответственно за один шаг по времени <math>dT</math>. <math>u</math> и <math>d</math> зависят от волатильности <math>\sigma</math>:

<math>u = e^{\sigma\sqrt{dT}}, d = e^{-\sigma\sqrt{dT}}, ud = 1.</math>

<math>p_d = 1 - p_u, p_u</math> ищется в предположении, что за <math>dT</math> доходность базового актива в среднем такая же, как и при отсутствии риска, то есть если в момент времени <math>t</math> стоимость базового актива <math>S</math>, то в момент времени <math>t + dT</math> она будет равна <math>Se^{rdT}</math>, где <math>r</math> - процентная ставка. Получается следующее уравнение:

<math>Se^{rdT} = (Su p_u + Sd p_d)</math>,

откуда <math>p_u = \frac{e^{rdT} - d}{u - d}.</math>

С помощью такого представления, можно получить цену в любом узле дерева. Для опциона "колл" она равна <math>V_{call} = max\{S - K, 0\}</math>, для "пут" <math>V_{put} = max\{K - S, 0\}</math>, <math>K</math> - страйк опциона. После расчета всех возможных цен опциона, начинается движение от листьев к корню по формуле

<math>V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT} (1)</math>,

где <math>V_t</math> - цена опциона в некотором узле, <math>V_{u, t+1}, V_{d, t+1}</math> - цены опциона в дочерних узлах.

=== Математическое описание алгоритма ===
Для реализации алгоритма потребуются две формулы:

1) <math>V_{T_i} = max\{Se^{V_sdT * 2i - N} - K, 0\}</math> - для расчета стоимости опциона в i-м листе дерева

2) <math>V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT}</math> - для расчета справедливой стоимости опциона

=== Вычислительное ядро алгоритма ===
Вычислительным ядром алгоритма является вычисление справедливой стоимости опциона. Для этого действия потребуется <math>\frac{N(N-1)}{2}</math> операций, где <math>N</math> - число шагов по времени.

=== Макроструктура алгоритма ===
Алгоритм состоит из двух шагов:

1. Генерация цен опциона в листьях.

2. Вычисление справедливой стоимости опциона по формуле <math>(1)</math>

=== Схема реализации последовательного алгоритма ===
На вход: количество этапов N, страйк K, цена базового актива на <math>t_0</math> S, волатильность базового актива v, шаг по времени dT, процентная ставка r.

1. Для i = 0, N:

1.1 price = S * exp(v * dT * (2 - i * N))

1.2 steps[i] = max(price - K, 0)

2. pu = (exp(r * dT) - exp(-sigma * sqrt(dT))) / (exp(sigma * sqrt(dT)) - exp(-sigma * sqrt(dT)))

3. pd = 1 - pu

4. Для i = N, 1

4.1 Для j = 0, i - 1

4.1.1 steps[j] = pu * steps[j + 1] + pd * steps[j]

=== Последовательная сложность алгоритма ===
Алгоритм требует <math>4N + 4 + N^2 - N = N^2 + 3N + 4</math> операций умножения, <math>N^2 + 2N + 3</math> операций вычитания, <math>N + 4</math> вычислений экспоненты, <math>N</math> вычислений максимума и 3 операции вычисления квадратного корня. В итоге, последовательная сложность алгоритма равна <math>2N^2 + 7N + 14</math> элементарных операций.

=== Информационный граф алгоритма ===
Информационный граф алгоритма изображен на рисунке 1

[[Файл:BOPM.png]]

=== Ресурс параллелизма алгоритма ===
Для вычисления значений справедливой стоимости опциона в листьях необходимо выполнить последовательно следующие ярусы:

1. Вычисление экспоненты

2. Умножение экспоненты на стоимость базового актива в момент времени <math>t_0</math>

При классификации по ширине ярусно-параллельной формы алгоритм имеет сложность <math>O(N)</math>. При классификации по высоте ЯПФ - <math>O(N)</math>

=== Входные и выходные данные алгоритма ===
Входные данные алгоритма, как было указано ранее, количество этапов <math>N</math>, страйк <math>K</math>, цена базового актива на <math>t_0</math> <math>S</math>, волатильность базового актива <math>\sigma</math>, шаг по времени <math>\Delta T</math>, процентная ставка <math>r</math>. На выходе получается справедливая стоимость опциона <math>C</math>.

=== Свойства алгоритма ===
Отношение последовательной и параллельной сложностей алгоритма в случае неограниченных ресурсов является линейным.

== Программная реализация алгоритма ==
=== Особенности последовательной реализации алгоритма ===
Код последовательной реализации на языке C может выглядеть так:
<pre>
#include <stdlib.h>
#include <float.h>
#include <math.h>

double price(int N, double K, double S, double vol, double dT, double r) {
double *steps = malloc(sizeof(double) * (N + 1));
for(int i = 0; i <= N; i++) {
double price = S * expf(vol * dT * (2. * i - N));
steps[i] = fmaxf(price - K, .0);
}

double pu = (expf(r * dT) - expf(-vol * sqrt(dT))) / (expf(vol * sqrt(dT)) - expf(-vol * sqrt(dT))), pd = 1 - pu;

for(int i = N; i > 0; i--)
for(int j = 0; j <= i - 1; j++)
steps[j] = pu * steps[j + 1] + pd * steps[j];

double C = steps[0];

free(steps);
steps = 0x0;

return C;
}
</pre>

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

=== Существующие реализации ===
Существует множество реализаций этой модели. [http://developer.download.nvidia.com/compute/cuda/1.1-Beta/x86_website/Computational_Finance.html#binomialOptions Одно из них] представлено в качестве примера для NVIDIA CUDA SDK. Оно используется здесь для исследований.

Биномиальная модель оценки опционов

2016-05-13T04:44:49Z

Nkrivenko: /* Выводы для классов архитектур */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Биномиальная модель оценки опциона – итерационный метод, моделирующий цену опциона на временном отрезке, когда опцион действителен. Для некоторых типов опционов, например, американского, это единственный способ оценки, так как точное решение, позволяющее предсказать цену на всем временном отрезке, неизвестно.

Если быть точнее, биномиальная модель представляет эволюцию цены базового актива опциона как двоичное дерево всех возможных цен при равномерном разбиении временного отрезка с сегодняшнего дня, с предположением, что на каждом шаге цена может только расти либо падать на фиксированное число с соответствующими вероятностями <math>p_u</math> и <math>p_d</math>. Другими словами, корнем дерева является сегодняшняя цена базового актива, каждый уровень представляет собой все возможные цены в данный момент времени. У каждого узла со значением <math>S</math> есть два дочерних со значениями <math>Su</math> и <math>Sd, u,d</math> – множители движения цены вверх и вниз соответственно за один шаг по времени <math>dT</math>. <math>u</math> и <math>d</math> зависят от волатильности <math>\sigma</math>:

<math>u = e^{\sigma\sqrt{dT}}, d = e^{-\sigma\sqrt{dT}}, ud = 1.</math>

<math>p_d = 1 - p_u, p_u</math> ищется в предположении, что за <math>dT</math> доходность базового актива в среднем такая же, как и при отсутствии риска, то есть если в момент времени <math>t</math> стоимость базового актива <math>S</math>, то в момент времени <math>t + dT</math> она будет равна <math>Se^{rdT}</math>, где <math>r</math> - процентная ставка. Получается следующее уравнение:

<math>Se^{rdT} = (Su p_u + Sd p_d)</math>,

откуда <math>p_u = \frac{e^{rdT} - d}{u - d}.</math>

С помощью такого представления, можно получить цену в любом узле дерева. Для опциона "колл" она равна <math>V_{call} = max\{S - K, 0\}</math>, для "пут" <math>V_{put} = max\{K - S, 0\}</math>, <math>K</math> - страйк опциона. После расчета всех возможных цен опциона, начинается движение от листьев к корню по формуле

<math>V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT} (1)</math>,

где <math>V_t</math> - цена опциона в некотором узле, <math>V_{u, t+1}, V_{d, t+1}</math> - цены опциона в дочерних узлах.

=== Математическое описание алгоритма ===
Для реализации алгоритма потребуются две формулы:

1) <math>V_{T_i} = max\{Se^{V_sdT * 2i - N} - K, 0\}</math> - для расчета стоимости опциона в i-м листе дерева

2) <math>V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT}</math> - для расчета справедливой стоимости опциона

=== Вычислительное ядро алгоритма ===
Вычислительным ядром алгоритма является вычисление справедливой стоимости опциона. Для этого действия потребуется <math>\frac{N(N-1)}{2}</math> операций, где <math>N</math> - число шагов по времени.

=== Макроструктура алгоритма ===
Алгоритм состоит из двух шагов:

1. Генерация цен опциона в листьях.

2. Вычисление справедливой стоимости опциона по формуле <math>(1)</math>

=== Схема реализации последовательного алгоритма ===
На вход: количество этапов N, страйк K, цена базового актива на <math>t_0</math> S, волатильность базового актива v, шаг по времени dT, процентная ставка r.

1. Для i = 0, N:

1.1 price = S * exp(v * dT * (2 - i * N))

1.2 steps[i] = max(price - K, 0)

2. pu = (exp(r * dT) - exp(-sigma * sqrt(dT))) / (exp(sigma * sqrt(dT)) - exp(-sigma * sqrt(dT)))

3. pd = 1 - pu

4. Для i = N, 1

4.1 Для j = 0, i - 1

4.1.1 steps[j] = pu * steps[j + 1] + pd * steps[j]

=== Последовательная сложность алгоритма ===
Алгоритм требует <math>4N + 4 + N^2 - N = N^2 + 3N + 4</math> операций умножения, <math>N^2 + 2N + 3</math> операций вычитания, <math>N + 4</math> вычислений экспоненты, <math>N</math> вычислений максимума и 3 операции вычисления квадратного корня. В итоге, последовательная сложность алгоритма равна <math>2N^2 + 7N + 14</math> элементарных операций.

=== Информационный граф алгоритма ===
Информационный граф алгоритма изображен на рисунке 1

[[Файл:BOPM.png]]

=== Ресурс параллелизма алгоритма ===
Для вычисления значений справедливой стоимости опциона в листьях необходимо выполнить последовательно следующие ярусы:

1. Вычисление экспоненты

2. Умножение экспоненты на стоимость базового актива в момент времени <math>t_0</math>

При классификации по ширине ярусно-параллельной формы алгоритм имеет сложность <math>O(N)</math>. При классификации по высоте ЯПФ - <math>O(N)</math>

=== Входные и выходные данные алгоритма ===
Входные данные алгоритма, как было указано ранее, количество этапов <math>N</math>, страйк <math>K</math>, цена базового актива на <math>t_0</math> <math>S</math>, волатильность базового актива <math>\sigma</math>, шаг по времени <math>\Delta T</math>, процентная ставка <math>r</math>. На выходе получается справедливая стоимость опциона <math>C</math>.

=== Свойства алгоритма ===
Отношение последовательной и параллельной сложностей алгоритма в случае неограниченных ресурсов является линейным.

== Программная реализация алгоритма ==
=== Особенности последовательной реализации алгоритма ===
Код последовательной реализации на языке C может выглядеть так:
<pre>
#include <stdlib.h>
#include <float.h>
#include <math.h>

double price(int N, double K, double S, double vol, double dT, double r) {
double *steps = malloc(sizeof(double) * (N + 1));
for(int i = 0; i <= N; i++) {
double price = S * expf(vol * dT * (2. * i - N));
steps[i] = fmaxf(price - K, .0);
}

double pu = (expf(r * dT) - expf(-vol * sqrt(dT))) / (expf(vol * sqrt(dT)) - expf(-vol * sqrt(dT))), pd = 1 - pu;

for(int i = N; i > 0; i--)
for(int j = 0; j <= i - 1; j++)
steps[j] = pu * steps[j + 1] + pd * steps[j];

double C = steps[0];

free(steps);
steps = 0x0;

return C;
}
</pre>

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

=== Существующие реализации ===
Существует

Биномиальная модель оценки опционов

2016-05-12T13:57:50Z

Nkrivenko:

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Биномиальная модель оценки опциона – итерационный метод, моделирующий цену опциона на временном отрезке, когда опцион действителен. Для некоторых типов опционов, например, американского, это единственный способ оценки, так как точное решение, позволяющее предсказать цену на всем временном отрезке, неизвестно.

Если быть точнее, биномиальная модель представляет эволюцию цены базового актива опциона как двоичное дерево всех возможных цен при равномерном разбиении временного отрезка с сегодняшнего дня, с предположением, что на каждом шаге цена может только расти либо падать на фиксированное число с соответствующими вероятностями <math>p_u</math> и <math>p_d</math>. Другими словами, корнем дерева является сегодняшняя цена базового актива, каждый уровень представляет собой все возможные цены в данный момент времени. У каждого узла со значением <math>S</math> есть два дочерних со значениями <math>Su</math> и <math>Sd, u,d</math> – множители движения цены вверх и вниз соответственно за один шаг по времени <math>dT</math>. <math>u</math> и <math>d</math> зависят от волатильности <math>\sigma</math>:

<math>u = e^{\sigma\sqrt{dT}}, d = e^{-\sigma\sqrt{dT}}, ud = 1.</math>

<math>p_d = 1 - p_u, p_u</math> ищется в предположении, что за <math>dT</math> доходность базового актива в среднем такая же, как и при отсутствии риска, то есть если в момент времени <math>t</math> стоимость базового актива <math>S</math>, то в момент времени <math>t + dT</math> она будет равна <math>Se^{rdT}</math>, где <math>r</math> - процентная ставка. Получается следующее уравнение:

<math>Se^{rdT} = (Su p_u + Sd p_d)</math>,

откуда <math>p_u = \frac{e^{rdT} - d}{u - d}.</math>

С помощью такого представления, можно получить цену в любом узле дерева. Для опциона "колл" она равна <math>V_{call} = max\{S - K, 0\}</math>, для "пут" <math>V_{put} = max\{K - S, 0\}</math>, <math>K</math> - страйк опциона. После расчета всех возможных цен опциона, начинается движение от листьев к корню по формуле

<math>V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT} (1)</math>,

где <math>V_t</math> - цена опциона в некотором узле, <math>V_{u, t+1}, V_{d, t+1}</math> - цены опциона в дочерних узлах.

=== Математическое описание алгоритма ===
Для реализации алгоритма потребуются две формулы:

1) <math>V_{T_i} = max\{Se^{V_sdT * 2i - N} - K, 0\}</math> - для расчета стоимости опциона в i-м листе дерева

2) <math>V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT}</math> - для расчета справедливой стоимости опциона

=== Вычислительное ядро алгоритма ===
Вычислительным ядром алгоритма является вычисление справедливой стоимости опциона. Для этого действия потребуется <math>\frac{N(N-1)}{2}</math> операций, где <math>N</math> - число шагов по времени.

=== Макроструктура алгоритма ===
Алгоритм состоит из двух шагов:

1. Генерация цен опциона в листьях.

2. Вычисление справедливой стоимости опциона по формуле <math>(1)</math>

=== Схема реализации последовательного алгоритма ===
На вход: количество этапов N, страйк K, цена базового актива на <math>t_0</math> S, волатильность базового актива v, шаг по времени dT, процентная ставка r.

1. Для i = 0, N:

1.1 price = S * exp(v * dT * (2 - i * N))

1.2 steps[i] = max(price - K, 0)

2. pu = (exp(r * dT) - exp(-sigma * sqrt(dT))) / (exp(sigma * sqrt(dT)) - exp(-sigma * sqrt(dT)))

3. pd = 1 - pu

4. Для i = N, 1

4.1 Для j = 0, i - 1

4.1.1 steps[j] = pu * steps[j + 1] + pd * steps[j]

=== Последовательная сложность алгоритма ===
Алгоритм требует <math>4N + 4 + N^2 - N = N^2 + 3N + 4</math> операций умножения, <math>N^2 + 2N + 3</math> операций вычитания, <math>N + 4</math> вычислений экспоненты, <math>N</math> вычислений максимума и 3 операции вычисления квадратного корня. В итоге, последовательная сложность алгоритма равна <math>2N^2 + 7N + 14</math> элементарных операций.

=== Информационный граф алгоритма ===
Информационный граф алгоритма изображен на рисунке 1

[[Файл:BOPM.png]]

=== Ресурс параллелизма алгоритма ===
Для вычисления значений справедливой стоимости опциона в листьях необходимо выполнить последовательно следующие ярусы:

1. Вычисление экспоненты

2. Умножение экспоненты на стоимость базового актива в момент времени <math>t_0</math>

При классификации по ширине ярусно-параллельной формы алгоритм имеет сложность <math>O(N)</math>. При классификации по высоте ЯПФ - <math>O(N)</math>

=== Входные и выходные данные алгоритма ===
Входные данные алгоритма, как было указано ранее, количество этапов <math>N</math>, страйк <math>K</math>, цена базового актива на <math>t_0</math> <math>S</math>, волатильность базового актива <math>\sigma</math>, шаг по времени <math>\Delta T</math>, процентная ставка <math>r</math>. На выходе получается справедливая стоимость опциона <math>C</math>.

=== Свойства алгоритма ===
Отношение последовательной и параллельной сложностей алгоритма в случае неограниченных ресурсов является линейным.

== Программная реализация алгоритма ==
=== Особенности последовательной реализации алгоритма ===
Код последовательной реализации на языке C может выглядеть так:
<pre>
#include <stdlib.h>
#include <float.h>
#include <math.h>

double price(int N, double K, double S, double vol, double dT, double r) {
double *steps = malloc(sizeof(double) * (N + 1));
for(int i = 0; i <= N; i++) {
double price = S * expf(vol * dT * (2. * i - N));
steps[i] = fmaxf(price - K, .0);
}

double pu = (expf(r * dT) - expf(-vol * sqrt(dT))) / (expf(vol * sqrt(dT)) - expf(-vol * sqrt(dT))), pd = 1 - pu;

for(int i = N; i > 0; i--)
for(int j = 0; j <= i - 1; j++)
steps[j] = pu * steps[j + 1] + pd * steps[j];

double C = steps[0];

free(steps);
steps = 0x0;

return C;
}
</pre>

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

Биномиальная модель оценки опционов

2016-05-12T13:34:34Z

Nkrivenko: /* Свойства и структура алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Биномиальная модель оценки опциона – итерационный метод, моделирующий цену опциона на временном отрезке, когда опцион действителен. Для некоторых типов опционов, например, американского, это единственный способ оценки, так как точное решение, позволяющее предсказать цену на всем временном отрезке, неизвестно.

Если быть точнее, биномиальная модель представляет эволюцию цены базового актива опциона как двоичное дерево всех возможных цен при равномерном разбиении временного отрезка с сегодняшнего дня, с предположением, что на каждом шаге цена может только расти либо падать на фиксированное число с соответствующими вероятностями <math>p_u</math> и <math>p_d</math>. Другими словами, корнем дерева является сегодняшняя цена базового актива, каждый уровень представляет собой все возможные цены в данный момент времени. У каждого узла со значением <math>S</math> есть два дочерних со значениями <math>Su</math> и <math>Sd, u,d</math> – множители движения цены вверх и вниз соответственно за один шаг по времени <math>dT</math>. <math>u</math> и <math>d</math> зависят от волатильности <math>\sigma</math>:

<math>u = e^{\sigma\sqrt{dT}}, d = e^{-\sigma\sqrt{dT}}, ud = 1.</math>

<math>p_d = 1 - p_u, p_u</math> ищется в предположении, что за <math>dT</math> доходность базового актива в среднем такая же, как и при отсутствии риска, то есть если в момент времени <math>t</math> стоимость базового актива <math>S</math>, то в момент времени <math>t + dT</math> она будет равна <math>Se^{rdT}</math>, где <math>r</math> - процентная ставка. Получается следующее уравнение:

<math>Se^{rdT} = (Su p_u + Sd p_d)</math>,

откуда <math>p_u = \frac{e^{rdT} - d}{u - d}.</math>

С помощью такого представления, можно получить цену в любом узле дерева. Для опциона "колл" она равна <math>V_{call} = max\{S - K, 0\}</math>, для "пут" <math>V_{put} = max\{K - S, 0\}</math>, <math>K</math> - страйк опциона. После расчета всех возможных цен опциона, начинается движение от листьев к корню по формуле

<math>V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT} (1)</math>,

где <math>V_t</math> - цена опциона в некотором узле, <math>V_{u, t+1}, V_{d, t+1}</math> - цены опциона в дочерних узлах.

=== Математическое описание алгоритма ===
Для реализации алгоритма потребуются две формулы:

1) <math>V_{T_i} = max\{Se^{V_sdT * 2i - N} - K, 0\}</math> - для расчета стоимости опциона в i-м листе дерева

2) <math>V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT}</math> - для расчета справедливой стоимости опциона

=== Вычислительное ядро алгоритма ===
Вычислительным ядром алгоритма является вычисление справедливой стоимости опциона. Для этого действия потребуется <math>\frac{N(N-1)}{2}</math> операций, где <math>N</math> - число шагов по времени.

=== Макроструктура алгоритма ===
Алгоритм состоит из двух шагов:

1. Генерация цен опциона в листьях.

2. Вычисление справедливой стоимости опциона по формуле <math>(1)</math>

=== Схема реализации последовательного алгоритма ===
На вход: количество этапов N, страйк K, цена базового актива на <math>t_0</math> S, волатильность базового актива v, шаг по времени dT, процентная ставка r.

1. Для i = 0, N:

1.1 price = S * exp(v * dT * (2 - i * N))

1.2 steps[i] = max(price - K, 0)

2. pu = (exp(r * dT) - exp(-sigma * sqrt(dT))) / (exp(sigma * sqrt(dT)) - exp(-sigma * sqrt(dT)))

3. pd = 1 - pu

4. Для i = N, 1

4.1 Для j = 0, i - 1

4.1.1 steps[j] = pu * steps[j + 1] + pd * steps[j]

=== Последовательная сложность алгоритма ===
Алгоритм требует <math>4N + 4 + N^2 - N = N^2 + 3N + 4</math> операций умножения, <math>N^2 + 2N + 3</math> операций вычитания, <math>N + 4</math> вычислений экспоненты, <math>N</math> вычислений максимума и 3 операции вычисления квадратного корня. В итоге, последовательная сложность алгоритма равна <math>2N^2 + 7N + 14</math> элементарных операций.

=== Информационный граф алгоритма ===
Информационный граф алгоритма изображен на рисунке 1

[[Файл:BOPM.png]]

=== Ресурс параллелизма алгоритма ===
Для вычисления значений справедливой стоимости опциона в листьях необходимо выполнить последовательно следующие ярусы:

1. Вычисление экспоненты

2. Умножение экспоненты на стоимость базового актива в момент времени <math>t_0</math>

При классификации по ширине ярусно-параллельной формы алгоритм имеет сложность <math>O(N)</math>. При классификации по высоте ЯПФ - <math>O(N)</math>

=== Входные и выходные данные алгоритма ===
Входные данные алгоритма, как было указано ранее, количество этапов <math>N</math>, страйк <math>K</math>, цена базового актива на <math>t_0</math> <math>S</math>, волатильность базового актива <math>\sigma</math>, шаг по времени <math>\Delta T</math>, процентная ставка <math>r</math>. На выходе получается справедливая стоимость опциона <math>C</math>.

=== Свойства алгоритма ===
Отношение последовательной и параллельной сложностей алгоритма в случае неограниченных ресурсов является линейным.

Биномиальная модель оценки опционов

2016-05-12T13:08:41Z

Nkrivenko: /* Свойства и структура алгоритма */

Биномиальная модель оценки опционов

2016-05-09T15:43:22Z

Nkrivenko: /* Свойства и структура алгоритма */

Применение методов Монте-Карло для оценки опционов европейского типа

2016-05-09T15:23:51Z

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

Биномиальная модель оценки опционов

2016-05-09T15:01:07Z

Nkrivenko: Новая страница: «== Свойства и структура алгоритма == === Общее описание алгоритма === Биномиальная модель оц…»

Применение методов Монте-Карло для оценки опционов европейского типа

2016-04-03T17:16:56Z

Nkrivenko:

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

Рассмотрим эволюционирующий в непрерывном времени финансовый рынок, состоящий из двух типов активов: акции (рисковые активы, S) и облигации (безрисковые активы, B). Для моделирования рынка будем использовать модель Блэка–Шоулса. Данная модель после ряда преобразований представляет собой систему стохастических дифференциальных уравнений следующего вида:

<math>dB_t = rB_tdt, B_0 > 0, (1)</math>

<math>dS_t = S_t((r-\delta)dt - \sigma dW_t), S_0 > 0. (2)</math>

Здесь первое уравнение представляет собой обыкновенное дифференциальное уравнение, описывающее поведение цены облигации <math>B_t</math>, на изменение которой влияет процентная ставка <math>r</math>. Уравнение (2) является стохастическим дифференциальным уравнением, описывающим эволюцию цены акции <math>S_t</math>. В этом уравнении: <math>\sigma</math> - волатильность акции, <math>\delta</math> - ставка дивиденда, <math>W_t</math> - винеровский случайный процесс.

Сделаем несколько предположений касательно рынка:

1. пусть модель будет без дивидендов: <math>\delta = 0</math>;

2. процентные ставки постоянны;

3. если время измеряется в годах, то все рассмотренные процентные ставки участвуют в уравнениях как числа от 0 до 1 и выражают проценты годовых, измеренные в долях.

При этих предположениях рассмотренная система имеет аналитическое решение:

<math>S_t = S_0 e^{(r - \frac{\sigma^2}{2})t + \sigma W_t}</math>.

Опцион, как производный финансовый инструмент, представляет собой контракт между сторонами <math>P_1</math> и <math>P_2</math>, который дает право стороне <math>P_2</math> в некоторый момент времени <math>t</math> в будущем купить у стороны <math>P_1</math> или продать стороне <math>P_1</math> акции по зафиксированной в контракте цене <math>K</math>. За это право сторона <math>P_2</math> выплачивает фиксированную сумму (премию) <math>C</math> стороне <math>P_1</math>. При этом K называется ценой исполнения опциона (страйк, strike price), а <math>C</math> – ценой опциона.

Основная идея заключения контракта состоит в игре двух лиц – <math>P_1</math> и <math>P_2</math>. Вторая сторона выплачивает некоторую сумму <math>C</math> и в некоторый момент времени <math>T</math> (срок выплаты, зафиксированный в контракте) принимает решение: покупать акции по цене <math>K</math> у первой стороны или нет. Решение принимается в зависимости от соотношения цены <math>S_T</math> и <math>K</math>. Если <math>S_T < K</math>, покупать акции не выгодно, сторона <math>P_1</math> получила прибыль <math>C</math>, а <math>P_2</math> – убыток <math>C</math>. В случае, если <math>S_T > K</math>, сторона <math>P_2</math> покупает у первой акции по цене <math>K</math>, в ряде случаев получая прибыль.

Справедливая цена опциона – цена, при которой наблюдается баланс выигрыша/проигрыша каждой из сторон. Определяется она как средний выигрыш стороны <math>P_2</math>:

<math>C = \mathop{\mathbb{E}}(e^{-rT} max\{S_T - K, 0\})</math>.

Точное решение этой системы уравнений известно:

<math>C = S_0N(d_1) - Ke^{-rT}N(d_2),</math>

<math>d_1 = ln{\frac{S_0}{K}} + \frac{(r + \sigma^2 / 2)T}{\sigma\sqrt{T}},</math>

<math>d_2 = d_1 - \sigma\sqrt{T}.</math>

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

=== Математическое описание алгоритма ===
Решаемая задача имеет следующий вид:

<math>C = e^{-rT}\int^{+\infty}_{-\infty}{f(z)\varphi(z)dz}, (3)</math>

<math>f(z) = max\{S_0 e^{(r - \sigma^2/2)T + \sigma\sqrt{T}z} - K, 0\}, (4)</math>

<math>\varphi(z) = \frac{1}{\sqrt{2\pi}} e^{-z^2/2}.</math>

Для вычисления этого интеграла будем использовать метод Монте-Карло. Если мы рассмотрим случайную величину <math>X = f(z)</math>, то математическое ожидание этой случайной величины будет совпадать с формулой (3) с точностью до коэффициента дисконтирования. Формула для вычисления искомого интеграла имеет вид:

<math>\hat{C} = \frac{e^{-rT}}{N} \sum^{N}_{i=1}{f(z_i)},</math>

<math>f(z_i) = max\{S_0 e^{(r - \sigma^2/2)T + \sigma\sqrt{T}z} - K, 0\}, z_i \sim N_{0,1}.</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма составляет вычисление следующей суммы:

<math>\sum^{N}_{i=1}{f(z_i)}.</math>

Поскольку время, требуемое на операцию сложения в реальных примерах мало по сравнению с временем, затрачиваемом на вычисление функции <math>f(z_i)</math>, для производительности вычислений становится маловажным, каким конкретным образом осуществлять сложение и умножение.

=== Макроструктура алгоритма ===
Алгоритм представляет собой сумму значений функции от случайной величины.
=== Схема последовательной реализации алгоритма ===
Формулы для реализации алгоритма приведены выше <math>(1)</math>. С помощью генератора случайных чисел в цикле получаются точки, и в них вычисляется соответствующая функция. Результаты складываются, полученная сумма умножается на коэффициент. При последовательной реализации для экономии памяти можно сразу не генерировать массив всех точек, в которых должна быть вычислена функция, а получать их последовательно.
=== Последовательная сложность алгоритма ===
Время, затраченное на вычисление интеграла растет как <math>Nt</math>, где <math>N</math> – количество случайных точек, <math>t</math> – время, необходимое для вычисления функции.
=== Информационный граф алгоритма ===
Информационный граф алгоритма представлен на рисунке 1,

[[Файл: MCG.png]]

Рисунок 1 – Информационный граф алгоритма

где вершина <math>f</math> – вычисление функции <math>f(z)</math>, <math>rnd</math> – генерация случайного числа. Анализ этого графа производится в последующих разделах описания алгоритма.

=== Ресурс параллелизма алгоритма ===
Для вычисления интеграла <math>(3)</math> методом Монте-Карло требуется последовательно выполнить следующие ярусы:

1) вычисление случайного числа <math>z</math>,

2) вычисление функции <math>f</math> на основании полученного случайного числа,

3) сложение полученных результатов.

В общем случае, все вычисления функции <math>f</math> могут производиться на разных узлах, следовательно, алгоритм идеально поддается распараллеливанию.
При классификации по высоте ярусно-параллельной формы этот алгоритм имеет сложность 3. При классификации по ширине – <math>O(N)</math>.

=== Входные и выходные данные алгоритма ===
Входные данные для вычисления алгоритма: число точек <math>N</math>, волатильность акции <math>\sigma</math>, время жизни опциона <math>T</math>, страйк <math>K</math>, процентная ставка <math>r</math>, стоимость акции в начальный момент времени <math>S_0</math>.
Выходные данные: справедливая цена опциона <math>C</math>.

=== Свойства алгоритма ===
Соотношение последовательной и параллельной сложностей в случае неограниченных ресурсов является линейным.

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

== Программная реализация алгоритма ==
=== Особенности последовательной реализации алгоритма ===
Код последовательной реализации на языке C может выглядеть так:
<pre>
double price(int N, double sigma, double T, double K, double S0, double r) {
coeff = exp(-r*T) / N, result = .0, sigma_coeff = (r - sigma * sigma / 2) * T, sigma_T_coeff = sigma * sqrt(T);
for (int i = 0; i < N; i++) {
result += max(0, S0 * exp(sigma_coeff + sigma_T_coeff * normalrand(i)) - K);
}
return coeff * result;
}
</pre>

Представленный алгоритм не является полностью детерминированным, так как он основан на использовании последовательностей случайных чисел.
=== Локальность данных и вычислений ===
Данные в представленном алгоритме обладают хорошей локальностью, так как на каждом шаге алгоритма приходится использовать значения переменных sigma_coeff и sigma_T_coeff, что повышает вероятность попадания этих значений в кэш.
=== Возможные способы и особенности реализации параллельного алгоритма ===
Один из возможных вариантов реализации алгоритма – независимое вычисление значений функции <math>f(z)</math> на различных вычислительных узлах, например, с помощью технологии MPI. «Подводным камнем» такой реализации может стать генерация случайных чисел, которая должна быть независимой на каждом вычислительном узле. Желательно использовать генератор случайных чисел с достаточно большим периодом.
=== Масштабируемость алгоритма и его реализации ===
Теоретические оценки показывают, что алгоритм должен быть хорошо масштабируем.
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
При достаточно большом числе точек N возможна реализация алгоритма на GPU для достижения большей скорости выполнения, чем на обычных процессорах.
=== Существующие реализации ===
Есть открытая реализация методов Монте-Карло, являющаяся частью GSL (GNU Scientific Library). Данная библиотека включает в себя как классический алгоритм, так и два адаптивных: «Vegas» и «Miser».

Участник:Nkrivenko

2016-03-26T21:47:55Z

Nkrivenko: Новая страница: «Николай Кривенко, студент магистратуры факультета ВМК, кафедра суперкомпьютеров и кван…»

Николай Кривенко, студент магистратуры факультета ВМК, кафедра суперкомпьютеров и квантовой информатики.

Применение методов Монте-Карло для оценки опционов европейского типа

2016-03-26T21:32:59Z

Nkrivenko:

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

Рассмотрим эволюционирующий в непрерывном времени финансовый рынок, состоящий из двух типов активов: акции (рисковые активы, S) и облигации (безрисковые активы, B). Для моделирования рынка будем использовать модель Блэка–Шоулса. Данная модель после ряда преобразований представляет собой систему стохастических дифференциальных уравнений следующего вида:

<math>dB_t = rB_tdt, B_0 > 0, (1)</math>

<math>dS_t = S_t((r-\delta)dt - \sigma dW_t), S_0 > 0. (2)</math>

Здесь первое уравнение представляет собой обыкновенное дифференциальное уравнение, описывающее поведение цены облигации <math>B_t</math>, на изменение которой влияет процентная ставка <math>r</math>. Уравнение (2) является стохастическим дифференциальным уравнением, описывающим эволюцию цены акции <math>S_t</math>. В этом уравнении: <math>\sigma</math> - волатильность акции, <math>\delta</math> - ставка дивиденда, <math>W_t</math> - винеровский случайный процесс.

Сделаем несколько предположений касательно рынка:

1. пусть модель будет без дивидендов: <math>\delta = 0</math>;

2. процентные ставки постоянны;

3. если время измеряется в годах, то все рассмотренные процентные ставки участвуют в уравнениях как числа от 0 до 1 и выражают проценты годовых, измеренные в долях.

При этих предположениях рассмотренная система имеет аналитическое решение:

<math>S_t = S_0 e^{(r - \frac{\sigma^2}{2})t + \sigma W_t}</math>.

Опцион, как производный финансовый инструмент, представляет собой контракт между сторонами <math>P_1</math> и <math>P_2</math>, который дает право стороне <math>P_2</math> в некоторый момент времени <math>t</math> в будущем купить у стороны <math>P_1</math> или продать стороне <math>P_1</math> акции по зафиксированной в контракте цене <math>K</math>. За это право сторона <math>P_2</math> выплачивает фиксированную сумму (премию) <math>C</math> стороне <math>P_1</math>. При этом K называется ценой исполнения опциона (страйк, strike price), а <math>C</math> – ценой опциона.

Основная идея заключения контракта состоит в игре двух лиц – <math>P_1</math> и <math>P_2</math>. Вторая сторона выплачивает некоторую сумму <math>C</math> и в некоторый момент времени <math>T</math> (срок выплаты, зафиксированный в контракте) принимает решение: покупать акции по цене <math>K</math> у первой стороны или нет. Решение принимается в зависимости от соотношения цены <math>S_T</math> и <math>K</math>. Если <math>S_T < K</math>, покупать акции не выгодно, сторона <math>P_1</math> получила прибыль <math>C</math>, а <math>P_2</math> – убыток <math>C</math>. В случае, если <math>S_T > K</math>, сторона <math>P_2</math> покупает у первой акции по цене <math>K</math>, в ряде случаев получая прибыль.

Справедливая цена опциона – цена, при которой наблюдается баланс выигрыша/проигрыша каждой из сторон. Определяется она как средний выигрыш стороны <math>P_2</math>:

<math>C = \mathop{\mathbb{E}}(e^{-rT} max\{S_T - K, 0\})</math>.

Точное решение этой системы уравнений известно:

<math>C = S_0N(d_1) - Ke^{-rT}N(d_2),</math>

<math>d_1 = ln{\frac{S_0}{K}} + \frac{(r + \sigma^2 / 2)T}{\sigma\sqrt{T}},</math>

<math>d_2 = d_1 - \sigma\sqrt{T}.</math>

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

=== Математическое описание алгоритма ===
Решаемая задача имеет следующий вид:

<math>C = e^{-rT}\int^{+\infty}_{-\infty}{f(z)\varphi(z)dz}, (3)</math>

<math>f(z) = max\{S_0 e^{(r - \sigma^2/2)T + \sigma\sqrt{T}z} - K, 0\}, (4)</math>

<math>\varphi(z) = \frac{1}{\sqrt{2\pi}} e^{-z^2/2}.</math>

Для вычисления этого интеграла будем использовать метод Монте-Карло. Если мы рассмотрим случайную величину <math>X = f(z)</math>, то математическое ожидание этой случайной величины будет совпадать с формулой (3) с точностью до коэффициента дисконтирования. Формула для вычисления искомого интеграла имеет вид:

<math>\hat{C} = \frac{e^{-rT}}{N} \sum^{N}_{i=1}{f(z_i)},</math>

<math>f(z_i) = max\{S_0 e^{(r - \sigma^2/2)T + \sigma\sqrt{T}z} - K, 0\}, z_i \sim N_{0,1}.</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма составляет вычисление следующей суммы:

<math>\sum^{N}_{i=1}{f(z_i)}.</math>

Поскольку время, требуемое на операцию сложения в реальных примерах мало по сравнению с временем, затрачиваемом на вычисление функции <math>f(z_i)</math>, для производительности вычислений становится маловажным, каким конкретным образом осуществлять сложение и умножение.

=== Макроструктура алгоритма ===
Алгоритм представляет собой сумму значений функции от случайной величины.
=== Схема последовательной реализации алгоритма ===
Формулы для реализации алгоритма приведены выше <math>(1)</math>. С помощью генератора случайных чисел в цикле получаются точки, и в них вычисляется соответствующая функция. Результаты складываются, полученная сумма умножается на коэффициент. При последовательной реализации для экономии памяти можно сразу не генерировать массив всех точек, в которых должна быть вычислена функция, а получать их последовательно.
=== Последовательная сложность алгоритма ===
Время, затраченное на вычисление интеграла растет как <math>Nt</math>, где <math>N</math> – количество случайных точек, <math>t</math> – время, необходимое для вычисления функции.
=== Информационный граф алгоритма ===
Информационный граф алгоритма представлен на рисунке 1,

[[Файл: MCG.png]]

Рисунок 1 – Информационный граф алгоритма

где вершина <math>f</math> – вычисление функции <math>f(z)</math>, <math>rnd</math> – генерация случайного числа. Анализ этого графа производится в последующих разделах описания алгоритма.

=== Ресурс параллелизма алгоритма ===
Для вычисления интеграла <math>(3)</math> методом Монте-Карло требуется последовательно выполнить следующие ярусы:

1) вычисление случайного числа <math>z</math>,

2) вычисление функции <math>f</math> на основании полученного случайного числа,

3) сложение полученных результатов.

В общем случае, все вычисления функции <math>f</math> могут производиться на разных узлах, следовательно, алгоритм идеально поддается распараллеливанию.
При классификации по высоте ярусно-параллельной формы этот алгоритм имеет сложность 3. При классификации по ширине – <math>O(N)</math>.

=== Входные и выходные данные алгоритма ===
Входные данные для вычисления алгоритма: число точек <math>N</math>, волатильность акции <math>\sigma</math>, время жизни опциона <math>T</math>, страйк <math>K</math>, процентная ставка <math>r</math>, стоимость акции в начальный момент времени <math>S_0</math>.
Выходные данные: справедливая цена опциона <math>C</math>.

=== Свойства алгоритма ===
Соотношение последовательной и параллельной сложностей в случае неограниченных ресурсов является линейным.

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

== Программная реализация алгоритма ==
=== Особенности последовательной реализации алгоритма ===
Код последовательной реализации на языке C может выглядеть так:
<pre>
double price(int N, double sigma, double T, double K, double S0, double r) {
coeff = exp(-r*T) / N, result = .0, sigma_coeff = (r - sigma * sigma / 2) * T, sigma_T_coeff = sigma * sqrt(T);
for (int i = 0; i < N; i++) {
result += max(0, S0 * exp(sigma_coeff + sigma_T_coeff * normalrand(i)) - K);
}
return coeff * result;
}
</pre>

Представленный алгоритм не является полностью детерминированным, так как он основан на использовании последовательностей случайных чисел.
=== Локальность данных и вычислений ===
Данные в представленном алгоритме обладают хорошей локальностью, так как на каждом шаге алгоритма приходится использовать значения переменных sigma_coeff и sigma_T_coeff, что повышает вероятность попадания этих значений в кэш.
=== Возможные способы и особенности реализации параллельного алгоритма ===
Один из возможных вариантов реализации алгоритма – независимое вычисление значений функции <math>f(z)</math> на различных вычислительных узлах, например, с помощью технологии MPI. «Подводным камнем» такой реализации может стать генерация случайных чисел, которая должна быть независимой на каждом вычислительном узле. Желательно использовать генератор случайных чисел с достаточно большим периодом.
=== Масштабируемость алгоритма и его реализации ===
Теоретические оценки показывают, что алгоритм должен быть хорошо масштабируем.
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
При достаточно большом числе точек N возможна реализация алгоритма на GPU для достижения большей скорости выполнения, чем на обычных процессорах.
=== Существующие реализации ===
Есть открытая реализация методов Монте-Карло, являющаяся частью GSL (GNU Scientific Library). Данная библиотека включает в себя как классический алгоритм, так и два адаптивных: «Vegas» и «Miser».

Применение методов Монте-Карло для оценки опционов европейского типа

2016-03-26T21:30:35Z

Nkrivenko: Новая страница: «== Свойства и структура алгоритма == === Свойства и структура алгоритма === Методы Монте-Карл…»

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

Рассмотрим эволюционирующий в непрерывном времени финансовый рынок, состоящий из двух типов активов: акции (рисковые активы, S) и облигации (безрисковые активы, B). Для моделирования рынка будем использовать модель Блэка–Шоулса. Данная модель после ряда преобразований представляет собой систему стохастических дифференциальных уравнений следующего вида:

<math>dB_t = rB_tdt, B_0 > 0, (1)</math>

<math>dS_t = S_t((r-\delta)dt - \sigma dW_t), S_0 > 0. (2)</math>

Здесь первое уравнение представляет собой обыкновенное дифференциальное уравнение, описывающее поведение цены облигации <math>B_t</math>, на изменение которой влияет процентная ставка <math>r</math>. Уравнение (2) является стохастическим дифференциальным уравнением, описывающим эволюцию цены акции <math>S_t</math>. В этом уравнении: <math>\sigma</math> - волатильность акции, <math>\delta</math> - ставка дивиденда, <math>W_t</math> - винеровский случайный процесс.

Сделаем несколько предположений касательно рынка:

1. пусть модель будет без дивидендов: <math>\delta = 0</math>;

2. процентные ставки постоянны;

3. если время измеряется в годах, то все рассмотренные процентные ставки участвуют в уравнениях как числа от 0 до 1 и выражают проценты годовых, измеренные в долях.

При этих предположениях рассмотренная система имеет аналитическое решение:

<math>S_t = S_0 e^{(r - \frac{\sigma^2}{2})t + \sigma W_t}</math>.

Опцион, как производный финансовый инструмент, представляет собой контракт между сторонами <math>P_1</math> и <math>P_2</math>, который дает право стороне <math>P_2</math> в некоторый момент времени <math>t</math> в будущем купить у стороны <math>P_1</math> или продать стороне <math>P_1</math> акции по зафиксированной в контракте цене <math>K</math>. За это право сторона <math>P_2</math> выплачивает фиксированную сумму (премию) <math>C</math> стороне <math>P_1</math>. При этом K называется ценой исполнения опциона (страйк, strike price), а <math>C</math> – ценой опциона.

Основная идея заключения контракта состоит в игре двух лиц – <math>P_1</math> и <math>P_2</math>. Вторая сторона выплачивает некоторую сумму <math>C</math> и в некоторый момент времени <math>T</math> (срок выплаты, зафиксированный в контракте) принимает решение: покупать акции по цене <math>K</math> у первой стороны или нет. Решение принимается в зависимости от соотношения цены <math>S_T</math> и <math>K</math>. Если <math>S_T < K</math>, покупать акции не выгодно, сторона <math>P_1</math> получила прибыль <math>C</math>, а <math>P_2</math> – убыток <math>C</math>. В случае, если <math>S_T > K</math>, сторона <math>P_2</math> покупает у первой акции по цене <math>K</math>, в ряде случаев получая прибыль.

Справедливая цена опциона – цена, при которой наблюдается баланс выигрыша/проигрыша каждой из сторон. Определяется она как средний выигрыш стороны <math>P_2</math>:

<math>C = \mathop{\mathbb{E}}(e^{-rT} max\{S_T - K, 0\})</math>.

Точное решение этой системы уравнений известно:

<math>C = S_0N(d_1) - Ke^{-rT}N(d_2),</math>

<math>d_1 = ln{\frac{S_0}{K}} + \frac{(r + \sigma^2 / 2)T}{\sigma\sqrt{T}},</math>

<math>d_2 = d_1 - \sigma\sqrt{T}.</math>

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

=== Математическое описание алгоритма ===
Решаемая задача имеет следующий вид:

<math>C = e^{-rT}\int^{+\infty}_{-\infty}{f(z)\varphi(z)dz}, (3)</math>

<math>f(z) = max\{S_0 e^{(r - \sigma^2/2)T + \sigma\sqrt{T}z} - K, 0\}, (4)</math>

<math>\varphi(z) = \frac{1}{\sqrt{2\pi}} e^{-z^2/2}.</math>

Для вычисления этого интеграла будем использовать метод Монте-Карло. Если мы рассмотрим случайную величину <math>X = f(z)</math>, то математическое ожидание этой случайной величины будет совпадать с формулой (3) с точностью до коэффициента дисконтирования. Формула для вычисления искомого интеграла имеет вид:

<math>\hat{C} = \frac{e^{-rT}}{N} \sum^{N}_{i=1}{f(z_i)},</math>

<math>f(z_i) = max\{S_0 e^{(r - \sigma^2/2)T + \sigma\sqrt{T}z} - K, 0\}, z_i \sim N_{0,1}.</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма составляет вычисление следующей суммы:

<math>\sum^{N}_{i=1}{f(z_i)}.</math>

Поскольку время, требуемое на операцию сложения в реальных примерах мало по сравнению с временем, затрачиваемом на вычисление функции <math>f(z_i)</math>, для производительности вычислений становится маловажным, каким конкретным образом осуществлять сложение и умножение.

=== Макроструктура алгоритма ===
Алгоритм представляет собой сумму значений функции от случайной величины.
=== Схема последовательной реализации алгоритма ===
Формулы для реализации алгоритма приведены выше <math>(1)</math>. С помощью генератора случайных чисел в цикле получаются точки, и в них вычисляется соответствующая функция. Результаты складываются, полученная сумма умножается на коэффициент. При последовательной реализации для экономии памяти можно сразу не генерировать массив всех точек, в которых должна быть вычислена функция, а получать их последовательно.
=== Последовательная сложность алгоритма ===
Время, затраченное на вычисление интеграла растет как <math>Nt</math>, где <math>N</math> – количество случайных точек, <math>t</math> – время, необходимое для вычисления функции.
=== Информационный граф алгоритма ===
Информационный граф алгоритма представлен на рисунке 1,

(МЕСТО ДЛЯ РИСУНКА)

Рисунок 1 – Информационный граф алгоритма

где вершина <math>f</math> – вычисление функции <math>f(z)</math>, <math>rnd</math> – генерация случайного числа. Анализ этого графа производится в последующих разделах описания алгоритма.

=== Ресурс параллелизма алгоритма ===
Для вычисления интеграла <math>(3)</math> методом Монте-Карло требуется последовательно выполнить следующие ярусы:

1) вычисление случайного числа <math>z</math>,

2) вычисление функции <math>f</math> на основании полученного случайного числа,

3) сложение полученных результатов.

В общем случае, все вычисления функции <math>f</math> могут производиться на разных узлах, следовательно, алгоритм идеально поддается распараллеливанию.
При классификации по высоте ярусно-параллельной формы этот алгоритм имеет сложность 3. При классификации по ширине – <math>O(N)</math>.

=== Входные и выходные данные алгоритма ===
Входные данные для вычисления алгоритма: число точек <math>N</math>, волатильность акции <math>\sigma</math>, время жизни опциона <math>T</math>, страйк <math>K</math>, процентная ставка <math>r</math>, стоимость акции в начальный момент времени <math>S_0</math>.
Выходные данные: справедливая цена опциона <math>C</math>.

=== Свойства алгоритма ===
Соотношение последовательной и параллельной сложностей в случае неограниченных ресурсов является линейным.

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

== Программная реализация алгоритма ==
=== Особенности последовательной реализации алгоритма ===
Код последовательной реализации на языке C может выглядеть так:
<pre>
double price(int N, double sigma, double T, double K, double S0, double r) {
coeff = exp(-r*T) / N, result = .0, sigma_coeff = (r - sigma * sigma / 2) * T, sigma_T_coeff = sigma * sqrt(T);
for (int i = 0; i < N; i++) {
result += max(0, S0 * exp(sigma_coeff + sigma_T_coeff * normalrand(i)) - K);
}
return coeff * result;
}
</pre>

Представленный алгоритм не является полностью детерминированным, так как он основан на использовании последовательностей случайных чисел.
=== Локальность данных и вычислений ===
Данные в представленном алгоритме обладают хорошей локальностью, так как на каждом шаге алгоритма приходится использовать значения переменных sigma_coeff и sigma_T_coeff, что повышает вероятность попадания этих значений в кэш.
=== Возможные способы и особенности реализации параллельного алгоритма ===
Один из возможных вариантов реализации алгоритма – независимое вычисление значений функции <math>f(z)</math> на различных вычислительных узлах, например, с помощью технологии MPI. «Подводным камнем» такой реализации может стать генерация случайных чисел, которая должна быть независимой на каждом вычислительном узле. Желательно использовать генератор случайных чисел с достаточно большим периодом.
=== Масштабируемость алгоритма и его реализации ===
Теоретические оценки показывают, что алгоритм должен быть хорошо масштабируем.
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
При достаточно большом числе точек N возможна реализация алгоритма на GPU для достижения большей скорости выполнения, чем на обычных процессорах.
=== Существующие реализации ===
Есть открытая реализация методов Монте-Карло, являющаяся частью GSL (GNU Scientific Library). Данная библиотека включает в себя как классический алгоритм, так и два адаптивных: «Vegas» и «Miser».