本科算法課程建設(shè)的一些實踐與思考

韓　軍　許　可

文章編號：1672-5913(2009)07-0064-04

摘要：本文介紹了北京航空航天大學(xué)計算機學(xué)院本科算法課程建設(shè)的現(xiàn)狀，分析了目前教學(xué)中存在的問題，總結(jié)了教學(xué)方法上的實踐經(jīng)驗，并對算法課程的建設(shè)提出了一些思考。

關(guān)鍵詞：算法；課程建設(shè)；實踐

中圖分類號：G642

文獻標(biāo)識碼：B

1算法課程建設(shè)的現(xiàn)狀

1.1課程的定位

《算法與數(shù)據(jù)結(jié)構(gòu)(2)》主要講述基本的算法設(shè)計方法以及對算法的時間、空間和其他方面進行度量分析。

算法，是程序設(shè)計的靈魂。著名的PASCAL之父、結(jié)構(gòu)化程序設(shè)計的首創(chuàng)者、1984年“圖靈獎”獲得者尼克勞斯·沃斯曾說過：“數(shù)據(jù)結(jié)構(gòu)+算法=程序”。這一公式在結(jié)構(gòu)化程序設(shè)計已相當(dāng)成熟的今天仍被視為經(jīng)典。由此可見，算法在計算機科學(xué)中具有不可替代的重要地位。

據(jù)統(tǒng)計，美國2007年綜合排名前50位的大學(xué)，歐洲名校如牛津、劍橋等均開設(shè)了算法課作為計算機專業(yè)的必修課。不僅如此，美國、歐洲一些普通高校的計算機專業(yè)也均開設(shè)了算法課。中國國家211工程重點建設(shè)的100所高等院校中有多于半數(shù)院校的計算機專業(yè)開設(shè)了算法課，國內(nèi)的一流高校也將算法設(shè)計與分析作為計算機專業(yè)本科生培養(yǎng)的重要環(huán)節(jié)。

算法課程是高等學(xué)校計算機專業(yè)重要的專業(yè)基礎(chǔ)課程之一，是計算機程序設(shè)計的重要理論和實踐基礎(chǔ)，是目前國內(nèi)計算機專業(yè)研究生招生考試的首選專業(yè)基礎(chǔ)課程，其獨特的應(yīng)用價值也使其成為信息類專業(yè)的重要課程之一。

算法課的先導(dǎo)課為離散數(shù)學(xué)、程序設(shè)計語言基礎(chǔ)和數(shù)據(jù)結(jié)構(gòu)。

1.2課程的目標(biāo)

開設(shè)算法課的目標(biāo)在于使學(xué)生通過該課程的學(xué)習(xí)，能夠運用課程所講授的概念和方法更好地進行算法設(shè)計，能夠?qū)σ延械乃惴ê托略O(shè)計的算法進行一般的效能和性能上的分析，并進一步提高程序設(shè)計的能力。學(xué)好該課程的主要目的是打好專業(yè)基礎(chǔ)，提高計算機理論和應(yīng)用水平。

因此，我們要求學(xué)生能夠掌握各種基本的算法設(shè)計方法(包括歸結(jié)法、分而治之法、貪心法、動態(tài)規(guī)劃和概率法等)，并能夠掌握基本的算法分析方法(算法的時間復(fù)雜度與空間復(fù)雜度分析)，并在學(xué)習(xí)已有知識的基礎(chǔ)上，加強思考和實踐。

1.3課程的主要講授內(nèi)容

根據(jù)北航學(xué)生的實際情況，算法課程目前分為18學(xué)時，以課堂講授為主，輔以參考資料閱讀以及每章的課后作業(yè)和練習(xí)題。授課內(nèi)容分為七章，分別為：算法分析的基礎(chǔ)知識、歸結(jié)法和分而治之法、貪心算法、動態(tài)規(guī)劃算法、概率算法、下界分析和求解NP完全問題的算法設(shè)計。重點講授內(nèi)容包括：算法的控制結(jié)構(gòu)、算法的復(fù)雜性分析、歸結(jié)法和分而治之法、貪心算法的基本思想及特點、設(shè)計動態(tài)規(guī)劃算法需要具有的前提及一般設(shè)計思路、主要的下界計算方法、回溯法和局部搜索算法等。

1.4課程的授課效果

