Algoritmy

V matematice, výpočetní technice, lingvistice a příbuzných oborech je algoritmus procedura (konečný soubor přesně definovaných instrukcí) pro splnění nějakého úkolu, který za daného počátečního stavu skončí v definovaném koncovém stavu. Výpočetní složitost a efektivní implementace algoritmu jsou ve výpočetní technice důležité, a to závisí na vhodných datových strukturách.

Neformálně je pojem algoritmus často ilustrován na příkladu receptu, i když mnoho algoritmů je mnohem složitějších. Algoritmus je v podstatě metoda, podobně jako recept, v tom smyslu, že sledováním kroků algoritmu zaručeně najdete řešení nebo odpověď, pokud nějaké existuje. Algoritmy mají často kroky, které se opakují (opakují) nebo vyžadují rozhodnutí (například logiku nebo srovnání). Algoritmy mohou být složeny tak, aby vytvářely složitější algoritmy.

Koncept algoritmu vznikl jako prostředek pro záznam postupů pro řešení matematických problémů, jako je nalezení společného dělitele dvou čísel nebo násobení dvou čísel. Koncept byl formalizován v roce 1936 prostřednictvím Turingových strojů a lambda kalkulu Alonza Churche, který zase tvořil základ informatiky.

Většina algoritmů může být přímo implementována počítačovými programy, jakékoliv jiné algoritmy mohou být alespoň teoreticky simulovány počítačovými programy. V mnoha programovacích jazycích jsou algoritmy implementovány jako funkce nebo procedury.

Vývojové diagramy se často používají ke grafické reprezentaci algoritmů.

Proč jsou algoritmy nutné: neformální definice

Neexistuje žádná obecně přijímaná formální definice „algoritmu“. Můžeme však odvodit vodítka k daným otázkám a neformální význam slova z následujícího citátu z knihy Boolos a Jeffrey (1974, 1999):

Slova „enumerably infinite“ znamenají „countable using integers perhaps extend to infinity“. Tudíž Boolos a Jeffrey říkají, že algoritmus implikuje instrukce pro proces, který „vytváří“ výstupní celá čísla z libovolného „vstupního“ čísla nebo celá čísla, která teoreticky mohou být zvolena od 0 do nekonečna. Tudíž můžeme očekávat, že algoritmus bude algebraická rovnice jako y = m + n – dvě libovolné „vstupní proměnné“ m a n, které vytvářejí výstupní y. Bohužel – jak vidíme v charakterizacích algoritmu – slovo algoritmus implikuje mnohem více než toto, něco v pořadí (pro náš příklad sčítání):

Evoluce jako algoritmický proces

Daniel Dennett analyzuje význam evoluce jako algoritmického procesu ve své knize Darwinova nebezpečná myšlenka z roku 1995. Dennett identifikuje tři klíčové rysy algoritmu:

Na základě této analýzy dochází Dennett k závěru, že evoluce je algoritmický proces.

Formalizace algoritmů

Algoritmy jsou nezbytné pro způsob, jakým počítače zpracovávají informace, protože počítačový program je v podstatě algoritmus, který říká počítači, jaké konkrétní kroky má provést (v jakém konkrétním pořadí), aby mohl provést zadaný úkol, jako je výpočet výplat zaměstnanců nebo tisk vysvědčení studentů. Algoritmus lze tedy považovat za jakoukoli posloupnost operací, které může provádět Turingův kompletní systém. Mezi autory, kteří prosazují tuto tezi, patří Savage (1987) a Gurevich (2000):

Pro každý takový výpočetní proces musí být algoritmus přesně definován: specifikován způsobem, jakým se uplatňuje za všech možných okolností, které by mohly nastat. To znamená, že všechny podmíněné kroky musí být systematicky řešeny případ od případu; kritéria pro každý případ musí být jasná (a vypočitatelná).

Protože algoritmus je přesný seznam přesných kroků, pořadí výpočtů bude téměř vždy kritické pro fungování algoritmu. Předpokládá se, že instrukce jsou obvykle uvedeny explicitně a jsou popsány tak, že začínají ‚shora‘ a jdou ‚dolů až dolů‘, což je myšlenka, která je popsána formálněji tokem řízení.

Dosud tato diskuse o formalizaci algoritmu předpokládala předpoklady imperativního programování. To je nejběžnější koncepce a pokouší se popsat úkol diskrétními, ‚mechanickými‘ prostředky. Unikátní pro tuto koncepci formalizovaných algoritmů je přiřazovací operace, nastavení hodnoty proměnné. Odvozuje se z intuice ‚paměti‘ jako scratchpadu. Níže je příklad takového přiřazení.

Pro některé alternativní pojetí toho, co představuje algoritmus viz funkční programování a logické programování .

