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

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

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

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

Świat matematyki bogaty jest w różne funkcje, definicje, odkrycia, które mogą wydawać się na pierwszy rzut oka całkowicie zbędne. I nie mam tutaj na myśli słynnych wzorów skróconego mnożenia, gdzie ludzie odmierzają sobie dni, kiedy ich nie użyli, tylko nieco bardziej zaawansowane koncepcje. W artykule chcę pochylić się nad jedną taką rzeczą — funkcją Ackermanna. Powstała, aby udowodnić, że można zrobić tak skomplikowaną i jednocześnie obliczalną funkcję. Zaś co może być ciekawe dla informatyków, w naszej niszy też znalazła pewne specyficzne zastosowanie. Poznajmy ją bliżej.

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

W świecie grafiki komputerowej, szczególnie tej wektorowej, chcemy móc opisać jak najwięcej rzeczy językiem matematyki. Dzięki temu możemy wykonywać różne przekształcenia bez utraty jakości. Tylko o ile oczywiste jest rysowanie odcinków, a co za tym idzie typowych figur geometrycznych, bardziej rozbudowane kształty wymagają już nieco bardziej zaawansowanych narzędzi matematycznych. O ile koła ktoś może jeszcze wyznaczyć szkolnymi wzorami, spirale niewiele trudniejszymi, to jak opisać dowolną krzywą? Poznajmy dziś najprostsze i zarazem najpopularniejsze z matematycznie zdefiniowanych krzywych — krzywe Béziera.

Omawiając ostatnio algebrę zbiorów, przedstawiłem jej zastosowanie w najbardziej oczywisty dla programistów sposób — na strukturach danych zbiorów i tablic. Jak się jednak okazuje, zagadnienia z niej mają znacznie więcej zastosowań w informatyce. Tym razem pokażę, jakie przełożenie ma ten obszar logiki matematycznej na język programowania TypeScript, a dokładniej na jego system typów. Innymi słowy, nie zastosujemy logiki w wykonywalnym kodzie programu, ale w technicznym opisie tego, co my w ogóle programujemy. A patrząc z jeszcze innej strony — poznamy wycinek teorii typów w praktyce.

Przedstawiając ostatnio podstawy logiki dla informatyków, ograniczyłem się tylko do podstaw rachunku zdań — bo to on jest najczęściej spotykany. Następnie opisałem kwantyfikatory, które rzadziej spotyka się w programowaniu, ale wciąż należy je znać. Moim zdaniem kolejnym często spotykanym zagadnieniem z logiki, aczkolwiek już mniej kojarzonym z programowaniem, jest algebra zbiorów. Zobaczmy, czym ona jest i jakie ma zastosowanie w informatyce.

Przedstawiając ostatnio podstawy logiki dla informatyków, ograniczyłem się tylko do rachunku zdań, bo to on jest najczęściej spotykany. Jednak logika matematyczna jest dużo bardziej rozbudowana i inne jej elementy też znajdują zastosowanie praktyczne. Kolejnym zagadnieniem, które chcę przedstawić, jest rachunek kwantyfikatorów. Z naszego punktu widzenia będzie to krótkie i proste, ale warte opowiedzenia.