Девлог #91 – Хвиля 70: CPM/PERT, k-NN, поздовжній вигин, дерево мінімакс, пояс Ван Аллена та релаксація Ллойда

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

CPM/PERT: аналіз критичного шляху

Планування проєктів має прекрасну теоретико-графову основу. Метод критичного шляху (CPM) та метод оцінки й аналізу програм (PERT) спираються на одну й ту саму структуру DAG, але по-різному враховують невизначеність тривалості робіт.

Топологічне сортування та прямий/зворотний прохід

Алгоритм Кана знаходить коректне топологічне впорядкування DAG робіт, послідовно видаляючи вузли з нульовою вхідною степенню. Прямий прохід потім обчислює ранні початок і завершення: ES_i = max(EF_j) за всіма попередниками j, і EF_i = ES_i + duration_i. Зворотний прохід встановлює дедлайн проєкту й поширюється назад: LS_i = LF_i − duration_i, LF_i = min(LS_k) за всіма наступниками k. Роботи з нульовим резервом часу (LF − EF = 0) формують критичний шлях — будь-яка затримка там затримує весь проєкт.

Триточкова оцінка PERT

PERT враховує невизначеність тривалості за допомогою трьох оцінок для кожної роботи: оптимістичної (o), найбільш імовірної (m) і песимістичної (p). Очікувана тривалість — t_e = (o + 4m + p) / 6, а дисперсія — σ² = ((p−o)/6)². Час завершення проєкту приблизно нормально розподілений із μ, що дорівнює сумі очікуваних тривалостей критичного шляху, і σ², що дорівнює сумі дисперсій критичного шляху. Панель імовірності дедлайну показує нормальну функцію розподілу P(T < дедлайн).

• Перетягуйте смуги тривалості робіт, щоб оновлювати критичний шлях у реальному часі
• Резерв часу показаний для кожної некритичної роботи
• Панель PERT з деталізацією невизначеності кожної окремої роботи
• Експорт мережі як простого JSON-списку робіт

k-NN: межі рішень через локальне голосування

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

Обчислення областей рішень

Симуляція малює сітку областей рішень 80×60 — кожна клітинка класифікується незалежно й забарвлюється відповідно до класу. Пропонуються три метрики відстані: евклідова (норма L2, кругові околиці), манхеттенська (норма L1, ромбоподібні) і чебишевська (норма L∞, квадратні околиці). За зважування 1/d² ближчі сусіди мають сильніший голос, що дає плавніші межі поблизу навчальних точок.

Компроміс зміщення й дисперсії через LOOCV

Перехресна перевірка з виключенням по одному видаляє кожну навчальну точку, класифікує її за допомогою решти точок і рахує правильні передбачення. Крива залежності точності від k розкриває фундаментальний компроміс: k=1 ідеально запам'ятовує навчальний набір (перенавчання, висока дисперсія), але погано узагальнює; велике k згладжує межу, але може недонавчатися. Оптимальне k відповідає піку кривої.

• 5 готових наборів даних: два гаусіани, чотири кластери, півмісяці-серпи, концентричні кола, XOR-плями
• Клацання додає власні навчальні точки в будь-якому з 4 класів
• Повзунок k від 1 до 25
• Перемикач накладення Вороного для перегляду точних меж 1-NN

Поздовжній вигин колони Ейлера: стійкість конструкцій

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

Критичне навантаження та зведена довжина

Формула критичного навантаження Ейлера: P_кр = π²EI / (KL)², де E — модуль Юнга, I — момент інерції перерізу відносно слабкої осі, L — фізична довжина, а K — коефіцієнт зведеної довжини, що залежить від граничних умов:

• Шарнір-шарнір (обидва кінці вільно обертаються): K = 1,0
• Шарнір-защемлення (один кінець закріплений): K = 0,7
• Защемлення-защемлення (обидва кінці затиснуті): K = 0,5
• Защемлення-вільний (флагшток / консоль): K = 2,0

Парабола Джонсона для коротких колон

Формула Ейлера справедлива лише для струнких колон (KL/r > π√(2E/σ_y), де r = √(I/A) — радіус інерції). Для коротших колон текучість матеріалу настає раніше, ніж пружний вигин. Парабола Джонсона P_кр/A = σ_y − (σ_y²/4π²E)(KL/r)² плавно переходить від межі текучості до кривої Ейлера в точці дотику, охоплюючи весь діапазон стрункості.

