Project Euler

Matematyka obowiązkowa na maturze! I co tu napisać? Nawet gdybym zdawał maturę w tym roku to ten przedmiot wybrałbym tak czy siak. Najchętniej pośmiałbym się z jęków przerażonych maturzystów i wspomniał o „humanistach” (koniecznie w cudzysłowie), ale nie ma co kopać leżącego. Uważam, że matematyka to podstawa każdej nowoczesnej nauki, a jej znajomość jest niezbędna dla każdego kto chce o sobie z dumą mówić, że jest ogólnie wykształcony (nie mówiąc już o kolejnych stopniach wtajemniczenia naukowego).

Ostatnio znalazłem bardzo fajną stronę, z ponad dwoma setkami zadań matematyczno-informatycznych. Zazwyczaj zadanie takie składa się z krótkiego wprowadzenia i zagadki, na którą trzeba odpowiedzieć wprowadzając jedną liczbę. Cudo to nazywa się Project Euler i jest naprawdę wciągające dla osób, które lubią takie łamigłówki i znają chociażby podstawy programowania w dowolnym języku. Zadanie pierwsze można jeszcze od biedy policzyć na kartce:

Jeśli wypiszemy wszystkie liczby naturalne poniżej 10 które są wielokrotnościami 3 lub 5, otrzymamy 3, 5, 6 i 9. Ich suma to 23.

Znajdź sumę wielokrotności 3 lub 5 mniejszych od 1000.

Ale z kolejnym nie byłoby już tak łatwo:

Każdy nowy wyraz w ciągu Fibonacciego jest utworzony poprzez dodanie do siebie dwóch poprzednich wyrazów. Rozpoczynając od 1 i 2, pierwsze 10 wyrazów to:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Znajdź sumę wszystkich parzystych wyrazów ciągu które nie przekraczają 4 milionów.

Naprawdę fajna i wciągająca sprawa. Można potrenować znajomość języka programowania, algorytmów, matematyki i angielskiego. Ja rozwiązałem już 50 problemów (co przy 254 zagadkach nie jest niczym imponującym), ale staram się dalej

Márai o lądowaniu

Jest godzina czwarta nad ranem, kiedy w naszym mieszkaniu w Salerno rozbłyskuje ekran telewizora. Pierwszy człowiek, Armstrong, w tej chwili stawia stopę na Księżycu. Za nim jego towarzysz; obraz jest ostry, wyrazisty. Przysnąłem trochę w ciągu tego długiego czuwania, teraz przecieram oczy, odpędzam senność, mrugam powiekami. Robię to razem z setkami milionów ludzi, którzy widzą na własne oczy i słyszą na własne uszy, jak dwóch ludzi staje na Księżycu. Zaskakuje mnie, że nie znajduję w sobie uczucia entuzjazmu. Może dlatego, że ta chwila przekracza próg wyobraźni, widzę coś, na co świadomość nie potrafi już automatycznie odpowiedzieć? Armstrong i jego towarzysz niezgrabnie, słoniowato gramolą się z rakiety, zataczając się, w kangurzych podskokach odtańcowują księżycowy balet.

W gazetach, w radio i telewizji skrzypi retoryka lądowania na Księżycu. „Człowiek wyruszył w Kosmos, zwyciężając grawitację, przekroczył wymiar Czasu i Przestrzeni…” „Człowiek otrzymał w świecie nowe zadanie…” Wspomnienie, które zachowałem z porannej godziny, jest, nie wiadomo dlaczego, przygnębiające. Los Człowieka związany jest z Ziemią i jakkolwiek by się wysilał, musi pozostać Człowiekiem tu, na Ziemi.

Sándor Márai, Dzienniki

Gingerbread – prezentacja

Jedną z fajniejszych rzeczy na studiach jest Programowanie zespołowe. Wszyscy studenci III roku podzieleni są na 5-osobowe zespoły i przez cały rok każda grupa pisze jakiś program – wymyślony przez siebie lub narzucony przez opiekuna. W maju lub kwietniu odbywa się gala, na której grupy prezentują swoje dokonania. Wszystko to naprawdę robi wrażenie i muszę przyznać, że w poprzednich latach patrzyłem na dokonania starszych kolegów z dużym podziwem. Dzięki TV UMK już po 1,5 miesiąca (!) mogę przestawić naszą prezentację. Projekt nazywa się Gingerbread.

Parę słów o liczbach losowych

Komputery są fajne. W pół sekundy umieją policzyć ile jest 42363 * 1234 a w czasie wyświetlania wyniku mogą przy okazji puścić ulubioną empetrójkę. Niestety, w pewnym sensie komputery są jak inteligentny, choć nudny sąsiad na imprezie. Bez problemu powie Ci, jaka jest stolica Paragwaju, ale kiedy przychodzi zrobić coś naprawdę szalonego, nie masz co na niego liczyć. Rozłoży bezradnie ręce i głupawo się uśmiechnie. Dobrze, ale dlaczego komputer miałby robić coś szalonego?

