Алгоритми та комбінаторика — сортування, розфарбування графів і задоволення обмежень

Навіщо візуалізувати алгоритми?

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

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

Шар 1: мистецтво впорядкування — алгоритми сортування

Візуалізатор алгоритмів сортування

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

Бульбашкове сортування має складність O(n²) і його болісно очевидно спостерігати: воно багаторазово сканує масив, міняючи місцями сусідні елементи не в порядку, і після кожного проходу найбільший невпорядкований елемент "спливає" на своє фінальне місце. Швидке сортування обирає опорний елемент, розбиває масив навколо нього і рекурсивно сортує кожну половину — у середньому O(n log n), але O(n²) на вже відсортованому чи майже відсортованому вводі (це вирішується випадковим вибором опорного елемента). Сортування злиттям завжди має складність O(n log n), але потребує O(n) додаткової пам'яті. Порозрядне сортування долає бар'єр O(n log n), але лише для цілочислових ключів.

Algorithm       Best      Average   Worst     Space  Stable?
─────────────────────────────────────────────────────────────
Bubble Sort     O(n)      O(n²)     O(n²)     O(1)   ✓
Insertion Sort  O(n)      O(n²)     O(n²)     O(1)   ✓
Selection Sort  O(n²)     O(n²)     O(n²)     O(1)   ✗
Shell Sort      O(n log n) varies  O(n^1.5)   O(1)   ✗
Merge Sort      O(n lgn)  O(n lgn)  O(n lgn)  O(n)   ✓
Heap Sort       O(n lgn)  O(n lgn)  O(n lgn)  O(1)   ✗
QuickSort       O(n lgn)  O(n lgn)  O(n²)     O(lgn) ✗
Tim Sort        O(n)      O(n lgn)  O(n lgn)  O(n)   ✓
Radix Sort      O(nk)     O(nk)     O(nk)     O(n+k) ✓
Counting Sort   O(n+k)    O(n+k)    O(n+k)    O(k)   ✓

Інформаційно-теоретична нижня межа для порівняльних сортувань:
  Будь-яке сортування на основі порівнянь потребує Ω(n log n) порівнянь
  Доведення: n! можливих порядків → потрібно ≥ log₂(n!) порівнянь
         Стірлінг: log₂(n!) ≈ n·log₂(n) − n·log₂(e)

Tim Sort (Python sorted(), Java Arrays.sort):
  Гібрид сортування злиттям і вставками
  Виявляє природні "прогони" (вже відсортовані підпослідовності)
  O(n) на майже відсортованих даних — оптимально в реальних умовах

Симуляція алгоритмів сортування одночасно запускає 15+ алгоритмів на одному й тому самому перемішаному масиві, показуючи кольорову стовпчикову діаграму, де висота кодує значення, а колір — статус порівняння/обміну. Лічильник обмінів і таймер оновлюються наживо, миттєво роблячи видимим розрив між O(n²) і O(n log n). Аудіорежим перетворює висоту стовпця на висоту тону — можна буквально почути, як швидке сортування завершується раніше за сортування злиттям.

Шар 2: розміщення ферзів, що не атакують — задача N ферзів

Симуляція беклтрекінгу для N ферзів

Задача N ферзів полягає у розміщенні N ферзів на шахівниці N×N так, щоб жодні два ферзі не атакували один одного — жодні два не можуть ділити рядок, стовпець чи діагональ. Для N=8 існує 92 розв'язки; для N=12 — 14 200; для N=20 — понад 39 мільярдів. Підрахувати їх усі можна лише повним перебором, але знайти один розв'язок швидко можна за допомогою евристик.

Беклтрекінг — систематичне дослідження дерева пошуку з ранньою зупинкою, коли частковий розв'язок виявляється нездійсненним — канонічний алгоритм для цього. Поставте ферзя в рядку 1, спробуйте кожен стовпець, поставте ферзя в рядку 2, спробуйте кожен допустимий стовпець і так далі. Коли в поточному рядку немає допустимого розміщення, поверніться до попереднього рядка і спробуйте наступний стовпець. У найгіршому випадку дерево пошуку має N! листків, але відсікання гілок робить задачу керованою.

