Algorytm

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 genetyczne –
• Algorytmy kwantowe –

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 –
• Algorytm Dijkstry –
• Algorytm Euklidesa –
• Stacja rozrządowa Dijkstry –
• Eliminacja Gaussa –

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ć?!

Przypisy

Szablon:Informatyka