Несколько модулей из Makarov Math Suite
Представляю несколько модулей из моей программы Makarov Math Suite. Здесь математические идеи превращаются в интерактивные эксперименты: можно менять условия, наблюдать результат и разбираться, почему всё работает именно так.
Как нарисовать плавный изгиб, не задавая положение каждой его точки? Эта задача возникает при создании шрифтов, автомобильных кузовов, анимации и компьютерной графики. Один из ответов - кривая Безье: достаточно нескольких управляющих точек, чтобы описать целую линию. Крайние точки задают её начало и конец, а промежуточные направляют изгиб, хотя сама кривая вовсе не обязана проходить через них.
В модуле можно увидеть, как такая линия строится. Алгоритм де Кастельжо последовательно выбирает точки на отрезках, соединяет их новыми отрезками и повторяет этот процесс, пока не остаётся одна точка на кривой. Меняется единственный параметр - и эта точка прочерчивает весь изгиб. На трёхмерной чертёжной доске абстрактный расчёт становится наглядной геометрической конструкцией.
Переместите управляющую точку и проследите, как изменится форма. Затем переключитесь на кубический B-сплайн: его линия составлена из согласованных участков. Сдвиньте управляющую точку возле края и заметьте, что часть кривой изменится, а другая сохранит форму. Так становится понятно, почему одни инструменты удобнее для отдельного изгиба, а другие - для длинного контура, который нужно аккуратно редактировать по частям.
Представьте доску с вбитыми гвоздиками. Если охватить их резинкой и отпустить её, резинка натянется вокруг самых крайних гвоздиков. Получившийся контур - выпуклая оболочка: наименьшая выпуклая область, содержащая все точки. Выпуклость означает, что отрезок между любыми двумя точками этой области целиком остаётся внутри неё.
Для человека внешний контур часто очевиден. Компьютеру нужен алгоритм. Метод Джарвиса обходит границу, последовательно выбирая следующую вершину. Алгоритм Грэхема упорядочивает точки и отбрасывает повороты, нарушающие выпуклость. QuickHull разбивает задачу на части, выделяя наиболее удалённые точки. Разные пути приводят к одной и той же геометрической оболочке, но требуют разного количества проверок.
В модуле точки превращены в штырьки, а граница - в натягивающийся пояс. Добавляйте точки внутри и снаружи контура, переключайте алгоритмы, сравнивайте площадь и число проверок ориентации. Точка внутри может вообще не изменить границу, тогда как одна новая внешняя точка перестроит целую её часть. Эта простая задача помогает понять, как компьютер выделяет форму из набора отдельных координат.
Как найти самый высокий пик, если перед вами сложный рельеф с множеством вершин? Двигаться только вверх недостаточно: можно остановиться на ближайшей горке, так и не узнав о более высокой. Генетический алгоритм ищет решение целой популяцией кандидатов и использует идеи отбора, наследования и мутаций.
В этой модели каждый кандидат закодирован последовательностью битов, а его положение на рельефе определяет качество решения. Более удачные кандидаты чаще становятся родителями. Скрещивание объединяет части их кодов, мутации случайно меняют отдельные биты. На сцене поколения показаны фигурками исследователей, а высота ландшафта соответствует значению целевой функции. Элитизм позволяет сохранить лучший найденный вариант при переходе к следующему поколению.
Изменяйте вероятность мутаций и наблюдайте одновременно за лучшим результатом и разнообразием популяции. При слишком слабых изменениях поиск может преждевременно сосредоточиться возле одной вершины; при слишком сильных - постоянно терять удачные сочетания. Метод не гарантирует нахождения глобального максимума, но показывает важный принцип оптимизации: успешный поиск требует и использования найденного, и исследования ещё неизвестного.
Светлячки могут вспыхивать согласованно, а связанные колебательные системы - постепенно подстраивать свои ритмы друг под друга. Как возникает такой порядок без единого дирижёра? Модель Курамото выделяет одну сторону этой задачи: у каждого участника есть собственная частота и фаза, но взаимодействие с остальными влияет на скорость изменения фазы.
В модуле сорок осцилляторов представлены огоньками и движущимися отметками на круговой шкале. При слабой связи различия частот разгоняют фазы в разные стороны. Достаточно сильное взаимодействие может собрать их в согласованную группу. Общая стрелка показывает параметр порядка R: он близок к единице, когда фазы почти совпадают, и мал, когда они распределены так, что взаимно компенсируются.
Увеличьте связь, затем расширьте разброс собственных частот. Посмотрите, когда вспышки начинают совпадать и насколько устойчиво это согласование. Одинаковый средний темп ещё не требует полного совпадения фаз: участники могут сохранять постоянные сдвиги друг относительно друга. Это упрощённая модель, но она позволяет увидеть, как коллективный ритм рождается из множества взаимных подстроек.
У этого муравья нет карты, цели и памяти о пройденном пути. В классическом варианте он действует по двум правилам: на белой клетке поворачивает направо, на чёрной - налево. Затем меняет цвет клетки и шагает вперёд. Казалось бы, такая программа должна быстро наскучить. Но её след превращается в удивительно сложный рисунок.
На первоначально пустом поле сначала возникают небольшие узоры, затем движение долго выглядит беспорядочным. Позже муравей выходит на «магистраль»: последовательность из 104 шагов повторяется, каждый раз сдвигая рисунок дальше. Периодическим становится способ движения и строительства пути, а не возвращение всего поля в прежнее состояние. Это известное поведение классического старта; из него не следует, что любая раскраска и любой набор правил дадут тот же результат.
В модуле можно ускорить движение, перейти вперёд на множество шагов и изменить последовательность поворотов для разноцветных клеток. Сравните, какие правила создают компактные узоры, а какие - растущие следы. Эксперимент показывает, насколько богатым может быть поведение системы, если простое действие многократно меняет среду, от которой зависит её следующий шаг.
Измерения почти никогда не ложатся на идеальную линию: шум и случайные отклонения неизбежны. Метод наименьших квадратов подбирает кривую, уменьшая сумму квадратов расхождений между её значениями и данными. Возведение в квадрат не только убирает знак ошибки, но и придаёт большим отклонениям особенно большой вес.
В модуле данные показаны точками, а их расхождения с подобранной кривой - пружинками. Увеличивая степень полинома, можно сделать его всё более гибким. Однако слишком гибкая кривая начинает воспроизводить случайный шум. Ошибка на исходных точках уменьшается, а совпадение с настоящей закономерностью может ухудшиться. Это переобучение: модель запоминает особенности конкретного набора вместо того, чтобы хорошо описывать породивший его процесс.
Здесь исходная функция известна, поэтому можно сравнить ошибку подгонки с отклонением от этой функции между точками. Измените шум, сдвиньте одну точку, включите регуляризацию. Она добавляет штраф за большие коэффициенты полинома и сдерживает чрезмерную гибкость. Эксперимент объясняет, почему самая извилистая линия не обязательно самая полезная - и почему один выброс способен заметно изменить выводы.
В основе цифровых вычислений лежат операции всего с двумя значениями - нулём и единицей. Элемент И выдаёт единицу, когда активны оба входа. ИЛИ - когда активен хотя бы один. Исключающее ИЛИ, XOR, - когда входы различаются. Из таких простых правил можно собрать устройство, которое складывает числа и сохраняет информацию.
В модуле логика превращена в настольную плату с переключателями, дорожками и светящимися выходами. Полусумматор складывает два бита, выдавая бит суммы и перенос. Полный сумматор учитывает ещё и перенос с предыдущего разряда. Соединив такие ступени, получаем четырёхбитный сумматор: перенос передаётся от младшего разряда к старшему, как при привычном сложении столбиком.
Отдельный режим показывает бит памяти. Его состояние обновляется по нарастающему фронту тактового сигнала и сохраняется между такими событиями, даже если вход изменился. Переключайте входы, проверяйте комбинации и подавайте такты вручную. Становится видна разница между схемой, которая прямо сейчас вычисляет результат, и схемой, которая ещё и хранит прошлое состояние. Именно сочетание логики и памяти делает возможными цифровые машины.
Лабиринт можно рассматривать как рисунок коридоров, а можно - как граф: комнаты становятся вершинами, проходы между ними - рёбрами. Такой взгляд превращает поиск выхода в математическую задачу. При этом построить хороший лабиринт и пройти его - две разные задачи, для которых нужны разные алгоритмы.
В модуле генераторы на основе поиска в глубину, алгоритма Прима и алгоритма Уилсона создают связные лабиринты без циклов. Между любыми двумя клетками в таком лабиринте есть единственный простой путь. Но характер коридоров и тупиков зависит от способа построения. На трёхмерном макете видно, как открываются проходы, какие клетки исследует поиск и где проходит найденный маршрут.
Сравните поиск в ширину, A* и движение вдоль стены. Поиск в ширину исследует пространство по слоям; A* дополнительно учитывает оценку расстояния до цели; правило стены опирается на локальное движение вдоль границы. Меняйте цель и смотрите на число посещённых клеток и длину маршрута. Даже когда итоговый простой путь единственный, затраты на его поиск могут сильно различаться: знать, куда идти, и понять, как это выяснить, - разные вещи.
Кубик Рубика можно изучать не только как головоломку на сборку цветов. Каждый поворот переставляет элементы, а последовательность поворотов задаёт новую перестановку. Такие преобразования образуют математическую группу: их можно последовательно выполнять, существует действие «ничего не менять», а у каждого преобразования есть обратное.
Особенно интересно, что порядок действий имеет значение. Повернуть правую грань, а затем верхнюю - обычно не то же самое, что выполнить эти повороты в обратном порядке. Последовательность R U R⁻¹ U⁻¹, называемая коммутатором, наглядно показывает это различие. Хотя в ней есть повороты и их обратные, они не обязаны взаимно уничтожиться: между ними уже произошло другое преобразование.
Модуль анимирует повороты и показывает циклы перестановки и порядок выбранного преобразования - сколько раз нужно повторить всю последовательность, чтобы вернуть каждый отслеживаемый элемент на исходное место. Попробуйте одиночный поворот, сочетание двух граней и коммутатор. За цветными квадратиками постепенно проступает структура: длинная цепочка действий подчиняется точным правилам, которые можно вычислить, а затем увидеть своими глазами.
Пусть каждой точке карты соответствует высота, температура или направление потока. Как описать происходящее рядом с выбранной точкой? Градиент показывает направление самого быстрого роста скалярной величины. Дивергенция измеряет местный баланс выхода и входа векторного поля. Ротор характеризует его локальную циркуляцию, а лапласиан - дивергенцию градиента, связанную с тем, насколько значение отличается от среднего по ближайшим окрестностям.
В модуле эти идеи показаны рельефом, стрелками и движущимися частицами. Переносите зонд и сравнивайте локальные значения. Одна и та же точка может оказаться на крутом склоне, в области расходящегося поля или внутри вращательного движения - в зависимости от выбранного режима. Объёмная сцена здесь помогает читать поля, заданные на плоскости.
Кольцо на поверхности позволяет связать локальные свойства с результатом для целой области. Поток через замкнутую границу сопоставляется с интегралом дивергенции внутри неё, а циркуляция вдоль границы - с интегралом ротора. Обе стороны рассчитываются независимо. Меняйте размер области и форму поля, наблюдая их согласие с учётом численной погрешности. Формулы начинают говорить о понятных вещах: росте, источниках, вращении и связи части с целым.
Есть три стержня и несколько дисков разного размера. Нужно перенести всю башню с одного стержня на другой, перемещая по одному диску и никогда не кладя большой диск на маленький. Правила помещаются в одну фразу, но число необходимых действий растёт удивительно быстро.
Чтобы переместить самый большой диск, сначала нужно убрать с него все меньшие на вспомогательный стержень. После одного хода большим диском меньшую башню приходится переносить ещё раз. Так задача сама раскладывается на две задачи того же типа, но меньшего размера. Получается рекурсия: T(n) = 2T(n − 1) + 1. Из неё следует точный минимум - 2ⁿ − 1 ходов. Для трёх дисков достаточно семи, а для восьми уже нужно 255.
В модуле можно переставлять диски вручную или наблюдать автоматическую последовательность, сравнивая свой счётчик с оптимальным. Попробуйте сначала решить небольшую башню и заметить повторяющиеся подзадачи. Затем добавьте диски: правила не станут сложнее, но работа резко вырастет. Это наглядный способ почувствовать разницу между краткостью алгоритма и количеством действий, которые ему предстоит выполнить.