創(chuàng)新能力培養(yǎng)的計(jì)算理論課程教學(xué)改革

前言：想要寫出一篇引人入勝的文章？我們特意為您整理了創(chuàng)新能力培養(yǎng)的計(jì)算理論課程教學(xué)改革范文，希望能給你帶來靈感和參考，敬請(qǐng)閱讀。

摘要：介紹以計(jì)算思維能力與創(chuàng)新能力培養(yǎng)為主線的計(jì)算理論課程教學(xué)設(shè)計(jì)方法，通過計(jì)算機(jī)學(xué)科素養(yǎng)訓(xùn)練、教學(xué)內(nèi)容與案例設(shè)計(jì)等，闡述如何培養(yǎng)研究生的計(jì)算思維與創(chuàng)新思維能力、提高教師素質(zhì)并設(shè)計(jì)合理的教學(xué)內(nèi)容，構(gòu)建適應(yīng)信息化時(shí)代的“啟發(fā)教”與“自主學(xué)”創(chuàng)新模式。

關(guān)鍵詞：計(jì)算理論；計(jì)算思維；能力培養(yǎng)；創(chuàng)新模式

0引言

前一段時(shí)間網(wǎng)上流傳中國(guó)科學(xué)院研制“龍芯”的胡偉武老師的一個(gè)視頻，其中提到中國(guó)能夠開發(fā)Java虛擬機(jī)的人才很少的問題，該問題的出現(xiàn)引人思考。我國(guó)計(jì)算機(jī)類專業(yè)的學(xué)生包括研究生畢業(yè)后做底層開發(fā)的人才很少，絕大多數(shù)人是把國(guó)外公司開發(fā)出來的編程語(yǔ)言拿過來直接使用，編程時(shí)直接調(diào)用軟件包中的函數(shù)，至于這些函數(shù)是如何實(shí)現(xiàn)的并沒有幾個(gè)人認(rèn)真思考。久而久之，學(xué)生（包括一些教師與軟件開發(fā)人員）也很少思考或研究這一問題，突然遇到這樣的問題就會(huì)束手無(wú)策、無(wú)從下手。所謂萬(wàn)丈高樓平地起，沒有基本的思維訓(xùn)練很難做到基礎(chǔ)性創(chuàng)新思維的能力培養(yǎng)。中興事件給我們國(guó)家的原始創(chuàng)新問題敲響了警鐘，有人在網(wǎng)上提出“假如微軟、谷歌不讓我們使用其操作系統(tǒng)怎么辦”的問題，說明應(yīng)用與創(chuàng)新缺一不可，只有應(yīng)用的火熱而沒有創(chuàng)新就會(huì)受制于人。計(jì)算理論課程是從本質(zhì)上介紹計(jì)算機(jī)科學(xué)的課程，是計(jì)算機(jī)學(xué)科發(fā)展的基石。為了計(jì)算機(jī)學(xué)科更好地發(fā)展，將計(jì)算理論作為一門必修課，作為培養(yǎng)高年級(jí)本科生或研究生計(jì)算思維和創(chuàng)新思維的重要一環(huán)是非常必要的，這是開設(shè)此門課程的現(xiàn)實(shí)選擇，也是必然選擇。

1計(jì)算理論在研究生教學(xué)中的重要性