• Перерізи: суцільний прямокутник (момент інерції слабкої осі I = bh³/12), суцільне коло (I = πd⁴/64), двотавр (обчислюється з розмірів полиці та стінки)
• Графік вилчастої біфуркації: прогин відносно навантаження, нормованого за P_кр
• Відображення коефіцієнта запасу відносно розрахункового навантаження
• База матеріалів: сталь, алюміній, деревина, вуглецеве волокно

Мінімакс з альфа-бета відсіканням

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

Вікно альфа-бета

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

Сила порядку ходів

Ефективність відсікання альфа-бета критично залежить від порядку ходів. У найкращому випадку (найкращий хід завжди перевіряється першим) воно скорочує кількість вузлів з O(b^d) до O(b^(d/2)) — фактично подвоюючи глибину пошуку. Симуляція одночасно запускає випадковий і оптимальний порядок ходів, показуючи кількість відвіданих вузлів, яка може відрізнятися в 5 і більше разів на тому самому дереві.

• 3 готові дерева: збалансоване, глибоке однобічне, змішане з багатьма відсіканнями
• Випадковий генератор дерев: коефіцієнт розгалуження b ∈ [2,4], глибина d ∈ [3,5]
• Покроковий режим із вікнами альфа, бета, показаними на кожному вузлі
• Лічильник відвіданих вузлів: повний мінімакс проти альфа-бета

Пояс Ван Аллена: захоплення частинок дипольним полем

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

Дипольне поле та сила Лоренца

Компоненти дипольного магнітного поля: B_r = 3rz/R⁵ і B_z = (3z²−R²)/R⁵ (у циліндричних координатах). Інтегратор Лоренца оновлює швидкість через обертання: половинний поштовх, потім обертання v навколо B на кут ω_c·dt (циклотронна частота ω_c = qB/m), потім ще половинний поштовх. Це точно зберігає магнітний момент μ = mv²_⊥/2B для малих dt.

Дзеркальний і дрейфовий рух

Коли частинка рухається по спіралі до магнітного полюса, силові лінії сходяться, і B зростає. Оскільки μ адіабатично зберігається, перпендикулярна кінетична енергія має зростати — тож паралельна кінетична енергія спадає до нуля, і частинка дзеркально відбивається назад. Конус втрат визначається як sin²α_lc = B_екватор/B_атмосфера; частинки з кутами нахилу всередині конуса втрат влучають в атмосферу. Параметр L-оболонки використовує точну формулу B(L,λ) = (1/L³)√(1+3sin²λ)/cos⁶λ.

• Перемикання між протоном (m = 1) та електроном (m = 1/1836) — спостерігайте різні гірорадіуси
• Візуалізація всіх трьох рухів: обертання, дзеркальне відбиття, азимутальний дрейф
• Повзунок кута нахилу для демонстрації відсікання конуса втрат
• Накладення силових ліній L-оболонки на вигляд перерізу

Релаксація Ллойда: центроїдна теселяція Вороного

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

Оновлення центроїда та зменшення енергії

Кожна ітерація: обчислюється діаграма Вороного, знаходиться центроїд площі кожної комірки c = (Σw(x)·x / Σw(x)), зважений функцією густини ρ(x), а потім кожна точка переміщується до свого центроїда. Енергія квантування E = Σ_i ∫_{V_i} ρ(x)|x−c_i|² dx монотонно спадає — метод Ллойда є координатним спуском за цією енергією. Збіжність гарантована, але може бути повільною поблизу рівноваги; вставний графік енергії показує характерне швидке початкове падіння з подальшим довгим хвостом.

• 4 режими густини: рівномірний, радіальний (з ущільненням у центрі), горизонтальний градієнт, малюється користувачем
• Накладення тріангуляції Делоне (дуальний граф до Вороного)
• Забарвлення за площею комірки (виявляє рівномірність), індексом комірки або монохромно
• Стандартне відхилення площ комірок прямує до нуля

Далі буде

Хвиля 71 продовжується степеневою ітерацією PageRank (з виправленням для тупикових вершин), круговим турніром ітерованої дилеми в'язня Аксельрода з 10 канонічними стратегіями, діелектричним пробоєм фігури Ліхтенберга через розв'язувач Лапласа SOR, налаштуванням ПІД-регулятора з автоналаштуванням Зіглера-Нікольса, принципом Архімеда з точними формулами зануреного об'єму для трьох форм корпусу та втомним зростанням тріщин за законом Періса з катастрофічним руйнуванням при K_IC.