Алгоритмы построения множества Мандельброта

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

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

Самый простой алгоритм создания представления множества Мандельброта известен как алгоритм «времени выхода». Повторяющийся расчет выполняется для каждой точки x , y в области графика, и на основе поведения этого расчета для этого пикселя выбирается цвет.

Неоптимизированный наивный алгоритм времени выхода

Как в неоптимизированном, так и в оптимизированном алгоритмах времени ухода координаты x и y каждой точки используются в качестве начальных значений в повторяющихся или итерирующих вычислениях (подробно описано ниже). Результат каждой итерации используется в качестве начального значения для следующей. Значения проверяются во время каждой итерации, чтобы увидеть, достигли ли они критического состояния «выхода» или «катастрофы». Если это условие достигнуто, расчет останавливается, пиксель рисуется и x , y исследуется следующая точка . Для некоторых начальных значений выход происходит быстро, после небольшого количества итераций. Для начальных значений, очень близких к множеству, но не входящих в него, для выхода могут потребоваться сотни или тысячи итераций. Для значений из множества Мандельброта экранирование никогда не произойдет. Программист или пользователь должен выбрать, сколько итераций – или какую «глубину» – они хотят изучить. Чем выше максимальное количество итераций, тем больше деталей и тонкостей появляется в конечном изображении, но тем больше времени потребуется для расчета фрактального изображения.

Условия побега могут быть простыми и сложными. Поскольку никакое комплексное число с действительной или мнимой частью больше 2 не может быть частью набора, обычным выходом является побег, когда любой из коэффициентов превышает 2. Более сложный в вычислительном отношении метод, который обнаруживает побеги раньше, заключается в вычислении расстояния от начала координат с помощью теорему Пифагора , т.е. для определения абсолютного значения или модуля комплексного числа. Если это значение превышает 2 или, что то же самое, когда сумма квадратов действительной и мнимой частей превышает 4, точка достигла выхода. Более ресурсоемкие варианты рендеринга включают метод Буддхаброта , который находит ускользающие точки и строит график их повторяющихся координат.

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

Для визуализации такого изображения рассматриваемую нами область комплексной плоскости разбивают на определенное количество пикселей . Чтобы раскрасить любой такой пиксель, пусть $c$ быть серединой этого пикселя. Теперь мы повторяем критическую точку 0 под $P_{c}$ , проверяя на каждом шаге, имеет ли точка орбиты модуль больше 2. В этом случае мы знаем, что $c$ не принадлежит множеству Мандельброта, и мы раскрашиваем наш пиксель в соответствии с количеством итераций, использованных для его определения. В противном случае мы продолжаем итерацию до фиксированного количества шагов, после чего решаем, что наш параметр «вероятно» принадлежит множеству Мандельброта или, по крайней мере, очень близок к нему, и окрашиваем пиксель в черный цвет.

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

for each pixel (Px, Py) on the screen do
    x0 := scaled x coordinate of pixel (scaled to lie in the Mandelbrot X scale (-2.00, 0.47))
    y0 := scaled y coordinate of pixel (scaled to lie in the Mandelbrot Y scale (-1.12, 1.12))
    x := 0.0
    y := 0.0
    iteration := 0
    max_iteration := 1000
    while (x*x + y*y ≤ 2*2 AND iteration < max_iteration) do
        xtemp := x*x - y*y + x0
        y := 2*x*y + y0
        x := xtemp
        iteration := iteration + 1
 
    color := palette[iteration]
    plot(Px, Py, color)

Здесь, связывая псевдокод с $c$ , $z$ и $P_{c}$ :

$z=x+iy\$
$z^{2}=x^{2}+2ixy$ - $y^{2}\$
$c=x_{0}+iy_{0}\$

и так, как видно из псевдокода при вычислении x и y :

$x=\mathop {\mathrm {Re} } (z^{2}+c)=x^{2}-y^{2}+x_{0}$ и $y=\mathop {\mathrm {Im} } (z^{2}+c)=2xy+y_{0}.\$

Чтобы получить красочные изображения множества, присвоение цвета каждому значению числа выполненных итераций может быть произведено с помощью одной из множества функций (линейной, экспоненциальной и т. д.). Одним из практических способов, не замедляющих расчеты, является использование количества выполненных итераций в качестве записи в палитре, инициализируемой при запуске. Если таблица цветов содержит, например, 500 записей, то выбор цвета равен n mod 500, где n — количество итераций.

Оптимизированные алгоритмы времени выхода

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

x2:= 0
y2:= 0
w:= 0

while (x2 + y2 ≤ 4 and iteration < max_iteration) do
    x:= x2 - y2 + x0
    y:= w - x2 - y2 + y0
    x2:= x * x
    y2:= y * y
    w:= (x + y) * (x + y)
    iteration:= iteration + 1

Приведенный выше код работает посредством некоторого алгебраического упрощения комплексного умножения:

${\begin{aligned}(iy+x)^{2}&=-y^{2}+2iyx+x^{2}\\&=x^{2}-y^{2}+2iyx\end{aligned}}$

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

Вышеупомянутый внутренний цикл while можно дополнительно оптимизировать, расширив w до

$w=x^{2}+2xy+y^{2}$

Подставив w в $y=w-x^{2}-y^{2}+y_{0}$ урожайность $y=2xy+y_{0}$ и, следовательно, вычисление w больше не требуется.

Дальнейший оптимизированный псевдокод для вышеизложенного:

x2:= 0
y2:= 0

while (x2 + y2 ≤ 4 and iteration < max_iteration) do
    y:= 2 * x * y + y0
    x:= x2 - y2 + x0
    x2:= x * x
    y2:= y * y
    iteration:= iteration + 1

