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

摘要：“算法設(shè)計(jì)與分析”是工程碩士研究生的一門(mén)核心課程，本文結(jié)合算法設(shè)計(jì)與分析課程的特點(diǎn)，對(duì)該課程的教學(xué)內(nèi)容、教學(xué)方法與教學(xué)手段等三方面的改革做了一些有益的探討。

關(guān)鍵詞：算法設(shè)計(jì)；算法分析；教學(xué)方法

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

1引言

“算法設(shè)計(jì)與分析”是計(jì)算機(jī)專(zhuān)業(yè)高年級(jí)學(xué)生與研究生的重要專(zhuān)業(yè)課，同時(shí)還是一門(mén)與計(jì)算機(jī)有關(guān)的非計(jì)算機(jī)專(zhuān)業(yè)如管理信息、系統(tǒng)工程、應(yīng)用數(shù)學(xué)與計(jì)算數(shù)學(xué)的專(zhuān)業(yè)課。本課程與前驅(qū)課程“離散數(shù)學(xué)”、“程序設(shè)計(jì)”、“計(jì)算方法”、“數(shù)據(jù)結(jié)構(gòu)”等聯(lián)系緊密，而且實(shí)踐性很強(qiáng)，各種經(jīng)典的算法思想如動(dòng)態(tài)規(guī)劃法、回溯法等，從一系列經(jīng)典問(wèn)題的解決方案中提煉出來(lái)后，再應(yīng)用于實(shí)際問(wèn)題的解決。但是我們?cè)诮虒W(xué)過(guò)程中發(fā)現(xiàn)，大部分學(xué)生把該課程看成單純的理論課學(xué)習(xí)，對(duì)算法設(shè)計(jì)思想死記硬背，而不是靈活運(yùn)用，不能對(duì)一種設(shè)計(jì)方法舉一反三。這就要求教師思考如何把其與程序設(shè)計(jì)教學(xué)相結(jié)合，而不是將孤立的算法設(shè)計(jì)思想傳授給學(xué)生。

2教學(xué)內(nèi)容

工程碩士研究生的算法設(shè)計(jì)與分析主要目的是講授計(jì)算機(jī)應(yīng)用中常常遇到的系統(tǒng)軟件或應(yīng)用軟件開(kāi)發(fā)中的具有廣泛工程背景的典型非數(shù)值計(jì)算問(wèn)題的解法，講授設(shè)計(jì)與分析各種算法的基本原理思想、方法與技術(shù)，重點(diǎn)闡述算法設(shè)計(jì)的典型方法，分析不同算法的時(shí)間和空間復(fù)雜度，建立計(jì)算機(jī)與應(yīng)用問(wèn)題之間的橋梁，從而使學(xué)生在選擇或者設(shè)計(jì)算法時(shí)可以對(duì)其進(jìn)行時(shí)空耗費(fèi)分析，并使所設(shè)計(jì)的算法時(shí)空復(fù)雜性最優(yōu)，進(jìn)而為其編寫(xiě)出高效程序、開(kāi)發(fā)出優(yōu)秀軟件系統(tǒng)奠定基礎(chǔ)。通過(guò)本課程的學(xué)習(xí)，學(xué)生應(yīng)基本掌握遞歸、分治法、動(dòng)態(tài)規(guī)劃、貪心算法、回溯法、分支限界法等經(jīng)典算法的設(shè)計(jì)和分析方法，學(xué)習(xí)為解決應(yīng)用中的非數(shù)值計(jì)算問(wèn)題建立計(jì)算機(jī)解題模型的設(shè)計(jì)和分析算法的理論基礎(chǔ)，并掌握對(duì)求解典型問(wèn)題必要的算法設(shè)計(jì)技術(shù)和編程技巧。