Okazuje się, że komputerom czasem przydałoby się nieco nieprzewidywalności. Kiedy grasz w Sapera, to liczysz na to, że miny będą za każdym razem w innych miejscach – inaczej gra byłaby równie ciekawa, jak rozmowa z zegarynką. Odrobina nieprzewidywalności przydaje się też w poważniejszych sytuacjach. Gdy kupujesz w Internecie roczny zapas Pepsi, wpisując swój numer karty kredytowej, to naprawdę liczysz na to, że nikt inny tych danych nie podejrzy. Komputer szyfruje całą Twoją komunikację, wykorzystując pewne dane losowe jako tak zwany klucz.

Komputer. Dane losowe. Jest w tych dwóch sformułowaniach jakaś sprzeczność (coś jakby „Mój Nudny Znajomy Z Imprezy” i „Rowerowa Wycieczka Po Pustyniach Ameryki Południowej”). Komputer wykonuje ścisłe polecenia: weź tę liczbę, dodaj to tamtej, pomnóż wynik i wyświetl to na ekranie. Te operacje łatwo mu zdefiniować. Ale jak zmusić go, by coś wylosował? Odpowiedź jest bardzo prosta: nie da się.

Po prostu, nie da się zapisać algorytmu losowania liczby, dlatego, że liczba losowa z definicji nie jest generowana żadnym algorytmem. Oczywiście miłośnicy Sapera odezwą się: hola hola, przecież komputer układa mi te miny za każdym razem w inny, losowy sposób. Prawda. Jednak nie jest to sposób losowy, a pseudolosowy. Coś jak z tą demokracją i demokracją ludową.

Istnieją pewne funkcje matematyczne, których kolejne wartości są bardzo dziwne, pozornie niezwiązane ze sobą. Nie tak jak stary dobry sinus, co się wiecznie powtarza, czy logarytm, który nie chce dorosnąć. Są to dziwne funkcje, których wartość raz wynosi 12, w kolejnym kroku 54 a za chwilę znowu 37. Ktoś kto przyjrzałby się z boku takiej funkcji, nie znając jej wzoru, krzyknąłby: „te liczby nie mają żadnego związku, wyglądają jakby były losowe”. Słusznie, takie jest ich zadanie.

Komputery, gdy prosi się je, by podały nam liczbę losową, podają po prostu kolejną wartość takiej funkcji. A my, naiwni, wierzymy, że wartość ta rzeczywiście jest dziełem przypadku. Warto zwrócić uwagę, że każda taka funkcja losowa musi od czegoś zacząć. Inaczej mówiąc: musimy komputerowi podać pierwszą liczbę (ziarno), żeby na jej podstawie wygenerował kolejną. Jeśli podamy dwa razy tę samą liczbę jako ziarno, wówczas otrzymamy ten sam rozkład min na mapie. Ziarno więc powinno być w jakiś sposób losowe.

Dochodzimy do punktu wyjścia: skąd do … wziąć liczbę, którą podamy jako owe ziarno? Można użyć się na przykład bieżącego czasu (Saper uruchomiony o tej samej godzinie na innym komputerze będzie miał miny w tym samym miejscu), dla kolegów informatyków zapiszę ten pomysł jako

srand(time(NULL));

Inni używają na przykład temperatury procesora, czy danych na temat brzęczenia dysku twardego – uciekamy się więc do świata rzeczywistego, który jest naprawdę nieprzewidywalny (świetnym przykładem jest MZK Toruń, w szczególności linia nr 15). Wszystko to jednak nieco koślawe.

W świecie Internetu można by w elegancki sposób rozwiązać ten problem. Dlaczegóż by nie posadzić 100 osób, by rzucały setką kostek do gry, wpisywały wyrzucone liczby do komputera i zamieszczały je w Internecie, jako liczby rzeczywiście losowe, które każdy mógłby sobie ściągnąć? Pomysł ten został zresztą zrealizowany (z tym, że bez kostek, no i bez 100 osób).

Każde dziecko wie, że najbardziej nieprzewidywalną rzeczą na świecie jest pogoda (no, oprócz kobiet, ale je ciężko podłączyć do komputera). Wiedzą to i twórcy serwisu random.org, który pobiera tak zwany szum atmosferyczny i przetwarza go na eleganckie liczby. Serwis Prawdziwie Losowych Liczb – oto slogan owej strony (brzmi niczym nazwa strony z ocenami z egzaminu z Programowania Równoległego).

