np完整性理論ppt課件-展示頁
2025-05-14 18:18本頁面
【正文】 機(jī)器字長要遠(yuǎn)大于其他模型。 例如，要表示一個(gè)有 100個(gè)頂點(diǎn)的圖中從頂點(diǎn) v到其余各頂點(diǎn) 間有沒有邊相連，可以用 100位的一個(gè)位向量表示。 在位式計(jì)算模型下，每個(gè)邏輯運(yùn)算指令耗費(fèi)一個(gè)單位時(shí)間。 (2)所用的運(yùn)算是邏輯運(yùn)算而不是算術(shù)運(yùn)算。在對數(shù) 耗費(fèi)標(biāo)準(zhǔn)下，使用另一個(gè) RAM的簡化計(jì)算模型，稱之為位式計(jì)算 (Bitwise Computation)模型。 每條指令耗費(fèi)一個(gè)單位時(shí)間。 由此，對每一個(gè)固定的 n得到一個(gè)無循環(huán)的直線式程序。 8 RAM模型的變形與簡化 2. 直線式程序 對于許多問題，所設(shè)計(jì)的 RAM程序中的轉(zhuǎn)移指令僅用于重復(fù) 一組指令，而且重復(fù)的次數(shù)與問題的輸入規(guī)模 n成比例。 (4)常見函數(shù)的計(jì)算，如三角函數(shù)，指數(shù)函數(shù)，對數(shù)函數(shù)等。 (2)2個(gè)實(shí)數(shù)間的比較 (， ≤ ， =， ≠ ， ≥ ， )。下列的各 運(yùn)算為基本運(yùn)算且每個(gè)運(yùn)算只耗費(fèi)單位時(shí)間?？臻g復(fù)雜性的情況也是類似的。在一個(gè)計(jì)算模型下 T(n)時(shí)間內(nèi)完成的輸入 輸出映射可在另一個(gè)計(jì)算模型下模擬，并在 kT(n)時(shí)間內(nèi)完成。 RASP指令用整數(shù)進(jìn)行編碼。每條 RASP指令占據(jù) 2個(gè)連續(xù)的寄存器。在 RAM計(jì)算模型下， 假定一個(gè)寄存器可存放一個(gè)任意大小的整數(shù)。以后除特別注明， RAM程序的復(fù)雜 性將按照均勻耗費(fèi)標(biāo)準(zhǔn)衡量。如果一個(gè) RAM程序 P讀了字符串 S及結(jié)束標(biāo)志符 0后，在輸出 帶的第一格輸出一個(gè) 1并停機(jī)，就說程序 P接受字符串 S。在輸入帶的第一個(gè)方 格中放入符號(hào) a1， 第二個(gè)方格中放入符號(hào) a2， … ， 第 n個(gè)方格中 放入符號(hào) an。 解釋一：把 RAM程序看成是計(jì)算一個(gè)函數(shù) 若一個(gè) RAM程序 P總是從輸入帶前 n個(gè)方格中讀入 n個(gè)整數(shù) x1， x2， … ， xn， 并且在輸出帶的第一個(gè)方格上輸出一個(gè)整數(shù) y 后停機(jī)，那么就說程序 P計(jì)算了函數(shù) f(x1， x2， … ， xn)=y 解釋二：把 RAM程序當(dāng)作一個(gè)語言接受器。1 第 8章 NP完全性理論 2 計(jì)算模型 ? 隨機(jī)存取機(jī) RAM ? 隨機(jī)存取存儲(chǔ)程序機(jī) RASP ? RAM模型的變形與簡化 ? 圖靈機(jī) ? 圖靈機(jī)模型與 RAM模型的關(guān)系 ? 問題變換與計(jì)算復(fù)雜性歸約 3 隨機(jī)存取機(jī) RAM 1. RAM的結(jié)構(gòu) 4 隨機(jī)存取機(jī) RAM 2. RAM程序 一個(gè) RAM程序定義了從輸入帶到輸出帶的一個(gè)映射。可以對 這種映射關(guān)系作 2種不同的解釋。 將字符串 S=a1a2… an放在輸入帶上。 然后在第 n+1個(gè)方格中放入 0，作為輸入串的結(jié)束標(biāo) 志符。 5 隨機(jī)存取機(jī) RAM 3. RAM程序的耗費(fèi)標(biāo)準(zhǔn) 標(biāo)準(zhǔn)一：均勻耗費(fèi)標(biāo)準(zhǔn) 在均勻耗費(fèi)標(biāo)準(zhǔn)下，每條 RAM指令需要一個(gè)單位時(shí)間；每 個(gè)寄存器占用一個(gè)單位空間。 標(biāo)準(zhǔn)二：對數(shù)耗費(fèi)標(biāo)準(zhǔn) 對數(shù)耗費(fèi)標(biāo)準(zhǔn)是基于這樣的假定，即執(zhí)行一條指令的耗費(fèi) 與以二進(jìn)制表示的指令的操作數(shù)長度成比例。因此若設(shè) l(i)是整 數(shù) i所占的二進(jìn)制位數(shù)，則 ? ?001||lo g)(??????iiiil6 隨機(jī)存取存儲(chǔ)程序機(jī) RASP 1. RASP的結(jié)構(gòu) RASP的整體結(jié)構(gòu)類似于 RAM， 所不同的是 RASP的程序是存儲(chǔ)在寄存器中的。第一個(gè)寄存器存放操作碼的編碼，第二個(gè)寄存器存放地址。 2. RASP程序的復(fù)雜性 不管是在均勻耗費(fèi)標(biāo)準(zhǔn)下，還是在對數(shù)耗費(fèi)標(biāo)準(zhǔn)下， RAM程序和 RASP程序的復(fù)雜性只差一個(gè)常數(shù)因子。其中 k是一個(gè)常數(shù)因子。 7 RAM模型的變形與簡化 1. 實(shí)隨機(jī)存取機(jī) RRAM 在 RRAM模型下，一個(gè)存儲(chǔ)單元可以存放一個(gè)實(shí)數(shù)。 (1)算術(shù)運(yùn)算 +，－，／。 (3)間接尋址 (整數(shù)地址 )。 優(yōu)點(diǎn)：能夠方便處理實(shí)數(shù)； 適合于用 FORTRAN， PASCAL等高級(jí)語言寫的算法。在這種情 況下，可以用重復(fù)地寫出相同指令組的方法來消除程序中的循環(huán)。 經(jīng)過對 RAM模型的簡化，得到直線式程序的指令系統(tǒng)如下： x←y+z x←y z x←y*z x←y/z x←i 其中 x， y和 z是符號(hào)地址 (或變量 )，而 i是常數(shù)。 9 RAM模型的變形與簡化 3. 位式計(jì)算 直線式程序計(jì)算模型顯然是基于均勻耗費(fèi)標(biāo)準(zhǔn)的。 除了下列 2點(diǎn)外，該計(jì)算模型與直線式程序計(jì)算模型基本 相同： (1)假設(shè)所有變量取值 0或 1，即為位變量。 用
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1