計(jì)算機(jī)科學(xué)的特點(diǎn)決定了它的內(nèi)容和手段始終處在不斷革新和變化的過(guò)程中。根據(jù)工程碩士研究生大多有一定的工程經(jīng)驗(yàn)，有一些工程需求。因此，本課程的授課內(nèi)容除了講授經(jīng)典算法設(shè)計(jì)理論外，應(yīng)結(jié)合教師科研實(shí)際，逐步引入并行算法、現(xiàn)代啟發(fā)式搜索算法等先進(jìn)內(nèi)容，盡量反映本學(xué)科領(lǐng)域最新的學(xué)術(shù)和科技成果，使學(xué)生既能夯實(shí)基礎(chǔ)，也能擴(kuò)大眼界。另外，算法的應(yīng)用領(lǐng)域很廣，基本上只要有計(jì)算機(jī)的地方就會(huì)有算法。我們?cè)诮虒W(xué)過(guò)程中還介紹了計(jì)算機(jī)其他領(lǐng)域方面的算法，如數(shù)據(jù)壓縮算法、并行算法、神經(jīng)網(wǎng)絡(luò)等等。雖然只能粗略的介紹其中很小的一部分，但是可以用很淺顯的例子進(jìn)行說(shuō)明，讓學(xué)生了解各個(gè)領(lǐng)域算法的大致思想，拓寬他們的專(zhuān)業(yè)知識(shí)面。

研究新動(dòng)向融會(huì)進(jìn)去，從而使學(xué)生可以用基本理論去解決遇到的新問(wèn)題，增強(qiáng)學(xué)習(xí)興趣，使其感到學(xué)有所用，也是如何在有限的教學(xué)時(shí)間內(nèi)講清基本理論知識(shí)，同時(shí)把本課程教學(xué)改革的關(guān)鍵所在。目前，計(jì)算機(jī)專(zhuān)業(yè)學(xué)生使用的“算法設(shè)計(jì)與分析”教材內(nèi)容較多，而工程碩士研究生學(xué)時(shí)有限，這就要求我們?cè)诮虒W(xué)中力求做到抓住關(guān)鍵，突出重點(diǎn)，解決難點(diǎn)，我們要把主要時(shí)間花在講解重要概念、基本設(shè)計(jì)思想和基本方法上，引導(dǎo)學(xué)生掌握課程內(nèi)容的內(nèi)在關(guān)聯(lián)性，比較不同算法特點(diǎn)，舉一反三，比如背包問(wèn)題，在講課中用圖解法、遞推法等多種方式，讓學(xué)生由淺入深逐漸理解動(dòng)態(tài)規(guī)劃算法原理。在規(guī)定的課時(shí)內(nèi)，既完成教學(xué)任務(wù)，也同時(shí)提高教學(xué)效果。在具體操作上，我們以一些基本算法設(shè)計(jì)技術(shù)內(nèi)容為主線，以其基本設(shè)計(jì)思想的具體應(yīng)用及分析為重點(diǎn)，講清楚算法設(shè)計(jì)及分析問(wèn)題。另外，為了激發(fā)學(xué)生的學(xué)習(xí)興趣，密切關(guān)注計(jì)算機(jī)算法的業(yè)內(nèi)發(fā)展，充分利用互聯(lián)網(wǎng)信息資源，跟蹤計(jì)算機(jī)科學(xué)的最新進(jìn)展，將新知識(shí)信息融入教學(xué)之中。

3教學(xué)方法

教學(xué)方法從傳統(tǒng)的“粉筆+黑板”模式為主過(guò)渡到“計(jì)算機(jī)+大屏幕”為主的授課模式。授課的電子教案開(kāi)始時(shí)以靜態(tài)文字為主的PowerPoint幻燈片方式提供，現(xiàn)在則在教案中穿插曲可動(dòng)態(tài)演示算法的多媒體課件，在大屏幕上展示抽象算法的執(zhí)行過(guò)程，輔之以板書(shū)交流，從而大大增加了從教師到學(xué)生傳遞的信息量和信息種類(lèi)，有助于建立從感性到理性的深入理解及相關(guān)技術(shù)掌握運(yùn)用。

(1) 啟發(fā)式教學(xué)

抽象、理論、分析是計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的三種基本形態(tài)。在基礎(chǔ)課的教學(xué)中應(yīng)將上述三種基本形態(tài)貫穿于教學(xué)的始終，融合新概念將各分支學(xué)科的內(nèi)在聯(lián)系串聯(lián)起來(lái)。在計(jì)算機(jī)專(zhuān)業(yè)課教學(xué)中針對(duì)不同教學(xué)內(nèi)容采取多樣化教學(xué)方式，以啟發(fā)式教學(xué)為主，輔以其他教學(xué)方法。

