728 x 90

O losowości nie tylko w informatyce. Część 1

O losowości nie tylko w informatyce. Część 1

Czym jest losowość? Trudne pytanie. Na pewno losowość nie jest przekleństwem. W informatyce jest wręcz pożyteczna; wystarczy zerknąć do podręcznika Mitzenmachera i Upfala ,,Metody probabilistyczne i obliczenia”. Nie tylko pytanie o to czym jest losowość wydaje się trudne. Wytwarzanie losowości w dużych ilościach wydaje się nie mniej trudne, a o ileż bardziej istotne w praktyce.

W myśl znanej zasady praktyków: nie wiem co to jest, ale świetnie działa, skuteczne wytwarzanie losowości jest ważniejsze niż rozumienie jej istoty. A może nie da się być skutecznym w danej materii bez jej zgłębienia? Zwykle oszukujemy naturę za pomocą pseudolosowości. Celem złagodzenia tej ułomności opracowano wiele technik wspomagających generowanie losowości, od klasycznego wybielacza von Neumanna (sposób na nieuczciwą monetę) po współczesne ekstraktory losowości. [Łagodnie podprowadza pod temat Avi Wigderson wykładem ,,Randomness (and Pseudorandomness)”   https://www.youtube.com/watch?v=ZzsFb-6wvoE ] Tylko czy to jeszcze próba zrozumienia losowości, czy już jej użytkowanie? Dyskretnie ignorujemy tu zaawansowanie matematyczne aparatu pojęciowego. Zadajmy wobec tego pytanie o istotę losowości w nieco odmienny sposób.

Czy losowość jest czymś obiektywnym? Znowu trudne pytanie. Początki metod statystycznych w fizyce odwołują się do niedostatku informacji. Teoretycznie można śledzić indywidualny ruch cząsteczek gazu, ale jeśli cokolwiek ma zostać obliczone w rozsądnym czasie, to skazani jesteśmy na uśrednienia. Jednak nawet gdyby losowość nie istniała, to człowiek by ją wymyślił. Bez losowości trudno bowiem nawet podjąć decyzję. Pamiętamy ciągnięcie słomek, gdy trzeba znaleźć ochotnika do wykonania niewdzięcznego zadania? Sędziowski rzut monetą przed meczem? To nie przypadek ani szczyt wyrafinowania. Opierając się na pojęciu losowości Klemens Szaniawski wyróżnił dwie zasady sprawiedliwego podziału dóbr: zasadę równych szans satysfakcji i zasadę równych szans wyboru. Cała książka autorstwa Lissowskiego o znamiennym tytule ,,Zasady sprawiedliwego podziału dóbr” została poświęcona podobnym dylematom. Jak to w nauce bywa ustalenia są niejednoznaczne; niczym w słynnym pytaniu: jaką metodą wybierzemy metodę głosowania?

I w drugą stronę: nawet jeśli losowość jest wymysłem, to człowiek może ją generować. Tu znowu pojawiają się kwestie z teorii gier i decyzji. Pamiętamy grę kamień, nożyce, papier? Każdy świadomie (cokolwiek to by miało nie znaczyć, ale wielu ludziom świadomość jawi się być czymś dalekim od przypadkowości) podejmuje decyzję. Aby wygrać musi przechytrzyć przeciwnika. Optymalne jest nieprzewidywalne stosowanie każdej z trzech strategii z jednakową częstością (tzw. mieszana strategia minimaksowa von Neumanna). Starając się grać jak najlepiej będziemy generowali ciąg losowy. Chyba, że wyczujemy u przeciwnika słabość (np. skłonność do ściskania dłoni w kształt kamienia) i ogramy go naszą poczciwą niesztuczną inteligencją.

Nie mamy słomek do losowania? Zagrajmy w marynarza. Powiedzmy, że w klasie dziesięcioosobowej (marzenie?) wybieramy ucznia do tablicy. W tym celu przypisujemy każdemu uczniowi jednoznaczny numer od 0 do 9 i sumujemy liczbę wyciągniętych przez wszystkich palców (u obu rąk) włączając w to palce nauczyciela. Wartość reszty z dzielenia przez 10 wskazuje szczęśliwca. Metoda jest sprawiedliwa w sensie Szaniawskiego. (Halo wieża: szczęśliwiec doznaje równych szans wyboru, czy równych szans satysfakcji?) Co ważniejsze, gra w marynarza jest odporna na manipulacje. Gdyby nawet cała klasa się zmówiła i chciała wysłać do tablicy swego dobrze przygotowanego kolegę, to elementu randomizacyjnego dostarcza nauczyciel.

Czy natura jest losowa? Wydaje się to być jej immanentną cechą i to na dwa ,,sposoby” zawarte w hasłach fizyka kwantowa oraz chaos deterministyczny. Tematyka kwantowych komputerów jest obecnie (lipiec 2017) chyba bardziej gorąca niż lato zapowiadane w mediach jako wielce groźne z racji na nadciągające sporadycznie egipskie upały. Nie potrzeba jednak kwantowego Bonda, by natura mrugała do nas losowo wytwarzając dziwnie uporządkowany chaos. Okazuje się, że już w świecie demona Laplace’a (teoretyczna możność przewidywania trajektorii wszystkich cząsteczek gazu) nie wszystko daje się przewidzieć. Kłopoty są co najmniej astronomicznej, meteorologicznej, chemicznej, zoologicznej i elektrycznej natury, a ich wdzięczne nazwy to: zagadnienie trzech ciał, motyl Lorenza, zegar Biełousowa-Żabotyńskiego, morfogeneza Turinga i obwód Chuy. Wszystkie te zagadnienia mogą się pojawić w życiu informatyka jako ćwiczenie programistyczne z obliczeń naukowych (dla leniwych kilka linijek w pakiecie algebry komputerowej). Zresztą nie ma czego się bać, gdyż podobnie jak kwantowość, tak i chaos zagościł już na stałe w kulturze, choćby w postaci tytułu pierwszej nieanglojęzycznej książki fantastyczno-naukowej, która zdobyła Nagrodę Hugo: Problem trzech ciał.

Zwróćmy uwagę na trzy nazwiska, które się dotąd pojawiły. Turing dał podstawy logiczne pojęciu obliczenia. Przykładową realizację maszyny liczącej odzwierciedla architektura von Neumanna. Trzecie nazwisko to Chua. Choć pierwsze realizacje komputerów były analogowe (lampowe), to dopiero wynalazek tranzystora umożliwił maszynom liczącym osiągnąć przeogromny sukces. Czy można coś jeszcze wymyślić w elektronice bez nanotechnologii, spintroniki itp.? Teoretycznie tak, czego przykładem jest memrystor wykoncypowany przez Chuę w 1971, a który być może już niedługo uda się wytworzyć w praktyce. Nomen omen, być może właśnie dzięki nanotechnologii.

Dalszą podróż będziemy kontynuować w części 2.

Źródło obrazu tytułowego: freeimages.com

2 comments

Leave a Comment

Your email address will not be published. Required fields are marked with *

Cancel reply

2 Comments

  • Mateusz
    11 lipca 2017, 21:45

    Największy problem z losowością polega na tym, że nikt nie potrafi napisać porządnej definicji tego zjawiska. Dlatego ścisłowcy zajmują się tak naprawdę procesami, które wyglądają na losowe (pseudolosowość), a losowość (na nieszczęście?) została filozofom…

    REPLY
    • Druh much@Mateusz
      12 lipca 2017, 23:14

      Nie wszystko stracone. W drugiej części pojawi się ,,ludowe" pojęcie losowości (namacalne). Z potencjałem do wyjaśniania niektórych symulacji komputerowych. Ma jednak poważną wadę – nie jest cryptographically strong; wręcz na odwrot. Chyba, że ktoś wierzy, że można innych przechytrzyć i bezczelnie w szyfrowanej kłódeczce ustawić ,,1234". https://www.youtube.com/watch?v=U_eZmEiyTo0 [Princess Bride; Vizzini vs Prince]

      REPLY

Inne artykuły