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ī

Slovo algoritmus pochází ze jména významného perského matematika žijícího v první polovině 9. století (cca 780–840 n. l.), kterým byl Abū ‘Abd Allāh Muhammad ibn Mūsā al-Khwārizmī. Tento učenec ve svém díle prakticky vytvořil systém arabských číslic a základy algebry (konkrétně metody řešení lineárních a kvadratických rovnic), jejíž název pochází přímo z titulu tohoto díla (Kitūb al-jabr waāl-muqūbala). Jeho jméno bylo do latiny převedeno jako algorismus, a původně znamenalo: „provádění aritmetiky pomocí arabských číslic

Pojem algoritmus je jedním ze základních pojmů v matematice. Algoritmem se rozumí 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.

Přestože se pojem algoritmus objevuje především v informatice, 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í jasně definované vlastnosti (viz dále).

Vlastnosti algoritmů

Konečnost

Požadovaný výsledek musí být poskytnut v „rozumném" čase (pokud by výpočet trval na nejrychlejším počítači např. jeden milion let, těžko bychom mohli hovořit o algoritmu řešení, nemluvě o výpočtu, který by neskončil vůbec). Za rozumný lze považovat čas, kdy nám výsledek výpočtu k něčemu bude.

Hromadnost

Vstupní data nejsou v popisu algoritmu reprezentována konkrétními hodnotami, ale spíše množinami, ze kterých lze data vybrat (např. při řešení trojúhelníka mohou být velikosti stran desetinná čísla). Při popisu algoritmu v programovacím jazyce se to projeví tím, že vstupy do algoritmu jsou označeny symbolickými jmény.

Jednoznačnost

Každý předpis je složen z kroků, které na sebe navazují. Každý krok můžeme charakterizovat jako přechod z jednoho stavu algoritmu do jiného, přičemž každý stav je určen zpracovávanými daty. Tím, jak data v jednotlivých stavech algoritmu vypadají, musí být jednoznačně určeno, který krok následuje (např: V řešení trojúhelníka může nastat situace, kdy vychází na základě vstupních dat jedno nebo dvě řešení. Situace je tedy nejednoznačná, řešení musí být jednoznačné, tzn. v předpisu se s touto možností musí počítat a musí v něm být návod, jak ji řešit.).

Opakovatelnost

Při použití stejných vstupních údajů musí algoritmus dospět vždy k témuž výsledku.

Rezultativnost

Algoritmus vede ke správnému výsledku.

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

• Rekurzivní algoritmy, které využívají (volají) samy sebe.
• Hladové algoritmy se k řešení propracovávají po jednotlivých rozhodnutích, která, jakmile jsou jednou učiněna, už nejsou dále revidována.
• Algoritmy typu rozděl a panuj dělí problém na menší podproblémy, na něž se rekurzivně aplikují (až po triviální podproblémy, které lze vyřešit přímo), po čemž se dílčí řešení vhodným způsobem sloučí.
• Algoritmy dynamického programování pracují tak, že postupně řeší části problému od nejjednodušších po složitější s tím, že využívají výsledky již vyřešených jednodušších podproblémů. Mnoho úloh se řeší převedením na grafovou úlohu a aplikací příslušného grafového algoritmu.
• Pravděpodobnostní algoritmy (někdy též probabilistické) provádějí některá rozhodnutí náhodně či pseudonáhodně.
• V případě, že máme k dispozici více počítačů (procesorů nebo jader), můžeme úlohu mezi ně rozdělit, což nám umožní ji vyřešit rychleji; tomuto cíli se věnují paralelní algoritmy.
• Genetické algoritmy pracují na základě napodobování biologických evolučních procesů, postupným „pěstováním“ nejlepších řešení pomocí mutací a křížení. V genetickém programování se tento postup aplikuje přímo na algoritmy (resp. programy), které jsou zde chápany jako možná řešení daného problému.
• Heuristické algoritmy si za cíl nekladou nalézt přesné řešení, ale pouze nějaké vhodné přiblížení; používají se v situacích, kdy dostupné zdroje (např. čas) nepostačují na využití exaktních algoritmů (nebo pokud nejsou žádné vhodné exaktní algoritmy vůbec známy).

Reprezentace a zápis algoritmů

• Slovním popisem – slovní popis v přirozeném jazyce
• Vývojovým diagramem (blokové schéma) – grafické znázornění algoritmu řešení úlohy jednotnými značkami a zkratkami (tento způsob kombinovaný se slovním popisem zde budu používat, tudíž přibude i článek na toto téma).
• Strukturogramy – používá obdobné symboly ale přesnější, tento systém přesně splňuje podmínky důležité pro strukturované programování
• Datově orientované diagramy 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.
• Rozhodovací tabulky – používané při velmi složitých větveních.

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>.