應(yīng)用型本科院校《算法設(shè)計(jì)與分析》課程實(shí)踐教學(xué)改革研究

趙曉麗

（長治學(xué)院計(jì)算機(jī)系,山西長治046011）

?

應(yīng)用型本科院校《算法設(shè)計(jì)與分析》課程實(shí)踐教學(xué)改革研究

趙曉麗

（長治學(xué)院計(jì)算機(jī)系,山西長治046011）

結(jié)合應(yīng)用型人才培養(yǎng)的目標(biāo)和理念，文章分析了《算法設(shè)計(jì)與分析》課程教學(xué)模式存在的弊端，提出了基于問題式實(shí)踐教學(xué)改革方案，探討了問題式實(shí)踐教學(xué)模式在課程教學(xué)中的重要性。

問題式；實(shí)踐教學(xué)；教學(xué)模式

引言

算法設(shè)計(jì)與分析是衡量軟件性能優(yōu)劣的一個(gè)核心指標(biāo)，也是應(yīng)用型本科院校中計(jì)算機(jī)專業(yè)本科生的一門必修的專業(yè)基礎(chǔ)課程。課程通過對經(jīng)典算法思想、特征與求解步驟進(jìn)行學(xué)習(xí)，使學(xué)生能夠掌握相關(guān)理論和使用技巧，培養(yǎng)學(xué)生正確分析算法的時(shí)空復(fù)雜性的能力和解決實(shí)際問題的算法設(shè)計(jì)能力，并從眾多方案中擇優(yōu)求解，對已有算法進(jìn)行分析改進(jìn)，為編寫出高效程序、開發(fā)優(yōu)秀軟件奠定堅(jiān)實(shí)的理論基礎(chǔ)。因此，算法設(shè)計(jì)的思維邏輯培養(yǎng)成為計(jì)算機(jī)專業(yè)人才培養(yǎng)的重要環(huán)節(jié)。在教學(xué)過程中為了增強(qiáng)學(xué)生的實(shí)踐應(yīng)用能力，就迫切需要進(jìn)行實(shí)踐教學(xué)的改革，從而構(gòu)建符合應(yīng)用型本科院校發(fā)展的教學(xué)模式，推動高校計(jì)算機(jī)專業(yè)教育的教學(xué)改革。

文章以“算法設(shè)計(jì)與分析”這門課程為研究對象，通過課堂教學(xué)模式多樣化的嘗試，針對課程在應(yīng)用型本科院校教學(xué)中的教學(xué)內(nèi)容、教學(xué)模式、實(shí)驗(yàn)項(xiàng)目訓(xùn)練驗(yàn)、綜合應(yīng)用四個(gè)方面問題，提出建立“問題+算法策略+實(shí)驗(yàn)”的實(shí)踐教學(xué)模式。

1　教學(xué)現(xiàn)狀

《算法設(shè)計(jì)與分析》作為計(jì)算機(jī)專業(yè)的課程，目的是為了讓學(xué)生對算法的基本理論，培養(yǎng)學(xué)生對實(shí)際問題的算法設(shè)計(jì)思維[1]。課堂采用理論教學(xué)，盡管學(xué)生具備數(shù)據(jù)結(jié)構(gòu)和編程語言的基礎(chǔ)，但課堂教學(xué)之后，學(xué)生運(yùn)用所學(xué)算法策略進(jìn)行獨(dú)立自主地求解實(shí)際問題的能力十分欠缺。針對這種情況，對長治學(xué)院計(jì)算機(jī)系2014級學(xué)生進(jìn)行問卷調(diào)查，調(diào)查結(jié)果表明學(xué)生對課堂教學(xué)的接受情況不理想，具體情況如下所示：

人數(shù)所占比例接受程度56%30%～50% 25%>60% 9%10% 10%>80%

