Devlog #90 – Fala 69: Otoczka Wypukła, Algorytm Grovera, Meandrowanie Rzeki, Fizyka Liny, Perceptron i Rezonans Orbitalny

Nowe symulacje

Otoczka wypukła: trzy algorytmy, jedna scena

Otoczka wypukła to najmniejszy wypukły wielokąt zawierający zbiór punktów — algorytmiczny odpowiednik naciągania gumki wokół gwoździ na desce. Trzy klasyczne algorytmy podchodzą do tego inaczej, a obserwowanie ich rywalizacji na tym samym wejściu jest jedną z najbardziej pouczających rzeczy w geometrii obliczeniowej.

Graham scan O(n log n)

Posortuj wszystkie punkty według kąta biegunowego względem najniższego punktu (rozstrzygając remisy według odległości). Następnie przemieć posortowaną listę: dla każdego nowego punktu usuń z otoczki punkty tworzące skręt zgodny z ruchem wskazówek zegara (nie w lewo) za pomocą iloczynu wektorowego 2D (b−a) × (c−a) = (b.x−a.x)(c.y−a.y) − (b.y−a.y)(c.x−a.x). Punkty współliniowe są obsługiwane jawnie — symulacja pozwala przełączać, czy włączać je do otoczki, czy wykluczać.

Marsz Jarvisa O(nh)

Zawijanie w prezent (gift wrapping) jest intuicyjne: zacznij od najbardziej wysuniętego w lewo punktu i wielokrotnie znajduj punkt tworzący najmniejszy kąt przeciwny do ruchu wskazówek zegara z bieżącą krawędzią. Przy n punktach łącznie i h na otoczce jest to O(nh) — szybsze niż Graham, gdy h jest małe, ale degeneruje się do O(n²) dla okrągłych wejść. Symulacja pokazuje obracającą się strzałkę „ramienia zawijającego" na każdym kroku.

Quickhull — dziel i zwyciężaj

Znajdź najbardziej wysunięte w lewo i w prawo punkty (krawędź bazowa). Najdalszy punkt od linii bazowej na pewno leży na otoczce — dodaj go i rekurencyjnie rozwiąż dwa trójkątne podproblemy. Średnio O(n log n), przypadek najgorszy O(n²) dla wejść przeciwnych. Rekurencyjny podział jest wizualizowany kolorowo oznaczonymi regionami.

• Wszystkie trzy algorytmy animowane jednocześnie na tym samym zbiorze punktów
• Licznik operacji na żywo dla każdego algorytmu (porównania + zamiany)
• Ustawienia wejściowe: losowe, skupione, okrągłe, przypadek przeciwny dla Quickhull
• Tryb krok po kroku, by zatrzymać się na każdej operacji

Wyszukiwanie Grovera: kwantowe wzmocnienie amplitudy

Klasyczne wyszukiwanie nieuporządkowane wymaga O(N) zapytań, by znaleźć jeden zaznaczony element wśród N. Algorytm Grovera (1996) robi to w O(√N) — dowiedlnie optymalne kwadratowe przyspieszenie — wykorzystując jedynie kwantową superpozycję i dwa proste operatory.

Operatory wyroczni i dyfuzji

Algorytm działa w całości na amplitudach rzeczywistych (bez potrzeby faz zespolonych dla jednego zaznaczonego elementu). Każda iteracja Grovera stosuje:

1. Wyrocznia: odwraca znak amplitudy stanu docelowego: α_cel → −α_cel
2. Dyfuzja: inwersja wokół średniej: α_i → 2μ − α_i, gdzie μ to średnia amplituda

Amplituda celu rośnie z każdą iteracją, podczas gdy wszystkie pozostałe maleją. Po k* = ⌊π√(N/M)/4⌋ iteracjach (M zaznaczonych elementów) prawdopodobieństwo sukcesu osiąga szczyt blisko 1. Nadmierna rotacja ponownie je zmniejsza — symulacja pokazuje ten okresowy zanik i odrodzenie.

Obraz geometryczny

