Algoritmus je přesný návod či postup, kterým lze vyřešit daný typ úlohy. Pojem algoritmus se nejčastěji objevuje připrogramování, kdy se jím myslí teoretický princip řešení problému (oproti přesnému zápisu v konkrétnímprogramovací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ř. kuchařský recept. Zpravidla však na algoritmy klademe určitá omezení.
V užším smyslu se slovem algoritmus označují takové postupy, které splňují některé silnější požadavky:
- Elementárnost
- Algoritmus se skládá z konečného počtu jednoduchých (elementárních) kroků.
- Konečnost (finitnost)
- Každý algoritmus musí skončit vkoneč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ývatvýpočetní metody. Speciálním příkladem nekonečné výpočetní metody jereaktivní proces, který průběžně reaguje s okolním prostředím. Někteří autoři však mezi algoritmy zahrnují i takovéto postupy.
- Obecnost (hromadnost, masovost, univerzálnost)
- 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“), má širokou množinu možných vstupů.
- Determinovanost
- Algoritmus je determinovaný, pokud za stejných podmínek (pro stejné vstupy) poskytuje stejný výstup. Tato vlastnost je požadována u velké části úloh; existují však úlohy, kdy je naopak vyžadována náhodnost (například simulacevrhu kostkou,míchání karet, generováníhesel ašifrovacích klíčů); na standardních počítačích je dosažení náhodnostiobtížné. Pravděpodobnostní algoritmy v sobě mají zahrnutu náhodu a nemusí být determinované.
- Determinismus
- Každý krok algoritmu musí býtjednoznačně apř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žepřirozené jazyky neposkytují naprostou přesnost a jednoznačnost vyjadřování, byly pro zápis algoritmů navrženyprogramovací 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. Některé algoritmy jsou sice determinované, ale nejsou deterministické (například řadící algoritmusrychlé řazení s náhodnou volbou pivota).
- Výstup
- Algoritmus má alespoň jedenvý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ší (algoritmus vede od zpracování hodnot k výstupu)
V praxi jsou proto předmětem zájmu hlavně takové algoritmy, které jsou v nějakém smyslukvalitní. Takové algoritmy splňují různá kritéria, měřená např. počtem kroků potřebných pro běh algoritmu, jednoduchost, efektivitu či eleganci. Problematikou efektivity algoritmů, tzn. metodami, jak z několika známých algoritmů řešících konkrétní problém vybrat ten vhodný, se zabývají odvětvíinformatiky nazývané algoritmická analýza ateorie složitosti.
Algoritmus se navrhuje několika možnými způsoby:
- Shora dolů – postup řešení rozkládáme na jednodušší operace, až dospějeme k elementárním krokům.
- Zdola nahoru – z elementárních kroků vytváříme prostředky, které nakonec umožní zvládnout požadovaný problém.
- Kombinace obou – obvyklý postup shora dolů doplníme "částečným krokem" zdola nahoru tím, že se například použijí knihovny funkcí, vyšší programovací jazyk nebo systém pro vytváření programů (CASE).
Při návrhu algoritmů se uplatňuje množství přístupů, které abstrahují od konkrétní úlohy. K nejužívanější metodám návrhu algoritmů patří:
Klasický případ aplikace postupu odshora dolů. Algoritmy typu rozděl a panuj dělí problém na menší podproblémy, na něž serekurzivně 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čí.
Zpracovává semnožinaV složená zn údajů. Tato množina se rozdělí nak disjunktníchpodmnožin, které se zpracují každá zvlášť. Získané dílčí výsledky se pak spojí a odvodí se z nich řešení pro celou množinuV.
Klasickým případem jebinární vyhledávání nebo řadící algoritmusrychlé řazení.
Velice přímočarý přístup k řešení určité třídyoptimalizačních úloh.
Zpracovává se množinaV složená zn údajů. Úkolem je najít podmnožinuW množinyV, která vyhovuje určitým podmínkám a přitom optimalizuje předepsanouúčelovou funkci. Jakákoliv množinaW, vyhovující daným podmínkám, se nazývápřípustné řešení. Přípustné řešení, pro které nabývá účelová funkce optimální hodnoty, se nazýváoptimální řešení.
Hladový algoritmus se skládá z kroků, které budou procházet jednotlivé prvky zV, a v každém kroku rozhodne, zda se daný prvek hodí do optimálního řešení. PrvkyV bude vybírat v pořadí určeném jistou výběrovou procedurou. Výběrová procedura bude založená na nějaké optimalizační míře – funkci, která může být odvozena od účelové funkce. V každém kroku ale musíme dostat přípustné řešení. Jakmile je učiněno takové rozhodnutí, už není dále revidováno.Příkladem je třeba hledání nejkratšícesty grafu.
Dynamické programování se používá v případech kdy lze optimální řešení složit z řešení jednodušších problémů. Protože se požadavky na řešení jednodušších podproblémů mohou mnohokrát opakovat, je nutné zvolit správné pořadí jejich řešení a výsledky si zapamatovat pro opakované použití.
Opírá se oprincip optimality:Optimální posloupnost rozhodnutí má tu vlastnost, že ať je počáteční stav a rozhodnutí jakékoliv, musí být všechna následující rozhodnutí optimální vzhledem k výsledkům rozhodnutí prvního.
Typickým příkladem využití dynamického programování jsougrafové úlohy a jejich příslušné grafové algoritmy.
U některých úloh nezbývá než postupně probírat všechna možná řešení – tak zvanámetoda hrubé síly – vygenerují se všechny možné posloupnosti a pak se vybere ta nejlepší. V některých případech lze použít metody, které vynechávají popřípadě odkládají procházení možností, které zřejmě nejsou optimální.
Hledání s návratem založené na prohledávánístavového prostoru problému. Též se nazývá metoda pokusů a oprav, metoda zpětného sledování, metodaprohledávání do hloubky.
Metodu je možné použít v případě, že řešením jevektor (x1,...,xn), jehož jednotlivé složky vybíráme z množinySi,xi∈Si. Zpravidla je třeba najítn-tici, která optimalizuje nějakou účelovou funkciP(x1,...,xn). Mohou se ale také hledat všechny n-tice, které tuto podmínku splňují. Metoda vytváří n-tice jednu složku po druhé. Přitom používá účelovou funkci (nebo nějakou vhodnou pomocnou funkci) a pro každou nově vytvořenou složku testuje, zda by taková n-tice vůbec mohla být optimální nebo splňovat dané podmínky. Jestliže pro nějakéxi žádaný vektor (x1,...,xi) nemůže být optimální, není třeba už žádný takový vektor testovat a vezmeme další možnou hodnotu i-té složky. Pokud jsou vyčerpány všechny hodnoty i-té složky, vrátí se metoda zpět o jeden krok a zkouší další možnou hodnotuxi-1.
Příkladem je třebaproblém osmi dam nebochůze koně celou šachovnicí.
Je třeba poznamenat, že abstraktní kritériumkonečnosti je pro praktické použití ještě příliš slabé. V praxi je třeba zajistit, aby algoritmus skončil „v rozumném“ čase. Za rozumný čas lze v praxi považovat takový čas, který nám umožní smysluplně využít výsledek.
Např. existuje jednoduchý algoritmus, který dokáže určit, zda v danéšachové pozici může hráč na tahu vynutit vítězství a zároveň dokáže určit nejlepší možný tah. Tento algoritmus se však nedá použít, protože by na svou činnost potřeboval ohromné množství času, jakkoli je toto množství konečné. Mimoto by takový algoritmus spotřeboval ohromné množství paměti, což je další praktický zřetel, který se uplatňuje při volbě algoritmu. I když průměrná počítačová paměť stále narůstá, pro některé algoritmy jí nebude nikdy dost.
Pro vyčíslenívýpočetní složitosti algoritmů v závislosti na velikosti vstupních dat se používáasymptotický zápis závislosti výpočetního času na rozsahu úlohy (typicky na počtu vstupních údajů). NapříkladO(log N) znamená, že počet kroků algoritmu závisí logaritmicky na velikosti vstupních dat. Pokud u takového algoritmu zdvojnásobíme rozsah vstupních údajů, doba výpočtu se zvýší o jednu jednotku času, pokud bude vstupních dat čtyřikrát více, doba výpočtu se prodlouží o dvě jednotky času, a tak dále. To je třeba případ nalezení jednoho prvku o určité hodnotě v seznamu prvků seřazeném podle hodnoty (např. nalezení jména v telefonním seznamu).
Algoritmy můžeme klasifikovat různými způsoby. Mezi důležité druhy algoritmů patří:
- Rekurzivní algoritmy, které využívají (volají) samy sebe.
- Pravděpodobnostní algoritmy (někdy téžprobabilistické) provádějí některá rozhodnutí náhodně čipseudoná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ýchevolučních procesů, postupným „pěstováním“ nejlepších řešení pomocímutací akřížení. Vgenetickém programování se tento postup aplikuje přímo na algoritmy (resp. programy), které jsou zde chápány 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).
Přitom jeden algoritmus může patřit zároveň do více skupin; například může být zároveň rekurzivní a genetický.
Slovo algoritmus pochází ze jména významnéhoperskéhomatematika žijícího v první polovině9. století (cca780–840), kterým bylAbū ʻAbd Allāh Muhammad ibn Mūsā al-Chwārizmī (أبو عبد الله محمد بن موسى الخوارزمي) (doslova „Otec Abdulláha, Mohamed, syn Mojžíšův, pocházející z města Chwārizm (Chórézm, dnesChiva)“; tento kraj se nachází vUzbekistánu jižně odAralského moře). Tento učenec ve svém díle prakticky vytvořil systémarabských číslic a základy algebry (konkrétně metody řešenílineárních akvadratickýchrovnic), jejíž název pochází přímo z titulu tohoto díla (Kitūb al-jabr waāl-muqūbala). Jeho jméno bylo dolatiny převedeno jakoalgorismus, 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štinyth změněno nat, vkatalánštině se vrátilos.) Toto slovo se používalo jako označení různých matematických postupů, např. v18. století označovallatinský termínalgorithmus infitesimalis „metodu výpočtů s využitím nekonečně malých veličin, vynalezenouLeibnizem“. Slovoalgoritmus v dnešním významu se používá až zhruba od20. století.
Algoritmy byly použity ve starověkém Řecku. Například Eratosthenovo síto nebo Eukleidův algoritmus.
Slovo algoritmus pochází z 9. století a je odvozeno z příjmení perského matematikaAl-Chorezmí. Slovo původně odkazovalo na pravidla provádění aritmetických operací s arabskými číslicemi, ale vyvinulo se prostřednictvím překladu matematikova jména na „algoritmus“ v 18. století a zahrnuje všechny určité postupy pro řešení problémů nebo plnění úkolů.
Tally-značky: K počítání stád, pytlů s obilím a peněz ve starověku se používaly akumulační kameny, značky vyškrábané na holích nebo záznam jednotlivých symbolů v jílu. Značky jsou obvykle vjedničkové soustavě, která se používá při kódování informací proTuringovy stroje vteorii automatů.
Hodiny: Podle Boltera je vynález mechanických hodin jedním z klíčových vynálezů. Zejména pak jejich setrvačná část –Lihýř. Přesný automat vedl okamžitě k mechanickému automatu (začátek 13. století) a nakonec k výpočetním strojům – diferenční aanalytický stroj (Charles Babbage aAda Lovelace) v polovině19. století. Lovelace je připočítáno první vytvoření algoritmu, který je zpracovatelný počítačem. Babbageův analytický stroj je považován za první Turingův kompletní počítač. Charles Babbage je někdy nazýván jako historicky první programátor.
Logické stroje 1870 –Jevonsovo logické počítadlo a logický stroj: Technický problém byl zjednodušení logických rovnice, které bylo představeno v podobě podobné tomu, co je nyní známo jakoKarnaughova mapa. Jevons (1880) popisuje první jednoduché počítadlo ze dřeva vybavené kolíky tak, aby jakákoli jeho třída kombinací šla vyzvednout mechanicky. Tento stroj je představen členům královské společnosti v roce 1870.
Tkalcovský stav,děrné štítky,telegrafie atelefonie – elektromechanické relé: Bell a Newell (1971) označují, že tkalcovský stav (1801), předchůdce děrných štítků (1887) a telefonní spínací technologie vedly k vývoji prvních počítačů. V polovině 19. století telegraf, předchůdce telefonu, byl v provozu po celém světě. V roce 1910 se objevildálnopis, který využíval mezinárodní telegrafní abecedu.
Telefonní sítě elektromechanických relé – George Stibitz (1937) pracoval v Bellových laboratořích a dokončil kalkulátor, který je schopen pracovat s komplexními čísly.
Symboly a pravidla: V rychlém sledu za sebou matematika George Boole,Gottlob Frege aGiuseppe Peano redukovala aritmetiku do sekvence symbolů, se kterými se manipulovalo pomocí daných pravidel. PeanovoThe principles of arithmetic, presented by a new method (1888) byl první pokus o axiomatizování matematiky v symbolický jazyk.
Heijenoort dává Fregemu (1879) tuto slávu: Fregovo dílo je možná nejdůležitější práce, která kdy bylo v logice napsána. Tato práce byla dále zjednodušena a umocněnaAlfredem North Whiteheadem aBertrandem Russellem v jejich Principia Mathematica (1910–1913).
Paradoxy: Ve stejné době se objevila řada znepokojivých elementů v literatuře, zejménaBurali-Fortiho paradox (1897),Russellův paradox (1902–1903) a Richardův paradox. Výsledné úvahy vedly kGödelovým větám o neúplnosti.
Efektivní vyčíslitelnost: Ve snaze vyřešitEntscheidungsproblem přesně definovanýmHilbertem v roce 1928 museli matematici nejprve definovat, co se rozumí pod pojmem „efektivní metoda“ nebo „efektivní výpočet“. V rychlém sledu se objeviliAlonzo Church,Stephen Cole Kleene a J. B. Rosser, kteří jsou známí především díkylambda kalkulu. Church pak společně sTuringem ukázal, že lambda kalkul (a další výpočetní modely) má výpočetní síluTuringova stroje, což otevřelo cestu kChurchově–Turingově tezi.
Algoritmy nejsou obvykle patentovány. Samotná manipulace s abstraktními pojmy, čísly, či dokonce signály není v USA (dle USPTO 2006) považována za proces. Jinými slovy lze říci, že algoritmy nelze patentovat (podobně jako v kauzeGottschalk v. Benson). Nicméně některá praktická využití algoritmů lze patentovat. Například v kauzeDiamond v. Diehr byl patentován jednoduchý algoritmuszpětné vazby na pomoc při vytvrzování syntetické gumy. Patentovánísoftwaru je i přes to velmi kontroverzní. Některé patentované algoritmy se potýkají s negativní kritikou, a to především algoritmy sloužící kekompresi dat.
- hesloAlgorithmus.Ottův slovník naučný I, p. 857
- Donald E. Knuth:The Art of Computer Programming, Vol 1–3, Addison Wesley 1998.ISBN 0-201-48541-9. Klasické dílo oboru, definitivní příručka.
- Gaston H. Gonnet, Ricardo Baeza-Yates: Zdrojové texty programů vHandbook of Algorithms and Data Structures.
- Dictionary of Algorithms and Data Structures. „Slovník algoritmů, technik, datových struktur, typických problémů a příslušných definic.“
- United States Patent and Trademark Office (2006),2106.02 **>Mathematical Algorithms: 2100 Patentability, Manual of Patent Examining Procedure (MPEP). Latest revision August 2006
