word-RAM

• 計算モデルの一つ

• RAMモデル(RAM: Random Access Machine)

  • 各単純計算(+, -, *, =, if, call)は一単位時間で実行できる
  • 各メモリアクセスは1単位時間で実行できる
  • メモリの1つのセルには任意の桁の数を格納できる

• word-RAM: RAMモデルをより現実的にしたもの

  • 

  • 計算機は$U$ビットのメモリを持つ。メモリのアドレスは[$0$, $U-1$]の整数で指定する

  • 計算機の語長は${\log }_{2}U$ビットである。つまり、$lo{g}_{2}U$ビットの数の算術・論理演算・および連続する$lo{g}_{2}U$ビットのメモリアクセスが1単位時間で行える

  • メモリから読み込んだ値は[$0,U-1$]の整数とみなす

• word-RAMにおける空間計算量

  • アルファベット: $A=1,2,...,\sigma -1,\sigma$
    • [$\mathrm{1..}\sigma$]と表すことも
    • 文字の集合
    • $\sigma$: アルファベットサイズ
  • サイズ$\sigma$のアルファベット上の、長さ$n$の文字列: $n{\log }_2\sigma$bitの領域を占める
    • 1文字あたり${\log }_2\sigma$bit使うのだから、あたりまえ体操(kekeho)