Podrobné instrukce definující výpočetní proces (o němž se pak říká, že je algoritmický), který začíná libovolným vstupem (z určitého počtu vstupů, které jsou pro daný algoritmus možné) a instrukcemi zaměřenými na získání výsledku (nebo výstupu), který je plně určen vstupem. Například pravidla vyučovaná na základních školách pro sloupcové sčítání, odčítání, násobení a dělení jsou algoritmy; v těchto algoritmech jsou možnými výsledky nezáporná celá čísla zapsaná v desítkové soustavě, zatímco možnými vstupy jsou uspořádané dvojice těchto čísel. Obecně se nepředpokládá, že výsledek je nutně získán: proces aplikace algoritmu na nějaký možný vstup (tj. algoritmický proces, který probíhá od tohoto vstupu) může také skončit, aniž by byl získán výsledek (v takovém případě máme stop stav bez výsledku), nebo nemusí skončit vůbec. Pokud proces skončí (neskončí), pak se říká, že vstup je vhodný (není vhodný) pro daný algoritmus.
Důležitým výsledkem v této oblasti je nerozhodnutelnost tzv. problému zastavení. Je možné zkonstruovat algoritmus $\alfa $tak, že neexistuje algoritmus, který by rozhodl, zda nějaký libovolný vstup, který je možný pro $\alfa $, je také vhodný pro $\alfa $. Zejména lze najít takový algoritmus $\alfa $, pro který je množinou jeho možných vstupů množina přirozených čísel.
Pojmem algoritmus je jeden z ústředních pojmů moderní matematiky, zejména v oblasti výpočtů. Příklad je uveden níže. Nalezení numerického řešení rovnic daného typu se rovná sestrojení algoritmu, který převede libovolnou rovnici tohoto typu a libovolné kladné racionální číslo $ \epsilon $na číslo (nebo množinu čísel), které se liší od kořene(ů) této rovnice o méně než $ \epsilon $. Termín „výpočetní proces“ , použitý v souvislosti s algoritmem, však nelze chápat pouze jako numerické výpočty: i v elementární algebře se používají výpočty s písmeny. Standardní aritmetické výpočty zahrnují některé symboly, které nejsou čísly (závorky, znaménka rovnosti, symboly pro aritmetické operátory). Je proto účelné uvažovat o algoritmech zahrnujících libovolné symboly a objekty složené ze symbolů. Nejjednodušším příkladem takového objektu je lineární posloupnost symbolů tvořící slovo. Je možné uvažovat i „nelineární“ objekty – algebraické matice, derivační stromy nějakého formálního jazyka a obecné grafy. Intuitivně nejmenším požadavkem na vstupy a výsledky algoritmů je, že musí jít o konstruktivní objekty (srov. Konstruktivní objekt). Pojem algoritmu je tedy velmi obecný. Lze hovořit o algoritmu pro překlad z jednoho jazyka do druhého, o algoritmu řídícího letového provozu (zpracovávajícího informace o pohybech letadel podle pevně stanovených pravidel) a dalších příkladech algoritmicky popsaných řídicích procesů. Pojem algoritmu je proto jednou z ústředních myšlenek kybernetiky a informatiky.
Příklad algoritmu.
Nechť jsou možnými vstupy a možnými výsledky všechna možná slova nad abecedou ${ a, b \} $. Přechod ze slova $ X $do slova $ Y $je „přípustný“ v následujících dvou případech (kde $ P $označuje libovolné slovo): 1) $ X $je tvaru $ aP $ a $ Y $je tvaru $ Pb $; nebo 2) $ X $je tvaru $ baP $, zatímco $ Y $je tvaru $ Paba $. Instrukce jsou formulovány takto: Instrukce se skládají ze slov: „označte nějaké slovo jako vstup, provádějte povolené přechody, dokud nezískáte slovo ve tvaru aaP; pak se zastavte a výsledkem nechť je slovo P“ . Tyto instrukce tvoří algoritmus, který budeme označovat $ \mathfrak A $. Jako vstup vezměme slovo $ babaa $. Po jednom přechodu získáme $ baaaba $, po druhém $ aabaaba $. Zde se algoritmus zastaví s $ baaba $ jako výsledkem. Uvažujme další vstup $ baaba $. Postupně získáme $ abaaba, baabab, abababa, bababab, babababa , . . . $. Lze ukázat, že tento proces nikdy neskončí (tj. žádné z vygenerovaných slov nebude nikdy začínat na $ aa $). Nyní vezměte $ abaab $jako vstup. Získáme $ baabb, abbaba, bbabab $; žádné další přípustné přechody nejsou možné a zároveň není splněna podmínka ukončení. Máme tedy stop stav bez výsledku. Vstup $ babaa $ je tedy vhodný pro $ \mathfrak A $ a vstupy $ baaba $a $ abaab $ vhodné nejsou.
Význam algoritmů.
Ve vědě se s algoritmy setkáváme všude: „obecné“ řešení problému vyžaduje algoritmus. Příkladem je schopnost člověka sčítat čísla. Nikoliv v tom smyslu, že dokáže dříve či později najít součet libovolných dvou čísel, ale spíše v tom smyslu, že disponuje metodou pro jedinečné sčítání libovolných dvou čísel daných v písemné podobě, tj. algoritmem sčítání, jako je známá metoda sloupcového sčítání. „Obecně“ je řešení problému formalizováno jako řešení algoritmického problému. Algoritmický problém se skládá ze samostatných případů problému a pro řešení všech je třeba najít jediný algoritmus. Pokud takový algoritmus neexistuje, říká se, že algoritmický problém je neřešitelný. Problém numerického řešení rovnic daného typu a problém automatického překladu jsou tedy algoritmické problémy. Jejich problémovými instancemi jsou respektive nalezení numerického řešení jednotlivých rovnic daného typu a překlad jednotlivých vět. Dalšími příklady jsou verifikace algebraických rovností v algebře; algoritmický problém rozpoznání odvoditelnosti vět z daných axiomů v matematické logice. (V matematické logice je pojem algoritmu také důležitý, protože slouží jako základ klíčového pojmu kalkulu, který je zobecněním a přesnější formou intuitivních pojmů „důkaz“ a „demonstrace“ .) Stanovení neřešitelnosti daného algoritmického problému (např. problému stanovení pravdivosti nebo dokazatelnosti vět v nějakém logicko-matematickém jazyce) je důležité, protože ukazuje, že konkrétní případy tohoto problému lze v zásadě řešit pouze metodami, které jsou specifické pro každý jednotlivý případ problému.
Vědecký význam pojmu algoritmu je uznáván již dlouho. Od nejstarších dob lidé hledali konstruktivní metody řešení matematických problémů. Tyto snahy obvykle těžily z nové dostupnosti vhodných symbolických zápisů. Tento proces významně přispěl k vědeckému poznání, a to zejména poté, co se ukázalo, že některé problémy jsou ze své podstaty neřešitelné (kvadratura kruhu apod.). Poté, co se zjistilo, že některé problémy nelze řešit přímými výpočty, zrodil se v 19. století teoretický pojem množiny. Teprve po období rychlého rozvoje tohoto pojmu (který se netýkal problémů konstruktivních metod v jejich moderním smyslu) bylo možné se v polovině 20. století vrátit ke konstruktivním problémům, ale stalo se tak na jiné úrovni, obohacené o pojem algoritmu, který mezitím vykrystalizoval. Tento pojem tvoří základ konstruktivního směru v matematice.
Slovo „algoritmus“ pochází ze slova „algoritmi“ , které je latinskou transliterací jména arabského matematika z 9. století Al-Khwarizmiho. „Algoritmus“ ve středověké Evropě znamenal „desítkovou poziční soustavu a umění počítat s ní“ , neboť právě prostřednictvím latinského překladu (12. století) Al-Khwarizmiho pojednání byla poziční soustava zavedena v Evropě.
Struktura algoritmického procesu.
Agoritmický proces je proces postupné přeměny konstrukčních objektů pomocí diskrétních „kroků“ , přičemž každý krok spočívá v nahrazení jednoho konstrukčního objektu jiným. Tak při aplikaci algoritmu $\mathfrak A$ na slovo $baaba$ následují postupně slova $baaba, abaaba, baabab$ atd. Aplikujeme-li, řekněme, algoritmus sloupcového odčítání na dvojici čísel <307, 49 >, pak získáme postupně tyto konstrukční objekty:
$$ \begin{array}{rrrr}307 &3 \dot{0} 7 &\dot{3} \dot{0} 7 &\dot{3} \dot{0} 7 \\\\underline{- 49 } &\underline{- 49 } &\underline{- 49 } &\underline{- 49 } \\{} & 8 &58 &258 \\\end{array}$$
Poznamenejme, že v řadě po sobě jdoucích konstrukčních objektů je každý následující konstrukční objekt plně určen (v rámci daného algoritmu) konstrukčním objektem, který mu bezprostředně předchází. V přísnějším přístupu se také předpokládá, že přechod z libovolného konstrukčního objektu do objektu bezprostředně následujícího je dostatečně „elementární“ – v tom smyslu, že jednokroková transformace předcházejícího do bezprostředně následujícího objektu je lokální (netransformuje se celý konstrukční objekt, ale pouze jeho algoritmicky omezená část; navíc tato transformace sama není určena kompletním předcházejícím objektem, ale pouze jeho omezenou částí).
Podle toho máme k dispozici nejen množinu možných vstupů a množinu možných výsledků, ale také množinu možných mezivýsledků, které představují pracovní prostředí, v němž se algoritmický proces vyvíjí. Pokud jde o $ \mathfrak A$, všechny tyto tři množiny se shodují, což však neplatí pro algoritmus sloupcového odčítání – možnými vstupy jsou dvojice čísel, možnými výsledky jsou čísla (vše v desítkové soustavě), zatímco možnými mezivýsledky jsou „třípatrové“ záznamy typu
$$ \begin{array}{r} p \\\underline{- q } \\ r \\\\konec{array}$$
kde $ q$ je zápis čísla v desítkové soustavě, $ r$ je podobný zápis nebo prázdné slovo, zatímco $ p$ je zápis čísla v desítkové soustavě s tečkami nad některými číslicemi. Jako pravidlo lze rozlišit několik (nikoliv nezávislých) parametrů, které jsou pro algoritmus charakteristické: 1) množinu možných vstupů; 2) množinu možných výsledků; 3) množinu možných mezivýsledků; 4) pravidlo startu; 5) pravidlo přímého přechodu; 6) pravidlo ukončení a 7) pravidlo pro získání výsledku.
Formalizace pojmu algoritmu.
Pojmem algoritmu v jeho obecné podobě je základní matematický pojem, který nelze definovat pomocí jednodušších pojmů. Přísně vzato, formalizace pojmu algoritmu jej ve skutečnosti poněkud omezují. V každé takové formalizaci je uvedena přesná definice určité třídy, v jejímž rámci se může každý z parametrů měnit. Různé formalizace se od sebe liší výběrem takových tříd. Protože parametry jednoznačně definují nějaký algoritmus, výběr oblastí parametrů určuje nějakou třídu algoritmů. Taková volba si však může činit nárok na to, že je formalizací intuitivního pojmu algoritmu, pouze tehdy, pokud si můžeme být jisti, že pro každý „intuitivní“ algoritmus existuje ekvivalentní algoritmus ve třídě algoritmů definované uvažovanou volbou. Tento požadavek je u každé formalizace formulován jako základní hypotéza, kterou za současného stavu poznání nelze matematicky prokázat.
První formalizace tohoto typu jsou zásluhou E. L. Posta
a A. M. Turinga , , jehož konstrukce v mnoha ohledech předjímaly myšlenky, na nichž jsou založeny moderní počítače. Existují také verze formulované A. A. Markovem ,
(srov. Normální algoritmus) a A. N. Kolmogorovem , který založil přístup na konstrukčních topologických komplexech určitého typu, což umožňuje přesněji vyjádřit vlastnost „být lokální“ transformace. V každé z těchto formalizací je základní hypotéza v uspokojivém souladu s praxí. Dalším argumentem ve prospěch této hypotézy je skutečnost, že, jak lze ukázat, všechny formální verze (efektivní spočitatelnosti), které byly navrženy, jsou ekvivalentní.
Jako příklad uveďme formalizaci navrženou Turingem. V původní podobě se jednalo o popis nějakého teoretického počítače, který se skládá z 1) nekonečné pásky rozdělené na po sobě jdoucí buňky, přičemž každá buňka může obsahovat nějaký symbol z „páskové abecedy“ stroje; a 2) „konečného řízení“, které je v každém časovém okamžiku v nějakém „stavu“ (z daného konečného seznamu stavů). Konečné řízení se může pohybovat po pásce po jedné buňce a měnit obsah buněk, kterými prochází. Program, který sleduje pohyb konečného řízení, představuje algoritmus pro výpočty prováděné na takovém stroji („Turingův algoritmus“ ). Přesnější a podrobnější popis viz Turingův stroj. Zde je uveden modernizovaný výklad Turingovy konstrukce. Pro definici Turingova algoritmu je třeba zadat a) dvojici nesouvislých abeced $B, D, C$ s rozlišujícím písmenem $\lambda$ v $D$ a rozlišujícími písmeny $\alfa$ a $\omega$ v $C$; a b) množina dvojic tvaru $ \langle p \xi , \eta Tq \rangle $ kde $ p, q \v C $, $ \xi , \eta \v B \cup D $, zatímco $ T $ je jeden ze tří symbolů $ -, 0, + $; v této množině (která se nazývá program) neexistují dvě dvojice se stejnou první souřadnicí. Možné vstupy a možné výstupy jsou slova nad $ B $, zatímco možné mezivýsledky jsou slova nad $ B \cup D \cup C $, která neobsahují více než jedno písmeno $ C $. Počáteční pravidlo je, že počáteční slovo $ P $ se převede na slovo $ \lambda \alfa P \lambda $. Pravidlo ukončení je, že mezivýsledek, který obsahuje $ \omega $, je konečný. Pravidlo pro získání výstupu je, že výstupem je posloupnost písmen v konečném mezivýsledku, která následuje po $ \omega $ a předchází prvnímu písmenu nepatřícímu do $ B $. Transformační pravidlo, které převádí $ A $ na $ A ^ \prime $, je následující. Písmeno $ \lambda $ se napíše nalevo a napravo od $ A $; v takto vzniklém slově se část tvaru $ \epsilon p \xi $, kde $ p \v C $, $ \epsilon \xi \v B \cup D $, nahradí slovem $ Q $ v souladu s pravidlem: V programu se hledá dvojice s prvním členem $ p \xi $; druhý člen této dvojice nechť je $ \eta Tq $; pokud $ T $je $ – $, $ Q = q \epsilon \eta $; pokud $ T = 0 $, $ Q = \epsilon q \eta $; jestliže $ T $je $ + $, $ Q = \epsilon \eta q $. Slovo vzniklé touto výměnou je $ A ^ \prime $. Odkazy viz , , , , , , , ,
z Algoritmy, teorie.
Výše uvedená základní hypotéza se obvykle nazývá Churchova-Turingova věta nebo Turingova hypotéza. Tato teze říká, že to, co lze efektivně vypočítat podle něčí intuice o tom, co představuje efektivní proces, lze také vypočítat Turingovým strojem, tj. formálně definovaným pojmem algoritmu. Churchovu-Turingovu tezi nelze ze samotné podstaty ztotožnění intuitivního neformálního pojmu s formální přesnou definicí formálně dokázat.
Mnoho formalizací se ukázalo jako ekvivalentních a žádná formalizace se neukázala jako striktně výkonnější. Kromě výše uvedených formalizací jsou na Západě nejstandardnější následující odkazy: Churchova formalizace čísel a vypočitatelných funkcí pomocí lambda členů, Kleeneho obecná rekurzivní schémata a model registračního stroje navržený J. C. Shepherdsonem a H. E. Sturgisem, který byl rozšířen na realističtější model počítače S. A. Cookem a R. A. Reckhowem. Markovova a Kolmogorovova verze jsou méně známé. Pro úplnost uvádíme i původní odkazy na Turinga a Posta:
| A.M. Turing, „On computable numbers, with an application to the Entscheidungsproblem“ Proc. London Math.Soc. Ser. 2 , 42 (1936) str. 230-265 | |
| A.M. Turing, „Corrections to „On computable numbers, with an application to the Entscheidungsproblem“ “ Proc. London Math.Soc. Ser. 2 , 43 (1937) str. 544-546 | |
| A. Church, „An unsolvable problem of elementary number theory“ Amer. J. Math. , 58 (1936) str. 345-363 | |
| S.C. Kleene, „General recursive functions of natural numbers“ Math. Ann. , 112 (1936) str. 727-742 | |
| E.L. Post, „Formal reductions of the general combinatorial decision problem“ Amer. J. Math. , 65 (1943) str. 197-268 | |
| J.C. Shepherdson, H.E. Sturgis, „Computability of recursive functions“ J. Assoc. Comp. Mach. , 10 (1963) str. 217-255 | |
| S.A. Cook, R.A. Reckhow, „Time-bounded random access machines“ J. Computer and System Sciences , 7 (1973) str. 354-375 |
.