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

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