“計(jì)算機(jī)科學(xué)技術(shù)日新月異，新東西層出不窮，舊的東西迅速被淘汰，但是作為一門科學(xué)，它有其自身的理論基礎(chǔ)，這些思想精華長(zhǎng)久地、甚至永恒地放射光芒，這些理論在應(yīng)用開發(fā)中好像是‘無(wú)用的’，但實(shí)際上，對(duì)于每一位從事計(jì)算機(jī)科學(xué)與技術(shù)的研究與開發(fā)的人來說，它們都是不可缺少的，就像能量守恒之類的物理定律對(duì)于每一位自然科學(xué)工作者和工程技術(shù)人員那樣”[1]?！巴ㄟ^這些要點(diǎn)，我們對(duì)計(jì)算機(jī)科學(xué)的重要基石有了一些新的認(rèn)知，有些之前我們認(rèn)為可能比較新穎的東西（比如層次化存儲(chǔ)），實(shí)際上在計(jì)算機(jī)誕生初期就被提出甚至進(jìn)行了量化分析，每年頂級(jí)會(huì)議上出現(xiàn)的一些新成果都是這些思想的實(shí)現(xiàn)；有些之前我們認(rèn)為可能比較陳舊的東西（比如虛擬化），實(shí)際上換一個(gè)角度可能是一種新的研究思路。真正具有本質(zhì)的重要性的東西，無(wú)所謂“新”與“舊”，應(yīng)該在歷史發(fā)展中傳承和保持下來”[2]。上述兩段話充分說明計(jì)算理論在現(xiàn)代計(jì)算機(jī)科學(xué)與技術(shù)研究生教學(xué)中的核心意義。從科學(xué)基礎(chǔ)理論角度來講，可計(jì)算性理論是計(jì)算機(jī)科學(xué)最核心的基礎(chǔ)理論，如果沒有可計(jì)算性理論，計(jì)算機(jī)將難以稱為計(jì)算機(jī)科學(xué)，這是學(xué)科發(fā)展需要，也是開設(shè)這門課程的根本原因。為創(chuàng)新能力的培養(yǎng)與思維訓(xùn)練過程，這一系列過程從低到高不斷升華，可逐步培養(yǎng)學(xué)生的計(jì)算思維與創(chuàng)新能力。在本科教學(xué)中，學(xué)生養(yǎng)成了“老師教什么，學(xué)生就記憶復(fù)述什么”的學(xué)習(xí)習(xí)慣，一般很少對(duì)教師講授的內(nèi)容提出異議和新的見解。只是在離散的抽象代數(shù)部分才開始涉及基本的運(yùn)算系統(tǒng)，但由于過于抽象，一般學(xué)生也是一知半解。在研究生教學(xué)中，教師教什么、學(xué)生就記憶復(fù)述什么的學(xué)習(xí)習(xí)慣一定要打破，學(xué)生要養(yǎng)成“老師講授的不一定是唯一的、最好的解決問題方法”的思想意識(shí)，教師要以“沒有最好，只有更好，優(yōu)化優(yōu)化再優(yōu)化”為教學(xué)理念。學(xué)生要勇于向老師提出問題，敢于向課本內(nèi)容提出挑戰(zhàn)，給出新的見解。研究生接受計(jì)算理論學(xué)位課程的學(xué)習(xí)已經(jīng)不僅是為了掌握知識(shí)獲得學(xué)分，還是對(duì)計(jì)算系統(tǒng)的了解逐步向更高級(jí)的計(jì)算系統(tǒng)（它的運(yùn)算呈現(xiàn)出模型化的特征）過渡，并由此學(xué)會(huì)一種思維方式、一種創(chuàng)新能力，這種思維方式與創(chuàng)新能力對(duì)于從事任何工作都是受益終身的。作為一門研究生素養(yǎng)訓(xùn)練的學(xué)位課程，計(jì)算理論課程的教學(xué)改革必須跟上國(guó)家創(chuàng)新人才培養(yǎng)的時(shí)代步伐，精心設(shè)計(jì)、合理安排、科學(xué)謀劃，這是計(jì)算機(jī)學(xué)科發(fā)展的需要，是國(guó)家積極推進(jìn)培養(yǎng)創(chuàng)新人才賦予我們的使命與任務(wù)。

2計(jì)算理論課程的教學(xué)內(nèi)容

