《np完整性理論》ppt課件-文庫吧
2025-04-20 18:18 本頁面
【正文】 tions) 若在直線式程序計算模型中，假設所有變量均為位向量，而 且所用的運算均為位操作指令，則得到位向量運算計算模型。 例如，要表示一個有 100個頂點的圖中從頂點 v到其余各頂點 間有沒有邊相連，可以用 100位的一個位向量表示。若頂點 v到頂 點 vj之間有邊相連，則該位向量的第 j位為 1，否則為 0。 缺點： 所需的機器字長要遠大于其他模型。 11 RAM模型的變形與簡化 5. 判定樹 判定樹是一棵二叉樹。它的每個內(nèi)結(jié)點表示一個形如 x∶y 的 比較。指向該結(jié)點左兒子的邊相應于 x≤y ， 標號為 ≤ 。指向該結(jié) 點右兒子的邊相應于 xy， 標號為 。每一次比較耗費一個單位時 間。下圖是對 a， b， c三個數(shù)進行排序的一棵判定樹。 在判定樹模型下，算法的時間復雜性可用判定樹的高度衡量。最大的比較次數(shù)是從根到葉的最長路徑的長度。 12 RAM模型的變形與簡化 6. 代數(shù)計算樹 ACT 以 x=(x1， x2， … ， xn)為輸入的一棵代數(shù)計算樹 T是一棵 二叉樹，且： (1)每個葉結(jié)點表示一個輸出結(jié)果 YES或 NO。 (2)每個單兒子內(nèi)部結(jié)點 (簡單結(jié)點 )v表示下列形式運算指令： op 或 op 或 其中， 和 分別是結(jié)點 v在樹 T中的祖先結(jié)點 v1和 v2處得到 的結(jié)果值，或是 x的分量； op∈{+ ，－， /}； c是一個常數(shù)。 (3)每個有 2個兒子的內(nèi)部結(jié)點 (分支結(jié)點 )v， 表示下列形式的 測試指令： 0或 ≥0 或 =0 其中， 是結(jié)點 v在樹 T中的祖先結(jié)點 v1處得到的結(jié)果值，或是 x的分量。 1vv ff ? 2vf cfv ? 1vf 1vv ff ?1vf 2vf1vf 1vf 1vf1vf13 RAM模型的變形與簡化 7. 代數(shù)判定樹 ADT(Algebraic Decision Tree) 在代數(shù)計算樹 T中，若將所有的簡單結(jié)點都壓縮到其最近 的子孫分支結(jié)點處，并將簡單結(jié)點處的計算在壓縮后的分支結(jié)點 處同時完成，則計算結(jié)果可看作是輸入 x的一個代數(shù)函數(shù) fv(x)。 由此引出另一個稱為代數(shù)判定樹的計算模型。 代數(shù)判定樹 T是一棵二叉樹，且 (1)每個葉結(jié)點表示輸出結(jié)果 YES或 NO。 (2)每個內(nèi)部結(jié)點 v表示一個形如 fv(x1， x2， … ， xn)∶0 的 比較。其中， x=( x1， x2， … ， xn)是輸入， fv是一個代數(shù) 函數(shù)。 14 圖靈機 1. 多帶圖靈機 15 圖靈機 1. 多帶圖靈機 根據(jù)有限狀態(tài)控制器的當前狀態(tài)及每個讀寫頭讀到的帶符號， 圖靈機的一個計算步可實現(xiàn)下面 3個操作之一或全部。 (1)改變有限狀態(tài)控制器中的狀態(tài)。 (2)清除當前讀寫頭下的方格中原有帶符號并寫上新的帶符號。 (3)獨立地將任何一個或所有讀寫頭，向左移動一個方格 (L)或向右移動一個方格 (R)或停在當前單元不動 (S)。 k帶圖靈機可形式化地描述為一個 7元組 (Q， T， I， δ ， b， q0，qf)， 其中 : (1)Q是有限個狀態(tài)的集合。 (2)T是有限個帶符號的集合。 (3)I是輸入符號的集合 ， I?T。 (4)b是惟一的空白符 ， b∈T I。 (5)q0是初始狀態(tài) 。 (6)qf是終止 (或接受 )狀態(tài) 。 (7)δ 是移動函數(shù)。它是從 Q?Tk的某一子集映射到 Q? (T?{L， R，S})k的函數(shù)。 16 圖靈機 1. 多帶圖靈機 圖靈機 M的時間復雜性 T(n)是它處理所有長度為 n的輸入所需的最大計算步數(shù)。如果對某個長度為 n的輸入，圖靈機不停機，T(n)對這個 n值無定義。 圖靈機的空間復雜性 S(n)是它處理所有長度為 n的輸入時，在 k條帶上所使用過的方格數(shù)的總和。如果某個讀寫頭無限地向右移動而不停機， S(n)也無定義。 與 RAM模型類似，圖靈機既可作為語言接受器，也可作為計算函數(shù)的裝置。 17 圖靈機模型與 RAM模型的關(guān)系 圖靈機模型與 RAM模型的關(guān)系是指同一問題在這 2種不同計算模型下的復雜性之間的關(guān)系。 定理 83 對于問題 P的任何長度為 n的輸入，設求解問題 P的算法 A在 k帶圖靈機模型 TM下的時間復雜性為 ，那么，算法 A在 RAM模型下的時間復雜性為 。 )(nT))(( 2
教學課件相關(guān)推薦
鄂ICP備17016276號-1