從經典到非經典

曾華琳　陳毅東　晁飛　李紹滋　周昌樂

摘要：從闡述智能專業的算法體系入手，介紹非經典計算課程的開設目的、內容及課程設計思路，重點闡述如何引導學生在課程中更有效地掌握與經典計算中不同的計算概念，促使學生更自主地跟蹤科學前沿技術，并對智能專業如何開展專業特色課程的設計提出討論和思考。

關鍵詞：非經典計算；算法設計與分析；智能科學與技術

1背景

智能科學與技術是人工智能方向的重點交叉學科，是一個包含了認知科學、腦科學、計算機科學的新興學科。按照教育部學科專業目錄，智能科學與技術是一級學科計算機科學與技術下的二級學科。如何在4年的本科教學過程中，既立足于計算機學科內容，又突出智能專業的特點，體現該專業區別于計算機科學專業的特色，培養一流的智能人才，是眾多智能專業積極探索的問題。

本著幫助學生建立寬廣厚實的知識基礎，使學生將來能向本專業任何一個分支方向發展，并能掌握本學科發展的最新動態和發展趨勢，深刻領會本學科與其他相關學科區別的目標，廈門大學智能科學與技術系于2012年合理調整了專業培養方案，制定了一套突出專業特色和個性的教學大綱，課程體系分為學科通修課程、專業必修課程、專業選修課程。其中，專業必修課程細分為智能基礎類課程、軟件理論類課程及硬件基礎類課程3個不同類別。在智能基礎類課程中，開設非經典計算課程。該課程是廈門大學智能科學與設計系最具特色的課程。

該課程以軟件理論類課程算法設計與分析為先導課程，在本科三年級的第一學期先講授算法知識，在同一學年度第三學期講授非經典計算的內容。教師首先介紹經典算法設計與分析中的各種傳統算法，借由經典算法發展過程中遇到的困境問題引出非經典計算的內容，前后呼應，有助于學生在智能計算上獲得完整的系統學習。

2非經典計算在智能科學與技術專業本科教學算法體系中的地位

算法設計是智能科學與技術專業中的核心內容。本科專業4年的專業教學計劃由4門核心課程構成算法體系的主線，包括高級語言程序設計（本科一年級學科通修課程）、數據結構（本科二年級方向必修課程）、算法設計與分析（本科三年級方向必修課程）、非經典計算（本科三年級方向限選課程）。這4門課程的教學內容和組織結構完整地構成了算法體系結構。以圖靈獎獲得者、pascal之父Niklaus Wirth提出的著名公式為參照，即Algorithm+Data Structures=Programs，算法體系以培訓計算機方向學生掌握編程能力，獨立完成分析問題、設計方案、解決問題的綜合能力為主要目標；在這個體系中，程序語言是基礎，數據結構是內涵，算法是框架。

在算法體系中，這4門課程以循序漸進的方式展開，注重對學生算法思維的培訓。

（1）高級語言程序設計講授的是c語言程序設計，通過對C語言的詳細介紹，讓學生掌握程序設計方法和編程技巧。作為初始啟蒙課程，選擇C語言作為程序教學語言，是因為C語言的使用廣泛，擁有嚴格完整的語法結構，適合教學。

（2）數據結構重點講授各種常用的數據表示邏輯結構、存儲結構及其基本的運算操作，并介紹相關算法及效率分析。教師通過在一年級對包括C語言在內的其他程序設計過程的訓練，加人對數據結構中各種數據的邏輯、存儲結構的表示和運算操作，從數據結構的角度闡述典型算法，并簡單介紹算法的效率分析，這是對程序設計訓練的進階內容。

（3）算法設計和分析主要介紹算法設計與分析的基本方法以及算法復雜性理論基礎。我們在本科三年級引入算法設計與分析課程，從算法的抽象角度總結和歸納各種算法思想，包括遞歸與分治法、貪心法、動態規劃法、回溯法、分支定界法、高級圖論算法、線性規劃算法等，最后闡述算法復雜性的分析方法、NP完全性理論基礎等計算復雜性的基本知識及完備性證明概要，重點闡述算法思想，從復雜性角度比較和分析不同的算法。上述（1）、（2）和（3）的內容構成了計算機學科通用算法體系的教學過程。