從結(jié)果看，有將近一半的學(xué)生只能接受知識的30%-50%，1/4的學(xué)生接受60%以上，只有1/10的學(xué)生能接受80%以上。由此可以看出學(xué)生接受情況并不是很好。課堂上雖然是多媒體ppt+板書講解的教學(xué)模式，但教師講解依然是中心，因此學(xué)生只能被動接受。

《算法設(shè)計(jì)與分析》課程的傳統(tǒng)教學(xué)模式對課程教學(xué)效果不好，隨著各種算法內(nèi)容的加深學(xué)習(xí)，學(xué)生會感覺越來越力不從心。這樣的教學(xué)模式太過于單調(diào)，只是一味的以枯燥的理論知識為主進(jìn)行講解，學(xué)生也只能被動的接受算法思想和強(qiáng)行記憶算法步驟，極大地降低了學(xué)生的學(xué)習(xí)興趣和積極性。其次“算法”教學(xué)方法上仍側(cè)重理論教學(xué)而忽視實(shí)踐教學(xué)，在學(xué)習(xí)算法設(shè)計(jì)策略和分析算法的時(shí)候，互動缺乏，導(dǎo)致課堂教學(xué)質(zhì)量低。在幾乎沒有實(shí)驗(yàn)課的課堂教學(xué)中，缺少綜合應(yīng)用算法的實(shí)踐性應(yīng)用項(xiàng)目，使得學(xué)生面對實(shí)際問題只能通過網(wǎng)絡(luò)來尋求解決方法。這樣的教學(xué)模式既不能培養(yǎng)學(xué)生的創(chuàng)造性思維，也不能提升解決實(shí)際問題的應(yīng)用實(shí)踐能力，根本不能完成教學(xué)目標(biāo)，所以，對《算法設(shè)計(jì)與分析》課程的教學(xué)模式進(jìn)行實(shí)踐性教學(xué)改革是十分重要的。

2　教學(xué)改革方案

針對課程教學(xué)過程中存在的問題，通過引入問題式實(shí)踐教學(xué)模式，激發(fā)了學(xué)生的學(xué)習(xí)熱情，教學(xué)效果十分明顯。因此，在教學(xué)中按照“問題提出、算法設(shè)計(jì)、實(shí)驗(yàn)實(shí)踐”的教學(xué)模式進(jìn)行實(shí)踐性教學(xué)是非常有必要的。具體實(shí)施方案如下。

2.1優(yōu)化教學(xué)內(nèi)容

算法設(shè)計(jì)與分析這門課程，需要學(xué)生具備良好的抽象邏輯思維能力及程序設(shè)計(jì)技巧。盡管學(xué)生之前都學(xué)習(xí)過“數(shù)據(jù)結(jié)構(gòu)”和“高級語言程序設(shè)計(jì)”這兩門課程，起初學(xué)習(xí)起來也都有興趣，但隨著課程內(nèi)容的深入學(xué)習(xí)，難度增大，導(dǎo)致學(xué)生學(xué)習(xí)困難。

因此，需要把課程中的各個(gè)算法思想的精華部分提取出來，對所講的教學(xué)內(nèi)容進(jìn)行優(yōu)化。每個(gè)算法都有各自的思想、步驟、基本特征要素,但彼此也有一定的關(guān)系。這樣我們就可以在學(xué)習(xí)每個(gè)算法的時(shí)候與所掌握的算法進(jìn)行對比,找出各自的相同點(diǎn)和不同點(diǎn)，不僅加深對算法的理解，使學(xué)生掌握算法基本特點(diǎn)、問題適用性及在具體例子中的靈活應(yīng)用，也為設(shè)計(jì)出效率較高的算法、編制程序、分析和優(yōu)化算法打好堅(jiān)定的基礎(chǔ)。

2.2問題式教學(xué)模式[4]

