比較教學法在“算法分析與設計”課程教學中的應用

劉偉

【摘要】“算法分析與設計”是計算機類專業的核心專業課程之一。在“算法分析與設計”教學過程中引入比較教學法，從同一算法求解不同問題、不同算法求解同一問題、同一算法求解同一問題中不同實現方式等多個角度開展比較教學，讓學生更好地歸納和整理所學知識，加深學生對知識的理解，建立相關知識之間的聯系，有效改善教學效果。

【關鍵詞】算法分析與設計 ?比較教學法 ?課程教學

【中圖分類號】G642 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文獻標識碼】A ? ? ?【文章編號】2095-3089（2016）11-0111-02

一、引言

“算法分析與設計”是計算機科學與技術、軟件工程、信息管理與信息系統、醫學信息工程等計算機相關專業一門重要的專業課[1]，是計算機科學和計算機應用的核心課程之一。“算法分析與設計”是一門兼具理論性和實踐性的課程，其中部分教學內容具有一定的難度，需要在教學過程中適當引入一些先進和高效的教學方法。

比較教學法是一種對具有可比性的教學內容通過橫向和縱向比較，找出它們具有的相同點和不同點，讓學生在對比分析中學習和掌握所學內容的教學方法，它通過在教學活動中比較兩個或兩個以上的認識對象，分析它們存在異同，達到辨識、了解和把握認識對象的目的[2-3]。比較教學法有助于加深學生對知識的理解，建立相關知識之間的聯系，培養學生知識遷移應用和自主學習的能力。比較教學法在計算機類專業課程的教學中得到了較為廣泛的應用[4-5]。通過多年的教學實踐，我們發現比較教學法也可以很好地應用到“算法分析與設計”課程的教學過程中。

二、比較教學法的應用

在“算法分析與設計”課程中，可以從多個角度對教學內容進行比較，下面介紹幾種較為典型的應用情況。

1.同一算法求解不同問題的比較

對于某一種算法通常會有大量的應用實例，例如我們在動態規劃算法的教學過程中主要講解五個實例，包括最長公共子序列、矩陣鏈連乘、01背包問題、數字三角形和最長遞增子序列，通過使用動態規劃法求解這些問題，對比分析這幾個問題的解決步驟，很容易歸納總結出動態規劃求解問題的基本步驟，即分析最優解結構、建立遞歸關系、計算最優值和構造最優解。動態規劃算法在求解問題時通常需要采用表格來保存子問題的解，不同的問題其表格的構造存在不同，但是都蘊含了自底向上求解問題的思想，通過對比分析不同問題的遞歸關系和算法結構，便于總結和整理動態規劃的特點，有助于學生更好地理解動態規劃算法。同時，通過比較教學法，可以更加深入理解動態規劃算法的基本步驟和原理，在比較分析的同時尋找這些問題的共同之處，更好地理解最優子結構和重疊子問題這兩個動態規劃的基本要素。

在開展“算法分析與設計”教學時，我們還發現對于一些具體問題，使用同一種算法思想從不同的角度考慮可以設計出不同的算法，例如在講解分治算法時，快速排序和歸并排序都基于遞歸和分治思想，但是這兩種算法的實現過程完全不同，可以將二者結合一些經典的排序算法，例如冒泡排序、選擇排序和插入排序等進行比較，對比項包括時間復雜度、空間復雜度、排序的穩定性等。通過比較，學生可以理解每一種排序算法的優缺點，便于根據待解決問題的特點選擇合適的算法進行求解。

2.不同算法求解同一問題的比較

對于某些實際問題，有時候可以使用多種算法來求解，例如對于最長公共子序列問題，可以采用窮舉搜索法、備忘錄法、動態規劃法等多種方法，且不同的方法具有不同的特點，其實現過程也不盡相同。因此，針對某一問題，在教學過程中對比分析不同算法的特點，有助于學生更好地理解和掌握相關算法的原理。

