Spotlight #72: Algorytmy, matematyka i nauka o danych

Algorytmy i czysta matematyka to dziedziny, w których luka między opisem podręcznikowym a prawdziwym zrozumieniem może być ogromna. Algorytm najkrótszej ścieżki jest zdefiniowany kilkoma liniami pseudokodu, ale zrozumienie, dlaczego działa — dlaczego heurystyka jest dopuszczalna, co się dzieje, gdy heurystyka przeszacowuje, jak ewoluuje zbiór otwarty w miarę postępu wyszukiwania — wymaga obserwowania jego działania. Podobnie, centralne twierdzenie graniczne jest sformułowane w jednej linijce, ale tempo zbieżności do normalności i sposób, w jaki nie-gaussowskie ogony utrzymują się przy skończonych rozmiarach próby, staje się intuicyjne tylko poprzez powtarzanie i bezpośrednią obserwację. Osiem symulacji w tym Spotlight zajmuje się właśnie tą luką.

I. Wyszukiwanie ścieżek A*

A* to standardowy algorytm wyszukiwania ścieżek w robotyce, tworzeniu gier i systemach nawigacyjnych. Łączy wyczerpujące wyszukiwanie najkrótszej ścieżki Dijkstry z funkcją heurystyczną, która kieruje wyszukiwanie w stronę celu, wymieniając wysiłek obliczeniowy na ukierunkowanie:

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

gdzie:
  g(n) : rzeczywisty koszt od startu do węzła n
  h(n) : heurystyczne oszacowanie kosztu od n do celu

Warunek dopuszczalności: h(n) ≤ prawdziwy koszt od n do celu
  ⇒ A* gwarantuje znalezienie optymalnej ścieżki

Popularne heurystyki dla grafów siatkowych:
  Manhattan:  h = |dx| + |dy|           (4-łączność)
  Czebyszew:  h = max(|dx|, |dy|)       (8-łączność)
  Euklidesowa: h = √(dx² + dy²)        (dowolna łączność)

Symulacja działa na siatce, gdzie ściany można rysować, klikając i przeciągając. Algorytm wykonuje się krok po kroku, kolorując komórki według ich bieżących wartości f, g i h. Zbiór otwarty (węzły rozważane) i zbiór zamknięty (węzły już przetworzone) są rozróżniane różnymi kolorami, a ostateczna najkrótsza ścieżka jest rysowana jasną zielenią. Suwak wagi heurystyki demonstruje ważone A* (f = g + wh): waga 1 daje optymalne A*, waga 0 degraduje do Dijkstry, a waga większa niż 1 daje suboptymalne, ale szybsze wyszukiwanie. Ta ostatnia cecha — wyraźna demonstracja kompromisu optymalność-szybkość — jest tą, która niezmiennie zaskakuje uczniów, którzy zakładali, że "lepsza heurystyka zawsze lepsza".

II. Krzywe Beziera

Krzywe Beziera leżą u podstaw każdego narzędzia grafiki wektorowej, silnika renderowania czcionek, systemu animacji i implementacji SVG w istnieniu. Są zdefiniowane algorytmem de Casteljau, który konstruuje krzywą poprzez wielokrotną interpolację liniową:

Algorytm de Casteljau dla krzywej stopnia n z punktami kontrolnymi P0...Pn:

  Pi(0) = Pi

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

  Punkt krzywej dla parametru t: B(t) = P0(n)

Postać wielomianu Bernsteina:
  B(t) = Σi=0n C(n,i) ti (1-t)n-i Pi

Właściwości:
  Leży wewnątrz otoczki wypukłej punktów kontrolnych
  Interpoluje punkty końcowe P0 i Pn
  Styczna w P0 jest wzdłuż (P1 - P0)

Symulacja renderuje konstrukcję de Casteljau dynamicznie, gdy parametr t przemiata się od 0 do 1. W każdym kroku pośrednie odcinki linii są rysowane w kolorze, pokazując dokładnie, które kombinacje liniowe produkują punkt krzywej. Punkty kontrolne można przeciągać, a krzywa aktualizuje się natychmiast. Selektor stopnia pozwala przełączać między krzywymi kwadratowymi (3 punkty kontrolne), sześciennymi (4), czwartego stopnia (5) i wyższych stopni. Otoczka wypukła wielokąta kontrolnego jest wyświetlana jako blada granica, czyniąc właściwość otoczki wypukłej bezpośrednio widoczną: krzywa nigdy z niej nie wychodzi, niezależnie od tego, jak są ułożone punkty kontrolne.

