1、計算理論基礎(chǔ)(Induction to the Theory of Computation)課程代碼：06410052學(xué)分：2.0學(xué)時：32 （其中：課堂教學(xué)學(xué)時：32實驗學(xué)時：0上機(jī)學(xué)時：0 ）先修課程：離散數(shù)學(xué)，程序設(shè)計基礎(chǔ)適用專業(yè)：信息安全教材：計算理論導(dǎo)引，Michael Sipser著，段磊，唐長杰等譯，機(jī)械工業(yè)出版社，2016 年10月第1版一、課程性質(zhì)與課程目標(biāo)（-）課程性質(zhì)計算理論基礎(chǔ)是專業(yè)基礎(chǔ)課、必修課。計算理論基礎(chǔ)討論了計算機(jī)科學(xué)中的純粹、引人 注目并且普遍存在的基本內(nèi)容，介紹構(gòu)成基本計算范例的基本概念、模型、技巧、結(jié)果，闡述當(dāng) 今計算機(jī)科學(xué)家用于建模、討論和預(yù)測算法與計算

2、的思想概念與數(shù)學(xué)知識。（二）課程目標(biāo)1.知識方面課程目標(biāo)1.1:掌握自動機(jī)等基本計算模型及其演繹模型的形式化描述。課程目標(biāo)1.2：掌握構(gòu)造能夠識別語言的自動裝置的基本方法。課程目標(biāo)1.3：掌握能夠證明語言特性的基本證明方法。課程目標(biāo)1.4： 了解計算模型在應(yīng)用領(lǐng)域的廣泛應(yīng)用。2.能力與素質(zhì)方面課程目標(biāo)2. 1：能夠針對信息系統(tǒng)的運行過程演繹其對應(yīng)的計算模型。課程目標(biāo)2.2：能夠針對簡單信息系統(tǒng)設(shè)計其對應(yīng)的計算模型，并理解模型的不足。課程目標(biāo)2. 3：能夠基于計算模型為信息系統(tǒng)的設(shè)計與測試提供指導(dǎo)。（三）課程目標(biāo)與專業(yè)畢業(yè)要求指標(biāo)點的對應(yīng)關(guān)系本課程支撐專業(yè)培養(yǎng)計劃中畢業(yè)要求指標(biāo)點1-4, 2-2

3、, 4-1 o1.畢業(yè)要求1-4：能將數(shù)學(xué)、自然科學(xué)、工程基礎(chǔ)和專業(yè)知識運用到復(fù)雜工程問題的表述中。2畢業(yè)要求2-2：借助文獻(xiàn)輔助，具備對復(fù)雜工程問題進(jìn)行識別、表達(dá)、建模、求解的能力, 以及對分析結(jié)論進(jìn)行有效性評價的能力。3.畢業(yè)要求4-1：掌握針對復(fù)雜工程問題設(shè)計實驗的科學(xué)方法。求指標(biāo)標(biāo)點課程目畢業(yè)要求1-4畢業(yè)要求2-2畢業(yè)要求4-1課程目標(biāo)1.1V課程目標(biāo)L2V課程目標(biāo)1.37V課程目標(biāo)2.1VV課程目標(biāo)2.2VV課程目標(biāo)2.3V二、課程內(nèi)容與教學(xué)要求第一章有窮自動機(jī)和正則語言本章支持課程目標(biāo)：L1掌握自動機(jī)等基本計算模型及其演繹模型的形式化描述；1.2掌握 構(gòu)造能夠識別語言的自動裝置的

4、基本方法；1.3掌握能夠證明語言特性的基本證明方法；1. 4 了 解計算模型在應(yīng)用領(lǐng)域的廣泛應(yīng)用；2.1能夠針對信息系統(tǒng)的運行過程演繹其對應(yīng)的計算模型； 2.2能夠針對簡單信息系統(tǒng)設(shè)計其對應(yīng)的計算模型，并理解模型的不足；2.3能夠基于計算模型 為信息系統(tǒng)的設(shè)計與測試提供指導(dǎo)。（一）課程內(nèi)容（1）有窮自動機(jī)。（講授）（2）正則語言和正則運算。（講授）（3）非確定性與非確定型有窮自動機(jī)。（講授）（4） NFA、DFA的等價行與正則運算的封閉性。（講授+課堂練習(xí)）（5）正則表達(dá)式。（講授+課堂練習(xí)）（6）正則語言的泵引理與非正則語言。（講授+課堂練習(xí)）（一）教學(xué)要求.理解有窮自動機(jī)的形式化定義與運行

5、過程。.掌握有窮自動機(jī)的構(gòu)造技術(shù)。.掌握正則語言的運算及其封閉性。.理解非確定型自動機(jī)的運行過程。.理解確定型有窮自動機(jī)與非確定型有窮自動機(jī)之間的等價性。.掌握構(gòu)造與非確定型有窮自動機(jī)之間等價的自動機(jī)的方法。.掌握基于自動機(jī)的正則語言運算的封閉性證明技術(shù)。.掌握正則語言與有窮自動機(jī)之間的等價性。.掌握證明非正則語言的基本技術(shù)。（三）重點與難點.重點有窮自動機(jī)的構(gòu)造技術(shù)、正則語言的運算及其封閉性、構(gòu)造與非確定型有窮自動機(jī) 之間等價的自動機(jī)的方法、基于自動機(jī)的正則語言運算的封閉性證明技術(shù)、證明非正則 語言的基本技術(shù)。.難點有窮自動機(jī)的構(gòu)造技術(shù)、構(gòu)造與非確定型有窮自動機(jī)之間等價的自動機(jī)的方法、證 明

