計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)

前言

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

內(nèi)容概要

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

書(shū)籍目錄

第一部分 形式語(yǔ)言與自動(dòng)機(jī)理論第一章 語(yǔ)言與正規(guī)語(yǔ)言1.1 符號(hào)、符號(hào)串及其運(yùn)算1.2 文法與語(yǔ)言的形式定義1.3 正規(guī)表達(dá)式1.4 正規(guī)文法與正規(guī)式第二章 有限自動(dòng)機(jī)2.1 有限自動(dòng)機(jī)的定義與構(gòu)造2.2 確定的有限自動(dòng)機(jī)（DFA）2.3 不確定的有限自動(dòng)機(jī)（NFA）2.4 NFA的確定化2.5 DFA的最小化2.6 正規(guī)集與有限自動(dòng)機(jī)的等價(jià)性2.7 雙向有限自動(dòng)機(jī)2.8 具有輸出的有限自動(dòng)機(jī)第三章 正規(guī)集的性質(zhì)3.1 正規(guī)集的泵作用引理3.2 正規(guī)集的封閉性質(zhì)3.3 正規(guī)集的一些判定算法第四章 上下文無(wú)關(guān)語(yǔ)言4.1 上下文無(wú)關(guān)文法4.2 上下文無(wú)關(guān)文法的簡(jiǎn)化4.3 Chomsky范式4.4 Greibach范式4.5 先天歧義的上下文無(wú)關(guān)語(yǔ)言的存在第五章 下推自動(dòng)機(jī)5.1 非形式的描述5.2 下推自動(dòng)機(jī)的定義5.3 下推自動(dòng)機(jī)和上下文無(wú)關(guān)語(yǔ)言第六章 上下文無(wú)關(guān)語(yǔ)言的性質(zhì)6.1 對(duì)CFL的泵作用引理6.2 上下文無(wú)關(guān)語(yǔ)言的封閉性質(zhì)6.3 CFL的某些判定算法第二部分 可計(jì)算理論第七章 圖靈機(jī)7.1 圖靈機(jī)模型7.2 可計(jì)算語(yǔ)言和函數(shù)7.3 圖靈機(jī)的構(gòu)造技術(shù)7.4 圖靈機(jī)的修改7.5 Church假設(shè)7.6 圖靈機(jī)作為枚舉器7.7 等價(jià)于基本模型的受限圖靈機(jī)第八章 短語(yǔ)結(jié)構(gòu)語(yǔ)言與上下文有關(guān)語(yǔ)言8.1 短語(yǔ)結(jié)構(gòu)語(yǔ)言與圖靈機(jī)8.2 上下文有關(guān)語(yǔ)言與線性有界自動(dòng)機(jī)8.3 上下文無(wú)關(guān)語(yǔ)言與遞歸集合8.4 上下文有關(guān)語(yǔ)言類的性質(zhì)第九章 可判定性9.1 遞歸語(yǔ)言和遞歸可枚舉語(yǔ)言的性質(zhì)9.2 通用圖靈機(jī)和一個(gè)不可判定問(wèn)題9.3 RICE定理和某些其他的不可判定問(wèn)題9.4 POST對(duì)應(yīng)問(wèn)題的不可判定性9.5 圖靈機(jī)的有效計(jì)算和無(wú)效計(jì)算9.6 Greibach定理9.7 圣人計(jì)算第十章 可計(jì)算理論10.1 原始遞歸函數(shù)10.2 遞歸函數(shù)與部分遞歸函數(shù)10.3 圖靈機(jī)與部分遞歸函數(shù)的等價(jià)性第三部分 邏輯學(xué)第十一章 命題邏輯與一階邏輯11.1 命題邏輯的自然推理11.2 命題演算的公理系統(tǒng)11.3 PC的可靠性與一致性11.4 PC的完備性11.5 一階邏輯第十二章 直覺(jué)主義邏輯12.1 直覺(jué)主義的一些基本觀點(diǎn)12.2 一階直覺(jué)主義邏輯的形式化12.3 完全性定理第十三章 模態(tài)邏輯13.1 模態(tài)詞“必然”與“可能”13.2 模態(tài)命題邏輯系統(tǒng)13.3 模態(tài)狹義謂詞邏輯第十四章 非單調(diào)邏輯14.1 單調(diào)性與非單調(diào)性14.2 非單調(diào)邏輯14.3 缺省推理14.4 非單調(diào)邏輯系統(tǒng)14.5 限定理論第十五章 模糊邏輯15.1 邏輯與不確定性的研究15.2 模糊集15.3 模糊邏輯的代數(shù)模型——De-Morgan代數(shù)15.4 模糊變量與模糊邏輯公式（函數(shù)）15.5 模糊邏輯真值表與范式15.6 模糊邏輯公式的極小化15.7 似然推理15.8 模糊歸納推理第十六章 多值邏輯16.1 三值邏輯16.2 多值命題邏輯16.3 三值邏輯代數(shù)系統(tǒng)16.4 n值邏輯代數(shù)系統(tǒng)16.5 閾值邏輯第四部分 程序設(shè)計(jì)理論第十七章 程序的指稱語(yǔ)義17.1 把程序看作函數(shù)17.2 序列程序結(jié)構(gòu)的程序函數(shù)17.3 分支程序結(jié)構(gòu)的程序函數(shù)17.4 循環(huán)程序結(jié)構(gòu)的程序函數(shù)17.5 循環(huán)程序的正確性證明第十八章 程序的公理語(yǔ)義18.1 程序的公理語(yǔ)義18.2 霍爾公理系統(tǒng)18.3 最弱前置謂詞與程序的公理語(yǔ)義第十九章 程序的形式推導(dǎo)19.1 程序形式推導(dǎo)的基本思想19.2 選擇語(yǔ)句的設(shè)計(jì)19.3 循環(huán)程序的設(shè)計(jì)19.4 不變式與界函數(shù)的構(gòu)造第二十章 遞歸程序理論20.1 遞歸的基本概念20.2 遞歸數(shù)據(jù)結(jié)構(gòu)20.3 遞歸程序的證明習(xí)題參考文獻(xiàn)

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ) PDF格式下載

---