23:10 

Пост номер три

Green October
Текст раз


Этот пост призван не дать дневнику простаивать более двух месяцев и потому не имеет какой-то определённой темы. Подобно одной книжке, тут будет информация типа «Три новых вещи, которые я узнал за подотчётный период». Получилось как-то неожиданно много, поэтому посту присвоен статус «содержательного». Первая вещь будет изложена по привычной схеме возрастания нудных и тоскливых деталей (осторожно, будут формулы!).


Игра хаоса

Наткнулся на такую забавную задачку, литературно обозванную «Игрой хаоса»:

На плоскости задано три точки: А, В, С. В нашем распоряжении имеется монета, которая умеет падать ребром, гербом или решкой. Выберем на плоскости случайную точку X1. Если монета упала гербом, поставим новую точку посередине между X1 и А, если решкой --- посередине между X1 и В, если ребром --- между X1 и С. Обозначим новую точку Х2. Снова подбросим монету и поставим Х3 посередине между Х2 и одной из точек А,В,С по тому же правилу. Повторим эту процедуру много-много раз. Как будет выглядеть набор получившихся точек?


«Фигня вопрос,» --- подумал я, прочитав условие первый раз. За конечное число шагов точка попадёт в треугольник ABC и потом будет в нём до бесконечности болтаться, возможно, полностью его закрашивая. Проверка показывает, что если соединить получившиеся точки линиями, то получится действительно нечто в таком духе:



Однако же, если точки не соединять, то получится нечто гораздо более интересное:







На последней картинке изображен небезызвестный объект --- треугольник Серпинского. Обычно он строится без применения всяких трюков с монеткой: берётся треугольник, из него выкидывается треугольник, образованный основаниями медиан; получается еще три треугольника, из них всё так же выкидываются серединные треугольники, и т. д. Вообще, я был страшно удивлён его появлению, но про это --- потом.

Итак, обещанный ответ на вопрос «Что это?» --- это частный пример так называемой системы итерированных функций (iterated function system, IFS). Идея метода проста: берётся N штук функций, f1(x), f2(x), … , fN(x), и какая-нибудь начальная точка X0. Затем эта точка последовательно сдвигается функциями, применяемыми к ней в случайном порядке: Xk+1(x) = fuk(Xk), где uk --- случайное число от 1 до N. Вот и всё. Если функции выбраны «удачно», то точки X0, X1, …, Х(большая чиселка) образуют любопытную картинку.

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





Если же подойти к вопросу основательно и с фантазией (а не как я), то IFS можно использовать для генерирования изображений всяких природных объектов --- растений, облаков, рельефа. Это, впрочем, выпадает из темы поста.



Важные Общие Слова и Огромное Прикладное Значение --- это, конечно, здорово, но мне больше всего захотелось понять, почему результатом Игры Хаоса является именно треугольник Серпинского. Поначалу мне это показалось вообще ни разу не очевидным. Попробую изложить разъяснение (и тем самым убедить себя, что я сам всё правильно понял). Осторожно, дальше идут скучные рассуждения на пальцах!

В терминах IFS, в Игре Хаоса мы имеем три отображения: каждое сдвигает свой аргумент в сторону одной из точек А,В,С. Как уже упоминалось, несложно сообразить, что абсолютно любая точка за не очень большое число шагов окажется внутри треугольника. Поскольку шагов «много-много», то отбросим начальные точки вне треугольника, и будем считать, что начальная точка с самого начала лежит внутри треугольника. Где может оказаться точка после первого шага? Рассмотрим какую-нибудь одну функцию,скажем, ту, которую приближает к вершине А. Эта функция оставит вершину А на месте; вершина В перейдёт в основание медианы, опущенной на АВ, вершина С --- в основание медианы, опущенной на АС. Соответственно, сторона ВС перейдёт в отрезок, эти два основания соединяющий. Таким образом, весь треугольник АВС перейдёт в подобный ему треугольник с общей вершиной А. Пометим этот новый треугольник синим:


Соответственно, две другие функции отобразят АВС в два похожих треугольника. В итоге, после первого шага АВС может перейти в один из трёх новых треугольников (= начальная точка окажется в одном из них). Обратим внимание, что картинка в точности есть первая итерация построения треугольника Серпинского (выкинут центральный треугольник). Что будет на втором шаге? Пусть на первом мы оказались в синем треугольнике. Тогда на втором шаге он может перейти в один из трёх треугольников (которые мы тоже покрасим в синий):


На третьем шаге точка из Синего-Треугольника-С-Первой-Итерации может оказаться уже в одном из девяти треугольников:


Покрасим оставшиеся два треугольника с первой итерации в красный и зелёный (абсолютно неожиданный выбор цветов) и проследим, куда эти треугольники могут перейти от шага к шагу. Получим такую картинку:


Таким образом, с каждой последующей итерации, вне зависимости от того, какая функция будет выбрана, наша точка будет передвигаться по приближениям треугольника Серпинского; наши функции оказались выбраны так, что они «загоняют» точку всё ближе и ближе к нему.

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



Как уже было сказано, меня очень удивил результат работы Игры Хаоса --- настолько, что, только прочитав условие, я тут же взял лист бумаги, карандаш, и подбросил монетку несколько миллионов раз написал программку для построения траектории. Попытаюсь объяснить мою реакцию.

(Пока есть место в скобках, два слова о переводе: исходное название, Chaos game, правильно было бы перевести как «Хаотическая игра» или «Игра «Хаос»» (по аналогии с «Игрой «Жизнь»»). Название «Игра Хаоса» выбрано мной потому, что оно напоминает мультик «Игра Бендера» роман «Игра Эндера».)

