算法設(shè)計與分析課程案例教學(xué)模式的探討

秦敏，王井陽，喬世權(quán)

（河北科技大學(xué) 信息科學(xué)與工程學(xué)院，河北石家莊 050018）

作為問題求解和程序設(shè)計的重要基礎(chǔ)——算法設(shè)計與分析在計算機(jī)科學(xué)與技術(shù)專業(yè)的課程體系中是一門重要的必修課，通過該課程的學(xué)習(xí)，不但為學(xué)習(xí)其他專業(yè)課程奠定了扎實(shí)的基礎(chǔ)，也對培養(yǎng)學(xué)生的邏輯思維和創(chuàng)造性起著不可替代的作用[1]。算法課程作為計算機(jī)學(xué)科的一門專業(yè)核心課程，尤其注重培養(yǎng)學(xué)生算法基本理論知識和計算思維、問題建模、算法設(shè)計與分析能力[2]。

1 教學(xué)目標(biāo)

本課程是計算機(jī)科學(xué)與技術(shù)專業(yè)的重要課程，由于課程的難度比較大，那么課程要達(dá)到什么目標(biāo)，如何講授好這門課就是值得探討的課題。目標(biāo)定得太高和太低都不可行，在這里給出本學(xué)校關(guān)于這門課的教學(xué)目標(biāo)，希望和大家探討。本課程是為讓學(xué)生掌握經(jīng)典算法，學(xué)會用算法編程解決實(shí)際問題而設(shè)立。通過本課程的學(xué)習(xí)，使學(xué)生能夠掌握經(jīng)典算法，并且能夠使用C 語言編程實(shí)現(xiàn)算法，以案例為驅(qū)動，理解算法開發(fā)過程，最終達(dá)到能夠進(jìn)行問題建模并用算法進(jìn)行分析和設(shè)計的目標(biāo)。

2 基于COID 的討論式案例教學(xué)模式

為了充分發(fā)揮學(xué)生的主動性，讓學(xué)生成為主體，并不斷提高學(xué)生解決問題的能力和編程能力，借鑒CDIO 思想進(jìn)行了教學(xué)模式的設(shè)計，稱為“基于COID的討論式案例教學(xué)模式”。CDIO 思想是國際工程教育的通用思想，即構(gòu)思（Conceive）、設(shè)計（Design）、實(shí)現(xiàn)（Implement）、運(yùn)作（Operate）[3]。在這個模式里教師提出案例問題，學(xué)生思考解決問題的算法策略，并編程實(shí)現(xiàn)，最后教師主持學(xué)生討論，比如從案例中發(fā)現(xiàn)的算法間的區(qū)別，以及比較誰的方法最優(yōu)，即哪種算法具有最小的時間復(fù)雜度或空間復(fù)雜度。在這個過程中，教師和學(xué)生的任務(wù)如表1所示。

表1 基于CDIO 的討論式案例教學(xué)模式表

每一個案例都經(jīng)過上述四個過程，經(jīng)過幾個案例之后，學(xué)生的編程能力顯著提高。在案例的指導(dǎo)和討論中，主要注意以下幾個方面：比較算法策略之間的關(guān)系，討論誰的方法最優(yōu)，以及思維方法的滲透。

2.1 比較算法策略之間的關(guān)系

由于課本重點(diǎn)是講算法策略，對策略之間的關(guān)系并沒有特別說明。如何才能讓學(xué)生更好地理解算法策略，這里采用了通過案例來進(jìn)行算法策略比較的方法。例如分治策略是將原問題分解為若干個規(guī)模較小但類似于原問題的子問題，遞歸地求解這些子問題，然后再合并這些子問題的解來建立原問題的解。因?yàn)樵谇蠼獯髥栴}時，需要遞歸地求解小問題，因此一般用遞歸的方法實(shí)現(xiàn)，即自頂向下。動態(tài)規(guī)劃把求解過程變成一個多步判斷的過程，每一步都對應(yīng)某個子問題，算法細(xì)心地劃分子問題的邊界，從小的子問題開始，逐層向上求解，通過子問題之間的依賴關(guān)系，有效利用前面已經(jīng)得到的結(jié)果，最大限度減少重復(fù)工作，以提高算法效率[1]。

