Výpočetní model (teorie algoritmů)

(přesměrováno z Výpočetní model)

Výpočetní model (anglicky model of computation) je abstraktní model v teorii vyčíslitelnosti a teorii složitosti definující množinu povolených operací používaných při výpočtu a jejich cen (nákladů). Používá se pro určení míry složitosti algoritmů vyjádřené dobou běhu nebo paměťovým prostorem: pro konkrétní výpočetní model lze analyzovat, jaké výpočetní prostředky vyžaduje, nebo diskutovat omezení algoritmů nebo počítačů.

Příklady

editovat

K příkladům výpočetních modelů patří Turingovy stroje, RAM stroje, konečné automaty, částečně rekurzivní funkce, lambda kalkul, kombinatorická logika a abstraktní přepisovací systémy. (...formální gramatika)

Použití

editovat

V oblasti běhové analýzy algoritmů je obvyklé zadat výpočetní model pomocí povolených primitivních operací, které mají jednotkové náklady nebo jednoduše operací s jednotkovými náklady (anglicky unit-cost operations). Často používaným příkladem je RAM stroj, který má jednotkové náklady na čtení i zápis každé paměťové buňky. V tomto ohledu se odlišuje od výše zmíněného Turingova stroje.

V modely řízeném inženýrství výpočetní model vysvětluje, jak je chování celého systému výsledkem chování jeho jednotlivých komponentů.

Klíčovým bodem, který je často přehlížen, je, že publikované spodní meze řešení problémů jsou často získané pro výpočetní model, který je omezenější než množina operací, které se obvykle používají v praxi, a proto mohou existovat algoritmy, které jsou rychlejší, než co bychom naivně považovali za možné[1].

Kategorie

editovat

Existuje mnoho modelů výpočtů, které se liší množinou přípustných operací a jejich výpočetními náklady. Do této široké kategorie patří mimo jiné abstraktní stroj[kdo?] a modely s ním ekvivalentní (například lambda kalkul je ekvivalentní s Turingovým strojem) používaný pro důkazy vyčíslitelnosti a zjištění horní meze výpočetní složitosti algoritmů nebo modely s[kdo?] rozhodovacím stromem (to jsou jiné rozhodovací stromy, než tamty v dataminingu) používané pro důkazy spodní meze výpočetní složitosti algoritmických problémů.

Zvláště v teoretické informatice se používá pojem Turingovsky úplný model, případně stroj či formalismus, pro modely, které jsou schopné spočítat vše co Turingův stroj. Viz Churchova–Turingova teze

Pro automaty a gramatiky existuje několik modelů výpočtů, které lze uspořádat do hierarchie podle tzv. výpočtové síly. Viz Chomského hierarchie.

Reference

editovat

V tomto článku byl použit překlad textu z článku Model of computation na anglické Wikipedii.

  1. Examples of the price of abstraction?, cstheory.stackexchange.com

Související články

editovat

Externí odkazy

editovat

Literatura

editovat