Algoritmus
Algoritmus je schematický postup pro řešení určitého druhu problémů, který je prováděn pomocí konečného množství přesně definovaných kroků. Ačkoliv se dnes tento pojem používá především v informatice a přírodních vědách obecně, tak je jeho působnost daleko širší (kuchyňské recepty, návody a postupy...). Samotné slovo „algoritmus“ pochází ze jména perského matematika 9. století Abu Jafar Muhammada ibn Mūsā al-Chwārizmího, který ve svých dílech položil základy algebry (arabské číslice, řešení lineárních a kvadratických rovnic).
Vlastnosti algoritmů
- Konečnost – algoritmus má konečné množství kroků.
- Korektnost – algoritmus skončí pro libovolná (korektní) data správným výsledkem v konečném množství kroků.
- Obecnost – algoritmus řeší všechny úlohy daného typu.
Dělení algoritmů
Rekurzivní a iterativní algoritmy
Iterativní algoritmus je takový, který spočívá v opakování určité své části (bloku). Rekurzivní algoritmus naproti tomu volá sám sebe (na dílčí podproblémy), dokud nenarazí na sadu triviálně řešitelných podproblémů, z nichž poté skládá celkové řešení. Výhoda rekurzivních algoritmů je v jejich snadno čitelném a kompaktním zápisu. Nevýhodou je nutnost dodatečných systémových prostředků pro jednotlivá rekurzivní volání. Každý rekurzivní algoritmus lze převést do iterativní podoby (a často tak činí automaticky i kompilátor).
Deterministické a nedeterministické algoritmy
Deterministický je takový algoritmus, který má v každém svém kroku právě jednu možnost, jak pokračovat. Nedeterministický jich má více. Příkladem může být deterministický a nedeterministický automat.
Sériové, paralelní a distribuované algoritmy
Sériový algorimus vykonává všechy kroky v sérii (jeden po druhém), paralelní algoritmus tyto kroky vykonává zároveň (ve více vlákech) a distribuovaný algoritmus kroky vykovává zároveň na více strojích.
Asymptotická složitost algoritmu
Asymptotická složitost algoritmu charakterizuje počet provedených operací v závislosti na velikosti dat. Například pokud procházíme pole, pak složitost bude lineární (na každý prvek připadá konstantní množství operací), pokud jej ovšem řadíme například Bubble sortem, pak složitost bude kvadratická (na n prvků bude připadat n2 operací).
Třída složitosti
Třída složitosti stanovuje obtížnost rozhodnutelnosti daného problému na Turingově stroji.
- Třída P – obsahuje problémy rozhodnutelné v polynomiálním čase.
- Má daný graf kostru o velikosti maximálně k?
- Existuje v daném acyklickém grafu mezi uzly a a b cesta, jejíž délka je nejvýše k?
- Třída NP – obsahuje problémy, které jsou rozhodnutelné pomocí nedeterministického Turingova stroje v polynomiálním čase – tzn. jsme schopni ověřit jejich řešení v polynomiálním čase.
- Lze daný graf obarvit maximálně k barvami?
- Existuje v daném grafu hamiltonovská kružnice?
- Existuje v daném grafu klika o alespoň k vrcholech?
Literatura
- WRÓBLEWSKI, Piotr. Algoritmy : Datové struktury a programovací techniky. Brno : Computer press, 2004. 351 s. ISBN 80-251-0343-9.
- KVASIL, Bohumil, et al. Algoritmus. In Malá československá encyklopedie. Praha : Academia, 1984. s. 108.
- VELEBIL, Jiří. Diskrétní matematika : Text k přednášce. Praha : [s.n.], 2007. 197 s.