人工智能、大數(shù)據(jù)、云計(jì)算、邊緣計(jì)算等領(lǐng)域正在蓬勃發(fā)展，越來越多的經(jīng)驗(yàn)在實(shí)踐中累積，但是理論基礎(chǔ)都相對(duì)薄弱，需要構(gòu)建各自領(lǐng)域中有較強(qiáng)針對(duì)性的基礎(chǔ)理論[2]。面對(duì)新形勢(shì)、新需求，計(jì)算理論要講述的內(nèi)容包括以下幾方面。1）以5條基本指令x=x+1、x=x-1、TOAIFx≠0、TOA和y=x為基礎(chǔ)的元語(yǔ)言程序描述可計(jì)算函數(shù)。使用5條基本指令的元語(yǔ)言程序教學(xué)過程，就是訓(xùn)練學(xué)生使用最基本的指令編程實(shí)現(xiàn)復(fù)雜的可計(jì)算函數(shù)的抽象思維能力過程。近年來出現(xiàn)的Python語(yǔ)言是一個(gè)比較流行的易學(xué)易用的編程語(yǔ)言，其創(chuàng)始人Guido也是從編寫Python的編譯器開始，將其逐步演化成今天的流行語(yǔ)言。程序員中流行的“人生苦短，我用python”也說明其受歡迎的程度，但火熱程度的背后是Guido及團(tuán)隊(duì)成員不懈努力的結(jié)果，沒有開發(fā)人員的默默付出，將從底層搭建出來的結(jié)果呈現(xiàn)給我們，就沒有今天的Python。對(duì)熱議的中興事件引起的處理器芯片設(shè)計(jì)問題來說，將指令集和程序區(qū)分開，可以以不變的少量指令構(gòu)成萬(wàn)變的應(yīng)用程序。指令集（如x86、MIPS、RISC-V）中不同類型的指令都是有限的，但可以編寫的不同程序的數(shù)量極其龐大，這樣硬件上的固定性與軟件上的任意性矛盾就得到解決[2]。2）從初始函數(shù)S(x)=x+1、n(x)=0和Ui(x1,x2�,xn)=xi出發(fā)，通過利用復(fù)合、遞歸算子得到的原始遞歸函數(shù)以及利用復(fù)合、遞歸與取極小算子得到的部分遞歸函數(shù)與遞歸函數(shù)描述可計(jì)算函數(shù)。遞歸函數(shù)是計(jì)算理論的核心概念，因?yàn)閳D靈可計(jì)算函數(shù)類就是遞歸函數(shù)類，兩者完全等價(jià)。遞歸函數(shù)是構(gòu)造更為復(fù)雜函數(shù)的基礎(chǔ)，現(xiàn)代以神經(jīng)網(wǎng)絡(luò)為代表的機(jī)器學(xué)習(xí)是一個(gè)黑箱算法，可解釋性不足，需要一個(gè)可被證明的理論作為基礎(chǔ)。從遞歸函數(shù)解讀深度學(xué)習(xí)過程，即一層神經(jīng)網(wǎng)絡(luò)的輸出是下一層神經(jīng)網(wǎng)絡(luò)的輸入，通過不斷地復(fù)合與遞歸層層深入最后得到深度學(xué)習(xí)訓(xùn)練的結(jié)果[3]，遞歸可以構(gòu)造出更復(fù)雜的函數(shù)，從而解決更復(fù)雜的計(jì)算機(jī)科學(xué)與工程問題。3）使用兩符號(hào)與多符號(hào)的波斯特圖靈機(jī)、四元組圖靈機(jī)、五元組圖靈機(jī)、通用圖靈機(jī)描述可計(jì)算函數(shù)。此處的兩符號(hào)（0和1）波斯特圖靈機(jī)接近于我們熟悉的匯編語(yǔ)言，而兩符號(hào)與我們現(xiàn)在所使用的計(jì)算機(jī)底層操作的符號(hào)是對(duì)應(yīng)的；多符號(hào)波斯特圖靈機(jī)是兩符號(hào)圖靈機(jī)的一種推廣?，F(xiàn)代計(jì)算機(jī)可以處理的數(shù)字、圖像、音頻、視頻等各種形式的數(shù)據(jù)，其實(shí)質(zhì)也是0和1兩符號(hào)推廣到多符號(hào)的擴(kuò)展形式，形式語(yǔ)言與自動(dòng)機(jī)理論也產(chǎn)生于此。四元組和五元組圖靈機(jī)是以元組形式描述的產(chǎn)生式規(guī)則，其中的狀態(tài)相當(dāng)于現(xiàn)代編程語(yǔ)言中的環(huán)境；每個(gè)產(chǎn)生式的前提（也稱為前件）和效果（也稱為后件），相當(dāng)于在不同狀態(tài)下采取不同的動(dòng)作需要的前提和產(chǎn)生的效果。通用圖靈機(jī)是進(jìn)行各種計(jì)算的元語(yǔ)言程序，可以完成各種計(jì)算操作，但其存在局限性，如計(jì)算機(jī)病毒作為一種具有特定功能的算法，同樣可以用圖靈機(jī)或通用圖靈機(jī)進(jìn)行描述，通用圖靈機(jī)模型只限于分析一種單一的算法或程序，如果要分析兩個(gè)或更多的算法和程序之間的聯(lián)系，這種模型顯然不夠。文獻(xiàn)[4]從計(jì)算機(jī)的基礎(chǔ)理論模型——圖靈機(jī)模型出發(fā)，提出一種擴(kuò)展的通用圖靈機(jī)模型EUTM，極大地簡(jiǎn)化了計(jì)算機(jī)病毒傳染機(jī)制的形式化描述，開辟了計(jì)算機(jī)病毒傳染特性和可傳播性形式化描述的新領(lǐng)域，有助于正確地理解計(jì)算機(jī)病毒。4）使用元語(yǔ)言程序描述不可判定性問題。圖靈機(jī)根據(jù)機(jī)器的程序處理初始格局，有的初始格局可能導(dǎo)致停機(jī)，有的則導(dǎo)致無(wú)限的格局序列，引出停機(jī)問題。圖靈機(jī)停機(jī)問題的實(shí)質(zhì)：是否存在一個(gè)算法，對(duì)于任意給定的圖靈機(jī)都能判定任意的初始格局是否會(huì)導(dǎo)致停機(jī)。圖靈已經(jīng)證明，這樣的算法是不存在的，即停機(jī)問題是不可判定的。停機(jī)問題是研究許多不可判定問題的基礎(chǔ)，人們往往把一個(gè)問題的判定歸結(jié)為停機(jī)問題：“如果問題X可判定，則停機(jī)問題可判定”，從而證明問題X的不可判定性。停機(jī)問題有多種不同的敘述方式和證明方法，分別適用于具有不同特征的問題，如對(duì)于目前人們使用的智能手機(jī)，經(jīng)常會(huì)出現(xiàn)某APP運(yùn)行了計(jì)算模型上沒有進(jìn)行定義的操作的現(xiàn)象，導(dǎo)致手機(jī)對(duì)用戶的任何操作都無(wú)法作出反應(yīng)，我們稱為“死機(jī)”。對(duì)于這種“死機(jī)”行為，手機(jī)開發(fā)商設(shè)計(jì)一個(gè)檢測(cè)軟件進(jìn)行監(jiān)控處理就是一個(gè)停機(jī)問題的現(xiàn)實(shí)反映。顯然，根據(jù)上述論述，這樣的軟件是設(shè)計(jì)不出來的。5）以產(chǎn)生式規(guī)則為基礎(chǔ)的圖厄系統(tǒng)描述可計(jì)算函數(shù)。這一部分主要講述圖厄系統(tǒng)識(shí)別符號(hào)串。在形式語(yǔ)義學(xué)中圖厄系統(tǒng)實(shí)際上被稱為文法，在計(jì)算機(jī)科學(xué)中，文法是編譯原理的基礎(chǔ)，是描述一門程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)其編譯方法的基礎(chǔ)，同時(shí)也是形式語(yǔ)義學(xué)的基礎(chǔ)。形式語(yǔ)義學(xué)在自然語(yǔ)言處理、程序語(yǔ)言設(shè)計(jì)、網(wǎng)絡(luò)搜索引擎以及計(jì)算復(fù)雜性上都有重要的影響，如通過設(shè)計(jì)類似于產(chǎn)生式系統(tǒng)的圖厄系統(tǒng)識(shí)別需要的符號(hào)串，可聯(lián)想到在網(wǎng)絡(luò)搜索引擎的文本檢索中常常涉及的問題[5]：給定一個(gè)單詞集合，查找包含一個(gè)（或全部）單詞的所有文檔。搜索引擎是這一過程的通俗示例，搜索引擎使用一種稱為“倒排索引”的特殊技術(shù)，對(duì)網(wǎng)絡(luò)上出現(xiàn)的每個(gè)單詞（有1億種不同的單詞）所有出現(xiàn)之處的列表進(jìn)行保存，有非常大的主存的機(jī)器保持這些列表的最常見部分隨處可見，允許許多人在瞬間搜索到這些文檔。此外，圖厄系統(tǒng)還是計(jì)算機(jī)文法的基礎(chǔ)，對(duì)于語(yǔ)言的語(yǔ)法分析等也起著重要的基礎(chǔ)性作用。6）以單帶與多帶圖靈機(jī)描述可計(jì)算函數(shù)。單帶圖靈機(jī)由3部分組成：一條帶、一個(gè)讀寫頭和一個(gè)控制器。圖靈機(jī)的格局由當(dāng)前狀態(tài)、當(dāng)前帶內(nèi)容、讀寫頭的當(dāng)前位置組成。圖靈機(jī)開始運(yùn)行后，根據(jù)轉(zhuǎn)移函數(shù)所描述的規(guī)則進(jìn)行計(jì)算，圖靈機(jī)就從一個(gè)格局到另一個(gè)格局進(jìn)行轉(zhuǎn)換。圖靈機(jī)本質(zhì)上是一個(gè)程序或算法的高度抽象，當(dāng)給定一個(gè)輸入x以后，就可以計(jì)算出f(x)。除了前面描述的計(jì)算模型外，人們還研究了圖靈機(jī)的各種變型，如非確定的圖靈機(jī)、多道圖靈機(jī)、多帶圖靈機(jī)、多維圖靈機(jī)、多頭圖靈機(jī)、帶外部信息源的圖靈機(jī)等，這些圖靈機(jī)變型對(duì)今天的計(jì)算機(jī)體系結(jié)構(gòu)設(shè)計(jì)仍具有重要的指導(dǎo)作用。除極個(gè)別情形外，這些變型并未擴(kuò)展圖靈機(jī)的計(jì)算能力，它們計(jì)算的函數(shù)類與基本圖靈機(jī)是相同的，但為研究不同類型的問題提供了方便的理論模型。上述圖靈機(jī)的組合變型演化出當(dāng)今的計(jì)算機(jī)硬盤存儲(chǔ)表示形式（通過磁頭、磁道、扇區(qū)等參數(shù)），而多帶圖靈機(jī)是研究計(jì)算復(fù)雜性理論的重要計(jì)算模型。人們還在圖靈機(jī)的基礎(chǔ)上提出不同程度的近似于現(xiàn)代計(jì)算機(jī)的抽象機(jī)器，如具有隨機(jī)訪問存儲(chǔ)器的程序機(jī)器等。