啟發(fā)式教學(xué)是從介紹典型應(yīng)用問(wèn)題入手，將計(jì)算機(jī)算法的構(gòu)建過(guò)程展現(xiàn)出來(lái)，同時(shí)提出新的算法設(shè)計(jì)問(wèn)題，以便讓學(xué)生進(jìn)行思考和研究。變單向傳輸式教學(xué)為雙向互動(dòng)式教學(xué)， 變以強(qiáng)調(diào)抽象算法設(shè)計(jì)為主的理論講授為探究解決應(yīng)用問(wèn)題為主的設(shè)計(jì)引導(dǎo)式講授。對(duì)一組相關(guān)的算法，分析、闡明不同算法的優(yōu)、缺點(diǎn)，啟發(fā)學(xué)生在能夠解決問(wèn)題的前提下探索新的設(shè)計(jì)思路，培養(yǎng)學(xué)生的創(chuàng)新思維，誘導(dǎo)學(xué)生深入思考，實(shí)現(xiàn)教與學(xué)的互動(dòng)，激發(fā)學(xué)生的創(chuàng)造性，達(dá)到創(chuàng)新能力培養(yǎng)和提高教學(xué)效果的目的。為此，我們?cè)谡n前應(yīng)充分備課，一方面吃透算法設(shè)計(jì)與分析的基本理論知識(shí)，另一方面則要多了解其最新應(yīng)用發(fā)展?fàn)顩r。另外，在講課方式上，采取“系統(tǒng)講解基本理論思想、反復(fù)強(qiáng)調(diào)重點(diǎn)難點(diǎn)、啟發(fā)性講解引申知識(shí)內(nèi)容”的方式，啟發(fā)并引導(dǎo)學(xué)生主動(dòng)探索知識(shí)，既注意了基礎(chǔ)的特點(diǎn)，同時(shí)又給學(xué)生提供了一個(gè)發(fā)散的思維空間。

(2) 理論聯(lián)系實(shí)際

計(jì)算機(jī)科學(xué)非常強(qiáng)調(diào)理論聯(lián)系實(shí)際，算法本身相對(duì)來(lái)說(shuō)比較枯燥，特別是對(duì)于工程碩士研究生，他們更注重應(yīng)用，如果能與實(shí)際應(yīng)用聯(lián)系起來(lái)，可以使學(xué)生學(xué)起來(lái)更有興趣。在教學(xué)中，算法設(shè)計(jì)技術(shù)、算法分析技術(shù)、基本設(shè)計(jì)思想及其應(yīng)用是我們教學(xué)的重點(diǎn)及難點(diǎn)，講課過(guò)程中，我們要把基本算法設(shè)計(jì)方法的思想及應(yīng)用結(jié)合起來(lái)講授，由簡(jiǎn)單應(yīng)用到解決復(fù)雜問(wèn)題，使學(xué)生循序漸進(jìn)接受算法基本思想，從而掌握所學(xué)知識(shí)及相應(yīng)的思維方法。同時(shí)在此過(guò)程中，不失時(shí)機(jī)提出一些問(wèn)題來(lái)引導(dǎo)學(xué)生積極思考。如貪心算法的思想很簡(jiǎn)單，也可以用于處理最優(yōu)化問(wèn)題，但是由于用此方法解決問(wèn)題時(shí)優(yōu)化測(cè)度要根據(jù)具體的問(wèn)題自己選取，故用此方法設(shè)計(jì)算法時(shí)對(duì)于解決不同問(wèn)題其具體實(shí)現(xiàn)方式也是不同的。以找硬幣為例，希望找的硬幣個(gè)數(shù)最少，如果硬幣面值為：1分、5分和11分，要找給顧客為15分，對(duì)貪心算法而言，則需要1枚11分，4枚1分，共用5枚硬幣；而用動(dòng)態(tài)規(guī)劃法求解，得出只用3枚5分硬幣就可以了。從這個(gè)小例子可以看出，貪心算法雖然好用，但對(duì)于有些問(wèn)題采用貪心算法不一定能得到最優(yōu)解。為了讓學(xué)生對(duì)算法設(shè)計(jì)有較完整的認(rèn)識(shí)，我們引導(dǎo)學(xué)生思考對(duì)于同一問(wèn)題時(shí)，選擇不同算法會(huì)有什么樣的結(jié)果，如調(diào)度問(wèn)題、0/1背包問(wèn)題、城市交通問(wèn)題、場(chǎng)地租用問(wèn)題等等。算法課不再是紙上談兵，而是實(shí)際中的運(yùn)用，這種教學(xué)方式讓學(xué)生帶著問(wèn)題學(xué)習(xí)，可以提高他們學(xué)習(xí)的興趣，更重要的是可以培養(yǎng)他們發(fā)現(xiàn)問(wèn)題、分析問(wèn)題及解決問(wèn)題的意識(shí)和能力，通過(guò)對(duì)不同的學(xué)生提出不同難度級(jí)別的問(wèn)題，配合給出不同級(jí)別的提示來(lái)調(diào)動(dòng)不同學(xué)生的主動(dòng)性。

