계산 자원

Computational resource
기타 용도는 리소스(컴퓨터 과학)를 참조하십시오.

계산 복잡도 이론에서 계산 자원은 계산 문제 해결에서 일부 계산 모델에 의해 사용되는 자원이다.

가장 간단한 계산 리소스는 계산 시간, 문제 해결에 필요한 단계 수, 그리고 문제 해결에 필요한 스토리지 양인 메모리 공간이지만, 더 복잡한 리소스가 많이 [citation needed]정의되어 있습니다.

계산 문제는 일반적으로 유효한 입력에 대한 동작의 관점에서 정의됩니다[citation needed].문제의 예로는 "n이 정수인지, n이 소수인지 확인" 또는 "x와 y 두 숫자를 지정하면 x*y 곱을 계산합니다" 등이 있습니다.입력이 커짐에 따라 문제 해결에 필요한 계산 자원의 양도 증가합니다.따라서, 문제 해결에 필요한 자원은 입력의 길이 또는 크기의 함수로서 자원을 식별함으로써 점근 분석의 관점에서 설명된다.리소스 사용량은 종종 빅 O 표기법을 사용하여 부분적으로 수량화됩니다.

계산 자원은 우리가 각 계산 자원에서 어떤 문제를 계산할 수 있는지를 연구할 수 있기 때문에 유용하다.이렇게 하면 문제를 해결하기 위한 알고리즘이 최적의지 여부를 판단할 수 있고 알고리즘의 효율성에 대해 설명할 수 있습니다.특정 계산 자원을 사용하여 해결할 수 있는 모든 계산 문제의 집합은 복잡도 클래스이며, 다른 복잡도 클래스 간의 관계는 복잡도 이론에서 가장 중요한 주제 중 하나입니다.

일반적으로 접근하기 쉬운 컴퓨팅 기기 설명

컴퓨팅 리소스라는 용어는 일반적으로 접근 가능한 컴퓨팅 기기 및 소프트웨어를 나타내기 위해 사용됩니다.유틸리티 컴퓨팅을 참조해 주세요.

컴퓨팅 기능의 정식 수량화

컴퓨팅 능력을 공식적으로 수치화하려는 노력이 있었습니다.유계 튜링 기계는 특정 [1][2]문제를 해결하기 위해 필요한 계산 노력을 정량화하기 위해 상태 전이 수와 알파벳 크기를 사용하여 특정 계산을 모델링하기 위해 사용되어 왔다.

레퍼런스

  1. ^ Gregory J., Chaitin (1966). "On the Length of Programs for Computing Finite Binary Sequences" (PDF). Journal of the ACM. 13 (4): 547–569. doi:10.1145/321356.321363. S2CID 207698337. Archived from the original (PDF) on 2007-02-05. Retrieved 2007-09-25.
  2. ^ Sow, Daby; Eleftheriadis, Alexandros (1998). "Representing Information with Computational Resource Bounds" (PDF). Signals, Systems & Computers. Conference Record of the Thirty-Second Asilomar Conference on. Vol. 1. pp. 452–456. ISBN 0-7803-5148-7. 10.1109/ACSSC.1998.750904. Retrieved 2007-09-25.