分治策略和動態(tài)規(guī)劃都是將原問題分解為若干個規(guī)模較小的子問題，求解這些子問題（Conquer），然后再合并這些子問題的解來建立原問題的解，那么這兩個算法策略之間的區(qū)別是什么呢？是否所有能用動態(tài)規(guī)劃解決的問題都可以用分治策略解決呢？區(qū)別在于這些子問題是否會有依賴，子問題在求解后，可能會再次求解，于是需要將這些子問題的解存儲起來，當(dāng)下次再次求解這個子問題時，可以直接使用。動態(tài)規(guī)劃所解決的問題是分治策略所解決問題的一個子集，只是這個子集更適合用動態(tài)規(guī)劃來解決，從而只需更少的運(yùn)行時間。即用動態(tài)規(guī)劃能解決的問題，分治策略肯定能解決，只是運(yùn)行時間更長。因此，分治策略一般用來解決子問題相互獨(dú)立的情況，各個子問題之間不能有依賴關(guān)系，稱為標(biāo)準(zhǔn)分治，而動態(tài)規(guī)劃用來解決子問題之間有依賴的情況。為了讓學(xué)生理解這一點(diǎn)，設(shè)計了兩個案例。案例“安排比賽日程表”要求按某種規(guī)則安排n 個選手的比賽日程表，當(dāng)n 比較大時，手動已無法安排，只能采用分治策略，安排n 個選手分成安排兩個n/2 的選手，依次類推直到人數(shù)少到可以安排為止，這是一個分治策略的案例?！扒髨D中兩點(diǎn)間的最短路徑”是一個動態(tài)規(guī)劃的案例，通過這兩個案例來讓學(xué)生體會兩個算法策略的區(qū)別。

再比如動態(tài)規(guī)劃一般由兩種方法來實(shí)現(xiàn)，一種為自頂向下的備忘錄方式，用遞歸實(shí)現(xiàn)，一種為自底向上的方式，用遞推實(shí)現(xiàn)?！扒髨D中兩點(diǎn)間的最短路徑”要求學(xué)生用兩種方法編程，體會其中的區(qū)別。并用動態(tài)規(guī)劃和分治策略兩種算法策略求解“求圖中兩點(diǎn)間的最短路徑”，比較哪種更合適，進(jìn)而思考什么情況下更適合用動態(tài)規(guī)劃策略，什么情況下更適合用分治策略？再比如既然動態(tài)規(guī)劃通常用遞推來實(shí)現(xiàn)，那么它與遞推之間是什么關(guān)系？動態(tài)規(guī)劃求解的多階段決策問題必須滿足最優(yōu)子結(jié)構(gòu)特性，而遞推所求解的問題則無須滿足。動態(tài)規(guī)劃求解的是最優(yōu)化問題，遞推求解的是判定性問題、構(gòu)造性或計數(shù)性問題。比如“整幣兌零”若求解最少零幣個數(shù)屬于求最優(yōu)解，可以采用動態(tài)規(guī)劃算法，如果求解的是不同的兌換種數(shù)則是計數(shù)性問題，只能采用遞推算法。再比如“0-1 背包問題”，是算法課程中動態(tài)規(guī)劃策略教學(xué)的重要內(nèi)容。0-1 背包問題可描述為：存在1 個有限容量的背包和一組有限個數(shù)的物品，已知背包的容量以及每個物品的重量和價值，如何選擇裝入背包的物品，使得在不超過背包容量的前提下裝入背包的物品的總價值最大[4]。這是一個典型的動態(tài)規(guī)劃算法策略的問題，而動態(tài)規(guī)劃算法隨著背包容量增大、物品數(shù)量增加，其運(yùn)行時間逐漸增加。貪心算法是指在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，它所做出的僅是在某種意義上的局部最優(yōu)解，是一種近似算法。從求解效率來說，貪心算法比動態(tài)規(guī)劃更高，可以使用“0-1 背包問題”案例讓學(xué)生比較兩種算法的運(yùn)行時間，進(jìn)而讓學(xué)生理解當(dāng)求解最優(yōu)解時間太長的話那么接受一個近似解也是可以的。

2.2 討論誰的方法最優(yōu)

在案例評價階段，要組織學(xué)生討論比較誰的方法最優(yōu)，比如“韓信點(diǎn)兵”這個案例，韓信在點(diǎn)兵的時候，為了知道有多少個士兵，同時又能保住軍事機(jī)密，便讓士兵排隊(duì)報數(shù)。按從1 至5 報數(shù)，記下最末一個士兵的數(shù)為1；再按從1 至6 報數(shù)，記下最末一個士兵的數(shù)為5；再按從1 至7 報數(shù)，記下最末一個士兵的數(shù)為4；再按從1 至11 報數(shù)，記下最末一個士兵的數(shù)為10。韓信至少有多少兵？韓信點(diǎn)兵是一個典型的枚舉算法的案例，但并不是一個一個數(shù)值地枚舉，如何枚舉才能枚舉次數(shù)最少，運(yùn)行時間最短，學(xué)生提出了各種各樣的方案。

方案1：初始值40，步長30 的方案，程序結(jié)果顯示枚舉次數(shù)為70 次。

