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

摘要：“算法設計與分析”是計算機科學與技術學科的核心課程之一。本文針對目前該課程教學中存在的問題，就教學內容、教學方法、教學手段、實驗環節和考核方式等五個方面的改革進行了探討。

關鍵詞：算法設計與分析；計算機專業；教學改革

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

1教學內容的改革

學生普遍反映“算法設計與分析”這門課難學，它不是靠死記硬背能夠掌握的，必須分析理解并且靈活應用，要求學生具有較好的數學和數據結構基礎，為了幫助學生渡過“難”關，作為教師，關鍵要選擇好教學內容。總的原則是：內容難度適中，結合實際問題和相關課程的知識講解算法設計技巧及算法分析方法，使學生既能理解，又能拓展創新。給本科生講授這門課，切忌講授太深奧的理論(如計算復雜性理論)，使學生失去學習的信心；同時，也切忌對數據結構課程內容的重復講授，使學生失去興趣。

目前，該門課程的大多數教材或多或少重復數據結構教材的內容，有待改編教材內容，保留經典算法部分，如涉及分治法、動態規劃法、貪心法、回溯法等有關策略的典型算法；增加算法設計與分析領域的新成果，如隨機算法、近似算法等。此外，教師應不局限于教材內容，可將計算機領域熱門話題或前沿知識擴展到教學中，如增加分布式計算、并行計算等方面算法的介紹。這門課程屬于計算機專業的綜合性課程，它還可以深化其它專業課程的學習與理解。例如“操作系統”課程中的資源分配算法、進程調度算法，“計算機網絡”課程中的路由算法等都應用了算法設計中的基本方法。另外，為了激發學生的學習興趣，應密切關注計算機算法的業內發展，充分利用互聯網信息資源，將新知識信息融入教學之中。

2教學方法的改革

(1) 加強分析和比較

對于排序、查找等典型問題，目前已有多種算法，它們的思路和效率各不相同。在給學生講解這些算法時，除了把它們的含義講解清楚外，還要加強橫向比較，這樣可以幫助學生把所學知識融會貫通，提高綜合分析的能力。例如，可以總結了幾種經典的排序算法的平均復雜度和最壞復雜度。通過比較，可以清楚地看出，堆排序、歸并排序和快速排序具有最優的平均復雜度。如果進一步考慮最壞復雜度，則堆排序和歸并排序的優勢更大。再比如對于最大子段和問題，可以采用簡單算法、分治算法和動態規劃算法分別解決，可以比較它們的復雜性，加深對算法的理解。

(2) 注重與數據結構內容相結合

算法和數據結構有著密不可分的聯系，著名計算機科學家沃思更是提出“數據結構+算法一程序”的觀點。每個算法都是建立在某種數據結構的基礎之上，一個算法不可能脫離數據結構而孤立存在。因此，學好算法需要認真掌握數據結構的內容。例如，哈夫曼算法中要求構造的哈夫曼編碼樹，其實是一個最優二叉樹。學生在前期數據結構課程中已經學習過最優二叉樹的相關知識，教師可以先溫習這部分內容，然后以一種具體應用的形式引出哈夫曼編碼樹。這種溫故而知新的教學方法，可以有效消除同學們在學習過程中的畏難情緒。

(3) 將理論分析和實際應用結合起來

算法本身相對來說比較枯燥，如果能拓展教材中的內容，在加強理論說明的同時，與實際應用聯系起來，可以使學生學起來更有興趣。例如，在教授哈夫曼算法時，我們首先由最優二叉樹引出哈夫曼編碼樹的構造方法，然后通過驗證它的貪婪選擇性質和最優子結構性質 ，從理論上證明哈夫曼編碼是平均碼長最短的整數碼。

(4) 強化習題討論教學環節

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

3教學手段的改革

將傳統教學方法與現代化教學手段相結合，也是我們教學改革的舉措之一。為了在有限的教學時間內，增加單位

時間的信息含量，將有限精力與時間用于剖析課程內容的重點難點。把抽象難于理解的內容直觀形象地展現，在該課程教學中，引入多媒體教學手段，制作課件，開展計算機輔助教學。計算機輔助教學的特點是將算法設計中較抽象的設計思想以動畫形式演示出來，既可以節省教師在課堂上的板書時間，也可以將算法設計的一系列步驟直觀展示在學生面前。如利用貪婪法解決單源的最短路徑問題時，利用課件可以讓學生更清楚了解求解指定頂點到其他頂點最短路徑的過程以及最終求解結果，更好掌握貪婪法的設計思想。采用這種教學方式可以更好發揮學生能動性，從而提高學生學習興趣。此外，可以把講課內容制作成PPT在校園網上發布，如果學生沒聽懂，可以上網察看，方便學生課后復習。將課件與幻燈片結合起來，教學效果有較大提高。

