“算法設計與分析”課程教學改革初探

摘要：“算法設計與分析”是工程碩士研究生的一門核心課程，本文結合算法設計與分析課程的特點，對該課程的教學內容、教學方法與教學手段等三方面的改革做了一些有益的探討。

關鍵詞：算法設計；算法分析；教學方法

中圖分類號：G642文獻標識碼：A

1引言

“算法設計與分析”是計算機專業高年級學生與研究生的重要專業課，同時還是一門與計算機有關的非計算機專業如管理信息、系統工程、應用數學與計算數學的專業課。本課程與前驅課程“離散數學”、“程序設計”、“計算方法”、“數據結構”等聯系緊密，而且實踐性很強，各種經典的算法思想如動態規劃法、回溯法等，從一系列經典問題的解決方案中提煉出來后，再應用于實際問題的解決。但是我們在教學過程中發現，大部分學生把該課程看成單純的理論課學習，對算法設計思想死記硬背，而不是靈活運用，不能對一種設計方法舉一反三。這就要求教師思考如何把其與程序設計教學相結合，而不是將孤立的算法設計思想傳授給學生。

2教學內容

工程碩士研究生的算法設計與分析主要目的是講授計算機應用中常常遇到的系統軟件或應用軟件開發中的具有廣泛工程背景的典型非數值計算問題的解法，講授設計與分析各種算法的基本原理思想、方法與技術，重點闡述算法設計的典型方法，分析不同算法的時間和空間復雜度，建立計算機與應用問題之間的橋梁，從而使學生在選擇或者設計算法時可以對其進行時空耗費分析，并使所設計的算法時空復雜性最優，進而為其編寫出高效程序、開發出優秀軟件系統奠定基礎。通過本課程的學習，學生應基本掌握遞歸、分治法、動態規劃、貪心算法、回溯法、分支限界法等經典算法的設計和分析方法，學習為解決應用中的非數值計算問題建立計算機解題模型的設計和分析算法的理論基礎，并掌握對求解典型問題必要的算法設計技術和編程技巧。

計算機科學的特點決定了它的內容和手段始終處在不斷革新和變化的過程中。根據工程碩士研究生大多有一定的工程經驗，有一些工程需求。因此，本課程的授課內容除了講授經典算法設計理論外，應結合教師科研實際，逐步引入并行算法、現代啟發式搜索算法等先進內容，盡量反映本學科領域最新的學術和科技成果，使學生既能夯實基礎，也能擴大眼界。另外，算法的應用領域很廣，基本上只要有計算機的地方就會有算法。我們在教學過程中還介紹了計算機其他領域方面的算法，如數據壓縮算法、并行算法、神經網絡等等。雖然只能粗略的介紹其中很小的一部分，但是可以用很淺顯的例子進行說明，讓學生了解各個領域算法的大致思想，拓寬他們的專業知識面。

研究新動向融會進去，從而使學生可以用基本理論去解決遇到的新問題，增強學習興趣，使其感到學有所用，也是如何在有限的教學時間內講清基本理論知識，同時把本課程教學改革的關鍵所在。目前，計算機專業學生使用的“算法設計與分析”教材內容較多，而工程碩士研究生學時有限，這就要求我們在教學中力求做到抓住關鍵，突出重點，解決難點，我們要把主要時間花在講解重要概念、基本設計思想和基本方法上，引導學生掌握課程內容的內在關聯性，比較不同算法特點，舉一反三，比如背包問題，在講課中用圖解法、遞推法等多種方式，讓學生由淺入深逐漸理解動態規劃算法原理。在規定的課時內，既完成教學任務，也同時提高教學效果。在具體操作上，我們以一些基本算法設計技術內容為主線，以其基本設計思想的具體應用及分析為重點，講清楚算法設計及分析問題。另外，為了激發學生的學習興趣，密切關注計算機算法的業內發展，充分利用互聯網信息資源，跟蹤計算機科學的最新進展，將新知識信息融入教學之中。

3教學方法

教學方法從傳統的“粉筆+黑板”模式為主過渡到“計算機+大屏幕”為主的授課模式。授課的電子教案開始時以靜態文字為主的PowerPoint幻燈片方式提供，現在則在教案中穿插曲可動態演示算法的多媒體課件，在大屏幕上展示抽象算法的執行過程，輔之以板書交流，從而大大增加了從教師到學生傳遞的信息量和信息種類，有助于建立從感性到理性的深入理解及相關技術掌握運用。

(1) 啟發式教學

抽象、理論、分析是計算機科學與技術學科的三種基本形態。在基礎課的教學中應將上述三種基本形態貫穿于教學的始終，融合新概念將各分支學科的內在聯系串聯起來。在計算機專業課教學中針對不同教學內容采取多樣化教學方式，以啟發式教學為主，輔以其他教學方法。

啟發式教學是從介紹典型應用問題入手，將計算機算法的構建過程展現出來，同時提出新的算法設計問題，以便讓學生進行思考和研究。變單向傳輸式教學為雙向互動式教學， 變以強調抽象算法設計為主的理論講授為探究解決應用問題為主的設計引導式講授。對一組相關的算法，分析、闡明不同算法的優、缺點，啟發學生在能夠解決問題的前提下探索新的設計思路，培養學生的創新思維，誘導學生深入思考，實現教與學的互動，激發學生的創造性，達到創新能力培養和提高教學效果的目的。為此，我們在課前應充分備課，一方面吃透算法設計與分析的基本理論知識，另一方面則要多了解其最新應用發展狀況。另外，在講課方式上，采取“系統講解基本理論思想、反復強調重點難點、啟發性講解引申知識內容”的方式，啟發并引導學生主動探索知識，既注意了基礎的特點，同時又給學生提供了一個發散的思維空間。

