可計(jì)算性與計(jì)算復(fù)雜性導(dǎo)引

定　價：￥15.00

作　者：	張立昂編著
出版社：	北京大學(xué)出版社
叢編項(xiàng)：	高等教育計(jì)算機(jī)專業(yè)教材
標(biāo)　簽：	電子計(jì)算機(jī)

購買這本書可以去

當(dāng)當(dāng)網(wǎng) (￥12.00)

ISBN：	9787301032299	出版時間：	1996-10-01	包裝：	膠版紙
開本：	20cm	頁數(shù)：	299頁	字?jǐn)?shù)：

內(nèi)容簡介

　　本書是學(xué)習(xí)理論計(jì)算機(jī)科學(xué)基礎(chǔ)的教材和參考書，內(nèi)容包括三部分：可計(jì)算性、形式語言與自動機(jī)、計(jì)算復(fù)雜性。主要介紹幾種計(jì)算模型及它們的等價性，函數(shù)、謂詞和語言的可計(jì)算性等基本概念，形式語言及其對應(yīng)的自動機(jī)模型，時間和空間復(fù)雜性，NP完全性等。本書可作為計(jì)算機(jī)專業(yè)本科生和研究生的教材，也可作為從事計(jì)算機(jī)科學(xué)技術(shù)的研究和開發(fā)人員的參考書，還可作為對理論計(jì)算機(jī)科學(xué)感興趣的讀者的入門教材。

作者簡介

暫缺《可計(jì)算性與計(jì)算復(fù)雜性導(dǎo)引》作者簡介

圖書目錄

第一章  程序設(shè)計(jì)語言和可計(jì)算函數(shù)
  1.1 預(yù)備知識
  1.2 程序設(shè)計(jì)語言
  1.3 可計(jì)算函數(shù)
  1.4 宏指令
  習(xí)題
第二章  原始遞歸函數(shù)
  2.1 原始遞歸函數(shù)
  2.2 原始遞歸謂詞
  2.3 迭代運(yùn)算、有界量詞和極小化
  2.4 配對函數(shù)和Godel數(shù)
  2.5 原始遞歸運(yùn)算
  2.6 Ackermann函數(shù)
  習(xí)題
第三章  通用程序
  3.1 程序的代碼
  3.2 停機(jī)問題
  3.3 通用程序
  3.4 參數(shù)定理
  3.5 遞歸定理
  習(xí)題
第四章  字符串計(jì)算
  4.1 字符串的數(shù)字表示
  4.2 程序設(shè)計(jì)語言
  4.3 Post-Turing語言
  4.4 用模擬
  4.5 用模擬
  習(xí)題
第五章  遞歸可枚舉集
  5.1 遞歸集和遞歸可枚舉集
  5.2 遞歸語言和遞歸枚舉語言
  5.3 非遞歸集和非遞歸可枚舉集
  習(xí)題
第六章  Turing機(jī)
  6.1 Turing機(jī)的基本模型
  6.2 Turing機(jī)與可計(jì)算性
  6.3 Turing機(jī)接受的語言
  6.4 Turing機(jī)的各種形式
  6.5 非確定型Turing機(jī)
  習(xí)題
第七章  過程與文法
  7.1 半Thue過程
  7.2 用半Thue過程模擬Turing機(jī)
  7.3 文法
  7.4 再論遞歸可枚舉集
  7.5 部分遞歸函數(shù)
  7.6 Church-Turing論題
  習(xí)題
第八章  不可判定的問題
  8.1 判定問題
  8.2 Turing機(jī)的停機(jī)問題
  8.3 字問題和Post對應(yīng)問題
  8.4 有關(guān)文法的不可判定問題
  8.5 一階邏輯中的判定問題
  習(xí)題
第九章  正則語言
第十章  上下文無關(guān)語言
第十一章  上下文有關(guān)語言
第十二章  計(jì)算復(fù)雜性
第十三章  NP完全性
第十四章  組合優(yōu)化問題的近似計(jì)算
附錄
參考文獻(xiàn)