算法分析與設(shè)計的研討型教學(xué)模式探討

張小峰 宋麗華 雷 鵬

魯東大學(xué)信息與電氣工程學(xué)院 山東煙臺 264025

“程序=數(shù)據(jù)結(jié)構(gòu)+算法”，計算機(jī)大師尼古拉斯?沃斯用非常簡潔的公式指明了算法在程序設(shè)計中的重要性。然而，與一般的課程不同，算法對學(xué)生的數(shù)學(xué)基礎(chǔ)、邏輯思維能力要求較高，強(qiáng)調(diào)對知識的理解和應(yīng)用，要求理論與實(shí)踐結(jié)合，知識與能力并重。由于算法課程具有上述特點(diǎn)，傳統(tǒng)的授課方式不適用算法的教學(xué)，如果授課教師不注意教學(xué)方法、教學(xué)模式等方面的研究，學(xué)生可能在算法的學(xué)習(xí)上不會有太多的收獲。為了有效解決學(xué)生在學(xué)習(xí)算法時的困難，從一定程度提高學(xué)生的算法設(shè)計能力，許多高校對于算法課程的教學(xué)采用了不同的方式。例如，將算法和數(shù)據(jù)結(jié)構(gòu)課程合并，開設(shè)數(shù)據(jù)結(jié)構(gòu)與算法，對一些非常經(jīng)典的算法和問題進(jìn)行分析；甚至有的高校直接將算法設(shè)計與分析安排為選修課，僅供有能力的學(xué)生選修。筆者認(rèn)為，算法是計算機(jī)類專業(yè)中的核心和主干課程，這在CC2001三種不同層次的教程模型中也有所體現(xiàn)。因而，采取不回避、不逃避的態(tài)度，積極圍繞算法分析與設(shè)計的教學(xué)內(nèi)容，認(rèn)真設(shè)計教學(xué)案例，改進(jìn)教學(xué)模式和教學(xué)方法，切實(shí)提高教學(xué)效果，這也是計算機(jī)教育界在進(jìn)行算法授課時共同面對的問題。

1 算法分析與設(shè)計授課中存在的問題

算法分析與設(shè)計課程是計算機(jī)、軟件工程等專業(yè)的核心和主干課程，除了要求學(xué)生掌握離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)等先導(dǎo)課程的基礎(chǔ)知識外，還要求學(xué)生具有較強(qiáng)的邏輯基礎(chǔ)和抽象思維能力。然而，目前的算法分析與設(shè)計的教學(xué)過程中存在許多問題，主要有以下幾點(diǎn)。

(1)學(xué)生對課程在教學(xué)體系中的重要性認(rèn)識不夠。算法是計算機(jī)課程體系中的核心課程之一，通常被安排在離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)等先修課程后開設(shè)。然而，許多學(xué)生認(rèn)為，計算機(jī)類專業(yè)的學(xué)生應(yīng)該掌握相關(guān)的前沿技術(shù)，不需要過多地對思維進(jìn)行訓(xùn)練，為算法分析與設(shè)計的學(xué)習(xí)埋下了隱患。

(2)學(xué)生不具備必要的學(xué)習(xí)素質(zhì)。在普通高校應(yīng)用型人才培養(yǎng)的課程體系中，大量的課程被壓縮課時，導(dǎo)致許多課程內(nèi)容被壓縮、刪減，導(dǎo)致應(yīng)擴(kuò)展的知識點(diǎn)沒有得到擴(kuò)展，產(chǎn)生的直接后果就是學(xué)生的基礎(chǔ)不扎實(shí)。特別是離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)等算法的先修課程的基礎(chǔ)不扎實(shí)。

(3)許多學(xué)生學(xué)習(xí)缺乏必要的興趣與動力。對于邏輯性強(qiáng)、難度大的算法課程而言，許多學(xué)生沒有意識到算法的重要性，特別是在一般的高校中，在他們的觀點(diǎn)中，算法不像技術(shù)類課程那樣，可以帶來最直接的收益。

