matematyka

Do tej pory przedstawiłem, czym są liczby pierwsze, ich zastosowania, jak możemy sprawdzać pierwszość liczb oraz jak możemy prostymi sposobami znajdować je. Jednak wszystko to, co do tej pory opowiedzieliśmy sobie, jest w dużej mierze zabawą. Jak poruszyłem już na samym początku serii, w kryptografii wykorzystuje się liczby pierwsze 2048-bitowe, więc w systemie dziesiętnym mogą one mieć nawet 617 cyfr. Dowiedzmy się więcej, jak jesteśmy w stanie odkryć tak duże, a nawet i większe liczby pierwsze. Na razie tylko w teorii.

Liczby pierwsze to jeden z ważniejszych terminów w matematyce, do tego mający dość istotne zastosowanie praktyczne. Na samym początku przygody z tym tematem przedstawmy sobie teorię, a także najprostsze testy pierwszości.

Tytuł brzmi strasznie, wiem. W końcu całki to już ten rejon matematyki, w który wielu nie chciało nigdy wchodzić. A w tym artykule nie dość, że opowiem, czym są całki, do tego oznaczone, to jeszcze pokażę sposoby na ich obliczanie. Co więcej, sposoby programistyczne! Ale tak całkowicie serio, to wbrew pozorom jest to bardzo prosty temat, za którym może nie stoi najprostsza matematyka, ale na pewno bardzo proste algorytmy. Tym samym stanowi to świetny początek do rozeznania rejonu algorytmiki, jakim są metody numeryczne.

Na przestrzeni ostatnich kilku artykułów zdążyłem poruszyć dwie zagadki logiczne: wieże Hanoi oraz kryptarytmy. Dlaczego więc nie opowiedzieć o najpopularniejszej z liczbowych zagadek logicznych, dostępnej w każdym osiedlowym kiosku — sudoku? Przy okazji poznamy kolejny algorytm, który może się przydać przy wyszukiwaniu rozwiązań wielu różnych problemów, nie tylko sudoku.

Wieże Hanoi to dla większości ludzi na świecie prosta, drewniana zabawka dla dzieci. Natomiast dla studentów informatyki to nie raz jedno z najgorszych wspomnień z pierwszych lat studiów i nauki programowania. Jak to możliwe? Co jest w nich takiego strasznego? Przekonajmy się na własną rękę.

Gdy we wczesnych latach podstawówki uczyliśmy się dzielenia (szczególnie „pod kreską”), w pewnym momencie dowiadywaliśmy się, że nie da się liczb idealnie podzielić. Czasami zostaje reszta. W końcu gdy dzielimy 6 na 4, to w szóstce zmieścimy tylko jedną czwórkę, ale to nie oznacza, że 6 dzielone przez 4 to po prostu 1. Mamy jeszcze 2 reszty, ewentualnie co dokładniejsi podaliby wynik 1,5. Jak się okazuje, obliczenie reszty z dzielenia, mimo że wydaje się czymś prostym i oczywistym... no cóż, zawsze coś musi się komplikować. Dlatego też przeanalizujmy tę operację: rozłóżmy ją na czynniki pierwsze i zobaczmy, co może tutaj pójść inaczej, i dlaczego, mimo różnych wyników, wciąż wszystko jest poprawnie.

Operując na grafice dwuwymiarowej, jesteśmy przyzwyczajeni, że możemy robić tak podstawowe operacje, jak jej obracanie, przesuwanie czy zmiana rozmiaru. Każdy program graficzny na to pozwala, a z punktu widzenia programisty są to operacje dostępne z poziomu CSS lub bibliotek graficznych. Ale, jak już nie raz na tym blogu, rozbiję to na czynniki pierwsze i pokażę, co tak naprawdę siedzi pod spodem tych funkcji, a dokładniej — matematyka za tym stojąca.

W poprzednim artykule pokazałem, jaka algorytmika stoi za rysowaniem linii na ekranie. Zaczęliśmy od znanego wszystkim wzoru na funkcję liniową, aby przejść do optymalnego algorytmu, który na pierwszy rzut oka nie ma z nim nic wspólnego. Tym razem chciałbym kontynuować tematykę grafiki komputerowej i pokazać, jaka algorytmika stoi tym razem za rysowaniem okręgów.

Korzystając na co dzień z komputera, jeżeli zastanawiamy się, jak on działa, to myślimy albo o tym, jakie algorytmy wykorzystują jakieś skomplikowane aplikacje, albo jakie rozwiązania użyto do ich stworzenia, albo, tak z innej strony, jak to wszystko działa na poziomie sprzętu. Jednak rzadziej się zastanawiamy nad rzeczami, które po prostu się dzieją, otaczają nas bez przerwy i nie są spektakularne, a jednak proces, jak to się dzieje, sam w sobie może być całkiem ciekawy. Dlatego dziś opowiedzmy sobie o tym, jaka algorytmika stoi za rysowaniem na ekranie, a dokładniej — rysowaniem linii (odcinków).

Z mojego poprzedniego artykułu wiemy już czym jest rekurencja, rekursja ogonowa oraz jak je stosujemy. Jednak temat rekurencji jest dość rozległy i warto opowiedzieć sobie o tym, jak rekurencji możemy się najzwyczajniej w świecie… pozbyć. Proces ten nazywamy derekursywacją i możemy podejść do tego na różne sposoby, których część tutaj opiszę.