Někteří autoři omezují definici algoritmu na procedury, které nakonec skončí. Do takové kategorie Kleene 1952 řadí „rozhodovací proceduru nebo rozhodovací metodu nebo algoritmus pro otázku“ (Kleene s. 136). Jiní, včetně Kleene, zahrnují procedury, které by mohly běžet věčně bez zastavení; taková procedura byla nazvána „výpočetní metoda“ (Knuth, Vol.1 s. 5) nebo „výpočetní procedura nebo algoritmus“ (Kleene s. 137); nicméně Kleene poznamenává, že taková metoda musí nakonec vykazovat „nějaký objekt“ (Kleene s. 137).

Doporučujeme:  Hyperpatie

Minksy trefně poznamenává, že pokud se algoritmus neukončil, pak nemůžeme odpovědět na otázku „Ukončí se správnou odpovědí?“:

Odpověď tedy zní: nerozhodnutelné. Nikdy to nemůžeme vědět a ani nemůžeme předem provést analýzu, abychom to zjistili. Analýza algoritmů pro pravděpodobnost jejich ukončení se nazývá Analýza ukončení. Více o tomto zapeklitém problému najdete v tématu Zastavení.

V případě nezastavující se výpočetní metody (výpočetní procedury) úspěch již nemůže být definován jako zastavení se smysluplným výstupem. Místo toho musí být definovány podmínky úspěchu, které umožňují neomezené výstupní sekvence. Například algoritmus, který ověřuje, zda je v nekonečné náhodné binární sekvenci více nul než jedniček, musí běžet věčně, aby byl účinný. Pokud je však implementován správně, bude výstup algoritmu užitečný: po dobu zkoumání sekvence bude algoritmus dávat kladnou odpověď, zatímco počet zkoumaných nul převyšuje jedničky, a zápornou odpověď v opačném případě. Úspěch tohoto algoritmu by pak mohl být definován jako eventuální výstup pouze kladných odpovědí, pokud je v sekvenci skutečně více nul než jedniček, a v každém jiném případě výstup jakékoli směsi kladných a záporných odpovědí.

Více o tom, co se může stát, když algoritmus selže u některých svých vstupních čísel – např. (i) neukončení, (ii) výroba „junk“ (výstup ve špatném formátu, aby byl považován za číslo) nebo vůbec žádné číslo(y) (zastavení ukončí výpočet bez výstupu), (iii) chybné číslo(y), nebo (iv) jejich kombinace. Kleene (1952) str. 322-323 navrhl, aby výroba „junk“ nebo neschopnost vyrobit číslo byla vyřešena tím, že algoritmus tyto instance detekuje a vyrobí např. chybové hlášení (navrhl „0“), nebo nejlépe donutí algoritmus k nekonečné smyčce. (Davis (1958) to dělá se svým algoritmem pro odčítání (str. 12-15) — fixuje svůj algoritmus ve druhém příkladu tak, aby to bylo správné odčítání). Spolu s logickými výsledky „true“ a „false“ Kleene také navrhuje použití třetího logického symbolu „u“ — nerozhodnuto (str. 326) — tak algoritmus vždy něco vytvoří, když je konfrontován s „propozicí“. Problém špatných odpovědí musí být vyřešen nezávislým „důkazem“ algoritmu např. použitím indukce:

Algoritmy mohou být vyjádřeny v mnoha druzích zápisu, včetně přirozených jazyků, pseudokódu, vývojových diagramů a programovacích jazyků. Výrazy algoritmů v přirozeném jazyce bývají upovídané a nejednoznačné a jen zřídka se používají pro složité nebo technické algoritmy. Pseudokódy a vývojové diagramy jsou strukturované způsoby vyjádření algoritmů, které se vyhýbají mnoha nejednoznačnostem běžným v příkazech v přirozeném jazyce a zároveň zůstávají nezávislé na konkrétním implementačním jazyce. Programovací jazyky jsou primárně určeny pro vyjádření algoritmů ve formě, kterou může počítač provést, ale často se používají jako způsob definování nebo dokumentace algoritmů.

Například Boolos-Burgess-Jeffrey (2002) (str. 26) uvádí příklady Turingových strojových programů psaných jako „strojové tabulky“ (více viz Turingův stroj, konečný stroj, převodní tabulka stavu), jako „průtokové grafy“ (více viz stavový diagram), nebo jako forma základního strojového kódu nebo montážního kódu zvaného „sady čtyřčlenek“ (více viz Turingův stroj). Dávají podrobnější obrys svého „násobícího stroje“ (viz obrázek 3.7 str. 30) nakresleného jako „průtokový graf“, jehož části jsou označeny krátkými popisy v přirozeném jazyce.