在“算法分析與設計”課程教學中，主要講解分治算法、動態規劃算法、貪心算法、回溯法和分支限界法這五大算法。對于某些具體問題而言，可以采用這些算法中的兩種或多種來求解。以經典的背包問題為例，可以使用多種算法來求解背包問題，但是不同的算法在求解問題時存在較大的區別。例如采用最簡單的不考慮跳躍點的動態規劃法求解01背包問題時，要求物品的重量為整數，其適用性不強，可以通過跳躍點來改進;如果采用貪心算法，則不能求解01背包問題，因為得到的不一定是最優解，貪心算法可以用于處理連續背包問題，對于01背包問題而言不適用;采用回溯法來求解雖然時間復雜度不及動態規劃，但是它是一種萬能解題法;也可以使用分支限界法來求解01背包問題，與回溯法的相同點在于都需要使用剪枝函數來刪除部分子樹，區別在于分支限界法采用廣度優先搜索來搜索問題的解空間，而回溯法采用的是深度優先搜索，因此在算法實現時回溯法和分支限界法需要使用不同的數據結構和代碼結構。

3.同一算法求解同一問題中不同實現方式的比較

有時候針對某一問題采用同一算法有不同的具體實現方案，例如在講解使用回溯法求解01背包問題時，重點在于教學生如何高效剪枝，在設計剪枝函數時引導學生主動思考，首先利用約束函數剪去左子樹，但時間復雜度仍然很高，然后設計限界函數剪去右子樹，最簡單的限界函數是直接將剩余物品的總價值與當前獲得的價值相加再與當前最優值比較，如果小于當前最優值，則剪去右子樹，更好的限界函數是計算得到右子樹的上界，如果將當前獲得的價值與右子樹價值的上界相加小于當前最優值，則剪去右子樹，通過計算可以得到右子樹的精確上界，進一步對算法進行優化。此外，在講解回溯法時，通過比較教學法，在分析具體實例時可以讓學生理解兩種典型的解空間樹的異同，遇到新的問題時根據問題的性質來確定是排列數還是子集樹，對于不同的解空間樹，有不同的算法框架。使用回溯法對解空間進行深度優先搜索時，可以采用遞歸回溯，也可以采用迭代回溯，通過對代碼實例進行比較讓學生更好地理解和掌握兩種回溯方法的異同。

對于分支限界法，根據從活結點表中選擇下一個擴展結點的不同方式也存在不同的分支界限法的實現方式，最常見的有隊列式分支限界法和優先隊列式分支限界法。在講解裝載問題等具體實例時，通過比較兩種不同的實現方法可以加深對這兩種實現方式的理解。

三、結語

比較教學法通過對比分析，尋找事物之間的聯系，分析待比較對象之間存在的異同，采用求同比較、求異比較、相似比較等形式，讓教學內容更加系統化、綜合化和條理化。在“算法分析與設計”課程教學過程中，通過對某些教學內容采用比較教學法，有助于培養學生整理和總結所學知識的能力，讓學生在面對新知識的學習時擺脫陌生感，增加學習的主動性，提高學習效率，優化學習效果。正確運用比較教學法可以讓學生更為深刻、更為全面地理解和掌握所學知識，從而獲得更好的教學效果。

參考文獻：

[1] 王曉東. 算法分析與設計（第3版）[M]. 北京：清華大學出版社， 2014.

[2] 李運模. 比較教學法論略[J]. 中南民族學院學報：人文社會科學版，2000，20（3）：125-127.

[3] 肖敏. 比較教學法在現代設計方法課程教學中的應用[J]. 高教論壇，2006（6）：120-121.

[4] 徐欽桂，楊桃欄. 比較教學法在操作系統教學中的應用與實踐 [J]. 計算機教育，2010（10）：95-99.

[5] 熊小兵. “匯編語言程序設計”的比較教學法 [J]. 計算機教育，2010（3）：147-149.