Девлог #90 – Хвиля 69: опукла оболонка, пошук Гровера, річкові меандри, фізика мотузки, перцептрон і орбітальний резонанс

Нові симуляції

Опукла оболонка: три алгоритми, одна сцена

Опукла оболонка — це найменший опуклий багатокутник, що охоплює набір точок, — алгоритмічний еквівалент натягування гумки навколо цвяхів на дошці. Три класичні алгоритми підходять до цього по-різному, і спостерігати за їхнім змаганням на одних і тих самих вхідних даних — одна з найповчальніших речей в обчислювальній геометрії.

Сканування Грема O(n log n)

Відсортуйте всі точки за полярним кутом відносно найнижчої точки (розв'язуючи нічию за відстанню). Потім пройдіть відсортованим списком: для кожної нової точки видаляйте точки оболонки, що утворюють поворот за годинниковою стрілкою (не вліво), використовуючи 2D векторний добуток (b−a) × (c−a) = (b.x−a.x)(c.y−a.y) − (b.y−a.y)(c.x−a.x). Колінеарні точки обробляються явно — симуляція дозволяє перемикати, чи включати їх до оболонки.

Обхід Джарвіса O(nh)

«Загортання в подарунковий папір» інтуїтивно зрозуміле: почніть із найлівішої точки й повторно знаходьте точку, що утворює найменший кут проти годинникової стрілки з поточним ребром. За n загальних точок і h на оболонці це O(nh) — швидше за Грема, коли h мале, але деградує до O(n²) для кругових вхідних даних. Симуляція показує обертову стрілку-«руку загортання» на кожному кроці.

Quickhull: розділяй і володарюй

Знайдіть найлівішу й найправішу точки (базове ребро). Найвіддаленіша точка від базової лінії точно належить оболонці — додайте її й рекурсивно розв'яжіть дві трикутні підзадачі. У середньому O(n log n), у найгіршому випадку O(n²) для несприятливих вхідних даних. Рекурсивний поділ візуалізується кольоровими областями.

• Усі три алгоритми анімуються одночасно на одному наборі точок
• Лічильник операцій у реальному часі для кожного алгоритму (порівняння + обміни)
• Готові вхідні дані: випадкові, кластеризовані, кругові, несприятливий випадок для Quickhull
• Покроковий режим для паузи на кожній операції

Пошук Гровера: квантове підсилення амплітуди

Класичний неструктурований пошук потребує O(N) запитів, щоб знайти один позначений елемент серед N. Алгоритм Гровера (1996) робить це за O(√N) — доведено оптимальне квадратичне прискорення — використовуючи лише квантову суперпозицію та два прості оператори.

Оператори оракула й дифузії

Алгоритм працює повністю з дійсними амплітудами (комплексні фази не потрібні для одного позначеного елемента). Кожна ітерація Гровера застосовує:

1. Оракул: змінює знак амплітуди цільового стану: α_ціль → −α_ціль
2. Дифузія: інверсія відносно середнього: α_i → 2μ − α_i, де μ — середня амплітуда

Цільова амплітуда зростає з кожною ітерацією, тоді як усі інші зменшуються. Після k* = ⌊π√(N/M)/4⌋ ітерацій (M позначених елементів) імовірність успіху досягає піку поблизу 1. Надлишкове обертання знову її зменшує — симуляція показує цей періодичний спад і відродження.

Геометрична картина

У 2D-підпросторі, натягнутому на |позначений⟩ та |непозначений⟩, кожна ітерація Гровера є поворотом на кут 2θ, де sin(θ) = √(M/N). Геометрична вставка показує це обертання явно, роблячи структуру алгоритму одразу зрозумілою.

• N від 4 до 128 станів; M від 1 до N/2 позначених елементів
• Стовпчикова діаграма амплітуд анімується в реальному часі
• Графік імовірності успіху відносно ітерації з позначкою оптимального k*
• Для порівняння показано класичну очікувану кількість запитів O(N)

Річкові меандри: еволюція, керована кривизною

Річки недовго течуть прямо. Крихітне збурення переростає у звивисті меандри, коли ерозія на зовнішньому березі перевищує відкладення на внутрішньому — контур позитивного зворотного зв'язку, викликаний відцентровою силою потоку води.

Рівняння міграції

Кожен вузол i на осьовій лінії річки мігрує перпендикулярно до напрямку течії зі швидкістю, пропорційною просторово запізнілій кривизні: dn/dt = E₀ · Σ C(s) · κ(s − запізнення), де κ — локальна кривизна, а запізнення враховує зсув вниз за течією піку ерозії відносно піку кривизни. Саме ця затримана реакція спричиняє меандрування, а не випадкове блукання.

Формування стариць

Коли петля меандра стягується настільки, що два несуміжні вузли зближуються на відстань відсічення (пропорційну ширині русла), відбувається відсічення шийки: русло вирізає коротший шлях через шийку, а покинута петля стає старицею. Симуляція зберігає палеорусла у вигляді тьмяних слідів — точно як вони виглядають на супутникових знімках заплав.

• Панель статистики: коефіцієнт звивистості (загальна довжина / пряма відстань), кількість стариць, домінантна довжина хвилі
• Амплітуда початкового збурення та швидкість міграції налаштовуються
• Режим прискореної зйомки стискає тисячі років еволюції

Фізика мотузки: обмеження Верле й Якобі

Позиційне інтегрування Верле зберігає лише поточну й попередню позиції, неявно виводячи швидкість як v ≈ (x_зараз − x_поперед) / dt. Це робить додавання обмежень тривіальним — просто скоригуйте позиції безпосередньо, не торкаючись швидкостей, які потім оновлюються автоматично.

Релаксація обмежень методом Якобі

Кожен сегмент мотузки має довжину спокою L₀. Корекція обмеження для пари вузлів: перемістіть кожен вузол до іншого (або від нього) на половину похибки довжини: Δx = ½ · (d − L₀) · n̂, де d — поточна відстань, а n̂ — одиничний вектор. Виконання K ітерацій цього на кадр наближує нерозтяжну мотузку — K=1 дає розтяжну еластичну, K=20+ дає жорстку мотузку. Оновлення методом Якобі (одночасне) уникає напрямкового зміщення, властивого методу Гаусса-Зейделя.

• 5 готових сценаріїв: батіг (один закріплений кінець), міст (два кріплення), катенарна крива з двома кріпленнями, вільне падіння котушки, тканинна сітка
• Перетягуйте будь-який вузол інтерактивно; додавайте циліндричні перешкоди-стовпчики
• Повзунок K від 1 до 30 ітерацій на кадр
• Повзунки напрямку й величини гравітації

Перцептрон: перша нейронна мережа

Перцептрон Френка Розенблата 1957 року — найпростіший класифікатор, що піддається навчанню. Він зберігає вектор ваг w і класифікує вхід x як позитивний, якщо w·x > 0, і негативний в іншому випадку. Правило оновлення елегантно просте: щоразу, коли трапляється помилка, зсуньте ваги в правильному напрямку.

Правило навчання та збіжність

На кожному неправильно класифікованому прикладі (y · (w·x) ≤ 0) оновіть: w ← w + η · y · x. Теорема збіжності перцептрона гарантує завершення за скінченну кількість кроків, якщо дані лінійно роздільні — обмежену квадратом margin. Симуляція рахує помилки на кожному проході (епосі) та показує їх спад до нуля для роздільних наборів.

Проблема XOR

XOR не є лінійно роздільним — жодна гіперплощина не може правильно розділити чотири точки. Перцептрон циклічно повторюється безкінечно, коливаючись між частковими розв'язками. Це обмеження, підкреслене Мінським і Пейпертом у 1969 році, спонукало розвиток багатошарових мереж. Симуляція яскраво це демонструє: межа рішення нескінченно обертається на XOR, а потім різко збігається на гаусовому наборі даних.

• 5 наборів даних: два гаусіани, смуга, XOR (невдача), коло в квадраті (невдача), власний (клацання додає точки)
• Площина межі рішення анімується в реальному часі
• Графік помилок на прохід відрізняє збіжність від циклічності
• Повзунок швидкості навчання η

Орбітальний резонанс: ритми Кеплера

Резонанс виникає, коли два тіла на орбіті завершують цілочисельні відношення обертів за однаковий час, спричиняючи повторювані гравітаційні поштовхи в тій самій орбітальній фазі. Ці резонанси можуть стабілізувати орбіти (троянці Юпітера, Галілеєві супутники) або очищати їх (проміжки Кірквуда в поясі астероїдів).

Третій закон Кеплера та резонансний кут

Для кругових орбіт період T = a^(3/2) (у відповідних одиницях). Резонанс p:q вимагає T₂/T₁ = p/q, тобто a₂/a₁ = (p/q)^(2/3). Резонансний кут σ = pλ₂ − qλ₁ (де λ — середня довгота) лібрує навколо фіксованого значення, якщо резонанс активний, або циркулює через 360°, якщо ні. Лібрація означає, що планети завжди зустрічаються поблизу тієї самої фази — поштовхи когерентні.

Тритільний резонанс Галілеєвих супутників 4:2:1

Галілеєві супутники Іо, Європа й Ганімед замкнені в резонансі Лапласа: на кожен оберт Ганімеда Європа здійснює 2, а Іо — 4. Кут Лапласа λ₁ − 3λ₂ + 2λ₃ лібрує навколо 180° — усі три супутники ніколи не вирівнюються одночасно. Це запобігало катастрофічній орбітальній нестабільності протягом 4 мільярдів років.

• 6 готових резонансів: 1:1, 3:2, 2:1, 5:3, 4:1 і порівняння поза резонансом
• Позначки з'єднань (червоні крапки) кластеризуються в одному напрямку в резонансі
• Графік резонансного кута σ показує лібрацію проти циркуляції
• Готовий сценарій Галілеєвих супутників показує тритільний резонанс Лапласа

Далі буде

Хвиля 70 береться за математику управління проєктами (критичний шлях CPM/PERT із невизначеністю PERT), класифікацію методом k найближчих сусідів, поздовжній вигин колони Ейлера з коефіцієнтами зведеної довжини, пошук у дереві мінімакс з альфа-бета відсіканням, захоплення частинок поясу Ван Аллена в дипольному полі та релаксацію Ллойда для центроїдної теселяції Вороного.