Výpočetní zdroj - Computational resource
V teorii výpočetní složitosti je výpočetní zdroj zdroj používaný některými výpočetními modely při řešení výpočetních problémů .
Nejjednodušší výpočetní zdroje jsou výpočetní čas , počet kroků nutných k vyřešení problému a paměťový prostor , množství paměti potřebné při řešení problému, ale bylo definováno mnoho složitějších zdrojů.
Výpočtový problém je obecně definován z hlediska jeho působení na jakýkoli platný vstup. Příklady problémů mohou být „dané celé číslo n , určit, zda n je prvočíslo“, nebo „vzhledem k dvěma číslům x a y vypočítat součin x * y “. Jak se vstupy zvětšují, množství výpočetních zdrojů potřebných k vyřešení problému se zvýší. Zdroje potřebné k vyřešení problému jsou tedy popsány z hlediska asymptotické analýzy pomocí identifikace zdrojů jako funkce délky nebo velikosti vstupu. Využití zdrojů je často částečně kvantifikováno pomocí Big O notace .
Výpočtové prostředky jsou užitečné, protože můžeme studovat, které problémy lze vypočítat v určitém množství každého výpočetního zdroje. Tímto způsobem můžeme určit, zda jsou algoritmy pro řešení problému optimální, a můžeme činit prohlášení o účinnosti algoritmu . Soubor všech výpočetních problémů, které lze vyřešit pomocí určitého množství určitého výpočetního zdroje, je třída složitosti a vztahy mezi různými třídami složitosti jsou jedním z nejdůležitějších témat teorie složitosti.
Popis obecně dostupného výpočetního zařízení
Termín „výpočetní zdroj“ se běžně používá k popisu dostupného výpočetního vybavení a softwaru. Viz Utility computing .
Formální kvantifikace výpočetní kapacity
Bylo vyvinuto určité úsilí formálně kvantifikovat výpočetní kapacitu. Ohraničený Turingův stroj byl použit k modelování konkrétních výpočtů pomocí počtu přechodů stavů a velikosti abecedy ke kvantifikaci výpočetního úsilí potřebného k vyřešení konkrétního problému.