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

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

關(guān)鍵詞：非經(jīng)典計算；算法設(shè)計與分析；智能科學(xué)與技術(shù)

1背景

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

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

該課程以軟件理論類課程算法設(shè)計與分析為先導(dǎo)課程，在本科三年級的第一學(xué)期先講授算法知識，在同一學(xué)年度第三學(xué)期講授非經(jīng)典計算的內(nèi)容。教師首先介紹經(jīng)典算法設(shè)計與分析中的各種傳統(tǒng)算法，借由經(jīng)典算法發(fā)展過程中遇到的困境問題引出非經(jīng)典計算的內(nèi)容，前后呼應(yīng)，有助于學(xué)生在智能計算上獲得完整的系統(tǒng)學(xué)習(xí)。

2非經(jīng)典計算在智能科學(xué)與技術(shù)專業(yè)本科教學(xué)算法體系中的地位

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

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

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

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

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

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

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

3非經(jīng)典計算課程內(nèi)容大綱

非經(jīng)典計算課程的主體課程內(nèi)容以專題形式展開，分為5個部分。

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

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

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

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

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

以上5個專題，結(jié)構(gòu)清晰，分工明確。第一部分討論經(jīng)典計算的困境，第二部分討論經(jīng)典計算機的發(fā)展瓶頸，從第三部分開始，引入非經(jīng)典計算模型，分別從生物學(xué)和計算機科學(xué)的交叉學(xué)科DNA計算、細胞自動機和集群計算、量子計算3個方面進行學(xué)習(xí)。5個專題，完成了對非經(jīng)典計算中前沿?zé)衢T計算模式的闡述，引導(dǎo)了學(xué)生對于前沿學(xué)科的認識和思考。

4非經(jīng)典計算課程授課方式

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

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

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

5關(guān)于非經(jīng)典計算課程的幾點思考

課程從廈門大學(xué)智能科學(xué)與技術(shù)系建系之初開始構(gòu)思和授課，在授課過程中不斷調(diào)整教學(xué)內(nèi)容和課程設(shè)計，緊緊圍繞學(xué)生的反饋完善課程建設(shè)。關(guān)于非經(jīng)典計算課程的幾點教學(xué)經(jīng)驗可以總結(jié)如下。

1）增加課時，優(yōu)化對課程設(shè)計的安排。

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

2）課程考核方式上的設(shè)計。

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

3）課程教材的選定。

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

6結(jié)語

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

（編輯：孫怡銘）