通過一些應(yīng)用性強(qiáng)的實(shí)例，激發(fā)學(xué)生自主學(xué)習(xí)的興趣，幫助學(xué)生構(gòu)建對經(jīng)典算法知識的認(rèn)知體系。如：分治算法、動態(tài)規(guī)劃算法和貪心算法，可以根據(jù)之間的關(guān)聯(lián)對比進(jìn)行學(xué)習(xí)。把重點(diǎn)放在對算法的設(shè)計(jì)上，讓學(xué)生學(xué)會如何對類似問題進(jìn)行算法的選擇、設(shè)計(jì)與實(shí)現(xiàn)[3]。

比如最優(yōu)子結(jié)構(gòu)性質(zhì)，這個(gè)知識點(diǎn)就貫穿在這三個(gè)算法中。通過0-1背包問題和普通背包問題的算法應(yīng)用，進(jìn)行多方面的對比分析，把分治算法、動態(tài)規(guī)劃算法和貪心算法的應(yīng)用要點(diǎn)進(jìn)行串聯(lián)，使得學(xué)生對這三個(gè)算法策略有了非常清晰的認(rèn)識。這種問題式啟發(fā)教學(xué)可以讓學(xué)生通過模仿，進(jìn)行實(shí)際問題的分析與算法應(yīng)用求解，從而使學(xué)生有自主獨(dú)立學(xué)習(xí)的興趣。

2.3建立開放實(shí)驗(yàn)項(xiàng)目訓(xùn)練

針對實(shí)踐應(yīng)用與理論教學(xué)嚴(yán)重脫節(jié)的弊端，筆者采用了開放式實(shí)驗(yàn)項(xiàng)目訓(xùn)練模式[2]，把學(xué)過的理論知識通過問題分析、算法分析、算法設(shè)計(jì)、算法實(shí)現(xiàn)這四大步加以實(shí)踐。在這樣的開放實(shí)驗(yàn)環(huán)境中，師生充分互動，不僅提高了教學(xué)質(zhì)量，也大大加深了學(xué)生對知識點(diǎn)的理解與應(yīng)用。

2.4增強(qiáng)經(jīng)典算法的綜合應(yīng)用

除了以上方面，還可以在教學(xué)中選取一些經(jīng)典問題,采用不同算法加以實(shí)現(xiàn)。對實(shí)現(xiàn)的各種算法的復(fù)雜度分析，并與實(shí)驗(yàn)結(jié)果進(jìn)行比較，從而正確評價(jià)每個(gè)算法的優(yōu)缺點(diǎn)。不僅如此，通過對這些經(jīng)典問題的綜合分析，可以對已有的條件進(jìn)行改變，正確引導(dǎo)學(xué)生對問題的深層次思考,培養(yǎng)他們的思考能力、邏輯能力及動手能力,加強(qiáng)經(jīng)典算法的綜合應(yīng)用。

3　問題式實(shí)踐教學(xué)模式的案例設(shè)計(jì)

為了進(jìn)一步說明上述教學(xué)模式，筆者通過一個(gè)教學(xué)案例《貪心算法—普通背包問題》來說明教學(xué)改革方案的執(zhí)行，案例設(shè)計(jì)如下。

（1）問題的確定。

問題:在給定n種物品選擇一種裝包方案使得裝入背包中物品的總價(jià)值最大?其中，物品的重量（Wi），價(jià)值（Pi），背包重量（M）。在動態(tài)規(guī)劃算法中對《0-1背包問題》進(jìn)行了動態(tài)規(guī)劃步驟的求解。解是（X1,X2,…Xn）,Xi=0,1

在此基礎(chǔ)上提出新的問題-普通背包問題，它與0-1背包問題類似，只是物品的裝入狀態(tài)0≤Xi≤1,直到背包裝滿為止。這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似。但由于背包可以裝入物品的一部分，那么普通背包問題還能否用動態(tài)規(guī)劃算法求解呢？問題提出來，為引入新的算法打好基礎(chǔ)，這就使得基于問題的教學(xué)模式很恰當(dāng)。

（2）情境創(chuàng)設(shè)，提出問題

結(jié)合一個(gè)實(shí)際的例子，背包重量M=20，物品n=3,重量、價(jià)值分別為（w1，w2，w3）=（15,10,15）；