Обратите внимание, что в приведенном выше псевдокоде $2xy$ кажется, увеличивает количество умножений на 1, но поскольку 2 — это множитель, код можно оптимизировать с помощью $(x+x)y$ .

Производная помощь или «дербайл»

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

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

$z_{n}^{\prime }:=(2*z_{n-1}^{\prime }*z_{n-1})+1$

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

Производные можно найти автоматически, используя автоматическое дифференцирование и вычисляя итерации с использованием двойных чисел .

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

Код Python:

Дербейл использовался на съемках горящего корабля Джулии.

def pixel(x: int, y: int, w: int, h: int) -> int:
    def magn(a, b):
        return a * a + b * b

    dbail = 1e6
    ratio = w / h

    x0 = (((2 * x) / w) - 1) * ratio
    y0 = ((2 * y) / h) - 1

    dx_sum = 0
    dy_sum = 0

    iters = 0
    limit = 1024

    while magn(dx_sum, dy_sum) < dbail and iters < limit:
        xtemp = x * x - y * y + x0
        y = 2 * x * y + y0
        x = xtemp

        dx_sum += (dx * x - dy * y) * 2 + 1
        dy_sum += (dy * x + dx * y) * 2

        iters += 1

    return iters

Алгоритмы окраски

Помимо построения набора, были разработаны различные алгоритмы для

эффективно раскрасить комплект эстетически приятным способом
показать структуры данных (научная визуализация)

Раскраска гистограммы

Более сложный метод раскраски включает использование гистограммы , которая связывает каждый пиксель с максимальным количеством итераций этого пикселя перед выходом/выходом из строя. Этот метод будет одинаково распределять цвета по одной и той же общей площади и, что важно, не зависит от выбранного максимального количества итераций. ^[1]

Этот алгоритм имеет четыре прохода. Первый проход включает в себя вычисление количества итераций, связанных с каждым пикселем (но без построения графика пикселей). Они сохраняются в массиве: IterationCounts[x][y], где x и y — координаты x и y указанного пикселя на экране соответственно.



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

Первым шагом второго прохода является создание массива размера n , который соответствует максимальному количеству итераций: NumIterationsPerPixel. Затем необходимо перебрать массив пар счетчиков пикселей и итераций IterationCounts[][] и получить сохраненное количество итераций каждого пикселя i , например, i = IterationCounts[x][y]. каждого пикселя После получения количества итераций i необходимо проиндексировать NumIterationsPerPixel на i и увеличить индексированное значение (которое изначально равно нулю) — например, NumIterationsPerPixel[ i ] = NumIterationsPerPixel[ i ] + 1 .

for (x = 0; x < width; x++) do
    for (y = 0; y < height; y++) do
        i:= IterationCounts[x][y]
        NumIterationsPerPixel[i]++

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

total: = 0
for (i = 0; i < max_iterations; i++) do
    total += NumIterationsPerPixel[i]

После этого начинается четвертый проход, и все значения в массиве IterationCounts индексируются, и для каждого счетчика итераций i , связанного с каждым пикселем, этот счетчик добавляется к глобальной сумме всех счетчиков итераций от 1 до i в массиве. Массив NumIterationsPerPixel. Затем это значение нормализуется путем деления суммы на общее значение, вычисленное ранее.

hue[][]:= 0.0
for (x = 0; x < width; x++) do
    for (y = 0; y < height; y++) do
        iteration:= IterationCounts[x][y]
        for (i = 0; i <= iteration; i++) do
            hue[x][y] += NumIterationsPerPixel[i] / total /* Must be floating-point division. */

...

color = palette[hue[m, n]]

...

Наконец, вычисленное значение используется, например, как индекс цветовой палитры.

Этот метод можно комбинировать с приведенным ниже методом плавной окраски для получения более эстетичных изображений.

Непрерывное (плавное) окрашивание

Это изображение было визуализировано с помощью алгоритма времени выхода. Есть очень очевидные цветные «полосы».

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

Алгоритм времени выхода популярен благодаря своей простоте. Однако он создает цветные полосы, которые, как тип сглаживания , могут умалять эстетическую ценность изображения. Это можно улучшить с помощью алгоритма, известного как «нормализованное количество итераций». ^[2]^[3] что обеспечивает плавный переход цветов между итерациями. Алгоритм связывает действительное число $\nu$ с каждым значением z , используя связь номера итерации с потенциальной функцией . Эта функция определяется выражением

\phi (z)=\lim _{n\to \infty }(\log |z_{n}|/P^{n}),

где z _n — значение после n итераций, а P — степень, до которой z возводится в уравнении множества Мандельброта ( z _{n +1} = z _n^П + c , P обычно 2).

Если мы выберем большой радиус спасения N (например, 10 ¹⁰⁰), у нас такое есть

\log |z_{n}|/P^{n}=\log(N)/P^{\nu (z)}

для некоторого действительного числа $\nu (z)$ , и это

\nu (z)=n-\log _{P}(\log |z_{n}|/\log(N)),

и поскольку n — номер первой итерации такой, что | з _п | > N , число, которое мы вычитаем из n, находится в интервале [0, 1).

Для раскраски нам необходима циклическая шкала цветов (построенная, например, математически) и содержащая H цветов с номерами от 0 до H - 1 ( H например, = 500). Умножаем действительное число $\nu (z)$ по фиксированному вещественному числу, определяющему плотность цветов на изображении, возьмите целую часть этого числа по модулю H и используйте его для поиска соответствующего цвета в таблице цветов.

Например, изменение приведенного выше псевдокода, а также использование концепции линейной интерполяции даст

