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ć.

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.

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.

Do tej pory omawiając macierze, zwykle pokazywałem takie o niedużych wymiarach, ładnie wypełnione liczbami. W praktyce algorytmicznej jednak spotykamy się nie dość, że z dużo większymi macierzami, to jeszcze takimi, które mają bardzo dużo zer. Ta ostatnia cecha interesuje nas najbardziej w ramach tego artykułu, bo możemy wtedy mówić o macierzach rzadkich. Zobaczmy, jakie typowe macierze rzadkie możemy wyróżnić i jakie powstały podejścia do ich przechowywania w pamięci.

Po pokazaniu ostatnio, czym są macierze i jak wykonuje się na nich podstawowe operacje, przyszedł czas opowiedzieć o tych związanych z nimi nieco trudniejszych zagadnieniach. Teraz skupię się na obliczaniu wyznacznika macierzy, czyli operacji, która jest bardzo charakterystyczna, ale wbrew pozorom nie aż tak trudna, jak mogłoby się wydawać. Temat poruszę zarówno od strony obliczania na kartce, jak i programowania.

Spośród mnogości zagadnień matematyki akademickiej na zagadnieniach z algebry liniowej znajdziemy jedno, które jest proste, a zarazem bardzo przydatne i szeroko stosowane w informatyce. Są to macierze. W tym artykule przybliżę, czym one są, co z nimi robimy i jakie mają zastosowania, szczególnie w informatyce. Z racji tego, że jest to blog głównie informatyczno-programistyczny, a nie matematyczny, to oprócz suchych opisów jak liczymy macierze ręcznie pokażę je też od strony algorytmicznej — zaprogramujemy je.