可計算性和計算復(fù)雜性

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