《算法設(shè)計(jì)與分析》課程教學(xué)方法改革探究

王彥群，劉付勇

（塔里木大學(xué)信息工程學(xué)院，阿拉爾 843300)

《算法設(shè)計(jì)與分析》課程教學(xué)方法改革探究

王彥群，劉付勇

（塔里木大學(xué)信息工程學(xué)院，阿拉爾 843300)

針對(duì)傳統(tǒng)教學(xué)方法不能取得較好教學(xué)效果的問(wèn)題，提出階段式的多元化教學(xué)法。該方法在《算法設(shè)計(jì)與分析》課程教學(xué)中的實(shí)施，極大提高學(xué)生的興趣和實(shí)踐能力，是值得借鑒和推廣的教學(xué)方法。

算法設(shè)計(jì)；基于問(wèn)題的教學(xué)法；任務(wù)驅(qū)動(dòng)教學(xué)法；案例教學(xué)法；分組討論法

0 引言

《算法設(shè)計(jì)與分析》是計(jì)算機(jī)、信息與計(jì)算科學(xué)、信息安全和系統(tǒng)工程等專業(yè)的一門(mén)重要專業(yè)課。該課程旨在通過(guò)對(duì)計(jì)算機(jī)算法的學(xué)習(xí)，使學(xué)生掌握算法設(shè)計(jì)及復(fù)雜性分析方法，培養(yǎng)學(xué)生分析問(wèn)題、解決問(wèn)題的能力[1]。

該課程是一門(mén)實(shí)踐性、技能性很強(qiáng)的課程，主要依靠理解與實(shí)踐，并加以靈活應(yīng)用。但在教學(xué)過(guò)程中較多的學(xué)生對(duì)該門(mén)課程掌握的情況并不理想，一方面源于學(xué)生知識(shí)學(xué)習(xí)深度不夠，另一方面源于教師缺乏有效的教學(xué)方法和手段。為取得較好的教學(xué)效果，任課教師必須具有較強(qiáng)的理論基礎(chǔ)和實(shí)踐技能，同時(shí)又要不斷探索改進(jìn)教學(xué)方法。

1 常用教學(xué)方法

常用的教學(xué)方法有講授法、基于問(wèn)題的教學(xué)法、任務(wù)驅(qū)動(dòng)教學(xué)法、案例教學(xué)法、項(xiàng)目教學(xué)法、分組討論法等。

講授法是以語(yǔ)言傳遞為主的教學(xué)方法；基于問(wèn)題的教學(xué)法是把教學(xué)內(nèi)容設(shè)計(jì)成問(wèn)題，教師引導(dǎo)學(xué)生帶著問(wèn)題學(xué)習(xí)，探討問(wèn)題解決的教學(xué)方法；任務(wù)驅(qū)動(dòng)教學(xué)法是把教學(xué)內(nèi)容設(shè)計(jì)成任務(wù)，由教師指導(dǎo)、學(xué)生主導(dǎo)來(lái)完成任務(wù)的教學(xué)方法[2]；案例教學(xué)法是通過(guò)對(duì)具體實(shí)例的演示、講解，讓學(xué)生對(duì)案例進(jìn)行分析、討論、交流，達(dá)到認(rèn)知學(xué)習(xí)目標(biāo)的一種啟發(fā)式教學(xué)方法[3]；項(xiàng)目驅(qū)動(dòng)教學(xué)法是案例教學(xué)法的基礎(chǔ)上采用“案例導(dǎo)向、項(xiàng)目驅(qū)動(dòng)”的教學(xué)方法[4]，通過(guò)項(xiàng)目的形式進(jìn)行教學(xué)，由教師指導(dǎo)、學(xué)生獨(dú)立完成相對(duì)獨(dú)立的項(xiàng)目。分組討論法將學(xué)生分成若干小組，教師提出一個(gè)具體問(wèn)題或方案，由學(xué)生以組為單位，進(jìn)行討論、分析和解決[5]。以上教學(xué)方法各有優(yōu)點(diǎn)，但在教學(xué)中需要綜合實(shí)施多種教學(xué)方法才能達(dá)到好的效果。

