np完整性理論ppt課件-wenkub
2023-05-20 18:18:47 本頁面
【正文】 RAM模型的變形與簡化 5. 判定樹 判定樹是一棵二叉樹。 10 RAM模型的變形與簡化 4. 位向量運(yùn)算 (Bit Vector Operations) 若在直線式程序計(jì)算模型中，假設(shè)所有變量均為位向量，而 且所用的運(yùn)算均為位操作指令，則得到位向量運(yùn)算計(jì)算模型。 除了下列 2點(diǎn)外，該計(jì)算模型與直線式程序計(jì)算模型基本 相同： (1)假設(shè)所有變量取值 0或 1，即為位變量。 經(jīng)過對 RAM模型的簡化，得到直線式程序的指令系統(tǒng)如下： x←y+z x←y z x←y*z x←y/z x←i 其中 x， y和 z是符號地址 (或變量 )，而 i是常數(shù)。 優(yōu)點(diǎn)：能夠方便處理實(shí)數(shù)； 適合于用 FORTRAN， PASCAL等高級語言寫的算法。 (1)算術(shù)運(yùn)算 +，－，／。其中 k是一個(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ù)長度成比例。 然后在第 n+1個(gè)方格中放入 0，作為輸入串的結(jié)束標(biāo) 志符?？梢詫? 這種映射關(guān)系作 2種不同的解釋。 解釋一：把 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è)語言接受器。如果一個(gè) RAM程序 P讀了字符串 S及結(jié)束標(biāo)志符 0后，在輸出 帶的第一格輸出一個(gè) 1并停機(jī)，就說程序 P接受字符串 S。在 RAM計(jì)算模型下， 假定一個(gè)寄存器可存放一個(gè)任意大小的整數(shù)。 RASP指令用整數(shù)進(jìn)行編碼?？臻g復(fù)雜性的情況也是類似的。 (2)2個(gè)實(shí)數(shù)間的比較 (， ≤ ， =， ≠ ， ≥ ， )。 8 RAM模型的變形與簡化 2. 直線式程序 對于許多問題，所設(shè)計(jì)的 RAM程序中的轉(zhuǎn)移指令僅用于重復(fù) 一組指令，而且重復(fù)的次數(shù)與問題的輸入規(guī)模 n成比例。 每條指令耗費(fèi)一個(gè)單位時(shí)間。 (2)所用的運(yùn)算是邏輯運(yùn)算而不是算術(shù)運(yùn)算。 例如，要表示一個(gè)有 100個(gè)頂點(diǎn)的圖中從頂點(diǎn) v到其余各頂點(diǎn) 間有沒有邊相連，可以用 100位的一個(gè)位向量表示。它的每個(gè)內(nèi)結(jié)點(diǎn)表示一個(gè)形如 x∶y 的 比較。下圖是對 a， b， c三個(gè)數(shù)進(jìn)行排序的一棵判定樹。 (2)每個(gè)單兒子內(nèi)部結(jié)點(diǎn) (簡單結(jié)點(diǎn) )v表示下列形式運(yùn)算指令： op 或 op 或 其中， 和 分別是結(jié)點(diǎn) v在樹 T中的祖先結(jié)點(diǎn) v1和 v2處得到 的結(jié)果值，或是 x的分量； op∈{+ ，－， /}； c是一個(gè)常數(shù)。 代數(shù)判定樹 T是一棵二叉樹，且 (1)每個(gè)葉結(jié)點(diǎn)表示輸出結(jié)果 YES或 NO。 (1)改變有限狀態(tài)控制器中的狀態(tài)。 (2)T是有限個(gè)帶符號的集合。 (6)qf是終止 (或接受 )狀態(tài) 。如果對某個(gè)長度為 n的輸入，圖靈機(jī)不停機(jī)，T(n)對這個(gè) n值無定義。 17 圖靈機(jī)模型與 RAM模型的關(guān)系 圖靈機(jī)模型與 RAM模型的關(guān)系是指同一問題在這 2種不同計(jì)算模型下的復(fù)雜性之間的關(guān)系。 (2)解出問題 B。 當(dāng) τ(n) 為 n的多項(xiàng)式時(shí)，稱問題 A可在多項(xiàng)式時(shí)間內(nèi)變換為問題 B。 19 問題變換與計(jì)算復(fù)雜性歸約 命題 1(計(jì)算時(shí)間下界歸約 )：若已知問題 A的計(jì)算時(shí)間下界為 T(n)， 且問題 A是 τ(n) 可變換到問題 B， 即 A∝ τ(n) B， 則 T(n)O(τ(n)) 為問題 B的一個(gè)計(jì)算時(shí)間下界。 nxxx ,..., 21?? ?ji ji xx )( 元素惟一性問題可以在 O(1)時(shí)間內(nèi)變換為判別函數(shù)問題。 在元素惟一性問題中，將每一個(gè)實(shí)數(shù) ， 1≤ i≤n ， 變換為平面上的點(diǎn) ( ， 0)， 1≤ i≤n ， 則元素惟一性問題可以在線性時(shí)間內(nèi)變換為最接近點(diǎn)對問題。x 1,x2,… ,xk)與之對應(yīng)。 23 P類與 NP類語言 P類和 NP類語言的定義： P={L|L是一個(gè)能在 多項(xiàng)式時(shí)間內(nèi) 被一臺 DTM所接受的語言 } NP={L|L是一個(gè)能在 多項(xiàng)式時(shí)間 內(nèi)被一臺 NDTM所接受的語言 } 由于一臺確定性圖靈機(jī)可看作是非確定性圖靈機(jī)的特例，所以可在多項(xiàng)式時(shí)間內(nèi)被確定性圖靈機(jī)接受的語言也可在多項(xiàng)式時(shí)間內(nèi)被非確定性圖靈機(jī)接受。 要求判定圖 G是否
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1