Számítási erőforrás - Computational resource
A számítási komplexitás elméletében a számítási erőforrás olyan erőforrás, amelyet egyes számítási modellek a számítási problémák megoldása során használnak .
A legegyszerűbb számítási erőforrások a számítási idő , a probléma megoldásához szükséges lépések száma és a memóriaterület , a probléma megoldása során szükséges tárterület mennyisége, de sok bonyolultabb erőforrást határoztak meg.
A számítási problémát általában minden érvényes bemenetre gyakorolt hatása alapján határozzák meg. Példák a problémákra: "megadhatunk n egész számot , meghatározhatjuk, hogy n prím-e", vagy "két x és y számot adunk , kiszámoljuk az x * y szorzatot ". Amint a bemenetek nagyobbak lesznek, a probléma megoldásához szükséges számítási erőforrások mennyisége megnő. Így a probléma megoldásához szükséges erőforrásokat aszimptotikus elemzéssel írják le , azonosítva az erőforrásokat a bemenet hosszának vagy méretének függvényében. Az erőforrás-felhasználást gyakran részben számszerűsítik Big O jelöléssel .
A számítási erőforrások azért hasznosak, mert megvizsgálhatjuk, mely problémák számíthatók ki az egyes számítási erőforrások bizonyos mennyiségében. Így meghatározhatjuk, hogy a probléma megoldására szolgáló algoritmusok optimálisak-e, és kijelentéseket tehetünk egy algoritmus hatékonyságáról . Az összes számítási probléma összessége, amely egy bizonyos számítási erőforrás bizonyos mennyiségének felhasználásával megoldható, egy komplexitási osztály , és a különböző komplexitási osztályok közötti kapcsolatok az egyik legfontosabb téma a komplexitáselméletben.
Az általánosan hozzáférhető számítástechnikai eszközök leírása
A "Számítási erőforrás" kifejezést általában az elérhető számítástechnikai berendezések és szoftverek leírására használják. Lásd: Segédprogram-számítás .
A számítási képesség hivatalos számszerűsítése
Némi erőfeszítés történt a számítási képesség formális számszerűsítésére. Határozott Turing-gépet használtak specifikus számítások modellezésére az állapotátmenetek számának és az ábécé méretének felhasználásával az adott probléma megoldásához szükséges számítási erőfeszítések számszerűsítésére.