2 階段式多元化教學(xué)法在算法設(shè)計(jì)與分析課程教學(xué)中的安排

根據(jù)以上教學(xué)方法分析，筆者提出階段式多元教學(xué)法。階段式多元教學(xué)法是將教學(xué)任務(wù)劃分為多個(gè)階段，有步驟地進(jìn)行，每個(gè)階段的目標(biāo)明確，并且根據(jù)各階段內(nèi)容特點(diǎn)融合多種教學(xué)法的一種方法。

2.1 算法設(shè)計(jì)與分析課程教學(xué)內(nèi)容分析

根據(jù)《算法設(shè)計(jì)與分析》課程教學(xué)大綱的要求，本課程具體教學(xué)內(nèi)容包括算法基本概念與分析方法、蠻力法、分治法、減治法、動(dòng)態(tài)規(guī)劃法、貪心法、回溯法、分

支限界法、概率算法、近似算法、計(jì)算復(fù)雜性理論等[6]。我們根據(jù)《算法設(shè)計(jì)與分析》課程教學(xué)內(nèi)容，融合以上幾種教學(xué)方法，同時(shí)把課程理論知識(shí)部分輔以教學(xué)網(wǎng)站實(shí)施，并注重學(xué)生主體性，提出階段式多元化教學(xué)法。

2.2 基于階段式多元化教學(xué)法的算法設(shè)計(jì)與分析課程教學(xué)安排

在實(shí)際教學(xué)過(guò)程中，我們根據(jù)教學(xué)內(nèi)容把整個(gè)教學(xué)環(huán)節(jié)劃分為基礎(chǔ)學(xué)習(xí)階段、進(jìn)階學(xué)習(xí)階段、拓展學(xué)習(xí)階段3個(gè)部分?；A(chǔ)學(xué)習(xí)階段側(cè)重基本知識(shí)點(diǎn)的掌握，只有通過(guò)了基礎(chǔ)學(xué)習(xí)階段才能進(jìn)入進(jìn)階學(xué)習(xí)階段，拓展學(xué)習(xí)階段的內(nèi)容大多屬于選修內(nèi)容，在課時(shí)充裕的情況下可以教授。

其中基礎(chǔ)學(xué)習(xí)階段的內(nèi)容包括算法基本概念與分析方法、蠻力法、分治法、減治法；進(jìn)階學(xué)習(xí)階段的內(nèi)容包括動(dòng)態(tài)規(guī)劃法、貪心法、回溯法、分支限界法；拓展學(xué)習(xí)階段包括概率算法、近似算法、計(jì)算復(fù)雜性理論。我們?cè)诟麟A段靈活運(yùn)用多元化教學(xué)法，其中基礎(chǔ)學(xué)習(xí)階段主要采用講授法、案例教學(xué)法、任務(wù)驅(qū)動(dòng)教學(xué)法，并把教學(xué)網(wǎng)站發(fā)布出去，供學(xué)生學(xué)習(xí)和復(fù)習(xí)；進(jìn)階學(xué)習(xí)階段主要采用案例教學(xué)法、分組討論法、任務(wù)驅(qū)動(dòng)教學(xué)法；拓展學(xué)習(xí)階段則主要采用基于問(wèn)題的教學(xué)法、分組討論法、案例教學(xué)法。這幾個(gè)階段是連續(xù)的，預(yù)示著學(xué)習(xí)環(huán)節(jié)由初級(jí)到高級(jí)的過(guò)程。每個(gè)階段用到的教學(xué)方法也并會(huì)根據(jù)教學(xué)內(nèi)容靈活使用。具體的教學(xué)環(huán)節(jié)安排詳見(jiàn)表1。

表1 算法設(shè)計(jì)與分析課程教學(xué)環(huán)節(jié)安排

3 階段式多元化教學(xué)法在算法設(shè)計(jì)與分析教學(xué)中的實(shí)施

