Algoritmus

Autor: Petr Věžník

Klíčová slova:

Synonyma: ---

Související pojmy:

nadřazené -

podřazené - ---

Definice

Abū ʿAbdallāh Muḥammad ibn Mūsā 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[x].

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.

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