for each pixel (Px, Py) on the screen do
    x0:= scaled x coordinate of pixel (scaled to lie in the Mandelbrot X scale (-2.5, 1))
    y0:= scaled y coordinate of pixel (scaled to lie in the Mandelbrot Y scale (-1, 1))
    x:= 0.0
    y:= 0.0
    iteration:= 0
    max_iteration:= 1000
    // Here N = 2^8 is chosen as a reasonable bailout radius.

    while x*x + y*y ≤ (1 << 16) and iteration < max_iteration do
        xtemp:= x*x - y*y + x0
        y:= 2*x*y + y0
        x:= xtemp
        iteration:= iteration + 1

    // Used to avoid floating point issues with points inside the set.
    if iteration < max_iteration then
        // sqrt of inner term removed using log simplification rules.
        log_zn:= log(x*x + y*y) / 2
        nu:= log(log_zn / log(2)) / log(2)
        // Rearranging the potential function.
        // Dividing log_zn by log(2) instead of log(N = 1<<8)
        // because we want the entire palette to range from the
        // center to radius 2, NOT our bailout radius.
        iteration:= iteration + 1 - nu

    color1:= palette[floor(iteration)]
    color2:= palette[floor(iteration) + 1]
    // iteration % 1 = fractional part of iteration.
    color:= linear_interpolate(color1, color2, iteration % 1)
    plot(Px, Py, color)

Экспоненциально отображаемые и циклические итерации

Экспоненциальная циклическая раскраска в цветовом пространстве LCH с затенением

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

Когда мы получили количество итераций, мы можем сделать диапазон цветов нелинейным. Возведение значения, нормализованного к диапазону [0,1] в степень n , отображает линейный диапазон в экспоненциальный диапазон, что в нашем случае может подтолкнуть появление цветов вдоль внешней стороны фрактала и позволить нам выявить другие цвета или переместите всю палитру ближе к границе.

$v=((\mathbf {i} /max_{i})^{\mathbf {S} }\mathbf {N} )^{1.5}{\bmod {\mathbf {N} }}$

где i — количество итераций после спасения, max_i — наш лимит итераций, S — показатель степени, до которого мы повышаем итерации, а N — количество элементов в нашей палитре. При этом количество итеров масштабируется нелинейно, а палитра циклически масштабируется примерно пропорционально масштабу.

Затем мы можем подключить v к любому желаемому алгоритму генерации цвета.

Передача итераций в цвет напрямую

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

v относится к нормализованному экспоненциально отображенному счетчику циклических итераций.

f(v) относится к передаточной функции sRGB.

Наивный метод генерации цвета таким способом — напрямую масштабировать v до 255 и передавать его в RGB как таковой.

rgb = [v * 255, v * 255, v * 255]

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

srgb = [v * 255, v * 255, v * 255]

Окраска ВПГ

Раскраску HSV можно выполнить путем сопоставления количества итеров с [0,max_iter) на [0,360), возведя его в степень 1,5, а затем по модулю 360. Затем мы можем просто взять экспоненциально отображенное количество итеров в значение и вернуть

hsv = [powf((i / max) * 360, 1.5) % 360, 100, (i / max) * 100]

Этот метод применим и к HSL, за исключением того, что вместо этого мы передаем насыщенность 50%.

hsl = [powf((i / max) * 360, 1.5) % 360, 50, (i / max) * 100]

ЛЧ раскраска

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

${\textstyle {\begin{array}{lcl}x&\in &\mathbb {Q+} \\s_{i}&=&(i/max_{i})^{\mathbf {x} }\\v&=&1.0-cos^{2}(\pi s_{i})\\L&=&75-(75v)\\C&=&28+(75-75v)\\H&=&(360s_{i})^{1.5}{\bmod {3}}60\end{array}}}$

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

s = iters/max_i;
v = 1.0 - powf(cos(pi * s), 2.0);
LCH = [75 - (75 * v), 28 + (75 - (75 * v)), powf(360 * s, 1.5) % 360];

Расширенные алгоритмы построения графиков

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

Оценка расстояния

Можно вычислить расстояние от точки c ( внешней или внутренней ) до ближайшей точки на границе множества Мандельброта. ^[4]^[5]

Оценка внешнего расстояния

Доказательство связности множества Мандельброта фактически дает формулу униформизирующего дополнения для отображения $M$ (и производная от этой карты). По теореме Кебе о четверти можно затем оценить расстояние между серединой нашего пикселя и набором Мандельброта с коэффициентом 4.

Другими словами, при условии, что максимальное число итераций достаточно велико, получается картина множества Мандельброта со следующими свойствами:

Каждый пиксель, содержащий точку множества Мандельброта, окрашен в черный цвет.
Каждый пиксель, окрашенный в черный цвет, близок к множеству Мандельброта.

Верхняя граница b для оценки расстояния пикселя c (комплексного числа) из множества Мандельброта определяется выражением ^[6]^[7]^[8]

b=\lim _{n\to \infty }{\frac {2\cdot |{P_{c}^{n}(c)|\cdot \ln |{P_{c}^{n}(c)}}|}{|{\frac {\partial }{\partial {c}}}P_{c}^{n}(c)|}},

где

$P_{c}(z)\,$ означает комплексный квадратичный полином
$P_{c}^{n}(c)$ означает n итераций $P_{c}(z)\to z$ или $z^{2}+c\to z$ , начиная с $z=c$ : $P_{c}^{0}(c)=c$ , $P_{c}^{n+1}(c)=P_{c}^{n}(c)^{2}+c$ ;
${\frac {\partial }{\partial {c}}}P_{c}^{n}(c)$ является производной от $P_{c}^{n}(c)$ относительно ц. Эту производную можно найти, начав с ${\frac {\partial }{\partial {c}}}P_{c}^{0}(c)=1$ а потом ${\frac {\partial }{\partial {c}}}P_{c}^{n+1}(c)=2\cdot {}P_{c}^{n}(c)\cdot {\frac {\partial }{\partial {c}}}P_{c}^{n}(c)+1$ . В этом легко убедиться, воспользовавшись цепным правилом для производной.