(4)教師的教學(xué)模式和教學(xué)方法亟須改進(jìn)。算法的邏輯性與難度同樣給授課教師帶來了許多困難，許多教師對于算法的授課，通常有兩種模式：一種是講解算法的思想，讓學(xué)生編程實(shí)現(xiàn)；另一種是降低課程的難度，從程序設(shè)計的角度實(shí)現(xiàn)相關(guān)的算法。從專業(yè)的角度看，這兩種教學(xué)模式適用于不同的高校，第一種適合培養(yǎng)高水平高校的學(xué)生，第二種則對非計算機(jī)類專業(yè)的學(xué)生適用。

2 算法分析與設(shè)計中實(shí)施研討型教學(xué)的探索

算法分析與設(shè)計是一門面向能力與思維培養(yǎng)的專業(yè)核心課程。與一般的計算機(jī)類專業(yè)核心課程相比，算法的核心內(nèi)容相對比較少，主要集中在遞歸與分治、動態(tài)規(guī)劃、回溯、分枝限界和貪心算法等幾種主要算法上，但由基礎(chǔ)算法擴(kuò)展的相關(guān)問題卻較多，不同的教師可以根據(jù)學(xué)生的不同情況選擇相應(yīng)的問題。

“授之以魚，不如授之以漁”，掌握相關(guān)的問題，不如掌握求解問題的思想。從這個角度看，算法分析與設(shè)計課程非常適合引入研討性教學(xué)。這種教學(xué)模式對教師而言，要求設(shè)計的問題具有啟發(fā)性，由易到難，由簡到繁，采取循序漸進(jìn)的教學(xué)。對學(xué)生而言，要求學(xué)生真正成為學(xué)習(xí)行為的主人，在學(xué)習(xí)過程中發(fā)掘自身的潛力，施展才華，在課堂教學(xué)中處于教學(xué)主體地位。在算法分析與設(shè)計中采取研討型教學(xué)，可以為學(xué)生提供思考問題和討論問題的機(jī)會，使學(xué)生圍繞相關(guān)的算法，應(yīng)用所學(xué)的知識解決相關(guān)的問題。這種教學(xué)模式，能使學(xué)生增長知識、開闊視野，有助于學(xué)生綜合能力的提高，還有助于師生共同探索、發(fā)現(xiàn)和研究，進(jìn)而密切師生關(guān)系，促進(jìn)教學(xué)相長。

2.1 算法課程由選修提升到必修 增加算法的課時

在修訂培養(yǎng)方案時，筆者所在的高校充分認(rèn)識到算法課程在學(xué)生能力培養(yǎng)中的重要性，將算法分析與設(shè)計從選修課修訂為必修課，這樣可以避免許多學(xué)生在選課時回避這門課程，從一定程度上提高學(xué)生對算法課程的重視程度。同時，將算法的課時設(shè)置為54課時左右，保證了教師有充足的時間講解課程的內(nèi)容。

2.2 有針對性地選擇授課內(nèi)容 避免盲目性

一般地，算法主要包括[1]：枚舉法(暴力搜索)、遞歸法、分治法、動態(tài)規(guī)劃、貪心算法、回溯法、分枝限界法、隨機(jī)化算法、線性規(guī)劃與網(wǎng)絡(luò)流等相關(guān)算法，授課內(nèi)容也是根據(jù)學(xué)生的具體情況，圍繞幾種典型算法介紹相關(guān)的問題，強(qiáng)化對相關(guān)算法的靈活應(yīng)用能力。在授課內(nèi)容的設(shè)計中，根據(jù)課時的需要，刪減了隨機(jī)化算法以及線性規(guī)劃與網(wǎng)絡(luò)流兩種經(jīng)典算法，重點(diǎn)圍繞其他7種算法講解，每一種算法設(shè)計3～5個典型問題重點(diǎn)講解，同時安排學(xué)生講解3～5個問題，進(jìn)一步熟悉相關(guān)算法。對每一個問題，從問題分析、算法的設(shè)計思想、解決問題的思路以及編程過程要求詳細(xì)地講解，不放過任何一個細(xì)節(jié)，切實(shí)提高算法設(shè)計能力和編程水平。表1列舉了筆者在授課過程中教師講授和學(xué)生練習(xí)的相關(guān)經(jīng)典題目。

