近世計算理論導引

書籍作者：黃文奇，許如初 著

圖書出版社：科學出版社

圖書品相：十品

庫 存 量：1 本

圖書類別：綜合類、其他類

圖書標籤：科學出版社 黃文奇許如初 著

上書時間：2011-12-06

出版時間： 2004-06

開本：16開 頁數：104 頁

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

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