齣版社： 北京大學齣版社
ISBN：9787301177686
版次：3
商品編碼：10831743
包裝：平裝
叢書名： 高等院校計算機專業及專業基礎課係列教材
開本：16開
齣版時間：2011-08-01
頁數：256
正文語種：中文
具體描述
內容簡介
《可計算性與計算復雜性導引（第3版）》是學習計算理論的教材和參考書，內容包括三部分：可計算性、形式語言與自動機、計算復雜性．主要介紹幾種計算模型及它們的等價性，函數、謂詞和語言的可計算性等基本概念，形式語言及其對應的自動機模型，時間和空間復雜性，np完全性等．《可計算性與計算復雜性導引（第3版）》可作為計算機專業本科生和研究生的教材，也可作為從事計算機科學技術的研究和開發人員的參考書，還可作為對計算理論感興趣的讀者的入門讀物．
目錄
第一章 程序設計語言 和可計算函數1.1 預備知識
1.2 church-turing論題
1.3 程序設計語言
1.4 可計算函數
1.5 宏指令
習題
第二章 原始遞歸函數
2.1 原始遞歸函數
2.2 原始遞歸謂詞
2.3 迭代運算、有界量詞和極小化
2.4 配對函數和godel數
2.5 原始遞歸運算
2.6 ackermann函數
2.7 字函數的可計算性
習題
第三章 通用程序
3.1 程序的代碼
3.2 停機問題
3.3 通用程序
3.4 遞歸可枚舉集
習題
第四章 turing機
4.1 turing機的基本模型
4.2 turing機的各種形式
4.3 turing機與可計算性
4.4 turing機接受的語言
4.5 非確定型turing機
習題
第五章 過程與文法
5.1 半thue過程
5.2 用半thue過程模擬turing機
5.3 文法
5.4 再論遞歸可枚舉集
5.5 部分遞歸函數
5.6 再論church-turing論題
習題
第六章 不可判定的問題
6.1 判定問題
6.2 turing機的停機問題
6.3 字問題和post對應問題
6.4 有關文法的不可判定問題
6.5 一階邏輯中的判定問題
習題
第七章 正則語言
7.1 chomsky譜係
7.2 有窮自動機
7.3 有窮自動機與正則文法的等價性
7.4 正則錶達式
7.5 非正則語言
習題
第八章 上下文無關語言
8.1 上下文無關文法
8.2 chomsky範式
8.3 bar-hillel泵引理
8.4 下推自動機
8.5 上下文無關文法與下推自動機的等價性
8.6 確定型下推自動機
8.7 上下文有關文法
習題
第九章 時間復雜性與空間復雜性
9.1 turing機的運行時間和工作空間
9.2 計算復雜性類
9.3 復雜性類的真包含關係
習題
第十章 np完全性
10.1 p與np
10.2 多項式時間變換和np完全性
10.3 cook定理
10.4 若乾np完全問題
10.5 conp
習題
第十一章 np類的外麵
11.1 pspace完全問題
11.2 一個難解問題
習題
第十二章 p類的裏麵
12.1 若乾例子
12.2 對數空間變換
12.3 nl類
12.4 p完全問題
習題
第十三章 隨機算法與隨機復雜性類
13.1 隨機算法
13.2 隨機復雜性類
習題
習題解答
附錄
附錄a 記號
附錄b 中英文名詞索引
參考文獻
前言/序言
用戶評價
評分
上課用的書，還算不錯，比以前的形式語言與自動機好些。
評分好！
評分東西不錯，很好用。價格便宜。
評分著者隻有一個人，不是七八個人的大拼湊。內容不錯的。
評分上課用的書，還算不錯，比以前的形式語言與自動機好些。
評分快遞快，送貨師傅很好。專業必備書哦。。。
評分紙質一般 而且京東買書嚮來是包裝隨意 總有損傷
評分講解的很詳細，會再慢慢研讀
評分很好很好很好很好很好很好很好很好很好很好很好很好很好很好
相關圖書
![模與環講義 [Lectures on Modules and Rings] pdf epub mobi 電子書 下載](https://pic.qciss.net/11124549/rBEHaFCsqMIIAAAAAACsi-ekTrsAAC5mQAUAeUAAKyj521.jpg)
![研究方法與論文設計/高等學校研究生方法論課程教材 [Ressrarch Methodology and Thesis Design] pdf epub mobi 電子書 下載](https://pic.qciss.net/11304262/5673bccbNdfa6fed9.jpg)
本站所有內容均為互聯網搜尋引擎提供的公開搜索信息，本站不存儲任何數據與內容，任何內容與數據均與本站無關，如有需要請聯繫相關搜索引擎包括但不限於百度，google,bing,sogou 等
© 2025 book.cndgn.com All Rights Reserved. 新城书站 版權所有