通過課堂上學(xué)生的聽課情況、對問題的反應(yīng)程度以及對小測驗的完成情況，我們可以看出部分學(xué)生對該課的興趣和重視程度較高、預(yù)習(xí)工作做得較好，能將老師當(dāng)堂所講的內(nèi)容消化和掌握；大多數(shù)學(xué)生能夠在課堂上對老師所講解的內(nèi)容加以理解，并能在課后加以復(fù)習(xí)并掌握；一些學(xué)生盡管沒有在課堂上對內(nèi)容理解和消化，但仍能通過下課向老師提問或課后發(fā)Email給老師的方式向老師詢問未理解的問題來加以反饋。

從課后作業(yè)的完成質(zhì)量以及期末考試的卷面成績來看，絕大多數(shù)學(xué)生能在學(xué)完算法課之后對計算機算法有一定的理解，并具備一定的算法設(shè)計與分析能力，達到該課程的基本要求，甚至有一些學(xué)生就此對算法產(chǎn)生了較濃厚的興趣，并能在以后的學(xué)習(xí)時間里繼續(xù)深入學(xué)習(xí)算法。課程達到了較好的授課效果。

1.5教學(xué)過程中發(fā)現(xiàn)的問題

在教學(xué)過程中，學(xué)生普遍暴露出不愿深入思考、不愛動手實踐的問題。盡管這些原則在平時的授課過程中再三地被強調(diào)，但能按照老師建議去做的人并不多，僅限于少數(shù)對算法有較大興趣的學(xué)生。

從試卷情況來看，一些同學(xué)仍然缺乏將算法思想應(yīng)用于同類問題求解中的能力，出現(xiàn)了同類問題不知道用同類算法求解的情況。究其原因在于未能將算法思想深入理解，做過的習(xí)題較少，對于同類問題無從下手。為應(yīng)付考試而死記硬背某些算法，這是學(xué)習(xí)算法的大忌。

另外，部分學(xué)生對先導(dǎo)知識的掌握還有欠扎實，對基礎(chǔ)知識和概念的掌握程度成了一些算法內(nèi)容理解的瓶頸。

2教學(xué)方法上的一些實踐經(jīng)驗

2.1提高學(xué)生學(xué)習(xí)基礎(chǔ)課程的興趣

從一定角度講，興趣是最好的老師，因此我們在講述課程的過程中會經(jīng)常從學(xué)生們感興趣的問題入手，為他們創(chuàng)造易于理解問題、加深記憶的活躍的課堂氣氛和環(huán)境。

我們在介紹一個算法問題時，首先介紹問題的背景，如河內(nèi)塔游戲、斐波那契數(shù)列等。在教學(xué)過程中，我們將本課程學(xué)科的發(fā)展歷史、前沿知識和自己從事科研實踐的體會與成果貫穿于教學(xué)中，例如蒙特卡洛概率算法與SAT問題等均是兩位授課教師曾深入研究過的算法和問題。另外，我們還結(jié)合課程內(nèi)容介紹了Google和Microsoft等知名IT公司的面試題目，激發(fā)學(xué)生對算法的興趣，令學(xué)生積極思考并展開討論。

算法本身的概念與理論是抽象的，但具體問題又是實際的、易懂的、有趣的。在教學(xué)過程中，只有通過具體問題，引申出求解該問題的有效算法，同時有效借助多媒體教學(xué)靈活而快捷的特點，將抽象的算法具體化講解，才能提高學(xué)生學(xué)習(xí)基礎(chǔ)課程的興趣。在每個問題的講解過程中，我們盡量采用圖文并茂的方式，將問題刻畫得清楚明了，實踐證明，該方法取得了較好的效果。

2.2培養(yǎng)學(xué)生提出問題、分析問題和解決問題的能力

在教學(xué)中，采用啟發(fā)和探索式的教學(xué)方法，注重培養(yǎng)學(xué)生提出問題、分析問題和解決問題的能力。在教學(xué)中，我們本著一系列連貫的思路講授學(xué)習(xí)內(nèi)容，例如：當(dāng)初某個算法問題是怎樣提出來的；求解該問題的方法和策略是如何形成的；如何應(yīng)用這些方法和策略來解決實際問題；對這些方法和策略做進一步的比較、分析和評價。

2.3增強與學(xué)生的交流

輕松活躍的課堂氣氛是激發(fā)學(xué)生聽課興趣，進而達到良好聽課效果的重要保證。在教學(xué)過程中，我們本著以學(xué)生為中心的原則，注重與學(xué)生的交流。通常一個問題、一個提示會達到良好的授課效果，實踐證明，這種方式是有效的。