Идея этой формулы проста: когда эквипотенциальные линии потенциальной функции $\phi (z)$ лежи рядом, число $|\phi '(z)|$ велика, и, наоборот, поэтому эквипотенциальные линии для функции $\phi (z)/|\phi '(z)|$ должно лежать примерно регулярно.

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

Как только b найдено по теореме Кебе 1/4, мы знаем, что не существует точки множества Мандельброта с расстоянием от c меньшим, чем b/4 .

Оценку расстояния можно использовать для рисования границы множества Мандельброта, см. статью Множество Юлии . В этом подходе пиксели, достаточно близкие к M, рисуются другим цветом. Это создает рисунки, на которых легко увидеть тонкие «нити» множества Мандельброта. Этот прием с успехом используется в черно-белых изображениях множеств Мандельброта в книгах «Красота фракталов». ^[9]и «Наука о фрактальных изображениях». ^[10]

Вот пример черно-белого изображения, отрендеренного с использованием оценки расстояния:

Оценку расстояния также можно использовать для рендеринга 3D-изображений множеств Мандельброта и Жюлиа.

Оценка внутреннего расстояния

Также возможно оценить расстояние предельно периодической (т. е. гиперболической ) точки до границы множества Мандельброта. Верхняя граница b для оценки расстояния определяется выражением ^[4]

b={\frac {1-\left|{{\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0})}\right|^{2}}{\left|{{\frac {\partial }{\partial {c}}}{\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0})+{\frac {\partial }{\partial {z}}}{\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0}){\frac {{\frac {\partial }{\partial {c}}}P_{c}^{p}(z_{0})}{1-{\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0})}}}\right|}},

где

$p$ это период,
$c$ это точка, которую нужно оценить,
$P_{c}(z)$ - комплексный квадратичный многочлен $P_{c}(z)=z^{2}+c$
$P_{c}^{p}(z_{0})$ это $p$ -кратная итерация $P_{c}(z)\to z$ , начиная с $P_{c}^{0}(z)=z_{0}$
$z_{0}$ это что-то из $p$ точки, которые составляют аттрактор итераций $P_{c}(z)\to z$ начиная с $P_{c}^{0}(z)=c$ ; $z_{0}$ удовлетворяет $z_{0}=P_{c}^{p}(z_{0})$ ,
${\frac {\partial }{\partial {c}}}{\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0})$ , ${\frac {\partial }{\partial {z}}}{\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0})$ , ${\frac {\partial }{\partial {c}}}P_{c}^{p}(z_{0})$ и ${\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0})$ представляют собой различные производные от $P_{c}^{p}(z)$ , оцененный в $z_{0}$ .

Аналогично внешнему случаю: как только b найдено, мы знаем, что все точки на расстоянии b /4 от c находятся внутри множества Мандельброта.

С оценкой внутреннего расстояния возникают две практические проблемы: во-первых, нам нужно найти $z_{0}$ именно, а во-вторых, нам нужно найти $p$ именно так. Проблема с $z_{0}$ заключается в том, что сходимость к $z_{0}$ путем итерации $P_{c}(z)$ теоретически требует бесконечного числа операций. Проблема с любым данным $p$ заключается в том, что иногда из-за ошибок округления период ошибочно идентифицируется как целое число, кратное реальному периоду (например, обнаруживается период 86, тогда как действительный период равен только 43=86/2). В таком случае расстояние завышено, т. е. заявленный радиус может содержать точки вне множества Мандельброта.

3D-вид: наименьшее абсолютное значение орбиты внутренних точек множества Мандельброта.

Проверка кардиоиды/лампочки

Один из способов улучшить расчеты — заранее выяснить, лежит ли данная точка внутри кардиоиды или в колбе периода 2. Прежде чем передавать комплексное значение через алгоритм времени выхода, сначала убедитесь, что:

p={\sqrt {\left(x-{\frac {1}{4}}\right)^{2}+y^{2}}}

,

x\leq p-2p^{2}+{\frac {1}{4}}

,

(x+1)^{2}+y^{2}\leq {\frac {1}{16}}

,

где x представляет собой реальное значение точки, а y — мнимое значение. Первые два уравнения определяют, что точка находится внутри кардиоиды, последнее — лампочки периода 2.

Кардиоидный тест можно эквивалентно выполнить без квадратного корня:

q=\left(x-{\frac {1}{4}}\right)^{2}+y^{2},

q\left(q+\left(x-{\frac {1}{4}}\right)\right)\leq {\frac {1}{4}}y^{2}.

Почки 3-го и более высокого порядка не имеют эквивалентных раковин, поскольку они не являются идеально круглыми. ^[11] Однако можно определить, находятся ли точки внутри кругов, вписанных в эти луковицы более высокого порядка, что предотвращает повторение многих, хотя и не всех, точек в луковице.

Проверка периодичности

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

xold := 0
yold := 0
period := 0
while (x*x + y*y ≤ 2*2 and iteration < max_iteration) do
    xtemp := x*x - y*y + x0
    y := 2*x*y + y0
    x := xtemp
    iteration := iteration + 1 
 
    if x ≈ xold and y ≈ yold then
        iteration := max_iteration  /* Set to max for the color plotting */
        break        /* We are inside the Mandelbrot set, leave the while loop */
 
    period:= period + 1
    if period > 20 then
        period := 0
        xold := x
        yold := y

Приведенный выше код сохраняет новое значение x и y каждые 20. ^й итерации, поэтому он может обнаруживать периоды длиной до 20 пунктов.

Отслеживание границ / проверка краев

