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

定　價：￥20.00

作　者：	黃文奇，許如初著
出版社：	科學出版社
叢編項：	數(shù)學機械化叢書
標　簽：	暫缺

購買這本書可以去

ISBN：	9787030126177	出版時間：	2004-06-01	包裝：	精裝
開本：	25cm	頁數(shù)：	87頁	字數(shù)：

內(nèi)容簡介

　　本書對迄今為止有關(guān)計算理論的實質(zhì)性成果作了深刻、嚴格而又直觀的論述，為計算機科學的實質(zhì)性難題NP難度問題的實現(xiàn)求解提出了一條現(xiàn)實的高效的求解途徑。它在透徹講解圖靈機的基礎(chǔ)上，闡明了為什么會有計算機不可解的問題，會有計算機難解的問題；然后為當代實質(zhì)性的計算機難解問題，即NP難度問題指明了得出高性能求解算法的現(xiàn)實途徑——擬物、擬人途徑；最后為設計算法與分析問題的復雜度提供了一個強有力的工具——有窮損害優(yōu)先方法。＜br＞本書的內(nèi)容經(jīng)過不同組合可作為大學生、碩士生、博士生的教材，也可供有關(guān)的科技人員參考。

作者簡介

暫缺《近世計算理論導引：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問題的純粹擬人方法
第五章設計算法與研究計算復雜度的結(jié)構(gòu)的一個工具——有窮損害優(yōu)先方法
1.遞歸論中的幾個基本概念
2.單純集的存在性的構(gòu)造性證明
3.對有窮損害優(yōu)先方法的幾點評注
參考文獻