Участник:Nbvehbectw/Алгоритм нахождения точек множества Мандельброта

2017-10-22T16:38:35Z

Nbvehbectw: Новая страница: «Жалеев Тимур, группа 404. == Свойства и структура алгоритмов == File:Mandelset hires.png|400px|thumb|right|Множ…»

Жалеев Тимур, группа 404.
== Свойства и структура алгоритмов ==
[[File:Mandelset hires.png|400px|thumb|right|Множество Мандельброта]]

=== Общее описание алгоритма ===
Множество Мандельброта - множество точек <math>c</math> комплексной плоскости таких, что последовательность <math>z_{n+1} = z_n^2 + c, z_0 = 0</math> ограничена<ref name=":0">[https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE_%D0%9C%D0%B0%D0%BD%D0%B4%D0%B5%D0%BB%D1%8C%D0%B1%D1%80%D0%BE%D1%82%D0%B0 Множество Мандельброта]</ref>. Для изображения области множества выбирается некоторое количество итераций (обычно зависящее от размеров изображаемой области) и так называемый "радиус выхода", и для соответствующих <math>c</math> из области вычисляются элементы данной последовательности. Если на всех итерациях модуль элемента остается не больше радиуса выхода, то считается, что последовательность ограничена, и данная точка принадлежит множеству. В противном случае последовательность считается уходящей в бесконечность, а точка - не принадлежащей множеству. Можно доказать, что если для какого-либо элемента последовательности выполняется <math>\left| z_n \right| > 2</math>, то последовательность не ограничена<ref name=":0" />, то есть в качестве радиуса выхода можно взять число 2.

=== Математическое описание алгоритма ===
Для изображения прямоугольной области множества Мандельброта можно выбрать следующие параметры: координаты центра изображения <math>(\overline{x}, \overline{y})</math>, ширина <math>W</math> и высота <math>H</math> изображения и расстояние между соседними пикселями <math>p</math>. Тогда для каждого пикселя с координатами <math>i</math> по горизонтали и <math>j</math> по вертикали вычисляется число <math>c</math> по следующим правилам:

<math>\operatorname{Re} \, c = \overline{x} + \left(i - \frac{W}{2}\right)p</math>

<math>\operatorname{Im} \, c = \overline{y} - \left(j - \frac{H}{2}\right)p</math>

Для полученных <math>c</math> определяется их принадлежность множеству по указанному выше алгоритму с количеством итераций <math>O \left( \frac{1}{\sqrt p} \right)</math><ref name=":1">[https://github.com/cslarsen/mandelbrot-js Mandelbrot.js by cslarsen]</ref> и радиусом выхода 2. В зависимости от того, определяется точка принадлежащей или не принадлежащей множеству, соответствующий ей пиксель окрашивается одним или другим цветом.

Также существуют различные способы построить изображение более наглядно с использованием цвета. Самый простой - окрашивать точки множества черным цветом, а остальные точки окрашивать различными цветами в зависимости от того, сколько потребовалось итераций <math>n</math>, чтобы элемент последовательности <math>z_{n+1} = z_n^2 + c, z_0 = 0</math> превысил радиус выхода. Однако этот метод тоже дает изображение с резкими границами: число итераций - это всегда целое число, и образуются области, окрашенные одним цветом. Более гладкий способ окрашивания точек вне множества использует следующую формулу:

<math>\mu = n + 1 - \frac{\ln(\ln \left| z_n \right|)}{\ln 2}</math>,

где <math>n</math> - число итераций, потребовавшееся для для превышения элементом последовательности радиуса выхода, а <math>z_n</math> - этот элемент<ref name=":2">[http://linas.org/art-gallery/escape/smooth.html Smooth Shading for the Mandelbrot Exterior]</ref>. Для понимания сути этой формулы можно использовать описание, приведенное Earl L. Hinrichs:

<blockquote>«Игнорируя <math>+ c</math> в обычной формуле, получим, что точки последовательности растут как <math>z := z^2</math>. То есть у нас есть последовательность <math>z, z^2, z^4, z^8, z^{16}</math>, и т.д. Подсчет числа итераций означает присвоение целого числа этим значениям. Если игнорировать множитель, логарифм этой последовательности получится: <math>1, 2, 4, 8, 16</math>». Логарифм логарифма: <math>0, 1, 2, 3, 4</math>, что соответствует целому значению из подсчета итераций. Таким образом, подходящим обобщением дискретного подсчета итераций на непрерывную функцию будет двойной логарифм»<ref name=":2" />.</blockquote>

При использовании этой формулы число <math>\mu</math> получается примерно равным <math>n</math>, однако меняющимся практически непрерывно по <math>c</math>.

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

=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
=== Схема реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===
=== Информационный граф ===
=== Ресурс параллелизма алгоритма ===
=== Входные и выходные данные алгоритма ===
=== Свойства алгоритма ===

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

== Литература ==
{{примечания}}

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

Участник:Nbvehbectw/Алгоритм нахождения точек множества Мандельброта