III. Wnioskowanie bayesowskie

Wnioskowanie bayesowskie to matematycznie spójne ramy aktualizacji przekonań w odpowiedzi na dowody. Twierdzenie Bayesa w najprostszej postaci:

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

posterior = wiarygodność × prior / dowód

Dla ciągłego parametru θ z priorami sprzężonymi:
  Beta-dwumianowy (estymacja proporcji):
    Prior:     θ ~ Beta(α, β)
    Wiarygodność: k sukcesów w n próbach
    Posterior:  θ ~ Beta(α + k, β + n - k)

  Normalny-normalny (estymacja średniej, znana wariancja):
    Prior:     μ ~ N(μ0, σ0²)
    Wiarygodność: x¯ z n obserwacji
    Posterior:  μ ~ N(μn, σn²)
    gdzie σn-2 = σ0-2 + n/σ²

Symulacja oferuje dwa tryby. W trybie rzutu monetą użytkownicy ustawiają prior Beta na prawdopodobieństwo obciążenia i obserwują, jak posterior aktualizuje się przy każdym nowym wyniku rzutu — klikając ręcznie lub uruchamiając zautomatyzowaną sekwencję. Prior, wiarygodność i posterior są wykreślane jednocześnie na tej samej osi, czyniąc twierdzenie Bayesa widoczną operacją geometryczną, a nie abstrakcyjnym wzorem. W trybie gaussowskim użytkownicy estymują średnią rozkładu normalnego o znanej wariancji, obserwując, jak posterior się zawęża wraz z gromadzeniem się obserwacji, i weryfikując, że średnia posterioru jest ważoną precyzją średnią priora i średniej próby.

IV. Centralne twierdzenie graniczne

Centralne twierdzenie graniczne (CTG) jest chyba najważniejszym wynikiem w statystyce. Mówi, że suma dużej liczby niezależnych zmiennych losowych, niezależnie od ich indywidualnego rozkładu, zbiega do rozkładu Gaussa. Ściślej, dla zmiennych IID o średniej μ i wariancji σ²:

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

Tempo zbieżności: twierdzenie Berry-Esseena
  |P(Sn ≤ x) - Φ(x)| ≤ C ρ / (σ³ √n)
  gdzie ρ = E[|X - μ|³]  (trzeci moment bezwzględny)
  Wolniejsza zbieżność dla rozkładów o ciężkich ogonach lub skośnych.

Symulacja pozwala użytkownikom wybrać spośród sześciu rozkładów macierzystych: jednostajny, wykładniczy, Cauchy'ego (który jawnie łamie warunki CTG z powodu nieokreślonej wariancji), Bernoulliego, dwumodalną mieszankę i Pareto z regulowanym wskaźnikiem ogona. Użytkownik ustawia rozmiar próby n, wykonuje powtarzane próbkowanie i obserwuje budujący się histogram średnich z próby. Nakładane jest teoretyczne przybliżenie normalne, a wykres Q-Q pokazuje, jak blisko empiryczny rozkład jest do Gaussowskiego. Tryb rozkładu Cauchy'ego jest najbardziej pouczający: średnia z próby nigdy nie zbiega, a wykres Q-Q odbiega coraz bardziej od przekątnej wraz ze wzrostem rozmiaru próby, czyniąc znaczenie warunku skończonej wariancji namacalnym.

V. Sieć Boolowska

Model sieci Boolowskiej NK Stuarta Kauffmana jest jednym z kanonicznych modeli układów złożonych i był stosowany do sieci regulacji genów, obwodów neuronowych i dynamiki wpływu społecznego. Każdy z N węzłów ma stan binarny i otrzymuje wejścia od K losowo wybranych innych węzłów, aktualizując się przez losową funkcję Boolowską:

Model NK Kauffmana:
  N węzłów, każdy o stanie binarnym si ∈ {0, 1}
  K losowych wejść na węzeł
  2K wpisów w losowej tabeli prawdy każdego węzła

