Algorytmy – wprowadzenie

Wielu początkujących programistów, szybko po przeczytaniu pierwszych rozdziałów o wybranym języku programowania, rzuca się do kodu i próbuje od razu tworzyć swoje aplikacje, uważając, że są w stanie je wykonać. Dość szybko zaliczają bolesne zderzenie z rzeczywistością, polegające na braku pomysłu jak dane elementy zrealizować, inne zaś są wolne lub wadliwe, pojawiają się problemy z brakami w znajomości konstrukcji bardziej zaawansowanych w danym języku – i przede wszystkim – wychodzi brak znajomości algorytmów i sposobu ich implementacji w wybranej technologii. Zastanawiające przy okazji jest to, że bez względu od poziomu egocentryzmu, popadamy w samo-zachwyt już przy początku nauki, jedni mniej, inni bardziej, zakrawając o farsę.
Ale czemu tak się dzieje? Tu do głosu dochodzi efekt Dunninga-Krugera. czyli zjawisko psychologiczne, polegające na przecenianiu swoich umiejętności przez osoby (jeszcze) niewykwalifikowane w danej dziedzinie, w opozycji do osób wysoko wykwalifikowanych, które mają znacznie bardziej samokrytyczne mniemanie o sobie.

Pierwszy peak, nazywany górką głupoty – to właśnie tutaj, uważamy się za ekspertów, kompletnie nimi nie będąc. Tutaj ignorancja przewyższa racjonalny ogląd sytuacji. Po przekroczeniu i „wyzerowaniu”, rośnie samoocena wraz ze wzrostem kompetencji. Istotnym jest, by przebrnąć przez tę górkę, bo wtedy mamy szanse na pokonanie ignoranckiej natury i realną drogę do poziomu eksperckiego. Wielu młodych w dziedzinie IT jej nie przekracza, tkwiąc w niej w przekonaniu, że są alfą i omegą, a to błąd, a zarazem problem, bo efekt kładzie cień na obiektywność nie tylko oceny umiejętności własnych ale również nie potrafią właściwie ocenić umiejętności innych ludzi – stąd też sporo kłótni na forach i grupach internetowych, szczególnie między reprezentantami tej samej grupy „peakowej”.

Tu warto przytoczyć słowa Darwina, które są esencją tego efektu.

 „Ignorancja częściej jest przyczyną pewności siebie, niż wiedza”

Charles Darwin

Ok, wróćmy do meritum – algorytmy. W początkowej fazie fascynacji programowaniem, zapominamy, nie wiemy czym są lub kwestionujemy zasadność uczenia się algorytmów i wzorców projektowych (wzorce są równie ważne, ale o nich innym razem). To zgubne podejście, które bardzo szybko się mści i demotywuje, co skutkuje zatrzymaniem postępu w nauce lub nawet porzuceniem całej idei uczenia się programowania.

Czym są te przeklęte algorytmy?

Na dobrą sprawę, algorytmy nie są domeną programowania jako takie. Nie jest to jakaś magiczny Graal koderów, a element codziennej matematyki. Idąc za definicją z Wikipedii:

Algorytm – skończony ciąg jasno zdefiniowanych czynności koniecznych do wykonania pewnego rodzaju zadań, sposób postępowania prowadzący do rozwiązania problemu. Można go przedstawić na schemacie blokowym.

Wikipedia – https://pl.wikipedia.org/wiki/Algorytm

Tak naprawdę, algorytmem możemy nazwać nawet sposób przejścia spod bramy zamkniętego osiedla, przez alejki, drzwi budynku, aż po konkretny pokój w mieszkaniu. Wymaga to instrukcji, jak iść, gdzie skręcić, co zrobić, jaki kod wprowadzić, itd. – taki opis, składający się z kroków, to właśnie algorytm dostania się do konkretnego pokoju. Innym przykładem, oklepanym do omdlenia, jest przepis kulinarny – ale pełny, nie lista składników, lecz cały przepis z opisem czynności co, z czym, ile, jak i gdzie. Trudne? Nie, ale w matematyce i programowaniu już tak łatwe nie jest.
Jakieś przykłady? Z pewnością znasz algorytm ze szkoły, mianowicie chodzi o największy wspólny dzielnik NWD, algorytmem Euklidesa, ponadto algorytm Fermata czy mrówkowy też powinieneś z zasłyszenia znać.
Z pewnością też – w okolicach tematu komputerów jako takich – znane są algorytmy kompresji danych czy kryptograficzne, przy początku przygody z programowaniem, powinieneś już znać algorytmy sortowania, przeszukiwania drzew i unifikacji.