W dwuwymiarowej podprzestrzeni rozpiętej przez |zaznaczone⟩ i |niezaznaczone⟩ każda iteracja Grovera to rotacja o kąt 2θ, gdzie sin(θ) = √(M/N). Geometryczny inset pokazuje tę rotację jawnie, czyniąc strukturę algorytmu natychmiast zrozumiałą.

• N od 4 do 128 stanów; M od 1 do N/2 zaznaczonych elementów
• Wykres słupkowy amplitud animowany w czasie rzeczywistym
• Wykres prawdopodobieństwa sukcesu w funkcji iteracji z oznaczeniem optymalnego k*
• Klasyczna oczekiwana liczba zapytań O(N) pokazana dla porównania

Meandrowanie rzeki: ewolucja sterowana krzywizną

Rzeki nie płyną prosto zbyt długo. Niewielkie zaburzenie rośnie w wężowate meandry, gdy erozja na brzegu zewnętrznym przewyższa depozycję na brzegu wewnętrznym — dodatnia pętla sprzężenia zwrotnego napędzana siłą odśrodkową płynącej wody.

Równanie migracji

Każdy węzeł i na linii środkowej rzeki migruje prostopadle do kierunku przepływu z prędkością proporcjonalną do przestrzennie opóźnionej krzywizny: dn/dt = E₀ · Σ C(s) · κ(s − opóźnienie), gdzie κ to lokalna krzywizna, a opóźnienie uwzględnia przesunięcie w dół rzeki szczytu erozji względem szczytu krzywizny. Ta opóźniona odpowiedź jest tym, co powoduje meandrowanie, a nie losowe błądzenie.

Powstawanie starorzeczy

Gdy pętla meandra zaciska się na tyle, że dwa niesąsiadujące węzły znajdują się w odległości mniejszej niż próg odcięcia (proporcjonalny do szerokości koryta), następuje odcięcie szyi: koryto skraca się przez szyję, a porzucona pętla staje się starorzeczem. Symulacja zachowuje paleokoryta jako blade ślady — dokładnie tak, jak wyglądają na zdjęciach satelitarnych równin zalewowych.

• Panel statystyk: współczynnik krętości (długość całkowita / odległość prosta), liczba starorzeczy, dominująca długość fali
• Regulowana amplituda początkowego zaburzenia i tempo migracji
• Tryb poklatkowy kompresuje tysiące lat ewolucji

Fizyka liny: Verlet + więzy Jacobiego

Integracja Verleta oparta na pozycjach przechowuje tylko bieżącą i poprzednią pozycję, wywodząc prędkość niejawnie jako v ≈ (x_teraz − x_poprz) / dt. To sprawia, że dodawanie więzów jest trywialne — wystarczy skorygować pozycje bezpośrednio, bez dotykania prędkości, które są następnie automatycznie aktualizowane.

Relaksacja więzów Jacobiego

Każdy segment liny ma długość spoczynkową L₀. Korekta więzu dla pary węzłów to: przesuń każdy węzeł w kierunku drugiego (lub od niego) o połowę błędu długości: Δx = ½ · (d − L₀) · n̂, gdzie d to bieżąca odległość, a n̂ to wektor jednostkowy. Uruchomienie K iteracji tego na klatkę przybliża linę nierozciągliwą — K=1 daje elastyczną, rozciągliwą linę, K=20+ daje sztywną linę. Aktualizacja Jacobiego (jednoczesna) unika kierunkowego obciążenia właściwego metodzie Gaussa-Seidla.

• 5 ustawień: bat (jeden przypięty koniec), most (dwa punkty mocowania), łańcuch łańcuchowy o dwóch punktach, swobodne opadanie w spiralę, siatka tkaniny
• Przeciąganie dowolnego węzła interaktywnie; dodawanie przeszkód w postaci cylindrycznych palików
• Suwak K od 1 do 30 iteracji na klatkę
• Suwaki kierunku i wielkości grawitacji

Perceptron: pierwotna sieć neuronowa

Perceptron Franka Rosenblatta z 1957 roku to najprostszy klasyfikator z możliwością trenowania. Utrzymuje wektor wag w i klasyfikuje wejście x jako dodatnie, jeśli w·x > 0, w przeciwnym razie jako ujemne. Reguła aktualizacji jest elegancko prosta: gdy tylko wystąpi błąd, przesuń wagi we właściwym kierunku.