為了對學(xué)生的基礎(chǔ)知識掌握情況有全面的了解，我們會以調(diào)查問卷的方式獲取每個學(xué)生的學(xué)習(xí)情況信息，通過一些簡單易答的算法題，幫助學(xué)生鞏固基礎(chǔ)知識，使聽課效果更佳。事實證明，通過調(diào)查問卷的開放性問題，我們了解了同學(xué)們大致的想法和對算法課的建議。另外，我們還鼓勵學(xué)生課后通過Email等手段與老師展開交流，并聽取學(xué)生的反饋意見，選取一些有代表性的問題在下一次課堂上講述。

2.4注重平時的考核方式

算法課程的特點是邏輯思維性強。因此，必須通過典型例子強化一般性問題。同時，為避免同學(xué)中大量存在的“平時不學(xué)習(xí)，考試搞突擊”現(xiàn)象的發(fā)生，我們注重對學(xué)生平時的考核，并主要采取課后作業(yè)的方式。為加強學(xué)生的動手實踐能力，我們要求學(xué)生用某一種語言(C、C++、Java、Delphi等)對作業(yè)問題進行實現(xiàn)。通過適當(dāng)調(diào)整課后作業(yè)在期末總成績中的比重，督促鼓勵同學(xué)自己動手進行編程實踐，進而有效地指導(dǎo)基礎(chǔ)理論知識的學(xué)習(xí)。從學(xué)生提交的課后作業(yè)程序來看，絕大多數(shù)同學(xué)理解了求解問題所使用的算法基本原理。

3算法課程建設(shè)的一些思考

3.1如何進一步提高學(xué)生學(xué)習(xí)算法的積極性

在教學(xué)過程中，我們本著培養(yǎng)學(xué)生學(xué)習(xí)算法興趣的原則，在授課過程中采用引導(dǎo)和鼓勵等方式，提高學(xué)生學(xué)習(xí)算法的積極性，并取得了較好的效果。

為了進一步提高學(xué)生學(xué)習(xí)算法的積極性，我們擬建設(shè)一個算法課程網(wǎng)站，并逐步向網(wǎng)站中添加在線求解問題(類似目前國內(nèi)多所大學(xué)的ACM網(wǎng)站)和算法討論區(qū)等諸多板塊，加強與同學(xué)的交流。鼓勵同學(xué)利用課余時間參加在線答題和算法討論。

通過平時與學(xué)生的交流我們發(fā)現(xiàn)，學(xué)生更愿意將理論知識實際化，在現(xiàn)實生活中尋找所學(xué)知識的應(yīng)用。例如，在一次與學(xué)生的交流中，我們談到在商場購物打折優(yōu)惠卷的優(yōu)化使用問題，之后一位學(xué)生便自己編寫了一個針對商場搞優(yōu)惠活動時不同折扣、返卷及優(yōu)惠卷使用規(guī)則的購物優(yōu)化算法程序，并在某商場進行了現(xiàn)場的咨詢服務(wù)。這種勤于思考和實踐的表現(xiàn)受到了教師的表揚和鼓勵，毫無疑問，這種學(xué)以致用的學(xué)習(xí)方式是非常有益的。

3.2是否需要介紹模擬退火和遺傳算法等啟發(fā)式算法

在以往的教學(xué)中，我們主要為學(xué)生講述求解問題的精確算法，如貪心策略、動態(tài)規(guī)劃等。但隨著當(dāng)前算法理論的深入研究，眾多學(xué)者越來越關(guān)注和研究難問題及啟發(fā)式算法。因此，為了鼓勵和啟發(fā)學(xué)生深入學(xué)習(xí)算法，我們正在考慮是否在以后的授課中加入對模擬退火和遺傳算法等啟發(fā)式算法的介紹，為學(xué)生以后對算法的深入研究起到拋磚引玉的作用。

3.3如何培養(yǎng)學(xué)生的研究能力

我們認為，北航的學(xué)生與國內(nèi)其他一流高校的計算機專業(yè)學(xué)生相比，普遍動手能力強，但具有研究能力的拔尖學(xué)生少，去國外一流高校深造和頂尖研究單位工作的學(xué)生則更少。如何培養(yǎng)學(xué)生的研究能力，是我們目前面臨的問題之一。我們認為，培養(yǎng)學(xué)生的研究興趣，激發(fā)學(xué)生的研究熱情，為學(xué)生營造良好的學(xué)術(shù)研究氛圍，鼓勵學(xué)生參加競賽，與國際接軌，是培養(yǎng)研究型人才的重要手段。因此，在教學(xué)工作中，我們試圖采取有力有效的方法帶動學(xué)生參與學(xué)術(shù)研究和項目工作，如：

