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

Výpočetní model 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

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. (. +moreformální gramatika).

Použití

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 . Č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. +more 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é.

Kategorie

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 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 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.

Odkazy

Reference

Související články

Zásobníkový počítač (0-operandový stroj) * Akumulátorový stroj (jednooperandový stroj) * Registrový stroj (2,3,...-operandový stroj) * RAM stroj * Cell-probe model

Externí odkazy

Literatura

Kategorie:Teorie algoritmů