Поскольку множество Мандельброта полно , ^[12] любая точка, заключенная в замкнутую фигуру, границы которой полностью лежат в пределах множества Мандельброта, сама должна принадлежать множеству Мандельброта. Трассировка границ работает, отслеживая лемнискаты различных уровней итерации (цветные полосы) по всему набору, а затем сразу заполняя всю полосу. Это также обеспечивает увеличение скорости, поскольку теперь можно пропустить большое количество точек. ^[13]

Анимация отслеживания границы

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

Проверка прямоугольника

Проверка прямоугольника — более старый и простой метод построения множества Мандельброта. Основная идея проверки прямоугольника заключается в том, что если каждый пиксель на границе прямоугольника имеет одинаковое количество итераций, то прямоугольник можно безопасно заполнить, используя это количество итераций. Существует несколько вариантов метода проверки прямоугольников, однако все они медленнее, чем метод трассировки границ, поскольку в конечном итоге они вычисляют больше пикселей. Один вариант просто вычисляет угловые пиксели каждого прямоугольника, однако это приводит к повреждению изображений чаще, чем вычисление всей границы, поэтому он работает достаточно хорошо только в том случае, если используются только маленькие прямоугольники размером около 6x6 пикселей и без рекурсии из больших блоков. ( Метод фрактинта .)

Самый простой метод проверки прямоугольников заключается в проверке границ прямоугольников одинакового размера, напоминающих сетку. (Алгоритм Мариани.) ^[14]

Более быстрый и немного более продвинутый вариант — сначала рассчитать блок большего размера, скажем, 25x25 пикселей. Если вся граница поля имеет один и тот же цвет, просто заполните его тем же цветом. Если нет, то разделите блок на четыре блока размером 13x13 пикселей, повторно используя уже вычисленные пиксели в качестве внешней границы и разделив внутренние «перекрестные» пиксели между внутренними блоками. Снова заполните те поля, у которых есть только один цвет границы. А те блоки, которые этого не делают, разделите теперь на четыре блока размером 7x7 пикселей. А потом те, что "проваливаются" в коробки 4х4. (Алгоритм Мариани-Сильвера.)

Еще быстрее — разделить коробки пополам, а не на четыре. Тогда может быть оптимальным использовать коробки с соотношением сторон 1,4:1 , чтобы их можно было разделить так же, как листы формата А3 складываются в листы формата А4 и А5. (Подход DIN.)

Как и при трассировке границ, проверка прямоугольников работает только в областях с одним дискретным цветом. Но даже если внешняя область использует плавную/непрерывную окраску, проверка прямоугольников все равно ускорит дорогостоящую внутреннюю область множества Мандельброта. Если только внутренняя область не использует какой-либо метод плавной окраски, например, оценку внутреннего расстояния .

Использование симметрии

Горизонтальная симметрия множества Мандельброта позволяет пропускать части процесса рендеринга при наличии реальной оси в конечном изображении. Однако независимо от того, какая часть зеркально отображается, будет отображено одинаковое количество точек.

Множества Джулии имеют симметрию относительно начала координат. Это означает, что квадрант 1 и квадрант 3 симметричны, а квадрант 2 и квадрант 4 симметричны. Поддержка симметрии для множеств Мандельброта и Жюлиа требует разного подхода к симметрии для двух разных типов графов.

Многопоточность

Рендеринг множеств Мандельброта и Джулии в режиме Escape-Time чрезвычайно хорошо подходит для параллельной обработки. На многоядерных машинах область, подлежащая построению, может быть разделена на ряд прямоугольных областей, которые затем могут быть предоставлены как набор задач для обработки пулом потоков рендеринга. Это досадная параллель ^[15] вычислительная проблема. (Обратите внимание, что наилучшего ускорения можно добиться, если сначала исключить симметричные области графика, а затем разделить оставшиеся уникальные области на прямоугольные области.) ^[16]

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

Это короткое видео, показывающее рендеринг множества Мандельброта с использованием многопоточности и симметрии, но с отключенным следованием границам.

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

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

Теория возмущений и рядовая аппроксимация

Очень сильно увеличенные изображения требуют большей точности, чем стандартные 64–128 бит или около того, которые обеспечивают большинство аппаратных модулей с плавающей запятой , что требует от рендереров использовать медленные «BigNum» или « произвольной точности математические библиотеки » для вычислений. Однако этот процесс можно ускорить, используя теорию возмущений . Данный

z_{n+1}=z_{n}^{2}+c

как итерация, так и небольшой эпсилон и дельта, это тот случай, когда

(z_{n}+\epsilon )^{2}+(c+\delta )=z_{n}^{2}+2z_{n}\epsilon +\epsilon ^{2}+c+\delta ,

или

=z_{n+1}+2z_{n}\epsilon +\epsilon ^{2}+\delta ,

поэтому, если кто-то определяет

\epsilon _{n+1}=2z_{n}\epsilon _{n}+\epsilon _{n}^{2}+\delta ,

можно вычислить одну точку (например, центр изображения) с помощью высокоточной арифметики ( z ), дав опорную орбиту , а затем вычислить множество точек вокруг нее с точки зрения различных начальных смещений дельта плюс вышеуказанная итерация для эпсилон, где epsilon-zero установлен в 0. Для большинства итераций epsilon не требуется более 16 значащих цифр, и, следовательно, для получения наиболее точного изображения можно использовать аппаратные средства с плавающей запятой. ^[17] Часто встречаются области, где орбиты точек настолько расходятся с опорной орбитой, что требуется дополнительная точность в этих точках или же требуются дополнительные локальные, рассчитанные с высокой точностью опорные орбиты. Измеряя расстояние по орбите между опорной точкой и точкой, рассчитанной с низкой точностью, можно обнаружить, что правильно вычислить точку невозможно, и расчет можно остановить. Эти неправильные точки впоследствии могут быть пересчитаны, например, из другой более близкой контрольной точки.