(3) 強(qiáng)化討論教學(xué)環(huán)節(jié)

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

4教學(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é)手段，制作課件，開(kāi)展計(jì)算機(jī)輔助教學(xué)。計(jì)算機(jī)輔助教學(xué)的特點(diǎn)是將算法設(shè)計(jì)中較抽象的設(shè)計(jì)思想以動(dòng)畫(huà)形式演示出來(lái)，既可以節(jié)省教師在課堂上的板書(shū)時(shí)間，也可以將算法設(shè)計(jì)的一系列步驟直觀展示在學(xué)生面前。如利用貪心法解決單源的最短路徑問(wèn)題時(shí)，利用課件可以讓學(xué)生更清楚了解求解指定頂點(diǎn)到其他頂點(diǎn)最短路徑的過(guò)程以及最終求解結(jié)果，更好掌握貪心算法的設(shè)計(jì)思想。課堂教學(xué)充分采用多媒體教學(xué)手段，使學(xué)生學(xué)得直觀、學(xué)得輕松、學(xué)得活躍，并提高課時(shí)利用率，增加課堂信息量，可以更好地發(fā)揮學(xué)生的能動(dòng)性，從而提高學(xué)生學(xué)習(xí)興趣。

另外，我們開(kāi)設(shè)“算法設(shè)計(jì)與分析”課程網(wǎng)站，在網(wǎng)站上配套電子教案、作業(yè)及其他課程資源，也是將傳統(tǒng)教學(xué)方法與現(xiàn)代化教學(xué)手段相結(jié)合的舉措之一。此外，可以把講課內(nèi)容制作成電子課件在校園網(wǎng)上發(fā)布，對(duì)工程碩士研究生有時(shí)可能因?yàn)楣ぷ髟虿荒艿綄W(xué)校上課，或者學(xué)生沒(méi)聽(tīng)懂，可以上網(wǎng)察看，方便學(xué)生自學(xué)、復(fù)習(xí)。

此外，我們也改進(jìn)了考核方式，將傳統(tǒng)、單一的閉卷考核方式，改變?yōu)閷?duì)平時(shí)課堂學(xué)習(xí)、課外設(shè)計(jì)(課外作業(yè))、

期末算法設(shè)計(jì)與分析筆試與交報(bào)告等多環(huán)節(jié)考核相結(jié)合的考核方式，逐漸加大對(duì)算法設(shè)計(jì)和程序開(kāi)發(fā)能力的考核力度，激發(fā)學(xué)生自主學(xué)習(xí)、自主訓(xùn)練的興趣和熱情，避免產(chǎn)生“高分低能”的現(xiàn)象。

參考文獻(xiàn)：

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

[2] 蘇德富. 計(jì)算機(jī)算法設(shè)計(jì)與分析[M]. 北京:電子工業(yè)出版社，2000.

[3] 陳國(guó)良. 并行算法實(shí)踐[M]. 北京:高等教育出版社，2002.

[4] 陳莉. 計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)課教學(xué)改革探索[J]. 高等理科教育，2004，(2):51-55．

First Step towards the Teaching Reform of Algorithm Design and Analysis

ZHENG Hong， SHAO Zhi-qing， FU Hai-bo

(College of Information Science and Engineering， East China University of Science and Technology， Shanghai 200237)

Abstract: Algorithm design and analysis course is a core course for engineering graduate students．This paper integrate with algorithm design and analysis course's characteristics，make beneficial discuss in the Reform of teaching method， teaching content and teaching instrument．

Key words: Algorithm Design， Algorithm Analysis， Teaching Reform