Boolos-Burgess-Jeffrey (2002) při popisu výpočtů svého modelu „počítacího stroje“ (více v registru) doplňují malé „průtokové grafy“ (stavové diagramy) výrazy v přirozeném jazyce a/nebo aritmetickými výrazy zapsanými uvnitř „blokových diagramů“, aby shrnuly, čeho „průtokové grafy“ dosahují. Někdy ve svých popisech kombinují jak „blokové diagramy“, tak „průtokové grafy“.

Doporučujeme:  Poradenství zaměřené na řešení

Ve své kapitole 3.3 nazvané Definice algoritmu Sipser (2006) popisuje tři úrovně popisu Turingova stroje (všechny citace str. 157):

Většina algoritmů má být implementována jako počítačové programy. Algoritmy jsou však implementovány i jinými prostředky, například v biologické neuronové síti (například lidský mozek provádějící aritmetiku nebo hmyz hledající potravu), v elektrickém obvodu nebo v mechanickém zařízení.

Jedním z nejjednodušších algoritmů je najít největší číslo v (netříděném) seznamu čísel. Řešení nutně vyžaduje podívat se na každé číslo v seznamu, ale pouze jednou u každého. Z toho vyplývá jednoduchý algoritmus, který lze uvést ve vysokém popisu anglické prózy, jako:

Pro složitější příklad algoritmu viz Euklidův algoritmus pro největší společný dělitel, jeden z nejranějších známých algoritmů.

Různé algoritmy mohou dokončit stejnou úlohu s jinou sadou instrukcí za méně nebo více času, prostoru nebo úsilí než ostatní. Například vzhledem ke dvěma různým receptům na přípravu bramborového salátu může jeden z nich oloupat bramboru před uvařením brambory, zatímco druhý předkládá kroky v opačném pořadí, přesto oba vyzývají k tomu, aby se tyto kroky opakovaly u všech brambor a skončily, když je bramborový salát připraven ke konzumaci.

Analýza a studium algoritmů je disciplínou informatiky a často se praktikuje abstraktně (bez použití specifického programovacího jazyka nebo jiné implementace). V tomto smyslu se podobá jiným matematickým disciplínám v tom, že se analýza zaměřuje na základní principy algoritmu, a ne na nějakou konkrétní implementaci. Pseudokód je pro takovou analýzu dostatečně jednoduchý a abstraktní.

Existují různé způsoby klasifikace algoritmů, každý z nich má své přednosti.

Klasifikace podle provádění

Jedním ze způsobů klasifikace algoritmů je implementace.

Klasifikace podle designového paradigmatu

Klasifikace podle studijního oboru

Každý vědní obor má své vlastní problémy a potřebuje efektivní algoritmy. Související problémy v jednom oboru jsou často studovány společně. Některé příkladové třídy jsou vyhledávací algoritmy, třídicí algoritmy, slučovací algoritmy, numerické algoritmy, grafové algoritmy, řetězcové algoritmy, výpočetní geometrické algoritmy, kombinatorické algoritmy, strojové učení, kryptografie, algoritmy komprese dat a parsovací techniky.

Klasifikace podle složitosti

To je vlastně klasifikace problémů v pravém slova smyslu. Některé algoritmy se dokončují v lineárním čase úměrném velikosti vstupu a některé v exponenciálním množství času a některé nikdy. Některé problémy mohou mít více algoritmů, některé problémy nemusí mít žádné algoritmy a některé problémy nemají známé efektivní algoritmy. Existují také mapování od některých problémů k jiným problémům. Počítačoví vědci tedy zjistili, že je vhodné klasifikovat problémy spíše než algoritmy do tříd ekvivalence na základě složitosti.

Některé země umožňují patentování algoritmů, pokud jsou obsaženy v softwaru nebo hardwaru. Patenty jsou již dlouho kontroverzní záležitostí (viz například debata o softwarových patentech). Některé země neumožňují vývoz některých algoritmů, například kryptografických algoritmů, z této země (viz export kryptografie).

Historie: Vývoj pojmu „algoritmus“

Slovo algoritmus pochází ze jména perského matematika z 9. století Abu Abdullah Muhammad ibn Musa al-Khwarizmi, jehož díla zavedla arabské číslice a algebraické pojmy. Pracoval v Bagdádu v době, kdy byl centrem vědeckých studií a obchodu. Slovo algorismus původně odkazovalo pouze na pravidla provádění aritmetiky pomocí arabských číslic, ale vyvinulo se prostřednictvím evropského latinského překladu jména al-Khwarizmi do algoritmu do 18. století. Slovo se vyvinulo tak, aby zahrnovalo všechny konečné postupy pro řešení problémů nebo plnění úkolů.

Diskrétní a rozlišitelné symboly

Manipulace se symboly jako „držáky míst“ pro čísla: algebra

Práce starověkých řeckých geometrů, perský matematik Al-Khwarizmi — často považován za „otce algebry“, čínské a západoevropské matematici vyvrcholil v Leibniz‘ pojetí kalkulu ratiocinator (ca 1680):