Algorytmy możemy klasyfikować w kilku kategoriach, pod kątem sposobu tworzenia, sposobu implementacji, przeznaczenia czy sposobu wykonywania obliczeń. Podziały choć nie stanowią rozprawy naukowej wielkości trzech tomów, są wokół tych podziałów pewne kontrowersje.

Rodzaje algorytmów

Podział algorytmów, ze względu na paradygmat ich konstrukcji:

• dziel i zwyciężaj – Problem dzielony jest na problemy składowe, które to znów są dzielone na mniejsze podproblemy, aż jednostkowo są łatwe do rozwiązania.
• programowanie dynamiczne – Metoda bardziej złożona. Problem dzieli się na kilka elementów, po czym oceniania jest ważność każdego z nich, a wyniki analizy części z prostszych, wykorzystuje się w procesie rozwiązania problemu głównego.
• metoda zachłanna – W tej metodzie, nie zważa się na dokładną analizę a wybiera najbardziej obiecującą w danym momencie drogę do rozwiązania.
• programowanie liniowe – oceniamy rozwiązanie problemu przez pewną funkcję jakości i szukamy jej minimum
• wyszukiwanie wyczerpujące – polega na przeszukiwaniu zbioru danych, aż do odnalezienia rozwiązania
• heurystyka – na podstawie własnego doświadczenia tworzymy algorytm, który działa w najbardziej prawdopodobnych warunkach; rozwiązanie zawsze jest przybliżone.

Sposoby implementacji algorytmów

Podział algorytmów ze względu na sposób ich implementacji w formie programu komputerowego, nie determinuje języka programowania, choć niektóre rozwiązania mogą nie być możliwe do realizacji w danym języku przez brak odpowiednich mechanizmów w nim zawartych – np. nie zaimplementujemy obiektowo algorytmu, w języku, który nie wspiera paradygmatu programowania obiektowego.

• proceduralne – algorytm dzieli się na serie podstawowych procedur. Wiele algorytmów ma wspólne biblioteki standardowych procedur, skąd można je wywoływać w razie potrzeby – i z reguły są znacznie lepiej napisane niż własne.
• sekwencyjne – wykonywanie poszczególnych procedur algorytmu, według kolejności ich wywołań, krok po kroku. Jednocześnie pracuje tylko jedna procedura
• wielowątkowe – procedury wykonywane są sekwencyjnie, ale kolejność ich wykonania jest trudna do przewidzenia dla programistę, ze względu na pracę w wielu wątkach równolegle, każda sekwencja w oddzielnym, niezależnym wątku.
• równoległe – wiele procedur wykonywanych jest w tym samym czasie, mogą one wymieniać się danymi, są zarządzanie/synchronizowane
• rekurencja – funkcja, która wywołuje sama siebie, aż do uzyskania wyniku lub braku rozwiązania.
• obiektowość – wykorzystuje się dobrodziejstwo programowania obiektowego aby procedury i dane połączyć w klasy reprezentujące najważniejsze elementy algorytmu oraz stan wewnętrzny wykonującego je systemu.
• algorytm probabilistyczny – działa poprawnie z bardzo wysokim prawdopodobieństwem, ale wynik nie jest stuprocentowy.

Czy mamy coś innego w menu? Ależ oczywiście, temat algorytmów jest tematem rzeką, o rwącym nurcie i dużej głębokości – trzeba uważać by się nie zakrztusić.
Do zestawu podstawowego, możemy dorzucić całe grupy algorytmów specjalistycznych, od algorytmów sztucznej inteligencji – które pomagają w problemach niedeterministycznych – krótko mówiąc, problemach, które nie mają jednoznacznego, prostego rozwiązania, przykładem może tu być rozpoznawanie pisma odręcznego czy twarzy na obrazie z kamery. Ponadto, mamy algorytmy kwantowe i genetyczne – gdzie te pierwsze będą dobrze znane ludziom zainteresowanym tematem kryptografii, natomiast drugie, polegają na obserwacji praw natury, doboru naturalnego i dziedziczenia.

Z biegiem czasu, na łamach tego bloga będę przybliżał wymienione algorytmy, jak i nie omieszkam opowiedzieć o takich tworach jak algorytm de Casteljau, algorytm do tworzenia diagramu Voronoi (czyli tesselacji), malarza, Warnocka czy algorytmy wykrywania kolizji.

Jak widać, jest w czym wybierać, i to co adepta nauki programowania czeka, to długa droga, często wyboista, w poznawaniu całej gamy algorytmów, niejednokrotnie ratujących odwłok w codziennej pracy, bo nie oszukujmy się – lepiej nie wynajdywać koła na nowo, szczególnie jak jest już zaimplementowane w bardzo optymalny sposób w ogólnodostępnej bibliotece 😉