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

韓　軍　許　可

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

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

關鍵詞：算法；課程建設；實踐

中圖分類號：G642

文獻標識碼：B

1算法課程建設的現狀

1.1課程的定位

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

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

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

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

算法課的先導課為離散數學、程序設計語言基礎和數據結構。

1.2課程的目標

開設算法課的目標在于使學生通過該課程的學習，能夠運用課程所講授的概念和方法更好地進行算法設計，能夠對已有的算法和新設計的算法進行一般的效能和性能上的分析，并進一步提高程序設計的能力。學好該課程的主要目的是打好專業基礎，提高計算機理論和應用水平。

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

1.3課程的主要講授內容

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

1.4課程的授課效果

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

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

1.5教學過程中發現的問題

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

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

另外，部分學生對先導知識的掌握還有欠扎實，對基礎知識和概念的掌握程度成了一些算法內容理解的瓶頸。

2教學方法上的一些實踐經驗

2.1提高學生學習基礎課程的興趣

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

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

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

2.2培養學生提出問題、分析問題和解決問題的能力

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

2.3增強與學生的交流

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

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

2.4注重平時的考核方式

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

3算法課程建設的一些思考

3.1如何進一步提高學生學習算法的積極性

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

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

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

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

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

3.3如何培養學生的研究能力

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

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

●將學生分成若干小組，每組有一個負責人，要求學生利用互聯網等手段去查找相關資料，以培養發現信息和處理信息的能力；

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

3.4如何將教學與目前算法研究的發展相結合

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

4結論

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

參考文獻：

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

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

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

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

[5] 殷人昆,鄧俊輝. 清華大學“數據結構”精品課程建設[J]. 計算機教育,2006,(05).

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

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

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

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

[10] 姜浩. 數據結構教學過程中應重視算法設計與分析能力的培養[J]. 計算機教育,2007,(16).

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

[12] 王金鳳,謝揚. 論“數據結構”教學改革[C]. 2008中國信息技術與應用學術論壇論文集(一),2008.

[13] 楊勇虎,駱偉. 以學習者為中心的“數據結構”教學方法探討[J]. 電腦知識與技術,2008,(13).