리얼 램

Real RAM

컴퓨터, 특히 컴퓨터 기하학에서 실제 RAM(Random-Access Machine)은 대부분의 실제 컴퓨터가 사용하는 이진 고정점이나 부동소수점 번호 대신 정확한 실수로 계산이 가능한 컴퓨터의 수학 모델이다.진짜 램은 마이클 이안 샤모스가 1978년 박사학위 논문에서 공식화한 것이다.[1]

모델

실제 RAM 모델 이름의 "RAM" 부분은 "랜덤 액세스 머신"을 의미한다.이것은 표준 컴퓨터 구조의 단순화된 버전을 닮은 컴퓨팅 모델이다.저장 프로그램, 셀의 배열로 이루어진 컴퓨터 메모리 유닛, 레지스터의 수가 한정된 중앙 처리 유닛으로 구성된다.각 메모리 셀 또는 레지스터는 실제 번호를 저장할 수 있다.프로그램의 제어 하에, 실제 RAM은 메모리와 레지스터 사이에 실수를 전송할 수 있으며 레지스터에 저장된 값에 대해 산술 연산을 수행할 수 있다.

허용된 연산에는 일반적으로 비교뿐만 아니라 덧셈, 뺄셈, 곱셈, 나눗셈을 포함하지만 계량이나 정수에 대한 반올림 등은 포함되지 않는다.정수 반올림과 계량 연산을 피하는 이유는 이러한 연산을 허용하면 실제 RAM에게 불합리한 양의 계산력을 부여하여 다항 시간 내에 PSPACE-완전 문제를 해결할 수 있기 때문이다.[2]

실제 RAM에 대한 알고리즘을 분석할 때, 허용된 각 작동은 일반적으로 일정한 시간이 걸리는 것으로 가정한다.

실행

프로그래머가 실제 RAM에서 실행하는 것처럼 작동하는 컴퓨터 프로그램을 작성할 수 있는 LEDA와 같은 소프트웨어 라이브러리가 개발되었다.이러한 라이브러리는 실제 RAM이 생성하는 것과 동일한 결과를 사용하여 산술 및 비교를 수행할 수 있는 데이터 구조를 사용하여 실제 값을 나타낸다.예를 들어, LEDA에서는 실수는 다음을 사용하여 표시된다.leda_real자연수 k, 이성 연산자 및 비교 연산자에 대해 k-th 루트를 지원하는 데이터 유형.[3]이러한 실제 데이터 유형을 사용한 기반 실제 RAM 알고리즘의 시간 분석은 주어진 알고리즘에 필요한 라이브러리 호출 수를 세는 것으로 해석할 수 있다.[4]

관련 모델

실제 RAM은 후기 블럼-블럼-과 매우 흡사하다.슈브-스마일 기계.[5]그러나 실제 RAM은 일반적으로 컴퓨터 기하학에서 콘크리트 알고리즘 분석에 사용되는 반면 블럼-은대신 슈브-스마일 기계는 NP-완전성 이론을 실제 수 계산으로 확장하기 위한 기초를 형성한다.

실제 RAM의 대안으로 문제에 대한 입력과 메모리와 레지스터에 저장된 값을 모두 고정된 비트 수를 가진 정수로 가정하는 RAM이라는 단어가 있다.예를 들어, RAM 모델이라는 단어는 실제 RAM보다 더 빠르게 일부 작업을 수행할 수 있다. 예를 들어, 그것은 빠른 정수 정렬 알고리즘을 허용하는 반면 실제 RAM에 대한 정렬은 느린 비교 정렬 알고리즘으로 이루어져야 한다.그러나 일부 계산 기하학 문제에는 정수 좌표를 사용하여 정확하게 나타낼 수 없는 입력 또는 출력이 있다. 예를 들어, 정수 좌표 표시가 없는 점 및 선 세그먼트의 배열인 Perles 구성을 참조하십시오.

참조

  1. ^ Shamos, Michael Ian (1978), Computational Geometry, Ph.D. dissertation, Yale University.
  2. ^ Schönhage, Arnold (1979), "On the power of random access machines", Proceedings of the Sixth International Colloquium on Automata, Languages and Programming (ICALP '79), Lecture Notes in Computer Science, vol. 71, Springer, pp. 520–529, doi:10.1007/3-540-09510-1_42, ISBN 978-3-540-09510-1, MR 0573259.
  3. ^ Melhorn, Kurt; Näher, Stefan (1999). The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press. Retrieved 12 November 2019.
  4. ^ Mehlhorn, Kurt; Schirra, Stefan (2001), "Exact computation with leda_real—theory and geometric applications" (PDF), Symbolic Algebraic Methods and Verification Methods (Dagstuhl, 1999), Springer, pp. 163–172, doi:10.1007/978-3-7091-6280-4_16, ISBN 978-3-211-83593-7, MR 1832422.
  5. ^ Blum, Lenore; Shub, Mike; Smale, Steve (1989), "On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines", Bulletin of the American Mathematical Society, 21 (1): 1–46, doi:10.1090/S0273-0979-1989-15750-9, Zbl 0681.03020.

외부 링크