Geometria i przypadek

Wstęp do działu

Ostatni dział algorytmiki łączy dwa światy, które na pozór nie mają ze sobą nic wspólnego: geometrię — bo komputery muszą rozumieć przestrzeń (gry, grafika, roboty, mapy, projektowanie) — i przypadek — bo, paradoksalnie, losowość bywa najszybszym sposobem policzenia rzeczy zupełnie nielosowych. Oba tematy są niemal w całości domeną rozszerzenia, oba są ulubieńcami matury rozszerzonej, i oba pokazują algorytmikę z nowej strony: nie „przetwórz dane", lecz „zrozum kształt" i „oszacuj przez eksperyment".

Nauczysz się, jak komputer rozstrzyga rzeczy, które dla oka są oczywiste, a dla maszyny wcale — po której stronie prostej leży punkt, czy dwa odcinki się przecinają, czy punkt jest wewnątrz trójkąta. A potem odwrócisz intuicję: zamiast liczyć pole skomplikowanej figury wzorem (którego często nie ma), rzucisz w nią losowo tysiące punktów i policzysz, ile trafiło — metodą Monte Carlo, którą wymyślono przy konstrukcji bomby atomowej, a dziś liczy się nią wszystko od liczby π po ryzyko finansowe. To zaskakujące, eleganckie i głęboko informatyczne domknięcie części o algorytmice.

Mapa pojęć działu

              GEOMETRIA I PRZYPADEK
                      |
   ┌──────────────────┴──────────────────┐
 GEOMETRIA OBLICZENIOWA          METODA MONTE CARLO
 punkt względem prostej          licz przez losowanie
 (iloczyn wektorowy — znak!)      π z rzucania punktów
 przynależność do odcinka        pole figury = trafienia/próby
 przecinanie odcinków            ruchy Browna (błądzenie losowe)
 punkt w trójkącie                      |
        |                     losowość liczy rzeczy NIElosowe
 orientacja trójki punktów:      (im więcej prób, tym dokładniej —
 lewo / prawo / współliniowo      prawo wielkich liczb)

Jednostki w tym dziale

10.1 Punkt, prosta, odcinek — orientacja (rozszerzenie)
10.2 Przecinanie odcinków i punkt w trójkącie (rozszerzenie)
10.3 Monte Carlo — licz przez losowanie (rozszerzenie)
10.4 Ruchy Browna — symulacje losowe (rozszerzenie)