算法設(shè)計與分析課程教學方法探討

封富君　李新社　姚俊萍

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

[關(guān)鍵詞]算法 教學方法 教學實踐

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

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

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

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

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

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

2.重理論輕實踐

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

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

二、課程內(nèi)容設(shè)置

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

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

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

（2）貪心算法的基本思想是什么？需要滿足的兩個要素（貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)）如何理解？

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

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

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

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

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

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

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

三、課堂教學方法

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

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

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

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

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

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

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

4.加強上機實驗，培養(yǎng)動手能力

上機實驗教學應(yīng)該考慮以下幾個問題：

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

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

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

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

四、結(jié)束語

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

[ 參 考 文 獻 ]

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

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

[責任編輯：鐘 嵐]