Далее можно аппроксимировать стартовые значения для точек низкой точности усеченным рядом Тейлора , что часто позволяет пропустить значительное количество итераций. ^[18] Рендереры, реализующие эти методы, общедоступны и обеспечивают ускорение обработки сильно увеличенных изображений примерно на два порядка. ^[19]

Альтернативное объяснение вышесказанного:

Для центральной точки диска $c$ и его итерации $z_{n}$ , и произвольная точка диска $c+\delta$ и его итерации $z'_{n}$ , можно определить следующие итерационные отношения:

z'_{n}=z_{n}+\epsilon _{n}

С $\epsilon _{1}=\delta$ . Последовательные итерации $\epsilon _{n}$ можно найти, используя следующее:

z'_{n+1}={z'_{n}}^{2}+(c+\delta )

z'_{n+1}=(z_{n}+\epsilon _{n})^{2}+c+\delta

z'_{n+1}={z_{n}}^{2}+c+2z_{n}\epsilon _{n}+{\epsilon _{n}}^{2}+\delta

z'_{n+1}=z_{n+1}+2z_{n}\epsilon _{n}+{\epsilon _{n}}^{2}+\delta

Теперь из исходного определения:

z'_{n+1}=z_{n+1}+\epsilon _{n+1}

,

Отсюда следует, что:

\epsilon _{n+1}=2z_{n}\epsilon _{n}+{\epsilon _{n}}^{2}+\delta

Поскольку итеративные отношения связывают произвольную точку с центральной точкой с помощью очень небольшого изменения $\delta$ , то большая часть итераций $\epsilon _{n}$ также малы и могут быть рассчитаны с использованием аппаратных средств с плавающей запятой.

Однако для каждой произвольной точки диска можно вычислить значение для заданного значения. $\epsilon _{n}$ без необходимости перебирать последовательность из $\epsilon _{0}$ , выражая $\epsilon _{n}$ как степенной ряд $\delta$ .

\epsilon _{n}=A_{n}\delta +B_{n}\delta ^{2}+C_{n}\delta ^{3}+\dotsc

С $A_{1}=1,B_{1}=0,C_{1}=0,\dotsc$ .

Теперь, учитывая итерационное уравнение $\epsilon$ , можно вычислить коэффициенты степенного ряда для каждого $\epsilon _{n}$ :

\epsilon _{n+1}=2z_{n}\epsilon _{n}+{\epsilon _{n}}^{2}+\delta

\epsilon _{n+1}=2z_{n}(A_{n}\delta +B_{n}\delta ^{2}+C_{n}\delta ^{3}+\dotsc )+(A_{n}\delta +B_{n}\delta ^{2}+C_{n}\delta ^{3}+\dotsc )^{2}+\delta

\epsilon _{n+1}=(2z_{n}A_{n}+1)\delta +(2z_{n}B_{n}+{A_{n}}^{2})\delta ^{2}+(2z_{n}C_{n}+2A_{n}B_{n})\delta ^{3}+\dotsc

Следовательно, отсюда следует, что:

A_{n+1}=2z_{n}A_{n}+1

B_{n+1}=2z_{n}B_{n}+{A_{n}}^{2}

C_{n+1}=2z_{n}C_{n}+2A_{n}B_{n}

\vdots

Коэффициенты в степенном ряду можно рассчитать как итеративный ряд, используя только значения из итераций центральной точки. $z$ , и не меняться ни для какой произвольной точки диска. Если $\delta$ очень маленький, $\epsilon _{n}$ должна быть вычислена с достаточной точностью, используя лишь несколько членов степенного ряда. Поскольку контуры выхода Мандельброта «непрерывны» на комплексной плоскости, если время ухода точки было рассчитано, то время ухода соседних точек должно быть одинаковым. Интерполяция соседних точек должна дать хорошую оценку того, с чего начать $\epsilon _{n}$ ряд.

Кроме того, отдельная интерполяция точек реальной оси и точек мнимой оси должна обеспечить как верхнюю, так и нижнюю границу вычисляемой точки. Если оба результата одинаковы (т.е. оба ускользают или не ускользают), то разница $\Delta n$ может использоваться для отказа до тех пор, пока не будут установлены верхняя и нижняя границы. Если аппаратное обеспечение с плавающей запятой может использоваться для итерации $\epsilon$ серии, то существует связь между тем, сколько итераций может быть выполнено за время, необходимое для использования программного обеспечения BigNum для вычисления заданного числа. $\epsilon _{n}$ . Если разница между границами превышает количество итераций, можно выполнить двоичный поиск с помощью программного обеспечения BigNum, последовательно сокращая разрыв вдвое, пока не станет более эффективным по времени поиск управляющего значения с использованием оборудования с плавающей запятой.

Ссылки

