中圖網小程序
一鍵登錄
更方便
本類五星書更多>
-
>
全國計算機等級考試最新真考題庫模擬考場及詳解·二級MSOffice高級應用
-
>
決戰行測5000題(言語理解與表達)
-
>
軟件性能測試.分析與調優實踐之路
-
>
第一行代碼Android
-
>
JAVA持續交付
-
>
EXCEL最強教科書(完全版)(全彩印刷)
-
>
深度學習
語言與機器-計算機科學理論導論(原書第3版) 版權信息
- ISBN：9787111226345
- 條形碼：9787111226345 ; 978-7-111-22634-5
- 裝幀：暫無
- 冊數：暫無
- 重量：暫無
- 所屬分類：>
語言與機器-計算機科學理論導論(原書第3版) 內容簡介
本書是計算理論方面的優秀教材之一，包括上下文無關文法、上下文無關文法范式、有限自動機、正則語言的性質、下推自動機和上下文無關語言、圖靈機、圖靈可計算函數、喬姆斯基層次、判定問題與丘奇圖靈機、不可判定性、Mu-遞歸函數、時間復雜性、庫克定理、NP-完全問題、LL(k)文法以及LR(k)文法等問題。本書不僅介紹了計算機科學的基礎，而且通過概念的嚴格表述，以及使用通俗的例子來闡釋定理，從而幫助學生提高數學論證能力以及對計算理論知識的全面深入的理解。書中每章后面都有附有大量習題，通過完成這些習題，學生可以加深對本章內容的理解。
本書可以用作計算機科學、計算機工程及其相關專業的教材，也可以作為從事計算理論、形式語言以及計算機系統研發的研究人員和工程技術人員的參考書。
語言與機器-計算機科學理論導論(原書第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范式定義
參考文獻
索引
專家指導委員會
譯者序
前言
緒論
**部分 基礎
第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范式定義
參考文獻
索引
展開全部
語言與機器-計算機科學理論導論(原書第3版) 節選
第1章 數學預備知識
集合論和離散數學為形式語言理論、可計算性理論和計算復雜性分析提供了數學基礎。我們首先回顧集合論的表示和基本操作。集合的基數度量集合的大小，并提供無窮集合大小的準確定義。德國數學家George Cantor深入研究集合的屬性后得出一條有趣的結論，就是存在不同大小的無窮集。盡管Cantor的工作僅僅表明存在一個完整的無窮集合規模層次，但是這已經足夠支持我們把無窮集合分成兩類的目的了。這兩類分別是可數的和不可數的。如果集合的元素數目與自然數一樣多，那么這個集合是可數的無窮集。如果元素數目比自然數多，就是不可數無窮集。 ．
在本章中，我們將使用對角化論證(diagonalization argument)結構來證明定義在自然數集合上的函數集合是不可數無窮集。我們在有效過程(effective procedure)和可計算函數(computable func—tion)的意義上達成共識后(這也是本書第三部分的主要目的)，將能夠確定可以用算法計算的函數集合的大小。通過比較這兩個集合的大小，就可以證明存在這樣的函數，它們的值不能使用任何算法過程計算得到。
一個集合可能由任意一組對象組成，我們對那些機械化生成元素的集合感興趣。然后，我們介紹可以產生集合元素的遞歸定義；接著構造遞歸生成的集合與數學歸納法之間的關系。歸納已經被證明能夠為遞歸產生的無窮集合中的元素性質提供一個通用的證明技巧。
在本章的*后，我們將復習有向圖和樹等知識，這是貫穿本書的兩種結構，并以圖形方式的解釋了形式語言理論和計算理論的概念。
……
語言與機器-計算機科學理論導論(原書第3版) 作者簡介
Thomas A．Sudkamp是美國萊特州立大學計算機科學及工程系的教授，他的研究領域
廣泛，包括近似推理、人工智能、數理邏輯、建模軟計算的應用、復雜問題領域的決策制定以及不確定、不精確信息和知識發掘的機器學習。Sudkamp教授目前還擔任IEEE Transactions on System，Man，and Cybemetics和IEEE Transactions on Fuzzy Systems的副編輯，International Journal of Approximate Reasonin9和Fuzzy Sets and Systems的領域編輯。他也曾經擔任過北美模糊信息處理協會NAFIPS)的主席以及國際模糊系統聯盟(IFSA)的副主席。
書友推薦
- >
煙與鏡
- >
唐代進士錄
- >
朝聞道
- >
龍榆生：詞曲概論/大家小書
- >
伊索寓言-世界文學名著典藏-全譯本
- >
李白與唐代文化
- >
名家帶你讀魯迅:朝花夕拾
- >
推拿
本類暢銷
