[拼音]：suiji cunqu jiqi moxing

[外文]：random access machine model

算法分析與計算復(fù)雜性理論中重要的串行計算模型，簡稱 RAM。引進(jìn)它是為了便于從理論上分析計算機(jī)串行程序所耗費的時間、空間等資源。一個RAM由k個變址器I₁，I₂，…，I_k、無窮個普通寄存器R₀，R₁，R₂，…和一個有窮長的程序所組成。變址器也是寄存器，每個寄存器中可以存放一個自然數(shù)，但只有變址器的內(nèi)容可以作為間接地址。

RAM的程序使用兩種形式的地址。一種是直接地址，形式為I_j(j=1，2，…，k)或R_i(i=0，1，2，…);另一種是間接地址，形式為I_j(j=1，2，…，k)。如果I_j中存的自然數(shù)為i，則I_j代表地址R_i。

RAM的指令為下列形式之一：

（1）A←a，表示把地址A的內(nèi)容改為自然數(shù)a；

（2）A←B，表示把地址A的內(nèi)容改為地址B的內(nèi)容；

（3）A←B*C，表示把地址B中的內(nèi)容和地址C中的內(nèi)容作為運算*之后，送入地址A。這里*可以是自然數(shù)的加法、減法、乘法或整數(shù)除法。減法的定義為：若a≥b則等于a–b，否則等于0；

（4）A←F(B，C)，此處F是一個可以用多帶圖靈機(jī)器在多項式空間和對數(shù)多項式的巡回中實現(xiàn)的變換（見多帶圖靈機(jī)模型）。A、B、C可以是直接地址，也可以是間接地址。A是寫入地址，B、C是讀出地址。

RAM除了可以用以上的指令編程序外，還可以判斷某個寄存器或變址器的內(nèi)容是否為0，以實現(xiàn)條件轉(zhuǎn)移。

變址器是用來實現(xiàn)間接地址的，所以要求在運算過程中變址器中所存的自然數(shù)不大于所用到的普通寄存器數(shù)目的某個常數(shù)倍。

RAM程序的一個例子是：設(shè)n個自然數(shù)a₁，a₂，…，a_n分別存放在R₁，R₂，…，R_n中，n存放在R₀中，要求把這n個數(shù)的和計算出來，結(jié)果放在R₀中。程序如圖。

RAM的資源耗費有兩種定義方式，即均勻耗費和對數(shù)耗費。均勻的空間耗費是指計算中曾經(jīng)使用過的寄存器的總數(shù)。均勻的時間耗費是指自始至終被執(zhí)行的指令和轉(zhuǎn)移的總條數(shù)。均勻耗費常用于算法分析中。

另一種標(biāo)準(zhǔn)是對數(shù)耗費。此時空間耗費指計算中普通寄存器存過的自然數(shù)的最大長度之和。時間耗費則指被執(zhí)行的每條指令的時間耗費之和。而一條指令的時間耗費則被認(rèn)為與被運算的自然數(shù)的長度成正比的。

對于RAM，還可以定義巡回（虛擬的并行時間）。它是計算中周相的總數(shù)，而一個周相則是 RAM工作的一個階段，在此階段中，沒有任何一個普通寄存器先被寫入然后又被讀出。

建筑資質(zhì)代辦咨詢熱線：13198516101

標(biāo)簽：suiji cunqu jiqi moxing、隨機(jī)存取機(jī)器模型

版權(quán)聲明：本文采用知識共享 署名4.0國際許可協(xié)議 [BY-NC-SA] 進(jìn)行授權(quán)

文章名稱：《隨機(jī)存取機(jī)器模型》

文章鏈接：http://m.fjemb.com/12391.html

該作品系作者結(jié)合建筑標(biāo)準(zhǔn)規(guī)范、政府官網(wǎng)及互聯(lián)網(wǎng)相關(guān)知識整合。如若侵權(quán)請通過投訴通道提交信息，我們將按照規(guī)定及時處理。