(2) 理論聯系實際

計算機科學非常強調理論聯系實際，算法本身相對來說比較枯燥，特別是對于工程碩士研究生，他們更注重應用，如果能與實際應用聯系起來，可以使學生學起來更有興趣。在教學中，算法設計技術、算法分析技術、基本設計思想及其應用是我們教學的重點及難點，講課過程中，我們要把基本算法設計方法的思想及應用結合起來講授，由簡單應用到解決復雜問題，使學生循序漸進接受算法基本思想，從而掌握所學知識及相應的思維方法。同時在此過程中，不失時機提出一些問題來引導學生積極思考。如貪心算法的思想很簡單，也可以用于處理最優化問題，但是由于用此方法解決問題時優化測度要根據具體的問題自己選取，故用此方法設計算法時對于解決不同問題其具體實現方式也是不同的。以找硬幣為例，希望找的硬幣個數最少，如果硬幣面值為：1分、5分和11分，要找給顧客為15分，對貪心算法而言，則需要1枚11分，4枚1分，共用5枚硬幣；而用動態規劃法求解，得出只用3枚5分硬幣就可以了。從這個小例子可以看出，貪心算法雖然好用，但對于有些問題采用貪心算法不一定能得到最優解。為了讓學生對算法設計有較完整的認識，我們引導學生思考對于同一問題時，選擇不同算法會有什么樣的結果，如調度問題、0/1背包問題、城市交通問題、場地租用問題等等。算法課不再是紙上談兵，而是實際中的運用，這種教學方式讓學生帶著問題學習，可以提高他們學習的興趣，更重要的是可以培養他們發現問題、分析問題及解決問題的意識和能力，通過對不同的學生提出不同難度級別的問題，配合給出不同級別的提示來調動不同學生的主動性。

(3) 強化討論教學環節

針對理論課教學中一些尚未理解透徹、容易出錯的問題，在教學中進行分析討論。選題要有代表性，不選難題繁題，但是要有討論引申之內容。通過一題多解和分析，加深學生對基本理論知識的理解而起到舉一反三、觸類旁通的作用，有助于學生結合實際進行具體應用。討論問題的同時，學生又會提出新問題，從而在討論問題、解決問題的過程中，使學生獨立思考能力得到培養和鍛煉。在講授遞歸方程解法時，以漢諾塔問題的遞歸方程為例，可以采用三種解法中任一個求解。同時可以聯系時間復雜性分析其時間耗費，從而引導學生思考三種求解方法各自的適用范圍及其優缺點。

4教學手段

將傳統教學方法與現代化教學手段相結合，也是我們教學改革的舉措之一。為了在有限的教學時間內，增加單位時間的信息含量，將有限精力與時間用于剖析課程內容的重點難點。把抽象難于理解的內容直觀形象地展現。在該課程教學中，引入多媒體教學手段，制作課件，開展計算機輔助教學。計算機輔助教學的特點是將算法設計中較抽象的設計思想以動畫形式演示出來，既可以節省教師在課堂上的板書時間，也可以將算法設計的一系列步驟直觀展示在學生面前。如利用貪心法解決單源的最短路徑問題時，利用課件可以讓學生更清楚了解求解指定頂點到其他頂點最短路徑的過程以及最終求解結果，更好掌握貪心算法的設計思想。課堂教學充分采用多媒體教學手段，使學生學得直觀、學得輕松、學得活躍，并提高課時利用率，增加課堂信息量，可以更好地發揮學生的能動性，從而提高學生學習興趣。

另外，我們開設“算法設計與分析”課程網站，在網站上配套電子教案、作業及其他課程資源，也是將傳統教學方法與現代化教學手段相結合的舉措之一。此外，可以把講課內容制作成電子課件在校園網上發布，對工程碩士研究生有時可能因為工作原因不能到學校上課，或者學生沒聽懂，可以上網察看，方便學生自學、復習。

此外，我們也改進了考核方式，將傳統、單一的閉卷考核方式，改變為對平時課堂學習、課外設計(課外作業)、

期末算法設計與分析筆試與交報告等多環節考核相結合的考核方式，逐漸加大對算法設計和程序開發能力的考核力度，激發學生自主學習、自主訓練的興趣和熱情，避免產生“高分低能”的現象。

參考文獻：

[1] 王曉東. 算法設計與分析[M]. 北京:清華大學出版社，2003.

[2] 蘇德富. 計算機算法設計與分析[M]. 北京:電子工業出版社，2000.

[3] 陳國良. 并行算法實踐[M]. 北京:高等教育出版社，2002.

[4] 陳莉. 計算機專業基礎課教學改革探索[J]. 高等理科教育，2004，(2):51-55．

First Step towards the Teaching Reform of Algorithm Design and Analysis

ZHENG Hong， SHAO Zhi-qing， FU Hai-bo

(College of Information Science and Engineering， East China University of Science and Technology， Shanghai 200237)

Abstract: Algorithm design and analysis course is a core course for engineering graduate students．This paper integrate with algorithm design and analysis course's characteristics，make beneficial discuss in the Reform of teaching method， teaching content and teaching instrument．

Key words: Algorithm Design， Algorithm Analysis， Teaching Reform