Od pogody jest jednakże coś bardziej nieprzewidywalnego – jest to atom promieniotwórczy. Ha! Zabrzmiało groźnie. Otóż taki atom promieniotwórczy może się rozpaść. Może też się nie rozpaść. O tym, czy w danej chwili atom się rozpadnie czy nie, wie tylko on sam. My, jako ludzie XXI wieku znamy prawdopodobieństwo zajścia jednego lub drugiego zdarzenia, ale to wszystko. Taki atom świetnie zastępuje osobę rzucającą kostką do gry, a urządzenie z większą ilością atomów mądrzy ludzie podłączyli do komputera i wyniki przesyłają na żądanie w serwisie hotbits. Atomowy saper – to jest gra warta napisania.

OK, wszyscy humaniści mogą się już oddalić, zaś miłośnikom języka Ruby polecam bibliotekę RealRand, która daje wygodny interfejs do obu serwisów:

require 'random/online'

generator1 = Random::RandomOrg.new
generator1.proxy_host = 'your.proxy.here'
generator1.proxy_port = 8080
generator1.proxy_usr  = 'your.user.here'
generator1.proxy_pwd  = 'secret'
puts generator1.randbyte(5).join(",")
puts generator1.randnum(100, 1, 6).join(",")  # Roll the dice 100 times.

Głupie pytanie

Czasem zdarza się, że nitki z kilku wątków naszego życia splatają się w jednym miejscu w gruby supeł – słyszymy jakąś piosenkę, oglądamy film i trach! – wszystko pasuje, jakby ktoś pisał o mnie. Obejrzałem ostatni internetowy komiks.

Hostage of love && Ulysses

W Trójce fajna piosenka leci. Nawet dwie.

Matematyka

Zastanawiałem się ostatnio, do czego możnaby porównać matematykę. Pierwsze skojarzenie: klocki Lego. Z drobnych cegiełek układamy większe konstrukcje, z nich jeszcze większe… No i tyle. Problem w tym, że w matematyce z tych większych układamy jeszcze większe i proces trwa i trwa  – w przeciwieństwie do klocków Lego, gdzie aż tak skomplikowanych rzeczy się nie robi.

Kwantowe komputery

Mechanika kwantowa. Według Bohra ludzie, którzy nie są zaszokowani, gdy pierwszy raz o niej słyszą, prawdopodobnie nigdy jej nie zrozumieją. Feynman twierdził, że może bezpiecznie powiedzieć, że nikt jej nie rozumie. Czasem dla rozrywki coś przeczytam sobie o mechanice kwantowej (o Nowym Umyśle Cesarza już wspominałem), ślizgając się na krawędzi zrozumienia, no przynajmniej zrozumienia tekstu.

Rzeczą, która mnie ostatnio zainteresowała (pod wpływem tego artykułu) są kwantowe komputery. Myśl o tym, że jakiś komputer może być w 2ⁿ pozycji na raz (gdzie n to ilość bitów, czy raczej bitów kwantowych – qubitów) jest całkiem inspirująca. Zresztą, powstało już parę przydatnych algorytmów na takie hipotytczne komputery, najbardziej znany to algorytm Shora. W wyżej wspomnianym artykule autor używa Pythonowej implementacji symulatora kwantowego komputera o nazwie qcs. Ponieważ o implementacji tej nie ma w necie zbyt dużo (w sumie, to znalazłem tylko dwie PDF-ki), ponadto napisana w języku którego nie znam, a przede wszystkim dlatego, że może to być fajne, postanowiłem napisać symulator w Ruby. Oto i rquantum. Mam nadzieję, że sprytne google’owe boty pokażą projekt komuś, komu może się przydać – osobiście niestety nie znam takiej osoby . Ale programowało się fajnie .

Nowy umysł cesarza

Jestem właśnie w trakcie lektury książki Rogera Penrose‘a pt. Nowy umysł cesarza. Autor zastanawia się, czy możliwe jest stworzenie komputera, który działałby tak jak ludzki umysł. Ale jak ten umysł właściwie działa? Aby to wyjaśnić, autor uważa za niezbędne przedstawienie teorii kwantów, ogólnej i szczególnej teorii względności, „klasycznych” teorii fizycznych, zagadnienia obliczalności, determinizmu, twierdzenia Gödla i wielu innych ważnych teorii nauk ścisłych. Czyni to jednak w sposób zrozumiały, każda nowa teoria jasno wypływa z poprzednich, a na początku wystarczy znajomość podstaw matematyki.

Zadziwiający dla mnie jest fakt, że w celu opisania działania ludzkiego umysłu, trzeba powoływać się na tak wiele nowych i zaawansowanych teorii. Jednak nawet te zaawansowane teorie nie wystarczają, aby w pełni wyjaśnić jak to się dzieje, że człowiek potrafi wymyśleć takie rzeczy i rozwiązać takie problemy, których setka komputerów nie rozwiąże nigdy.