Reguła uczenia i zbieżność

Dla każdego błędnie sklasyfikowanego przykładu (y · (w·x) ≤ 0), aktualizuj: w ← w + η · y · x. Twierdzenie o zbieżności perceptronu gwarantuje, że proces zakończy się w skończonej liczbie kroków, jeśli dane są liniowo separowalne — ograniczonej kwadratem marginesu. Symulacja liczy błędy na przebieg (epokę) i pokazuje ich malenie do zera dla zbiorów separowalnych.

Problem XOR

XOR nie jest liniowo separowalny — żadna pojedyncza hiperpłaszczyzna nie może poprawnie podzielić czterech punktów. Perceptron krąży w nieskończoność, oscylując między częściowymi rozwiązaniami. To ograniczenie, podkreślone przez Minsky'ego i Paperta w 1969 roku, zmotywowało rozwój sieci wielowarstwowych. Symulacja pokazuje to dobitnie: granica decyzyjna kręci się bez końca na XOR, po czym błyskawicznie zbiega się na zbiorze Gaussa.

• 5 zbiorów danych: dwa rozkłady Gaussa, pasek, XOR (zawodzi), okrąg w kwadracie (zawodzi), niestandardowy (kliknij, by dodać punkty)
• Płaszczyzna granicy decyzyjnej animowana w czasie rzeczywistym
• Wykres błędów na przebieg odróżnia zbieżność od krążenia
• Suwak współczynnika uczenia η

Rezonans orbitalny: rytmy Keplera

Rezonans zachodzi, gdy dwa ciała krążące wykonują całkowite proporcje orbit w tym samym czasie, powodując powtarzające się kopnięcia grawitacyjne w tej samej fazie orbitalnej. Rezonanse te mogą stabilizować orbity (trojańczycy Jowisza, księżyce galileuszowe) lub je oczyszczać (luki Kirkwooda w pasie planetoid).

Trzecie prawo Keplera i kąt rezonansowy

Dla orbit kołowych okres T = a^(3/2) (w odpowiednich jednostkach). Rezonans p:q wymaga T₂/T₁ = p/q, więc a₂/a₁ = (p/q)^(2/3). Kąt rezonansowy σ = pλ₂ − qλ₁ (gdzie λ to średnia długość) libruje wokół stałej wartości, jeśli rezonans jest aktywny, lub cyrkuluje przez 360°, jeśli nie. Libracja oznacza, że planety zawsze spotykają się w pobliżu tej samej fazy — kopnięcia są spójne.

Galileuszowy rezonans trójciałowy 4:2:1

Księżyce galileuszowe Io, Europa i Ganimedes są zablokowane w rezonansie Laplace'a: na każdą orbitę Ganimedesa Europa wykonuje 2, a Io wykonuje 4. Kąt Laplace'a λ₁ − 3λ₂ + 2λ₃ libruje wokół 180° — trzy księżyce nigdy nie są jednocześnie wyrównane. To zapobiegło katastrofalnej niestabilności orbitalnej przez 4 miliardy lat.

• 6 ustawień rezonansu: 1:1, 3:2, 2:1, 5:3, 4:1 oraz porównanie poza rezonansem
• Znaczniki koniunkcji (czerwone kropki) grupują się w tym samym kierunku podczas rezonansu
• Wykres kąta rezonansowego σ pokazuje librację kontra cyrkulację
• Ustawienie galileuszowe pokazuje trójciałowy rezonans Laplace'a

Co dalej

Fala 70 zajmuje się matematyką zarządzania projektami (ścieżka krytyczna CPM/PERT z niepewnością PERT), klasyfikacją k najbliższych sąsiadów, wyboczeniem kolumny Eulera ze współczynnikami długości efektywnej, przeszukiwaniem drzewa minimax z przycinaniem alfa-beta, pułapkowaniem cząstek w pasie Van Allena w polu dipolowym oraz relaksacją Lloyda dla centroidalnej triangulacji Woronoja.