計算機科學的數學基礎

前言

　　形式語言與自動機理論、可計算理論、邏輯學和程序設計理論，都是研究計算模型的。它們之間也是相互關聯(lián)的，共同構成了現(xiàn)代計算機科學技術的理論基礎。這些理論都是屬于數學學科的。形式語言與自動機理論、可計算理論和邏輯學的研究都始于20世紀初葉，特別是20世紀30年代的數學家church（邱奇）、G甜el（哥德爾）、Ⅺeene（克林）、P0st（波斯特）以及Turing（圖靈）等人的杰出工作催生了現(xiàn)代電子數字計算機的硬件和軟件的誕生。程序設計理論的研究相比則要遲一些，是20世紀后半葉現(xiàn)代電子數字計算機以‘。及程序設計語言和軟件誕生之后的事情了。它是專門研究程序設計語言和程序設計方法的數學理論。這些工作對于計算機科學的實踐和理論的發(fā)展有著深遠的影響。比如，圖靈機模型就被證明是現(xiàn)代電子數字計算機的理論模型。這些先驅者的工作在今天看來似乎是很平常的，它們的思想淵源甚至并不為今天眾多的計算機的使用者所知道。但是這些先驅者的工作確實是應該被那些從事計算機科學技術的工作者們所熟悉、所掌握的。因為這些思想和方法將對他們的工作產生很重要的啟示和指導作用。正是因為這一點，形式語言與自動機理論、可計算理論、邏輯學和程序設計理論一直以來都是國內外計算機科學技術專業(yè)碩士研究生的課程，而且還是作為重要的課程來開設的。　　然而，20多年來計算機科學技術已經發(fā)生了翻天覆地的變化，它作為一門年輕的學一科已經增長到了幾乎無法想象的程度，而同時計算機的應用也已經到了無所不在的地步。在這種情形下，人們都感到有必要對原有的課程設置作一番調整。盡管在計算機科學技術領域越來越追求實用化，但是我們仍然執(zhí)著地認為系統(tǒng)地了解和掌握計算機科學的數學理論對于從事計算機科學技術的工作者是重要的。本著“厚基礎、寬口徑、重能力”的精神，我們在計算機科學技術碩士研究生的教學計劃的調整中將這幾門課程合并為一門課程，取名為《計算機科學的數學基礎》，并把它作為計算機科學技術一級學科的碩士研究生的必修課程。通過這幾年的教學實踐，我們感到這個調整是成功的。但是一直苦于在國內外找不到一本與之相適應的統(tǒng)一的教材，這樣就萌發(fā)了編寫這樣一本教材的想法。我們的想法立刻得到了湘潭大學出版社的支持。

內容概要

　　《計算機科學的數學基礎》共分形式語言與自動機理論，可計算理論，邏輯學，程序設計理論等四個部分。內容包括：語言與正規(guī)語言；有限自動機；短語結構語言與上下文有關語言；可計算理論；模糊邏輯等?！队嬎銠C科學的數學基礎》內容豐富，講解通俗易懂，具有很強的可讀性。　　形式語言與自動機理論、可計算理論、邏輯學和程序設計理論，都是研究計算模型的。它們之間也是相互關聯(lián)的，共同構成了現(xiàn)代計算機科學技術的理論基礎。這些理論都是屬于數學學科的。形式語言與自動機理論、可計算理論和邏輯學的研究都始于20世紀初葉，特別是20世紀30年代的數學家Church（邱奇）、GMel（哥德爾）、Kleene（克林）、Post（波斯特）以及Turing（圖靈）等人的杰出工作催生了現(xiàn)代電子數字計算機的硬件和軟件的誕生。程序設計理論的研究相比則要遲一些，是20世紀后半葉現(xiàn)代電子數字計算機以及程序設計語言和軟件誕生之后的事情了。它是專門研究程序設計語言和程序設計方法的數學理論。這些工作對于計算機科學的實踐和理論的發(fā)展有著深遠的影響。比如，圖靈機模型就被證明是現(xiàn)代電子數字計算機的理論模型。這些先驅者的工作在今天看來似乎是很平常的，它們的思想淵源甚至并不為今天眾多的計算機的使用者所知道。但是這些先驅者的工作確實是應該被那些從事計算機科學技術的工作者們所熟悉、所掌握的。因為這些思想和方法將對他們的工作產生很重要的啟示和指導作用。正是因為這一點，形式語言與自動機理論、可計算理論、邏輯學和程序設計理論一直以來都是國內外計算機科學技術專業(yè)碩士研究生的課程，而且還是作為重要的課程來開設的。

書籍目錄

第一部分 形式語言與自動機理論第一章 語言與正規(guī)語言1.1 符號、符號串及其運算1.2 文法與語言的形式定義1.3 正規(guī)表達式1.4 正規(guī)文法與正規(guī)式第二章 有限自動機2.1 有限自動機的定義與構造2.2 確定的有限自動機（DFA）2.3 不確定的有限自動機（NFA）2.4 NFA的確定化2.5 DFA的最小化2.6 正規(guī)集與有限自動機的等價性2.7 雙向有限自動機2.8 具有輸出的有限自動機第三章 正規(guī)集的性質3.1 正規(guī)集的泵作用引理3.2 正規(guī)集的封閉性質3.3 正規(guī)集的一些判定算法第四章 上下文無關語言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.2 命題演算的公理系統(tǒng)11.3 PC的可靠性與一致性11.4 PC的完備性11.5 一階邏輯第十二章 直覺主義邏輯12.1 直覺主義的一些基本觀點12.2 一階直覺主義邏輯的形式化12.3 完全性定理第十三章 模態(tài)邏輯13.1 模態(tài)詞“必然”與“可能”13.2 模態(tài)命題邏輯系統(tǒng)13.3 模態(tài)狹義謂詞邏輯第十四章 非單調邏輯14.1 單調性與非單調性14.2 非單調邏輯14.3 缺省推理14.4 非單調邏輯系統(tǒng)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 三值邏輯代數系統(tǒng)16.4 n值邏輯代數系統(tǒng)16.5 閾值邏輯第四部分 程序設計理論第十七章 程序的指稱語義17.1 把程序看作函數17.2 序列程序結構的程序函數17.3 分支程序結構的程序函數17.4 循環(huán)程序結構的程序函數17.5 循環(huán)程序的正確性證明第十八章 程序的公理語義18.1 程序的公理語義18.2 霍爾公理系統(tǒng)18.3 最弱前置謂詞與程序的公理語義第十九章 程序的形式推導19.1 程序形式推導的基本思想19.2 選擇語句的設計19.3 循環(huán)程序的設計19.4 不變式與界函數的構造第二十章 遞歸程序理論20.1 遞歸的基本概念20.2 遞歸數據結構20.3 遞歸程序的證明習題參考文獻

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    計算機科學的數學基礎 PDF格式下載

---