Resursă computațională - Computational resource
În teoria complexității de calcul , o resursă de calcul este o resursă utilizată de unele modele de calcul în soluția problemelor de calcul .
Cele mai simple resurse de calcul sunt timpul de calcul , numărul de pași necesari pentru rezolvarea unei probleme și spațiul de memorie , cantitatea de stocare necesară pentru rezolvarea problemei, dar au fost definite multe resurse mai complicate.
O problemă de calcul este în general definită în termenii acțiunii sale asupra oricărei intrări valide. Exemple de probleme ar putea fi „dat un număr întreg n , determinați dacă n este prim” sau „având două numere x și y , calculați produsul x * y ”. Pe măsură ce intrările cresc, cantitatea de resurse de calcul necesare pentru rezolvarea unei probleme va crește. Astfel, resursele necesare pentru rezolvarea unei probleme sunt descrise în termeni de analiză asimptotică , prin identificarea resurselor în funcție de lungimea sau dimensiunea intrării. Utilizarea resurselor este adesea parțial cuantificate folosind Big O notație .
Resursele de calcul sunt utile deoarece putem studia care probleme pot fi calculate într-o anumită cantitate din fiecare resursă de calcul. În acest fel, putem determina dacă algoritmii pentru rezolvarea problemei sunt optimi și putem face afirmații despre eficiența unui algoritm . Setul tuturor problemelor de calcul care pot fi rezolvate folosind o anumită cantitate dintr-o anumită resursă de calcul este o clasă de complexitate , iar relațiile dintre diferite clase de complexitate sunt unul dintre cele mai importante subiecte din teoria complexității.
Descrierea echipamentelor de calcul accesibile în general
Termenul „resursă de calcul” este utilizat în mod obișnuit pentru a descrie echipamente și software de calcul accesibile. Vezi Calculul utilitar .
Cuantificarea formală a capacității de calcul
S-au depus unele eforturi pentru a cuantifica formal capacitatea de calcul. O mașină Turing mărginită a fost utilizată pentru a modela calcule specifice folosind numărul de tranziții de stare și dimensiunea alfabetului pentru a cuantifica efortul de calcul necesar pentru a rezolva o anumită problemă.