Model výpočtu - Model of computation

tento článek ne uvést žádný Zdroje. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Model výpočtu"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Květen 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v počítačová věda a konkrétněji v teorie vypočítatelnosti a teorie výpočetní složitosti, a model výpočtu je model, který popisuje, jak výstup a matematická funkce je vypočítán s daným vstupem. Model popisuje, jak jsou organizovány jednotky výpočtů, paměti a komunikace. The výpočetní složitost z algoritmus lze měřit na základě modelu výpočtu. Použití modelu umožňuje studovat výkon algoritmů nezávisle na variantách, které jsou specifické pro konkrétní implementace a konkrétní technologie.

Modely

Modely výpočtu lze rozdělit do tří kategorií: sekvenční modely, funkční modely a souběžné modely.

Sekvenční modely zahrnují:

• Konečné stavové automaty
• Pushdown automaty
• Stroje s náhodným přístupem
• Turingovy stroje

Mezi funkční modely patří:

• Lambda kalkul
• Obecné rekurzivní funkce
• Kombinovaná logika
• Abstraktní přepisovací systémy

Souběžné modely zahrnují:

• Buněčný automat
• Digitální obvody
• Kahn zpracovává sítě
• Petriho sítě
• Synchronní tok dat
• Interakční sítě
• Herecký model

Modely se liší svou expresivní silou; například každá funkce, kterou lze vypočítat pomocí a Konečný stavový stroj lze také vypočítat pomocí a Turingův stroj, ale ne naopak.

A nedeterministický model výpočtu je spojen s některými z těchto modelů výpočtu. Nedeterministické modely nejsou pro praktické výpočty užitečné; používají se při studiu výpočetní složitost algoritmů.

Použití

V oblasti runtime analýza algoritmů, je běžné specifikovat výpočetní model z hlediska primitivní operace povolené, které mají jednotkové náklady, nebo jednoduše operace jednotkových nákladů. Běžně používaným příkladem je stroj s náhodným přístupem, který má jednotkové náklady na přístup ke čtení a zápisu do všech svých paměťových buněk. V tomto ohledu se liší od výše uvedeného modelu stroje Turing.

Kategorie

Existuje mnoho modelů výpočtu, které se liší souborem přípustných operací a náklady na jejich výpočet. Spadají do následujících širokých kategorií:

• Abstraktní stroj a modely k tomu rovnocenné (např. lambda kalkul je ekvivalentní s Turingův stroj ) - používá se v důkazech vypočítatelnosti a horních mezích výpočetní složitosti algoritmů.
• Modely rozhodovacích stromů - používá se v důkazech dolních mezí výpočetní složitosti algoritmických problémů.

Viz také

• Stohovací stroj (0-operandový stroj)
• Akumulátorový stroj (1-operandový stroj)
• Zaregistrujte stroj (2,3, ... operandový stroj)
• Stroj s náhodným přístupem
• Model buněčné sondy

Reference

Další čtení

• Fernández, Maribel (2009). Modely výpočtu: Úvod do teorie vypočítatelnosti. Pregraduální témata v informatice. Springer. ISBN  978-1-84882-433-1.
• Savage, John E. (1998). Modely výpočtu: Zkoumání výpočetní síly. Addison-Wesley. ISBN  978-0201895391.