近世計(jì)算理論導(dǎo)引

內(nèi)容概要

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

書籍目錄

第一章 計(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.Gōdel不完備性定理第三章 NP完全理論  1.增長速度  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)

編輯推薦

《近世計(jì)算理論導(dǎo)引:NP難度問題的背景、前景及其求解算法研究》由科學(xué)出版社出版。

圖書封面

圖書標(biāo)簽Tags

無

評(píng)論、評(píng)分、閱讀與下載

---

    近世計(jì)算理論導(dǎo)引 PDF格式下載

---