Obsah
Algoritmus
Algoritmus je teoretický základ veškerého programování. Aby mohl být postup považován za algoritmus, musí splňovat několik základních vlastností:
- Konečnost: Musí skončit po konečném počtu kroků.
- Determinovanost: Každý krok musí být jasně definován; za stejných podmínek musí dát vždy stejný výsledek.
- Obecnost: Neměl by řešit pouze jeden konkrétní příklad (např. 2+2), ale celou třídu úloh (např. sčítání dvou čísel).
- Resultativnost: Musí mít jasný výstup (řešení).
1. Způsoby zápisu algoritmu
Než programátor začne psát kód, často si algoritmus navrhne v jedné z těchto forem:
- Slovní popis: Jednotlivé kroky v přirozeném jazyce.
- Vývojový diagram: Grafické znázornění pomocí bloků a šipek.
- Pseudokód: Mezistupeň mezi lidskou řečí a programovacím jazykem (např. „IF teplota > 30 THEN zapni klimatizaci“).
2. Složitost algoritmu (O-notace)
V informatice nás nezajímá jen to, zda algoritmus funguje, ale také jak je rychlý a kolik paměti spotřebuje. K tomu slouží tzv. Asymptotická složitost ($O$):
| Složitost | Název | Příklad | |
|---|---|---|---|
| $O(1)$ | Konstantní | Přístup k prvku v poli podle indexu. | |
| $O(\log n)$ | Logaritmická | Binární vyhledávání v seřazeném seznamu. | |
| $O(n)$ | Lineární | Prohledání neseřazeného seznamu prvek po prvku. | |
| $O(n | 2)$ | Kvadratická | Jednoduché třídicí algoritmy (např. Bubble Sort). |
3. Typické příklady algoritmů
- Třídicí (Sorting): Seřazení seznamu jmen podle abecedy (QuickSort, MergeSort).
- Vyhledávací (Searching): Nalezení konkrétního slova v textu.
- Grafové: Nalezení nejkratší cesty v mapě (Dijkstrův algoritmus) – základ pro GPS navigace.
- Kryptografické: Šifrování dat, aby je nikdo nepovolaný nepřečetl (AES, RSA).
- Rekurzivní: Algoritmus, který volá sám sebe (např. výpočet faktoriálu).
4. Algoritmy a Umělá inteligence
V oblasti strojového učení se algoritmy liší tím, že se „učí“ z dat. Místo toho, aby programátor přesně popsal každý krok („pokud uvidíš uši, je to kočka“), algoritmus analyzuje tisíce obrázků a sám si vytvoří statistický model pro rozpoznání.
5. Proč je návrh algoritmu důležitý?
Špatně navržený algoritmus může fungovat na malém množství dat, ale při velkém objemu (Big Data) může trvat roky, než doběhne. Optimalizace algoritmu často přinese větší zrychlení než nákup dražšího hardwaru.
Zajímavost: Slovo „algoritmus“ vzniklo latinizací jména perského matematika z 9. století, který se jmenoval Al-Chorezmí. Ten položil základy algebry a systematického řešení rovnic.