リアルRAM

コンピューティング、特に計算幾何学において、実 RAM (ランダムアクセスマシン) は、実際のコンピュータのほとんどで使用されるバイナリ固定小数点数または浮動小数点数の代わりに正確な実数で計算できるコンピュータの数学的モデルです。実 RAM は、マイケル・イアン・シャモスが1978 年の博士論文で定式化しました。^[1]

モデル

実 RAM モデル名の「RAM」部分は、「ランダムアクセスマシン」の略です。これは、標準的なコンピュータアーキテクチャの簡略版に似たコンピューティングモデルです。格納されたプログラム、セルの配列で構成されるコンピュータメモリユニット、および制限された数のレジスタを備えた中央処理装置で構成されます。各メモリセルまたはレジスタには、実数を格納できます。プログラムの制御下で、実 RAM はメモリとレジスタ間で実数を転送し、レジスタに格納された値に対して算術演算を実行できます。

許可される演算には通常、加算、減算、乗算、除算、比較が含まれますが、剰余や整数への丸めは含まれません。整数の丸めや剰余演算を避ける理由は、これらの演算を許可すると実際のRAMに不当な量の計算能力が与えられ、PSPACE完全問題を多項式時間で解くことができるようになるためです。^[2]

実際の RAM のアルゴリズムを分析する場合、許可される各操作には通常、一定の時間がかかるものと想定されます。

実装

LEDAなどのソフトウェアライブラリが開発され、プログラマーは実際の RAM 上で実行されているかのように動作するコンピュータプログラムを作成できます。これらのライブラリは、実際の RAM と同じ結果で算術演算や比較を実行できるデータ構造を使用して実数値を表します。たとえば、LEDA では、実数はleda_realデータ型を使用して表され、任意の自然数kのk乗根、有理数演算子、比較演算子をサポートします。^[3]これらの実数データ型を使用する基礎となる実際の RAM アルゴリズムの時間分析は、特定のアルゴリズムに必要なライブラリ呼び出しの数をカウントすることと解釈できます。^[4]

他の計算モデルとの比較

チューリングマシンモデルでは、計算の基本単位は 1 ビットです。したがって、数値アルゴリズムの時間と空間の複雑さは、数値を表現するために必要なビット数に依存します。対照的に、実数 RAM モデルでは、計算の基本単位は、表現に必要なビット数に関係なく、実数です。この違いは、ガウス消去法などのアルゴリズムを分析するときに重要です。このアルゴリズムは、実数に対して多項式数の算術演算を必要とするため、実数 RAM モデルでは多項式です。ただし、中間計算で使用される数は (単純に実装された場合) 指数的に大きくなる可能性があるため、チューリングマシンモデルでは実行時間は指数的になります。^[5]^{: Sec.1.4}
実RAMは、後のブルーム・シューブ・スメール・マシンによく似ています。^{[6]しかし、実RAMは通常、}計算幾何学における具体的なアルゴリズムの分析に使用され、ブルーム・シューブ・スメール・マシンは、 NP完全性の理論を実数計算に拡張するための基礎を形成します。
実 RAM の代替としてワード RAMがあります。ワード RAMでは、問題への入力とメモリおよびレジスタに格納される値は、両方とも固定ビット数の整数であると想定されます。ワード RAM モデルは、実 RAM よりも高速にいくつかの操作を実行できます。たとえば、実 RAM でのソートは低速の比較ソートアルゴリズムで行う必要がありますが、ワード RAM モデルでは高速な整数ソートアルゴリズムを使用できます。ただし、計算幾何学の問題の中には、整数座標を使用して正確に表現できない入力または出力を持つものがあります。たとえば、整数座標表現を持たない点と線分の配置であるPerles 構成を参照してください。

参考文献

^ シャモス、マイケル・イアン（1978）、計算幾何学、イェール大学博士論文。
^ Schönhage, Arnold (1979)、「ランダムアクセスマシンのパワーについて」、第6回オートマトン、言語、プログラミングに関する国際会議 (ICALP '79) の議事録、コンピュータサイエンスの講義ノート、第71巻、Springer、pp. 520– 529、doi :10.1007/3-540-09510-1_42、ISBN 978-3-540-09510-1、MR 0573259。
^ Melhorn, Kurt; Näher, Stefan (1999). The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press . 2019年11月12日閲覧。
^ Mehlhorn, Kurt ; Schirra, Stefan (2001)、「leda_real による正確な計算 - 理論と幾何学的応用」(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。
^ Grötschel, M.; Lovász, L.; Schrijver, A. (1981-06-01). 「楕円体法と組み合わせ最適化におけるその影響」. Combinatorica . 1 (2): 169– 197. doi :10.1007/BF02579273. ISSN 1439-6912. S2CID 43787103.
^ ブルーム、レノア、シューブ、マイク、スメール、スティーブ（1989）「実数上の計算と複雑性の理論について：NP完全性、再帰関数、ユニバーサルマシン」、アメリカ数学会誌、21（1）：1– 46、doi：10.1090 / S0273-0979-1989-15750-9、Zbl 0681.03020。

外部リンク

実現可能なリアルランダムアクセスマシンの参考文献
幾何学的計算幾何学的アルゴリズムを機能させる科学

[1] シャモス、マイケル・イアン（1978）、計算幾何学、イェール大学博士論文。

[2] Schönhage, Arnold (1979)、「ランダムアクセスマシンのパワーについて」、第6回オートマトン、言語、プログラミングに関する国際会議 (ICALP '79) の議事録、コンピュータサイエンスの講義ノート、第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 . 2019年11月12日閲覧。

[4] Mehlhorn, Kurt ; Schirra, Stefan (2001)、「leda_real による正確な計算 - 理論と幾何学的応用」(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] Grötschel, M.; Lovász, L.; Schrijver, A. (1981-06-01). 「楕円体法と組み合わせ最適化におけるその影響」. Combinatorica . 1 (2): 169– 197. doi :10.1007/BF02579273. ISSN 1439-6912. S2CID 43787103.

[6] ブルーム、レノア、シューブ、マイク、スメール、スティーブ（1989）「実数上の計算と複雑性の理論について：NP完全性、再帰関数、ユニバーサルマシン」、アメリカ数学会誌、21（1）：1– 46、doi：10.1090 / S0273-0979-1989-15750-9、Zbl 0681.03020。