계산 모형
Model of computation | 이 기사는 대부분 또는 전체적으로 단일 출처에 의존하고 있습니다.: · · · ( 2021년 2월) |
컴퓨터 과학에서, 특히 계산 가능성 이론과 계산 복잡성 이론에서, 계산 모델은 입력이 주어졌을 때 수학 함수의 출력이 어떻게 계산되는지를 설명하는 모델이다.모델은 계산, 메모리 및 통신 단위가 어떻게 [1]구성되는지 설명합니다.알고리즘의 계산 복잡도는 계산 모델이 주어졌을 때 측정될 수 있다.모델을 사용하면 특정 구현 및 특정 기술에 고유한 변형으로부터 독립적으로 알고리즘의 성능을 연구할 수 있습니다.
모델
계산 모델은 순차 모델, 기능 모델 및 동시 모델의 세 가지 범주로 분류할 수 있습니다.
시퀀셜 모델
시퀀셜 모델에는 다음이 포함됩니다.
- 유한 상태 기계
- 포스트 머신(Post-Turing 머신 및 태그 머신)
- 푸시다운 오토마타
- 머신을 등록
- 튜링 기계
- 의사결정 트리 모델
기능 모델
기능 모델은 다음과 같습니다.
동시 모델
동시 모델에는 다음이 포함됩니다.
이들 모델 중 일부는 결정론적 변종과 비결정론적 변형을 모두 가지고 있다.비결정론적 모델은 실제 [citation needed]계산에 유용하지 않습니다. 알고리즘의 계산 복잡성 연구에 사용됩니다.
모델은 표현력에 차이가 있다. 예를 들어, 유한 상태 기계에 의해 계산될 수 있는 각 함수는 튜링 기계에 의해 계산될 수도 있지만, 그 반대는 아니다.
사용하다
알고리즘의 런타임 분석 분야에서는 단위 비용 또는 단순히 단위 비용 연산이 허용되는 원시 연산의 관점에서 계산 모델을 지정하는 것이 일반적이다.일반적으로 사용되는 예로는 랜덤액세스 머신이 있습니다.랜덤액세스 머신은 모든 메모리셀에 대한 읽기 및 쓰기 액세스의 단가를 가집니다.이 점에서, 그것은 위에서 언급한 튜링 기계 모델과 다르다.
「 」를 참조해 주세요.
- 스택 머신(0-operand 머신)
- 어큐뮬레이터 머신(1 오퍼랜드 머신)
- 기계 등록(2,3,... 피연산자 기계
- 랜덤 액세스 머신
- 추상 기계
- 세포 프로브 모델
- Robertson-Webb 쿼리 모델
- 촘스키 계층
- 튜링 완전성
레퍼런스
- ^ "Models of Computation" (PDF).
추가 정보
- Fernández, Maribel (2009). Models of Computation: An Introduction to Computability Theory. Undergraduate Topics in Computer Science. Springer. ISBN 978-1-84882-433-1.
- Savage, John E. (1998). Models Of Computation: Exploring the Power of Computing. Addison-Wesley. ISBN 978-0201895391.
