W informatyce bardzo często spotykamy się z pojęciem losowości. Generujemy losowe liczby (w tym pierwsze), losowe dane. Wymieniając bardziej szczegółowo, mamy losowe identyfikatory, losowy stan gier, losowe przeszukiwanie przestrzeni rozwiązań. Przykładów można wymieniać wiele, tylko odpowiedzmy sobie na kluczowe pytanie — jak w ogóle komputer losuje? Czy komputer jest w stanie wygenerować coś, co jest naprawdę losowe?

W aplikacjach graficznych jedną z dostępnych funkcji jest możliwość skorygowania perspektywy wykonanego zdjęcia. Zwykle jest to w bardzo prostej formie, gdzie korygujemy perspektywę do „wyprostowania” zdjęcia. Możliwe, że spotkałeś(-aś) się z tym w aplikacjach mobilnych, gdzie po zrobieniu zdjęcia kartki z tekstem aplikacja sama wyprostuje zdjęcie. Robienie czegoś takiego (aczkolwiek bez wykrycia położenia kartki) jest przedmiotem tego artykułu. Zrozummy temat z punktu widzenia matematyki, a następnie zaimplementujmy wszystko od zera. Aczkolwiek po drodze wskażę też, gdzie można znaleźć gotowe rozwiązania.

Już dawno niczego nie rysowaliśmy na blogu, czyż nie? Powróćmy więc do tej przyjemnej serii i zobaczmy, w jaki sposób algorytmicznie rysować kolejną rzecz. Tym razem częściowo w klimacie zbliżających się świąt — porysujmy gwiazdy. A to dlatego, że kryje się za tym prosta, ale ciekawa matematyka i algorytmika.

Opowiadając do tej pory o problemie komiwojażera (TSP), pokazałem, w jaki sposób możemy bardzo powoli znajdować optymalne rozwiązanie i jak zadowalające (nieco szybciej), korzystając z heurystyk. Wszystko to były sposoby stworzone typowo pod problem komiwojażera i nie da się ich przełożyć na inne problemy obliczeniowe. Mamy jednak całą klasę algorytmów metaheurystycznych, które możemy wykorzystać do dowolnych, trudnych obliczeniowo problemów. Poznajmy przykładowe, dalej zostając w uniwersum TSP.

Opisując ostatnio problem komiwojażera, pokazałem sposoby, jak możemy otrzymać optymalne rozwiązanie. Niestety, co było widać na przykładach załączonych w artykule, algorytmy te były bardzo wolne, więc i nie do użycia w praktycznych zastosowaniach. W praktyce zaś stosuje się heurystyki, które może nie zapewniają znalezienia najlepszego rozwiązania, ale w zależności od tego, jaką zastosujemy, możemy uzyskać wynik bliski optymalnego. Zobaczmy przykładowe podejścia tego typu.

Do tej pory na blogu miałem okazję pokazać dwa ciekawe problemy obliczeniowe: problem skoczka szachowego oraz zliczania unikalnych elementów. Omawiając je (i nie tylko), wspominałem o innym, może i najbardziej znanym — problemie komiwojażera. Czytaj dalej, aby dowiedzieć się, o co w nim chodzi, jak możemy go rozwiązać, dlaczego na okładce jest listonosz, a także co ma wspólnego z grafami. Tak, niemal równo po dwóch latach wracam na blogu do tematyki grafów.

Bardzo często w Internecie znajdziemy przykłady dziwnego kodu, najczęściej napisanego w JavaScripcie. Nie zabierając temu wartości humorystycznej, to nieraz takie wpisy pokazują brak zrozumienia mechanizmów języków programowania. Wybrałem 5 takich przykładowych dziwactw, które wyjaśnię, dlaczego tak jest. Oczywiście dalej będzie mogło to wszystko wydawać się dziwne, ale może już nieco mniej. Dodatkowo, żeby nie było tak dobrze, większość przykładów nie będzie javascriptowa.

Programowanie jeszcze do niedawna mogło się niektórym wydawać wiedzą ezoteryczną, tajemną, przekazywaną jedynie wybranym. Dziś zwykłe programowanie raczej nikogo nie zadziwia, a też dostęp do wiedzy o nim jest powszechny. Jednak coś się ostało — mamy całą kategorię ezoterycznych języków programowania. A pośród nich, prawdopodobnie najbardziej rozpoznawalny z nich w dużej mierze dzięki swojej nazwie, Brainfuck. Dowiedzmy się, na czym polega ta programistyczna ezoteryka i spróbujmy napisać jakiś kod w ten sposób.

Każdy, kto na matematyce dotarł do kombinatoryki, trafił na dziwną operację matematyczną, gdzie w nawiasie zapisywało się dwie liczby jedna pod drugą bez kreski ułamkowej. Jest to symbol Newtona, znany też jako współczynnik dwumianowy Newtona. Tutaj jednak nie chcę się skupiać na jego zastosowaniu w matematyce, tylko na tym, jak go obliczać. Przejdziemy krok po kroku przez różne podejścia, tym samym eksplorując na konkretnym przykładzie, w jaki sposób można optymalizować algorytmy. A na dokładkę opowiemy sobie o powiązanym z symbolem Newtona trójkącie Pascala, którego tworzenie jest popularnym ćwiczeniem dla początkujących programistów.

Na łamach bloga miałem już okazję pokazywać, jak narysować zegar analogowy, wykorzystując do tego celu prostą matematykę. Dzisiaj przedstawię inny rodzaj zegara, który traktuje się raczej jako ciekawostkę — zegar binarny. Na początek jak odczytujemy na nim godzinę (w zależności od rodzaju), a następnie spróbujemy wspólnie zaprogramować wyświetlanie czasu w taki sposób.