6、非正則語言的基本技術(shù)。第二章上下文無關(guān)語言與下推自動機(jī)本章支持課程目標(biāo)：1.1掌握自動機(jī)等基本計算模型及其演繹模型的形式化描述；1.3掌握 能夠證明語言特性的基本證明方法；1.4 了解計算模型在應(yīng)用領(lǐng)域的廣泛應(yīng)用；2.1能夠針對信 息系統(tǒng)的運行過程演繹其對應(yīng)的計算模型；2.2能夠針對簡單信息系統(tǒng)設(shè)計其對應(yīng)的計算模型， 并理解模型的不足。（-）課程內(nèi)容（1）上下文無關(guān)文法。（講授）（2）設(shè)計上下文無關(guān)文法與喬姆斯基范式。（講授+課堂練習(xí)）（3）下推自動機(jī)。（講授）（4）與上下文無關(guān)文法的等價性。（講授+課堂練習(xí)）（5）非上下文無關(guān)語言。（講授+課堂練習(xí)）（二）教學(xué)要求（1）掌握上下文無關(guān)文法的形

7、式化定義。（2）掌握基于文法的語言派生過程。（3）理解喬姆斯基范式。（4）掌握下推自動機(jī)的形式化定義及其運行過程。（5）理解下推自動機(jī)與上下文無關(guān)文法的等價性。（6）掌握非上下文無關(guān)語言的證明方法。（三）重點與難點1.重點基于文法的語言派生過程、下推自動機(jī)與上下文無關(guān)文法的等價性、非上下文無關(guān) 語言的證明方法。2 .難點非上下文無關(guān)語言的證明方法。第三章邱奇-圖靈論題本章支持課程目標(biāo)：1.1掌握自動機(jī)等基本計算模型及其演繹模型的形式化描述；L2掌握 構(gòu)造能夠識別語言的自動裝置的基本方法;2. 1能夠針對信息系統(tǒng)的運行過程演繹其對應(yīng)的計算 模型；2.2能夠針對簡單信息系統(tǒng)設(shè)計其對應(yīng)的計算模型，并

8、理解模型的不足；2. 3能夠基于計 算模型為信息系統(tǒng)的設(shè)計與測試提供指導(dǎo)。（-）課程內(nèi)容（1）圖靈機(jī)作為一個計算模型的基本定義。（講授）（2）圖靈機(jī)運行過程與接受的語言。（講授）（3）構(gòu)造圖靈機(jī)的基本技術(shù)。（講授講授+課堂練習(xí)）（4）圖靈機(jī)的變形。（講授+課堂練習(xí)）（5）算法的定義。（講授）（二）教學(xué)要求（1）理解圖靈機(jī)的形式化定義、運行過程。（2）掌握圖靈機(jī)的基本構(gòu)造技術(shù)。了解計算模型之間的等價性。（4）掌握對計算模型進(jìn)行演繹的基本思路。（三）重點與難點.重點圖靈機(jī)的運行過程、圖靈機(jī)的構(gòu)造技術(shù)、圖靈機(jī)的演繹。.難點圖靈機(jī)的構(gòu)造技術(shù)。第四章可判定性本章支持課程目標(biāo)：L1掌握自動機(jī)等基本計算模型

9、及其演繹模型的形式化描述；L 2掌握 構(gòu)造能夠識別語言的自動裝置的基本方法；1.3掌握能夠證明語言特性的基本證明方法；2.1能 夠針對信息系統(tǒng)的運行過程演繹其對應(yīng)的計算模型。（-）課程內(nèi)容（1）與正則語言相關(guān)的可判定性問題。（講授）（2）與上下文無關(guān)語言相關(guān)的可判定性問題。（講授+課堂練習(xí)）（3）對角化方法。（講授）（4）不可判定語言。（講授+課堂練習(xí)）（-）教學(xué)要求（1）理解可判定與不可判定語言的內(nèi)涵。（2）掌握證明可判定語言的基本方法。（3）掌握對角化方法。（4）理解可判定與圖靈可識別之間的關(guān)系。（三）重點與難點.重點證明可判定語言的基本方法、對角化方法。.難點對角化方法。三、學(xué)時分配及教

10、學(xué)方法章（按序填寫）教學(xué)形式及學(xué)時分配主要教學(xué)方法支撐的課程目標(biāo)課堂 教學(xué)實 驗上 機(jī)課程 實踐小 計第一章1010講授、課堂練習(xí)1、2、3、4、5、6、7第二章88講授、課堂練習(xí)1、 3、 4、 5、 6第三章88講授、課堂練習(xí)1、 2、 5、 6、 7第四章66講授、課堂練習(xí)1、 2、 3、 5合計3232四、課程考核目考核形式考核要求考核權(quán)重備注五平時作業(yè)按照作業(yè)題目進(jìn)行評分，總分?jǐn)?shù)平均 計算（5次以上）20%各次作業(yè)得分取 平均值、參隨堂測試閉卷10%考期末考試閉卷70%書及學(xué)習(xí)資料1、計算理論導(dǎo)引，Michael Sipser著，段磊，唐長杰等譯，機(jī)械工業(yè)出版社，2016 年10月第1版2、自動機(jī)理論、語言和計算導(dǎo)論（原書第3版），John E. Hopcroft等著，機(jī)械工業(yè) 出版社，2008年7月第1版3、形式語言，自動機(jī)理論與計算導(dǎo)論，Kamala Krithivasan Rama R （拉瑪）著；孟宇