Hlavní strana | See live article

Algoritmus

Algoritmus (nebo dřívějším pravopisem algorithmus) je přesný návod či postup, kterým lze vyřešit daný typ úlohy. Pojem algoritmu se nejčastěji objevuje při programování, kdy se jím myslí teoretický princip řešení problému (oproti přesnému zápisu v konkrétním programovacím jazyce). Obecně se ale algoritmus může objevit v jakémkoli jiném vědeckém odvětví. Jako jistý druh algoritmu se může chápat i např. kuchyňský recept. V užším smyslu se slovem algoritmus rozumí pouze takové postupy, které splňují některé silnější požadavky:

Table of contents
1 Vlastnosti algoritmů
2 Druhy algoritmů
3 Etymologie
4 Reference
5 Podívejte se též na

Vlastnosti algoritmů

; Konečnost : Každý algoritmus musí skončit v konečném počtu kroků. Tento počet kroků může být libovolně velký (podle rozsahu a hodnot vstupních údajů), ale pro každý jednotlivý vstup musí být konečný. Postupy, které tuto podmínku nesplňují, se mohou nazývat výpočetní metody. Speciálním příkladem nekonečné výpočetní metody je reaktivní proces, který průběžně reaguje s okolním prostředím. ; Determinismus : Každý krok algoritmu musí být jednoznačně a přesně definován; v každé situaci musí být naprosto zřejmé, co a jak se má provést, jak má provádění algoritmu pokračovat. Protože běžný jazyk obvykle neposkytuje naprostou přesnost a jednoznačnost vyjadřování, byly pro zápis algoritmů navrženy programovací jazyky, ve kterých má každý příkaz jasně definovaný význam. Vyjádření výpočetní metody v programovacím jazyce se nazývá program. ; Vstup : Algoritmus obvykle pracuje s nějakými vstupy, veličinami, které jsou mu předány před započetím jeho provádění, nebo v průběhu jeho činnosti. Vstupy mají definované množiny hodnot, jichž mohou nabývat. ; Výstup : Algoritmus má alespoň jeden výstup, veličinu, která je v požadovaném vztahu k zadaným vstupům, a tím tvoří odpověď na problém, který algoritmus řeší. ; Efektivita : Obecně požadujeme, aby algoritmus byl efektivní, v tom smyslu, že požadujeme, aby každá operace požadovaná algoritmem, byla dostatečně jednoduchá na to, aby mohla být alespoň v principu provedena v konečném čase pouze s použitím tužky a papíru. ; Obecnost : Algoritmus neřeší jeden konkrétní problém (např. „jak spočítat 3×7“), ale obecnou třídu obdobných problémů (např. „jak spočítat součin dvou celých čísel“).

Je třeba poznamenat, že kritérium konečnosti je pro praktické použití ještě příliš slabé. Užitečný algoritmus musí skončit nejenom v konečném počtu kroků; měl by skončit ve velice konečném počtu kroků, v nějakém rozumném čase. Např. existuje jednoduchý algoritmus, který dokáže určit, jestli v dané šachové pozici může hráč na tahu vynutit vítězství. (Takže by v libovolné pozici dokázal určit nejlepší možný tah.) Tento algoritmus se však nedá použít, protože by na svou činnost potřeboval nepředstavitelně ohromné množství času, jakkoli je toto množství konečné.

V praxi jsou proto předmětem zájmu hlavně takové algoritmy, které jsou v nějakém smyslu kvalitní. Takové algoritmy splňují různá kritéria, měřená např. počtem kroků potřebných pro běh algoritmu, nebo jednoduchost či elegance algoritmu. Problematikou efektivity algoritmů, tzn. metodami, jak z několika známých algoritmů řešících konkrétní problém vybrat ten nejlepší, se zabývají odvětví počítačové vědy nazývané algoritmická analýza a teorie složitosti.

Druhy algoritmů

Algoritmy můžeme řadit do mnoha skupin. Rekurzivní algoritmy využívají při své definici samy sebe pro práci nad nějakou částí úlohy. Hladové algoritmy se k řešení propracovávají po jednotlivých rozhodnutích, která, jakmile jednou učiněna, už nejsou dále zvažová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čů, 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ý algoritmus si za cíl neklade nalézt přesné řešení, ale pouze nějaké vhodné přiblížení; používá 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).

Etymologie

Slovo algoritmus pochází ze jména významného perského matematika žijícího v první polovině 9. století (cca 780–840), kterým byl Abū ʻAbd Allāh Muhammad ibn Mūsā al-Khwārizmī (أبو عبد الله محمد بن موسى الخوارزمي) (doslova „Otec Abdulláha, Mohameda, syn Mojžíšův, pocházející z města Khwārizm“; region Khwārizm se nachází jižně od Aralského moře). 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“; abacisté počítali pomocí abaku, algoristé pomocí algorismů.

Postupem času se kvůli neznalosti původu slova jeho podoba měnila, záměnou arabského kořene s kořenem řeckého slova αριθμός (arithmos) se z algorismu stal algorithmus. (Později bylo v některých jazycích včetně češtiny th změněno na t, v se vrátilo s.) Toto slovo se používalo jako označení různých matematických postupů, např. v 18. století označoval latinský termín algorithmus infitesimalis „metodu výpočtů s využitím nekonečně malých veličin, vynalezenou Leibnizem“. Slovo algoritmus v dnešním významu se používá až zhruba od 20. století.

Reference

  1. heslo Algorithmus. Ottův slovník naučný I, p. 857
  2. Donald E. Knuth: The Art of Computer Programming, Vol 1–3, Addison Wesley 1998. ISBN 0201485419. Klasické dílo oboru, definitivní příručka.
  3. Gaston H. Gonnet, Ricardo Baeza-Yates: Zdrojové texty programů v Handbook of Algorithms and Data Structures.
  4. Dictionary of Algorithms and Data Structures. „Slovník algoritmů, technik, datových struktur, typických problémů a příslušných definic.“

Podívejte se též na