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

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

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

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

0引言

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

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

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

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

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

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

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

4結(jié)語

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

作者：李占山 呂帥 單位：吉林大學 計算機科學與技術學院