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

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

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

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

0引言

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

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

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

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

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

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

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

4結(jié)語

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

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