方案2：初始值65，步長66 的方案，程序結(jié)果顯示枚舉次數(shù)為32 次。

方案3：初始值32，步長77 的方案，程序結(jié)果顯示枚舉次數(shù)為28 次。

還有各種其他方案，通過對這些方案的比較，學(xué)生對枚舉的認(rèn)識進(jìn)一步提高。再比如“求圖中兩點(diǎn)間的最短路徑”，就圖的存儲，有的學(xué)生存儲了圖中所有的點(diǎn)和所有的邊，有的學(xué)生則知道這是一個鄰接矩陣。鄰接矩陣是一個對稱的矩陣，因?yàn)锳 點(diǎn)到B 點(diǎn)的距離為X，B 點(diǎn)到A 點(diǎn)的距離也為X，所以只保存上三角就可以了，減少了空間復(fù)雜度。而在算法上有的學(xué)生采用“Dijkstra”算法，有的學(xué)生采用動態(tài)規(guī)劃算法，可以就不同的圖，比較兩種算法的運(yùn)行時間?？傊ㄟ^設(shè)置案例讓學(xué)生編程，然后互相討論互相比較，一方面教學(xué)相長，另一方面也提高了學(xué)生的編程能力。

2.3 思維方法的滲透

國內(nèi)教材大部分都是按照基本算法策略進(jìn)行章節(jié)劃分，它們主要以分治法、貪心法、動態(tài)規(guī)劃法、回溯法、分枝限界法等算法策略來組織內(nèi)容，這樣有利于學(xué)生著重體會各種算法的思想[5]。這種教學(xué)方式的優(yōu)點(diǎn)是學(xué)生在遇到具體問題時往往能夠較快地選擇合適的算法策略作為解題思路，然后根據(jù)現(xiàn)有算法作一定的變換后找到新問題的解決方法；缺點(diǎn)是對于那些無法明確歸類為某種算法策略的問題則可能無法迅速找到解題思路。所以在教學(xué)過程中有意識滲透一些科學(xué)思維方法，比如比較與分類方法、順向思維與逆向思維方法、分析與整合方法、發(fā)散與收斂方法、搭橋過河方法和模糊性思維方法等。如果遇到無法明確歸類為某種算法策略的問題，學(xué)生可以從更高一級的思維方法出發(fā)，來找到解題的思路。在教學(xué)中有意識地講解科學(xué)的思維方法，不但有助于學(xué)生學(xué)習(xí)，而且有助于學(xué)生開闊思路，對于學(xué)生以后的人生也有幫助。

比較與分類方法是貫穿始終的，比如回溯法與枚舉法的比較、遞推與遞歸的比較、遞歸與動態(tài)規(guī)劃的比較、動態(tài)規(guī)劃與分治策略之間的比較等[6]。枚舉法和回溯法都屬于搜索技術(shù)，動態(tài)規(guī)劃和分治策略都屬于分析與整合方法，諸如此類的分類有助于學(xué)生的總結(jié)和理解。順向思維與逆向思維方法也是經(jīng)常用到的，比如遞推有順推有逆推，采用哪種遞推須根據(jù)實(shí)際情況來定。在編程中更是經(jīng)常把乘法變成除法或者除法變成乘法、開方變成平方或者平方變成開方等。分析與整合方法，整個程序設(shè)計是結(jié)構(gòu)化的、是分模塊的，很多算法也體現(xiàn)了分析和整合方法，比如遞推、動態(tài)規(guī)劃和分治策略。發(fā)散與收斂方法，教學(xué)中采用的討論式案例教學(xué)法就是一種發(fā)散與收斂方法，把案例布置下去，學(xué)生提出不同的解決方案，這屬于發(fā)散，再討論比較找出最佳方案，這屬于收斂。模糊性思維方法，在自然界與日常生活中，許多現(xiàn)象帶有不確定性，很難建立確切的數(shù)學(xué)模型，也不是所有問題都要求最優(yōu)解，這時就用到了模擬算法和貪心算法。表2給出了部分算法和思維方法之間的分類聯(lián)系。

表2 算法和思維方法之間的分類聯(lián)系

3 結(jié)語

算法作為一門比較難學(xué)的課程，如何才能講授好這門課是很多教師需要討論的問題。案例式教學(xué)可以發(fā)揮學(xué)生的主動性，提高學(xué)生分析問題和解決問題的能力。本文根據(jù)COID 思想提出了一種討論式案例教學(xué)法供大家探討，強(qiáng)調(diào)在教學(xué)過程中對算法的比較和程序的優(yōu)化，并建議從更高一級的思維方法入手，進(jìn)一步開闊學(xué)生的思路。