Algorytm

Przykład czytelnie opisanego algorytmu w formie pseudokodu

Algorytm – (nie)skończony ciąg niejasno zdefiniowanych czynności, które w pokrętny i zawiły sposób prowadzą do kompletnej frustracji programisty, użytkownika i procesora. Według niepotwierdzonych teorii algorytmy mają służyć rozwiązywaniu problemów.

Rodzaje

Żeby się nie nudzić, matematycy i informatycy wymyślili całą masę rodzajów algorytmów.

• Dziel i zwyciężaj – technika ta polega na dzieleniu zadania na wiele malutkich części. Następnie owe części rozdaje się praktykantom do rozwiązania. Dzięki temu możemy mieć pewność, że każda z części zostanie źle rozwiązana i po połączeniu błędy te się zniwelują.
• Programowanie dynamiczne – podobnie jak w poprzedniej metodzie dzielimy zadanie na kilka mniejszych i łatwe części dajemy rozwiązać komuś innemu. Następnie na podstawie tych rozwiązań zgadujemy wynik.
• Metoda zachłanna – czyli metoda na pałę. Rozwiązujemy problem jak popadnie, a na koniec zabieramy zachłannie wypłatę dla całego zespołu dla siebie.
• Programowanie liniowe – łączymy wszystkie literki, kropeczki, krówki czy co tam mamy linią. Po tym zabiegu wystarczy rzucić okiem na kartkę, a rozwiązanie samo się ujawni.
• Brute force – metoda na zastraszanie. Do jej przeprowadzenia niezbędna jest jakaś broń, nada się np. bejsbol albo wałek kuchenny. Rozkazujemy komputerowi rozwiązać problem pod groźbą pobicia wyżej wymienioną bronią. Gdy to nie da oczekiwanego rezultatu, namy w komputer do skutku. Efekt gwarantowany, aczkolwiek metoda ta może być nieco czasochłonna.
• Heurystyka – piszemy algorytm, który działa dla jakichś danych byleby działał. Następnie modlimy się żeby wykonywało się to poprawnie.
• Rekurencja – tę metodę da się wyjaśnić tylko przy pomocy rekursji.
• Praca równoległa – ta metoda polega na wzmaganiu ducha sportu i rywalizacji w komputerach. Dajemy to samo zadanie kilku komputerom i każemy im je rozwiązać na czas. Komputer który wygra w nagrodę dostaje nowy dysk twardy/RAM/procesor.
• Sztuczna inteligencja – czyli zrzucanie całej roboty na komputer.

Główny artykuł: Sztuczna inteligencja

• Algorytmy ewolucyjne – tworzymy kilka byle jakich algorytmów, zostawiamy je w ciepełku i czekamy aż zaczną się rozmnażać. Po kilku pokoleniach powinny się pojawić jakieś sensowne programy. Jedyną wadą tej metody jest możliwość narażenia się lokalnemu guślarzowi za stosowanie niezgodnych z Biblią praktyk ewolucyjnych.
• Algorytmy kwantowe – (bardzo) teoretyczne metody oparte na splątywaniu ze sobą kwantów i skwarków. Dokładnie nie wiadomo jak to niby ma działać, ale według niekoniecznie trzeźwych fizyków algorytmy kwantowe zrewolucjonizują kryptografię.

Przykłady algorytmów

• Sortowanie bąbelkowe – bardzo intuicyjny algorytm, aby go należycie wykonać należy wrzucić wszystkie liczby do garnka z wodą (koniecznie posolić!) i wstawić na gaz. Podczas gotowania na powierzchni wody zaczną się pojawiać bąbelki z liczbami w środku. Należy wtedy wyjmować liczby z garnka w kolejności, w jakiej wypływały na wierzch.
• Sortowanie szybkie – w gruncie rzeczy działa tak samo jak poprzedni algorytm, tyle że trzeba to robić szybciej. Można sporo czasu zaoszczędzić poprzez zatrudnienie kilku murzynów do wyciągania pierogów liczb i dokupienie większej ilości garnków.
• Algorytm Dijkstry – metoda opracowana przez wkego korkami Holendra Edsgera Dijkstrę. Pozwala znaleźć najdłuższą i najbardziej pokrętną drogę z punktu A do punktu B przez punkty H, W, D i oczywiście P.
• Stacja rozrządowa Dijkstry – bardzo polski algorytm, mimo że jest autorstwa Holendra. Pozwala zamienić normalne działanie matematyczne – na przykład $x{\frac {a}{b-c}}$ na jakże czytelną odwrotną notację polską czyli $abc-/x*$.
• Eliminacja Gaussa – właściwie to jest zabawa polegająca na znalezieniu i zabiciu Gaussa ukrytego w układzie równań liniowych. Ulubiona rozrywka znudzonych studentów matematyki.

Złożoność obliczeniowa

Znudzeni problemami codziennego życia, informatycy obmyślili pewnego dnia zabawę – zawody gdzie zadaniem jest zaprojektować jak najwolniejszy algorytm. Na sędziów wybrali matematyków, którzy w przypływie inwencji wymyślili nawet sposób oceniania – notację O. Można w ten sposób wiarygodnie^{[potrzebne źródło]} oceniać szybkość zżerania RAMu i cykli procesora przez algorytm.

• $O(1)$ – podejrzałeś wynik, przyznaj się draniu!
• $O(log_{n}(n))$ – to przecież to samo, weź się wreszcie do roboty;
• $O(log(n))$ – albo jesteś algorytmicznym geniuszem, albo się pomyliłeś przy szacowaniu;
• $O(n)$ – no, wreszcie jakiś sensowny wynik;
• $O(nlog(n))$ – zazwyczaj tyle wychodzi dla skomplikowanych algorytmów, w praktyce okazuje się, że to jednak $O(n^{2})$;
• $O(n^{1.001}log(log(n))$ – żebyś nie wiem jak się spinał, nie wyjdzie ci z tego $O(nlog(n))$;
• $O(n^{2})$ – słabo, próbuj dalej!
• $O(n^{3})$ – toż to zwykły, chwy brute-force!
• $O(n!)$ – chyba przesadziłeś z tą rekurencją;
• $O(n^{n})$ – tak zwane $O(kurwa!)$;
• $O\left(n^{n^{n}}\right)$ – zaraz, ty chyba nie…
• $O\left(n_{n_{n_{n_{n_{n_{n}n}n}n}n}n}^{n^{n^{n^{n^{n^{n}n}n}n}n}n}n\right)$ – co… Co to w ogóle, ka, ma być?!

Zobacz też

• programowanie na kartce

Przypisy

Zobacz więcej artykułów w portalu o informatyce.