近世計算理論導引：NP難度問題的背景、前景及其求解算法研究

第一章計算的數(shù)學模型——Turing機
1.Turing機的定義及其直觀形象
2.Turing機所計算的函數(shù)和所接受的語言,計算復雜度
3.Church-Turing論題
4.Turing機的編碼
第二章不可計算性
1.勝弈機之不存在性
2.不可計算函數(shù)的存在性
3.停機問題的不可解性
4.Turing機停機問題之Turing機不可解性
5.Godel不完備性定理
第三章NP完全理論
1.增長速度
2.P和NP
3.Cook定理
4.另外幾個NP完全問題
第四章現(xiàn)實生活中的NP難度問題及其現(xiàn)實處理方法——處理NP難度問題的擬物擬人途徑
1.求解Packing問題的擬物方法
2.求解覆蓋(Covering)問題的擬物方法
3.求解SAT問題的擬物方法
4.求解不等圓Packing問題的擬物擬人方法
5.求解SAT問題的擬物擬人方法
6.求解不等圓Packing問題的純粹擬人方法
第五章設計算法與研究計算復雜度的結構的一個工具——有窮損害優(yōu)先方法
1.遞歸論中的幾個基本概念
2.單純集的存在性的構造性證明
3.對有窮損害優(yōu)先方法的幾點評注
參考文獻