創新能力培養的計算理論課程教學改革

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

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

關鍵詞：計算理論；計算思維；能力培養；創新模式

0引言

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

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

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

2計算理論課程的教學內容

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

3計算理論啟發式案例教學

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

4結語

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

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