算法設計與分析課程教學方法探討

封富君　李新社　姚俊萍

[摘 要]算法設計與分析是計算機專業的一門核心課程，具有較強的理論性和實踐性。結合該課程的教學經驗，對教學內容設置進行探討，同時提出幾種適合于該課程的教學方法，使課程教學達到了較好的教學效果。

[關鍵詞]算法 教學方法 教學實踐

[中圖分類號] G642 [文獻標識碼] A [文章編號] 2095-3437（2014）18-0149-02

算法設計與分析課程是計算機專業為本科生開設的一門必修專業課，主要通過對一些有代表性的算法進行系統學習，使學生掌握算法的設計思想，培養算法設計與分析的能力，提高學生算法編程的實踐能力、知識綜合運用能力和解決實際問題的創新能力。

算法設計與分析課程是理論與實踐并重的課程，但是在教學過程中筆者發現，大部分學生將其視為理論課，對算法思想雖然理解了，但是不能靈活運用，在編程實踐過程中，缺乏解決實際問題的能力。因此，如何提高教學效果，不僅讓學生增加理論知識，同時培養學生的實踐能力，是本課程教學中需要探索的問題，同時也對授課老師提出了挑戰。本文結合算法設計與分析課程的講授經驗，對教學內容設置和教學方法進行探索。

一、目前課程教學中存在的問題

1.算法思想死記硬背，不能舉一反三

在教學過程中，發現學生不能真正理解算法的設計思想，而是死記硬背，不能實現舉一反三的教學效果。出現這種情況的原因，一方面是沒有激發學生的學習興趣以及自主學習的積極性，另一方面是采用的教學方法不靈活，達不到讓學生理解知識的教學目的。因此，該課程教學方法的運用應該考慮如何提高學生學習的興趣，既要有教學方法的多樣性，又要適合該課程的教學。

2.重理論輕實踐

算法設計與分析課程往往以理論教授為主，實踐環節比較薄弱，因此學生有重理論輕實踐的傾向。很多學生雖然理解了算法的設計思想，但是在編程實現算法的過程中總是不能達到滿意的結果，究其原因，是由于動手編程的機會太少，實踐能力較弱。

課程中所涉及的經典算法都是與實際應用聯系緊密的，如果在教學過程中讓學生了解相關算法的實際應用，增強學生提高實踐能力的意識，培養學生的實際編程能力，對學生以后進行計算機科學研究具有重要的作用。在教學過程中應該多增加一些上機實踐課，使學生在實踐的過程中加深對算法思想的理解，增強解決實際問題的能力。

二、課程內容設置

算法設計與分析課程在教學內容的選擇上應該結合學生的知識背景和接受能力，以典型算法的設計思想為主線，既要掌握算法設計的理論知識，又要提高解決問題的實踐能力，同時激發學生自主學習的積極性，使所學內容不局限于書本，而是與實際應用相聯系。因此在課程內容設置上應該注意以下幾個方面：

1.以算法的基本思想作為主線，并緊緊圍繞這條主線，通過具體實例讓學生真正理解算法的思想及其分析問題的方法，在解決問題的過程中加深對知識的理解和應用，并培養學生解決問題的綜合實踐能力。每個典型算法的講解過程是類似的，以講解貪心算法為例，采用問題驅動式方法啟發學員思考并回答以下問題：

（1）貪心算法的起源是怎樣的？為什么會提出這種算法？用于解決哪些問題？

（2）貪心算法的基本思想是什么？需要滿足的兩個要素（貪心選擇性質和最優子結構性質）如何理解？

（3）以最小生成樹問題為例，該問題是否適合用貪心算法解決，如何進行分析？

（4）Prim算法和Kruskal算法的基本思想是什么？二者有何區別，分別適合于解決哪類無向連通帶權圖？

（5）Prim算法和Kruskal算法的時間復雜度如何分析？請進行比較。

（6）分組編程實現Prim算法和Kruskal算法，并研討交流。

如果學生可以把以上所有問題都能夠正確的回答出來，說明對該算法的講解達到了教學目的。由于課程學時的限制，不可能把所有的實例都講到，因此，在教學過程中，選擇典型例題進行講解，并讓學生自學一部分內容，往往可以達到舉一反三的效果。

2.介紹一些經典問題的算法研究新進展，讓學生了解該領域的前沿，為以后的科學研究方向奠定基礎。例如，最短路徑問題的Dijkstra算法目前出現很多的改進，讓學生通過查找文獻資料了解相關的研究進展，并編程實現感興趣的改進算法，培養學生解決問題的科學探索精神。

