近世計(jì)算理論導(dǎo)引：NP難度問題的背景、前景及其求解算法研究

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