4實驗環節的改革

對于迅速發展起來的計算機科學技術和相關專業而言，實驗與課程設計仍然是教學過程薄弱環節和難點，而它們是理論教學不可替代的。“算法設計與分析”這門課理論性較強，同時實踐性也很強。此外上機實驗不但能培養學生的實踐能力，而且，對編程也有所提高，由于算法設計與分析不但要求適合于計算機上使用，而且該算法必須具有算法的穩定性、理論的可靠性及計算的復雜性，因而上機實踐是必不可少的。這也是一個消化所學內容的過程，以此來驗證各種方法的優缺點，同時也是改進編寫計算機程序的過程，通過自己的親自編程實踐，來解決一些簡單的實際問題，了解了解決問題的基本過程，思維方式及規律，也是充分調動學生參與主動性的過程，做到學有所用。這樣不僅使學生掌握了算法設計與分析的理論知識，學會了解決一些簡單問題的方法更重要的是了解和體會了數學的用處。尤其是近幾年來全國大學生數學建模比賽，更是體現了利用數學思想提煉出解決一些實際問題的數學模型，然后從理論上進行分析研究，最后編制實驗程序，上機實踐，使得問題得以解決，這就是理論與實踐的完美結合。

學生的接收能力、理解能力、編程能力以及創新能力各不相同，需要因材施教，區別對待。因此，可以設計以下三個不同層次的要求，最低要求必須完成第一層次的實驗。(1)選擇某些經典問題，采用不同算法實現，輸入大量數據，測試程序運行時間，與理論結果進行比較。如0～1背包問題，可以選用動態規劃、回溯法、分支限界法等算法，將三個算法的實際執行時間進行比較，從實驗結果證明理論分析的正確性。(2)設計一個實際問題，能夠應用所學算法或經過變換解決。這可以充分發揮學生的主觀能動性。例如流水作業調度算法可以應用到產品生產安排、設備分配等實際問題，旅行售貨員問題的算法可以應用到郵遞員送信、物流配送線路選擇等實際應用問題。(3)提出一個綜合性問題，利用所學的知識，設計出新的算法，并用實驗模擬驗證。例如曾經有學生提出旅行社優化安排旅游線路的問題，設計出綜合考慮旅客、季節、費用等因素的優化算法。

另外對實驗結果可以要求可視化，如講授回溯算法這章內容時，一般以n皇后問題為例講解回溯算法，因此可以以n皇后問題為內容設置一個實驗，同時要求對每個解實現可視化。如產生如下圖所示的界面，可以顯示每一個解，這樣比較直觀形象。下圖顯示了列出了8皇后的所有92個解，并顯示了第4個解。

5考核形式的改革

與外國學生相比，中國學生理論基礎扎實，從老師和教材吸取的知識較多，對講授的內容掌握牢靠；但創新能力較差，不善于發現問題、提出問題，缺乏實際解決問題的能力。這種現象的根源在于考試制度，包括考核形式與評分標準。目前，算法設計與分析這門課程的成績大多按兩部分計算：一部分是平時作業情況，占總成績的30％～40％；另一部分是閉卷考試，占總成績的60％～70％。這樣，大部分學生只重視閉卷考試部分，不重視平時學習，更不會挖掘潛力進行創新研究。因此，考試形式和評分標準的改革是中國教育體制改革的重中之重，尤其對于本科生以及本科學歷以上的高級人才的培養更為重要。就“算法設計與分析”這門課程，筆者提出了考核內容及所占總分的比例。平時課堂表現占10%、作業占10%、實驗成績占30％，而閉卷考試只占總成績的60％。這樣更注重考核學生學習過程中的表現情況，有利于促進學生積極主動學習，培養創新能力。

參考文獻：

[1] 孫紅麗，葉斌. 淺談算法設計與分析課程的教學改革[J]. 太原教育學院學報，2005，23(4):54-56.

[2] 巫小蓉，李霞. 計算機算法設計與分析教學經驗淺談[J]. 廣西大學梧州分校學報，2004，14(3):71-73.

[3] 於東軍，李勇智. 算法設計與分析教學改革初探[J]. 中國輕工教育，2005，(3):55-56.

[4] 劉波. “算法設計與分析”教學探討[J]. 高等理科教育，2007，(4):78-80.

[5] 張玉清，王群. “算法分析與設計”教學方法的探索[J]. 中國地質教育，2006，(4):119-120.