表1 授課過程中授課和練習(xí)的主要問題

2.3 注意知識講解的遞進(jìn)性

由于算法課程的難度，在講解算法時，需要按照由易到難的原則，讓學(xué)生逐漸掌握算法的精髓。這里以回溯法為例進(jìn)行介紹?；厮莘ǖ木柙谟谠O(shè)計解空間的樹結(jié)構(gòu)是通過對解空間樹進(jìn)行深度優(yōu)先遍歷完成的。按照問題解空間的組織形式，解空間樹有子集樹和排列樹兩種形式。一般而言，排列樹比子集樹更復(fù)雜，在講解過程中，可以把排列樹安排在子集樹后講解。而在構(gòu)造子集樹時，需要重點(diǎn)考慮參數(shù)的個數(shù)和子集樹的高度兩個主要因素，在構(gòu)造回溯函數(shù)時，則需要重點(diǎn)考慮參數(shù)的個數(shù)和參數(shù)的含義。在設(shè)計時應(yīng)按照知識的遞進(jìn)性，由易到難構(gòu)造不同的子集樹。筆者在授課過程中設(shè)計了4個教學(xué)案例：0-1背包問題、李白飲酒問題、8皇后問題和郵資問題，分別對上述問題進(jìn)行了解釋和說明。

2.4 教學(xué)過程中需要重視案例的設(shè)計

算法課程在授課時，需要注意相關(guān)案例的設(shè)計。一般來講，案例的設(shè)計應(yīng)具有代表性、實(shí)用性，從案例設(shè)計的角度培養(yǎng)學(xué)生的學(xué)習(xí)興趣。例如，在介紹回溯法時，可以通過8皇后、數(shù)獨(dú)這些生活中的實(shí)際問題對回溯法進(jìn)行分析，提高學(xué)生的學(xué)習(xí)興趣。

同時，備課時要注重案例的設(shè)計應(yīng)遵循“由易到難，由簡到繁”的原則，逐漸培養(yǎng)學(xué)生的算法設(shè)計能力[2]。以枚舉法為例對案例的設(shè)計進(jìn)行說明，在介紹枚舉法的基本思想后，通過“啤酒飲料問題—子集和問題—8皇后問題”三個問題介紹枚舉法的基本思想以及實(shí)現(xiàn)枚舉法中的細(xì)節(jié)處理。

2.5 注重算法設(shè)計中的數(shù)學(xué)思想

算法的設(shè)計離不開數(shù)學(xué)基礎(chǔ)，好的數(shù)學(xué)思想會讓算法的設(shè)計事半功倍，教師在授課過程中不能僅僅滿足算法的實(shí)現(xiàn)，而更應(yīng)該通過相應(yīng)的數(shù)學(xué)思想，對學(xué)生的思維和算法設(shè)計能力進(jìn)行訓(xùn)練[3]。通過最大間隙問題、最多約數(shù)問題、整數(shù)劃分問題3個例子說明。

在最大間隙問題中，如果不考慮算法的復(fù)雜度，可以直接對給定的數(shù)進(jìn)行排序，線性掃描一次后可以得到最大差值。然而，排序算法的最優(yōu)時間復(fù)雜度明顯不滿足線性時間的要求，因此，需要借助離散數(shù)學(xué)中的鴿籠原理這一關(guān)鍵數(shù)學(xué)思想設(shè)計相應(yīng)的算法。在最多約數(shù)問題中，如果沒有算法基礎(chǔ)，可以通過簡單的循環(huán)也可以計算出來，但更優(yōu)秀的算法可以結(jié)合算術(shù)基本定理實(shí)現(xiàn)。在整數(shù)劃分問題中，雖然可以通過遞歸得到整數(shù)劃分的遞推公式，但如果教師在授課過程中將整數(shù)的劃分問題變成多項式的乘法，引入母函數(shù)法，從另一個角度講解正整數(shù)的劃分，不僅可以加深學(xué)生對劃分問題的理解，也可以進(jìn)一步開闊學(xué)生的視野。