Granica fazowa (przybliżenie wyżarzone):
  Kc = 1 / (2 p(1-p))
  gdzie p = prawdopodobieństwo wyjścia = 1

  K < Kc : faza uporządkowana  (atraktory małe, zaburzenia zanikają)
  K = Kc : faza krytyczna (atraktory ~ √N, odległość Hamminga ~ 1)
  K > Kc : faza chaotyczna  (atraktory wykładnicze, zaburzenia wzmacniają się)

Symulacja wyświetla N węzłów jako sieć okrągłą, każdy węzeł kolorowany według bieżącego stanu binarnego. Cykle atraktorów są wykrywane automatycznie i podświetlane: sieć zawsze wpada w powtarzający się cykl z dowolnego warunku początkowego, a symulacja pokazuje zarówno przejściowe zbliżanie się do atraktora, jak i długość cyklu atraktora. Krytyczna łączność K = 2 jest domyślnie wybrana, ponieważ leży na granicy fazowej dla p = 0,5: eksperymenty zaburzeniowe przy tej łączności nie pokazują ani natychmiastowego wygaśnięcia (faza uporządkowana), ani wybuchowego rozprzestrzeniania się (faza chaotyczna), lecz zamiast tego marginalną, dalekozasięgową propagację, którą Kauffman zaproponował jako sygnaturę biologicznych sieci regulatorowych.

VI. Drzewo B

Drzewo B jest dominującą strukturą danych do indeksowania baz danych i systemów plików, używaną w każdej większej relacyjnej bazie danych i systemie operacyjnym. Uogólnia binarne drzewo wyszukiwania, pozwalając węzłom mieć wielu potomków, utrzymując małą wysokość drzewa nawet dla miliardów rekordów:

Drzewo B rzędu m:
  Każdy węzeł wewnętrzny ma od ⌈m/2⌉ do m potomków
  Każdy węzeł liściowy ma od ⌈m/2⌉ - 1 do m - 1 kluczy
  Wszystkie liście są na tej samej głębokości h

Ograniczenie wysokości:
  h ≤ log⌈m/2⌉( (n+1)/2 )

Dla n = 106 rekordów, m = 100:
  h ≤ log50(500001) ≈ 3,4  ⇒  h = 4 co najwyżej

Dlatego drzewa B są używane do pamięci dyskowej:
  4 odczyty dysku, by zlokalizować dowolny rekord wśród miliona.

Symulacja animuje wstawianie, usuwanie i wyszukiwanie w drzewie B o rzędzie konfigurowanym przez użytkownika. Każda operacja jest przechodzona wizualnie krok po kroku: wstawienia wyzwalają podziały węzłów animowane jako podziały, usunięcia wyzwalają scalenia lub redystrybucję podświetlone przejściami kolorystycznymi, a wyszukiwania śledzą ścieżkę od korzenia do liścia z każdym porównaniem pokazanym. Drzewo automatycznie się rebalansuje, a wysokość jest wyświetlana na bieżąco, umożliwiając bezpośrednią obserwację, że wysokość rośnie tylko logarytmicznie wraz z wstawianiem rekordów — fundamentalna właściwość, która czyni drzewa B praktycznymi dla indeksów baz danych.

VII. Filtr Blooma

Filtr Blooma to probabilistyczna struktura danych, która odpowiada na zapytania o przynależność do zbioru bez fałszywych negatywów i z ograniczonym wskaźnikiem fałszywych pozytywów, wykorzystując ułamek pamięci, jakiej wymagałaby dokładna struktura:

Filtr Blooma z m bitami, k funkcjami hash, n wstawionymi elementami:

Prawdopodobieństwo fałszywego pozytywu:
  P(fp) ≈ (1 - e-kn/m)k

Optymalna liczba funkcji hash:
  kopt = (m/n) ln 2 ≈ 0,693 (m/n)

Optymalna liczba bitów na element dla docelowego wskaźnika fałszywych pozytywów p:
  m/n = -log2(p) / ln 2 ≈ -1,44 log2(p)

Przykład: wskaźnik fałszywych pozytywów 1% wymaga ~9,6 bitów/element
         0,1% wymaga ~14,4 bitów/element