Псевдокод беклтрекінгу:
  solve(row):
    if row == N: solution found; record()
    for col in 0..N-1:
      if safe(row, col):
        place(row, col)
        solve(row + 1)
        remove(row, col)      ← backtrack

Перевірка безпеки O(1) з бітовими масками:
  cols    = множина зайнятих стовпців
  diag1   = множина зайнятих діагоналей (row − col)
  diag2   = множина зайнятих антидіагоналей (row + col)
  безпечно, якщо col ∉ cols ∧ (row−col) ∉ diag1 ∧ (row+col) ∉ diag2

Кількість розв'язків (загалом, з урахуванням поворотів/віддзеркалень):
  N   Розв'язків    N   Розв'язків
  4      2         12   14 200
  5      10        14   365 596
  6      4         16   14 772 512
  7      40        20   39 029 188 884
  8      92
  10     724

Для великих N: Q(N) ≈ (0.143 N)^N  (експоненційне зростання)

NP-повний варіант:
  Визначення, чи можна завершити часткове розміщення, є NP-повною задачею
  (варіант рішення, який вивчають у задоволенні обмежень у ШІ)

Симуляція N ферзів візуалізує кожен крок беклтрекера: активний ферзь, що розміщується, світиться жовтим, успішно розміщені ферзі — зеленим, а ферзі в конфлікті — червоним. Лічильник розв'язків і лічильник відступів оновлюються з кожним кроком. Встановіть N від 4 до 12 та оберіть швидкість анімації, щоб стежити за логікою алгоритму у власному темпі, або натисніть «Авто», щоб прогнати всі розв'язки одразу.

Шар 3: розфарбування графів

Симуляція розфарбування графів

Розфарбування графа присвоює кольори вершинам графа так, щоб жодні дві суміжні вершини не мали однакового кольору. Мінімальна кількість необхідних кольорів — хроматичне число χ(G), один з найдослідженіших параметрів комбінаторики. Він має пряме застосування в плануванні (призначення часових слотів для завдань, що конфліктують), розподілі регістрів (призначення регістрів процесора змінним), розфарбуванні карт (знаменита теорема чотирьох кольорів) і призначенні частот у бездротових мережах.

Точне знаходження χ(G) є NP-складною задачею — але кілька поліноміальних евристик швидко дають майже оптимальні розфарбування. Жадібний алгоритм присвоює кожній вершині найменший доступний колір у певному порядку. Алгоритм Уелша-Пауела покращує це, впорядковуючи вершини за ступенем (від найбільшого). DSatur (ступінь насичення) — жадібний алгоритм із динамічним пріоритетом: на кожному кроці він розфарбовує вершину з найбільшою кількістю по-різному розфарбованих сусідів, що часто дає оптимальне розфарбування.

