Спотлайт №72: Алгоритми, математика та наука про дані

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

I. Пошук шляху A*

A* — стандартний алгоритм пошуку шляху в робототехніці, розробці ігор та навігаційних системах. Він поєднує вичерпний пошук найкоротшого шляху за Дейкстрою з евристичною функцією, яка спрямовує пошук до цілі, обмінюючи обчислювальні витрати на спрямованість:

f(n) = g(n) + h(n)

де:
  g(n) : фактична вартість шляху від старту до вузла n
  h(n) : евристична оцінка вартості шляху від n до цілі

Умова допустимості: h(n) ≤ справжня вартість шляху від n до цілі
  ⇒ A* гарантовано знаходить оптимальний шлях

Поширені евристики для решітчастих графів:
  Манхеттенська:  h = |dx| + |dy|           (4-зв'язність)
  Чебишовська:    h = max(|dx|, |dy|)       (8-зв'язність)
  Евклідова:      h = √(dx² + dy²)        (будь-яка зв'язність)

Симуляція працює на решітці, де стіни можна малювати клацанням і перетягуванням миші. Алгоритм виконується покроково, розфарбовуючи клітинки відповідно до поточних значень f, g та h. Відкрита множина (вузли, що розглядаються) та закрита множина (вже оброблені вузли) розрізняються різними кольорами, а фінальний найкоротший шлях прокреслюється яскраво-зеленим. Повзунок ваги евристики демонструє зважений A* (f = g + wh): вага 1 дає оптимальний A*, вага 0 зводить алгоритм до Дейкстри, а вага більша за 1 дає неоптимальний, але швидший пошук. Саме ця остання можливість — наочна демонстрація компромісу між оптимальністю та швидкістю — незмінно дивує студентів, які вважали, що "чим краща евристика, тим краще завжди".

II. Криві Без'є

Криві Без'є лежать в основі кожного інструменту векторної графіки, рендерера шрифтів, системи анімації та реалізації SVG, що існує. Вони визначаються алгоритмом де Кастельжо, який будує криву через повторну лінійну інтерполяцію:

Алгоритм де Кастельжо для кривої степеня n з контрольними точками P0...Pn:

  Pi(0) = Pi

  Pi(r) = (1-t) Pi(r-1) + t Pi+1(r-1)

  Точка кривої за параметром t: B(t) = P0(n)

Форма через поліноми Бернштейна:
  B(t) = Σi=0n C(n,i) ti (1-t)n-i Pi

Властивості:
  Лежить у межах опуклої оболонки контрольних точок
  Інтерполює кінцеві точки P0 та Pn
  Дотична у P0 спрямована вздовж (P1 - P0)

Симуляція динамічно відображає побудову де Кастельжо, поки параметр t пробігає від 0 до 1. На кожному кроці проміжні відрізки прямих малюються кольором, наочно показуючи, які саме лінійні комбінації утворюють точку кривої. Контрольні точки можна перетягувати, і крива миттєво оновлюється. Селектор степеня дозволяє перемикатися між квадратичними (3 контрольні точки), кубічними (4), кривими четвертого степеня (5) та кривими вищих степенів. Опукла оболонка контрольного багатокутника показана як ледь помітна межа, роблячи властивість опуклої оболонки безпосередньо видимою: крива ніколи не виходить за її межі, незалежно від розташування контрольних точок.

III. Баєсівський висновок

Баєсівський висновок — це математично послідовний фреймворк для оновлення переконань у відповідь на нові дані. Теорема Баєса в найпростішому вигляді:

P(H | D) = P(D | H) × P(H) / P(D)

апостеріорна = правдоподібність × апріорна / свідчення

Для неперервного параметра θ зі спряженими апріорними розподілами:
  Бета-біноміальна модель (оцінка частки):
    Апріорна:      θ ~ Beta(α, β)
    Правдоподібність: k успіхів з n випробувань
    Апостеріорна:  θ ~ Beta(α + k, β + n - k)

  Нормально-нормальна модель (оцінка середнього, відома дисперсія):
    Апріорна:      μ ~ N(μ0, σ0²)
    Правдоподібність: x¯ за n спостереженнями
    Апостеріорна:  μ ~ N(μn, σn²)
    де σn-2 = σ0-2 + n/σ²

Симуляція пропонує два режими. У режимі підкидання монети користувач задає апріорний бета-розподіл ймовірності зміщення й спостерігає, як апостеріорний розподіл оновлюється щоразу, коли надходить новий результат кидка — або клацанням (ручне спостереження), або запуском автоматизованої послідовності. Апріорний, правдоподібність та апостеріорний розподіли відображаються одночасно на одній осі, роблячи теорему Баєса видимою геометричною операцією, а не абстрактною формулою. У гаусовому режимі користувач оцінює середнє нормального розподілу з відомою дисперсією, спостерігаючи, як апостеріорний розподіл звужується з накопиченням спостережень, і перевіряючи, що апостеріорне середнє є зваженим за точністю середнім апріорного середнього та вибіркового середнього.

IV. Центральна гранична теорема

Центральна гранична теорема (ЦГТ) — можливо, найважливіший результат у статистиці. Вона стверджує, що сума великої кількості незалежних випадкових величин, незалежно від їхнього індивідуального розподілу, збігається до гаусового розподілу. Точніше, для незалежних однаково розподілених величин із середнім μ та дисперсією σ²:

Sn = (X1 + ... + Xn - nμ) / (σ√n) → N(0, 1) при n → ∞

Швидкість збіжності: теорема Беррі-Ессеена
  |P(Sn ≤ x) - Φ(x)| ≤ C ρ / (σ³ √n)
  де ρ = E[|X - μ|³]  (третій абсолютний момент)
  Повільніша збіжність для важкохвостих або асиметричних розподілів.

Симуляція дозволяє обирати з-поміж шести батьківських розподілів: рівномірного, експоненційного, розподілу Коші (який явно порушує умови ЦГТ через невизначену дисперсію), Бернуллі, бімодальної суміші та розподілу Парето з регульованим індексом хвоста. Користувач задає розмір вибірки n, багаторазово генерує вибірки й спостерігає, як формується гістограма вибіркових середніх. Поверх неї накладається теоретичне нормальне наближення, а Q-Q графік показує, наскільки емпіричний розподіл близький до гаусового. Режим розподілу Коші — найбільш повчальний: вибіркове середнє ніколи не збігається, а Q-Q графік дедалі більше відхиляється від діагоналі зі зростанням розміру вибірки, роблячи важливість умови скінченної дисперсії відчутною буквально на власні очі.

V. Булева мережа

Модель NK-булевих мереж Стюарта Кауффмана — одна з канонічних моделей складних систем, застосовувана до мереж генної регуляції, нейронних контурів та динаміки соціального впливу. Кожен із N вузлів має бінарний стан і отримує входи від K випадково обраних інших вузлів, оновлюючись за допомогою випадкової булевої функції:

Модель NK Кауффмана:
  N вузлів, кожен із бінарним станом si ∈ {0, 1}
  K випадкових входів на вузол
  2K записів у випадковій таблиці істинності кожного вузла

Фазова межа (відпалене наближення):
  Kc = 1 / (2 p(1-p))
  де p = ймовірність виходу = 1

  K < Kc : упорядкована фаза  (атрактори малі, збурення згасають)
  K = Kc : критична фаза (атрактори ~ √N, гемінгова відстань ~ 1)
  K > Kc : хаотична фаза  (атрактори експоненційні, збурення посилюються)

Симуляція відображає N вузлів у вигляді кільцевої мережі, де кожен вузол зафарбований відповідно до свого поточного бінарного стану. Цикли-атрактори виявляються автоматично та підсвічуються: із будь-якого початкового стану мережа завжди потрапляє в повторюваний цикл, і симуляція показує як перехідний рух до атрактора, так і довжину самого циклу-атрактора. Критична зв'язність K = 2 обрана типовою, оскільки саме вона лежить на фазовій межі для p = 0.5: експерименти зі збуренням за такої зв'язності не показують ні миттєвого згасання (упорядкована фаза), ні вибухового поширення (хаотична фаза), а натомість те граничне, далекосяжне поширення, яке Кауффман запропонував як ознаку біологічних регуляторних мереж.

VI. B-дерево

B-дерево — домінантна структура даних для індексації баз даних і файлових систем, яка використовується всередині кожної великої реляційної СУБД та операційної системи. Вона узагальнює двійкове дерево пошуку, дозволяючи вузлам мати багато нащадків, зберігаючи невелику висоту дерева навіть для мільярдів записів:

B-дерево порядку m:
  Кожен внутрішній вузол має від ⌈m/2⌉ до m нащадків
  Кожен листовий вузол має від ⌈m/2⌉ - 1 до m - 1 ключів
  Усі листки знаходяться на однаковій глибині h

Оцінка висоти:
  h ≤ log⌈m/2⌉( (n+1)/2 )

Для n = 106 записів, m = 100:
  h ≤ log50(500001) ≈ 3.4  ⇒  h = 4 щонайбільше

Ось чому B-дерева використовують для дискового зберігання:
  усього 4 звернення до диска, щоб знайти будь-який запис серед мільйона.

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

VII. Фільтр Блума

Фільтр Блума — це ймовірнісна структура даних, яка відповідає на запити про належність до множини без хибнонегативних результатів і з обмеженою частотою хибнопозитивних, використовуючи лише частку пам'яті, необхідної для точної структури:

Фільтр Блума з m бітами, k хеш-функціями, n вставленими елементами:

Ймовірність хибнопозитивного результату:
  P(fp) ≈ (1 - e-kn/m)k

Оптимальна кількість хеш-функцій:
  kopt = (m/n) ln 2 ≈ 0.693 (m/n)

Оптимальна кількість бітів на елемент для цільової частоти хибнопозитивних p:
  m/n = -log2(p) / ln 2 ≈ -1.44 log2(p)

Приклад: частота хибнопозитивних 1% вимагає ~9.6 біт/елемент
         0.1% вимагає ~14.4 біт/елемент

Симуляція відображає бітовий масив як рядок кольорових клітинок. Кожна вставка хешує ключ k незалежними хеш-функціями та встановлює відповідні біти. Операції запиту простежують ті самі хеш-позиції, і хибнопозитивний результат спрацьовує щоразу, коли всі перевірені біти виявляються встановленими попередніми вставками інших ключів. Виміряна експериментально частота хибнопозитивних результатів збігається з теоретичною формулою зі зростанням кількості вставлених елементів, а графік виміряної та передбаченої частоти в реальному часі підтверджує точність наближення. Компроміс між m, k, n та частотою хибнопозитивних результатів повністю налаштовується, роблячи задачу проєктування фільтра безпосередньо дослідною.

VIII. Функції комплексної змінної

Комплексний аналіз — одна з найкрасивіших областей математики, і розфарбовування області (domain colouring) робить її ключові об'єкти безпосередньо видимими. Комплексна функція f(z) зіставляє комплексне число кожній точці комплексної площини; розфарбовування області відображає результат у колір:

Схема розфарбовування області:
  Відтінок:      arg(f(z)) відображається у [0, 2π]  (кут)
  Яскравість: |f(z)| кодується періодичною функцією від log|f(z)|

Нулі f: точки, де |f(z)| = 0 (чорний)
Полюси f: точки, де |f(z)| → ∞ (білий)
Розрізи гілок: розриви відтінку

Приклади:
  f(z) = z²      : відтінок обертається двічі навколо початку координат
  f(z) = 1/z     : полюс у початку координат (біла точка), відтінок обертається у зворотному напрямку
  f(z) = ez     : горизонтальна періодичність, без нулів і полюсів у ℂ
  f(z) = Γ(z)  : полюси в 0, -1, -2, ... (білі точки), красиві спіралі

Симуляція обчислює розфарбовування області на GPU за допомогою фрагментного шейдера WebGL, обчислюючи обрану функцію в кожному пікселі одночасно й відображаючи результат у колірний простір HSL. Доступні функції включають елементарні функції (поліноми, раціональні функції, експоненту, логарифм, тригонометричні), спеціальні функції (гамма-функцію, дзета-функцію Рімана, еліптичні функції Якобі) та власний парсер виразів, який приймає довільний синтаксис комплексних функцій. Перетягування вікна перегляду переміщує зображення, а колесо прокрутки масштабує його, зберігаючи рендеринг у реальному часі протягом усього процесу.

Дзета-функція Рімана — найбільш візуально вражаючий варіант. Знамениті нетривіальні нулі на критичній лінії Re(s) = 1/2 з'являються як чорні точки на висотах, що відповідають відомим значенням (14.13, 21.02, 25.01, ...), а самоподібну структуру функції поза критичною смугою можна спостерігати безпосередньо. Жоден інший загальнодоступний інструмент не дозволяє нефахівцю досліджувати дзета-функцію з такою наочністю.

Навіщо алгоритми й математика?

Іноді виникає запитання: навіщо включати суто абстрактні алгоритми й математику на платформу, яка почалася з фізичних симуляцій? Відповідь у тому, що межа між абстрактною математикою та фізичною реальністю пролягає не там, де здається на перший погляд. Пошук шляху A* використовується в кожному безпілотному автомобілі. Фільтри Блума обробляють мільярди запитів на день у розподілених базах даних, що обслуговують науку не менше, ніж комерцію. Криві Без'є відтворюють кожну векторну графіку в кожній науковій статті та кожній презентації. Центральна гранична теорема лежить в основі кожного планки похибки в кожному фізичному вимірюванні. Функції комплексної змінної — математичний хребет квантової механіки. Булеві мережі — прикладні моделі генної регуляції.