（4）非經典計算主要討論何為計算的本質以及經典計算在計算能力上遇到的困境，以此為契機討論自然計算——生物計算、集群計算、量子計算等內容。算法設計和分析的最后一個章節是對算法復雜性的分析方法及NP完全性理論基礎的介紹，不可避免地會討論到現代電子數字計算機體系在計算能力上的瓶頸以及由NP完全問題（Non-deterministic Polynomial），號稱世界七大數學難題之一的經典問題，引出對經典計算機體系的深層思考，進一步引導學生思考如何解決計算能力的瓶頸問題。這是教師設計非經典計算課程的出發點，也是對算法體系更完整的補充和更深層次的探討。

此外，我們還需要對授課學期選擇進行考慮。廈門大學實行三學期制度，在第三學期內開設的課程大多是實踐類課程及前沿技術介紹課程。在本科三年級的小學期階段，學生基本完成了智能專業大部分必修課程的學習，擁有了一定的計算機基礎和學科素養。這時，依賴學生已經具有的數據結構與算法的基本知識，可以將學生的學習引向如何理解計算的本質；再從計算本質出發，由易到難，介紹采用非計算機的不同計算媒介和方法，例如DNA計算、元胞自動機、集群計算等知識，結合計算機模擬程序加深認識。在逐步加深學生對非經典方法計算的理解之后，再引入量子信息與量子計算。至此，智能專業關于算法體系的整體構建已基本完成。

3非經典計算課程內容大綱

非經典計算課程的主體課程內容以專題形式展開，分為5個部分。

第一部分：計算本質。從什么是計算人手，列舉各種計算的形式，由數字的計算到命題的證明，由數值計算到符號推導，引出計算本質的廣義定義，“計算是從一個符號串f變換成另一個符號串g”，即從已知符號（串）開始，一步一步地改變符號（串），經過有限步驟，最后得到一個滿足預先規定的符號（串）的變換過程；進一步展開對什么是計算、什么是可計算性的討論，展開介紹計算理論上4個著名的計算模型——般遞歸函數、λ可計算函數、圖靈機和波斯特系統；最后歸結到丘奇·圖靈論點。以上是第一條主線，第二條主線從計算復雜性角度人手，討論在經典算法中難解決的NP完全問題，提出在經典計算體系中隨著輸入數據規模增大而難以計算的瓶頸，從而引發學生對于經典計算的思考。

第二部分：智能計算機的發展。這個部分主要討論計算機硬件的發展歷史，即從原始時期的計算工具，到現代計算機的4個發展階段：史前期、機械式計算機、機電式計算機、電子計算機。教師從模擬型計算機到數字型計算機，闡述馮·諾依曼關于計算機五大基本組成對現代計算機體系結構的影響及其帶來的限制；從硬件角度提出非經典計算機的討論，鼓勵學生對現代智能計算機硬件進行調查。

第三部分：DNA計算。主要闡述DNA計算的基本原理，并以旅行商問題為引子，展開經典計算難解決問題的討論，重點介紹第一個由DNA計算模型解決的問題——L.Adleman構建的7個節點的DHP，并著重指出DNA計算潛在的巨大并行性和待研究的問題；然后介紹R.Lipton用DNA實驗解決的另一個NP問題——可滿足性問題（SAT）；最后將DNA計算與軟計算結合，闡述粘貼模型以及DNA的軟計算模擬與遺傳算法的對比。對于DNA計算強大的并行性，以具體的算法實例加以詳細闡述和說明，教師應指出分子計算的優缺點以及在計算能力上的巨大潛力。

第四部分：細胞自動機和集群計算。這個部分主要討論群體計算，一方面，從細胞自動機的形式化闡述及其所帶來的哲學意義出發，描述細胞自動機在計算機交叉學科上的運用；另一方面，介紹集群計算，以歐盟“藍腦計劃”為出發點，闡述如何從硬件體系和軟件體系上用計算機架構類神經元的協同合作方式。

第五部分：量子計算。從基本的量子力學知識開始，完整闡述量子計算的基本概念、量子信息、量子計算機和量子通信。量子計算機的構建除了要包含最基本的操作外，還需要介紹基本的量子計算機體系結構、計算載體等知識，加深對量子計算的理解，最后介紹的量子通信。這種已經應用在實際生活中的量子計算，更貼合實際。

以上5個專題，結構清晰，分工明確。第一部分討論經典計算的困境，第二部分討論經典計算機的發展瓶頸，從第三部分開始，引入非經典計算模型，分別從生物學和計算機科學的交叉學科DNA計算、細胞自動機和集群計算、量子計算3個方面進行學習。5個專題，完成了對非經典計算中前沿熱門計算模式的闡述，引導了學生對于前沿學科的認識和思考。