Człowiek jest więc zwieńczeniem stworzenia, umysł jest bytem korzystającym z najbardziej zaawansowanych (a może właśnie najbardziej pierwotnych i podstawowych) właściwości naszego świata. Czy istnieją nauki bardziej humanistyczne niż nauki ścisłe, skoro matematyka i fizyka pozwalają nam dojść do takich właśnie wniosków?

Zbiór Mandelbrota

Kiedyś, gdy byłem dość młodym użytkownikiem 8-bitowego komputera Atari 65XE (z magnetofonem XC12 jako pamięcią masową) zobaczyłem w telewizji program edukacyjny poświęcony fraktalom. Zaciekawiło mnie to, że każdy fragment takiego fraktala po przybliżeniu daje w obraz bardzo podobny do całości. Marzyło mi się, żeby móc narysować coś takiego na moim komputerze – niestety nie posiadałem w tamtym czasie dostatecznych umiejętności matematyczynych, by zrozumieć w ogóle czym np. taki zbiór Mandelbrota jest (nie miałem zresztą również skąd zaczerpnąć tej wiedzy).

Na szczęście teraz mam dostęp do Wikipedii, a także znam już liczby zespolone – okazuje się, że nic więcej nie potrzeba, by zrozumieć, czym jest fraktal i jak go narysować. Jeśli jednak drogi czytelniku nie wiesz, czym są liczby zespolone, to nie przejmuj się tym za bardzo. Na użytek poniższego tekstu możemy przyjąć po prostu, że liczba zespolona określa pewien punkt na płaszczyźnie (tak jak liczba rzeczywista określa pewien punkt na prostej). Liczby zespolone najczęściej zapisuje się tak: , lub tak: . Liczba ma taką ciekawą właściwość, że podniesiona do kwadratu daje : . Wiedza ta przyda nam się do wyprowadzenia wzoru na kwadrat liczby zespolonej, który to wzór jest niezbędny do narysowania ładnego fraktala: .

Wiemy już, czym są liczby zespolone, jak można taką liczbę podnieść do kwadratu, możemy więc określić, czym jest zbiór Mandelbrota. Otóż, zbiór Mandelbrota, to zbiór takich liczby zespolonych , dla których ciąg określony wzorem rekurencyjnym:

ma określoną granicę (nie dąży do nieskończoności). W praktyce wystarczy sprawdzić, czy punkt określony przez tę liczbę zespoloną, leży w odległości mniejszej od od początku układu współrzędnych (w Wikipedii napisane jest, że dla , a nie dla , ale widocznie działa i tak i tak). Odległość punktu określonego przez liczbę zespoloną od początku układu współrzędnych można dość prosto obliczyć. Dla liczby zespolonej jest to po prostu . Odległość ta nazywa się modułem liczby zespolonej. Moduł ten musi więc wynosić mniej niż dla pewnej liczby pierwszych wyrazów ciągu . Powstaje oczywiście pytanie: ile tych pierwszych wyrazów trzeba zbadać. Odpowiedź nie jest taka prosta – im mniej wyrazów zbadamy, tym szybszy uzyskamy algorytm, ale z drugiej strony – tym mniej dokładny obraz fraktala powstanie.

Pozostaje jeszcze pytanie o kolory. Fraktale, które widziałem w telewizji były bardzo kolorowe, tymczasem w/w algorytm pozwala nam jedynie domyśleć się, gdzie postawić kropkę, a gdzie jej nie stawiać. Otóż, jeśli w pewnych punktach -ty wyraz ciągu z ma moduł większy od , to możemy sobie zapamiętać i na jego podstawie pokolorować punkt, który aktualnie rozważamy.

„Przepis” na narysowanie fraktalu Mandelbrota jak widać nie jest bardzo skomplikowany, a pozwala uzyskać zadziwiające efekty. Pół godziny pracy w C# zaowocowało następującym obrazkiem:

Jednak to nie koniec. Zachęcony powodzeniem tej operacji, postanowiłem sprawdzić, czy małe Atari poradzi sobie z narysowaniem fraktala (pomyślałem, że wystarczy przedstawienie dwukolorowe). Efektem krótkiego (nieco ponad 20 linijek!) programu w Basicu jest następujący obrazek:

Mimo, że program w Basicu był krótszy niż ten w C# (a może właśnie dlatego), wykonywał się on o wiele dłużej. Uruchomiłem go na emulatorze z opcją Full speed (prędkość 10-krotnie przewyższająca oryginalne Atari), a mimo to obrazek powstawał przez kilkanaście godzin. Może gdyby zakodować to w asemblerze…

Listing programu w Basicu.

Źródła w C#.