《計算機科學的數學基礎》是2007年9月1日湘潭大學出版社出版的圖書。本書系統介紹計算機科學的基礎理論，可作為研究生的選修教材和一級學科碩士研究生的必修課教材。
基本介紹
- 書名：計算機科學的數學基礎
- ISBN：9787811280067
- 頁數：343頁
- 出版社：湘潭大學出版社
- 出版時間：2017年9月1日
- 裝幀：平裝
- 開本： 16
內容簡介,目錄,
內容簡介
《計算機科學的數學基礎》共分形式語言與自動機理論，可計算理論，邏輯學，程式設計理論等四個部分。內容包括：語言與正規語言；有限自動機；短語結構語言與上下文有關語言；可計算理論；模糊邏輯等。《計算機科學的數學基礎》內容豐富，講解通俗易懂，具有很強的可讀性。
形式語言與自動機理論、可計算理論、邏輯學和程式設計理論，都是研究計算模型的。它們之間也是相互關聯的，共同構成了現代計算機科學技術的理論基礎。這些理論都是屬於數學學科的。形式語言與自動機理論、可計算理論和邏輯學的研究都始於20世紀初葉，特別是20世紀30年代的數學家Church（邱奇）、GMel（哥德爾）、Kleene（克林）、Post（波斯特）以及Turing（圖靈）等人的傑出工作催生了現代電子數字計算機的硬體和軟體的誕生。程式設計理論的研究相比則要遲一些，是20世紀後半葉現代電子數字計算機以及程式設計語言和軟體誕生之後的事情了。它是專門研究程式設計語言和程式設計方法的數學理論。這些工作對於計算機科學的實踐和理論的發展有著深遠的影響。比如，圖靈機模型就被證明是現代電子數字計算機的理論模型。這些先驅者的工作在今天看來似乎是很平常的，它們的思想淵源甚至並不為今天眾多的計算機的使用者所知道。但是這些先驅者的工作確實是應該被那些從事計算機科學技術的工作者們所熟悉、所掌握的。因為這些思想和方法將對他們的工作產生很重要的啟示和指導作用。正是因為這一點，形式語言與自動機理論、可計算理論、邏輯學和程式設計理論一直以來都是國內外計算機科學技術專業碩士研究生的課程，而且還是作為重要的課程來開設的。
目錄
第一部分 形式語言與自動機理論
第一章 語言與正規語言
1.1 符號、符號串及其運算
1.2 文法與語言的形式定義
1.3 正規表達式
第二章 有限自動機
2.1 有限自動機的定義與構造
2.2 確定的有限自動機（DFA）
2.3 不確定的有限自動機（NFA）
2.4 NFA的確定化
2.5 DFA的最小化
2.6 正規集與有限自動機的等價性
2.7 雙向有限自動機
2.8 具有輸出的有限自動機
第三章 正規集的性質
3.1 正規集的泵作用引理
3.2 正規集的封閉性質
3.3 正規集的一些判定算法
第四章 上下文無關語言
4.1 上下文無關文法
4.2 上下文無關文法的簡化
4.3 Chomsky範式
4.4 Greibach範式
4.5 先天歧義的上下文無關語言的存在
第五章 下推自動機
5.1 非形式的描述
5.2 下推自動機的定義
5.3 下推自動機和上下文無關語言
第六章 上下文無關語言的性質
6.1 對CFL的泵作用引理
6.2 上下文無關語言的封閉性質
6.3 CFL的某些判定算法
第二部分 可計算理論
第七章 圖靈機
7.1 圖靈機模型
7.2 可計算語言和函式
7.3 圖靈機的構造技術
7.4 圖靈機的修改
7.5 Church假設
7.6 圖靈機作為枚舉器
7.7 等價於基本模型的受限圖靈機
第八章 短語結構語言與上下文有關語言
8.1 短語結構語言與圖靈機
8.2 上下文有關語言與線性有界自動機
8.3 上下文無關語言與遞歸集合
8.4 上下文有關語言類的性質
第九章 可判定性
9.1 遞歸語言和遞歸可枚舉語言的性質
9.2 通用圖靈機和一個不可判定問題
9.3 RICE定理和某些其他的不可判定問題
9.4 POST對應問題的不可判定性
9.5 圖靈機的有效計算和無效計算
9.6 Greibach定理
9.7 聖人計算
第十章 可計算理論
10.1 原始遞歸函式
10.2 遞歸函式與部分遞歸函式
10.3 圖靈機與部分遞歸函式的等價性
第三部分 邏輯學
第十一章 命題邏輯與一階邏輯
11.1 命題邏輯的自然推理
11.3 PC的可靠性與一致性
11.4 PC的完備性
11.5 一階邏輯
第十二章 直覺主義邏輯
12.1 直覺主義的一些基本觀點
12.2 一階直覺主義邏輯的形式化
12.3 完全性定理
第十三章 模態邏輯
13.1 模態詞“必然”與“可能”
13.2 模態命題邏輯系統
13.3 模態狹義謂詞邏輯
第十四章 非單調邏輯
14.1 單調性與非單調性
14.2 非單調邏輯
14.3 預設推理
14.4 非單調邏輯系統
14.5 限定理論
第十五章 模糊邏輯
15.1 邏輯與不確定性的研究
15.2 模糊集
15.3 模糊邏輯的代數模型——De-Morgan代數
15.4 模糊變數與模糊邏輯公式（函式）
15.5 模糊邏輯真值表與範式
15.6 模糊邏輯公式的極小化
15.7 似然推理
15.8 模糊歸納推理
第十六章 多值邏輯
16.1 三值邏輯
16.2 多值命題邏輯
16.3 三值邏輯代數系統
16.4 n值邏輯代數系統
16.5 閾值邏輯
第四部分 程式設計理論
第十七章 程式的指稱語義
17.1 把程式看作函式
17.2 序列程式結構的程式函式
17.3 分支程式結構的程式函式
17.4 循環程式結構的程式函式
17.5 循環程式的正確性證明
第十八章 程式的公理語義
18.1 程式的公理語義
18.2 霍爾公理系統
18.3 最弱前置謂詞與程式的公理語義
第十九章 程式的形式推導
