比較教學(xué)法在“算法分析與設(shè)計(jì)”課程教學(xué)中的應(yīng)用

劉偉

【摘要】“算法分析與設(shè)計(jì)”是計(jì)算機(jī)類專業(yè)的核心專業(yè)課程之一。在“算法分析與設(shè)計(jì)”教學(xué)過(guò)程中引入比較教學(xué)法，從同一算法求解不同問(wèn)題、不同算法求解同一問(wèn)題、同一算法求解同一問(wèn)題中不同實(shí)現(xiàn)方式等多個(gè)角度開展比較教學(xué)，讓學(xué)生更好地歸納和整理所學(xué)知識(shí)，加深學(xué)生對(duì)知識(shí)的理解，建立相關(guān)知識(shí)之間的聯(lián)系，有效改善教學(xué)效果。

【關(guān)鍵詞】算法分析與設(shè)計(jì) ?比較教學(xué)法 ?課程教學(xué)

【中圖分類號(hào)】G642 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文獻(xiàn)標(biāo)識(shí)碼】A ? ? ?【文章編號(hào)】2095-3089（2016）11-0111-02

一、引言

“算法分析與設(shè)計(jì)”是計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、信息管理與信息系統(tǒng)、醫(yī)學(xué)信息工程等計(jì)算機(jī)相關(guān)專業(yè)一門重要的專業(yè)課[1]，是計(jì)算機(jī)科學(xué)和計(jì)算機(jī)應(yīng)用的核心課程之一。“算法分析與設(shè)計(jì)”是一門兼具理論性和實(shí)踐性的課程，其中部分教學(xué)內(nèi)容具有一定的難度，需要在教學(xué)過(guò)程中適當(dāng)引入一些先進(jìn)和高效的教學(xué)方法。

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

二、比較教學(xué)法的應(yīng)用

在“算法分析與設(shè)計(jì)”課程中，可以從多個(gè)角度對(duì)教學(xué)內(nèi)容進(jìn)行比較，下面介紹幾種較為典型的應(yīng)用情況。

1.同一算法求解不同問(wèn)題的比較

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

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

2.不同算法求解同一問(wèn)題的比較

對(duì)于某些實(shí)際問(wèn)題，有時(shí)候可以使用多種算法來(lái)求解，例如對(duì)于最長(zhǎng)公共子序列問(wèn)題，可以采用窮舉搜索法、備忘錄法、動(dòng)態(tài)規(guī)劃法等多種方法，且不同的方法具有不同的特點(diǎn)，其實(shí)現(xiàn)過(guò)程也不盡相同。因此，針對(duì)某一問(wèn)題，在教學(xué)過(guò)程中對(duì)比分析不同算法的特點(diǎn)，有助于學(xué)生更好地理解和掌握相關(guān)算法的原理。

在“算法分析與設(shè)計(jì)”課程教學(xué)中，主要講解分治算法、動(dòng)態(tài)規(guī)劃算法、貪心算法、回溯法和分支限界法這五大算法。對(duì)于某些具體問(wèn)題而言，可以采用這些算法中的兩種或多種來(lái)求解。以經(jīng)典的背包問(wèn)題為例，可以使用多種算法來(lái)求解背包問(wèn)題，但是不同的算法在求解問(wèn)題時(shí)存在較大的區(qū)別。例如采用最簡(jiǎn)單的不考慮跳躍點(diǎn)的動(dòng)態(tài)規(guī)劃法求解01背包問(wèn)題時(shí)，要求物品的重量為整數(shù)，其適用性不強(qiáng)，可以通過(guò)跳躍點(diǎn)來(lái)改進(jìn);如果采用貪心算法，則不能求解01背包問(wèn)題，因?yàn)榈玫降牟灰欢ㄊ亲顑?yōu)解，貪心算法可以用于處理連續(xù)背包問(wèn)題，對(duì)于01背包問(wèn)題而言不適用;采用回溯法來(lái)求解雖然時(shí)間復(fù)雜度不及動(dòng)態(tài)規(guī)劃，但是它是一種萬(wàn)能解題法;也可以使用分支限界法來(lái)求解01背包問(wèn)題，與回溯法的相同點(diǎn)在于都需要使用剪枝函數(shù)來(lái)刪除部分子樹，區(qū)別在于分支限界法采用廣度優(yōu)先搜索來(lái)搜索問(wèn)題的解空間，而回溯法采用的是深度優(yōu)先搜索，因此在算法實(shí)現(xiàn)時(shí)回溯法和分支限界法需要使用不同的數(shù)據(jù)結(jié)構(gòu)和代碼結(jié)構(gòu)。

3.同一算法求解同一問(wèn)題中不同實(shí)現(xiàn)方式的比較

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

對(duì)于分支限界法，根據(jù)從活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)的不同方式也存在不同的分支界限法的實(shí)現(xiàn)方式，最常見的有隊(duì)列式分支限界法和優(yōu)先隊(duì)列式分支限界法。在講解裝載問(wèn)題等具體實(shí)例時(shí)，通過(guò)比較兩種不同的實(shí)現(xiàn)方法可以加深對(duì)這兩種實(shí)現(xiàn)方式的理解。

三、結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1] 王曉東. 算法分析與設(shè)計(jì)（第3版）[M]. 北京：清華大學(xué)出版社， 2014.

[2] 李運(yùn)模. 比較教學(xué)法論略[J]. 中南民族學(xué)院學(xué)報(bào)：人文社會(huì)科學(xué)版，2000，20（3）：125-127.

[3] 肖敏. 比較教學(xué)法在現(xiàn)代設(shè)計(jì)方法課程教學(xué)中的應(yīng)用[J]. 高教論壇，2006（6）：120-121.

[4] 徐欽桂，楊桃欄. 比較教學(xué)法在操作系統(tǒng)教學(xué)中的應(yīng)用與實(shí)踐 [J]. 計(jì)算機(jī)教育，2010（10）：95-99.

[5] 熊小兵. “匯編語(yǔ)言程序設(shè)計(jì)”的比較教學(xué)法 [J]. 計(jì)算機(jī)教育，2010（3）：147-149.