Symulacja wyświetla tablicę bitów jako rząd kolorowych komórek. Każde wstawienie hashuje klucz k niezależnymi funkcjami hash i ustawia odpowiadające bity. Operacje zapytań śledzą te same pozycje hash, a fałszywy pozytyw jest wyzwalany, gdy wszystkie odpytywane bity okazują się ustawione przez wcześniejsze wstawienia innych kluczy. Wskaźnik fałszywych pozytywów mierzony eksperymentalnie zbiega do wzoru teoretycznego wraz z wstawianiem coraz większej liczby elementów, a wykres na żywo zmierzonego kontra przewidywanego wskaźnika fałszywych pozytywów potwierdza dokładność przybliżenia. Kompromis między m, k, n a wskaźnikiem fałszywych pozytywów jest w pełni regulowany, czyniąc problem projektowania filtra bezpośrednio eksplorowalnym.

VIII. Funkcje zespolone

Analiza zespolona jest jedną z najpiękniejszych dziedzin matematyki, a kolorowanie dziedziny czyni jej kluczowe obiekty bezpośrednio widocznymi. Funkcja zespolona f(z) przypisuje liczbę zespoloną każdemu punktowi płaszczyzny zespolonej; kolorowanie dziedziny mapuje wyjście na kolor:

Schemat kolorowania dziedziny:
  Odcień:        arg(f(z)) mapowany na [0, 2π]  (kąt)
  Jasność: |f(z)| kodowana funkcją okresową log|f(z)|

Zera f: punkty, gdzie |f(z)| = 0 (czarne)
Bieguny f: punkty, gdzie |f(z)| → ∞ (białe)
Cięcia gałęzi: nieciągłości odcienia

Przykłady:
  f(z) = z²      : odcień okręca się dwukrotnie wokół początku
  f(z) = 1/z     : biegun w początku (biały punkt), odcień okręca się wstecz
  f(z) = ez     : pozioma okresowość, brak zer i biegunów w ℂ
  f(z) = Γ(z)  : bieguny przy 0, -1, -2, ... (białe punkty), piękne spirale

Symulacja oblicza kolorowania dziedziny na GPU za pomocą shadera fragmentów WebGL, ewaluując wybraną funkcję w każdym pikselu jednocześnie i mapując wynik na przestrzeń kolorów HSL. Dostępne funkcje obejmują funkcje elementarne (wielomiany, funkcje wymierne, wykładnicza, logarytm, trygonometryczne), funkcje specjalne (Gamma, dzeta Riemanna, funkcje eliptyczne Jacobiego) oraz niestandardowy parser wyrażeń akceptujący dowolną składnię funkcji zespolonej. Przeciąganie widoku przesuwa, a kółko przewijania zoomuje, utrzymując renderowanie w czasie rzeczywistym przez cały czas.

Funkcja dzeta Riemanna to najbardziej wizualnie uderzająca opcja. Słynne nietrywialne zera na linii krytycznej Re(s) = 1/2 pojawiają się jako czarne punkty na wysokościach odpowiadających znanym wartościom (14,13, 21,02, 25,01, ...), a samopodobna struktura funkcji poza pasem krytycznym może być obserwowana bezpośrednio. Żadne inne powszechnie dostępne narzędzie nie pozwala osobie niebędącej specjalistą eksplorować funkcji dzeta na tym poziomie wizualnej bezpośredniości.

Dlaczego algorytmy i matematyka?

Czasem pojawia się pytanie: dlaczego umieszczać czysto abstrakcyjne algorytmy i matematykę na platformie, która zaczęła się od symulacji fizycznych? Odpowiedź jest taka, że granica między abstrakcyjną matematyką a rzeczywistością fizyczną nie znajduje się tam, gdzie się wydaje. A* jest używane w każdym pojeździe autonomicznym. Filtry Blooma obsługują miliardy zapytań dziennie w rozproszonych bazach danych, które służą nauce w takim samym stopniu, jak handlowi. Krzywe Beziera renderują każdą grafikę wektorową w każdej pracy naukowej i prezentacji. Centralne twierdzenie graniczne leży u podstaw każdego słupka błędu w każdym pomiarze fizycznym. Funkcje zespolone są matematycznym szkieletem mechaniki kwantowej. Sieci Boolowskie są stosowanymi modelami regulacji genów.