11-編程的靈魂——數(shù)據(jù)結(jié)構(gòu)算法=程序-資料下載頁(yè)
2025-08-04 07:28本頁(yè)面
【正文】 一類問(wèn)題很可能屬于 NPP，滿足 –屬于 NP – NP中的每個(gè)問(wèn)題可以多項(xiàng)式歸約到它 ? 這類問(wèn)題稱為 NP完全問(wèn)題 (NPC)，如果某個(gè) NP完全問(wèn)題找到多項(xiàng)式算法，那么所有NP問(wèn)題都可以用多項(xiàng)式時(shí)間解決 ? NP難度問(wèn)題：滿足②卻不滿足① NP完全性 ? 證明 NP完全性的技巧：歸約 – x屬于 A iff f(x)屬于 B，則 A多對(duì)一歸約到 B –若 f是多項(xiàng)式可計(jì)算的，則為多項(xiàng)式時(shí)間多對(duì)一歸約 ? 第一個(gè)自然的 NP完全問(wèn)題： SAT問(wèn)題 – (Cook, 1970)SAT是 NP完全問(wèn)題 –推論： 3SAT是 NP完全問(wèn)題 ? 在實(shí)用中，一般取布爾公式的簡(jiǎn)單形式，如合取范式（ CNF），即初等和的乘積 △ 復(fù)雜度類 ? DTM和 NTM上的常數(shù)消除：帶壓縮定理（時(shí)間）、線性加速定理（空間） ? 重要的復(fù)雜度類： – P = DTIME(poly) – NP = NTIME(poly) – PSPACE = DSPACE(poly) – NPSPACE = NSPACE(poly) ? 顯然 NPC是 PS的子集 . ? Savitch定理： PS=NPS △ 復(fù)雜度類 ? 函數(shù)可計(jì)算性： FP、 FPSPACE ? 其他復(fù)雜度類 – LOGSPACE = DSPACE(logn) – NLOGSPACE = NSPACE(logn) – EXP、 NEXP、 EXPSPACE ? 模型無(wú)關(guān)： F, FP, PSPACE ? 模型相關(guān)： DTIME(n2)、 DSPACE(n) △ 可計(jì)算性 ? ChurchTuring命題：如果一個(gè)函數(shù)在某個(gè)合理的計(jì)算模型上可計(jì)算，那么它在圖靈機(jī)上也是可計(jì)算的 ? 什么是合理的計(jì)算模型？無(wú)準(zhǔn)確定義，但一般需要至少滿足： –計(jì)算一個(gè)函數(shù)只要有限條指令； –每條指令可由模型中的有限個(gè)計(jì)算步驟完成； –執(zhí)行指令的過(guò)程是確定型的 △ 可計(jì)算性 ? 所有可計(jì)算函數(shù)組成之族是 可數(shù)的 。顯然存在 不可計(jì)算 的函數(shù)。例：停機(jī)問(wèn)題 ? 廣義 ChurchTuring命題：如果一個(gè)函數(shù)在某個(gè)合理的計(jì)算模型上使用合理時(shí)間復(fù)雜性度量是多項(xiàng)式時(shí)間可計(jì)算的，那么它在圖靈機(jī)上也是多項(xiàng)式時(shí)間可計(jì)算的 ? 挑戰(zhàn)：量子 TM上找到了整數(shù)因子分解問(wèn)題的多項(xiàng)式時(shí)間解 其他概念 ? 計(jì)數(shù)復(fù)雜性： P完全問(wèn)題 ? 概率： RP（只允許單邊失誤）和 ZPP（期望多項(xiàng)式時(shí)間） .定理： ZPP = RP∩coRP ? 近似算法 –多項(xiàng)式時(shí)間近似方案 (PTAS)：近似比 r = 1 + 1/k，存在算法 Ak， k常數(shù)時(shí)為多項(xiàng)式算法 –完滿多項(xiàng)式時(shí)間近似方案 (FPTAS)： Ak的運(yùn)算時(shí)間同時(shí)也是 k的多項(xiàng)式函數(shù) . 例：背包問(wèn)題中，設(shè) M為最大價(jià)值，做價(jià)值替換 ui=[vin(k+1)/M]，近似比 1+1/(k1) 小結(jié) ? RAM模型 ? 非確定機(jī)、 NP完全問(wèn)題、 3SAT的 NP完全性、多項(xiàng)式時(shí)間多對(duì)一歸約 ? 計(jì)數(shù)復(fù)雜性，概率復(fù)雜性和近似復(fù)雜性 八、總結(jié) 一、緒論 ? 問(wèn)題、實(shí)例、算法 ? 輸入、輸出與算法步驟（偽代碼 /代碼） ? 算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系 ? 算法改進(jìn)與硬件投資的比較；核心算法在項(xiàng)目中的作用 二、算法的實(shí)現(xiàn)與比較 ? 算法的重用性 ? 基本算法的實(shí)現(xiàn)：微調(diào)、新計(jì)算環(huán)境 ? 簡(jiǎn)潔性、教育性與效率的權(quán)衡 ? 真實(shí)實(shí)現(xiàn)：過(guò)度優(yōu)化、錯(cuò)誤處理、維護(hù)性的考慮 ? 算法分析和實(shí)驗(yàn)比較的側(cè)重點(diǎn) ? 實(shí)驗(yàn)比較時(shí)的代碼編寫(xiě) ? 測(cè)試數(shù)據(jù)的設(shè)計(jì) ? 待定參數(shù)的調(diào)節(jié) 三、算法分析 ? 三個(gè)任務(wù)（比較、預(yù)測(cè)、設(shè)置參數(shù)）、挑戰(zhàn)、基礎(chǔ)（理想模型） ? 時(shí)間分析的對(duì)象：起決定因素部分的基本操作數(shù)量的合理近似 ? 輸入建模：隨機(jī)數(shù)據(jù)、針對(duì)性數(shù)據(jù) 四、函數(shù)增長(zhǎng)和記號(hào) ? 主要參數(shù) n，操作數(shù)函數(shù) f(n) ? 增長(zhǎng)的含義、最高項(xiàng) ? 常見(jiàn)的函數(shù)增長(zhǎng)和運(yùn)行時(shí)間 ? 常見(jiàn)函數(shù)的近似 ? 復(fù)雜度常用記號(hào)，上限和下限 五、遞歸式的遞歸樹(shù)分析 ? 遞歸方程 T(n) = aT(n/b) + f(n) ? 遞歸樹(shù)得到的結(jié)果： – T(n) = f(n)+af(n/b)+a2f(n/b2)+…+ aLf(n/bL) –其中 L=logbn ? T(n) = 2T(n/2) + n，則 T(n)=O(nlogn) 六、算法設(shè)計(jì)與分析實(shí)例 ? 最大連續(xù)序列問(wèn)題 – 算法一：完全枚舉 O(n3) – 算法二：利用前綴和優(yōu)化枚舉 O(n2) – 算法三：分治 O(nlogn) – 算法四：掃描 O(n) ? 思考題：最大連續(xù)子矩陣問(wèn)題 – 給一個(gè)矩陣，每個(gè)元素 aij為整數(shù) – 尋找一個(gè)子矩陣 (i,j)(k,l)，使得子矩陣內(nèi)數(shù)和最小 – 提示：利用算法四設(shè)計(jì) O(n3)算法 七、計(jì)算模型與難解問(wèn)題 ? RAM模型：順序執(zhí)行指令，隨機(jī)存取，基本操作需要常數(shù)時(shí)間 . 未考慮字長(zhǎng)、層次存儲(chǔ)器等問(wèn)題 ? 并行計(jì)算機(jī)和非確定機(jī) ? P類問(wèn)題、 NP類問(wèn)題、 NP完全問(wèn)題 ? 3SAT問(wèn)題的 NP完全性，多項(xiàng)式時(shí)間多對(duì)一歸約 ? P完全問(wèn)題、 RP、 ZPP問(wèn)題、 PTAS和FPTAS 結(jié)束
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1