4非經典計算課程授課方式

本課程屬于本科三年級第三學期的課程，授課除了上文提到的內容之外，另一個更重要的方面是引導學生對學科前沿以及熱點內容的跟蹤和思考。因此在教學方式上，我們采取了教師授課及學生調查報告相結合的形式。教師上課對應課程的基本內容，學生調查報告對應學科前沿跟蹤與思考。

5個專題內容的授課經過了如下設計。在每個專題的授課結束后，布置相關專題內的一些熱點、難點問題供學生課后查閱、討論和思考。每個專題由學生自主報名，學生需要對相關內容進行跟蹤，查閱近5年的科技文獻，總結出論文綜述，并準備10分鐘左右的課堂報告，教師針對課堂報告指出相關的問題，由學生課后進行進一步的思考和再次的文獻查閱，形成最終報告后提交課程論文。

這樣的課程設計安排，可以很好地實現教學相長。在學生方面，促使學生除了上課聽課，必須主動參與文獻的查詢過程，主動對授課內容或延展部分的概念進行思考。由于提供給學生選擇專題的自由，所以也可以大大提高學生的積極性，讓學生可以從感興趣的角度對本門課程涵蓋的內容進行調查，從而獲得更加深刻的上課體驗。最后，由于每個學生選擇的題目必須提前匯總，不能與別人重復，所以在其聽取其他學生的報告過程中，學生可以更廣地拓展自己的知識面。對于授課教師而言，能夠保持對該門課程研究現狀的實時性跟蹤，更加全面地更新課程內容，還可以將學生查閱的重要理論和知識補充到課程基本內容中，同時促進教師與學生之間的互動，活躍課堂氣氛，提高教學質量。

5關于非經典計算課程的幾點思考

課程從廈門大學智能科學與技術系建系之初開始構思和授課，在授課過程中不斷調整教學內容和課程設計，緊緊圍繞學生的反饋完善課程建設。關于非經典計算課程的幾點教學經驗可以總結如下。

1）增加課時，優化對課程設計的安排。

2015年開始，由于學科教學計劃的調整，非經典計算課程由最初的20課時拓展為30課時，集中在本科三年級第三學期進行講授，一共5周，每周6課時。課時安排上，除了增加教學內容，更加強了對學生的文獻查閱和報告部分的考查。在論文報告環節，爭取做到有目標、有指導、有結論、有總結。學生所做的報告除了在初始選題階段要有區別之外，還要求有一定的文獻查閱難度。從選題確定，到針對報告指出具體的問題，要求學生根據教師指出的問題進行進一步的思考和資料查閱，最后形成論文。這樣的安排貫穿整個課程的全過程，學生的參與度獲得了極大的提高。對于教師而言，在學期末總結學生所做的報告內容，并增加本門課的知識點覆蓋程度，對教學也有比較大的促進作用。

2）課程考核方式上的設計。

非經典課程屬于必修課程，在考核方式上除了提交論文外，也必須要有必要的考試環節。在考試環節中，主要考查學生對教師上課內容的理解。在具體授課中，教師從經典計算到非經典計算進行講解，也從算法角度給出了非經典計算強大計算力帶來的改變，既延續了經典算法課程中對算法的介紹和討論方式，又對比了典型問題在經典算法和非經典算法中的不同解決方式。這樣的授課內容作為對算法體系基本知識點的考查，以閉卷考試內容來設計，是十分合適的。課程延展部分的開放知識點由學生的論文及報告內容進行評分衡量。最后，我們將兩個部分的成績作為本門課程的最終成績。

3）課程教材的選定。

由于本門課程是廈門大學智能系的特色課程，所以國內并沒有合適的教材作為授課使用。在積累了幾年的教學經驗后，我們準備著手進行教材的編寫。如何選定更加合理的專題、更為廣泛而前沿的知識，這關系到智能專業對這門課和教材的全局考量。

6結語

廈門大學智能科學與技術系開設的非經典計算是一門對智能專業算法體系進行全局衡量后設計的特色專業課程，這門課程通過擴充計算機學科的算法體系，既能拓展學生的知識面，又能促進學生自主學習的積極性，滿足了智能學科的專業目標和培養人才的目的。如何在今后的教學過程中發掘智能學科的特色，推動智能專業的持續而長期的發展，任重而道遠。

（編輯：孫怡銘）