^ «Новичок: как сопоставить цвета в множестве Мандельброта?» . www.fractalforums.com . Май 2007 г. Архивировано из оригинала 9 сентября 2022 г. Проверено 11 февраля 2020 г.
^ Гарсия, Фрэнсис; Анхель Фернандес; Хавьер Барралло; Луис Мартин. «Раскраска динамических систем в комплексной плоскости» (PDF ) Архивировано (PDF) 30 ноября. из оригинала Получено 21 января. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Линас Вепстас. «Перенормировка выхода Мандельброта» . Архивировано из оригинала 14 февраля 2020 года . Проверено 11 февраля 2020 г.
^ Перейти обратно: ^а ^б Альберт Лобо. «Внутренние и внешние границы расстояний множества Мандельброта» . Архивировано из оригинала 9 сентября 2022 года . Проверено 29 апреля 2021 г.
^ Уилсон, доктор Линдси Роберт (2012). «Метод оценки расстояния для рисования множеств Мандельброта и Жюлиа» (PDF) . Архивировано (PDF) из оригинала 3 мая 2021 года . Проверено 3 мая 2021 г.
^ Шерита, Арно (2016). «Методы обнаружения границ с помощью оценщиков расстояний» . Архивировано из оригинала 18 декабря 2022 года . Проверено 2 января 2023 г.
^ Кристенсен, Микаэль Хвидтфельдт (2011). «Трехмерные фракталы с оценкой расстояния (V): лампочка Мандельбулбы и различные приближения DE» . Архивировано из оригинала 13 мая 2021 года . Проверено 10 мая 2021 г.
^ Данг, Юмей; Луи Кауфман ; Дэниел Сандин (2002). «Глава 3.3: Формула оценки расстояния». Гиперкомплексные итерации: оценка расстояния и фракталы более высоких измерений (PDF) . Всемирная научная. стр. 17–18. Архивировано (PDF) из оригинала 23 марта 2021 года . Проверено 29 апреля 2021 г.
^ Пейтген, Хайнц-Отто; Рихтер Питер (1986). Красота фракталов . Гейдельберг: Springer-Verlag. ISBN 0-387-15851-0 .
^ Пейтген, Хайнц-Отто; Саупе Дитмар (1988). Наука фрактальных изображений . Нью-Йорк: Springer Verlag. стр. 202. ИСБН 0-387-96608-0 .
^ «Математика почек Мандельброта» . Архивировано из оригинала 14 февраля 2020 года . Проверено 11 февраля 2020 г.
^ Дуади, Адриан; Хаббард, Джон (2009). «Исследование множества Мандельброта. Исследование множества Мандельброта. Записки Орсе» . Проверено 9 апреля 2023 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ «Метод отслеживания границ» . Архивировано из оригинала 20 февраля 2015 года.
^ Дьюдни, АК (1989). «Компьютерные развлечения, февраль 1989 года; Экскурсия по Мандельброту, расположенному на борту Мандельбуса». Научный американец . п. 111. JSTOR 24987149 . (требуется подписка)
^ http://courses.cecs.anu.edu.au/courses/COMP4300/lectures/embParallel.4u.pdf. Архивировано 27 января 2020 г. в Wayback Machine. ^{[ только URL-адрес PDF ]}
^ http://cseweb.ucsd.edu/groups/csag/html/teaching/cse160s05/lectures/Lecture14.pdf. Архивировано 26 января 2020 г. в Wayback Machine. ^{[ только URL-адрес PDF ]}
^ «Суперфрактальная вещь — рендеринг множества Мандельброта произвольной точности на Java» . Архивировано из оригинала 30 июня 2020 года . Проверено 11 февраля 2020 г.
^ КИ Мартин. «Суперфрактальная математика» (PDF) . Архивировано из оригинала (PDF) 28 июня 2014 года . Проверено 11 февраля 2020 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ «Каллес Фракталер 2» . Архивировано из оригинала 24 февраля 2020 года . Проверено 11 февраля 2020 г.

[1] «Новичок: как сопоставить цвета в множестве Мандельброта?» . www.fractalforums.com . Май 2007 г. Архивировано из оригинала 9 сентября 2022 г. Проверено 11 февраля 2020 г.

[2] Гарсия, Фрэнсис; Анхель Фернандес; Хавьер Барралло; Луис Мартин. «Раскраска динамических систем в комплексной плоскости» (PDF ) Архивировано (PDF) 30 ноября. из оригинала Получено 21 января. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[3] Линас Вепстас. «Перенормировка выхода Мандельброта» . Архивировано из оригинала 14 февраля 2020 года . Проверено 11 февраля 2020 г.

[Albert_Lobo-4] Перейти обратно: ^а ^б Альберт Лобо. «Внутренние и внешние границы расстояний множества Мандельброта» . Архивировано из оригинала 9 сентября 2022 года . Проверено 29 апреля 2021 г.

[5] Уилсон, доктор Линдси Роберт (2012). «Метод оценки расстояния для рисования множеств Мандельброта и Жюлиа» (PDF) . Архивировано (PDF) из оригинала 3 мая 2021 года . Проверено 3 мая 2021 г.

[Cheritat-6] Шерита, Арно (2016). «Методы обнаружения границ с помощью оценщиков расстояний» . Архивировано из оригинала 18 декабря 2022 года . Проверено 2 января 2023 г.

[Syntopia-7] Кристенсен, Микаэль Хвидтфельдт (2011). «Трехмерные фракталы с оценкой расстояния (V): лампочка Мандельбулбы и различные приближения DE» . Архивировано из оригинала 13 мая 2021 года . Проверено 10 мая 2021 г.

[8] Данг, Юмей; Луи Кауфман ; Дэниел Сандин (2002). «Глава 3.3: Формула оценки расстояния». Гиперкомплексные итерации: оценка расстояния и фракталы более высоких измерений (PDF) . Всемирная научная. стр. 17–18. Архивировано (PDF) из оригинала 23 марта 2021 года . Проверено 29 апреля 2021 г.

[9] Пейтген, Хайнц-Отто; Рихтер Питер (1986). Красота фракталов . Гейдельберг: Springer-Verlag. ISBN 0-387-15851-0 .

[10] Пейтген, Хайнц-Отто; Саупе Дитмар (1988). Наука фрактальных изображений . Нью-Йорк: Springer Verlag. стр. 202. ИСБН 0-387-96608-0 .

[11] «Математика почек Мандельброта» . Архивировано из оригинала 14 февраля 2020 года . Проверено 11 февраля 2020 г.

