Algorytmy

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?

Piąty rok istnienia bloga świstak.codes trzeba zacząć z przytupem. Czas więc poeksplorować temat matematyczny, który jest na pewno bliski sercom programistów lubującym się w wyzwaniach algorytmicznych typu Advent of Code. A jest to chińskie twierdzenie o resztach. Dowiedzmy się, o co w nim chodzi, jak działa i jakie ma praktyczne zastosowania. Co najważniejsze dla programistów, pokażę także, jak je zaimplementować w kodzie.

Przez 8 artykułów na blogu omawiałem sortowanie i wówczas interesowało nas ułożenie elementów rosnąco bądź malejąco na podstawie ich cech — w tamtym przypadku po wartości numerycznej. Często też sortujemy po nazwie lub czasie utworzenia. Jednak w praktyce, przy pisaniu aplikacji, często spotykamy się z przypadkiem, gdy chcemy umożliwić użytkownikom ustawienie własnej kolejności elementów. Mimo że brzmi to prosto, implementacja wbrew pozorom niekoniecznie taka musi być. Zobaczmy, jak ten problem rozwiązać.

W rzeczywistym świecie mamy nieraz potrzebę jasnego zidentyfikowania, że coś jest czymś w taki sposób, żeby było to określenie jak najbardziej unikalne jak się da. Stąd mimo że każdy z nas ma imię i nazwisko, to jednak mamy też nadane numery PESEL, bo same imię i nazwisko nie są wystarczająco unikalne. Z dokładnie taką samą potrzebą spotykamy się w informatyce. Musimy być w stanie jasno zidentyfikować dowolną encję: plik na dysku, wpis w bazie danych, wersję oprogramowania, podzespół w komputerze. Poznajmy przykładowe sposoby, jak takie identyfikatory się generuje.

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.

W świecie informatyki mamy wiele znanych problemów obliczeniowych, takich jak problem komiwojażera, które z jednej strony mają praktyczne zastosowania, a z drugiej stanowią idealny przykład do nauki algorytmów heurystycznych. Dzisiaj chciałem pokazać mniej znany z problemów, który, nawet mogłoby się wydawać na pierwszy rzut oka, problemem nie jest — zliczanie unikalnych elementów. Opowiem, dlaczego jest to problem, gdzie ma zastosowania i pokażę do niego przykładowe podejście algorytmiczne.

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.

W artykule o krzywych Béziera wspomniałem, że będą one zawsze zawierać się wewnątrz otoczki wypukłej wszystkich punktów kontrolnych je opisujących. Można zadać bardzo trafne pytanie — jak je wyznaczyć? Mimo że na pierwszy rzut oka nie brzmi to jakoś fascynująco, to znajdowanie otoczki wypukłej jest dość ciekawym zagadnieniem algorytmicznym. Pokażę jedno podejście, które wykorzystując bardzo proste założenia, przeprowadza nas przez kilka różnych zagadnień związanych z geometrią obliczeniową, rozwijając tym samym postrzeganie, jak można podchodzić do rozwiązywania problemów algorytmicznych.