świstak.codes

O programowaniu, informatyce i matematyce przystępnym językiem

Matematyka

Funkcja Ackermanna

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

Czytaj więcej

Otoczka wypukła

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.

Czytaj więcej

Krzywe Béziera

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.

Czytaj więcej

Teoria zbiorów a TypeScript

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.

Czytaj więcej

Logika dla informatyków — algebra zbiorów

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.

Czytaj więcej

Logika dla informatyków — kwantyfikatory

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.

Czytaj więcej

Logika dla informatyków — podstawy

Dość często można spotkać się w Internecie z twierdzeniem, że aby programować, nie trzeba znać matematyki. Jednak jakkolwiek na to nie spojrzeć, komputer to przerośnięty kalkulator, maszyna obliczeniowa, stąd w wielu dziedzinach programowania natkniemy się na różne rzeczy wywodzące się z matematyki. Jest jeden dział matematyki, z którym do czynienia ma na co dzień każdy programista, a nawet ogólniej — każdy informatyk. Tym działem jest logika matematyczna. Poznajmy i uporządkujmy sobie jej absolutne podstawy w kontekście programowania.

Czytaj więcej

Obliczanie wyrażeń matematycznych

W ostatnim artykule przedstawiłem odwrotną notację polską (ONP) i jak obliczać wyrażenia matematyczne zapisane za jej pomocą. Jednak powiedzmy sobie szczerze — pisząc aplikację obliczającą wyrażenia, nie możemy zmuszać użytkowników do stosowania małopopularnej notacji tylko dlatego, że wygodnie się ją programuje. Dlatego też w tym artykule opiszę, w jaki sposób wiedzę na temat ONP zastosować do obliczania wyrażeń matematycznych zapisanych w tradycyjny, infiksowy sposób.

Czytaj więcej

Odwrotna notacja polska

Kolejność wykonywania działań to, jak można zauważyć w Internecie, jeden z największych problemów, jakie przeciętne osoby mają z matematyką. Regularnie od wielu lat pojawia się w mediach społecznościowych jakiś wariant zagadki „oblicz 6/2(2+1)”, gdzie ludzie się kłócą, czyja odpowiedź jest prawidłowa. W idealnym świecie takich problemów nie powinno być. Dlatego powstały alternatywne sposoby zapisu działań matematycznych pozbywające się nawiasów, takie jak np. odwrotna notacja polska. Nasz świat idealnym jednak nie jest, więc męczymy się z nawiasami, ale poznajmy tę notację, bo akurat w świecie informatyki ma ona duże znaczenie.

Czytaj więcej

Dziel i zwyciężaj a mnożenie

Podczas nauki programowania jedną z pierwszych koncepcji z zakresu projektowania algorytmów, którą poznajemy, jest „dziel i zwyciężaj”. Poznaje się ją w kontekście wyszukiwania binarnego, a niektórzy nauczyciele przypominają, że strategia ta jest też wykorzystywana w najszybszych algorytmach sortowania. Jednak wiesz, że to podejście ma jeszcze więcej zastosowań? W artykule chciałem pokazać moim zdaniem jedno z ciekawszych — algorytm Karacuby, czyli algorytm szybkiego mnożenia oparty na „dziel i zwyciężaj”.

Czytaj więcej