Mechanické vynálezy s diskrétními stavy

Jacquardův tkalcovský stav, Hollerithovy děrné štítky, telegrafie a telefonování — elektromechanické relé: Bell a Newell (1971) naznačují, že Jacquardův tkalcovský stav (1801), předchůdce Hollerithových karet (děrné štítky, 1887), a „technologie přepínání telefonů“ byly kořeny stromu vedoucího k vývoji prvních počítačů (Bellův a Newellův diagram str. 39, srov. Davis (2000)). V polovině 19. století se telegraf jako předchůdce telefonu používal po celém světě, jeho diskrétní a rozlišitelné kódování písmen jako „tečky a čárky“ bylo běžným zvukem. Koncem 19. století se používal ticker tape (cca 1870), stejně jako použití karet Hollerith v roce 1890 při sčítání lidu v USA, Teletype (cca 1910) s použitím děrovaného papíru binárního kódování Baudotova kódu na pásce.

Doporučujeme:  Seymour Benzer

Telefonní spínací sítě elektromechanických relé (vynalezeny 1835) stály za dílem George Stibitze (1937), vynálezce digitálního sčítacího zařízení. Když pracoval v Bellových laboratořích, pozoroval „zatěžující“ používání mechanických kalkulaček s ozubenými koly. „Jednoho večera v roce 1937 šel domů s úmyslem otestovat svůj nápad…. Když bylo po kutění, Stibitz sestrojil binární sčítací zařízení“ (Valley News, str. 13).

Davis (2000) si všímá zvláštního významu elektromechanického relé (s jeho dvěma „binárními stavy“ otevřenými a uzavřenými):

Matematika od roku 1800 až do poloviny roku 1900

Ale Heijenoort dává Frege (1879) tento kudos: Frege je to „snad nejdůležitější jediné dílo, které kdy bylo napsáno v logice. … ve kterém vidíme “ ‚formule jazyk‘, to je lingua characterica, jazyk psaný se speciálními symboly, „pro čisté myšlení“, to znamená, bez rétorických ozdob … konstruované ze specifických symbolů, které jsou manipulovány podle určitých pravidel „( str. 1). Práce Frege byla dále zjednodušena a zesílena Alfred North Whitehead a Bertrand Russell v jejich Principia Mathematica (1910-1913).

Emil Post (1936) a Alan Turing (1936, 1937)

Zde je pozoruhodná shoda okolností, kdy se dva muži neznají, ale popisují proces, kdy muži-jako-počítače pracují na výpočtech — a přinášejí prakticky totožné definice.

Emil Post (1936) popsal činnost „počítače“ (lidské bytosti) takto:

Jeho symbol prostor by byl

Práce Alana Turinga (1936-1937) předcházela práci Stibitze (1937); není známo, zda Stibitz věděl o práci Turinga. Turingův životopisec se domníval, že Turingovo používání modelu podobného psacímu stroji bylo odvozeno z mladického zájmu: „Alan snil o vynálezu psacích strojů jako chlapec; paní Turingová měla psací stroj; a on mohl docela dobře začít tím, že se sám sebe zeptal, co bylo míněno tím, že se psací stroj nazývá ‚mechanický’“ (Hodges, str. 96) Vzhledem k rozšíření Morseovy abecedy a telegrafie, přístrojů na lepící pásky a Teletypů bychom se mohli domnívat, že vše byly vlivy.

Turingův – jeho výpočetní model se dnes nazývá Turingův stroj – začíná, stejně jako Post, analýzou lidského počítače, kterou redukuje na jednoduchou sadu základních pohybů a „stavů mysli“. Ale pokračuje o krok dál a vytváří svůj stroj jako model výpočtu čísel (Nerozhodnutelný str. 116):

Turingova snížení přináší následující:

„Je možné, že některé z těchto změn nutně vyvolávají změnu stavu mysli. Nejobecnější jednotlivou operaci je tedy třeba chápat jako jednu z následujících:

J. B. Rosser (1939) a S. C. Kleene (1943)

J. Barkley Rosser směle definoval „efektivní [matematickou] metodu“ následujícím způsobem (tučně přidáno):

Rosserova poznámka pod čarou č. 5 odkazuje na práci (1) Churche a Kleenea a jejich definici λ-definability, zejména na Churchovo použití v jeho An Unsolvable Problem of Elementary Number Theory (1936); (2) Herbranda a Gödela a jejich použití rekurze zejména Gödelovo použití v jeho slavné knize On Formally Undecidable Propostions of Principia Mathematica and Related Systems I (1931); a (3) Post a Turing v jejich mechanismu-modely výpočtu.

Stephen C. Kleene (1943) definoval jako svou dnes již slavnou „Diplomovou práci I“ známou jako „Církevní-Turingova diplomová práce“. Udělal to však v následujícím kontextu (tučné písmo v originále):