np完整性理論ppt課件-在線瀏覽
2025-06-22 18:18本頁面
【正文】 ∧ 代表與， ∨ 代表或， ?代表異或， ?代表非。 10 RAM模型的變形與簡化 4. 位向量運算 (Bit Vector Operations) 若在直線式程序計算模型中，假設(shè)所有變量均為位向量，而 且所用的運算均為位操作指令，則得到位向量運算計算模型。若頂點 v到頂 點 vj之間有邊相連，則該位向量的第 j位為 1，否則為 0。 11 RAM模型的變形與簡化 5. 判定樹 判定樹是一棵二叉樹。指向該結(jié)點左兒子的邊相應(yīng)于 x≤y ， 標(biāo)號為 ≤ 。每一次比較耗費一個單位時 間。 在判定樹模型下，算法的時間復(fù)雜性可用判定樹的高度衡量。 12 RAM模型的變形與簡化 6. 代數(shù)計算樹 ACT 以 x=(x1， x2， … ， xn)為輸入的一棵代數(shù)計算樹 T是一棵 二叉樹，且： (1)每個葉結(jié)點表示一個輸出結(jié)果 YES或 NO。 (3)每個有 2個兒子的內(nèi)部結(jié)點 (分支結(jié)點 )v， 表示下列形式的 測試指令： 0或 ≥0 或 =0 其中， 是結(jié)點 v在樹 T中的祖先結(jié)點 v1處得到的結(jié)果值，或是 x的分量。 由此引出另一個稱為代數(shù)判定樹的計算模型。 (2)每個內(nèi)部結(jié)點 v表示一個形如 fv(x1， x2， … ， xn)∶0 的 比較。 14 圖靈機 1. 多帶圖靈機 15 圖靈機 1. 多帶圖靈機 根據(jù)有限狀態(tài)控制器的當(dāng)前狀態(tài)及每個讀寫頭讀到的帶符號， 圖靈機的一個計算步可實現(xiàn)下面 3個操作之一或全部。 (2)清除當(dāng)前讀寫頭下的方格中原有帶符號并寫上新的帶符號。 k帶圖靈機可形式化地描述為一個 7元組 (Q， T， I， δ ， b， q0，qf)， 其中 : (1)Q是有限個狀態(tài)的集合。 (3)I是輸入符號的集合 ， I?T。 (5)q0是初始狀態(tài) 。 (7)δ 是移動函數(shù)。 16 圖靈機 1. 多帶圖靈機 圖靈機 M的時間復(fù)雜性 T(n)是它處理所有長度為 n的輸入所需的最大計算步數(shù)。 圖靈機的空間復(fù)雜性 S(n)是它處理所有長度為 n的輸入時，在 k條帶上所使用過的方格數(shù)的總和。 與 RAM模型類似，圖靈機既可作為語言接受器，也可作為計算函數(shù)的裝置。 定理 83 對于問題 P的任何長度為 n的輸入，設(shè)求解問題 P的算法 A在 k帶圖靈機模型 TM下的時間復(fù)雜性為 ，那么，算法 A在 RAM模型下的時間復(fù)雜性為 。 )(nT))(( 2 nTO18 問題變換與計算復(fù)雜性歸約 具體地說 ， 假設(shè)有 2個問題 A和 B， 將 問題 A變換為問題 B是指： (1)將問題 A的輸入變換為問題 B的適當(dāng)輸入 。 (3)把問題 B的輸出變換為問題 A的正確解 。 其中的 n通常為問題 A的規(guī)模 (大小 )。特別地，當(dāng) τ(n) 為 n的線性函數(shù)時，稱問題 A可線性地變換為問題 B。這樣就可以將一個問題的計算復(fù)雜性歸結(jié)為另一個問題的計算復(fù)雜性，從而實現(xiàn)問題的計算復(fù)雜性歸約。 命題 2(計算時間上界歸約 )：若已知問題 B的計算時間上界為 T(n)， 且問題 A是 τ(n) 可變換到問題 B， 即 A∝ τ(n) B， 則T(n)+O(τ(n)) 是問題 A的一個計算時間上界。 20 問題變換與計算復(fù)雜性歸約 通過問題變換獲得問題的計算時間下界的例子 ： (1)判別函數(shù)問題：給定 n個實數(shù) ，計算其判別函數(shù) 。任何一個計算判別函數(shù)的算法，計算出判別函數(shù)值后，再作一次測試，判斷其值是否為 0，即可得到元素惟一性問題的解。 )log( nn? (2)最接近點對問題：給定平面上 n個點，找出這 n個點中距離最近的 2個點。 ixix21 P類與 NP類問題 ? 非確定性圖靈機 ? P類與 NP類語言 ? 多項式時間驗證 22 非確定性圖靈機 非確定性圖靈機（ NDTM ） ：一個 k帶的非確定性圖靈機 M是一個 7元組： (Q， T， I， δ ， b， q0， qf)。x1,x2,… ,xk)， 當(dāng)它屬于 δ 的定義域時， Q?(T?{L，R， S})k中有惟一的一個 子集 δ(q?？梢栽讦?q。 在圖靈機計算模型中，移動函數(shù) δ 是單值的 ，即對于 Q?Tk中的每一個值，當(dāng)它屬于 δ 的定義域時， Q?(T?{L， R， S})k中只有惟一的值與之對應(yīng)，稱這種
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1