3計(jì)算理論啟發(fā)式案例教學(xué)

計(jì)算理論課程講述多種模型，一方面是為了讓學(xué)生了解與掌握計(jì)算理論知識(shí)并證明它們的等價(jià)性，因而論證Church-Turing問題；另一方面也是為了訓(xùn)練學(xué)生創(chuàng)新思維，打破思維框架束縛，培養(yǎng)學(xué)生從不同角度解決問題的能力。各種模型具有不同的特點(diǎn)，針對(duì)不同的問題各有其價(jià)值。不同研究者在解決同一科學(xué)問題時(shí)，會(huì)給出不同的算法：這些算法或者演化于某些著名學(xué)者提出的基本方法，或者是自己提出的一個(gè)不同于常人的方法（這也相當(dāng)于一個(gè)個(gè)小的具有針對(duì)性的計(jì)算模型）。之所以有膾炙人口的三國(guó)演義產(chǎn)生，就在于有陳壽的三國(guó)志，三國(guó)志相當(dāng)于我們上述描述的某一“計(jì)算模型”，而三國(guó)演義就在此“計(jì)算模型”下加上民間傳說在羅貫中的筆下演化而來的，妙筆生花（從計(jì)算機(jī)科學(xué)角度看就是組合新的理論與方法到原有模型中用于解決新的問題）更加接地氣。以具體案例對(duì)啟發(fā)式案例教學(xué)作進(jìn)一步說明如下。案例1：在遞歸函數(shù)的謂詞遞歸性證明中，首先通過使用真值表分析法得到證明過程的特征函數(shù)，進(jìn)一步引入廣義德•摩根律，并通過啟發(fā)使少部分學(xué)生給出不同于原有教案上的證明方法。案例2：在講授四元組、五元組圖靈機(jī)過程中，引入三國(guó)演義中的劉備東吳招親、諸葛亮授趙云3條錦囊妙計(jì)的故事展開圖靈機(jī)的狀態(tài)變化與操作過程，將深?yuàn)W的教學(xué)內(nèi)容與大家熟悉的故事巧妙結(jié)合，達(dá)到寓教于樂的目的。計(jì)算理論的講述一方面可以使學(xué)生了解這些計(jì)算模型的知識(shí)，看到它們的現(xiàn)代應(yīng)用演化。在教學(xué)中，注重啟發(fā)學(xué)生將這種“演化”方法融入自己的科學(xué)研究中，利用自己所研究領(lǐng)域先驅(qū)學(xué)者提出的原創(chuàng)方法加上其他方法及所解決問題的特性解決問題，把“共性”+“特性”解決問題的思想融進(jìn)計(jì)算思維與創(chuàng)新能力的培養(yǎng)過程中。另一方面，在各章不同計(jì)算模型講授過程中，以問題啟發(fā)學(xué)生思考，問題可以是：這些計(jì)算模型有什么區(qū)別？共同點(diǎn)又是什么？在不同講述內(nèi)容中可計(jì)算是如何定義的？通過學(xué)生思考與教師釋疑，學(xué)生可意識(shí)到同樣的問題有不同的解決方法，學(xué)會(huì)從不同角度思考問題，勇于探索并打破思維框架的束縛，尋求問題新的解決方案，這是創(chuàng)新能力培養(yǎng)的必要過程；同時(shí)，學(xué)生可在這個(gè)過程中充分理解和掌握計(jì)算機(jī)科學(xué)先驅(qū)們對(duì)問題的定義、方法的描述、性質(zhì)的驗(yàn)證或證明，這也是今后從事科學(xué)研究的研究生應(yīng)該掌握的必要方法與思維方式。