《算法設(shè)計(jì)與分析》主要是講授計(jì)算機(jī)應(yīng)用中經(jīng)常遇到的實(shí)際問(wèn)題的各種解法，講授各種算法的基本思想、方法與技術(shù)，旨在培養(yǎng)學(xué)生分析問(wèn)題和解決問(wèn)題的能力。為此，筆者精心設(shè)計(jì)了階段式多元化教學(xué)法，以期獲得良好教學(xué)效果。

3.1 基礎(chǔ)學(xué)習(xí)階段

基礎(chǔ)學(xué)習(xí)階段的教學(xué)內(nèi)容相對(duì)基礎(chǔ)、容易理解，內(nèi)容包括動(dòng)態(tài)規(guī)劃法、貪心法、回溯法、分支限界法。采用講授法，能讓學(xué)生短時(shí)間內(nèi)獲得本課程的性質(zhì)、地位、作用、學(xué)習(xí)方法，算法基本概念與分析方法等知識(shí)，為以后的學(xué)習(xí)指明方向。在講解蠻力法、分治法、減治法時(shí)，采用案例教學(xué)法和任務(wù)驅(qū)動(dòng)教學(xué)法結(jié)合的方法。例如，講解蠻力法時(shí)，拋出案例：旅行商問(wèn)題，即TSP問(wèn)題(Travelling Salesman Problem)又譯為旅行推銷(xiāo)員問(wèn)題、貨郎擔(dān)問(wèn)題，是數(shù)學(xué)領(lǐng)域中著名問(wèn)題之一。假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來(lái)出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。

教師通過(guò)對(duì)TSP問(wèn)題講解和實(shí)驗(yàn)演示，讓學(xué)生對(duì)蠻力法的特點(diǎn)進(jìn)行分析、討論、交流。然后把查找問(wèn)題中的順序查找、串匹配以及排序問(wèn)題中的選擇排序、冒泡排序等，設(shè)計(jì)成任務(wù)，由教師指導(dǎo)、學(xué)生主導(dǎo)用蠻力法來(lái)完成。

3.2 進(jìn)階學(xué)習(xí)階段

進(jìn)階學(xué)習(xí)階段的教學(xué)內(nèi)容相對(duì)難理解，內(nèi)容包括動(dòng)態(tài)規(guī)劃法、貪心法、回溯法、分支限界法。采用案例教學(xué)法、分組討論法、任務(wù)驅(qū)動(dòng)教學(xué)法。

例如，講解動(dòng)態(tài)規(guī)劃法時(shí)，拋出案例：0/1背包問(wèn)題，即給定n種物品和一背包，物品i的重量是wi，其價(jià)值是pi，背包的容量是M，問(wèn)如何選擇裝入背包中的物品總價(jià)值最大？

教師通過(guò)對(duì)0/1背包問(wèn)題講解和實(shí)驗(yàn)演示，讓學(xué)生對(duì)動(dòng)態(tài)規(guī)劃法的特點(diǎn)有所了解，然后3人或4人一組對(duì)動(dòng)態(tài)規(guī)劃法的解題思路和步驟進(jìn)行討論、交流。由各小組代表發(fā)言，回答同學(xué)們的各種提問(wèn)，教師進(jìn)行總結(jié)。最后把查找問(wèn)題中的最優(yōu)二叉查找樹(shù)、近似串匹配以及圖問(wèn)題中的TSP問(wèn)題、多段圖的最短路徑等，設(shè)計(jì)成任務(wù)，由教師指導(dǎo)、學(xué)生主導(dǎo)用動(dòng)態(tài)規(guī)劃法來(lái)實(shí)現(xiàn)。

3.3 拓展學(xué)習(xí)階段

拓展學(xué)習(xí)階段的教學(xué)內(nèi)容屬于選修內(nèi)容，包括概

