Výpočetní model (teorie algoritmů)
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 | editovat zdroj]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 | editovat zdroj]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 | editovat zdroj]
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.
Odkazy
[editovat | editovat zdroj]Reference
[editovat | editovat zdroj]V tomto článku byl použit překlad textu z článku Model of computation na anglické Wikipedii.
- ↑ Examples of the price of abstraction?, cstheory.stackexchange.com
Související články
[editovat | editovat zdroj]- 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
[editovat | editovat zdroj]
Obrázky, zvuky či videa k tématu výpočetní model na Wikimedia Commons
Literatura
[editovat | editovat zdroj]- FERNÁNDEZ, Maribel. Models of Computation: An Introduction to Computability Theory. Dordrecht Heidelberg London New York: Springer, 2009. (Undergraduate Topics in Computer Science). Dostupné v archivu pořízeném dne 2015-04-02. ISBN 978-1-84882-433-1. Archivováno 2. 4. 2015 na Wayback Machine.
- SAVAGE, John E. Models Of Computation: Exploring the Power of Computing. USA: Addison-Wesley, 2008. Dostupné v archivu pořízeném dne 2016-10-12. Archivováno 12. 10. 2016 na Wayback Machine.
