語言與機器：計算機科學理論導論

《語言與機器：計算機科學理論導論》是2007年清華大學出版社出版的圖書，作者是蘇達坎。

基本介紹

• 書名：語言與機器：計算機科學理論導論
• 作者：蘇達坎
• ISBN：9787302151722
• 定價：69.00元
• 出版社：清華大學出版社
• 出版時間：2007
• 開本：16

內容簡介

《語言與機器：計算機科學理論導論》介紹了計算機科學的基礎知識，以及各種算法計算的能力和局限性。本書通過大量示例，以一種直觀、易懂的方式闡釋了計算機科學理論的概念及相關數學知識。第3版還擴展介紹了自動機理論、計算理論和計算複雜性等內容。本書可作為計算機及相關專業的計算機科學理論課程的教材。

目錄

出版者的話

專家指導委員會

譯者序

前言

緒論

第一部分 基礎

第1章 數學預備知識

1.1　集合論

1.2　笛卡兒積、關係和函式

1.3　等價關係

1.4　可數集合和不可數集合

1.5　對角化和自反

1.6　遞歸定義

1.7　數學歸納

1.8　有向圖

1.9　練習

參考文獻注釋

第2章 語言

2.1　字元串和語言

2.2　語言的有窮規格說明

2.3　正則集合和表達式

2.4　正則表達式和文本搜尋

2.5　練習

參考文獻注釋

第二部分 文法、自動機和語言

第3章 上下文無關文法

3.1　上下文無關文法和語言

3.2　文法和語言的例子

3.3　正則文法

3.4　驗證文法

3.5　最左推導和二義性

3.6　上下文無關文法和程式語言定義

3.7　練習

參考文獻注釋

第4章 上下文無關文法範式

4.1　文法轉換

4.2　消去入規則

4.3　去掉鏈規則

4.4　無用符

4.5　喬姆斯基範式

4.6　CYK算法

4.7　去掉直接左遞歸

4.8　格立巴赫範式

4.9　練習

參考文獻注釋

第5章 有限自動機

5.1 一個有限狀態自動機

5.2 確定型有限自動機

5.3 狀態圖和例子

5.4 非確定型有限自動機

5.5 λ-轉換

5.6 去掉非確定性

5.7 DFA的最小化

5.8 練習

參考文獻注釋

第6章 正則語言的性質

6.1 有限狀態機接收正則語言

6.2 表達式圖

6.3 正則文法和有限自動機

6.4 正則語言的封閉性質

6.5 非正則語言

6.6 規則語言的泵引理

6.7 Myhill-Nerode定理

6.8 練習

參考文獻注釋

第7章 下推自動機和上下文無關語言

7.1 下推自動機

7.2 PDA的變種

7.3 上下文無關語言的接收

7.4 上下文無關語言的泵引理

7.5 上下文無關語言的封閉性

7.6　練習

參考文獻注釋

第三部分 可計算性

第8章 圖靈機

8.1　標準圖靈機

8.2　作為語言接收器的圖靈機

8.3　可供選擇接收標準

8.4　多道圖靈機

8.5　雙向圖靈機

8.6　多帶圖靈機

8.7　非確定型圖靈機

8.8　用來枚舉語言的圖靈機

8.9　練習

參考文獻注釋

第9章 圖靈可計算函式

9.1　函式的計算

9.2　數值計算

9.3　圖靈機的順序操作

9.4　函式的合成

9.5　不可計算函式

9.6　關於程式語言

9.7　練習

參考文獻注釋

第10章 喬姆斯基層次

10.1　無限制文法

10.2　上下文有關文法

10.3　線性有界自動機

10.4　喬姆斯基層次

10.5　練習

參考文獻注釋

第11章 判定問題與丘奇—圖靈論題

11.1　判定問題的描述

11.2　判定問題和遞歸語言

11.3　問題歸約

11.4　丘奇—圖靈論題

11.5　通用機

11.6　練習

參考文獻注釋

第12章 不可判定性

12.1　圖靈機的停機問題

12.2　問題歸約和不可判定性

12.3　其他的停機問題

12.4　萊斯定理

12.5　不可解決的詞問題

12.6　波斯特對應問題

12.7　上下文無關文法中的不可判定問題

12.8　練習

參考文獻注釋

第13章 Mu-遞歸函式

13.1　原始遞歸函式

13.2　一些原始遞歸函式

13.3　有界操作符

13.4　除法函式

13.5　歌德爾數字和串值遞歸

13.6　可計算部分函式

13.7 圖靈可計算函式和Mu-遞歸函式

13.8　修訂的丘奇—圖靈論題

13.9　練習

參考文獻注釋

第四部分　計算複雜性

第14章 時間複雜性

14.1　複雜性度量

14.2　增長的速度

14.3　圖靈機的時間複雜性

14.4　複雜性和圖靈機的變種

14.5　線性加速

14.6　語言時間複雜性的屬性

14.7　計算機計算的模擬

14.8　練習

參考文獻注釋

第15章 P、NP和庫克定理

15.1 非確定型圖靈機的時間複雜性

15.2　P類和NP類

15.3　問題表示和複雜性

15.4　判定問題和複雜性類

15.5　哈密爾頓迴路問題

15.6　多項式時間歸約

15.7 P=NP？

15.8 可滿足性問題

15.9 複雜類的關係

15.10　練習

參考文獻注釋

第16章 NP-完全問題

16.1　歸約和NP-完全問題

16.2　三元可滿足性問題

16.3　三元可滿足性的歸約

16.4　歸約和子問題

16.5　最最佳化問題

16.6　近似算法

16.7　近似方案

16.8　練習

參考文獻注釋

第17章 其他複雜性類

17.1 派生的複雜性類

17.2 空間複雜性

17.3 空間複雜性和時間複雜性的關係

17.4 P-空間，NP-空間和薩維奇定理

17.5 P-空間完全性

17.6 一個難解問題

17.7 練習

參考文獻注釋

第五部分　確定型語法分析

第18章　語法分析引論

18.1 文法圖

18.2　自頂向下語法分析

18.3　歸約和自底向上語法分析

18.4　自底向上語法分析器

18.5　語法分析和編譯

18.6　練習

參考文獻注釋

第19章　LL(k)文法

19.1 上下文無關文法中的預讀

19.2 FIRST集合、FOLLOW集合和預讀集合

19.3 強LL(k)語法

19.4 FIRSTk集合的構造

19.5 FOLLOWk集合的構造

19.6 強LL(1)文法

19.7 強LL(k)分析器

19.8 LL(k)文法

19.9 練習

參考文獻注釋

第20章 LR(k)文法

20.1 LR(0)上下文

20.2 LR(0)分析器

20.3 LR(0)機

20.4 被LR(0)機接收

20.5 LR(1)文法

20.6 練習

參考文獻注釋

附錄

附錄Ⅰ 標記索引

附錄Ⅱ 希臘字母表

附錄Ⅲ ASC Ⅱ字元集

附錄Ⅲ Java的BNF範式定義

參考文獻

索引