4結(jié)語(yǔ)

吉林大學(xué)是一所綜合性雙一流國(guó)家重點(diǎn)建設(shè)大學(xué)，研究生的培養(yǎng)更加應(yīng)該以思維方式與創(chuàng)新能力為主，計(jì)算機(jī)學(xué)院的研究生從20世紀(jì)80年代開始學(xué)習(xí)計(jì)算理論這門課程，一直持續(xù)至今。在教學(xué)實(shí)踐中，我們發(fā)現(xiàn)很多學(xué)生學(xué)習(xí)以后并不了解這門課程的真正內(nèi)涵，創(chuàng)新思維的訓(xùn)練更是無(wú)從談起。計(jì)算機(jī)學(xué)科研究生從基礎(chǔ)知識(shí)掌握與編程能力培養(yǎng)到計(jì)算思維與創(chuàng)新能力的養(yǎng)成，是對(duì)高校計(jì)算機(jī)學(xué)科研究生理論教學(xué)的一個(gè)挑戰(zhàn)。計(jì)算思維與創(chuàng)新是運(yùn)用計(jì)算機(jī)科學(xué)的基本知識(shí)進(jìn)行分析問題、發(fā)現(xiàn)問題與解決問題所涉及的計(jì)算機(jī)科學(xué)各個(gè)方面的一系列思維活動(dòng)與創(chuàng)新設(shè)計(jì)過程，其中計(jì)算思維著眼于求解問題思維模式的養(yǎng)成與訓(xùn)練，而創(chuàng)新著眼于突破原有思維定式與框架，敢于打破常規(guī)的思維能力培養(yǎng)。計(jì)算理論課程的教學(xué)內(nèi)容和教學(xué)方法，是訓(xùn)練學(xué)生計(jì)算思維和創(chuàng)新思維的有效手段。前者從不同計(jì)算模型的角度研究相同問題的可計(jì)算性，后者以對(duì)比分析的形式完美地呈現(xiàn)計(jì)算模型的表示方法、計(jì)算過程、計(jì)算能力，二者異曲同工，緊緊圍繞訓(xùn)練計(jì)算思維、培養(yǎng)創(chuàng)新能力的目的展開。我們從計(jì)算理論課程的意義、研究生培養(yǎng)中的作用、課程講述內(nèi)容與演化、啟發(fā)式教學(xué)幾方面進(jìn)行描述，力圖探索計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科研究生計(jì)算思維與創(chuàng)新能力培養(yǎng)的新模式，希望為高水平創(chuàng)新型人才培養(yǎng)提供可供借鑒的教學(xué)模式與方法。

作者：李占山 呂帥 單位：吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院