封富君　李新社　姚俊萍

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

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

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

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

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

一、目前課程教學(xué)中存在的問題

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

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

2.重理論輕實踐

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三、課堂教學(xué)方法

1.引入趣味問題，提高學(xué)習(xí)興趣

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

2.采用比較教學(xué)，加強算法理解

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

3.制作動畫演示，提高教學(xué)效果

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

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

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

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

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

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

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

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

四、結(jié)束語

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

[ 參 考 文 獻 ]

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

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

[責(zé)任編輯：鐘 嵐]