Есть большой класс красивых (по меньшей мере, в визуальном плане) объектов в математике, которые получаются в результате итеративного применения какого-нибудь простого правила. Такие объекты меня всегда привлекали. На втором курсе, умирая со скуки внимательно слушая лекции по системному программированию, я занимался тем, что рисовал кривую Пеано,

(Чудом уцелевший фрагмент с лекции по грамматикам Холмского!)

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



--- трёхмерный аналог треугольника Серпинского. С точки зрения программирования тут есть огромный плюс: все эти кривые Пеано, треугольники Серпинского и прочие драконы Леви очень легко задаются --- надо написать чуть-чуть строчек очень простого кода. Так, на рисование разноцветного треугольника из предыдущего раздела ушло 8 строк кода на Матлабе:

Эта функция рекурсивная; математики --- народ, ленивый ценящий лаконичность, и, как говорил мой семинарист по дискретке, «рекурсия --- значит, легко программировать». У этой лаконичности, впрочем, есть цена: для рисования достаточно большой итерации, скажем, пятнадцатой, придётся сделать 315 = 14348907 вызовов функций. Поскольку вызовы функции вложены друг в друга, то все входные аргументы будут благополучно занимать место в оперативной памяти, пока раскрутка рекурсии не закончится (параметр iter не станет равен maxIter, т. е., 15). В случае приведенной тут функции, один вызов «обходится» в три точки с двумя координатами по восемь байт каждая (48 байт) + три числа по еще восемь байт каждое (24 байта), что в сумме даёт 72 байта за вызов. Казалось бы, копейки, да? Но тогда наши 315 вызовов съедят 315 * 72 = 1033121304 байт, что примерно равно 985 мегабайтам. Для шестнадцатой итерации эта цифра возрастёт в три раза и составит почти три гигабайта. Можно, конечно, справедливо заметить, что А) алгоритм можно переписать из рекурсивного в не рекурсивный и Б) никому такие высокие итерации на фиг не сдались.


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

Два завершающих замечания в стиле «власти скрывают» «на самом деле»:

1. На самом деле, Игра Хаоса лишь «на поверхности» демонстрирует идеально ровный треугольник. Если приблизить изображение несколько раз, скажем, в районе вершины А, то всё встанет на свои места:





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

2. На самом деле, нет ничего удивительного в том, что детерминированный объект эффективно приближается вероятностным процессом. Еще в XVIII веке была рассмотрена и решена следующая задача (т. н. «Игла Бюффона»):

Плоскость разлинована набором параллельных прямых, идущих с одинаковым интервалом. На эту плоскость бросается иголка, длина которой равна расстоянию между соседними прямыми. C какой вероятностью иголка пересечёт какую-нибудь из этих прямых?

Ответ: 2/π. Да, это то же самое π, которое фигурирует в формуле длины окружности (3,1415926...). Казалось бы, откуда оно здесь? Тем не менее, если много-много раз кинуть иглу на плоскость, а потом поделить число пересечений на общее число бросков, то получится величина, довольно близкая к 2/π, что позволяет вычислить число π в бытовых условиях.






Индукционные установки нагрева от Тани™

По-моему, спамеры начали о чём-то догадываться. Некоторое время назад мне на почту пришло такое письмо:


Уважаемый профессор
Это Таня из Китая,"маленький человек",кто работает на заводе. Пишу Вам это письмо--моя большая честь. Прежде всего,благодарю Вас за внимание к моему письмо. Разрешите показать Вам наши установки:

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

Если Вас интересуются наши установки,свяжитесь со мной!И у Вас что-нибудь вопросы,свяжитесь со мной!Надеемся с Вами сотрудничать!


Мне стало интересно, что такое «гауссово ускорение массой». Единственное похожее, на что я наткнулся --- электромагнитный ускоритель масс Гаусса, более известный в народе как гаусган. Теперь, наверно, надо ожидать предложения покупки обогащенного урана.




Смайлики, солнце и глаза


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

Орбитальная ловушка --- очень простая штука, относящаяся скорее к области искусства, нежели математики. Пусть мы хотим нарисовать некую картинку в M на N пикселов, и сопоставим каждому пикселу точку на плоскости. Идея: помещаем на плоскость некоторую картинку, скажем, смайлик («ловушку»). После этого из каждого пиксела будем строить некоторую траекторию на плоскости вида zk+1 = f(zk), где функция f одна на все пикселы. Как только траектория попадёт на ловушку, то окрасим пиксел, из которого она стартовала, в цвет пиксела картинки, куда она пришла. Хотя метод очень прост (и в интернете много картинок с ним), очень непонятно (во всяком случае, мне), как связана форма картинки, используемой в качестве ловушки, и функция f. Если в фракталах Ньютона из предыдущего поста нули функции «подсказывали» внешний вид результат заранее, то тут ничего подобного не наблюдается. В ролике, на который была ссылка, использовалась ловушка в форме квадрата (хотя логичнее было бы использовать ловушку в форме круга (смайлик-то круглый), автор это объясняет техническими причинами) и простая функция вида z2 +c, где c --- комплексное число, определяемое кликом мышки. Я подумал, что от этого уже можно хоть как-то отталкиваться.


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

Смайлик было получить легко:


Потом я решил взять что-то похожее, но не совсем; выбор пал солнце:







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

















Такие дела =)






@музыка: Ayreon --- Unnatural Selection

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

URL
Комментарии
2014-05-02 в 09:55 

-Шинигами-
Лисявое ОБЛО
ГЛАЗИКИ

   

Дневника название

главная