Algoritmus

Autor: Petr Věžník

Klíčová slova: algoritmus, vlastnosti algoritmů, definice algoritmů, reprezentace a zápis algoritmů

Synonyma: návod, postup

Související pojmy:

nadřazené - informatika, matematika

podřazené - vývojový diagram, strukturogram, rozhodovací tabulka, HIPO diagram

Definice

al-Khwārizmī

Samotné slovo algoritmus je odvozeno ze jména významného perského matematika a astronoma jménem Abū ‘Abd Allāh Muhammad ibn Mūsā al-Khwārizmī[4]. Ten ve svém díle vytvořil systém arabských číslic a základy algebry. Jeho jméno bylo do latinky převedeno jako algoritmus a stalo se synonymem pro označení různých matematických postupů. Teprve zhruba od 20. století se používá v dnešním významu slova a je jedním ze základních pojmů v matematice. „Algoritmem rozumíme soubor přesně stanovených pravidel, určující pořadí daného konečného systému operací, který zabezpečuje řešení všech úloh daného typu"[2]. Nebo také můžeme říci, že „algoritmus je možno chápat i jako mlýnek na data. Nasypeme-li do něj správná data a zameleme, obdržíme požadovaný výsledek“ [3, s. 28].

Přestože se pojem algoritmus objevuje především v informatice a matematice, do jisté míry se s ním můžeme setkat i v dalších vědních oborech. V širším slova smyslu se jedná o jakýsi návod nebo postup. V užším slova smyslu se algoritmem rozumí pouze takové postupy, které splňují definované vlastnosti.

Vlastnosti algoritmů

Jak již bylo řečeno výše, každý postup musí splňovat definované vlastnosti, abychom jej mohli klasifikovat jako algoritmus. Jaké to jsou vlastnosti je nastíněno dále v textu. Nejprve je však nutné varovat, že teorie se zde trochu rozchází. Můžeme nalézt jak rozličné definice vlastností, tak nesjednocenou terminologii. Proto v textu zaměříme pouze na ty nejdůležitější.

Konečnost

Každý algoritmus musí obsahovat pouze konečné množství kroků, po kterých skončí (jinými slovy, nezacyklí se). Bez této vlastnosti by byl algoritmus nepoužitelný.

Opakovatelnost

Jsou-li zadána stejná data, algoritmus vždy dospěje ke stejným výsledkům

Rezultativnost

Algoritmus vede vždy ke správnému výsledku

V literatuře je možné se dočíst také o dalších vlastnostech, jako je např. obecnost, determinovatelnou, hromadnost, jednoznačnost, aj.

Dělení algoritmů

Algoritmy můžeme klasifikovat různými způsoby, přičemž jeden algoritmus může patřit zároveň do více skupin. Narozdíl od vlastností algoritmů, zde je terminologie poměrně sjednocená.

• Rekurzivní algoritmy - využívají a odkazují sami na sebe
• Hladové algoritmy - propracovávají se k řešení pomocí jednotlivých rozhodnutí, která jakmile jsou učiněna, už nejsou dále revidována
• Iterativní algoritmy - opakují některou svou část (cykly)
• Algoritmy typu rozděl a panuj - problém na menší podproblémy a dílčí řešení slučují
• Algoritmy dynamického programování - řeší problémy od nejjednodušších po složitější, přičemž využívají výsledky již vyřešených jednodušších problémů
• Pravděpodobnostní algoritmy - některá rozhodnutí provádějí náhodně
• Paralelní algoritmy - využívají více počítačů, úlohu mezi ně rozdělí a díky tomu dospějí k rychlejšímu výsledku
• Genetické algoritmy – napodobují biologické evoluční procesy
• Heuristické algoritmy – nehledají přesná řešení, pouze nějaká vhodná přiblížení

Reprezentace a zápis algoritmů

ukázka vývojového diagramu

Zde je vysvětleno několik základních způsobů, jak můžeme zapsat algoritmy. Správně zapsat algoritmus je důležité především pro jeho další využití, případně úpravu.

• Slovní popis – slovní popis v přirozeném jazyce. Vysvětlení krok po kroku, co algoritmus v dané fázi provádí a jak bude reagovat
• Vývojový diagram - grafické znázornění algoritmu, řešení úlohy jednotnými značkami a zkratkami
• Strukturogram – Úspornější znázornění algoritmu, kombinace grafického a textového popisu
• Datově orientovaný diagram HIPO – (z angl. Hierarchy plus Input- Process- Output), je grafickým vyjádřením funkčního členění problému, struktury dat a postupu řešení problému při různém stupni podrobnosti [3].
• Rozhodovací tabulka – používá se zejména při složitějších větvení, tabulka rozdělená do kvadrantů

Použitá literatura

1. DVORSKÝ, Jiří. Algoritmy I : Pracovní verze skript [online]. 2008 [cit. 2010-06-10]. Dostupné z WWW: <http://www.cs.vsb.cz/dvorsky/Download/Algoritmy/ZakladyAlgoritmizace28022007.pdf>.
2. ŠALÁT, Tibor. Malá encyklopedie matematiky. 1. vyd. Bratislava : Obzor, 1967. 692 s. ISBN 65-083-87.
3. Algoritmy: Teoretický úvod [online]. 2006 [cit. 2010-06-11]. Dostupný z WWW: <http://www.manualy.net/article.php?articleID=12>.
4. History of mathematics for young mathematicians: Al-Khwarizmi [online]. [cit. 2010-06-11]. Dostupný z WWW: <http://www.mathsisgoodforyou.com/people/alkhwarizmi.htm>.