率算法、近似算法、計(jì)算復(fù)雜性理論。采用基于問(wèn)題的教學(xué)法、分組討論法、案例教學(xué)法。例如，講解近似算法時(shí)，拋出問(wèn)題：TSP問(wèn)題的時(shí)間復(fù)雜度是多少，有沒(méi)有其它降低時(shí)間度的解決辦法？然后小組討論，由各小組代表發(fā)言，學(xué)生代表覺(jué)得指數(shù)時(shí)間內(nèi)求解的問(wèn)題，轉(zhuǎn)化成多項(xiàng)式時(shí)間內(nèi)求解決最好。教師給予贊許，接著介紹近似算法，它是處理難解的組合優(yōu)化問(wèn)題的一個(gè)非常重要和有效的方法。它可以在多項(xiàng)式時(shí)間內(nèi)求得問(wèn)題的一個(gè)解，并使其目標(biāo)函數(shù)值與最優(yōu)解的目標(biāo)函數(shù)值之比不超過(guò)一個(gè)常數(shù)。

教師舉出TSP問(wèn)題、頂點(diǎn)覆蓋問(wèn)題用近似算法求解的案例，學(xué)生對(duì)近似算法有了一定的認(rèn)識(shí)。最后，教師讓學(xué)生再討論，以前我們遇到的問(wèn)題，哪些可以用近似算法實(shí)現(xiàn)，并給出解題步驟。

通過(guò)這些方法的綜合應(yīng)用，拓展學(xué)習(xí)階段也達(dá)到教好的教學(xué)效果。

4 結(jié)語(yǔ)

階段式多元化教學(xué)法在2015級(jí)軟件工程班實(shí)施后，教學(xué)效果顯著。學(xué)生學(xué)習(xí)的積極性、學(xué)習(xí)能力和動(dòng)手實(shí)踐能力有了很大提高。藍(lán)橋杯程序設(shè)計(jì)大賽的獲獎(jiǎng)率比上屆提高了10%以上?？梢?jiàn)，階段式多元化教學(xué)法教學(xué)效果良好，值得推廣使用。作為高校教師，要不斷探索、創(chuàng)新有益教學(xué)方法，使學(xué)生滿意、受益。

[1]李建忠.《算法設(shè)計(jì)與分析》課程教學(xué)模式探索[J].現(xiàn)代計(jì)算機(jī),2014(7):24-26.

[2]李華,張俊星,謝輝.一種計(jì)算機(jī)網(wǎng)絡(luò)課的教學(xué)方法設(shè)計(jì)[J].計(jì)算機(jī)教育,2012(1):72-74.

[3]吳剛.數(shù)據(jù)庫(kù)原理課程教學(xué)改革探討與實(shí)踐[J].科技信息,2013(12):10.

[4]司春景,李向陽(yáng).基于多元教學(xué)模式的“軟件工程”課程改革研究[J].中國(guó)電力教育,2013(7):98-100.

[5]賈虹.淺談?dòng)⒄Z(yǔ)專業(yè)教學(xué)中商務(wù)知識(shí)的導(dǎo)入方法[J].佳木斯大學(xué)社會(huì)科學(xué)學(xué)報(bào),2007,25(2):162-163.

[6]王紅梅.算法設(shè)計(jì)與分析[M].第2版.北京:清華大學(xué)出版社，2013.

Exploration of the Reformation on Algorithm Design and Analysis Course Teaching Method

WANG Yan-qun，LIU Fu-rong

（College of Information Engineering,Tarim University，Alaer 843300）

Aiming at the problem that traditional teaching method can't get better teaching effect,puts forward the diversified method of stage based. This method has greatly improved the students'interest and practical ability in Algorithm Design and Analysis course,it is a teaching method which is worth learning and promotion.

Algorithm Design;Problem Based Teaching Method;Task Driven Teaching Method;Case Teaching Method;Group Discussion Method

1007-1423（2016）30-0015-03

10.3969/j.issn.1007-1423.2016.30.004

塔里木大學(xué)校長(zhǎng)基金項(xiàng)目（No.TDZKQN201616）、新疆南疆農(nóng)業(yè)信息化研究中心項(xiàng)目（No.TSAI201402）

王彥群（1982-），男，湖北襄陽(yáng)人，講師，碩士，研究方向?yàn)檐浖こ?、農(nóng)業(yè)信息化

劉付勇（1985-），男，講師，碩士，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)、農(nóng)業(yè)信息化，E-mail：417416506@qq.com

2016-09-08修稿日：2016-10-16