“算法設(shè)計(jì)與分析”課程改革初探

摘要：“算法設(shè)計(jì)與分析”是計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的核心課程之一。本文針對(duì)目前該課程教學(xué)中存在的問題，就教學(xué)內(nèi)容、教學(xué)方法、教學(xué)手段、實(shí)驗(yàn)環(huán)節(jié)和考核方式等五個(gè)方面的改革進(jìn)行了探討。

關(guān)鍵詞：算法設(shè)計(jì)與分析；計(jì)算機(jī)專業(yè)；教學(xué)改革

中圖分類號(hào)：G642文獻(xiàn)標(biāo)識(shí)碼：A

1教學(xué)內(nèi)容的改革

學(xué)生普遍反映“算法設(shè)計(jì)與分析”這門課難學(xué)，它不是靠死記硬背能夠掌握的，必須分析理解并且靈活應(yīng)用，要求學(xué)生具有較好的數(shù)學(xué)和數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，為了幫助學(xué)生渡過“難”關(guān)，作為教師，關(guān)鍵要選擇好教學(xué)內(nèi)容?？偟脑瓌t是：內(nèi)容難度適中，結(jié)合實(shí)際問題和相關(guān)課程的知識(shí)講解算法設(shè)計(jì)技巧及算法分析方法，使學(xué)生既能理解，又能拓展創(chuàng)新。給本科生講授這門課，切忌講授太深?yuàn)W的理論(如計(jì)算復(fù)雜性理論)，使學(xué)生失去學(xué)習(xí)的信心；同時(shí)，也切忌對(duì)數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容的重復(fù)講授，使學(xué)生失去興趣。

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

2教學(xué)方法的改革

(1) 加強(qiáng)分析和比較

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

(2) 注重與數(shù)據(jù)結(jié)構(gòu)內(nèi)容相結(jié)合

算法和數(shù)據(jù)結(jié)構(gòu)有著密不可分的聯(lián)系，著名計(jì)算機(jī)科學(xué)家沃思更是提出“數(shù)據(jù)結(jié)構(gòu)+算法一程序”的觀點(diǎn)。每個(gè)算法都是建立在某種數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)之上，一個(gè)算法不可能脫離數(shù)據(jù)結(jié)構(gòu)而孤立存在。因此，學(xué)好算法需要認(rèn)真掌握數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。例如，哈夫曼算法中要求構(gòu)造的哈夫曼編碼樹，其實(shí)是一個(gè)最優(yōu)二叉樹。學(xué)生在前期數(shù)據(jù)結(jié)構(gòu)課程中已經(jīng)學(xué)習(xí)過最優(yōu)二叉樹的相關(guān)知識(shí)，教師可以先溫習(xí)這部分內(nèi)容，然后以一種具體應(yīng)用的形式引出哈夫曼編碼樹。這種溫故而知新的教學(xué)方法，可以有效消除同學(xué)們?cè)趯W(xué)習(xí)過程中的畏難情緒。

(3) 將理論分析和實(shí)際應(yīng)用結(jié)合起來

算法本身相對(duì)來說比較枯燥，如果能拓展教材中的內(nèi)容，在加強(qiáng)理論說明的同時(shí)，與實(shí)際應(yīng)用聯(lián)系起來，可以使學(xué)生學(xué)起來更有興趣。例如，在教授哈夫曼算法時(shí)，我們首先由最優(yōu)二叉樹引出哈夫曼編碼樹的構(gòu)造方法，然后通過驗(yàn)證它的貪婪選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì) ，從理論上證明哈夫曼編碼是平均碼長(zhǎng)最短的整數(shù)碼。

(4) 強(qiáng)化習(xí)題討論教學(xué)環(huán)節(jié)

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

3教學(xué)手段的改革

將傳統(tǒng)教學(xué)方法與現(xiàn)代化教學(xué)手段相結(jié)合，也是我們教學(xué)改革的舉措之一。為了在有限的教學(xué)時(shí)間內(nèi)，增加單位

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

4實(shí)驗(yàn)環(huán)節(jié)的改革

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

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

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

5考核形式的改革

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

參考文獻(xiàn)：

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

[2] 巫小蓉，李霞. 計(jì)算機(jī)算法設(shè)計(jì)與分析教學(xué)經(jīng)驗(yàn)淺談[J]. 廣西大學(xué)梧州分校學(xué)報(bào)，2004，14(3):71-73.

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

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

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