由教師直接拋出問題，采用窮舉法求解。

（3）分析問題

根據(jù)問題的特點(diǎn)，按照生活實(shí)踐經(jīng)驗(yàn)，我們給出三種求解思路。

①以重量wi從小到大排列輸入”為量度標(biāo)準(zhǔn)

②以“價(jià)值pi從大到小排列輸入”為量度標(biāo)準(zhǔn)：

③以“單位重量價(jià)值pi/wi從大到小輸入”為量度標(biāo)準(zhǔn)：

學(xué)生們分組討論，分析各種實(shí)際情況的出現(xiàn)，最終給出解決問題的最優(yōu)步驟，以“單位重量價(jià)值pi/wi從大到小輸入”為量度標(biāo)準(zhǔn)得出的結(jié)果是裝包價(jià)值最大的。

（4）解決問題，確定算法。

結(jié)合已學(xué)習(xí)的知識，依據(jù)剛剛得出的結(jié)論，找出解決步驟的主要性質(zhì)—貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。最終給出普通背包問題的算法步驟。①按照物品的單位重量的價(jià)值進(jìn)行由高到低的排序；②依貪心選擇策略，選擇單位重量價(jià)值最高的物品盡可能多的進(jìn)行裝包；③若此時(shí)背包未滿，繼續(xù)選擇單位重量價(jià)值次高的物品并盡可能多地裝入背包；④重復(fù)第三個(gè)步驟，直到背包無法再裝入物品為止。

（5）程序展示

根據(jù)算法步驟，給出程序代碼實(shí)現(xiàn)。

（6）總結(jié)、概括。

總結(jié)解決問題的思路，概括算法設(shè)計(jì)的方法，引導(dǎo)學(xué)生們對實(shí)際問題的算法設(shè)計(jì)過程進(jìn)行復(fù)述，將問題式思維過程用算法步驟描述出來。

4　結(jié)論

文章結(jié)合在教學(xué)中的一點(diǎn)教學(xué)實(shí)踐摸索，對算法設(shè)計(jì)與分析的教學(xué)改革進(jìn)行了探討，提出了基于問題式的實(shí)踐教學(xué)模式。通過該教學(xué)模式的改革方案的實(shí)施，較大程度的改善了此前的教學(xué)現(xiàn)狀，不僅改變了學(xué)生被動學(xué)習(xí)的學(xué)習(xí)方式，提高了教學(xué)質(zhì)量，也使得教學(xué)的互動過程更加和諧。這對于轉(zhuǎn)變傳統(tǒng)的教育觀念和培養(yǎng)學(xué)生自主學(xué)習(xí)的能力起到了主要的作用。

［1］王曉東.算法設(shè)計(jì)與分析［M］.北京:清華大學(xué)出版社,2012.

［2］徐楠.基于項(xiàng)目驅(qū)動的Java課程教學(xué)改革研究教育與職業(yè)［J］.2011,5(14）：26-27.

［3］肖小克,陳莉.《算法設(shè)計(jì)與分析》實(shí)踐教學(xué)探討［J］.福建電腦,2009,5(10):210.

［4］袁宇翔,基于問題的教學(xué)模式的構(gòu)建與應(yīng)用探究［J］.教育與職業(yè),2013.2.

（責(zé)任編輯張劍妹）

Zhao Xiao-li
（The Computer Department of Changzhi University,Changzhi Shanxi 046011）

G642

A

1673-2014（2016）02-0072-03

長治學(xué)院教研項(xiàng)目“應(yīng)用本科院校《算法設(shè)計(jì)與分析》實(shí)驗(yàn)教學(xué)改革”（JY201505）；山西省教研項(xiàng)目“基于云計(jì)算的虛擬實(shí)驗(yàn)教學(xué)改革研究”（J2014113）。

2016—03—10

趙曉麗（1980－），女，河北臨西人，碩士，主要從事計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)用技術(shù)、信息安全研究。