3.在講解算法的過程中注重與實際的具體應用相聯系，讓學生認識到學習算法的目的就是為了解決實際的問題，達到理論與實際相聯系的目的。例如，在講解最小生成樹和最短路徑時，讓學生知道該算法的設計可以解決城市交通問題或計算機網絡路由問題；回溯法可以應用在電路板排列和圖的著色問題中等。

三、課堂教學方法

1.引入趣味問題，提高學習興趣

通過一些大家比較感興趣的謎題、故事或生活中的常見問題等，引導學生進入課堂的教學內容，同時提高學生的學習興趣。例如，漢諾塔問題可以用遞歸算法解決；棋盤覆蓋問題可以用分治法解決；背包問題可以用貪心法解決；0 / 1背包問題可以用動態規劃法解決；n后問題可以用回溯法解決等等。這些趣味問題，提高了學生學習算法的熱情以及分析問題和解決問題的能力。

2.采用比較教學，加強算法理解

課程中涉及一些基本的算法，包括分治法、動態規劃法、貪心法、回溯法、分支界限法和隨機化法。不同算法的設計思想不同，解決問題的類型不同，算法設計時需要考慮的代碼細節也不同，學生在剛開始學習不同算法時往往容易混淆，如果在教學過程中進行不斷的比較學習就可以加深學生對不同算法的理解，如表1所示。

3.制作動畫演示，提高教學效果

在課程教學中，通過制作動畫演示，把抽象和難以理解的內容直觀形象的展現給學生，這樣可以在有限的學時內，既將算法執行的步驟一步步的展現給學生，也加深了學生對算法的理解，同時提高了教學效果。

在算法設計與分析課程中，易于用動畫演示的算法有：漢諾塔問題的遞歸算法、二分搜索算法、快速排序算法、合并排序算法、單源最短路徑Dijkstra算法、最小生成樹Prim算法和Kruskal算法、n后問題和0 / 1背包問題的回溯算法。通過以上實例和算法的動畫演示，在教學過程中，取得了很好的教學效果。

4.加強上機實驗，培養動手能力

上機實驗教學應該考慮以下幾個問題：

（1）實驗題目的選擇不宜過難，要根據學生的知識水平和目前的實際能力，由易到難的選取一些題目，一方面調動了學生的積極性，另一方面也發揮了學生的主觀能動性。

（2）實驗內容的安排依照教學內容而定，選取一些趣味習題，且面向實際應用，例如：航線選擇問題、錢幣變換問題、最大覆蓋問題、字典序編碼問題、田忌賽馬問題、任務調度問題、購物問題、士兵隊列問題等，這些學生日常生活中常見的問題會引起學生編程的興趣。

（3）為了使學生更好的理解算法思想，可以布置上機大作業，讓學生分組完成不同題目的實驗內容，上交實驗報告，并在課堂中進行匯報，與其他學生分享自己的收獲與經驗。例如，實驗內容可以是0 / 1背包問題的算法設計與分析，或單源最短路徑問題的算法設計與分析等，要求用兩種算法設計并編程實現，并比較不同算法的效率。通過學生提交的大作業情況，以及課堂匯報，可以看出學生基本上都能按照要求完成，并出現了很多新的想法，學生的自信心和創造力得到了激發，達到了較好的教學效果。

（4）對于動手能力較強的學生，可以再增加一些有難度的問題，激發學生的創新能力。讓學生閱讀一些有關算法的文獻，了解當前的算法發展，并編程實現。

四、結束語

為了幫助學生更好的理解算法的思想，同時培養解決問題和分析問題的能力，筆者采取了多樣的教學手段，如引入趣味問題、采用比較教學、制作動畫演示和加強上機實驗，在教學中取得了令人滿意的教學效果。算法設計與分析課程對教師也提出了挑戰，教師不僅應該具有算法的理論知識，還應該具備實踐經驗，在教學過程中，轉變傳統的教學觀念，采用多樣的教學方法，充分調動學生的積極性，鼓勵創新，培養學生分析問題和解決問題的能力，使該課程的教學逐步趨于完善。

[ 參 考 文 獻 ]

[1] 王曉東.計算機算法設計與分析（第4版）[M].北京：電子工業出版社，2012.

[2] Thomas H.Cormen，潘金貴等，譯.算法導論（第2版）[M].北京：機械工業出版社，2008.

[責任編輯：鐘 嵐]