2.6 注重對問題的縱向和橫向擴(kuò)展

在算法分析與設(shè)計的授課中，對給定的問題，不能僅局限一種算法，也不能僅局限在這一個問題上，要注重對問題的縱向和橫向擴(kuò)展。例如，介紹棋盤覆蓋問題時，通過判斷特殊格的位置，可以將問題分解為4個子問題，在不包含特殊格的3個子問題交接處，構(gòu)造1個特殊的L型骨牌，這樣問題就可以運(yùn)用分治法求解。按照這個思路，可以對馬的Hamilton周游世界問題進(jìn)行同樣的分析，將1個問題分解為4個子問題，運(yùn)用同樣的思路求解，以加深學(xué)生對分治法的理解。例如，在求解0-1背包問題時，可以運(yùn)用枚舉法、動態(tài)規(guī)劃法、回溯法、分枝限界法對問題進(jìn)行求解，讓學(xué)生比較幾種算法的優(yōu)劣，以加深對相關(guān)算法的理解。同樣，在介紹動態(tài)規(guī)劃算法時，可以對每一個問題用遞歸算法、備忘錄算法和動態(tài)規(guī)劃算法實(shí)現(xiàn)，讓學(xué)生徹底理解自下向上和自上向下兩種不同的設(shè)計思想。

2.7 注重宏觀與微觀上算法的教學(xué)

講授算法時，筆者認(rèn)為授課教師應(yīng)該注重從宏觀和微觀兩方面把握算法的教學(xué)，即不僅講授算法的思想，而且應(yīng)該講授算法的具體實(shí)現(xiàn)。如果僅僅停留在算法思想的層次，能力較差的學(xué)生會失去興趣而直接放棄算法的實(shí)現(xiàn)。同時，注重微觀上的教學(xué)，除了可以讓學(xué)生深入了解算法的思想外，還可以進(jìn)一步熟悉和掌握先修課程的相關(guān)知識。以8皇后問題為例進(jìn)行說明。

在8皇后問題中，如果用枚舉法實(shí)現(xiàn)，可以簡單為每一個棋盤格設(shè)計一個變量，判斷在該棋盤格是否放置皇后。這樣進(jìn)行簡單的枚舉，需要考慮的可能數(shù)量為264。類似漢諾塔問題，該問題在理論上可以求解，但實(shí)際情況無法求解，無法在有效時間內(nèi)解決。在算法實(shí)現(xiàn)時，可以借助數(shù)據(jù)結(jié)構(gòu)對問題進(jìn)行簡化。通過引入一維數(shù)組，保證每一列上只有一個皇后，可以將變量數(shù)從64減少到8，將需要考慮的情況減為28=256，進(jìn)一步運(yùn)用枚舉法，可以得到8皇后問題的解。

通過這樣的教學(xué)，不僅可以讓學(xué)生進(jìn)一步理解和掌握枚舉法的思想，而且可以熟悉和掌握數(shù)據(jù)結(jié)構(gòu)在算法設(shè)計中的作用，提高學(xué)生的學(xué)習(xí)興趣。

3 結(jié)語

在算法分析與設(shè)計中實(shí)施研討型教學(xué)，筆者已經(jīng)探索了3年。這種教學(xué)模式受到了學(xué)生的普遍歡迎，除了編程水平、算法設(shè)計能力得到了較大的提升外，思維能力以及分析和解決問題的能力也得到了一定的訓(xùn)練。有多名學(xué)生參加全國程序設(shè)計大賽獲獎，有多名學(xué)生考取了西安電子科技大學(xué)、天津大學(xué)的研究生，并且在復(fù)試階段得到了較高的評價。同時，實(shí)施研討性教學(xué)，對于密切師生關(guān)系，提高教師的教學(xué)水平，充實(shí)教師的教學(xué)內(nèi)容也大有益處。實(shí)踐證明，在算法分析與設(shè)計課程的教學(xué)中實(shí)施研討型教學(xué)，對計算機(jī)類專業(yè)培養(yǎng)高水平的應(yīng)用型人才大有益處。