[Proof_of_connectedness-12] Дуади, Адриан; Хаббард, Джон (2009). «Исследование множества Мандельброта. Исследование множества Мандельброта. Записки Орсе» . Проверено 9 апреля 2023 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[13] «Метод отслеживания границ» . Архивировано из оригинала 20 февраля 2015 года.

[14] Дьюдни, АК (1989). «Компьютерные развлечения, февраль 1989 года; Экскурсия по Мандельброту, расположенному на борту Мандельбуса». Научный американец . п. 111. JSTOR 24987149 . (требуется подписка)

[15] ttp://courses.cecs.anu.edu.au/courses/COMP4300/lectures/embParallel.4u.pdf. Архивировано 27 января 2020 г. в Wayback Machine. ^{[ только URL-адрес PDF ]}

[16] ttp://cseweb.ucsd.edu/groups/csag/html/teaching/cse160s05/lectures/Lecture14.pdf. Архивировано 26 января 2020 г. в Wayback Machine. ^{[ только URL-адрес PDF ]}

[17] «Суперфрактальная вещь — рендеринг множества Мандельброта произвольной точности на Java» . Архивировано из оригинала 30 июня 2020 года . Проверено 11 февраля 2020 г.

[18] КИ Мартин. «Суперфрактальная математика» (PDF) . Архивировано из оригинала (PDF) 28 июня 2014 года . Проверено 11 февраля 2020 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[19] «Каллес Фракталер 2» . Архивировано из оригинала 24 февраля 2020 года . Проверено 11 февраля 2020 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

v т и Фракталы
Characteristics	Fractal dimensions Assouad Box-counting Higuchi Correlation Hausdorff Packing Topological Recursion Self-similarity
Iterated function system	Barnsley fern Cantor set Koch snowflake Menger sponge Sierpinski carpet Sierpinski triangle Apollonian gasket Fibonacci word Space-filling curve Blancmange curve De Rham curve Minkowski Dragon curve Hilbert curve Koch curve Lévy C curve Moore curve Peano curve Sierpiński curve Z-order curve String T-square n-flake Vicsek fractal Hexaflake Gosper curve Pythagoras tree Weierstrass function
Strange attractor	Multifractal system
L-system	Fractal canopy Space-filling curve H tree
Escape-time fractals	Burning Ship fractal Julia set Filled Newton fractal Douady rabbit Lyapunov fractal Mandelbrot set Misiurewicz point Multibrot set Newton fractal Tricorn Mandelbox Mandelbulb
Rendering techniques	Buddhabrot Orbit trap Pickover stalk
Random fractals	Brownian motion Brownian tree Brownian motor Fractal landscape Lévy flight Percolation theory Self-avoiding walk
People	Michael Barnsley Georg Cantor Bill Gosper Felix Hausdorff Desmond Paul Henry Gaston Julia Helge von Koch Paul Lévy Aleksandr Lyapunov Benoit Mandelbrot Hamid Naderi Yeganeh Lewis Fry Richardson Wacław Sierpiński
Other	"How Long Is the Coast of Britain?" Coastline paradox Fractal art List of fractals by Hausdorff dimension The Fractal Geometry of Nature (1982 book) The Beauty of Fractals (1986 book) Chaos: Making a New Science (1987 book) Kaleidoscope Chaos theory

v т и Информатика
Note: This template roughly follows the 2012 ACM Computing Classification System.
Hardware	Printed circuit board Peripheral Integrated circuit Very Large Scale Integration Systems on Chip (SoCs) Energy consumption (Green computing) Electronic design automation Hardware acceleration Processor Size / Form
Computer systems organization	Computer architecture Computational complexity Dependability Embedded system Real-time computing
Networks	Network architecture Network protocol Network components Network scheduler Network performance evaluation Network service
Software organization	Interpreter Middleware Virtual machine Operating system Software quality
Software notations and tools	Programming paradigm Programming language Compiler Domain-specific language Modeling language Software framework Integrated development environment Software configuration management Software library Software repository
Software development	Control variable Software development process Requirements analysis Software design Software construction Software deployment Software engineering Software maintenance Programming team Open-source model
Theory of computation	Model of computation Formal language Automata theory Computability theory Computational complexity theory Logic Semantics
Algorithms	Algorithm design Analysis of algorithms Algorithmic efficiency Randomized algorithm Computational geometry
Mathematics of computing	Discrete mathematics Probability Statistics Mathematical software Information theory Mathematical analysis Numerical analysis Theoretical computer science
Information systems	Database management system Information storage systems Enterprise information system Social information systems Geographic information system Decision support system Process control system Multimedia information system Data mining Digital library Computing platform Digital marketing World Wide Web Information retrieval
Security	Cryptography Formal methods Security hacker Security services Intrusion detection system Hardware security Network security Information security Application security
Human–computer interaction	Interaction design Social computing Ubiquitous computing Visualization Accessibility
Concurrency	Concurrent computing Parallel computing Distributed computing Multithreading Multiprocessing
Artificial intelligence	Natural language processing Knowledge representation and reasoning Computer vision Automated planning and scheduling Search methodology Control method Philosophy of artificial intelligence Distributed artificial intelligence
Machine learning	Supervised learning Unsupervised learning Reinforcement learning Multi-task learning Cross-validation
Graphics	Animation Rendering Photograph manipulation Graphics processing unit Mixed reality Virtual reality Image compression Solid modeling
Applied computing	Quantum Computing E-commerce Enterprise software Computational mathematics Computational physics Computational chemistry Computational biology Computational social science Computational engineering Differentiable computing Computational healthcare Digital art Electronic publishing Cyberwarfare Electronic voting Video games Word processing Operations research Educational technology Document management
Category Outline Glossaries