# świstak.codes świstak.codes to blog o programowaniu, informatyce i matematyce, który w przystępny sposób łączy solidne podstawy teoretyczne z praktycznymi przykładami kodu i realnymi zastosowaniami w pracy programisty. Autor skupia się na ponadczasowych zagadnieniach, takich jak algorytmy, struktury danych, matematyka w IT czy grafika komputerowa, unikając krótkotrwałych technologicznych mód. ## Listy — najpopularniejsze złożone typy danych https://swistak.codes/post/listy-najpopularniejsze-zlozone-typy-danych Artykuł wyjaśnia pojęcie list jako abstrakcyjnego typu danych: uporządkowany, policzalny zbiór elementów dopuszczający duplikaty. Wyjaśniono różnicę między typami danych i strukturami danych oraz pojęciem abstrakcyjnego typu danych. Omówiono dwie podstawowe implementacje list: tablice (statyczne) — ciąg elementów w pamięci o z góry określonym rozmiarze, umożliwiający szybki dostęp losowy; oraz listy wiązane — elementy rozmieszczone w dowolnych miejscach pamięci powiązane wskaźnikami, zoptymalizowane pod częste wstawianie/usuwanie i sekwencyjny dostęp. Opisano także tablice dynamiczne/wektory (ArrayList, std::vector, List w C#) wykorzystujące przepisanie do większej tablicy przy rozszerzaniu, oraz warianty list wiązanych (jednokierunkowe, dwukierunkowe, cykliczne, z wartownikiem), skip listy i tablice bitowe jako specjalne odmiany. Podano wskazówki, kiedy stosować które rozwiązanie: tablice gdy rozmiar jest przewidywalny, potrzebny jest szybki dostęp losowy i rzadkie modyfikacje; listy wiązane gdy rozmiar jest nieznany, często dodajemy/usuwamy elementy i odczytujemy sekwencyjnie. Zaznaczono, że listy są popularne i proste, ale nie zawsze optymalne — warto dobrać odpowiednią implementację do zastosowania. ## Tablice i listy tablicowe https://swistak.codes/post/tablice-i-listy-tablicowe Artykuł wyjaśnia tablice i oparte na nich listy tablicowe (dynamiczne). Tablice to ciąg elementów w pamięci umożliwiający bezpośredni dostęp przez obliczenie adresu: adres_i = adres_0 + i * rozmiar_elementu. Przykład w C pokazuje odwołania *(array + i) i adresy w pamięci. Listy tablicowe (ArrayList, List, Array, Vector itp.) oferują losowy dostęp w czasie stałym O(1), ale modyfikacje wymagają przesunięć elementów i mogą być kosztowne: wstawianie/usuwanie w środku lub na początku to O(n). Dodawanie na końcu jest zwykle amortyzowane O(1), lecz gdy zabraknie miejsca następuje realokacja i kopiowanie (O(n)). Aby zredukować częstotliwość realokacji stosuje się strategię powiększania z zapasem (np. podwajanie w C#/C++, wzrost o ~50% w Javie), co zwiększa wydajność kosztem niewykorzystanej pamięci. Inne operacje: wstawianie zakresu, odwracanie, konwersja do tablicy, ensureCapacity, trimToSize. Wniosek: listy tablicowe są najpopularniejsze dzięki szybkiemu dostępowi, choć mają kompromisy dotyczące kosztów modyfikacji i wykorzystania pamięci. ## Listy z dowiązaniami https://swistak.codes/post/listy-z-dowiazaniami Artykuł omawia listy wiązane: idea (elementy przechowują wskaźniki do następnych/przednich), typy — lista jednokierunkowa, dwukierunkowa, cykliczna oraz wersja z wartownikiem (sentinel, w praktyce często jedna wartownika w liście cyklicznej wg Cormena). Zwraca uwagę na narzut pamięci wynikający z wskaźników (np. 64‑bitowy wskaźnik = 8 B) oraz brak ciągłości pamięci. Analizuje podstawowe operacje: pobieranie (pierwszy element O(1), dostęp losowy/ostatni bez tail O(n)), wstawianie/usuwanie (po znalezieniu miejsca O(1), ale znalezienie O(n)). Omówione są zalety i wady względem tablic dynamicznych — lepsze przy częstych wstawieniach, gorsze pod względem pamięci i kosztów przeszukiwania; praktyczna rada: zaczynać od tablicy dynamicznej i przełączyć na listę wiązaną dopiero przy rzeczywistych potrzebach optymalizacyjnych. Cytat ostrzegający przed przedwczesną optymalizacją. ## Sztuczna inteligencja — a co to? a komu to potrzebne? https://swistak.codes/post/sztuczna-inteligencja-a-co-to-a-komu-to-potrzebne Artykuł objaśnia, że „sztuczna inteligencja” (SI/AI) stała się wszechobecnym buzzwordem, często nadużywanym w marketingu, co rodzi mity i nieporozumienia. Definiuje SI jako zdolność maszyn do wykonywania zadań wymaganych od istot inteligentnych i wyróżnia kluczowe aspekty: uczenie (zapamiętywanie i generalizacja wzorców), wnioskowanie (wyciąganie konsekwencji z reguł i danych), rozwiązywanie problemów (przeszukiwanie przestrzeni rozwiązań, np. problem komiwojażera), percepcję (analiza „zmysłów”, np. rozpoznawanie twarzy — z wysokim potencjałem i ryzykiem nadużyć) oraz język (NLP i granica między naśladowaniem a „rozumieniem”, powiązana z testem Turinga). Opisane są podejścia top-down (symboliczne) i bottom-up (redukcjonistyczne, sieci neuronowe) oraz rozróżnienie między słabą SI (wyspecjalizowane systemy) a silną SI/AGI (uniwersalna, myśląca maszyna; według części ekspertów możliwa w latach 2040–2050, stan na czerwiec 2020 — nieosiągnięta). Poruszono etyczne i społeczne zagrożenia (utrata prywatności, inwigilacja, utrata pracy, autorytarne zastosowania) oraz paradoks Moraveca: łatwiej osiągnąć u komputerów zdolności wysokopoziomowe niż podstawowe umiejętności percepcyjno-ruchowe. ## Testowanie i wykrywanie sztucznej inteligencji https://swistak.codes/post/testowanie-i-wykrywanie-sztucznej-inteligencji Artykuł omawia klasyczne i współczesne metody rozpoznawania sztucznej inteligencji: test Turinga (imitacja ludzkiej rozmowy, testuje użycie języka, niekoniecznie rozumienie), jego ograniczenia oraz filozoficzny eksperyment chińskiego pokoju Searle’a (różnica między symulacją a rozumieniem). Przedstawione są odmiany Turinga: test Feigenbauma (udawanie eksperta), totalny test Turinga (percepcja i manipulacja), minimum intelligent signal (binarny test wiedzy) oraz test Eberta (syntezatory mowy). Omówiono także odwrotny test Turinga w praktyce (CAPTCHA) i Winograd Schema Challenge jako alternatywę sprawdzającą zdolność rozumienia kontekstu i rozwiązywania anaforycznych niejednoznaczności. W kontekście współczesnych zagrożeń opisano wykrywanie treści generowanych przez SI (deepfake, synteza głosu, fake news), użycie sieci neuronowych i zbiorów danych (np. FaceForensics), konkursy detekcji oraz trudności praktyczne i wyścig zbrojeń między generowaniem a wykrywaniem. Zwrócono uwagę, że testy służą zarówno ocenie SI, jak i mogą być wykorzystywane do ulepszania lub dostrajania systemów tak, by je przechodziły (przykład bota Eugene Goostman). ## 1 0 0 0? 0 1 0 1! 1 0 0 1 – czyli matematyka zero-jedynkowa https://swistak.codes/post/matematyka-zero-jedynkowa Komputery przechowują wszystkie dane w systemie binarnym, używając tylko cyfr 0 i 1. To przykład systemu pozycyjnego: wartość zapisu zależy od cyfr i potęg podstawy b (wartość liczby = suma ai * b^(i-1)), w przypadku binarnego b = 2. Zamiana z binarnego na dziesiętny polega na sumowaniu ai * 2^k, a odwrotna konwersja wykonywana jest przez dzielenie przez 2 i zapisywanie reszt, albo przez odejmowanie kolejnych potęg dwójki. Podstawowe działania arytmetyczne (dodawanie, odejmowanie, mnożenie, dzielenie) działają analogicznie jak w systemie dziesiętnym, a przesunięcia bitowe w lewo/prawo odpowiadają szybkiemu mnożeniu/dzieleniu przez 2^k. Znajomość tych zasad wyjaśnia, jak na najniższym poziomie komputery reprezentują i przetwarzają liczby oraz dane. ## Sposoby zapisywania liczb przez komputery https://swistak.codes/post/sposoby-zapisywania-liczb-przez-komputery Tekst opisuje dwa spojrzenia na to, jak komputery zapisują liczby: fizyczne (jak bity są reprezentowane w świecie rzeczywistym) i logiczne (jak są interpretowane). Fizycznie „0” i „1” to dowolne przeciwstawne stany: wgłębienia na nośnikach optycznych lub kartach perforowanych, obecność/brak ładunku lub różne napięcie w pamięciach elektrycznych, polaryzacja napięcia przy przesyłaniu, namagnesowanie w dyskach HDD itp. Wyjaśniono pojęcia bit i bajt (1 bajt = 8 bitów) oraz zamieszanie z przedrostkami kilo/mega/giga (decimalne vs binarne, propozycje kibi/mibi/gibi). Logicznie liczby mają stałą długość (bajt, słowo procesora), a powszechnym sposobem zapisu liczb całkowitych jest kod uzupełnień do dwóch (U2) — MSB działa jak znak, negacja przez zanegowanie bitów i dodanie 1, zakres dla n bitów: −2^(n−1) do 2^(n−1)−1. Wspomniano też inne kody: uzupełnień do jedności, znak-moduł, przesunięciowy (bias), BCD i kod Graya. Na końcu omówiono końcówkowość bajtów (endianness): big-endian vs little-endian, przy czym popularne procesory x86 używają little-endian, a ARM zwykle wspiera oba, zwykle little-endian. ## Liczby wymierne i rzeczywiste w zero-jedynkowym świecie https://swistak.codes/post/liczby-wymierne-i-rzeczywiste-w-zero-jedynkowym-swiecie Artykuł wyjaśnia, jak komputery przechowują liczby wymierne i rzeczywiste dwoma podejściami: stałoprzecinkowym (fixed‑point, kod Qm.n) i zmiennoprzecinkowym (floating‑point, np. IEEE‑754). W zapisie Qm.n część bitów jest traktowana jako część całkowita (m) a część ułamkowa (n); zakres wartości jest rzędu −2^{m−1}..2^{m−1}−2^{−n}, a dokładność = 2^{−n}. Format ten jest prosty, nie jest natywnie wspierany przez procesory (stosowany historycznie tam, gdzie brak FPU, np. Doom używał Q16.16) i w zastosowaniach wymagających precyzji finansowej często stosuje się BCD. Liczby zmiennoprzecinkowe opisuje postać wykładnicza: znak, mantysa i wykładnik, przy czym mantysa jest normalizowana (np. w systemie dziesiętnym M∈[1,10)) i zaokrąglana do dostępnej liczby cyfr. Standard IEEE‑754 określa binarny format i reguły zaokrąglania: pojedynczy (32 bity: 1 bit znak, 8 bitów wykładnik, 23 bity mantysa, bias=127) i podwójny (64 bity: 1, 11, 52, bias=1023), z wartościami specjalnymi NaN, +/−0 i +/−∞. Wartość reprezentacji podaje wzór x = (−1)^S · M · 2^{E−bias}; standard jest powszechnie stosowany i sprzętowo wspierany, co umożliwia szybkie obliczenia (również na GPU). ## Nie-liczby jako liczby, czyli zapis danych cyfrowych https://swistak.codes/post/nie-liczby-jako-liczby-czyli-zapis-danych-cyfrowych Artykuł tłumaczy, że wszystkie dane w komputerze to liczby zapisane według określonego kodowania. Omówiono kodowanie znaków: ASCII (7‑bitowe, 128 znaków, znaki sterujące 0–31, spacja 32, cyfry 48–57, duże litery 65–90, małe 97–122; różnice CR/LF między systemami) i jego ograniczenia, rozwój ISO‑8859 oraz powstanie Unicode (1988) z popularnymi formami UTF‑8 i UTF‑16 — zgodność z ASCII, zmienna długość kodów i przykład (U+20AC). Opisano też reprezentację obrazów (bitmapa: paleta lub RGB 24‑bit; Full HD bez kompresji ok. 6 MB; JPEG jako kompresja) oraz dźwięku (PCM: częstotliwość próbkowania i rozdzielczość; CD: 44 kHz, 16 bitów → ~86 kB/s na kanał; stereo i wielokanałowość zwiększają rozmiar; MP3 jako kompresja). Wniosek: zapis czegokolwiek sprowadza się do ustalenia sposobu kodowania informacji liczbowo. ## Systemy liczbowe — uzupełnienie https://swistak.codes/post/systemy-liczbowe-uzupelnienie Artykuł omawia różne systemy liczbowe poza binarnym i dziesiętnym: definicję systemów (addytywne vs. pozycyjne) i ogólną zasadę zapisu pozycyjnego jako sumy cyfr razy potęgi podstawy. Opisano systemy addytywne (np. jedynkowy i rzymski — używany historycznie i współcześnie do oznaczeń) oraz wybrane systemy pozycyjne: heksadecymalny (podst.16, szeroko stosowany w informatyce, prosty konwersji do/z binarnego po 4 bity), negabinarny (podst. −2, cyfry 0/1 — zapisuje liczby ujemne bez znaku), czwórkowy (podst.4 — konwersja po 2 bity, związek z kodem DNA i zastosowaniami w transmisji sygnału), oktalny (podst.8 — historyczne użycie w mainframe’ach, konwersja po 3 bity), Base64 (kodowanie 6-bitowe do przesyłania binarnych danych jako ASCII) oraz dwunastkowy i sześćdziesiątkowy (historyczne i praktyczne aspekty: dwunastkowy — lepsze ułamki i historyczne jednostki, sześćdziesiątkowy — źródło podziału czasu i kątów). Tekst łączy właściwości matematyczne z praktycznymi zastosowaniami i historycznym kontekstem. ## Przetwarzanie plików w praktyce — obrazy BMP https://swistak.codes/post/przetwarzanie-plikow-w-praktyce-obrazy-bmp Artykuł opisuje, jak napisać prosty parser plików BMP na przykładzie JavaScript (szablon na CodeSandbox/GitHub). Wyjaśnia korzyści z implementacji (czytanie dokumentacji, ćwiczenie algorytmiki i umiejętności programistycznych) oraz podstawowe pojęcia: piksel, przestrzeń barw (RGB), paleta, płótno, parser. Dla uproszczenia autor zakłada: pliki zaczynają się od sygnatury "BM", używają nagłówka BITMAPINFOHEADER, są nieskompresowane i 24-bitowe. Kluczowe metadane do odczytu: sygnatura (0x00, 2B), offset danych (0x0A, 4B), szerokość (0x12, 4B), wysokość (0x16, 4B), bity/piksel (0x1C, 2B) i typ kompresji (0x1E, 4B). Liczby są little-endian; piksele zapisane są w kolejności B,G,R; obraz jest przechowywany od dołu ku górze; każdy wiersz jest wyrównany do wielokrotności 4 bajtów. Kroki implementacji: wczytać plik do tablicy bajtów, przygotować płótno i funkcję putPixel, sprawdzić sygnaturę, odczytać wartości little-endian (przesunięcia bitowe i OR), obliczyć rozmiar wiersza z paddingiem, iterować wierszami od dołu i po 3 bajty czytać B,G,R i rysować piksel. Autor podaje przykładowy kod JS i omawia skutki pominięcia walidacji (zniekształcenia), a także propozycje rozszerzeń: refaktoryzacja, obsługa 32/16/8-bitów i palety, optymalizacja zapisu do ImageBuffer oraz obsługa kompresji RLE. ## Tekstowy zapis danych cyfrowych https://swistak.codes/post/tekstowy-zapis-danych-cyfrowych Artykuł opisuje przechowywanie danych w formie tekstowej i porównuje je z zapisem binarnym. Format tekstowy używa widzialnych znaków (ASCII/Unicode), jest czytelny i edytowalny zwykłym edytorem oraz łatwiejszy do przetwarzania, natomiast format binarny traktuje bajty jako wartości 0–255, jest bardziej zwarty (przykład: 16 B binarnie vs 107 B tekstowo) i trudniejszy do analizy bez dokumentacji. Jako uniwersalne standardy tekstowe omówiono XML (znaczniki, atrybuty, struktura drzewiasta, XPath; zastosowania: SVG, Office Open XML, OpenDocument, RSS, EPUB, XHTML) oraz JSON (typy: number, string, boolean, array, object, null; szerokie użycie w komunikacji sieć-serwer i plikach konfiguracyjnych). Wspomniano też alternatywy i uzupełnienia: YAML, TOML, Protocol Buffers, SGML. Dodatkowo opisano specyficzne tekstowe formaty aplikacyjne, np. RTF, TeX/LaTeX, OBJ i tekstowe/binarne STL. W podsumowaniu zaznaczono kompromis: czytelność i prostota przetwarzania kontra większy rozmiar danych oraz wybór między użyciem standardów a własnymi rozwiązaniami zależnie od potrzeb. ## Wyszukiwanie w listach https://swistak.codes/post/wyszukiwanie-w-listach Artykuł omawia podstawowe algorytmy wyszukiwania w listach: liniowe, binarne i interpolacyjne, kontynuując wcześniejszą serię o strukturach listowych. Wyszukiwanie liniowe przegląda elementy kolejno, ma złożoność O(n) i działa dla dowolnego ułożenia danych. Wyszukiwanie binarne wykorzystuje strategię "dziel i zwyciężaj", wymaga posortowanej kolekcji i dostępu losowego (np. tablice, nie listy wiązane), ma złożoność O(log n), jest dostępne w wielu bibliotekach języków (np. BinarySearch/arrays.binarySearch), ale wymaga ostrożnej implementacji (unikać przepełnienia przy obliczaniu środka — użyć L + (R - L) / 2). Wyszukiwanie interpolacyjne szacuje pozycję przez interpolację liniową i może osiągać średnio O(log log n) dla rozkładu jednostajnego, ale w najgorszym przypadku degraduje do O(n); eksperymenty pokazują doskonałe wyniki dla ciągów arytmetycznych i rozkładu jednostajnego, a gorsze dla ciągów geometrycznych i niektórych rozkładów losowych (np. Gauss). Artykuł zawiera też praktyczne uwagi (np. git-bisect jako przykład binarnego przeszukiwania), odniesienia literaturowe i link do repozytorium z kodem testów. ## Sortowanie, cz. 1 — wprowadzenie teoretyczne https://swistak.codes/post/sortowanie-cz-1-wprowadzenie-teoretyczne Wprowadzenie do teorii sortowania: definicja jako permutacja elementów tak, by spełniony był warunek porządku względem funkcji porządkującej (komparator/klucz). Omówiono podstawowe pojęcia: funkcja porządkująca (jak porównywane są elementy) i stabilność algorytmu (czy równe elementy zachowują oryginalną kolejność). Wymieniono najpopularniejsze algorytmy: bubble sort, insertion sort, quick sort i merge sort, oraz wzmiankę o licznych innych i o funkcjach sortujących w bibliotekach standardowych. Zwrócono uwagę na wpływ struktury danych na wybór metody (tablice — losowy dostęp i tanie zamiany; listy wiązane — kosztowny dostęp i wstawianie) oraz ograniczenia porównywania (porównujemy po dwa elementy). Tekst koncentruje się na mechanizmach i sensie sortowania; szczegóły implementacyjne mają być omówione w kolejnych artykułach. ## Sortowanie, cz. 2 — sortowanie bąbelkowe https://swistak.codes/post/sortowanie-cz-2-sortowanie-babelkowe Artykuł opisuje sortowanie bąbelkowe (swap-based, bubble sort) i jego optymalizacje oraz udostępnia kod do wizualizacji w repozytorium GitHub (JS). Wyjaśniono podstawową ideę: porównywanie sąsiednich elementów i zamiany, co w najprostszej formie prowadzi do O(n^2) porównań (n(n−1)). Przedstawiono trzy poprawki: 1) skracanie zakresu porównań o jeden po każdej iteracji (klasyczna wersja podręcznikowa), 2) wczesne przerwanie, gdy w przebiegu nie dokonano żadnej zamiany, oraz 3) sortowanie koktajlowe (shaker sort) — dwukierunkowe przejścia skracające zakresy z obu stron. Omówiono też sortowanie grzebieniowe (comb sort, Dobosiewicz) — porównania z odstępem malejącym co iterację (współczynnik ~1.3), które łagodzi problem „żółwi i zajęcy”. Mimo optymalizacji złożoność praktyczna pozostaje bliska O(n^2), więc algorytmy te mają głównie wartość edukacyjną. Stabilność: bubble i cocktail są stabilne, comb sort — niestabilny. Literatura źródłowa wymieniona. ## Sortowanie, cz. 3 — sortowanie przez wstawianie https://swistak.codes/post/sortowanie-cz-3-sortowanie-przez-wstawianie Artykuł omawia sortowania oparte na wstawianiu: podstawowy algorytm sortowania przez wstawianie (insert sort) oraz jego warianty optymalizujące, przede wszystkim sortowanie Shella. Wyjaśniono koszt wstawiania w tablicach (przesunięcia/zamiany) vs. darmowe wstawianie w strukturach takich jak listy wiązane, oraz dwa podejścia pamięciowe: tworzenie dodatkowej tablicy (O(n) pamięci) lub sortowanie in-place z O(1) pamięci. Insert sort: prosty, stabilny, online, typowo O(n^2) czasowo (praktycznie wydajniejszy niż bubble sort). Shell sort (Donald Shell, 1959) stosuje malejące odstępy (gapy), wykonując wstawianie co gap; dobór ciągu odstępów ma kluczowy wpływ na wydajność — przykłady: Shell (⌊N/2^k⌋), Knuth, Sedgewick, oraz doświadczalnie najlepszy ciąg Ciury (1,4,10,23,57,123,301,701). Złożoność Shella zależy od ciągu: od O(n^2) do około O(n log^2 n) w najlepszych analizach, z najlepszym przypadkiem często O(n log n); Shell sort jest niestabilny. Repozytorium z kodem i wizualizacjami na GitHubie: https://github.com/swistak-codes/sorting-algorithms. Literatura: Knuth, Harris & Ross, Wirth, Ciura. ## Sortowanie, cz. 4 — sortowanie przez wybieranie https://swistak.codes/post/sortowanie-cz-4-sortowanie-przez-wybieranie Artykuł opisuje sortowanie przez wybieranie oraz szybszą wariantę z użyciem kopca (heapsort). Najpierw przypomniano proste wyszukiwanie minimum/maksimum liniowo, które jest podstawą algorytmu selection sort: iteracyjnie wyodrębnia się część posortowaną, w nieposortowanej szuka się najmniejszego elementu i zamienia z pierwszym nieposortowanym. Selection sort ma złożoność O(n^2) porównań, ale bardzo małą liczbę zamian, ponieważ elementy trafiają od razu na swoje miejsce. Aby przyspieszyć wyszukiwanie ekstremów w nieposortowanej części, wprowadzono strukturę kopca binarnego — drzewo reprezentowane w tablicy, gdzie rodzic jest większy (max-heap) lub mniejszy (min-heap) od dzieci; indeksy: dzieci 2i, 2i+1, rodzic ⌊i/2⌋. Omówiono operację naprawy kopca (heapify) i budowanie kopca przez kolejne naprawianie poddrzew. Heapsort polega na zbudowaniu kopca z całej tablicy, zamianie korzenia z ostatnim elementem, skróceniu obszaru i ponownym heapify; daje złożoność O(n log n) (najgorszy i przeciętny przypadek), kosztem większej liczby zamian niż selection sort. Oba algorytmy są niestabilne, choć selection sort można uczynić stabilnym przez wstawianie zamiast zamiany (większe koszty zapisu). Kod i wizualizacje użyte w artykule są dostępne na GitHub: https://github.com/swistak-codes/sorting-algorithms. Literatura klasyczna: Knuth, Cormen i inni. ## Sortowanie, cz. 5 — „dziel i zwyciężaj” https://swistak.codes/post/sortowanie-cz-5-dziel-i-zwyciezaj Artykuł omawia algorytmy sortowania oparte na metodzie „dziel i zwyciężaj”, koncentrując się na quicksort i merge sort. Quicksort: dzielenie przez partycjonowanie względem piwota (zamiany w miejscu), rekurencyjne sortowanie podtablic, średnia złożoność O(n log n), najgorszy przypadek O(n^2), małe wymagania pamięciowe, niestabilny; wydajność zależy od wyboru piwota (optymalizacje: różne schematy partycjonowania, wielopiwotowe). Merge sort: dzielenie na jednoelementowe podtablice i scalanie (merge) poprzez porównania do nowej tablicy, stabilny, gwarantowane O(n log n) także w najgorszym przypadku, ale wymaga dodatkowej pamięci; wersje top-down i bottom-up, optymalizacje: naturalny merge sort, użycie list wiązanych, hybrydyzacja z insertion sort (np. TimSort), cache-aware warianty. Omówiono rolę rekurencji i możliwości implementacyjne (wersje bez rekursji, równoległe), porównanie właściwości obu algorytmów oraz praktyczne zastosowania (np. dwupiwotowy quicksort i TimSort w Javie). ## Sortowanie, cz. 6 — teraz bez porównywania! https://swistak.codes/post/sortowanie-cz-6-teraz-bez-porownywania Artykuł omawia sortowanie bez porównań — counting sort i radix sort — oraz ich ograniczenia i wydajność. Counting sort działa dla liczb naturalnych w zakresie 0..k: zlicza wystąpienia, przekształca je w wskaźniki pozycji i tworzy posortowaną tablicę; ma złożoność O(n + k) i jest stabilny, lecz wymaga dużej pamięci gdy k jest duże. Radix sort to modyfikacja korzystająca wielokrotnie z counting sort na kolejnych pozycjach cyfr/bitów; dla słów w-bitowych dzielimy je na p = w/d przebiegów, gdzie pomocnicza tablica ma rozmiar 2^d, a wydajność zależy od wyboru d (mniej przebiegów ↔ większa tablica). Obie metody redukują liczbę porównań, ale nadal obciążają pamięć i wykonywanie zapisów/odczytów; są stabilne i ograniczone głównie do liczb (radix można rozszerzyć na floats). Dodatkowo krótko omówiono optymalne minimalne drzewa porównań dla małych n (np. 2 i 3 elementy) oraz podano odniesienia literaturowe. ## Sortowanie, cz. 7 — inne podejścia https://swistak.codes/post/sortowanie-cz-7-inne-podejscia Artykuł opisuje trzy mniej popularne algorytmy sortowania: odd-even (odd–even transposition sort), gnome sort oraz sortowanie drzewiaste. Odd-even to odmiana sortowania przez zamianę bazująca na bubble sort — wykonuje naprzemienne przejścia po parach na nieparzystych i parzystych pozycjach; ma złożoność O(n^2) i niewielkie praktyczne zastosowania (zauważa się jednak powiązanie z wydajniejszym, równoległym Batcher's odd–even mergesortem). Gnome sort (pierwotnie „stupid sort”) miesza idee bubble i insertion sort: przesuwa się do przodu, przy błędnej parze zamienia i cofa się aż element znajdzie miejsce; też O(n^2) i traktowany głównie jako ciekawostka. Sortowanie drzewiaste buduje binarne drzewo poszukiwań (BST) przez wstawianie elementów, potem odczytuje wyniki przez przejście in-order; daje średnio O(n log n) (ale O(n^2) w najgorszym przypadku dla niezrównoważonego drzewa) i wymaga dodatkowej pamięci na węzły. Wskazano wady BST (może degenerować do listy) oraz możliwości poprawy przez drzewa zrównoważone (AVL, red–black, splay — splaysort). Podsumowanie: dwa pierwsze algorytmy to głównie ciekawostki edukacyjne, natomiast sortowanie drzewiaste bywa praktyczne, chociaż koszt pamięciowy i ryzyko niezrównoważenia ograniczają jego zastosowania. ## Rekurencja — co to jest? https://swistak.codes/post/rekurencja-co-to-jest Rekurencja to technika definiowania funkcji (lub typów danych) przez odwołanie do samej siebie, wymagająca warunku brzegowego, by uniknąć nieskończonego zapętlenia. Przykłady matematyczne: ciąg Fibonacciego (fib(n)=fib(n-1)+fib(n-2) z fib(0)=0,fib(1)=1) oraz silnia (n!=(n-1)!·n z 0!=1), które dają się bezpośrednio przenieść na kod (przykłady w C i F#). Rekurencja w programowaniu ułatwia wyrażanie algorytmów i jest podstawą pętli w paradygmacie funkcyjnym, ale obciąża pamięć przez tworzenie call stack (ryzyko stack overflow, złożoność pamięciowa O(n)). Rekurencja ogonowa (tail recursion) używa akumulatorów i pozwala wyeliminować odkładanie wywołań na stos, osiągając O(1) pamięci przy wsparciu kompilatora/interpretera; jednak przekształcenie algorytmów do postaci ogonowej bywa nieintuicyjne, a wsparcie dla TCO nie jest uniwersalne (np. Python). Zastosowania: algorytmy dziel i zwyciężaj (quicksort, mergesort), funkcja Ackermanna (test optymalizacji rekurencji), rysowanie fraktali (np. trójkąt/dywan Sierpińskiego, krzywe Hilberta), oraz definiowanie rekurencyjnych struktur danych (drzewa, listy wiązane). Dalsze kroki: teoria rekursji i obliczeń, konwersje rekurencji na iterację oraz wzory zamykające (np. wzór Bineta dla Fibonacciego). ## Derekursywacja https://swistak.codes/post/derekursywacja Artykuł opisuje derekursywację — techniki usuwania rekurencji — oraz kiedy warto je stosować. Motywacja: rekurencja jest czytelna i matematycznie naturalna, ale niesie koszty stosu wywołań i może generować znacznie cięższy kod maszynowy; wersje ogonowe i iteracyjne są zwykle wydajniejsze. Główne sposoby derekursywacji przedstawione w tekście: - Usunięcie rekurencji ogonowej przez proste przepisanie na pętlę (while/for), przenosząc dodatkowe argumenty do zmiennych lokalnych i ewentualnie odwracając warunki. - Symulowanie rekurencji za pomocą struktur kolejkowych: LIFO (stos) i FIFO (kolejka). Rekurencję można odwzorować ręcznie utrzymując stos „adresów przypadków”, argumentów i akumulatorów — przykład pełnej derekursywacji funkcji silnia w C. - Derekursywacja matematyczna: przejście od wzoru rekurencyjnego do wzoru jawnego przy użyciu funkcji tworzących dla liniowych rekurencji o stałych współczynnikach. Pokazano wyprowadzenie funkcji tworzącej i wzoru Bineta dla ciągu Fibonacciego (złota liczba, miejsca zerowe wielomianu, rozkład na ułamki proste). Autor porównuje wydajność wielu implementacji Fibonacciego: rekurencyjna, ogonowa, iteracyjna, symulowana stosem, ze wzoru Bineta i z zapamiętywaniem (memoizacja). Eksperyment (C, pomiary CPU, n od 0 do 40, 10 powtórzeń, wyniki w ns) wykazał, że ręczna symulacja stosu miała najgorsze czasy (szybki wzrost wykładniczy), zwykła rekurencja też rośnie wykładniczo, natomiast wersje ogonowe i iteracyjne są na zbliżonym, dobrym poziomie. Wzór Bineta jest nieco wolniejszy z powodu kosztów operacji zmiennoprzecinkowych; memoizacja nie daje wielkiej przewagi przy prostych obliczeniach z powodu kosztów pamięci/cache. Wnioski: derekursywacja bywa opłacalna (redukcja kosztów stosu, poprawa wydajności), szczególnie przez usunięcie rekurencji ogonowej lub napisanie algorytmu iteracyjnie. Symulacja stosu może być przydatna jako baza do optymalizacji, ale zwykle jest mniej wydajna. Metody matematyczne dają eleganckie wzory jawne, lecz mają ograniczone zastosowanie. Ostateczny wybór zależy od czytelności, ograniczeń języka/kompilatora i charakteru problemu. Literatura i linki do przykładów kodu (OnlineGDB) są dołączone. ## Jak komputer rysuje linie? https://swistak.codes/post/jak-komputer-rysuje-linie Artykuł wyjaśnia, jak komputer rysuje linie na rastrowym ekranie: od pojęć podstawowych (piksel, bufor ramki, karta graficzna) przez problem reprezentacji matematycznej odcinka na siatce pikseli (zaokrąglanie, wybór punktów) po kolejne algorytmy rysowania. Pokazane są podejścia: bezpośrednie użycie y = ax + b z iteracją po x lub y, wersja inkrementalna (przyrost y o a lub x o 1/a) z akumulatorem błędu, oraz klasyczny algorytm Bresenhama (midpoint/incremental error), który dzięki postaci uwikłanej funkcji i podwojeniu wartości eliminuje dzielenie i operacje zmiennoprzecinkowe, używając tylko dodawania/odejmowania i decyzji D, incrE, incrNE. Omówiono też ograniczenia (obsługa 8 oktantów, przypadki pionowe/poziome), potrzebę antyaliasingu dla wygładzenia (np. Xiaolin Wu, Gupta–Sproull) oraz historyczne konteksty (tryb 13h w DOS, Atari 2600). Ćwiczeniowe implementacje w TypeScript/Svelte i pełne kody są dostępne na GitHubie; literatura i źródła (Foley i in., Bresenham, DDA, artykuły online) są podane jako odniesienia. ## Jak komputer rysuje okręgi? https://swistak.codes/post/jak-komputer-rysuje-okregi Artykuł omawia algorytmikę rysowania okręgów na pikselowej siatce: od prostego wykorzystania równania okręgu (x−a)^2+(y−b)^2=R^2 i iteracji po x z użyciem y = sqrt(R^2−x^2) (unikając kosztownych funkcji trygonometrycznych), przez wykorzystanie symetrii okręgu do jednoczesnego rysowania ośmiu punktów, aż po efektywny algorytm punktu środkowego autorstwa J. E. Bresenhama. Pokazane są trzy wersje algorytmu punktu środkowego: zmiennoprzecinkowa (z d = 5/4 − R), całkowitoliczbowa (d = 1 − R) oraz w pełni przyrostowa wersja całkowitoliczbowa, która eliminuje operacje kosztowne i redukuje obliczenia do prostych dodawań przy użyciu przyrostów ΔE i ΔSE. Omówiono także warunki optymalizacji (np. rysowanie 4 zamiast 8 punktów przy x=y lub przy współrzędnej równej 0) oraz praktyczne implementacje w TypeScript/Svelte dostępne w repozytorium autora. Artykuł podkreśla, że techniki używane do rysowania linii można adaptować do rysowania okręgów, a matematyczne podejście pozwala znacząco usprawnić algorytmy. Literatura: fragment z Foley i in., „Konwersja okręgów”. ## Algorytmy-żarty, czyli o sortowaniu cz. 9 https://swistak.codes/post/algorytmy-zarty-czyli-o-sortowaniu-cz-9 Artykuł opisuje „żartobliwe” algorytmy sortowania, które nie nadają się do praktycznych zastosowań: losowe podejścia (bozosort: losowa zamiana dwóch elementów; bogosort: ciągłe tasowanie tablicy przy użyciu Fishera–Yatesa) z szansą trafienia posortowanej permutacji 1/n! (np. 1/4!, 1/10!, 1/100!); ekstremalny bogobogosort (rekurencyjne tasowanie) o astronomicznie dużej, dyskutowanej złożoności; deterministyczny, ale niepraktyczny stooge sort (sortowanie głupie) o złożoności wyższej niż O(n^2); oraz sleep sort — nieporównawczy algorytm zakładający tworzenie wątków usypianych na czas równy wartości elementu (pochodzący z 2011 z 4chana), podatny na problemy z precyzją i harmonogramowaniem wątków. Autor zaznacza, że prezentowane algorytmy to ciekawostki (kod dostępny na GitHub), a informatycy tworzą też inne żartobliwe byty jak ezoteryczne języki programowania (Brainfuck, Piet, Malbolge). ## Algorytmika gier — saper https://swistak.codes/post/algorytmika-gier-saper Artykuł opisuje krok po kroku stworzenie prostego klonu gry Saper (implementacja w JavaScript/React, logika oddzielona w src/logic) w celu zrozumienia algorytmiki stojącej za grą. Wyjaśnione są zasady: siatka pól, kliknięcie odkrywa pole lub kończy grę przy trafieniu miny, odkryte pole pokazuje liczbę sąsiadujących min, a pola z wartością 0 uruchamiają automatyczne odsłanianie sąsiadów (flood‑fill). Architektura opiera się na dwóch tablicach 2D: plansza z zawartością pól (miny jako "X" i liczby 0..8) oraz tablica widocznego stanu (np. null = nieodsłonięte). Główne funkcje: generowanie planszy (losowe rozstawienie min + obliczenie sąsiedztw), odsłanianie pól (rekurencyjne wypełnianie zer) oraz sprawdzanie wygranej/przegranej (iteracja po tablicach). Omówiono też szczególne przypadki przy generowaniu (miny niemożliwe do odgadnięcia) i sposoby zapobiegania im (dodatkowe warunki przy losowaniu), oraz sugerowane ulepszenia: generowanie planszy po pierwszym kliknięciu, oznaczanie min (flagowanie), licznik czasu, wybór rozmiaru planszy i inne usprawnienia rozgrywki. ## Komputer w komputerze, czyli emulacja, wirtualizacja i konteneryzacja https://swistak.codes/post/komputer-w-komputerze-czyli-emulacja-wirtualizacja-i-konteneryzacja Artykuł opisuje trzy techniki uruchamiania „komputera w komputerze”: emulację, wirtualizację i konteneryzację, ich zasady działania, zastosowania oraz wady i zalety. Emulacja programowo odwzorowuje sprzęt/API (moduły: CPU, pamięć, I/O) — przykłady: DOSBox, emulatory konsol, terminale — pozwala uruchamiać oprogramowanie/architektury różne od hosta, lecz bywa powolna i nie zawsze wierna. Wirtualizacja tworzy maszyny wirtualne zarządzane przez hipernadzorcę (hypervisor); wyróżnia się typ 1 (bare metal) i typ 2 (hosted). Kluczowe pojęcia to kryteria Popeka–Goldberga (wydajność, kontrola zasobów, ekwiwalencja) oraz pełna wirtualizacja realizowana przez translację binarną lub wsparcie sprzętowe (Intel VT-x/AMD‑V). Przykłady: VMware, VirtualBox, Hyper‑V, ESXi. Zaleta: uruchamianie różnych systemów z dobrą wydajnością (szczególnie typ 1); wada: potrzeba odpowiedniego sprzętu i ograniczenie architekturą. Konteneryzacja (OS‑level virtualization) udostępnia jądro hosta i izoluje procesy (Docker, LXC, Singularity, OpenVZ), oferując niskie narzuty i szybkość, ale działa tylko w tej samej architekturze/systemie (na macOS/Windows Docker używa VM). Zastosowania wszystkich technik: kompatybilność, testy, konsolidacja serwerów, izolacja (np. analiza malware), tworzenie odtwarzalnych środowisk. ## Jak komputer zapisuje dźwięk? https://swistak.codes/post/jak-komputer-zapisuje-dzwiek Artykuł wyjaśnia, jak komputer zapisuje dźwięk: rozróżnia zapis wierny (analogowy sygnał z mikrofonu, zapisany cyfrowo przez próbkowanie i kwantyzację) oraz zapis notacji muzycznej (MIDI). Dźwięk to fale akustyczne rozchodzące się w ośrodkach sprężystych; ludzkie ucho słyszy ok. 16 Hz–20 kHz. Przetworniki (mikrofony) zamieniają drgania na sygnał elektryczny, a ADC konwertuje go na cyfrowy za pomocą PCM/LPCM — parametry kluczowe to częstotliwość próbkowania (liczba próbek/s) i rozdzielczość bitowa (liczba bitów na próbkę). Częstotliwość Nyquista = 1/2 częstotliwości próbkowania determinuje maksymalne odwzorowane pasmo; wpływ kwantyzacji opisuje SQNR ≈ 6,02·Q dB. Rozmiar nieskompresowanego nagrania (PCM) zależy od: częstotliwości próbkowania · czasu · rozdzielczości · liczby kanałów. Pliki WAV/AIFF/AU przechowują PCM (bezstratnie); alternatywy to bezstratne FLAC/ALAC oraz stratne MP3/OGG/AAC wykorzystujące modele psychoakustyczne i MDCT — jakość tu mierzy bitrate. Istnieją też odmiany PCM (DPCM, ADPCM, PCMU/PCMA) i inny sposób PDM/DSD (1-bit, bardzo wysokie fs, np. SACD). ## Przekształcenia grafiki 2D — matematyczny punkt widzenia https://swistak.codes/post/przeksztalcenia-grafiki-2d Artykuł opisuje matematykę przekształceń grafiki 2D: podstawowe operacje (translacja, skalowanie, obrót, odbicie, pochylenie) zapisane jako działania na wektorach i macierzach. Przekształcenia afiniczne wyraża się jako P' = A·P + T, a użycie współrzędnych jednorodnych (wektor 3D z w ≠ 0) pozwala scalić translacje i obroty w jedną macierz 3×3, z pełną macierzą 3×3 opisującą także przekształcenia perspektywiczne (homografie). Pokazane są standardowe macierze: translacji, skalowania i obrotu (oraz sposób złożenia transformacji przez mnożenie macierzy i przykład obrotu wokół punktu P1 jako T(x1,y1)·R(θ)·T(−x1,−y1)). Dla grafiki rastrowej konieczne jest stosowanie odwrotnego mapowania (użycie macierzy odwrotnej) i interpolacji kolorów; omówione metody interpolacji to najbliższy sąsiad, dwuliniowa, dwusześcienna i Lanczosa, z krótkim opisem algorytmu dwuliniowego (wagowana interpolacja w poziomie i pionie). Na końcu wymieniono praktyczne implementacje i API (CSS matrix(a,b,c,d,tx,ty), CanvasRenderingContext2D.transform, Java AffineTransform, .NET MatrixTransform, biblioteki typu Cairo, ImageMagick, oraz narzędzia graficzne jak GIMP). Literatura: Foley i inni oraz Klawonn. ## Przekształcenia grafiki 3D https://swistak.codes/post/przeksztalcenia-grafiki-3d Artykuł omawia przekształcenia grafiki 3D za pomocą macierzy jednorodnych (punkty 4-wymiarowe, macierz 4×4) oraz alternatywnie kwaternionów. Opisano translacje i skalowania w postaci macierzy 4×4, oraz macierze obrotów wokół osi Z, X i Y (i uproszczone 3×3 dla samych rotacji). Poruszono problem orientacji układu współrzędnych (lewo-/prawoskrętny) i sposób konwersji między nimi. Wyjaśniono kąty RPY (roll, pitch, yaw) i zjawisko gimbal lock na przykładzie złożenia obrotów, wskazując utratę stopnia swobody i zależność od kolejności mnożenia macierzy. Przedstawiono rzutowania: ortograficzne (macierz M_ort) i perspektywiczne (M_per z parametrem odległości d). Jako alternatywę dla macierzy omówiono kwaterniony (H) — ich postać, użycie do reprezentacji obrotów, przeliczanie kwaternionu na macierz rotacji oraz zaletę w postaci odporności na gimbal lock i prostszego składania rotacji przez mnożenie. Na koniec podano przykłady implementacji w CSS (matrix3d), bibliotekach graficznych (GLM/OpenGL, WebGL), silnikach (Unity, Three.js, Source) i Blenderze oraz źródła literaturowe. ## Jak komputer mierzy czas? https://swistak.codes/post/jak-komputer-mierzy-czas Artykuł wyjaśnia, skąd komputer „wie” godzinę, rozdzielając pomiar czasu (sprzęt) od jego przechowywania i przetwarzania (oprogramowanie). Sprzętowo czas mierzą: RTC (Real‑Time Clock) na płycie głównej oparty na rezonatorze kwarcowym 32 768 Hz i zasilany baterią — służy do odmierzania czasu kalendarzowego; PIT (Programmable Interval Timer, np. Intel 8253/8254) z rezonatorem ~1,19 MHz i trzema licznikami, historycznie używany do przerwań i prostych zadań; TSC (Time Stamp Counter) — 64‑bitowy licznik w procesorze dostępny przez instrukcję RDTSC, dawniej inkrementowany co cykl; oraz HPET (High Precision Event Timer) — niezależny, wysokorozdzielczy licznik (>=10 MHz) zaprojektowany do synchronizacji multimediów. Autor radzi: do pomiarów wysokiej rozdzielczości używać funkcji systemowych (np. clock_gettime), a nie bezpośrednio liczników sprzętowych. Data jest przechowywana w nieulotnej pamięci BIOS/CMOS (ok. 256 B), która zawiera też ustawienia BIOS; rejestry RTC: 0x00 sekundy, 0x02 minuty, 0x04 godziny, 0x06 dzień tygodnia, 0x07 dzień miesiąca, 0x08 miesiąc, 0x09 rok, 0x32 wiek (stulecie). Na koniec — gdy zegar „się rozjeżdża”, często rozwiązaniem jest wymiana baterii RTC. ## Jak komputer przechowuje datę i skąd zna aktualną? https://swistak.codes/post/jak-komputer-przechowuje-date-i-skad-zna-aktualna Artykuł wyjaśnia, jak oprogramowanie przechowuje i uzyskuje datę: kluczowe pojęcia to epoka (epoch) — punkt startowy liczenia czasu przyjęty przez różne systemy (np. 1601 dla Windows NT, 1900 dla Excel/Lotus, 1.01.1970 dla Unix/POSIX, 6.01.1980 dla GPS) — oraz popularny czas uniksowy (Unix Time) liczony zwykle jako sekundy od 1.01.1970, często zapisywany jako 32-bitowe signed int (stąd problem 19.01.2038). Omówione są też formaty tekstowe (ISO 8601 / RFC 3339) i dokładniejsze reprezentacje (ms/µs/ns). Źródła aktualnego czasu to sieciowe serwery NTP (stratum, 64-bitowy format czasu od 1900), precyzyjny PTP (IEEE 1588) oraz zegary atomowe, satelity GPS/GLONASS/Beidou/Galileo i nadajniki naziemne (np. DCF77, RDS, BTS). Artykuł opisuje historyczne i przyszłe „apokalipsy czasowe” (Y2K, GPS week rollovers, NTP/Unix/plików systemowych przepełnienia: 2038, 2036, 2040, 2107, dalsze limity dla FAT, HFS+, Java, Windows) oraz typowe błędy związane z latami przestępnymi. Wnioski: problematyka czasu jest złożona — nie wynajduj własnych rozwiązań; korzystaj z bibliotek i funkcji systemowych, by uniknąć pułapek związanych z formatami, zakresami i synchronizacją. ## Dlaczego mierzenie i przetwarzanie czasu jest trudne? — część 1 z 2 https://swistak.codes/post/dlaczego-mierzenie-i-przetwarzanie-czasu-jest-trudne-czesc-1 Zagadnienia dat i czasu są pozornie proste, lecz pełne niuansów: omówiono lata przestępne, różne systemy kalendarzowe i sekundy przestępne oraz ich wpływ na systemy informatyczne. Lata przestępne korygują różnicę między rokiem kalendarzowym a słonecznym; współczesna reguła (od 1582) to: rok podzielny przez 4 i nieprzez 100, lub przez 400. Kalendarz gregoriański wprowadzono w 1582 r.; wcześniej używano juliańskiego (inny schemat przestępności i historyczne błędy), a adopcja gregoriańskiego nastąpiła w różnych krajach dopiero w XIX–XX w., co powodowało pomijanie dni przy zmianie i komplikacje historyczne; różnica między kalendarzami wynosi dziś 13 dni (po 2100 r. będzie 14). W astronomii używa się daty juliańskiej (JD/JDN) i zmodyfikowanej MJD dla jednoznacznych obliczeń czasowych. Istnieje wiele innych kalendarzy (rzymski, chiński lunisolarny z dodawanym miesiącem, tajwański/republikański, dżucze, japoński era, muzułmański księżycowy z obserwacyjną naturą), a konwersje (szczególnie dla kalendarza islamskiego) bywają złożone. Sekunda przestępna dodawana jest nieregularnie przez IERS (30 VI lub 31 XII) by utrzymać różnicę UT1–UTC <0,9 s; decyzje są półroczne, więc zdarzeń nie da się przewidzieć prostym wzorem. Istnieją różne standardy czasu: TAI (atomowy), UTC (z sekundami przestępnymi) i TT (TT = TAI + 32,184 s); w 2021 TAI wyprzedzał UTC o 37 s. Komputery radzą sobie z tym różnie: NTP informuje o leap second, Linux ma metody (np. powtórzenie 59. sekundy), Windows zwykle ignoruje i koryguje przy synchronizacji, dostawcy chmurowi stosują „leap smear”, a czas uniksowy nie uwzględnia sekund przestępnych (dzień = 86400 s), co komplikuje konwersje. Praktyczne zalecenie: korzystać z gotowych bibliotek i systemowych implementacji dat/czasu; rozważ proleptyczny kalendarz gregoriański używany w bazach danych i standardzie ISO 8601, jeśli nie musisz obsługiwać wiernie historycznych dat. ## Dlaczego mierzenie i przetwarzanie czasu jest trudne? — część 2 z 2 https://swistak.codes/post/dlaczego-mierzenie-i-przetwarzanie-czasu-jest-trudne-czesc-2 Artykuł omawia złożoność przetwarzania dat i czasu: genezę i nieregularności stref czasowych (nie tylko pełne godziny, ale też przesunięcia o 30 i 45 minut), przypadki wielu stref w jednym kraju i odstępstwa (np. Chiny stosujące jedną strefę), oraz skomplikowane zasady czasu letniego/zimowego (różne daty/godziny, wyjątki terytorialne). Wyjaśnia praktyczne narzędzia i mechanizmy: IANA tz database jako podstawowe źródło reguł strefowych, oraz protokoły synchronizacji czasu (NTP i PTP) z korekcją opóźnień (RTT) i znacznikiem czasowym w pakietach; opisano też prostsze algorytmy synchronizacji (Cristian, Berkeley). Podkreślono, że źródła czasu i reguły mogą się zmieniać (ustawodawstwo, jednorazowe przesunięcia), co wymaga ostrożności przy projektowaniu systemów. Omówiono propozycje reform kalendarza (World Calendar, International Fixed Calendar, Symmetry454, Hanke‑Henry itp.) oraz ich motywacje. Na koniec poruszono problemy kosmiczne: odmienne jednostki i systemy czasu na Marsie (sol, dłuższa sekunda; Mars Sol Date) i propozycje czasu księżycowego (Lunar Standard Time), wskazując, że eksploracja kosmosu dodatkowo skomplikuje zagadnienia dat i synchronizacji. ## Określanie dnia tygodnia dla dowolnej daty https://swistak.codes/post/okreslanie-dnia-tygodnia-dla-dowolnej-daty Artykuł opisuje kilka sposobów wyznaczania dnia tygodnia dla dat w kalendarzu gregoriańskim — matematycznych, programistycznych i zapamiętywalnych „rekreacyjnych” metod. Wyjaśniono krótko operacje modulo i floor oraz uwagę o różnicach definicji modulo w matematyce i językach programowania. Metody matematyczne obejmują Rata Die (liczenie dni od ustalonej daty, powiązanie z datą juliańską) oraz kongruencję Zellera (wzór z podziałem miesięcy od marca i zmiennymi q, m, K, J). Wśród podejść programistycznych omówiono algorytm z RFC3339 i popularną metodę Sakamoto (tablica przesunięć; prosta implementacja w C/JS). Sekcja „rekreacyjna” przedstawia pamięciowe techniki: metodę Lewisa Carrolla (kroki operacyjne na wiekach, latach, miesiącach, dniach — szybkie obliczenia w pamięci) oraz regułę Doomsday Johna Conwaya (stałe „doomsdayy” w roku, kotwice dla wieków i proste dodawanie tuzinów/lat przestępnych). Autor zaleca używanie bibliotek dat w programowaniu, ale podkreśla wartość poznania tych algorytmów jako ćwiczenia umysłowego i wyjaśnienia, co kryje się w implementacjach. ## Dziwny przypadek reszty z dzielenia https://swistak.codes/post/dziwny-przypadek-reszty-z-dzielenia Artykuł wyjaśnia, dlaczego operator modulo zwraca różne wyniki w różnych językach: matematyczna (euklidesowa) definicja reszty wymaga 0 ≤ r < |b|, ale w praktyce języki stosują różne konwencje. Najczęściej spotykane implementacje to: „dzielenie obcięte” (trunc) — reszta ma znak dzielnej (np. operator % w C, C++, JavaScript, Java, C#, Go itp.); „dzielenie z podłogą” (floor) — reszta ma znak dzielnika (np. Python, Ruby, Lua, R); „dzielenie z zaokrągleniem” zgodne ze standardem IEEE-754 (funkcja remainder) — zaokrąglenie do najbliższej liczby całkowitej. Dart (i niektóre inne języki) stosuje definicję euklidesową (r ≥ 0). R. T. Boute zaproponował formułę używającą |b| zapewniającą zgodność z definicją euklidesową. Artykuł opisuje też algorytmy konwersji: E — przekształca wynik trunc do postaci euklidesowej; F — do postaci floor. Wniosek: przy operacjach modulo trzeba sprawdzić konwencję języka, szczególnie gdy występują liczby ujemne. ## Algorytmika gier — kółko i krzyżyk https://swistak.codes/post/algorytmika-gier-kolko-i-krzyzyk Artykuł przedstawia dwa podejścia do stworzenia AI do gry w kółko i krzyżyk: prostą strategię regułową opisaną przez Crowleya i Sieglera oraz algorytm Minimax. Strategia regułowa to zestaw priorytetowych warunków (w kolejności: wygraj, zablokuj, zrób rozgałęzienie (fork), zrób blokujące rozgałęzienie, zagraj środek, zagraj przeciwny narożnik, pusty narożnik, pusty bok) — łatwa do zaimplementowania, daje możliwość prostego dostosowania poziomu trudności przez pomijanie niektórych reguł. Minimax to uniwersalna metoda przeszukiwania drzewa stanów gry rekurencyjnie, oceniająca liście (wygrana/przegrana/remis) i propagująca min/max wartości w górę drzewa, wybierając optymalny ruch przy założeniu racjonalnego przeciwnika; dla tic‑tac‑toe pełne przeszukanie jest wykonalne. Omówiono też praktyczne uwagi: liczba możliwych gier (255 168), przewagę pierwszego gracza przy optymalnej grze, oraz usprawnienia/alternatywy dla Minimax (alfa‑beta, Negamax, NegaScout, Expectiminimax, MCTS) i możliwość użycia uczenia głębokiego (np. podejście AlphaZero) w bardziej złożonych grach. ## Wieże Hanoi https://swistak.codes/post/wieze-hanoi Artykuł opisuje zagadkę Wieże Hanoi: jej historię (wynalazca Édouard Lucas, insp. przez chińskie pierścienie), legendę „wieży Brahmy”, zasady gry (3 słupki, przesunięcie jednego krążka naraz, większy na mniejszym) oraz klasyczne algorytmiczne podejścia. Pokazuje rekurencyjne rozwiązanie „dziel i zwyciężaj” i dowód, że minimalna liczba ruchów to 2^n−1 (dla 64 krążków ≈1,84·10^19 ruchów, co przy 1 ruchu/s to ~5·10^11 lat). Omawia implementację rekurencyjną i iteracyjne metody (algorytm Olive’a, Idle Peg), oraz matematyczne wzory określające które krążki ruszają się kiedy, pozycje krążków i nieaktywny słupek. Wspomina warianty (więcej słupków — problem Reve’go, Tower/Little Antwerpen z kolorami, psychologiczny Tower of London) oraz zastosowanie ciągu ruchów do generowania kodu Graya. Na końcu poleca monografię The Tower of Hanoi: myths and maths jako źródło głębszej wiedzy. ## Kryptarytmy https://swistak.codes/post/kryptarytmy Artykuł wyjaśnia, czym są kryptarytmy — zadania, w których litery zastępują cyfry tak, by działanie było poprawne (jedna litera = jedna unikalna cyfra, max. 10 liter). Podane są odmiany (alfametyki, podwójnie prawdziwe, alfabetyki literackie, algebrafy) oraz klasyczny przykład SEND+MORE=MONEY z rozwiązaniem SEND=9567, MORE=1085, MONEY=10652 i opisem ręcznego rozumowania po kolumnach. Autor pokazuje podejście algorytmiczne: wygenerować wszystkie przypisania cyfr do liter (perm utacje cyfr 0–9), uwzględniając ograniczenia typu brak zer jako pierwszej cyfry i filtrowanie sztucznych rozwiązań gdy liter <10; można przerwać po pierwszym rozwiązaniu lub sprawdzić wszystkie. Opisane są dwa algorytmy generowania permutacji: leksykograficzny (Narayaṇa Paṇḍita) i algorytm prostych zmian (Plain changes, historycznie używany przez dzwonników), oba o podobnej wydajności; implementacje w JavaScript są dostępne. W tekście podkreślono, że 10! permutacji (3 628 800) jest dużą, ale wykonalną przestrzenią przeszukiwań, oraz odwołano się do Knutha (TAOCP 4A) i innych źródeł. ## Sudoku https://swistak.codes/post/sudoku Artykuł opisuje sudoku — krótka historia i zasady (9×9, unikalne cyfry 1–9 w wierszach, kolumnach i 3×3 kwadratach), fakty: liczba możliwych pełnych rozwiązań ≈6,671×10^21 oraz minimalna liczba wskazówek zapewniająca unikalność = 17. Przedstawione jest algorytmiczne podejście do rozwiązywania przez przeszukiwanie z nawrotami (backtracking) w ujęciu CSP ⟨X,D,C⟩; praktyczne wskazówki obejmują reprezentację planszy jako jednowymiarowej tablicy 81-elementowej (mapowanie indeksów), dziedzinę {1..9} oraz sprawdzanie ograniczeń w wierszach, kolumnach i kwadratach przy użyciu struktur typu set/hashset. Omówione są zalety backtrackingu (prosta implementacja, zawsze znajdzie rozwiązanie, niezależność od subiektywnej trudności) oraz wady (duża i nieprzewidywalna liczba iteracji — od kilkunastu tysięcy do milionów, wolniejsze w niektórych przypadkach). Jako ulepszenia i alternatywy opisano forward checking, metody stochastyczne (symulowane wyżarzanie, algorytmy ewolucyjne, mrówkowe) oraz redukcję do problemu exact cover rozwiązywanego algorytmem X Knutha. Artykuł odsyła do implementacji na GitHubie i literatury (prace Felgenhauer & Jarvis, McGuire et al., Simonis, Perez & Marwala, Kapanowski). ## Obliczanie całek oznaczonych https://swistak.codes/post/obliczanie-calek-oznaczonych Artykuł wyjaśnia, czym są całki oznaczone (Riemanna) — interpretowane jako pola pod wykresem funkcji na przedziale [a,b] i definiowane poprzez sumy Riemanna jako granice sum f(qi)·Δpi — oraz pokazuje proste przykłady (∫_0^5 x dx = 12.5, ∫_0^π sin x dx = 2, ∫_0^r sqrt(r^2−x^2) dx = πr^2/4). Omawia różnicę między obliczeniami symbolicznymi (CAS) a szybkimi przybliżeniami numerycznymi i przedstawia podstawowe metody numeryczne: metoda prostokątów (punkt lewy/prawy/środkowy), trapezów (średnia wartości na końcach), metoda Simpsona (aproksymacja paraboli) oraz Monte Carlo (losowanie punktów w prostokącie, estymacja udziału pod wykresem; wymaga generatora pseudolosowego i jednorodnego rozkładu). Zawiera przykładowe implementacje w JavaScript/TypeScript oraz wskazuje zastosowania w informatyce: symulacje inżynierskie (MATLAB/Octave), PID, symulacje fizyki w grach, DSP (transformaty) oraz zastosowania Monte Carlo (AlphaZero, path tracing). ## Jak komputer zapisuje kolory? https://swistak.codes/post/jak-komputer-zapisuje-kolory Artykuł opisuje kolory od strony fizycznej, biologicznej i informatycznej: kolor to psychiczne wrażenie wywołane promieniowaniem elektromagnetycznym (u ludzi ~400–700 nm), które można również mierzyć (np. spektrofotometr). Kluczowa jest teoria Younga–Helmholtza: widzenie barwne opiera się na trzech rodzajach czopków reagujących na składowe odpowiadające w praktyce czerwonej, zielonej i niebieskiej; dodatkowo istnieją pręciki do widzenia monochromatycznego. Wyjaśniono podstawowe pojęcia: jasność, odcień, nasycenie, synteza addytywna (światło) i subtraktywna (farby) oraz kanał alpha (przezroczystość). Omówiono główne przestrzenie barw i modele stosowane w informatyce: RGB/RGBA (i standard sRGB), CMYK dla druku, modele telewizyjne YUV/YCbCr (używane też w kompresji JPEG/MPEG i HDMI), oraz intuicyjne HSL/HSV. Wspomniano też modele CIE (CIEXYZ, CIELAB, CIELUV) jako pełniejszą bazę kolorów i systemy nazewnictwa (Pantone, indeksy). W praktycznym zapisie barw poruszono palety/indexed color i CLUT (historyczne standardy MDA/CGA/EGA/VGA), głębię koloru (16/24/32/30 bpp i deep color), problemy niskiej rozdzielczości tonalnej (banding) i techniki redukcji (dithering, np. Floyd–Steinberg). Zapis w plikach: formaty tekstowe (SVG/CSS: #RRGGBB, rgb(), hsl(), lab()/lch()/color()) oraz binarne, gdzie istotne są głębia, przestrzeń barw i końcówkowość (np. BMP BBGGRR); kompresja to odrębny temat. ## Podstawowe operacje na barwach https://swistak.codes/post/podstawowe-operacje-na-barwach Artykuł omawia podstawowe operacje na kolorach z interaktywnymi prezentacjami (TypeScript + Preact) uruchamianymi lokalnie w przeglądarce. Zawiera: - Konwersję na skalę szarości: prosta średnia (R'=G'=B'=(R+G+B)/3) oraz średnia ważona używana w YUV/YCbCr (R'=G'=B'=KrR+KgG+KbB, np. Kr=0.299, Kg=0.587, Kb=0.114). Tryb dwukolorowy przez progowanie (threshold). - Jasność: dodawanie stałej I do każdego kanału z ograniczeniem do [0,255] (R'=trunc(R+I) itd.). - Kontrast: mnożenie wokół punktu 128 z czynnikiem F = 259*(C+255)/(255*(259−C)); R'=trunc(F*(R−128)+128). - Korekcja gamma: nieliniowa transformacja R'=255*(R/255)^(1/γ) (analogicznie dla G,B). - Negatyw: inwersja kolorów R'=255−R (G',B'). - Solaryzacja: częściowa inwersja względem progu T, np. R'=255−R dla R≤T, inaczej R (związek z efektem Sabattiera). Na końcu lista źródeł i odnośników do literatury i przykładów implementacyjnych. ## Algorytmiczne rysowanie roślin https://swistak.codes/post/algorytmiczne-rysowanie-roslin Artykuł opisuje wykorzystanie L-systemów (systemów Lindenmayera) razem z grafiką żółwiową do rysowania prostych, dwuwymiarowych roślin i fraktali. Wyjaśnia podstawowe pojęcia L-systemów: alfabet, aksjomat i reguły produkcji oraz sposób, w jaki ciągi symboli można interpretować jako polecenia żółwia (F, f, +, -) z parametrem kąta δ. Pokazane są typowe przykłady fraktali zapisane jako L-systemy — krzywe Kocha (w tym śnieżynka) i smok Heighwaya — oraz mechanizm rozgałęzień realizowany przez znaki [ i ] (stos stanów żółwia). Przedstawiono także generowanie prostych roślin (przykłady z The Algorithmic Beauty of Plants) i rozszerzenie do stochastycznych L-systemów, gdzie reguły mają przypisane prawdopodobieństwa, co pozwala wprowadzić naturalną zmienność. Implementacje demonstracyjne są w JavaScript z użyciem biblioteki Lindenmayer (kod na GitHubie). Autor odsyła do prac Prusinkiewicza i książki The Algorithmic Beauty of Plants jako głównych źródeł. ## Algorytmiczne rysowanie roślin w 3D https://swistak.codes/post/algorytmiczne-rysowanie-roslin-w-3d Artykuł opisuje rozszerzenie techniki L-systemów i grafiki żółwiowej z 2D do 3D, pokazując praktyczne zasady i przykłady generowania trójwymiarowych fraktali i modeli roślin. Wyjaśniono podstawowe polecenia obrotów w 3D (rotacje wokół osi X, Y, Z oraz obrót o 180°), sposób ich zapisu w L-systemach oraz użycie macierzy transformacji lub kwaternionów do obliczeń. Omówiono dwa podejścia do renderowania: dyskretne (woksele) oraz budowanie modeli z wielokątów (np. cienkie walce dla gałęzi i modele liści), a także reguły rysowania wielokątów zapisane w klamrach {}. Przedstawiono dodatkowe polecenia sterujące średnicą i kolorem oraz konkretne przykłady L-systemów w 3D: wyspę Kocha, trójwymiarową krzywą Hilberta oraz generowanie krzewu i rośliny (na podstawie The Algorithmic Beauty of Plants), z ilustracją użycia reguł i modeli liści/kwiatów. Pokazano też zastosowanie stochastycznych reguł (losowość w regułach) dla większej naturalności. Implementacje demonstracji napisano w JavaScript z użyciem Three.js i biblioteki Lindenmayer; kod dostępny na GitHubie. Artykuł odsyła do dalszej literatury (Prusinkiewicz i współautorzy) oraz zasobów Algorithmic Botany. ## Liczby pierwsze i proste sposoby na ich sprawdzanie https://swistak.codes/post/liczby-pierwsze-i-proste-sposoby-na-ich-sprawdzanie Artykuł wyjaśnia pojęcie liczby pierwszej (naturalna >1 mająca tylko dzielniki 1 i siebie), podaje przykłady (2, 3, 5, 7, 11, …), przypomina dowód nieskończoności przez Euklidesa oraz historyczne uwagi (decyzja o wyłączeniu 1, twierdzenie o jednoznacznym rozkładzie na czynniki pierwsze przypisywane Gaussowi). Wskazuje podstawowe własności: poza 2 wszystkie są nieparzyste, poza 2,3,5 kończą się cyfrą 1,3,7 lub 9. Omawia zastosowania w informatyce: kryptografia klucza publicznego (RSA bazujący na iloczynie dwóch dużych (np. 2048-bit) liczb pierwszych), sumy kontrolne (Adler‑32 używa modulo 65521, ISBN modulo 11), funkcje haszujące (konstrukcje Wegmana–Cartera) oraz generatory pseudolosowe (Mersenne Twister oparty na primo‑Mersenne’ie 2^19937−1, Blum Blum Shub używający iloczynu dwóch dużych pierwszych). Opisuje testy pierwszości ze szczegółami na przykładzie dzielenia próbnego (trial division) i jego optymalizacji: od sprawdzania dzielników do n, przez n/2, aż do sqrt(n) (opisanego już u Fibonacciego), z przykładowymi implementacjami JS. Wyniki benchmarku dla sprawdzania pierwszości do liczby 15 484 279 (milionowa liczba pierwsza) pokazują znaczną poprawę: bez optymalizacji ~45 ms, opt.1 ~22 ms, opt.2 ~0,11 ms (średnie czasy). Podsumowanie podkreśla zarówno teoretyczne znaczenie liczb pierwszych, jak i praktyczne zastosowania oraz wartość nauki optymalizacji algorytmów na prostym przykładzie. ## Proste sposoby na znajdowanie liczb pierwszych https://swistak.codes/post/proste-sposoby-na-znajdowanie-liczb-pierwszych Artykuł opisuje podstawowe metody znajdowania liczb pierwszych: metodę naiwną (sprawdzanie kolejnych liczb dzielnikami do √n), klasyczne sito Eratostenesa (oznaczanie wielokrotności jako złożonych) oraz sito Sundarama (wykluczanie liczb zgodnie z wzorem i + j + 2ij, które daje po przekształceniu nieparzyste liczby pierwsze 2i+1). Dla każdej metody pokazano prostą implementację w JavaScripcie i przykłady działania (np. Eratostenes dla 2..10). Przeprowadzono benchmark do 100000 (50 powtórzeń) — metoda naiwna była znacznie wolniejsza, a sito Eratostenesa nieco szybsze od Sundarama (wersja nieskomplikowana). Autor podkreśla edukacyjną wartość sita Eratostenesa i sugeruje dalsze optymalizacje oraz zapoznanie się z sitami Atkina i innymi modyfikacjami. ## Duże liczby pierwsze https://swistak.codes/post/duze-liczby-pierwsze Artykuł opisuje, jak matematycy teoretycznie i praktycznie wyszukują bardzo duże liczby pierwsze. Omawia historyczne i empiryczne zależności pozwalające „namierzyć” pierwsze: wielomian Eulera generujący wiele pierwszych dla małych n, spiralę Ulama ujawniającą geometryczne wzory związane z pewnymi kwadratowymi wielomianami, funkcję zliczającą π(x) oraz przybliżenia π(x) ∼ x/log x i Li(x) (twierdzenie o liczbach pierwszych), które dają gęstość pierwszych i przybliżenie n-tej liczby pierwszej pn ∼ n log n oraz prawdopodobieństwo, że losowa liczba k-bitowa jest pierwsza (~1/ln n, stąd np. dla 1024-bitowej liczby potrzeba średnio kiluset prób). Opisuje klasy szczególnych rodzin pierwszych użytecznych do wyszukiwań i testów: Mersenne’a (Mn = 2^n−1, test Lucas‑Lehmera, projekt GIMPS), Fermata, Protha, primorial i „factorial primes” — wszystkie mają postać ±1 względem prostej funkcji, co ułatwia testowanie. Przedstawia także narzędzia testowania: szybkie, probabilistyczne testy pseudopierwszności (test Fermata, silny test Millera‑Rabina, Baillie‑PSW) oraz pojęcie pseudopierwszych (np. 341 dla podstawy 2); deterministyczne testy klasyczne opierające się na rozkładzie n−1 lub n+1 (Lucasa, Pepina, Protha, Lucas‑Lehmer dla Mersenne’ów) oraz nowocześniejsze testy ogólnego przeznaczenia (APR, APR‑CL, ECPP na krzywych eliptycznych i deterministyczny AKS). Wyjaśnia znaczenie tych metod w kontekście kryptografii, projekty rozproszone (GIMPS, PrimeGrid), oraz motywacje — praktyczne zastosowania i tradycja matematyczna, nagrody za rekordowe odkrycia. ## Szybkie szukanie dużych liczb pierwszych https://swistak.codes/post/szybkie-szukanie-duzych-liczb-pierwszych Artykuł opisuje praktyczną implementację testu Millera–Rabina do szybkiego wykrywania dużych liczb pierwszych oraz generatora takich liczb. Kluczowe punkty: - Idea testu: dla nieparzystego n zapisujemy n−1 = 2^s * d (d nieparzyste). Dla losowej podstawy a ∈ (1, n−1) obliczamy x = a^d mod n. Jeśli x == 1 lub x == n−1 n uznajemy za „prawdopodobnie pierwsze” dla tej próby. W przeciwnym razie wielokrotnie podnosimy x do kwadratu (x = x^2 mod n) dla r = 1..s−1, szukając x == n−1; jeśli nadal nie, n jest złożone. a, które ujawnia złożoność to „świadek złożoności”. - Algorytmy pomocnicze: szybkie potęgowanie modularne (binary exponentiation / modPow) oraz faktoryzacja n−1 na 2^s * d (dzielenie przez 2 aż do uzyskania nieparzystego d). - Usprawnienia: podczas kolejnych kroków ponownie używamy poprzedniego x i kolejno podnosimy go do kwadratu zamiast liczyć od nowa; jeśli x==1 w pętli, można od razu stwierdzić złożoność. - Wersja deterministyczna: zamiast losować a, używa się ustalonych zbiorów podstaw wystarczających dla danych zakresów n (np. {2} dla n<2047, {2,3} dla n<1373653, {31,73} dla n<9080191 itd.). - Generowanie dużych liczb pierwszych: losujemy b-bitowe nieparzyste liczby (ustawiając najwyższy i najmłodszy bit na 1) i testujemy je Millera–Rabinem aż znajdziemy „silnie prawdopodobną” pierwszą. - Pewność i częstość powtórzeń: dla złożonego n jedna próba ma prawdopodobieństwo błędu ≤ 1/2, więc po k niezależnych próbach błąd ≤ 2^−k. Warunkowe prawdopodobieństwo, że liczba jest rzeczywiście pierwsza po pozytywnym teście, daje przybliżenie P(A|B) ≈ 1 / (1 + 2^−k (ln n − 1)). Minimalna liczba powtórzeń ≈ log2(ln n − 1) ≈ log2(b/1.443); przykłady: 64 bit ≈5, 512 bit ≈8, 1024 bit ≈9; 50 iteracji uznaje się za bardzo bezpieczne. - Implementacja i uwagi praktyczne: przykłady w JavaScript (modPow, factorize, millerRabin) dostępne na GitHubie; jednak JS nie jest najszybszy i kod ma charakter edukacyjny — do zastosowań kryptograficznych lepiej używać zweryfikowanych bibliotek. ## Porównanie szybkich testów pierwszości https://swistak.codes/post/porownanie-szybkich-testow-pierwszosci Porównanie szybkich testów pierwszości (Fermat, Miller–Rabin, deterministyczny Miller–Rabin, Solovay–Strassen) z metodą naiwną przeprowadzono w JavaScripcie na MacBooku Pro (2018, 6‑rdzeniowy i7); każdy test uruchamiano 100 razy i agregowano wyniki. Wyniki szybkości: testy probabilistyczne są znacznie szybsze i mają czas wykonania w przybliżeniu stały w funkcji wielkości liczby (w przeciwieństwie do metody naiwnej); Fermat i losowy Miller–Rabin mają porównywalne czasy, Solovay–Strassen jest nieco wolniejszy, a deterministyczny Miller–Rabin wykazuje niewielki skok tam, gdzie dodano kolejne bazy. Czas skalował się w przybliżeniu liniowo z liczbą powtórzeń (1, 5, 10, 100), choć bez idealnej proporcji z powodu narzutu funkcji i pomiarów w ns. Dokładność (liczby z zakresu 3–999999, nieparzyste): przy jednym powtórzeniu liczba błędów (fałszywych pozytywów) wyniosła: Fermat 41 719 (≈0,083%), Miller–Rabin 9 183 (≈0,018%), Solovay–Strassen 15 887 (≈0,032%), deterministyczny Miller–Rabin 0. Zwiększenie powtórzeń znacząco zmniejszało błędy — przy 5/10/100 powtórzeniach Fermat: 1 738 / 86 / 14 (≈0,00348% / 0,00172% / 0,00001%), Miller–Rabin: spadek do 0 przy ≥5 powtórzeń w badanym zakresie, Solovay–Strassen: 1 400 przy 5 powtórzeniach i 0 przy ≥10. Wniosek: szybkie testy są znacznie wydajniejsze od metody naiwnej i — przy odpowiedniej liczbie powtórzeń lub dobranych bazach deterministycznego MR — praktycznie bezbłędne dla badanych zakresów. ## świstak.codes powraca! https://swistak.codes/offtopic/swistak-codes-powraca świstak.codes wróciło w nowej odsłonie: autor porzucił WordPress na rzecz autorskiego rozwiązania napisanego w TypeScript z użyciem Next.js (strony generowane statycznie podczas kompilacji), co umożliwiło lepszą kontrolę techniczną, optymalizację zasobów (mniejsze skrypty, style, obrazy) i szybsze ładowanie. Nowości UX/UI: nowy, oryginalny layout, ciemny motyw, spisy treści przy wpisach, indeks zagadnień (tagi jako indeks), kategoria offtopic, szybkie udostępnianie oraz usunięcie baneru cookies dzięki rezygnacji z Google Analytics. Zrezygnowano z Google Analytics ze względów prywatności i częstego blokowania — analitykę prowadzi się teraz na podstawie logów serwera oraz testowo Matomo w trybie anonimowym (brak śledzących ciastek, IP zamaskowane). W planach: newsletter, prywatnościowo‑świadomy system komentarzy, poprawa dostępności i dalsze usprawnienia (35 z 50 zaplanowanych zadań już wykonanych). Autor prosi o feedback (mail/LinkedIn/Facebook) i zaprasza do subskrypcji RSS oraz śledzenia mediów społecznościowych. ## Grafy — wprowadzenie https://swistak.codes/post/grafy-wprowadzenie Artykuł omawia podstawy teorii grafów i ich zastosowania w informatyce. Graf definiowany jest jako para G=(V,E) wierzchołków (węzłów) i krawędzi (połączeń); węzły mogą mieć etykiety/wagi i reprezentować różne byty, a krawędzie mogą być pętlami, skierowane (łuki) lub nieskierowane oraz także wagowane. Wyróżnione są typy grafów: skierowane (digrafy), mieszane i ważone, oraz klasy: grafy pełne, spójne, acykliczne i drzewa (nieskierowane, spójne i acykliczne). Krótka historia przypomina Eulera i problem mostów królewieckich oraz późniejsze nazewnictwo Sylvestra. Przykładowe zastosowania to znajdowanie tras i routing (np. algorytmy najkrótszej ścieżki, A*), reprezentacja wiedzy i ontologie (WordNet, grafowe bazy danych), modelowanie hierarchii i struktur drzewiastych, tworzenie diagramów (UML, BPMN) oraz zastosowania w grach (drzewa stanów, grafy plansz). Artykuł zapowiada dalsze materiały o reprezentacji grafów w programowaniu i algorytmach. ## Sposoby reprezentacji grafów https://swistak.codes/post/sposoby-reprezentacji-grafow Artykuł opisuje, jak reprezentować grafy jako strukturę danych: graf jako ADT przechowuje zbiór wierzchołków i rodzinę krawędzi (skierowane/nieskierowane), opcjonalnie wagi i dodatkowe dane; podstawowe operacje to dodanie/usunięcie wierzchołka/krawędzi oraz sprawdzenie sąsiedztwa. Omówione reprezentacje: - Lista krawędzi: lista par/obiektów krawędzi (zwykle razem z listą wierzchołków); pamięć O(|E|), operacje w najgorszym wypadku O(|E|); elastyczna, obsługuje wielokrotne krawędzie, popularna przy wizualizacji (np. GoJS). - Lista sąsiedztwa: lista list sąsiadów indeksowanych wierzchołkami; pamięć O(|V|+|E|), dodawanie krawędzi O(1), sprawdzenie sąsiedztwa O(d); najlepsza dla grafów rzadkich i algorytmiki (np. Boost adjacency_list). - Macierz sąsiedztwa: tablica |V|×|V| z wartościami (0/1 lub wagi); pamięć O(|V|^2), dostęp do krawędzi O(1), kosztowne przy zmianie rozmiaru; odpowiednia dla grafów gęstych. - Macierz incydencji: tablica |V|×|E| z informacją o powiązaniu wierzchołka z krawędzią; pamięć i modyfikacje O(|V|·|E|), zwykle niepraktyczna poza teorią. Wnioski: wybierać strukturę wedle zastosowania — lista sąsiedztwa dla algorytmów i grafów rzadkich, macierz dla grafów gęstych, lista krawędzi przy wizualizacji i potrzebie przechowywania dodatkowych danych. Autor udostępnia demonstrację napisaną w TypeScript/React z Cytoscape.js i odwołuje się do literatury (m.in. Cormen, Boost). ## Przechodzenie po grafie https://swistak.codes/post/przechodzenie-po-grafie Artykuł opisuje podstawy przechodzenia grafów (graph traversal): cele (zbieranie informacji, część innych algorytmów) i złożoność O(|V|+|E|). Omawia dwa kluczowe sposoby: DFS (depth-first search) — eksploracja wzdłuż jednej ścieżki do końca, z rekurencyjną i iteracyjną (stos LIFO) implementacją; oraz BFS (breadth-first search) — eksploracja warstwami z użyciem kolejki FIFO, również w wersjach z kolorowaniem wierzchołków (white/gray/black) lub praktycznym zapisem z visited-set. Zwrócono uwagę na problemy z cyklami i grafami nieskończonymi oraz praktyczne różnice kolejności odwiedzin między wersjami rekurencyjną i iteracyjną. Dla drzew przechodzenie jest analogiczne; wyróżniono pre-order (DFS), post-order, level-order (BFS) oraz in-order dla drzew binarnych. Wyszczególniono zastosowania: wykrywanie cykliczności, eksploracja (np. crawlery), odkrywanie ścieżek/data lineage; specyficzne zastosowania DFS: sortowanie topologiczne, rozwiązywanie labiryntów, znajdowanie mostów (Tarjan); BFS: najkrótsze ścieżki w grafach nieważonych, Edmonds–Karp w problemie maksymalnego przepływu, Aho–Corasick przy wyszukiwaniu wzorców. Wzmianka o praktycznej prezentacji napisanej w TypeScript/React z Cytoscape.js i źródłach literaturowych (Cormen i inni, Wikipedia, Cytoscape.js). ## Praktyczne zastosowania przechodzenia po grafie https://swistak.codes/post/praktyczne-zastosowania-przechodzenia-po-grafie Artykuł pokazuje praktyczne zastosowania algorytmów przechodzenia grafu (DFS i BFS) na trzech przykładach: wyszukiwanie spójnych składowych (subgrafów) w strukturze grafowej, wykrywanie i wypisywanie cykli oraz znajdowanie najkrótszych ścieżek w grafie nieważonym. - Wyszukiwanie subgrafów: iterujemy po wszystkich wierzchołkach, trzymamy zbiór odwiedzonych i dla każdego nieodwiedzonego uruchamiamy przejście (np. iteracyjny DFS), zbierając wierzchołki aktualnej składowej; wynik to lista zbiorów wierzchołków. - Wykrywanie cykli: używamy DFS z kolorowaniem wierzchołków (WHITE/GRAY/BLACK) i stosem ścieżki; napotkanie szarego sąsiada oznacza cykl, który rekonstruujemy za pomocą pomocniczego stosu, co pozwala też wypisać wszystkie cykle (przydatne np. do wykrywania circular dependency w kodzie i do zapewnienia acykliczności wymaganej przez algorytmy typu topologiczne lub układ warstwowy Sugiyamy). - Najkrótsze ścieżki w grafie nieważonym: BFS z zapamiętywaniem poprzedników (previous) daje najkrótsze ścieżki liczonych krawędziowo; ścieżkę rekonstruuje się cofając się po tablicy poprzedników (rekursywnie lub iteracyjnie). Przydatne np. w grach planszowych — dla grafów ważonych lepsze są algorytmy typu A*. W artykule podano przykładowe implementacje w JavaScript wykorzystujące pomocnicze funkcje getAllNodes, getNeighbors/getConnectedNodes oraz pokazano zarówno rekurencyjny, jak i iteracyjny DFS. Literatura: rozdziały o BFS i DFS z Cormen et al. ## Szukanie najkrótszych ścieżek w grafie https://swistak.codes/post/szukanie-najkrotszych-sciezek-w-grafie Artykuł opisuje problem znajdowania najkrótszych ścieżek w grafach ważonych, omawiając teoretyczne aspekty wag (dodatnie, ujemne, zerowe) oraz trzy klasyczne algorytmy i ich zastosowania, implementacje i złożoności. - Kontekst: w grafach ważonych interesują nas wagi krawędzi i suma wag na ścieżce; wagi ujemne mogą powodować problem istnienia cykli o ujemnej sumie (dają dystans → −∞), które uniemożliwiają wyznaczenie najkrótszej ścieżki; cykle o zerowej wadze można pominąć przy rekonstrukcji ścieżki. - Dwa typy zadań: single-source shortest paths (SSSP) oraz all-pairs shortest paths (APSP). Algorytmy: - Bellman–Ford: SSSP z obsługą ujemnych wag i wykrywaniem ujemnych cykli; opiera się na relaksacji wszystkich krawędzi powtarzanej |V|−1 razy; zwraca tablice distance i previous; złożoność O(|V|·|E|), pamięć O(|V|). - Dijkstra: SSSP dla grafów bez ujemnych wag; relaksacja w porządku zachłannym wybierając zawsze najbliższy wierzchołek za pomocą kolejki priorytetowej (min-heap); implementacje: kopiec binarny → O((|E|+|V|) log |V|), kopiec Fibonacciego → O(|E| + |V| log |V|), prosty wybór z tablicy → O(|V|^2); zwraca distance i previous. - Floyd–Warshall: APSP dla grafów bez ujemnych cykli (dopuszcza ujemne wagi); dynamiczne programowanie z trzema zagnieżdżonymi pętlami i macierzą odległości oraz macierzą następników do rekonstrukcji ścieżek; złożoność O(|V|^3), pamięć O(|V|^2). Dodatkowe podejścia i uwagi: - BFS dla grafów nieważonych: O(|E|+|V|). - Topologiczne SSSP dla DAG: O(|E|+|V|) (relaksacja w kolejności topologicznej). - Algorytmy specjalne: Thorup (grafy nieskierowane z całkowitymi wagami — bardzo szybki), Dial (kubełki dla wag naturalnych), Johnson (APSP dla skierowanych z dowolnymi wagami bez ujemnych cykli — łączy Bellman–Ford i Dijkstrę), Seidel (specjalne przypadki), A* (SSSP dla jednej pary z heurystyką; przyspiesza przeszukiwanie praktyczne). - Implementacje w artykule: przykładowy kod JavaScript dla Bellman–Ford, Dijkstry (z kopcem Fibonacciego) i Floyda-Warshalla; wskazówki do rekonstrukcji ścieżek (previous dla SSSP, next dla APSP). Podsumowanie praktyczne: - APSP → Floyd–Warshall (jeśli mała liczba wierzchołków i brak ujemnych cykli), złożoność O(|V|^3). - SSSP, niewymagające ujemnych wag → Dijkstra (z kolejką priorytetową; efektywnie O((|E|+|V|) log |V|)). - SSSP z możliwymi ujemnymi wagami → Bellman–Ford (i wykrycie ujemnych cykli), O(|V|·|E|). - Dla specjalnych klas grafów (DAG, całkowite wagi, specyficzne ograniczenia) stosować algorytmy wyspecjalizowane (topologiczne SSSP, Thorup, Dial, Johnson). ## Szybkie wyszukiwanie ścieżek https://swistak.codes/post/szybkie-wyszukiwanie-sciezek Artykuł opisuje algorytm A* do efektywnego wyszukiwania najkrótszych ścieżek w grafach, który łączy Dijkstrę z heurystyką odległości, dzięki czemu eksploruje tylko obiecujące ścieżki i znacząco zmniejsza liczbę iteracji przy nieujemnych wagach. Wyjaśniono rolę funkcji heurystycznej (przybliżającej odległość do celu) i przedstawiono typowe heurystyki: euklidesową, Manhattan, Czebyszewa dla siatek/gier oraz haversine i przybliżenie walcowe dla map geograficznych. Opisano krok po kroku implementację A*: inicjalizacja zbioru do sprawdzenia (open set), tablic poprzedników, rzeczywistych odległości i przewidywanych odległości, pętlę wyboru wierzchołka o najmniejszym f = g + h, aktualizację sąsiadów i rekonstrukcję ścieżki. Wskazano kompromis: A* zwykle szybki pod względem obliczeń, ale pamięciożerny, co doprowadziło do wariantów oszczędzających pamięć (IDA*, SMA*) oraz rozszerzeń do specyficznych zastosowań (D*, ALT, Theta*, ANYA). Zamieszczono przykładową implementację w JavaScript i omówiono praktyczne zastosowania A* w mapowaniu i grach (Organic Maps, GraphHopper, OpenTripPlanner, Godot, CryEngine, Unreal), podkreślając, że dobór heurystyki decyduje o efektywności. ## Rysowanie grafów — algorytmy https://swistak.codes/post/rysowanie-grafow-algorytmy Artykuł omawia algorytmikę rysowania grafów ze szczególnym naciskiem na rozmieszczanie wierzchołków: dlaczego wizualizujemy grafy i typowe zastosowania (diagramy UML, schematy baz danych, organizacje, sieci społeczne, grafy wiedzy, analiza procesów). Opisuje proste układy: losowe (szybkie, przydatne jako baza animacji lub dla bardzo dużych/głównych danych) i siatkę (deterministyczne, dobre dla niepołączonych węzłów lub sekwencji). Omawia układy okrągłe i koncentryczne oraz algorytmy minimalizujące przecięcia krawędzi (Mäkinen, CIRCULAR, Baur–Brandes, AVSDF). Szczegółowo przedstawia klasyczne force-directed (symulacje sił: sprężyny/Coulomb) — zalety (naturalna klasteryzacja, dobra dla sieci społecznych) i wady (koszt obliczeniowy, granica praktyczna ~100 wierzchołków); przykłady: Tutte, Kamada–Kawai, CoSE, CoLa. Opisuje też warstwowe algorytmy dla grafów skierowanych i hierarchii bazujące na metodzie Sugiyamy (etapy: warstwowanie, sztuczne wierzchołki, redukcja przecięć, ustalanie pozycji). Wspomina hybrydowe i specjalistyczne podejścia (CiSE, Spread z teselacją Voronoja, drzewo hiperboliczne, fishbone, spirala, Cactus Group Layout) oraz narzędzia/implementacje (Cytoscape, GoJS, yFiles) i literaturę referencyjną, w tym „Handbook of Graph Drawing and Visualization”. ## Problem skoczka szachowego https://swistak.codes/post/problem-skoczka-szachowego Artykuł omawia problem skoczka (knight's tour): znalezienie sekwencji ruchów skoczka odwiedzającej każde pole planszy dokładnie raz (warianty: ścieżka otwarta/zamknięta, ścieżka bez przecięć). Pokazuje redukcję do problemu grafowego — pola jako wierzchołki, legalne ruchy skoczka jako krawędzie — co sprowadza zadanie do znalezienia ścieżki lub cyklu Hamiltona. Podstawowe podejście to przeszukiwanie z nawrotami; efektywniejsza heurystyka to reguła Warnsdorffa: zawsze przechodź do nieodwiedzonego sąsiada o najmniejszym stopniu. Omawiane są ulepszenia tej reguły (Roth, Squirrel, Pohl); autor skupia się na metodzie Pohla (Pohl–Warnsdorff), która przy remisie rekurencyjnie sumuje stopnie sąsiadów i wybiera minimalną sumę (dla skoczka k=1), co zwiększa skuteczność i działa też na ogólnych grafach (Pohl zastosował ją m.in. do grafu Tutte'a). Podano też prostą implementację w JavaScript (funkcje getNodeWithMinDegree i findKnightsTour, parametr recursionDepth steruje głębokością tie‑breakingu). Metoda jest szybka (liniowa względem rozważanej głębokości) i praktyczna, ale nie gwarantuje znalezienia rozwiązania we wszystkich przypadkach. Literatura: Pohl 1967, Squirrel & Cull 1996, Roth, Ganzfried & Cull. ## Liczby rzymskie https://swistak.codes/post/liczby-rzymskie Artykuł opisuje rzymski system zapisu liczb: system addytywny z regułą odejmowania (mniejszy symbol przed większym oznacza odjęcie), podstawowe symbole i wartości (I,V,X,L,C,D,M) oraz ograniczenie standardowego zapisu do zakresu 1–3999 (największa liczba MMMCMXCIX). Wzmiankowane są historyczne i regionalne odstępstwa (np. IIII na zegarach, dodatkowe symbole, różne sposoby zapisu dużych liczb, implementacje jak Excel) oraz zapisy ułamków i brak zera. Przedstawione są trzy zadania algorytmiczne i ich proste rozwiązania w JavaScripcie: konwersja z rzymskiego na dziesiętny (przechodzenie od lewej, lookahead dla odejmowania), konwersja z dziesiętnego na rzymski (greedy z tabelą symboli i par odejmujących) oraz walidacja poprawności zapisu przy pomocy wyrażenia regularnego ^M{0,3}(C[MD]|D?C{0,3})(X[CL]|L?X{0,3})(I[XV]|V?I{0,3})$. Autor celowo ignoruje niestandardowe odmiany i zapisy spoza 1–3999, podkreślając praktyczne, czytelne algorytmy przystosowane do kursów programowania. ## Podstawy algorytmiki: największy wspólny dzielnik https://swistak.codes/post/najwiekszy-wspolny-dzielnik Artykuł opisuje problem największego wspólnego dzielnika (NWD) — jego definicję, podstawowe własności (przemienność, łączność, NWD(a,0)=|a|, własność skalarna) oraz związek z najmniejszą wspólną wielokrotnością (NWW(a,b)=a·b/NWD(a,b)). Przedstawione są trzy podejścia do obliczania NWD: rozkład na czynniki pierwsze (intuicyjny, lecz niepraktyczny), klasyczny algorytm Euklidesa w wersji z odejmowaniem, zoptymalizowana wersja z operacją modulo (iteracyjna i rekurencyjna) oraz binarny algorytm NWD (Steina) wykorzystujący reguły dla parzystości i przesunięcia bitowe dla szybszej implementacji. Omówiono także implikacje implementacyjne (obsługa liczb ujemnych, użycie przesunięć zamiast dzielenia przez 2) oraz fakt, że na bazie algorytmu Euklidesa powstał rozszerzony algorytm znajdujący zastosowanie w kryptografii. Literaturę uzupełniają odwołania do klasycznych podręczników (Cormen et al., Knuth) i źródeł dotyczących binary GCD. ## Iteracja — co to jest? https://swistak.codes/post/iteracja-co-to-jest Iteracja to wielokrotne powtarzanie procedury sterowane warunkiem (określona liczba, stan systemu lub sygnał zewnętrzny); może być skończona lub nieskończona, a warunek sprawdza się przed lub po przebiegu. W programowaniu istnieją klasyczne konstrukcje: while (warunek przed), do/while (sprawdzenie po pierwszej iteracji) i for (różne formy: licznikowa, C‑podobna z inicjalizacją/warunkiem/inkrementacją — de facto wariant while). Na najniższym poziomie wszystkie pętle są realizowane przez skoki/rozgałęzienia (jmp, je itd. w asemblerze); kompilatory zamieniają wysokopoziomowe konstrukcje na takie skoki. Instrukcje sterujące to continue (przeskok do następnej iteracji) i break (przerwanie pętli); wielopoziomowy exit można uzyskać przez goto, etykiety, lub return. Rekurencja pełni rolę iteracji w paradygmatach funkcyjnych. Iteratory/enumeratorzy i pętle for‑each (JS, Java, C#, C++) upraszczają przechodzenie po kolekcjach; generatory (yield) tworzą leniwe/ograniczone lub nieskończone sekwencje. Funkcje wyższego rzędu (map/filter/reduce/where/any/all/forEach) oraz języki zapytań (SQL, LINQ, Cypher) realizują iteracje deklaratywnie i kompilują plany wykonań. Artykuł omawia też praktyki użycia break/continue/goto, kompilację pętli i odsyła do tematów pominiętych: inwarianty pętli, logika Hoare’a i optymalizacja. ## Podstawy algorytmiki: szybkie potęgowanie https://swistak.codes/post/szybkie-potegowanie Artykuł wyjaśnia algorytm szybkiego potęgowania (exponentiation by squaring / binary exponentiation): zamiast wykonywać n mnożeń (O(n)), wykorzystuje własności potęgowania, aby obliczyć a^n w O(log n) mnożeń przez rekurencyjne lub iteracyjne podnoszenie do kwadratu i dopasowywanie, gdy wykładnik jest nieparzysty. Omawia definicje potęg dla wykładników naturalnych, całkowitych i wymiernych oraz przypadki związane z zerem (w tym 0^0). Prezentuje warianty implementacji: proste (iteracyjne i rekurencyjne), zoptymalizowane rekurencyjne, iteracyjne według definicji, wersję binarną korzystającą z operacji bitowych (n & 1, n >> 1) oraz specjalny szybki sposób dla potęg dwójki (przesunięcie bitowe <<). Wspomina o zastosowaniu do potęgowania modularnego i historycznym pochodzeniu (Chanshsutra). Autor przeprowadza benchmarki w JavaScript dla typów Number i BigInt: dla Number różnice między implementacjami są niewielkie, dla BigInt widać wyraźne przewagi wbudowanej funkcji i różne zachowanie wersji binarnej (operacje bitowe są mniej efektywne, gdy są emulowane). Wniosek: szybkie potęgowanie to prosta i użyteczna technika zmniejszająca liczbę mnożeń, ale w praktyce warto korzystać z wbudowanych operatorów/funkcji języka, chyba że potrzebujemy kontrolowanej implementacji (np. modularnej). ## Pierwiastkowanie https://swistak.codes/post/pierwiastkowanie Artykuł wyjaśnia pierwiastkowanie jako odwrotność potęgowania i rozróżnia pierwiastek arytmetyczny (jedno dodatnie rozwiązanie dla nieujemnego a). Pokazuje redukcję pierwiastkowania do znalezienia miejsca zerowego funkcji f(x)=x^k−a i opisuje metodę Newtona‑Raphsona jako iteracyjny algorytm z ogólną formułą xn+1 = xn − f(xn)/f′(xn). Dla pierwiastka kwadratowego daje to klasyczny wzór xn+1 = 1/2 (xn + a/xn) (metoda babilońska/Herona), a dla pierwiastka stopnia k wzór xn+1 = (1/k)((k−1)xn + a/xn^{k−1}). Omawiane są kryteria stopu (np. |f(xn)| ≤ ε lub |xn−xn−1| ≤ ε) oraz praktyczne wybory ziarna początkowego (np. x0=1, heurystyka oparta na liczbie cyfr) i typowe liczby iteracji (kilka iteracji dla wysokiej dokładności). Podano też uproszczoną, geometryczną interpretację (przekształcanie prostokąta w kwadrat) oraz przykładowe implementacje w JavaScripcie. Na koniec wymieniono alternatywne metody obliczania pierwiastków: Bakhshali, algorytm cyfry po cyfrze, Goldschmidt, szeregi Taylora, metoda Halleya oraz optymalizacje bitowe dla reprezentacji IEEE‑754. ## Jak narysować zegar analogowy? https://swistak.codes/post/jak-narysowac-zegar-analogowy Artykuł opisuje, jak za pomocą podstawowej matematyki i trygonometrii (x = r·cosα, y = r·sinα) stworzyć animowany zegar analogowy. Zegarek traktowany jest jako zestaw kół o wspólnym środku — każda wskazówka to punkt na okręgu wyznaczony kątem; kąt przeliczany jest z godzin/minut/sekund (z uwzględnieniem ułamków dla płynnego ruchu) i przesunięty o −90° (−π/2), a współrzędne przesunięte o środek canvasu. Implementacja w JavaScript wykorzystuje , requestAnimationFrame, funkcje getPosition(angle,radius), drawHand oraz specjalizowane drawHoursHand/drawMinutesHand/drawSecondsHand; autor opisuje też rysowanie tarczy: obwód, znaczniki minut/co 5 minut i numery godzin. Podane są praktyczne wskazówki środowiskowe (CodePen/CodeSandbox/StackBlitz) oraz wzmianka o porcie na Pythona z pygame i uwagach o antyaliasingu. Tekst ilustruje podejście: uogólnienie problemu, zastosowanie trygonometrii i praktyczną realizację w kodzie. ## Jak narysować spiralę? https://swistak.codes/post/jak-narysowac-spirale Artykuł wyjaśnia matematykę spirali Archimedesa i pokazuje, jak ją narysować w JavaScripcie na elemencie . Spirala Archimedesa w zapisie biegunowym ma postać r = aθ + b, gdzie a kontroluje odstęp między zwojami, a b przesunięcie od środka; współrzędne kartezjańskie uzyskujemy przez x = r cosθ, y = r sinθ. Podano też uogólnienie r = a θ^{1/n} + b (n=1 Archimedes, n=2 Fermat, n=-1 spirala hiperboliczna, n=-2 lituus) oraz spirale logarytmiczną r = a e^{bθ} i złotą r = φ^{2θ/π}. Implementacja opisuje: przygotowanie , funkcje getRadius(i parametry) i polarToCartesian, stałe (MAX_RADIUS, A, B, ANGLE_INCREMENT), iteracyjną pętlę while obliczającą punkty aż do maksymalnego promienia oraz rysowanie odcinków za pomocą moveTo/lineTo i stroke. Wskazówka: aby narysować inną spiralę, wystarczy zmienić funkcję getRadius; autor udostępnia przykłady na CodePen i zachęca do eksperymentów z układem biegunowym. ## Sumy kontrolne https://swistak.codes/post/sumy-kontrolne Artykuł wyjaśnia, czym są sumy kontrolne: krótkie bloki danych dołączane do danych w celu wykrycia błędów (integrity), niekoniecznie ich autentyczności. Omawia pojęcie kolizji oraz fakt, że różne algorytmy mają różny stopień odporności na przypadkowe i celowe zmiany (część kodów pełni też funkcje korekcji błędów). Przykłady cyfr kontrolnych: PESEL (wagi 1,3,7,9,1,3,7,9,1,3 i obliczenie moduł 10), NIP (wagi 6,5,7,2,3,4,5,6,7 i modulo 11 — liczba pierwsza zmniejsza kolizje), ISBN‑13/EAN‑13 (wagi 1/3) oraz algorytm Luhna (mod 10, stosowany w kartach kredytowych; mnożenie co drugiej cyfry przez 2, suma cyfr lub odejmowanie 9). Wzmiankowane są też rozszerzony Luhn oraz algorytmy Verhoeffa i Damm. Dla danych binarnych opisane są: bit parzystości (różne implementacje XOR/shift), Adler‑32 (dwie sumy A i B modulo 65521), Fletcher, CRC (najpopularniejszy, oparty na wielomianie, szeroko w sieciach i z możliwością prostej korekcji) oraz checksum IPv4. Na koniec omówione są kryptograficzne funkcje skrótu (MD5, SHA‑1, SHA‑256) używane do weryfikacji plików — MD5/SHA‑1 podatne na złośliwe kolizje, dziś preferowane SHA‑256. Podsumowanie: sumy kontrolne skutecznie wykrywają przypadkowe błędy; odporność na ataki zależy od rodzaju algorytmu (najbezpieczniejsze to funkcje kryptograficzne). ## Algorytmika gier — obrót do punktu https://swistak.codes/post/algorytmika-gier-obrot-do-punktu Krótko: aby obrócić obiekt (x1,y1) w kierunku punktu (x2,y2) wystarczy obliczyć kąt: Math.atan2(y2 - y1, x2 - x1) (w JavaScript kolejność argumentów to najpierw y, potem x). Jeśli potrzebujesz stopni: *180/Math.PI; możesz też dodać/odjąć stały kąt (np. π/2), gdy grafika domyślnie nie „patrzy” w prawo. atan2 jest 2‑argumentowym arcus tangensem, który rozwiązuje problem nieokreśloności arctan(y/x) przez uwzględnienie ćwiartki układu i przypadków x=0, y=0 (działa też poprawnie przy ujemnych współrzędnych). Na ekranie oś Y zwykle rośnie w dół — trzeba to uwzględnić, ale obliczenia kątów pozostają takie same. Powiązanie z układem biegunowym: r = sqrt(x^2+y^2), θ = atan2(y,x). Funkcja atan2 powstała historycznie w kontekście obliczeń naukowych (m.in. Fortran) i jest praktycznym narzędziem do obracania obiektów w grach i wizualizacjach. ## Codzienny wtręt programisty (1-30) https://swistak.codes/offtopic/codzienny-wtret-programisty Zbiór 30 krótkich porad dla początkujących i praktyków IT z serii „Codzienny wtręt programisty”: praktyczne wskazówki obejmują wybór struktur danych (używaj map/słowników gdy odwołujesz się po id), ucz się myślenia algorytmicznego, a nie tylko konkretnej technologii, i poznaj bibliotekę standardową języka; uwagi o precyzji liczb zmiennoprzecinkowych, ważeniu składowych przy konwersji na szarość, rolę matematyki w programowaniu oraz praktyczne zastosowania grafów; narzędzia i praktyki: Docker, sprawdzone gotowce, wyrażenia regularne, generowanie bezpiecznych ID (crypto.randomUUID/uuid/nanoid) i biblioteki do rysowania grafów w JS; front-endowe dobre praktyki: semantyczne tagi (button/a zamiast klikalnych div), dostępność, lista kluczowych zagadnień frontendowych i Reactowych; porady zawodowe: nie musisz znać wszystkiego, podejmuj decyzje i proaktywnie proponuj rozwiązania, nie rozpraszaj się wieloma zadaniami naraz, rób przerwy i nie pracuj nadmiarowo; dodatkowo: AI jako narzędzie, krytyczne podejście do rekomendacji w sieci, kreatywne pomysły jak programowanie muzyki (Sonic Pi) oraz drobne praktyczne tipy i linki do dalszej lektury na autorowym blogu. ## Dziel i zwyciężaj a mnożenie https://swistak.codes/post/dziel-i-zwyciezaj-a-mnozenie Artykuł opisuje algorytm Karacuby (Karatsuba) — zastosowanie strategii „dziel i zwyciężaj” do szybszego mnożenia dużych liczb: zamiast klasycznego mnożenia pisemnego O(n^2) osiąga złożoność O(n^{log2 3}) ≈ O(n^{1.58}). Idea: rozbić liczby a i b na połowy a1,a0 i b1,b0 (a=a1B^m+a0), obliczyć z0=a0b0, z2=a1b1 oraz z1=(a0+a1)(b0+b1)−z2−z0, co zmniejsza liczbę mnożeń z czterech do trzech i stosować rekurencję aż do prostego przypadku (np. jednocyfrowego). Autor zamieszcza przykładowe obliczenie i prostą implementację w JavaScripcie (uwagi: usuwanie zer wiodących, wybór m jako połowy długości, konwersje/BigInt dla dużych liczb). Wspomniane są też szybsze algorytmy (Toom–Cook, Schönhage–Strassen) oraz nowszy wynik Harvey’a i van der Hoevena z 2021 r. złożoności O(n log n). ## Rozwiązujemy maturę próbną 2022 z informatyki https://swistak.codes/post/matura-probna-2022 Artykuł prezentuje przykładowe rozwiązania zadań z próbnej matury 2022 z informatyki (pominięto zadania z Excela i baz danych) z implementacjami w Javie (OpenJDK 17). Autor opisuje wspólny szkielet projektu (interfejs Task, metody odczytu/zapisu plików) i szczegółowo rozwiązuje zadania: 1) operacje na ciągu znaków — 1.1 liczenie zmian między sąsiednimi znakami, 1.2 symulacja punktacji z warunkiem zwycięstwa (>=1000 i przewaga >=3), 1.3 zliczanie serii >=10 i najdłuższa seria; 2) zadania o drzewie binarnym — rozpoznanie drzewa, rysuj(x)/rekurencja, liczba krawędzi N−1, głębokość ⌊log2 N⌋ oraz funkcja sprawdzająca osiągalność węzła; 3) liczby pierwsze — omówienie sita Eratostenesa (implementacja i optymalizacje), zastosowania: 3.2 sprawdzenie czy n−1 jest pierwsze, 3.3 liczenie rozkładów parzystych na sumy dwóch liczb pierwszych (prosta metoda z sitem), 3.4 zliczanie wystąpień cyfr w zapisie szesnastkowym (Integer.toHexString). Dodatkowo krótkie odpowiedzi teoretyczne: protokoły (SMTP, FTP, HTTPS, IMAP), szyfrowanie symetryczne vs asymetryczne, oraz przykłady działań i konwersji w systemie czwórkowym. Kod i przykłady dostępne na OnlineGDB; autor rekomenduje proste, czytelne podejście, IDE (IntelliJ/PyCharm) i ostrzega przed pułapkami implementacyjnymi i rozbieżnościami z kluczem oceny. ## Odwrotna notacja polska https://swistak.codes/post/odwrotna-notacja-polska Artykuł wyjaśnia odwrotną notację polską (ONP, postfiksową), porównując ją krótko z notacją infiksową (z nawiasami) i notacją polską (prefiksową). ONP eliminuje nawiasy i jest wygodna algorytmicznie — wyrażenia czyta się od lewej, a napotkany operator stosuje się do dwóch poprzednich elementów. Schemat obliczania opiera się na stosie (LIFO): liczby pushujemy na stos, przy operatorze popujemy odpowiednią liczbę argumentów, wykonujemy operację i pushujemy wynik; na końcu na stosie powinna zostać pojedyncza wartość. Przykład: 6/2·(2+1) zapiszemy jako 6 2 / 2 1 + · i obliczamy kolejno 3 2 1 + · → 3 3 · → 9. Artykuł pokazuje też prostą implementację w JavaScript (parsowanie symboli, pop/ push, obsługa +,-,*,/), oraz zaznacza, że algorytm łatwo rozszerzyć na funkcje jednoargumentowe i inne operatory. Historycznie ONP była używana już w komputerze Z3 (1941) i znalazła popularne zastosowanie m.in. w kalkulatorach HP oraz w informatyce (konwersje infiks → ONP, S-wyrażenia w Lispu są powiązane z notacją prefiksową). ## Obliczanie wyrażeń matematycznych https://swistak.codes/post/obliczanie-wyrazen-matematycznych Artykuł opisuje konwersję wyrażeń infiksowych na odwrotną notację polską (ONP/RPN) za pomocą algorytmu stacji rozrządowej (shunting yard) E. Dijkstry. Algorytm przetwarza symbole od lewej do prawej, używa stosu, dodaje liczby bezpośrednio do wyniku, a operatory i nawiasy obsługuje zgodnie z priorytetami i asocjacyjnością (uwaga: potęgowanie jest prawostronnie łączne). Podano szczegółowe kroki działania oraz przykład konwersji 6/2*(2+1) → 6 2 / 2 1 + *. Zamieszczono też prostą implementację w JavaScripcie (mapa priorytetów, obsługa +,-,*,/ i nawiasów) oraz wskazówkę, by po konwersji użyć wcześniej opisanego algorytmu do obliczania ONP. Omówiono typowe pułapki przy przyjmowaniu surowego ciągu od użytkownika: tokenizacja, spacje, pomijane mnożenie, rozróżnienie minusu unarnego i binarnego oraz różne separatory dziesiętne. Całość ma złożoność liniową O(n), a rozszerzenia (funkcje, dodatkowe operatory) wymagają niewielkich modyfikacji. ## (prawie) Codzienny wtręt programisty (31-40) https://swistak.codes/offtopic/prawie-codzienny-wtret-programisty Zbiór krótkich wpisów (31–40) z serii „(prawie) Codzienny wtręt programisty”: #31 – cztery sposoby zaokrąglania (round, floor, ceil, trunc) i różne zachowania dla liczb ujemnych oraz przypadków .5; #32 – trzy pułapki nauki w IT: wkuwanie zamiast zrozumienia, kopiowanie gotowych rozwiązań bez teorii, bierne szkolenia dla „papierka”; #33 – reszta z dzielenia dla liczb ujemnych działa różnie w różnych językach (Dart, Python, JavaScript), warto znać różnice i matematyczną definicję; #34 – nieoczywiste korzyści testów jednostkowych: żywa dokumentacja, wymuszanie małych funkcji i dobrych konwencji architektonicznych; #35 – przy zakładaniu projektu JS warto skonfigurować ESLint, Prettier i EditorConfig oraz integrować je w CI, pre-commit hookach i wtyczkach edytora; #36 – złożoność cyklomatyczna mierzy liczbę ścieżek w funkcji, wpływa na liczbę wymaganych testów i branch coverage; #37 – 3 lata świstak.codes: migracja z WordPress do Next.js, statystyki odwiedzin i liczba artykułów; #38 – phind.com jako wyszukiwarka dla programistów oparta na GPT‑4 łącząca odpowiedzi z linkami do źródeł (StackOverflow, dokumentacje); #39 – sposoby usuwania domyślnych stylów przeglądarki: reset/normalize/modern-css-reset oraz CSS all: unset dla pojedynczego elementu; #40 – powtarzanie kodu w testach jest akceptowalne i często pożądane, bo testy pełnią funkcję dokumentacji — lepiej opisywać i oddzielać przypadki testowe niż upakowywać je w jeden zbiorczy test. ## Logika dla informatyków — podstawy https://swistak.codes/post/podstawy-logiki Artykuł przedstawia podstawy logiki matematycznej z perspektywy informatycznej: cel jej nauki dla programistów (formalny opis matematyki, warunki w kodzie, teoria zbiorów, kwantyfikatory, semantyka języków, typy i programowanie logiczne). Omawia pojęcia pierwotne i aksjomaty oraz rachunek zdań z dwiema wartościami logicznymi (prawda/fałsz) i tablicami prawdy. Szczegółowo opisano podstawowe spójniki (negacja, koniunkcja, alternatywa, implikacja, równoważność) oraz dodatkowe użyteczne w informatyce/elektronice (XOR, NOR, NAND), ich własności, zapisy symboliczne i odpowiedniki w programowaniu (operatory logiczne i bitowe) z przykładami w JavaScript. Wyjaśniono pojęcia tautologii i aksjomatów, prawa De Morgana, rozdzielności i łączności oraz metodę dowodzenia tautologii przez tabele prawdy. Przedstawiono praktyczne zastosowania operacji bitowych: flagi (ustawianie, sprawdzanie, resetowanie), sprawdzanie parzystości i użycie XOR w prostych szyfrach i kryptografii. Omówiono też uniwersalność bramek NOR i NAND (możliwość złożenia dowolnej funkcji logicznej) i krótko wskazano dalsze kierunki zgłębiania logiki w informatyce. ## Logika dla informatyków — kwantyfikatory https://swistak.codes/post/kwantyfikatory Artykuł opisuje rachunek kwantyfikatorów pod kątem zastosowań w informatyce: podstawowe kwantyfikatory uniwersalny (∀ — „dla każdego”) i egzystencjalny (∃ — „istnieje”), ich programistyczne odpowiedniki (np. every()/All(), some()/Any(), First/Single/SingleOrDefault) oraz wariant ścisły ∃! (istnieje dokładnie jeden) i sposoby jego implementacji. Omawia praktyczne tautologie i prawa: prawa de Morgana dla kwantyfikatorów, podwójną negację i możliwość definiowania jednego kwantyfikatora przez drugi, pełną rozdzielność (∀ względem ∧, ∃ względem ∨) oraz niepełne prawa rozdzielności, prawa przestawiania (komutatywność kwantyfikatorów tego samego typu) i niepełne przestawianie mieszane. Autor ilustruje zastosowania i optymalizacje w kodzie JavaScript/C# (przykłady every/some, łączenie warunków, implementacje single) i zwraca uwagę na kompromis między czytelnością a wydajnością podczas przekształceń logicznych. Końcowe wnioski: znajomość tych praw pozwala upraszczać, optymalizować i lepiej rozumieć warunki operujące na kolekcjach; dowodów tu nie podano, podane są odwołania do literatury. ## Logika dla informatyków — algebra zbiorów https://swistak.codes/post/algebra-zbiorow Artykuł przedstawia podstawy algebry zbiorów z perspektywy informatycznej. Opisuje pojęcie zbioru, notację (a∈A, ∅, uniwersum Ω) oraz sposoby definiowania zbiorów (wypisanie elementów i zapis przez właściwość). Pokazuje wizualizację za pomocą diagramów Venna i podstawowe relacje między zbiorami: rozłączność, przecięcie, równość i inkluzję (⊆, ⊂, ⊇) wraz z formalnymi definicjami zawierania i równości. Główna część omawia operacje na zbiorach i ich zastosowania w programowaniu: suma/unia (A∪B, operator |, Python .union(), _.union), iloczyn/przecięcie (A∩B, &, .intersection(), _.intersection), różnica (A\B, -, .difference(), _.difference), dopełnienie (A′ = Ω\A) oraz różnica symetryczna (A△B, ^, .symmetric_difference(), _.xor). Przedstawiony jest też iloczyn kartezjański (A×B — uporządkowane pary) oraz implementacje tych operacji w Pythonie i JavaScript (własne funkcje i użycie Lodash). Relacje definiowane są jako podzbiory iloczynu kartezjańskiego; funkcje są przykładem relacji o dodatkowych warunkach (zip jako prosta relacja). Wspomniane są podstawowe prawa teorii zbiorów (łączność, rozdzielność, prawa de Morgana, własności dotyczące zbioru pustego). Konkluzja: znajomość rachunku zbiorów (wraz z rachunkiem zdań i kwantyfikatorami) jest przydatna w programowaniu i łączy logikę z praktycznymi operacjami na kolekcjach. ## Teoria zbiorów a TypeScript https://swistak.codes/post/teoria-zbiorow-typescript Artykuł pokazuje, jak pojęcia z algebry zbiorów i logiki matematycznej przekładają się na system typów TypeScript. Typy traktowane są jak zbiory: string, number, boolean to zbiory wartości; any/unknown pełnią rolę uniwersum (unknown jako prawdziwe nadtyp), a never to zbiór pusty; null i undefined to osobne jednoelementowe typy. Typy literalne to singletony (podzbiory), a operator | realizuje sumę zbiorów (unia) — przydatną do tworzenia restrykcyjnych zbiorów wartości, symulowania enumów i oznaczania opcjonalności (| undefined). Operator & realizuje iloczyn (część wspólną): dla prostych typów często daje never, ale w przypadku literal i any/unknown zachowuje się inaczej; dla typów obiektowych & działa jak łączenie pól (odpowiednik dziedziczenia), wymagając spełnienia obu kształtów, a konflikty pól mogą prowadzić do never. Typy obiektowe opisują pary klucz‑typ, obsługują pola opcjonalne (?), indeksy ([k: string]: ...), a unie obiektów pozwalają na wartość zgodną z którymkolwiek kształtem zaś przecięcia łączą wymagania. Autor podkreśla, że spojrzenie przez pryzmat teorii zbiorów ułatwia zrozumienie zachowań systemu typów TypeScript i wyjaśnia praktyczne zastosowania tych konstrukcji. ## Mierzenie podobieństwa ciągów znaków https://swistak.codes/post/podobienstwo-ciagow-znakow Artykuł opisuje metryki odmienności ciągów znaków (string metrics), ze szczególnym uwzględnieniem odległości edycyjnej. Metryka to funkcja odległości spełniająca m.in. nierówność trójkąta; w tekście przedstawiono najczęściej używane operacje edycyjne: wstawienie, usunięcie, zamiana i transpozycja. Odległość Hamminga mierzy liczbę różnic na tych samych pozycjach dla ciągów równej długości (tylko zamiany). Odległość Levenshteina (wliczająca wstawienia, usunięcia i zamiany) zdefiniowano rekurencyjnie i omówiono jej efektywną iteracyjną implementację algorytmem Wagnera–Fischera (programowanie dynamiczne), o złożoności czasowej O(|a|·|b|) i możliwościach optymalizacji pamięciowych (przechowywanie tylko ostatniego wiersza, przejścia po przekątnej). Wspomniano też warianty i alternatywy: Damerau–Levenshtein (transpozycje), LCS (tylko wstawienia/usunięcia) oraz Jaro–Winkler (normalizowana miara podobieństwa, nie spełnia nierówności trójkąta). Zastosowania obejmują przybliżone dopasowanie i korektę literówek (fuzzy search), algorytmy dopasowania sekwencji w analizie DNA (Hirschberg, Smith–Waterman) oraz ogólne porównywanie tekstów. ## Podstawy działania UI — wzorzec obserwator https://swistak.codes/post/obserwator Artykuł wyjaśnia wzorzec obserwator (Observer) jako podstawę reaktywności UI: definiuje zależność jeden-do-wielu, gdzie zmiana stanu Subject/Observable automatycznie powiadamia obserwatorów (Observer), opisując też role ConcreteSubject i ConcreteObserver. Omówione są korzyści architektoniczne (decoupling, łatwiejsze utrzymanie, równoległa praca zespołów, prostsze testy) oraz związek z MVC/MVVM. Przedstawiono wzorcową i uproszczoną implementację w TypeScript (również odniesienie do Kotlina), warianty pull vs push oraz praktyczne uproszczenia wykorzystujące callbacki. Wskazano popularne biblioteki i podejścia: ReactiveX/RxJS jako gotowe implementacje oraz signals (np. w Preact, Solid, Angular), które integrują obserwacje z frameworkiem i ukrywają mechanizm subskrypcji. Podsumowanie: mimo różnych nazw i implementacji, podstawowa idea pozostaje niezmienna i warto ją znać, by zrozumieć działanie nowoczesnych frameworków UI. ## Wzorzec obserwator w UI — podejścia scentralizowane https://swistak.codes/post/scentralizowany-obserwator Artykuł opisuje scentralizowane podejścia do wzorca obserwator, koncentrując się na architekturze Publish‑Subscribe (Pub‑Sub) jako modelu z brokerem wiadomości i kanałami, który odseparowuje publikujących od subskrybentów. Wyjaśnia różnicę między wzorcem architektonicznym a projektowym oraz omawia przykłady implementacji (RabbitMQ, newslettery, serwisy społecznościowe) i kwestię retencji wiadomości. Pokazuje prostą implementację brokera w TypeScript (subscribe/unsubscribe/sendMessage) oraz wersję opartą na RxJS (Subject z filtrowaniem kanałów). Przedstawia też związek z architekturą sterowaną zdarzeniami: event loop, event handlers i dispatcher (dyspozytor/ broker), z praktycznymi przykładami w JavaScript używającymi EventTarget, CustomEvent i postMessage do iframe. Wnioski: zarówno podstawowy observer, jak i scentralizowany pub‑sub są kluczowe przy budowie UI i systemów rozproszonych; wybór między wieloma tematami a centralnym brokerem zależy od potrzeb projektu. ## Wzorzec obserwator w UI — Flux i Redux https://swistak.codes/post/flux-redux Artykuł kontynuuje serię o wzorcu obserwator w kontekście UI, przypomina rozróżnienie stanu lokalnego i globalnego oraz opisuje architekturę Flux (store, dispatcher, view) i jej przepływ danych, ilustrując implementację przykładową aplikacją pobierającą dane o Pikachu z PokeApi (implementacja w RxJS). Następnie omawia Redux jako ewolucję Fluksa: pojedynczy store, czyste reduktory (funkcje zwracające nowy stan), combineReducers i selektory, oraz pokazuje przykład przepisywania aplikacji na Redux. Porusza też współczesne praktyki: Redux Toolkit, NgRx (Angular), oraz alternatywy i biblioteki zarządzania stanem inspirowane lub upraszczające podejście reduksowe — m.in. Zustand, Pinia, Akita, mobx-state-tree, Elf, Jotai. Końcowe wnioski podkreślają, że nie ma uniwersalnego rozwiązania — wybór zależy od kontekstu — i zachęca do praktycznych eksperymentów oraz poszerzania wiedzy (CQRS, Event Sourcing). Literatura i linki do przykładów na StackBlitz i dokumentacji Redux/Flux dołączone. ## Krzywe Béziera https://swistak.codes/post/krzywe-beziera Artykuł opisuje matematykę i implementację krzywych Béziera: historię (Pierre Bézier, de Casteljau), formę parametryczną i bazę teoretyczną. Krzywe wielomianowe definiuje się jako B(t)=∑_{i=0}^n P_i · b_{n,i}(t) dla 0≤t≤1, gdzie wielomiany bazowe Bernsteina b_{n,k}(t)=C(n,k) t^k (1−t)^{n−k} (C(n,k) — symbol Newtona, obliczalny przez trójkąt Pascala). Omówione są przypadki liniowe, kwadratowe i sześcienne oraz własności: krzywa zaczyna się w P0, kończy w Pn, zawiera się w otoczce wypukłej punktów kontrolnych, można ją dzielić i transformować afinicznie; wyższe stopnie mogą się samoistnie przecinać, a zmiana jednego punktu wpływa na całość. Wspomniano wymierne krzywe Béziera z wagami w_i, które pozwalają opisać stożkowe (okręgi, elipsy itp.). Po stronie informatycznej przedstawiono dwa podejścia do obliczeń: bezpośrednie (forma Bernsteina, wymaga symbolu Newtona i potęgowania) oraz algorytm de Casteljau (iteracyjna interpolacja liniowa, numerycznie stabilna), wraz z przykładowymi implementacjami w JavaScripcie; wskazano też alternatywy (reprezentacja macierzowa, optymalizacje, GPU). Podsumowanie: krzywe Béziera są proste matematycznie, powszechne w grafice wektorowej i oferują różne algorytmy obliczeniowe o różnych własnościach numerycznych i wydajnościowych. ## Otoczka wypukła https://swistak.codes/post/otoczka-wypukla Artykuł wyjaśnia pojęcie zbioru wypukłego i otoczki wypukłej oraz przedstawia algorytm Grahama (Graham's scan) do wyznaczania otoczki wypukłej punktów na płaszczyźnie. Algorytm: wybierz punkt startowy P0 (najniższe y, przy remisie najniższe x), posortuj pozostałe punkty rosnąco według kąta względem P0 (np. atan2), przy równych kątach zostaw tylko punkt najdalszy, a następnie przechodząc po posortowanej liście używaj stosu i eliminuj ostatni punkt, gdy nie występuje lewoskręt (test ccw przy pomocy iloczynu wektorowego). Złożoność czasowa O(n log n) (dominowane przez sortowanie); przejście po punktach jest O(n). Omówiono praktyczne implementacje (różne sposoby porównywania kątów, uwagi o precyzji zmiennoprzecinkowej i alternatywne metryki odległości) oraz podano funkcję ccw (cross product) do wykrywania skrętów. Wspomniano alternatywne algorytmy: Jarvisa, Quickhull, Andrew’s monotone chain, oraz typowe zastosowania otoczek wypukłych: wizualizacja danych, granice na mapach, upraszczanie obiektów do detekcji kolizji w grafice i grach, rozpoznawanie obrazów i inne. ## Funkcja Ackermanna https://swistak.codes/post/funkcja-ackermanna Artykuł wyjaśnia funkcję Ackermanna: jej historię (Ackermann i Sudan), matematyczną definicję i znaczenie jako przykładu funkcji obliczalnej, która nie jest prymitywnie rekurencyjna. Dla informatyków prymitywna rekurencja odpowiada pętlom z licznikiem (for), natomiast funkcje nieprymitywnie rekurencyjne wymagają np. pętli while lub nie dają się zderekursywować do takiej postaci. Omówione są oryginalna trójargumentowa wersja φ(m,n,p) oraz powszechnie używana dwuargumentowa wersja Ackermanna–Péter A(m,n) (rekurencyjna definicja i równoważny wzór z użyciem strzałek Knutha), pokazujące ekstremalnie szybki wzrost (hiperoperacje/tetracja i dalej). Funkcja ma głównie wartość teoretyczną — obaliła przekonanie, że każda obliczalna funkcja jest prymitywnie rekurencyjna — ale znajduje zastosowanie w informatyce jako test wydajności i optymalizacji kompilatorów (Ackermann rating). Przykłady implementacji w C: prosta rekurencyjna (bardzo powolna), iteracyjna symulująca stos oraz zoptymalizowana wersja pamiętająca powtarzające się wartości; ich złożoności pamięciowe i czasowe to odpowiednio O(A(m,n)) pamięci dla prostego stosu oraz dla wariantu zoptymalizowanego złożoność czasowa O(m·A(m,n)) i pamięciowa O(m), co praktycznie daje ogromne przyspieszenie (na przykład autor odnotował ~18 s dla rekurencji vs ~0.4 ms dla zoptymalizowanej metody dla A(4,1)). Podsumowując, Ackermann jest ważnym teoretycznym przykładem ekstremalnego wzrostu funkcji i użytecznym narzędziem do badania derekursywacji i wydajności kompilatorów. ## Mierzenie czasu wykonania https://swistak.codes/post/mierzenie-czasu-wykonania Artykuł opisuje praktyczne metody mierzenia czasu wykonania aplikacji i fragmentów kodu: kiedy używać profilerów (szczegółowa inspekcja, nagrywanie przebiegu, ale duża ilość danych i wpływ na wydajność), a kiedy proste, ręczne pomiary. Omówione są narzędzia systemowe: time (Linux/macOS) i Measure-Command (PowerShell) do mierzenia czasu całych procesów oraz interpretacja pól real/user/sys. Dla pomiarów w kodzie pokazano podejścia w popularnych językach: w C clock_gettime (CLOCK_PROCESS_CPUTIME_ID / CLOCK_MONOTONIC), w C# System.Diagnostics.Stopwatch, w JavaScript performance.now (Web Performance API) i process.hrtime.bigint (Node.js), oraz w Pythonie time.process_time_ns, time.perf_counter_ns i moduł timeit do powtarzanych pomiarów statystycznych. Wyjaśniono, dlaczego nie używać czasu kalendarzowego (nie jest monotoniczny; NTP, DST, sekundy przestępne mogą zaburzać pomiary) oraz które liczniki są monotoniczne. Podano wskazówki dotyczące poprawnej interpretacji wyników: powtarzanie pomiarów, wykresy pudełkowe, mediany/średnie, odchylenie standardowe, odrzucanie skrajnych wartości, uruchamianie w podobnych warunkach i porównywanie przyrostów/relacji zamiast bezwzględnych wartości. ## Rysowanie gradientów https://swistak.codes/post/gradienty Artykuł wyjaśnia algorytmiczne podejście do rysowania gradientów: czym są i jakie są ich rodzaje (liniowe, radiacyjne, stożkowe), oraz jak obliczać kolory między punktami. Omawia interpolację liniową (lerp) w praktyce — jednowymiarowo i wektorowo dla przestrzeni RGB (kolory jako punkt w sześcianie RGB) z przykładami JS (lerp, lerpColor, getGradientColors). Porównuje też interpolację w przestrzeni HSL (cylindryczna), zwracając uwagę na szczególne przypadki związane z kątem H i nasyceniem S (np. różne przejścia między bielą a czernią). Przedstawia interpolację wielomianową/easing realizowaną przez sześcienne krzywe Béziera (cubic Bezier) — stosowanie krzywej jako mapy prędkości interpolacji: aproksymacja krzywej, znalezienie polyT dla danego t i użycie go w lerp między kolorami. Podaje przykładowe punkty kontrolne (ease-in/out/in-out), kod JS przykłady, narzędzia (easings.net, cubic-bezier.com) i eksperyment 3D: użycie punktów kontrolnych bezpośrednio w przestrzeni barw. W praktyce najczęściej używa się liniowej interpolacji w RGB, choć alternatywne metody dają bardziej estetyczne efekty. ## Zegar binarny https://swistak.codes/post/zegar-binarny Artykuł opisuje działanie dwóch typów zegarów binarnych — sześćdziesiątkowego (godziny, minuty, sekundy jako całe liczby binarne, zwykle siatka 6×3, bity od prawej: 1,2,4,8,16,32) oraz dziesiętnego (kodowanie BCD: każda cyfra dziesiętna jako oddzielny nibble). Pokazuje, jak odczytywać oba typy i przeprowadza krok po kroku implementację wyświetlacza w JavaScript z użyciem elementu . Kluczowe elementy implementacji to: konwertery toBinary() i toBcd(), rysowanie diod (drawDiode) na siatce z marginesami i obliczaniem środka, rysowanie wierszy/kolumn (drawRow/drawColumn) oraz funkcje drawNumber i pętla rysująca z pobieraniem aktualnego czasu i requestAnimationFrame. Dla wersji sześćdziesiątkowej użyto siatki 6 kolumn × 3 wiersze (canvas 600×300), a dla BCD 6 kolumn × 4 wiersze (canvas 600×400) — przy czym w implementacji zmieniono numerację i rozmieszczenie diod. Końcowy kod dostępny jest na CodePen; artykuł zachęca do eksperymentów z wyglądem i animacjami. ## Symbol Newtona i trójkąt Pascala https://swistak.codes/post/symbol-newtona Artykuł omawia sposoby obliczania symbolu Newtona (współczynnika dwumianowego) i powiązanie z trójkątem Pascala. Zaczyna od definicji przez silnie (n!/(k!(n−k)!)) i prostego kodu, wskazując wady: dużo mnożeń i bardzo duże liczby. Następnie przedstawia ulepszenia: zapis jako iloczyn n(n−1)…(n−k+1)/k!, wykorzystanie symetrii k := min(k,n−k) oraz całkowite wyeliminowanie silni przez iteracyjny iloczyn ∏_{i=1}^k (n−i+1)/i, co zmniejsza wielkość operowanych liczb. Pokazuje też związek z trójkątem Pascala i rekurencyjny wzór C(n,k)=C(n−1,k)+C(n−1,k−1) (prosty, lecz wykładniczy w czasie), oraz jego derekursywację do programowania dynamicznego: iteracyjne wypełnianie trójkąta daje O(n^2) czasu i pamięci, a ograniczenie do liczenia tylko do min(k,n−k) oraz przechowywanie jedynie poprzedniego wiersza redukuje koszty do O(n·min(n,k)) czasu i O(min(n,k)) pamięci. Na końcu krótkie zastosowania: kombinatoryka, rozkład dwumianowy, krzywe Béziera; ciekawostka: przy wypisywaniu wartości mod 3 pojawia się trójkąt Sierpińskiego. ## Programistyczna ezoteryka, czyli Brainfuck https://swistak.codes/post/brainfxck Artykuł opisuje ezoteryczne języki programowania ze szczególnym uwzględnieniem Brainfucka. Wyjaśnia, czym są języki ezoteryczne (artystyczne/żartobliwe, nietypowa składnia) oraz pojęcie kompletności Turinga jako kryterium uznania za język programowania, w tym pojęcie „Turing tarpit” (praktycznie możliwe, ale niepraktyczne do użycia). Podane są nietypowe przykłady kompletności Turinga (PowerPoint, Excel z LAMBDA, Minecraft, system typów TypeScript). Brainfuck (Urban Müller, 1993) ma osiem jednoznakowych instrukcji i prosty model pamięci (tablica bajtów—standardowo 30 000 elementów i wskaźnik); opisano znaczenie znaków > < + - . , [ ]. Pokazano przykładowe programy (Hello World — wersja naiwną i krótszą) oraz omawiano generowanie kodu Brainfuck z tekstu (algorytm różnic ASCII) i konwerter Brainfuck→JavaScript (mapowanie symboli, obsługa wejścia/wyjścia, getChar dla Node.js). Opisano też implementację interpretera w JS, ze szczególnym uwzględnieniem obsługi zagnieżdżonych pętli przy użyciu stosu oraz technik wypisywania pojedynczych znaków. Wspomniano ciekawostki: historyczne języki minimalistyczne, JSFuck i że Brainfuck służy głównie jako ciekawostka edukacyjna dotycząca modeli obliczeniowych, kompilatorów i algorytmów (normlane języki zwykle analizuje się przez AST). Literatura i źródła do dalszej lektury są załączone. ## Rozwiązujemy maturę próbną 2023 z informatyki https://swistak.codes/post/matura-probna-2023 Artykuł prezentuje przykładowe rozwiązania zadań z próbnej matury 2023 z informatyki z perspektywy programisty, głównie w Pythonie (porady dot. Javy/C++ i edytorów: PyCharm/IntelliJ). Zawiera praktyczne wskazówki dotyczące wczytywania/zapisu plików oraz różnic składniowych Pythona. Zadanie 1 (Szachy): parsowanie plansz 8×8, funkcje pomocnicze do wczytywania, zliczania pustych kolumn, bilansu bierek oraz wyszukiwania pozycji i sprawdzania, czy wieże szachują króla (find_char, kierunkowe kontrole). Zadanie 2 (Gra): analiza i przyspieszone symulacje zajmowania pól, przykłady strategii dla ciągów arytmetycznych i geometrycznych oraz konstrukcja sekwencji A (np. potęgi dwójki) do wypełnienia zakresu. Zadanie 3 (Potęgowanie modulo): omówienie szybkiego potęgowania modulo (algorytm O(log x)), praktyczne zadania: test pierwszości (naiwna do sqrt(n)), NWD algorytmem Euklidesa oraz przeszukiwanie x dla a^x ≡ b (brute force z pow_mod). Zadanie 5 (bazy danych): przykładowe zapytania SQL — GROUP BY + COUNT dla liczby armatorów wg typu działalności oraz SELECT DISTINCT z JOIN dla nazw statków powiązanych z armatorami; uwagi o używaniu = vs LIKE i o cudzysłowach vs apostrofach. Dodatkowo krótkie wyjaśnienia dotyczące licencji Wikipedii (CC BY‑SA 4.0) oraz dobre praktyki bezpieczeństwa: nie przechowywać danych kart płatniczych, hasła trzymać jako hashe (nie w jawnej postaci), login może być w postaci jawnej. Linki do kodów na OnlineGDB i do bloga autora. ## Historie zza kulis bloga na 4-lecie https://swistak.codes/offtopic/historie-zza-kulis-bloga-4-lecie Kilka obserwacji po prawie 4 latach prowadzania bloga świstak.codes: po refaktoryzacji stylów z styled-components na CSS Modules wydajność w Lighthouse wzrosła z 62 do 83 (styled-components pogarszały podział CSS/JS, DX jednak był przyjemny), planowane kolejne optymalizacje to eliminacja duplikacji stylów i ewentualne użycie Tailwinda. Opisuję też realny problem dostępu czytelnika spowodowany zwracaniem przez DNS rekordu AAAA (IPv6) zamiast A (IPv4) oraz brakiem prekonfigurowanego IPv6 na serwerze OVH — wymagało to ręcznej konfiguracji i testów ping6. Wyjaśniam stosowanie grafik generowanych przez AI (DALL·E, Stable Diffusion) od 2021 r.: traktuję je jako praktyczne okładki, nie zastępujące pracy grafików, i staram się unikać naśladowania konkretnych artystów. Na koniec rozważam rolę blogów programistycznych wobec narzędzi jak ChatGPT — mimo wątpliwości mam nadzieję kontynuować prowadzenie bloga do 5-lecia. ## Kompresja obrazów https://swistak.codes/post/kompresja-obrazow Artykuł przeglądowo opisuje koncepcje, podejścia i typowe algorytmy stosowane przy kompresji obrazów. Na wstępie definiuje pojęcia: kompresja, kompresja bezstratna vs stratna, artefakt, grafika rastrowa vs wektorowa oraz podstawy zapisu koloru i przetwarzania sygnałów (kwantyzacja, transformacje liniowe). W części bezstratnej omawia proste metody (RLE), kodowanie Huffmana, metody słownikowe (LZ77, LZW), palety barw oraz popularny algorytm DEFLATE (LZ77 + Huffman) wykorzystywany m.in. w PNG i zlib. W części stratnej wyjaśnia kwantyzację barw (redukcja liczby kolorów i dithering), podpróbkowanie chrominancji (YCbCr, schematy 4:4:4, 4:2:2, 4:2:0 stosowane w JPEG/WebP/wideo) oraz kodowanie transformatowe jako główną technikę stratną. Dla transformacyjnego kodowania szczegółowo opisuje DCT w JPEG: podział na bloki 8×8, przesunięcie zakresu, DCT → kwantyzacja za pomocą macierzy → pojawienie się wielu zer → kodowanie RLE + Huffman (z kodowaniem różnic DC) oraz odwrotne kroki przy dekompresji. Wspomina też alternatywne transformaty (falkowa w JPEG2000, Hadamard w WebP). Praca podkreśla, że skuteczność kompresji opiera się na modelowaniu redundancji i niedoskonałości ludzkiego wzroku oraz łączeniu wielu technik dla kompromisu między jakością a rozmiarem pliku. ## Kompresja wideo https://swistak.codes/post/kompresja-wideo Artykuł opisuje podstawy kompresji wideo jako przedłużenie kompresji obrazów (bez audio, skupienie na kompresji stratnej). Wyjaśnia rozróżnienie kontenera (AVI/MP4/MKV/WebM), formatu kodowania (H.261/H.264/H.265 itp.) i kodeka (implementacja, np. x264), oraz różnicę między filmem a wideo cyfrowym. Omawia kodowanie wewnątrzklatkowe (intra-frame, np. MJPEG, MJ2) i międzyklatkowe (inter-frame) z pojęciami GOP, I-frame/P-frame/B-frame, kolejnością dekodowania oraz zamkniętymi i otwartymi GOP. Opisuje przeplot (interlacing) i metody usuwania przeplotu (weaving, line doubling, blending, deinterlacing z kompensacją ruchu). Wyjaśnia makrobloki, bloki transformacji/predykcji, estymację ruchu i kompensację ruchu: wektory ruchu, pel/Qpel, algorytmy dopasowania bloków (np. Diamond Search) oraz kompresję residuum (motion‑compensated DCT). Zaznacza kompromisy: znaczne oszczędności miejsca przy inter-frame kosztem złożoności obliczeniowej i trudności w edycji oraz wrażliwości na szum/ruch kamery. Wspomina standardy stosowane powszechnie (H.264/H.265), nowsze VVC/H.266 oraz rozwijające się kodeki wspomagane AI (np. AIVC), a także profesjonalne formaty zapisu (Apple ProRes, CinemaDNG) i zastosowania (streaming, cyfrowa telewizja, archiwizacja). ## 5 programistycznych dziwactw — wyjaśnione https://swistak.codes/post/programistyczne-dziwy Artykuł opisuje pięć pozornie dziwnych zachowań w językach programowania oraz ich wyjaśnienia: 1) "operator" --> w C to w rzeczywistości kombinacja -- i > (np. while (i --> 0) działa jak while ((i--) > 0)) — wynik działania wynika z lekceważenia białych znaków i składni operatorów; 2) iterowanie znaków (for (char c='a'; c<='z'; c++)) działa, ponieważ char to liczba (ASCII), więc ++ inkrementuje kod znaku; 3) 0.1 + 0.2 !== 0.3 w JavaScripcie (i wielu innych językach) przez ograniczenia reprezentacji zmiennoprzecinkowej (double, przybliżenia binarne) — porównania należy robić z marginesem błędu lub używać typów całkowitych/skalowanych przy finansach; 4) indeksowanie tablicy jak 3[array] w C jest możliwe, bo a[b] jest zdefiniowane jako *(a + b), a dodawanie wskaźników jest przemienne, stąd składnia działa, choć jest nieczytelna; 5) koercja typów w JavaScripcie — mechanizm ułatwiający pracę, ale prowadzący do zaskakujących wyników: np. !![] == true (obiekty są truthy), ale [] == true daje false z powodu konwersji [] → '' → 0 oraz true → 1; oraz '0' + 1 == '01' vs '0' - -1 == 1, bo + dokonuje konkatenacji stringów, a inne operatory wymuszają konwersję do liczb. W podsumowaniu autor podkreśla, że większość tych anomalii wynika z podstawowych reguł języków i warto rozumieć mechanizmy (koercję, reprezentację liczb, wskaźniki), stosować === w JS, porównania z epsylonem i odpowiednie typy dla precyzji. ## Problem zliczania unikalnych elementów https://swistak.codes/post/zliczanie-unikalnych-elementow Artykuł opisuje problem zliczania unikalnych elementów (count-distinct) w strumieniach danych: zdefiniowanie zadania, ograniczenia pamięci i czasu oraz praktyczne zastosowania (monitoring popularności, wykrywanie DDoS, zarządzanie zasobami). Pokazuje naiwną metodę (przechowywanie wszystkich elementów w zbiorze) i jej ograniczenia przy dużych danych. Następnie szczegółowo opisano algorytm HyperLogLog (pochodny LogLog i Flajoleta–Martina): elementy są haszowane (32/64 bity), hasze dzielone na m = 2^b koszyków, w każdym koszyku przechowuje się maksymalną liczbę wiodących zer z pozostałej części hasza. Estymacja wykorzystuje średnią harmoniczną z 2^{-M_i}, mnożnik korekcyjny α_m oraz poprawki dla bardzo małych i bardzo dużych estymacji; celem jest oszczędność pamięci O(m) i szybkie dodawanie O(1) (liczenie O(m)). Błąd standardowy algorytmu ~ 1.05 / sqrt(m). Przedstawiono przykładową implementację JS (DJB2, rekomendacja MurmurHash3) oraz eksperymenty potwierdzające zależność błędu od liczby koszyków i funkcji haszującej. Wspomniano też inne podejścia: Flajolet–Martin, LogLog, HyperLogLog++, min/max i bottom-m sketches oraz nowy algorytm CVM (2022) jako alternatywa nieoparta na haszowaniu. Podsumowanie: HyperLogLog to praktyczne, pamięciooszczędne przybliżenie liczby unikalnych elementów używane np. w Redis PFCOUNT; wybór parametrów i funkcji haszującej determinuje dokładność. ## Macierze — podstawowe operacje https://swistak.codes/post/macierze-podstawy Artykuł wyjaśnia podstawy macierzy z perspektywy informatycznej: macierz to prostokątna tablica liczb wymiaru m×n z elementami a_{ij}; szczególnym przypadkiem jest macierz kwadratowa (n=m). Omówione operacje: transpozycja A^T (a_{ij}→a_{ji}), symetryczność i antysymetryczność, wektory wierszowe/kolumnowe; dodawanie/odejmowanie element‑wise (tylko macierze tych samych wymiarów); mnożenie przez skalar (każdy element razy c); mnożenie macierzy (Cauchy) z warunkiem cols(A)=rows(B) i elementem c_{ij}=∑_r a_{ir} b_{rj} — naiwny algorytm O(n^3), istnieją szybsze metody (np. praca SODA 2024 z oszacowaniem ≈O(n^{2.371552})), a dla specjalnych przypadków (np. macierze diagonalne) można uzyskać O(n). Potęgowanie macierzy wymaga macierzy kwadratowej, A^0=I, A^{n+1}=A·A^n, z efektywną implementacją przez szybkie potęgowanie. W artykule pokazano proste implementacje w JavaScript: transpose, add, multiplyByScalar, multiply (trójnested loop) i power (rekurencyjne szybkie potęgowanie). Zastosowania w informatyce: przekształcenia grafiki 2D/3D i rzutowanie, renderowanie, algorytmy uczenia maszynowego (sieci neuronowe), wykorzystanie GPU/CUDA, kompresja obrazów, porównywanie ciągów, reprezentacja grafów, kryptografia i symulacje fizyczne; biblioteki: MATLAB, Octave, Scilab, NumPy. Literatura i przykłady uzupełniają te praktyczne i teoretyczne aspekty. ## Macierze — obliczanie wyznacznika https://swistak.codes/post/macierze-wyznacznik Artykuł wyjaśnia, czym jest wyznacznik macierzy, jak go zapisywać i interpretować (geometrycznie jako n-wymiarową objętość równoległościanu) oraz jak obliczać go ręcznie i algorytmicznie. Podstawowe przypadki: det[ a ] = a; dla 2×2 det[[a,b],[c,d]] = ad − bc; dla 3×3 można użyć wzoru lub reguły Sarrusa. Dla ogólnych n×n opisano rozwinięcie Laplace’a (minory i dopełnienia algebraiczne) oraz przykład rozwinięcia dla 4×4. Omawiane są też bardziej wydajne metody programistyczne: rekurencyjne rozwinięcie Laplace’a (złożoność O(n!)), algorytm Bareissa (montante) — fraction-free Gaussian elimination, opis idei i implementacji, złożoność O(n^3). Wspomniano inne podejścia: eliminacja Gaussa (O(n^3), problemy numeryczne), wzór Leibniza (O(n!)), algorytm Berkowitza (brak dzielenia, równoleglenie, O(n^4)) i metoda Dodgsona. Zastosowania wyznaczników: rozwiązywanie układów liniowych (wzory Cramera), obliczanie macierzy odwrotnej przez macierz dołączoną i dzielenie przez det(A), obliczanie pól/objętości, testy współliniowości, iloczyn wektorowy, oraz w zaawansowanej analizie — hesjany, jakobiany, wrońskiany; także twierdzenie Kirchhoffa (liczba drzew rozpinających). Podsumowanie podkreśla praktyczność tematu w matematyce i informatyce oraz różne kompromisy między prostotą a wydajnością algorytmów. Literatura i przykładowe implementacje (JS, OnlineGDB) są wskazane. ## Macierze rzadkie https://swistak.codes/post/macierze-rzadkie Artykuł wyjaśnia, że macierze rzadkie to takie, w których większość elementów to zero (praktycznie opłacalne przy ~70–99.9% zer dla bibliotek GPU jak cuSPARSE). Opisuje typowe struktury: macierze wstęgowe (band/diagonal, tridiagonal, pentadiagonal), trójkątne, macierze blokowe i blokowo‑rzadkie (w tym blokowo‑diagonalne). Następnie omawia popularne formaty przechowywania i ich zastosowania: DIA (optymalny dla macierzy wstęgowych), BSR (dla macierzy blokowo‑rzadkich), LIL i DOK (wygodne do tworzenia i modyfikacji), COO (koordynatowy, prosty do konwersji), oraz CSR i CSC (skompr. wiersz/kolumna — najlepsze do obliczeń; CSR lepszy dla operacji na wierszach, CSC dla kolumn). Podano krótkie przykłady implementacji w SciPy (NumPy) oraz przykładowe algorytmy na CSR: konwersja do gęstej macierzy, transpozycja (CSR↔CSC), dodawanie i mnożenie macierzy, z uwagami o wydajności i ograniczeniach formatów. Wnioski: wybór formatu zależy od struktury macierzy i typów operacji — stosując odpowiednią reprezentację można znacząco oszczędzić pamięć i przyspieszyć obliczenia; odnośniki do SciPy, dokumentacji i materiałów NVIDIA. ## Problem komiwojażera https://swistak.codes/post/problem-komiwojazera Artykuł wyjaśnia problem komiwojażera (TSP): znalezienie najkrótszej zamkniętej ścieżki przechodzącej dokładnie raz przez każdy z zadanych punktów. Omówione są odmiany: symetryczny (STSP) i asymetryczny (ATSP), wersja decyzyjna (NP-zupełna) oraz wariant Steinera. TSP formułuje się jako znalezienie minimalnego cyklu Hamiltona w ważonym grafie pełnym. Przedstawiono praktyczne zastosowania (logistyka, robotyka, optymalizacja produkcji) oraz spokrewnione problemy: chiński listonosz, vehicle routing problem (VRP), Set TSP i travelling purchaser problem. Opisano dwie metody znajdowania rozwiązań optymalnych: metodę siłową (generowanie permutacji, złożoność O(n!) — praktycznie nieużyteczną dla większych n) oraz algorytm Helda–Karpa z programowaniem dynamicznym (1962), redukujący złożoność do O(n^2·2^n). Artykuł zawiera przykładowe implementacje w JavaScript (generowanie leksykograficzne permutacji i Held–Karp), porównanie wydajności (drastyczna przewaga Held–Karpa dla średnich n) oraz interaktywne wizualizacje i linki do kodu/zbiorów TSPLIB. W podsumowaniu zwrócono uwagę, że w praktyce stosuje się heurystyki i algorytmy przybliżone, a znajomość metod dokładnych jest nadal wartościowa. Literatura i źródła do dalszego zgłębienia są podane. ## Problem komiwojażera — podejścia heurystyczne https://swistak.codes/post/problem-komiwojazera-heurystyki Artykuł omawia heurystyczne metody rozwiązywania problemu komiwojażera jako praktyczną alternatywę dla algorytmów dokładnych. Przedstawiono prosty algorytm najbliższego sąsiada (NN) — wybiera kolejno najbliższy nieodwiedzony wierzchołek, jest szybki (O(n^2), wersja sprawdzająca wszystkie starty O(n^3)) lecz daje przeciętne wyniki i zależy od punktu startowego. Głównym opisanym podejściem jest algorytm Christofidesa (gwarantuje ≤1.5× optymalnego dla metrycznego TSP): kroki to zbudowanie MST (tu Kruskal z DSU), wybranie wierzchołków o nieparzystym stopniu, minimalne skojarzenie doskonałe (tu prosty greedy O(n^2)), dodanie krawędzi tworzące multigraf, znalezienie cyklu Eulera (Fleury/Hierholzer) i skrócenie do ścieżki Hamiltona; całkowita złożoność oceniana na O(n^3). Zamieszczono przykładowe implementacje JS (MST, perfect matching, Euler circuit, konwersja do Hamiltonian path) oraz interaktywne demonstracje. Wspomniano także inne heurystyki: algorytm zachłanny, bitoniczne TSP, Clarke–Wright, lokalne poprawki k-opt (2-opt, 3-opt), Lin–Kernighan oraz metaheurystyki (symulowane wyżarzanie, tabu search, algorytmy ewolucyjne) i podejścia z sieciami neuronowymi. Ogólny wniosek: heurystyki nie gwarantują optimum, ale w praktyce dają szybkie i bliskie optymalnym rozwiązania dla rzeczywistych rozmiarów problemu. ## Problem komiwojażera — przykładowe metaheurystyki https://swistak.codes/post/problem-komiwojazera-metaheurystyki Artykuł opisuje zastosowanie metaheurystyk do znajdowania satysfakcjonujących rozwiązań problemu komiwojażera (TSP), koncentrując się na 2-opt, hill climbing (simple i steepest-ascent) oraz symulowanym wyżarzaniu, z przykładami implementacji w JavaScript. 2-opt służy jako podstawowa operacja modyfikacji trasy (odwrócenie segmentu), a autor pokazuje zarówno in-place, jak i tworzącą nową tablicę implementację. Hill climbing przedstawiony jest jako lokalne przeszukiwanie (generowanie wszystkich sąsiadów przez 2-opt i wybór najlepszego), omawia problem utknięcia w minima lokalnym oraz praktyczne obserwacje: start z losowej trasy bywa lepszy niż z RNN, które natomiast zmniejsza liczbę iteracji. Symulowane wyżarzanie opisane jest jako rozszerzenie pozwalające akceptować gorsze rozwiązania z prawdopodobieństwem P = exp(−ΔE/T), z mechanizmem chłodzenia (liniear, logarytmiczne, wykładnicze, potęgowe) i przykładową implementacją wykorzystującą losowego sąsiada oraz limit iteracji i śledzenie globalnego najlepszego rozwiązania. Artykuł zawiera też wskazówki dotyczące wyboru strategii temperatury, uwagi o niedeterministyczności SA, interaktywne wizualizacje (ReactFlow) oraz zachętę do eksperymentów i próby innych metaheurystyk (algorytmy genetyczne, tabu) oraz zastosowania metod do innych problemów kombinatorycznych. Literatura i odwołania do TSPLIB i materiałów teoretycznych są podane na końcu. ## Unikalne identyfikatory https://swistak.codes/post/unikalne-identyfikatory Artykuł opisuje cel i podstawy stosowania unikalnych identyfikatorów oraz przedstawia popularne algorytmy ich generowania. Zwraca uwagę na istotę losowości i pseudolosowości (konieczność użycia dobrych generatorów), oraz problem kolizji wyrażony przez paradoks urodzin. Omawia UUID/GUID (128-bitowy format, zapis hex z wariantami i wersjami): v4 — w większości losowy (122 bity losowe), v7 — czas w ms + losowe bity (sortowalny), v1/v6 — czas (100 ns od epoki gregoriańskiej) + sekwencja + identyfikator urządzenia (MAC), oraz inne wersje/warianty. Opisuje Snowflake (64-bitowy ID od Twittera: bit znakowy, 41-bit timestamp, 10-bit machine, 12-bit sequence) i jego warianty (Discord, Instagram, Mastodon, Sonyflake). Przedstawia MongoDB ObjectId (12 bajtów: 4B timestamp, 5B process/id, 3B licznik). Omawia Nano ID — konfigurowalne krótkie ID o zadanym alfabecie; domyślnie 21 znaków z 64-znakowego alfabetu (~126 bitów losowości). Wspomina inne podejścia (cuid2, xid, ShortUUID, PushID, KSUID, ULID) i podkreśla praktyczną zasadę: wybierać rozwiązanie dopasowane do potrzeb (prostota, sortowalność, rozkład losowości, dostęp do centralnego licznika) oraz korzystać ze sprawdzonych bibliotek i kryptograficznie bezpiecznych generatorów. ## Jak narysować gwiazdę? https://swistak.codes/post/jak-narysowac-gwiazde Artykuł opisuje algorytmiczne rysowanie wielokątów gwiaździstych foremnych (gwiazd) — zarówno „właściwych” (jedna łamana) jak i „niewłaściwych” (kilka łamanych). Wprowadza matematyczne oznaczenie Schläfliego {n/x} (n — liczba wierzchołków, x — skok; x>1, x i JavaScriptu: funkcja getVertices(count) generuje współrzędne, connectVertices łączy wierzchołki z zadanym krokiem (z wariantem obsługującym wielokąty niewłaściwe przez startIndex i zbiór visited), a drawStar scala wszystkie połączenia i rysuje ścieżkę (context.stroke()). Jako bonus pokazano rysowanie „zamkniętych” gwiazd przez dwa zestawy wierzchołków (zewnętrzny i wewnętrzny) z przesunięciem kąta (shift = π / n) i naprzemiennym łączeniem, co tworzy klasyczną wypełnioną gwiazdę. Kod jest uniwersalny (można przenieść do innych języków) i dostępny do testów na CodePen; artykuł zawiera też bibliografię (Wikipedia, MathWorld). ## Ustawianie kolejności elementów https://swistak.codes/post/kolejnosc-elementow Artykuł opisuje problem przechowywania kolejności zdefiniowanej przez użytkownika: nie wystarczy polegać na pozycji w tablicy, trzeba zapisać porządek w bazie danych, co przy dużych zmianach wymaga kosztownych aktualizacji i długich transakcji. Jako proste rozwiązanie przedstawiono nadawanie rankingu z dużymi odstępami (np. co 1000) i wstawianie nowych elementów poprzez nadawanie wartości pośredniej (średniej/połowy). Metoda ta wymaga rebalansu (przepisania rankingów) po przekroczeniu granicy drobienia i można ją wydłużyć używając typów zmiennoprzecinkowych. Opisano też podstawowe operacje implementacyjne: getNextRank, getFirstRank, getRankBetween, getMinDistance, rebalance oraz przykładowe fragmenty JS. Jako bardziej zaawansowane rozwiązanie omówiono LexoRank (ranking jako string w base-36, leksykograficzne porządkowanie), używany w Jirze: start w środku przestrzeni, kroki ≈8, rozszerzanie przez dopisywanie części po dwukropku gdy zabraknie miejsca oraz mechanizm „koszyków” (bucketów 0–2) pozwalający na nieblokujący rebalans. Podano też praktyczne progi rebalansu z Jiry (np. 128/160/254 znaków) i uproszczoną implementację LexoRanka w JS. Wnioski: obie metody są praktyczne — gap-ranking proste i wystarczające w wielu przypadkach; LexoRank lepszy dla bardzo dużych i intensywnie modyfikowanych list, ale nadmiarowy dla prostych aplikacji. ## Chińskie twierdzenie o resztach https://swistak.codes/post/chinskie-twierdzenie-o-resztach Chińskie twierdzenie o resztach (CRT) mówi, że dla układu kongruencji n ≡ a_i (mod m_i) z parami względnie pierwszymi modułami m_i istnieje jednoznaczne rozwiązanie modulo M = ∏ m_i. Konstruktywny algorytm oblicza M, Mi = M / m_i, znajduje odwrotności modularne Mi^{-1} (mod m_i) za pomocą rozszerzonego algorytmu Euklidesa i buduje rozwiązanie wzorem n = ∑ a_i e_i (mod M), gdzie e_i = Mi·(Mi^{-1} mod m_i). Przykład: dla modułów 3,5,7 i reszt 2,3,2 otrzymujemy n ≡ 23 (mod 105), czyli rozwiązania n = 23 + 105k. Implementacja w praktyce wymaga funkcji extendedGCD, modularInverse i funkcji CRT (pokazana w JavaScript), a złożoność zależy głównie od liczby równań, nie od wielkości M. Zastosowania: kryptografia (m.in. RSA, schematy dzielenia sekretów), systemy zapisu resztowego (RNS), algorytmy FFT (Good–Thomas) oraz rozwiązywanie zadań algorytmicznych (np. Advent of Code). Historycznie opisane w chińskim traktacie Sunzi Suanjing; kluczowe warunki to parami względnie pierwsze moduły i unikalność rozwiązania modulo iloczynu. ## Korekcja perspektywy — algorytmiczne podejście https://swistak.codes/post/korekcja-perspektywy Artykuł opisuje od podstaw algorytmiczne podejście do korekcji perspektywy w grafice rastrowej: modelowanie transformacji perspektywicznej (homografii) jako macierzy 3×3 z ośmioma niewiadomymi, wyznaczanie tej macierzy na podstawie czterech par punktów docelowych oraz zastosowanie jej do „wyprostowania” zdjęcia. Pokazano tworzenie układu równań dla parametrów macierzy, jego zapis w postaci macierzy A i wektora b oraz rozwiązanie za pomocą eliminacji Gaussa (implementacja w JavaScript). Omówiono też konieczność odwrotnego mapowania pikseli (dla grafiki rastrowej): obliczenie macierzy odwrotnej homografii, użycie jej do znalezienia źródłowych współrzędnych dla każdego piksela docelowego oraz przeliczenie tych współrzędnych na konkretne wartości piksela. Przedstawiono wzory na wyznacznik i macierz dołączoną, gotowe formuły elementów macierzy odwrotnej oraz implementację funkcji zwracających odwrotną macierz i przekształcone punkty. Omówiono metody odczytu wartości piksela ze współrzędnych niecałkowitych: najbliższego sąsiada (prosty) oraz interpolację dwuliniową (praktyczna, z opisem wzorów i kodu). Wskazano gotowe narzędzia (OpenCV: getPerspectiveTransform + warpPerspective) oraz przykładowe implementacje i demonstracje w JS/TypeScript (React, CSS matrix3d) dostępne na GitHubie. Artykuł łączy teorię macierzową transformacji 2D z praktycznymi implementacjami korekcji perspektywy i renderowania rastrów. ## Losowość w informatyce https://swistak.codes/post/losowosc Artykuł opisuje znaczenie i źródła losowości w informatyce, rozróżniając pseudolosowość (PRNG) od prawdziwej losowości (TRNG). Definiuje losowość i procesy stochastyczne oraz wymienia trzy kluczowe właściwości generatorów: długość okresu, jednorodność i nieprzewidywalność. Przegląd PRNG obejmuje historyczne i praktyczne algorytmy: metodę środka kwadratu (von Neumann) — prosta, ale z krótkim okresem i cyklami; liniowy generator kongruencyjny (LCG) z rekurencją X_{n+1}=(aX_n+c) mod m i warunkami Hull–Dobell; rodzinę Xorshift — szybkie operacje bitowe; PCG — kombinację LCG + permutacja bitowa dającą długi okres i dobrą jakość; oraz klasę kryptograficznie bezpiecznych generatorów (CSPRNG) spełniających next-bit test i odporność na wycieki stanu. Opisano też konkretne konstrukcje CSPRNG: Blum Blum Shub (bezpieczeństwo związane z faktoryzacją, lecz wolny) oraz standard NIST SP 800-90A (Hash_DRBG, HMAC_DRBG, CTR_DRBG) z zasadami inicjalizacji, reseedowania i generowania. Omówiono źródła ziarna: systemowy czas (łatwy, przewidywalny), entropię użytkownika (ruch myszki, klawiatura) oraz sprzętowe źródła entropii (szumy kwantowe, elektryczne, rozpad radioaktywny, Lavarand). Wspomniano o wbudowanych TRNG w CPU (RDRAND, PadLock, Secure Enclave) oraz serwisach z TRNG (Random.org, ID Quantique). Przykłady zastosowań i używane generatory w środowiskach: C/C++ rand() (LCG), C++ mt19937 (Mersenne Twister), Java util.random (LXM od JDK17), JavaScript Math.random (Xorshift128+ w V8), .NET (Xoshiro256**), Python random (Mersenne Twister). Zaznaczono praktyczne zalecenie: korzystać ze sprawdzonych implementacji; do zastosowań kryptograficznych używać CSPRNG lub TRNG, a prostsze PRNG wystarczają do testów i gier niekrytycznych. ## świstak.codes staje się open‑source! https://swistak.codes/offtopic/opensource Artykuł informuje o udostępnieniu kodu źródłowego bloga świstak.codes na GitHubie (MIT; artykuły/grafiki nadal chronione) jako migawki gałęzi main bez historii commitów — PR nie będą akceptowane, sugestie przez GitHub Discussions. Repozytorium to projekt Next.js (aktualnie v15) napisany w TypeScript, pierwotnie z Next.js 12, styled-components i Nx; odświeżono do CSS Modules + SCSS, zrezygnowano z monorepo, dalej używany Pages Router i Webpack oraz niektóre legacy API Next.js. Artykuły są w MDX z niestandardowymi metadanymi i rozdzielone w /src/_posts, /src/_offtopic, /src/_pages; strony generowane są skryptem (npm run generate-pages), a RSS/sitemap i indeks wyszukiwarki powstają niestandardowymi skryptami (scraper, public-fix.sh). Instrukcje uruchomienia: Node.js (w artykule 22.12.0), npm install && npm start; Matomo i Typesense można uruchomić lokalnie przez Docker (npm run docker:matomo / npm run docker:search). TypeScript i testy jednostkowe istnieją, ale część testów i integracji z MDX obecnie nie działa z powodu problemów narzędziowych. Wyjaśniono wybory technologiczne: Next.js zamiast Gatsby/Jekyll/Nuxt/Remix (dziś rozważyłby Astro/Docusaurus), CSS Modules zamiast Tailwind/styled-components, Matomo z uwagi na prywatność, Typesense jako open-sourceowa wyszukiwarka (i wektorowa baza), Giscus do komentarzy. Autor argumentuje za self-hostingiem (kontrola danych, brak vendor lock-in), przyznaje, że wiele rozwiązań powstało w toku nauki i zaprasza do pytań i dyskusji. ## Wyszukiwanie obiektów w przestrzeni https://swistak.codes/post/wyszukiwanie-w-przestrzeni Artykuł omawia techniki wyszukiwania obiektów w 2D stosowane m.in. w grach, GIS i przetwarzaniu obrazów. Definiuje problem: szybkie znajdowanie obiektów w punkcie, w promieniu lub w prostokącie; porusza zastosowania (rendering, kolizje, kliknięcia, pole widzenia). Opisuje drzewo czwórkowe (point-region quadtree): węzły reprezentują obszary, mają stałą pojemność, przy przepełnieniu dzielą się na 4 dzieci; elementy zwykle przechowywane w liściach; operacje insert/query rekurencyjne; złożoność średnio O(log n), w najgorszym O(n); dobre dla nierównomiernych rozkładów i danych statycznych. Przedstawia haszowanie przestrzenne (spatial hashing): stała siatka o rozmiarze komórki, mapa klucz→lista obiektów; insert/query o koszcie opt. O(1), w praktyce O(m) zależnie od liczby komórek obiektu; sprawdza się przy ruchomych obiektach, równomiernym rozkładzie i zapytaniach punktowych. Omawia wady obu metod, możliwość hybryd (quadtree + hashing) oraz alternatywy: R-/R*-tree, BSP, k-d tree. Zawiera przykładowe implementacje w TypeScript i wskazówki praktyczne. ## Renderowanie grafiki w stylu Wolfenstein 3D https://swistak.codes/post/renderowanie-wolf-3d Artykuł opisuje algorytmikę renderowania w stylu Wolfenstein 3D: gra używa świata zapisanego na ortogonalnej dwuwymiarowej siatce (plansza z komórkami 1×1), brak jest ruchu w pionie, a ściany i obiekty są prostymi prostokątami lub sprite’ami 2D. Widok 3D realizowany jest przez ray casting: dla każdej kolumny pikseli na szerokość ekranu wypuszczany jest promień, znajduje się punkt kolizji z siatką (algorytm DDA) i na podstawie odległości rysowana jest pionowa kolumna o wysokości odwrotnie proporcjonalnej do odległości (h = screenHeight / distance). Kierunek promienia wyznacza wektor kierunku gracza skombinowany z wektorem rzutni (plane), który definiuje pole widzenia; aby skorygować efekt „rybiego oka” używa się odległości prostopadłej do rzutni (dzielenie przez składową wektora kierunku lub obliczenie parametru t). Implementacja DDA wykorzystuje deltaDist, sideDist oraz kroki stepX/stepY do sprawnego przechodzenia po komórkach siatki; po trafieniu obliczana jest odległość bez pierwiastkowania. Oświetlenie symulowano prosto: dwie wersje tekstur (jasna/ciemna) w zależności od tego, czy trafienie było od strony pionowej czy poziomej. Artykuł pokazuje też prostą współczesną implementację w JavaScript (stan: pos, dir, plane, map; funkcje castRay, render, move, rotate) i zaznacza różnice względem oryginału (stałoprzecinkowe obliczenia, asemblerowe optymalizacje). Pominięto szczegóły oryginalnych optymalizacji, pełne teksturowanie i sprite’y w przykładowym kodzie; za rozszerzeniami odsyła do źródeł i książki Fabiena Sanglarda. ## Silnia i powiązane zagadnienia https://swistak.codes/post/silnia Artykuł omawia funkcję silni i powiązane pojęcia: definicję n! = 1·2·...·n (0! = 1), rekurencyjne formy, szybko rosnące wartości (przykłady 0!–10!) oraz praktyczne implikacje (przepełnienia typów: ~12! dla 32-bit, ~20! dla 64-bit). Pokazano implementacje w JavaScript (iteracyjna, rekurencyjna, dynamiczna, zoptymalizowana, generator) z użyciem BigInt. Omówiono liczbę zer na końcu n! z formułą f(n)=∑⌊n/5^i⌋. Zastosowania w kombinatoryce: permutacje, wariacje, kombinacje i symbol Newtona (w tym trójkąt Pascala, dwumian Newtona i krzywe Béziera). Wzory Taylora/Maclaurina wykorzystują silnię w mianownikach szeregu potęgowego, co ułatwia obliczanie funkcji trygonometrycznych w informatyce. Funkcja Gamma Γ(z) jako uogólnienie silni na liczby rzeczywiste/zespolone: definicja całkowa Γ(z)=∫0∞ t^{z-1} e^{-t} dt (Re(z)>0), własność rekurencyjna Γ(z+1)=zΓ(z) i związki z silnią Γ(n)=(n−1)!. Omówiono trudności obliczeniowe i metody aproksymacji: wzór Stirlinga n! ≈ √(2πn)(n/e)^n (i ln(n!)≈n ln n − n) oraz dokładniejsze przybliżenie Lanczosa dla Γ(z). Rozszerzenia silni: silnia podwójna i wielokrotna (n!!, n!^{(k)}), definicje dla liczb ujemnych (z wyjątkami), przybliżenia podwójnej silni; potęgi kroczące — silnia górna (rising) x^{\overline{n}} i dolna (falling) x^{\underline{n}}, związki z silnią przez Γ, rozszerzenia na ujemne wykładniki. Podsilnia (!n, subfactorial) i jej interpretacja jako liczby derangements (!n ≈ n!/e) oraz wzory iteracyjne. Pierwsznia (primorial) n# — iloczyn liczb pierwszych ≤ n (alternatywnie p_n#) — zastosowania: poszukiwanie primorial primes, testy gładkości (B-smooth) i struktury sita primorialowego (metody generowania liczb pierwszych). Krótkie wspomnienie dalszych tematów: factorion, superfactorial, funkcja G Barnesa itp. Literatura i źródła wymienione na końcu. ## Określanie trudności pisania słowa https://swistak.codes/post/trudnosc-pisania Artykuł opisuje sposoby mierzenia trudności pisania słów na fizycznej klawiaturze QWERTY przy założeniu poprawnego, bezwzrokowego pisania (przypisanie palców do kolumn, kciuk do spacji/Alt dla diakrytyków). Przedstawione trzy metryki rosnącej złożoności: 1) suma odległości pokonywanej przez palce (współrzędne układu, odległość Manhattan/Euklidesowa, uwzględnienie ruchu na Alt dla polskich znaków); 2) rozszerzenie z uwzględnieniem, który palec naciska dany klawisz i pozycji startowych palców (model „fingers”); 3) model wysiłku palców oparty na Colemak Mod‑DH (waga palców, użycie prawa Fittsa, tablica wartości wysiłku dla klawiszy). Jako najbardziej zaawansowaną metodę opisano Carpalx: dzielenie słowa na triady, obliczanie kosztu triady jako sumy składowych (bazowy, kary, ścieżka) z wagami (kb≈0.3555, kp≈0.6423, ks≈0.4268; k1=1,k2≈0.367,k3≈0.235; w_h,w_r,w_f i specyficzne kary dla rzędu/palca), oraz szczegółową logiką oceny ścieżki (ręce, rzędy, palce). Autor zamieszcza przykładowe implementacje JS (kod dostępny na OnlineGDB), porównuje wyniki dla słów (np. Asdf, las, piłka, chrząszcz, programmer, javascript) i pokazuje, że różne metryki dają różne rankingi trudności. Podsumowanie: proste metryki są łatwe w implementacji, modele uwzględniające komfort palców (Colemak Mod‑DH) i Carpalx dają pełniejsze, konfigurowalne oceny przy zastosowaniu wielu czynników; dalsze badania mogą porównać różne układy klawiatury i alternatywne umieszczenie znaków diakrytycznych. Źródła: artykuły StackOverflow, Digital Bunker, Colemak Mods, Carpalx. ## Znajdowanie dominującej barwy https://swistak.codes/post/barwa-dominujaca Artykuł omawia różne metody statystyczne i praktyczne podejścia do wyznaczania „dominującej” barwy obrazu: średnie (arytmetyczna i kwadratowa/RMS, z iteracyjnym obliczaniem dla strumienia pikseli), skalowanie obrazu do 1x1 (różne przeglądarki dają różne wyniki), medianę (component-wise i geometryczną wyznaczaną algorytmem Weiszfelda) oraz dominantę/modę kolorów z grupowaniem przez tolerancję. Autor porównuje wyniki na przykładowych okładkach (np. Trello) i pokazuje, że średnie są wrażliwe na wartości skrajne, skalowanie jest niedeterministyczne między silnikami, mediana bywa lepsza, ale najlepsze i najbardziej spójne rezultaty daje dominanta uzyskana przez grupowanie podobnych kolorów. Opisane implementacje obejmują prosty algorytm odległościowy (O(n^2)) oraz zoptymalizowane grupowanie przez zaokrąglanie składowych do wielokrotności tolerancji i użycie mapy kluczy (szybkie). Autor sugeruje dodatkowe ulepszenia: analizę pikseli przy brzegach (dla koloru tła) lub klasteryzację (np. k‑means) i udostępnia interaktywne demonstracje oraz kod JS. Literatura i źródła do średnich, mediany geometrycznej i dominanty są również podane. ## Liczby zespolone https://swistak.codes/post/liczby-zespolone Artykuł opisuje liczby zespolone: jednostkę urojoną i (i^2 = −1), liczby urojone bi oraz ogólną postać a + bi z częścią rzeczywistą i urojoną. Pokazuje geometryczną reprezentację na płaszczyźnie zespolonej (diagram Arganda) i interpretację jako wektory, co upraszcza dodawanie i mnożenie. Omawia moduł |z| (długość wektora) i argument Arg(z) (kąt, implementowany jako atan2), oraz zapisy: algebraiczny, trygonometryczny (|z|(cosφ + i sinφ)), wykładniczy (|z| e^{iφ}) i macierzowy (2x2), z zależnością det = |z|^2. Przedstawia operacje: mnożenie/dzielenie (w polarnych: mnożenie modułów i dodawanie/odejmowanie kątów), wzór de Moivre’a dla potęg i wzory na pierwiastki (wielowartościowe). Opisuje implementacje w językach: Python, Go, C (C99), C++, C#, Ruby, MATLAB, Julia; pokazuje prostą klasę Complex w JavaScript. Wskazuje praktyczne zastosowania: grafika 2D (skalowanie/obrót przez mnożenie), generowanie fraktali (zbiór Mandelbrota), przetwarzanie sygnałów i transformacje Fouriera, oraz wykorzystanie w fizyce (równanie Schrödingera, analiza obwodów). Na koniec wspomina o rozszerzeniach do wyższych wymiarów (kwaterniony, oktoniony itd.) i podkreśla, że liczby zespolone upraszczają i elegancko rozwiązują problemy dwuwymiarowe oraz wiele zadań w matematyce, informatyce i inżynierii. ## Problem selekcji https://swistak.codes/post/problem-selekcji Artykuł opisuje problem selekcji — znalezienia k-tego najmniejszego elementu w n-elementowym zbiorze — i omawia algorytmy rozwiązujące go z naciskiem na osiągnięcie liniowej złożoności O(n). Wyjaśniono proste przypadki: minimum/maksimum wymagają n−1 porównań, a ich jednoczesne znalezienie można zoptymalizować do 3⌊n/2⌋ porównań przez przetwarzanie par. Przedstawiono quickselect (algorytm Hoare’a), oparty na partycjonowaniu jak w quicksort — szybki w praktyce, ze średnią złożonością O(n) przy losowym wyborze pivota, ale z najgorszym przypadkiem O(n^2) dla złego wyboru pivota. Jako deterministyczne rozwiązanie gwarantujące O(n) w najgorszym przypadku opisano algorytm „mediana median” (BFPRT/magiczne piątki): dzielenie na grupy po 5, znajdowanie median każdej grupy, wybór mediany median jako pivota i rekursywne partycjonowanie, co daje gwarantowany dobrze zbalansowany podział. Omówiono także alternatywy: pełne sortowanie i pobranie elementu (O(n log n)), częściowe sortowanie (O(k·n)), heapselect (O(n log k)) oraz introselect — hybrydę szybkiego selekcjonowania z przełącznikiem na bezpieczniejsze metody. W podsumowaniu wskazano, że w praktyce często używa się sortowania z powodu prostoty i wydajnych bibliotek, a algorytmy selekcji są szczególnie przydatne dla bardzo dużych zbiorów lub specyficznych wartości k; rekomendacją praktyczną jest użycie introselect lub heapselect zależnie od przypadku. ## Jak działają kody 2FA? https://swistak.codes/post/kody-2fa Artykuł wyjaśnia, jak działają kody 2FA generowane lokalnie: opierają się na wspólnym sekretnym kluczu i prostych operacjach kryptograficznych (HMAC + dynamiczne przycinanie), dzięki czemu aplikacje typu Google Authenticator działają całkowicie offline po jednorazowej synchronizacji z serwerem. HOTP (RFC 4226) używa licznika, co wymaga synchronizacji i tolerancji przesunięcia; TOTP (RFC 6238) zastępuje licznik czasem (zwykle 30 s), co eliminuje problem desynchronizacji. Sekret (w formacie Base32) i parametry algorytmu przekazywane są w URI otpauth zakodowanym w QR; domyślnie używa się SHA-1 i 6 cyfr. Przykładowa implementacja (TypeScript) pokazuje użycie HMAC, offsetu z ostatniego bajtu i modulo 10^digits do uzyskania kodu. Z punktu widzenia bezpieczeństwa serwery powinny wydzielać i szyfrować sekrety (envelope encryption: DEK/KEK), korzystać z KMS/HSM, przechowywać odszyfrowane wartości w pamięci tylko chwilowo oraz stosować rate-limiting; OWASP publikuje dobre praktyki. Użytkownicy powinni wybierać zaufane, aktualizowane aplikacje, nie udostępniać sekretów i szyfrować kopie zapasowe; klucze sprzętowe (FIDO2/WebAuthn) oferują silniejszą ochronę przeciw phishingowi. Autor przytacza przykłady wycieków i błędów (Spoutible 2024, wyciek bazy giełdy 2025, błąd Proton Authenticator 2025) i konkluduje, że mimo ryzyka przechowywanie sekretów w formie odwracalnej, 2FA znacząco podnosi bezpieczeństwo kont, choć nie jest nieomylne. ## Podobieństwo wektorów, czyli jak działają bazy wektorowe https://swistak.codes/post/podobienstwo-wektorow Artykuł wyjaśnia, że bazy wektorowe indeksują dane za pomocą wektorów (embeddingów) generowanych przez modele ML, dzięki czemu można szybko wyszukiwać semantycznie podobne treści. Wektory to uporządkowane listy liczb (często setki–tysiące wymiarów); porównywanie wymaga jednak tej samej liczby wymiarów i zwykle normalizacji długości. Popularne metryki podobieństwa to odległość euklidesowa (L2), Manhattan (L1) i podobieństwo kosinusowe — to ostatnie jest najczęściej używane, bo ignoruje długość wektora i jest proste obliczeniowo (dla znormalizowanych wektorów redukuje się do iloczynu skalarnego). Autor porównał wyniki kilku modeli embeddingowych (m.in. OpenAI, Mistral, Google, Qwen) na zestawie przykładowych tekstów; klastry semantyczne generalnie się zachowują, ale ranking zależy od modelu. Przeprowadzono też test analogii (3CosAdd) z dodatkiem klasycznego GloVe — analogie zwykle działają, choć nowoczesne modele czasem zwracają inne, sensowne odpowiedzi. Szybkość wyszukiwania w dużych zbiorach zapewniają algorytmy ANN (Approximate Nearest Neighbor) — głównie HNSW (wysoka dokładność, większe zużycie pamięci), IVF/IVFPQ (segmentacja przestrzeni i kwantyzacja, mniejsze pamięciożerność kosztem dokładności) oraz LSH (haszowanie czułe na lokalność). Zastosowania obejmują wyszukiwanie podobnych dokumentów/obrazów, semantyczne wyszukiwanie i RAG (Retrieval-Augmented Generation) do wzbogacania odpowiedzi LLM treściami z zewnętrznych źródeł. Artykuł zawiera praktyczne wskazówki, przykładowe kody i uwagi o trade-offach między dokładnością, pamięcią i kosztami. ## Sztuczna inteligencja — mity a rzeczywistość https://swistak.codes/post/mity-ai Artykuł obala mity o AI (stan na kwiecień–lipiec 2026) i wyjaśnia, czym rzeczywiście są jej współczesne możliwości i ograniczenia. Autor (doświadczony programista z projektami R&D i pracą nad generowaniem muzyki przez sieci neuronowe) rozróżnia pojęcia: AI jako szeroka dziedzina, generative AI (LLM, generatory obrazów/wideo/dźwięku), sieci neuronowe, transformery (mechanizm attention, tokeny, embeddingi) oraz modele dyfuzyjne i eksperymentalne dLLM. Opisuje proces trenowania LLM: base → SFT → RLHF → chat tuning; techniki generowania (sampling) i ograniczenia (halucynacje, brak trwałego uczenia „w locie”). Szeroka dyskusja o AGI: różne definicje, propozycja DeepMind (6 zasad, 6 poziomów ogólności/poprawności) i poziomy autonomii (0–5). Wnioski: współczesne LLM-y są w najlepszym razie „wschodzącą”/słabą formą ogólności, ale nie pełnym AGI ani świadomymi bytami. Agenty (OpenClaw, Claude Code itp.) podnoszą autonomię, lecz nie zwiększają samej inteligencji modeli ani nie uczą ich trwale. Omówione też zagrożenia związane z RSI/recursive self-improvement — automatyzacją R&D i obawy o „explosion”, ale pełne autonomiczne RSI jeszcze nie nastąpiło. Świadomość i antropomorfizacja: przegląd teorii świadomości (IIT, GWT, AST, HOT itp.), testów (np. 14 wskaźników Butlina i in.) i wnioski — brak dowodu, że LLM-y są świadome; efekt Elizy i psychologia antropomorfizacji (HADD, język, interfejsy), oraz celowe projektowanie interakcji zwiększające to zjawisko. Przestroga: nie ufać deklaracjom modeli o „świadomości” — są one wynikiem danych treningowych i instrukcji systemowych. AI vs roboty i zastosowania praktyczne: AI to oprogramowanie; roboty to ciało/aktuatory — można mieć jedno bez drugiego. Robotyka stoi przed dodatkowymi wyzwaniami (dane, sim-to-real gap, energia, bezpieczeństwo). LLM-y są wszechstronne, ale nie zawsze najlepsze: wiele zadań lepiej rozwiążą wyspecjalizowane modele (YOLO, U-Net, Dex-Net, medyczne modele, systemy rekomendacyjne), a czasami wystarczą klasyczne algorytmy. Rady praktyczne: wybierać mniejsze/wyspecjalizowane modele, nie strzelać „armatą do muchy”. Hype, marketing i polityka: krytyka przesadnych komunikatów firm (OpenAI, Anthropic), przypadki ograniczeń dostępu (Mythos, Claude Fable), rola regulatorów (AI Act, DMA) i potrzeba suwerenności cyfrowej (Europa ma Mistral, DeepL, Stability, ElevenLabs). Omówione etyczne i prawne aspekty danych treningowych, licencji i praw autorskich. Sztuka i kreatywność: AI jako narzędzie (historia od AARON po DeepDream i generatory), ale nie jako autonomicznie kreatywna bytowość — brak „duszy”, masowa produkcja generycznych treści („AI slop”) i spory o prawa autorów. Przykłady zastosowań pozytywnych i kontrowersyjnych w muzyce i wideo. Podsumowanie i rekomendacje: traktować generatywną AI jako potężne narzędzie, nie jako świadomość; weryfikować źródła i twierdzenia; preferować otwarte, lokalne/europejskie rozwiązania; stosować AI tam, gdzie ma sens; zachować człowieka w pętli decyzyjnej i krytycznie podchodzić do marketingu.