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

內(nèi)容概要

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

書(shū)籍目錄

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

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

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

---

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

---