Межі хроматичного числа:
  χ(G) ≥ ω(G)          (кліковe число — найбільший повний підграф)
  χ(G) ≤ Δ(G) + 1      (межа Брукса; рівність лише для повних графів або непарних циклів)
  χ(G) ≤ Δ(G)          (теорема Брукса для зв'язних неповних графів без непарних циклів)

Теорема чотирьох кольорів (Аппель і Гакен, 1976):
  Будь-який плоский граф задовольняє χ(G) ≤ 4
  (Перша велика теорема, доведена за допомогою комп'ютера — понад 1200 конфігурацій)

Алгоритм DSatur:
  saturation(v) = |{кольори сусідів v}|  (кількість різних кольорів сусідів)
  1. Обрати нерозфарбовану вершину v з максимальним насиченням (нічия розбивається за ступенем)
  2. Присвоїти найменший колір, не використаний жодним сусідом v
  3. Повторювати, доки всі вершини не розфарбовано
  Складність: O(n²) наївно, O((n+m) log n) з чергою з пріоритетами

Жадібна верхня межа:
  Жадібний алгоритм упорядковує вершини довільно → χ ≤ Δ + 1
  Уелш-Пауел упорядковує за спаданням ступеня → жорсткіша межа на практиці
  Найгірший випадок жадібного алгоритму: χ = Δ + 1 (напр. двочастковий граф з вершинами високого ступеня, що чергуються)

Граф Петерсена:
  10 вершин, 15 ребер, Δ = 3, χ = 3
  3-регулярний, без мостів — контрприклад для багатьох гіпотез теорії графів

Симуляція розфарбування графів показує роботу алгоритмів Greedy, Welsh-Powell та DSatur на готових і власних графах. Покроковий режим підсвічує, яка вершина розфарбовується і чому — можна побачити, як DSatur динамічно перебудовує чергу пріоритетів у міру присвоєння кольорів. Перетягуйте вершини, щоб змінити розташування; клацніть на порожньому місці, щоб додати нову вершину; конфлікти підсвічуються червоним, коли ручні призначення їх створюють.

Шар 4: площі під кривими — інтегрування Рімана

Симуляція інтеграла Рімана

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

Точність кожного методу залежить від гладкості підінтегральної функції. Для гладких функцій метод Сімпсона досягає похибки O(h⁴) — той самий результат, який потребує мільйонів прямокутників Рімана, можна отримати лише 8 інтервалами Сімпсона. Саме тому чисельні бібліотеки для промислових обчислень використовують адаптивну квадратуру (розбиття інтервалів там, де підінтегральна функція швидко змінюється), а не рівномірні суми Рімана.

∫ₐᵇ f(x) dx  з n рівними підінтервалами шириною h = (b−a)/n

Ліва сума Рімана:
  L_n = h · Σᵢ₌₀^{n−1} f(xᵢ)
  Похибка: O(h) = O(1/n)  — метод першого порядку

Права сума Рімана:
  R_n = h · Σᵢ₌₁^n f(xᵢ)
  Похибка: O(h) = O(1/n)  — метод першого порядку

Правило середньої точки:
  M_n = h · Σᵢ f(xᵢ + h/2)
  Похибка: O(h²) — другий порядок; удвічі краще за L/R для гладких f

Правило трапецій:
  T_n = h · [f(x₀)/2 + f(x₁) + f(x₂) + ... + f(xₙ₋₁) + f(xₙ)/2]
  Похибка: O(h²) — той самий порядок, що й у середньої точки, але більша константа

Складене правило Сімпсона 1/3:
  S_n = (h/3) · [f(x₀) + 4f(x₁) + 2f(x₂) + 4f(x₃) + ... + 4f(xₙ₋₁) + f(xₙ)]
  (потребує парного n)
  Похибка: O(h⁴) — четвертий порядок; у 100 разів менше обчислень, ніж у Рімана, для тієї самої точності

Порівняння збіжності для ∫₀¹ sin(x) dx = 1 − cos(1) ≈ 0.459698:
  n=10:  похибка L 0.0450,  середня точка 0.00046,  Сімпсон 4.5×10⁻⁷
  n=100: похибка L 0.0045,  середня точка 4.6×10⁻⁶, Сімпсон 4.5×10⁻¹¹

Симуляція інтегрування Рімана малює прямокутники чи трапеції кожного чисельного методу різними кольорами, показуючи заповнену площу та непокриті проміжки поруч. Живий показник похибки демонструє, як кожне правило сходиться зі збільшенням кількості підінтервалів за допомогою повзунка — роблячи перевагу O(h⁴) методу Сімпсона разючою: збільште n з 10 до 20, і похибка Сімпсона падає у 16 разів, тоді як похибки Рімана — лише вдвічі.

Шар 5: недоведена гіпотеза — задача Коллатца

Симуляція гіпотези Коллатца

Візьміть будь-яке додатне ціле число. Якщо воно парне, поділіть на 2. Якщо непарне, помножте на 3 і додайте 1. Повторюйте. Гіпотеза Коллатца стверджує, що будь-яке додатне ціле число зрештою досягає 1. Її перевірено для всіх чисел до приблизно 2.95 × 10²⁰, проте загального доведення не існує. Пол Ердеш сказав: «Математика ще не готова до таких задач».

Послідовності демонструють здавалося б хаотичну поведінку. Починаючи з 27, потрібно 111 кроків, щоб досягти 1, з підйомом до 9232. Починаючи з 871, послідовність сягає 190 996 перед спуском. Час зупинки (кількість кроків до досягнення 1) коливається шалено й непередбачувано — проте гіпотеза стверджує, що він завжди скінченний. Задача Коллатца перебуває на перетині теорії чисел, динамічних систем і обчислювальної складності.

Функція 3n+1:
  T(n) = n/2       якщо n ≡ 0 (mod 2)
  T(n) = (3n+1)/2  якщо n ≡ 1 (mod 2)  [прискорена форма]

Час зупинки σ(n): найменше k, таке що T^k(n) = 1
Повний час зупинки τ(n): кількість ітерацій до першого досягнення 1

Екстремальні приклади:
  n=27:  σ=111, максимальне значення 9232
  n=871: σ=178, максимальне значення 190 996
  n=6171: σ=261, максимальне значення 975 400
  n=77031: σ=350, максимальне значення 21 933 016

Евристичний аналіз (Террас, 1976):
  Середнє T(n) ≈ n · (3/4)  [за припущення випадкової парності]
  Очікуваний час зупинки: O(log n)
  Але найгірший час зупинки не обмежений жодною доведеною функцією від log n

Перевірений діапазон (станом на 2024):
  Гіпотеза Коллатца виконується для всіх n ≤ 2.95 × 10²⁰
  (Барина, 2020, розподілене обчислення на кластері GPU)

Зв'язок із відкритими проблемами:
  Террі Тао (2019) довів, що «майже всі» орбіти досягають значення нижче
  будь-якої заданої f(n) для f, що повільно прямує до нескінченності —
  найближче до доведення на сьогодні

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

Шар 6: нескінченні суми як функції — ряди Тейлора

Симуляція рядів Тейлора

Теорема Тейлора стверджує, що будь-яку нескінченно диференційовну функцію можна наблизити скільки завгодно точно поблизу точки поліномом — а в багатьох випадках наближення сходиться до точної функції всюди. Коефіцієнти полінома повністю визначаються похідними функції в одній точці: f(a), f'(a), f''(a) і так далі. Це глибоке спостереження: уся поведінка sin(x) на всій числовій осі закодована в одному числі sin(0) = 0 та його похідних 1, 0, −1, 0, 1, 0, …

Ряди Тейлора — двигун наукових обчислень. Вони перетворюють трансцендентні функції на поліноми, дозволяючи швидке обчислення на апаратному забезпеченні, що нативно виконує лише додавання й множення. Вони пояснюють, чому sin(x) ≈ x для малих x (фізичне наближення, що використовується всюди — від оптики до орбітальної механіки) і чому e^x ≈ 1+x для малих збурень. Вони дають теоретичну основу для чисельного диференціювання, автоматичного диференціювання та функцій активації нейронних мереж.

Ряд Тейлора функції f(x) навколо x = a:
  f(x) = Σₙ₌₀^∞ f⁽ⁿ⁾(a) / n! · (x−a)ⁿ
       = f(a) + f'(a)(x−a) + f''(a)(x−a)²/2! + f'''(a)(x−a)³/3! + ...

Ряд Маклорена (a = 0):
  sin(x)   = x − x³/3! + x⁵/5! − x⁷/7! + ...        R = ∞
  cos(x)   = 1 − x²/2! + x⁴/4! − x⁶/6! + ...        R = ∞
  eˣ       = 1 + x + x²/2! + x³/3! + x⁴/4! + ...     R = ∞
  ln(1+x)  = x − x²/2 + x³/3 − x⁴/4 + ...            R = 1
  (1+x)^α  = 1 + αx + α(α−1)x²/2! + ...               R = 1  (біноміальний)
  arctan(x) = x − x³/3 + x⁵/5 − x⁷/7 + ...           R = 1
              (→ формула Лейбніца: π/4 = 1 − 1/3 + 1/5 − ...)

Радіус збіжності R:
  Визначається найближчою особливою точкою на комплексній площині
  ln(1+x): особлива точка при x = −1 → R = 1
  1/(1−x) = Σ xⁿ: особлива точка при x = 1 → R = 1
  sin(x): скінченних особливих точок немає → R = ∞

Оцінка залишку (Лагранж):
  |f(x) − Tₙ(x)| ≤ M · |x−a|^{n+1} / (n+1)!
  де M = max |f^{(n+1)}(t)| для t між a і x

Симуляція рядів Тейлора накладає часткові суми T₁(x), T₂(x), ..., Tₙ(x) поверх вихідної функції f(x). Повзунок додає по одному члену за раз, з анімацією кожного нового члена протягом 600 мс. Окремий графік похибки показує |f(x) − Tₙ(x)| у логарифмічній шкалі, роблячи видимою експоненційну збіжність. Спостерігайте, як наближення розширюється назовні від точки розкладу подібно до хвилі, сходячись до різних функцій з різною швидкістю залежно від їх радіуса збіжності.

Шар 7: числа в трикутнику — трикутник Паскаля

Симуляція трикутника Паскаля

Трикутник Паскаля будується за правилом, що кожен елемент є сумою двох елементів над ним, з краями, заповненими одиницями. Отриманий трикутник містить біноміальні коефіцієнти C(n,k) = n!/(k!(n−k)!) — що рахують кількість способів обрати k елементів з n — які з'являються як коефіцієнти в розкладі (a+b)ⁿ. Але трикутник приховує значно більше, ніж біноміальні коефіцієнти.

Сума діагоналей рядка n і рядка n−1 дає числа Фібоначчі. Розфарбування клітин за парністю (парне/непарне) дає фрактал трикутника Серпінського. Розфарбування за лишком за модулем p для простого p дає p-адичний фрактал із самоподібною структурою на всіх масштабах. Суми рядків — степені двійки; тотожність «хокейної ключки» дає кумулятивні суми стовпців; центральний стовпець містить центральні біноміальні коефіцієнти, які з'являються в ймовірностях повернення випадкового блукання.

Базове визначення:
  C(n, k) = C(n−1, k−1) + C(n−1, k)    (правило Паскаля)
  C(n, 0) = C(n, n) = 1

Біноміальна теорема:
  (a + b)ⁿ = Σₖ₌₀^n C(n,k) · aⁿ⁻ᵏ · bᵏ

Суми рядків (покласти a=b=1):
  Σₖ C(n,k) = 2ⁿ   (кожен рядок дає в сумі степінь двійки)

Діагональні суми Фібоначчі:
  Σₖ C(n−k, k) = F(n+1)  (суми неглибоких діагоналей = числа Фібоначчі)

Тотожність «хокейної ключки»:
  Σⱼ₌ᵣ^n C(j, r) = C(n+1, r+1)

Патерн парності (теорема Куммера):
  C(n, k) непарне ⟺ k AND n = k  у двійковому вигляді (побітове AND)
  Еквівалентно: при додаванні k і (n−k) у двійковій системі немає перенесення
  → Непарні елементи утворюють фрактал трикутника Серпінського

Центральні біноміальні коефіцієнти:
  C(2n, n) = (2n)! / (n!)²  ≈ 4ⁿ / √(πn)  (наближення Стірлінга)
  Зустрічається в: очікуваному часі повернення симетричного випадкового блукання,
              числах Каталана C_n = C(2n,n)/(n+1), підрахунку решітчастих шляхів

Симуляція трикутника Паскаля відображає до 20 рядків із трьома режимами розфарбування: логарифмічна шкала (відносні величини), режим парності (що виявляє трикутник Серпінського) та модульне розфарбування (де обирається простий модуль і колір визначається лишком — створюючи різні p-адичні фрактали для кожного простого числа). Діагоналі Фібоначчі та трикутних чисел можна підсвітити окремо. Наведіть курсор на будь-яку клітину, щоб побачити точне значення і формулу C(n,k).

Усі сім симуляцій одним поглядом

Єдність дискретної математики

Ці сім симуляцій можуть здатися окремими темами, але вони глибоко пов'язані крізь призму дискретної математики. Алгоритми сортування — це спеціалізації порівняльних мереж, оптимальна глибина яких пов'язана з інформаційно-теоретичними нижніми межами. Розфарбування графів і задача N ферзів — обидві є задачами задоволення обмежень, що належать до одного класу складності (NP-повного для варіантів рішення). Ряди Тейлора — неперервний аналог елементів рядків трикутника Паскаля: коефіцієнти e^x у ряді Тейлора — це 1/n! = 1/C(n,n) · n!/n! — обернені до діагональних елементів трикутника Паскаля.

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

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