RAMモデルで1つの操作/サイクル/移動を構成するものは何ですか？

Question

入力テープ、出力テープ、プログラム（読み取り専用）、命令ポインター、およびメモリレジスタを表示するRAMモデル図が表示されました。ただし、時間の複雑さの質問を見ると、プログラムが1つのアクションに費やす必要がある時間に関連しています。読み取りテープから1つの整数記号を読み取り、メモリレジスタから整数に追加し、結果を書き込みテープセルに押し上げ、読み取りヘッドを右に移動し、ヘッドを書き込みます。左側。どれくらいの時間またはいくつの動きを無駄にしましたか？

Answer 1

通常、複雑さは、チューリングマシンモデルを使用して定義され、整数の追加などの複雑な操作中に取られたリソースの量の問題を回避します。

RAMマシンの複雑さのさまざまな表記法を使用できます。これは、あなたがやろうとしていることに依存します。チューリングマシンを使用して定義されている標準の複雑さクラスと比較できる場合は、チューリングマシンがその操作をシミュレートするために必要なリソース使用量の量を各操作に割り当てる必要があります。答えは、RAMマシンがどのような操作をサポートしているかにも依存します。

標準RAMモデルは、プログラムが保存される有限コントロール、1つまたは複数のアキュムレータが$ acc $、命令カウンター、およびメモリの無限のコレクション$ r [0]、r [1]、 ldots $を登録する有限コントロールで構成されています。命令は4つのカテゴリに分類できます。

• フローコントロール：無条件のジャンプ、受け入れ、拒否、停止、条件ジャンプ（「条件」は$ acc = 0？$のように単純です）;

• 入力/出力：読み取り、書き込み;

• アキュムレータとメモリ間のデータ移動：ロード、保存;
• 算術：$ acc：= 0 $、$ r [i] $を追加$ acc $;

さらに2つの一般的なコストは、均一で対数です。 2つは、上記の命令セットの関連する四重局です（つまり、ユニフォームを実行時間を四角化するために必要な対数に変換するため）。対数とは、操作への入力の対数（つまり、ビット数）にコストを取ることを意味しますが、ユニフォームはすべての操作に単位時間がかかると見なされることを意味します。