可計算性和計算復雜性

第一章 概論
第一節(jié) 相關定義
第二節(jié) 可計算性
第三節(jié) 計算復雜性
第四節(jié) 對可計算性定義的質疑
練習題
第二章 一般遞歸函數
第一節(jié) 初始函數
第二節(jié) 合成法生成新函數
第三節(jié) 算子法構造函數
練習題
第三章 圖靈機
第一節(jié) 圖靈機的基本模型
第二節(jié) 圖靈機基本模型的功能
第三節(jié) 圖靈機基本模型的修改
第四節(jié) 圖靈機和判定問題
第五節(jié) 圖靈機和遞歸函數
練習題
第四章 r演算
第一節(jié) r演算的語法
第二節(jié) 三個重要的組合算子
第三節(jié) r演算系統的擴充
第四節(jié) 組約
第五節(jié) 其他重要的組合算子
第六節(jié) r可定義的函數和歸函數
練習題
第五章 馬爾可夫算法
第一節(jié) 演算和算法
第二節(jié) 馬爾可夫算法
第三節(jié) 圖靈可計算的函數
第四節(jié) 圖靈機和巴爾可夫算法
第五節(jié) 馬爾可夫算法和遞歸函數
練習題 馬爾可夫算法和遞歸函數
第六章 計算復雜性
第一節(jié) 函數的計算雜性
第二節(jié) 圖靈機的計算復雜性
第三節(jié) 可構造的函數
練習題
第七章 計算復雜性的分類
第一節(jié) 時間復雜類和空間復雜類
第二節(jié) 三個NP問題
練習題
第八章 NP完全理論
第一節(jié) 多項式可計算的函數
第二節(jié) 多項式時間的多一化歸和NP完全集
第三節(jié) 多項式同構和P≠NP
第四節(jié) 稀疏的NP完全集和N=NP
第五節(jié) 多項式時間圖靈化歸和NP=co-NP
練習題
第九章 非一致復雜性
第一節(jié) 布爾代數和布爾線路
第二節(jié) 布爾線路和圖靈機
第三節(jié) 多項式超前函數
第四節(jié) 布爾單行函數
練習題
第十章 謂詞的可計算性
第一節(jié) 一階語言L的語法和語義
第二節(jié) 一階謂詞演算系統K
第三節(jié) 數論謂詞的判定性
第四節(jié) 摹狀詞和摹狀算子
參考文獻