可計算性和計算復(fù)雜性

內(nèi)容概要

本書深入淺出地介紹了研究可計算性的四個主要模型以及四個模型彼此之間的關(guān)系：介紹了計算復(fù)雜性的基本概念和重要的研究方法與一些研究成果。內(nèi)容涉及遞歸函數(shù)、圖靈機、λ演算、馬爾可夫算法、計算復(fù)雜度的分類、NP完全理論、非一致復(fù)雜性等。分述于十章,書中附有習(xí)題。    本書可作為廣大有志于突破計算復(fù)雜性研究僵局——“P=NP？”的科技工作者,計算機科學(xué)和元計算機科學(xué)工作者,數(shù)學(xué)和元數(shù)學(xué)工作者以及大專院校的教師和學(xué)生的入門書、教材和參考書,亦可作為計算機基礎(chǔ)理論的參考書。

書籍目錄

第一章 概論  第一節(jié) 相關(guān)定義  第二節(jié) 可計算性  第三節(jié) 計算復(fù)雜性  第四節(jié) 對可計算性定義的質(zhì)疑  練習(xí)題第二章 一般遞歸函數(shù)  第一節(jié) 初始函數(shù)  第二節(jié) 合成法生成新函數(shù)  第三節(jié) 算子法構(gòu)造函數(shù)  練習(xí)題第三章 圖靈機  第一節(jié) 圖靈機的基本模型  第二節(jié) 圖靈機基本模型的功能  第三節(jié) 圖靈機基本模型的修改  第四節(jié) 圖靈機和判定問題  第五節(jié) 圖靈機和遞歸函數(shù)  練習(xí)題第四章 r演算  第一節(jié) r演算的語法  第二節(jié) 三個重要的組合算子  第三節(jié) r演算系統(tǒng)的擴充  第四節(jié) 組約  第五節(jié) 其他重要的組合算子  第六節(jié) r可定義的函數(shù)和歸函數(shù)  練習(xí)題第五章 馬爾可夫算法  第一節(jié) 演算和算法  第二節(jié) 馬爾可夫算法  第三節(jié) 圖靈可計算的函數(shù)  第四節(jié) 圖靈機和巴爾可夫算法  第五節(jié) 馬爾可夫算法和遞歸函數(shù)  練習(xí)題 馬爾可夫算法和遞歸函數(shù)第六章 計算復(fù)雜性  第一節(jié) 函數(shù)的計算雜性  第二節(jié) 圖靈機的計算復(fù)雜性  第三節(jié) 可構(gòu)造的函數(shù)  練習(xí)題第七章 計算復(fù)雜性的分類  第一節(jié) 時間復(fù)雜類和空間復(fù)雜類  第二節(jié) 三個NP問題  練習(xí)題第八章  NP完全理論  第一節(jié) 多項式可計算的函數(shù)  第二節(jié) 多項式時間的多一化歸和NP完全集  第三節(jié) 多項式同構(gòu)和P≠NP  第四節(jié) 稀疏的NP完全集和N=NP  第五節(jié) 多項式時間圖靈化歸和NP=co-NP  練習(xí)題第九章 非一致復(fù)雜性  第一節(jié) 布爾代數(shù)和布爾線路  第二節(jié) 布爾線路和圖靈機  第三節(jié) 多項式超前函數(shù)  第四節(jié) 布爾單行函數(shù)  練習(xí)題第十章 謂詞的可計算性  第一節(jié) 一階語言L的語法和語義  第二節(jié) 一階謂詞演算系統(tǒng)K  第三節(jié) 數(shù)論謂詞的判定性  第四節(jié) 摹狀詞和摹狀算子參考文獻

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    可計算性和計算復(fù)雜性 PDF格式下載

---