●在教學(xué)中布置一些研究性的題目并介紹相關(guān)的背景知識(如SAT問題的求解算法)；

●將學(xué)生分成若干小組，每組有一個負責(zé)人，要求學(xué)生利用互聯(lián)網(wǎng)等手段去查找相關(guān)資料，以培養(yǎng)發(fā)現(xiàn)信息和處理信息的能力；

●鼓勵學(xué)生提出自己的求解算法進行計算實驗分析，最后撰寫技術(shù)報告，并進行組內(nèi)排名，從中挑一些優(yōu)秀的算法參加國際算法競賽。

3.4如何將教學(xué)與目前算法研究的發(fā)展相結(jié)合

近些年，算法的研究發(fā)展呈現(xiàn)了一些新特點，不完全算法的發(fā)展很快。國際算法競賽的興起亦對中國大學(xué)計算機專業(yè)的大學(xué)生產(chǎn)生了較深的影響。為了將教學(xué)與目前算法研究的發(fā)展相結(jié)合，除了在加強教師自身科研工作的同時，我們也在試著尋找當(dāng)前科研工作在教學(xué)內(nèi)容中的切入點。讓學(xué)生在學(xué)習(xí)基礎(chǔ)內(nèi)容的同時，通過聽取教師的切身體會和指導(dǎo)，把握學(xué)術(shù)研究的動態(tài)。

4結(jié)論

本文總結(jié)了北航計算機學(xué)院本科算法課程建設(shè)的現(xiàn)狀和存在的問題，介紹了激發(fā)學(xué)生的學(xué)習(xí)興趣和注重學(xué)生的能力培養(yǎng)等方面的一點經(jīng)驗，提出了在增加授課內(nèi)容、培養(yǎng)研究型人才和進一步提高學(xué)生學(xué)習(xí)的積極性等方面的一些思考，并強調(diào)了將教學(xué)與目前算法研究的發(fā)展相結(jié)合的重要性，而未來我院本科算法課程的建設(shè)也請各位老師提出寶貴意見。

參考文獻：

[1] Top 100 Universities:Top 100 Colleges and Universities[N/OL]. http://www.ulinks.com.

[2] 王曉東. 計算機算法設(shè)計與分析(第二版)[M]. 北京:電子工業(yè)出版社,2004.

[3] Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein. Introduction to Algorithms (Second Edition). 北京:高等教育出版社,2002.

[4] 陳國龍,王曉東,傅清祥. “算法與數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)改革和實踐[J]. 高等理科教育,2003,(03).

[5] 殷人昆,鄧俊輝. 清華大學(xué)“數(shù)據(jù)結(jié)構(gòu)”精品課程建設(shè)[J]. 計算機教育,2006,(05).

[6] 廖明宏,張巖,李秀坤,李治軍. 哈爾濱工業(yè)大學(xué)“數(shù)據(jù)結(jié)構(gòu)與算法” 精品課程介紹[J]. 計算機教育,2006,(05).

[7] 王綿森. 以現(xiàn)代教育理念為指導(dǎo),加強精品課程建設(shè)——建設(shè)精品課程的幾點體會[J]. 中國大學(xué)教學(xué),2006,(05).

[8] 楊圣洪. 編程訓(xùn)練與課程學(xué)習(xí)的相互滲透[J]. 計算機教育,2006,(10).

[9] 吳英杰,王一蕾,王曉東. 面向問題求解的實踐教學(xué)模式——“算法與數(shù)據(jù)結(jié)構(gòu)”實踐教學(xué)改革[J]. 計算機教育,2007,(07).

[10] 姜浩. 數(shù)據(jù)結(jié)構(gòu)教學(xué)過程中應(yīng)重視算法設(shè)計與分析能力的培養(yǎng)[J]. 計算機教育,2007,(16).

[11] 李軍利,卜曉燕. 精品課程與精品課程網(wǎng)站的建設(shè)[J]. 教育與職業(yè),2007,(14).

[12] 王金鳳,謝揚. 論“數(shù)據(jù)結(jié)構(gòu)”教學(xué)改革[C]. 2008中國信息技術(shù)與應(yīng)用學(xué)術(shù)論壇論文集(一),2008.

[13] 楊勇虎,駱偉. 以學(xué)習(xí)者為中心的“數(shù)據(jù)結(jié)構(gòu)”教學(xué)方法探討[J]. 電腦知識與技術(shù),2008,(13).