算法設(shè)計與分析課程研討教學(xué)的探索

郭惠芳，劉寒冰

（黃河科技學(xué)院 計算機(jī)科學(xué)系，河南 鄭州 450063）

0 引 言

算法設(shè)計與分析課程講授各類經(jīng)典算法的基本策略和算法設(shè)計與分析的基本技巧，為學(xué)生打開了更為廣闊的視野。該課程歷來在專業(yè)教學(xué)中都屬于高階的、有挑戰(zhàn)性的課程[1-2]，為此各院校就如何提高該課程教學(xué)效果與質(zhì)量進(jìn)行了有益的探索[3-4]。應(yīng)用技術(shù)類院校培養(yǎng)人才的側(cè)重點是應(yīng)用型人才，算法設(shè)計與分析課程對于培養(yǎng)學(xué)生分析、解決問題的能力，提高學(xué)生實際編程技能有重要的作用。然而課程抽象理論偏多，相當(dāng)一部分學(xué)生的基礎(chǔ)知識不夠扎實，接受能力有限。每年課程剛開始時，學(xué)生對算法設(shè)計有較濃的興趣，這個從他們熱切的眼神中可以看出來，但隨著課程的推進(jìn)，部分學(xué)生遇到了一些困難，學(xué)習(xí)參與度降低，課堂效率降低。

1 研討課的設(shè)想

為了改善算法設(shè)計與分析課程的教學(xué)效果，希望通過研討課的模式，在教學(xué)過程中啟發(fā)學(xué)生研究和探索的興趣，培養(yǎng)學(xué)生發(fā)現(xiàn)問題、提出問題、解決問題的意識和能力。首先引導(dǎo)學(xué)生在課下進(jìn)行自“研”：充分利用老師提供的及網(wǎng)上的學(xué)習(xí)資源，就布置的專題查閱資料，研究其內(nèi)在原理和過程。然后在課上的“討”：匯報研究的內(nèi)容，并將研究過程中遇到的問題提出來討論。我們?yōu)樵撜n程設(shè)計了1個課外開放專題、4個課內(nèi)專題，課前2周布置。

1.1 課外開放專題

基于前序數(shù)據(jù)結(jié)構(gòu)課程的學(xué)習(xí)，引導(dǎo)學(xué)生了解算法在各行各業(yè)中的運用，如大數(shù)據(jù)挖掘中的算法、導(dǎo)航系統(tǒng)中的算法等。督促學(xué)生查閱在各個應(yīng)用領(lǐng)域得到較好應(yīng)用的算法，通過查找相關(guān)資料，引導(dǎo)大家了解算法應(yīng)用的不同業(yè)務(wù)領(lǐng)域，并寫出報告，在研討課中進(jìn)行匯報與討論。

1.2 課內(nèi)專題

課內(nèi)專題是在教材[5]的每類算法中選擇一個問題進(jìn)行討論。

（1）分治法中選擇了快速排序，要求課下通過閱讀相關(guān)材料，給出快排中劃分方法的幾種實現(xiàn)，討論使用尾元素作為劃分基準(zhǔn)的方法。

（2）動態(tài)規(guī)劃方法中選擇了最大子段和的求解，要求課下閱讀相關(guān)材料，分別給出窮舉法、分治法以及動態(tài)規(guī)劃方法的實現(xiàn)，討論3種方法的時間復(fù)雜度，體會相同問題的不同算法效率的差別。

（3）貪心算法中選擇了貪心算法適用性的討論，以0-1背包和背包問題為案例，說明貪心算法的適用性，同時討論找零錢問題的貪心算法的適用性。

（4）回溯法和分支限界法選擇了迷宮問題進(jìn)行討論，要求分別給出迷宮問題的回溯法（以深度優(yōu)先搜索順序）以及分支限界法（以廣度優(yōu)先搜索順序/最優(yōu)目標(biāo)值優(yōu)先順序）的求解方法，并給出搜索軌跡，討論兩種方法的聯(lián)系及區(qū)別。

通過課下研究、課上討論，引導(dǎo)學(xué)生獨立思考，深入理解相關(guān)內(nèi)容，逐步掌握經(jīng)典算法的設(shè)計技巧，提高代碼編寫的能力，同時不斷樹立學(xué)習(xí)的自信心，提高自主學(xué)習(xí)的能力。

2 研討課的實施

2.1 課外專題研討的困境

研討題目和要求布置一周后，發(fā)現(xiàn)學(xué)生課下研究的主動性不高，詢問后得知，獨立自主地選擇一個主題、查資料進(jìn)行研究對于他們還有些陌生。經(jīng)過在線的跟蹤指導(dǎo)，學(xué)生上報了一些好的選題，例如，百度云秒傳功能的實現(xiàn)——淺談Hash算法、網(wǎng)易云音樂的推薦算法、地圖中最短路徑的搜索算法研究、遺傳算法、數(shù)獨算法、衛(wèi)星導(dǎo)航定位系統(tǒng)等。

在隨后的專題研究中，大部分學(xué)生有等、靠、拖的思想，部分學(xué)生研究、思考浮于表面，上交的匯報很大程度上是從網(wǎng)上摘抄下來且沒有自己的理解與思考的內(nèi)容。在老師的持續(xù)督促及指導(dǎo)下，一部分學(xué)生查詢與消化相關(guān)專題的資料，課下進(jìn)行了較為細(xì)致的研究，共有5組學(xué)生進(jìn)行了課上匯報。課外專題匯報過程中，臺下的學(xué)生雖然有一定的興趣，但極少發(fā)言，大部分學(xué)生未能真正進(jìn)入討論狀態(tài)，主要原因是臺下學(xué)生很難明白臺上講的內(nèi)容，課外專題的研討未能達(dá)到預(yù)期狀態(tài)。

2.2 化整為零的課內(nèi)專題研討

課外專題研討的冷場說明，研討環(huán)節(jié)中的“研”完全依賴學(xué)生課下進(jìn)行自主地學(xué)習(xí)與研究是有一定困難的，就一個完整問題進(jìn)行研究，學(xué)生畏難情緒重，自學(xué)能力偏弱。僅僅開展形式上的研討教學(xué)，并不能達(dá)到預(yù)期，研討的內(nèi)容必須根據(jù)不同的教學(xué)對象進(jìn)行相應(yīng)調(diào)整，于是我們將每個算法問題化整為零，降低研究難度，將部分完整專題分解為局部問題的討論。

1）快速排序。

我們將研討題目細(xì)分為4個子題目：①利用一個劃分實例演示以首元素為基準(zhǔn)進(jìn)行劃分的過程；②在前者基礎(chǔ)上，i、j指針輪流進(jìn)行掃描后進(jìn)行交換以及i、j掃描后即進(jìn)行元素的移動，兩種方式分別進(jìn)行演示；③以尾元素進(jìn)行劃分基準(zhǔn)，以實例演示劃分過程；④實例演示后，對照過程實現(xiàn)該過程的程序代碼。

分解后的每個子題目分配給一位學(xué)生準(zhǔn)備，課上進(jìn)行演示，由于難度降低，學(xué)生完成度高，其余學(xué)生對相應(yīng)問題都有一定的知識基礎(chǔ)，學(xué)生在臺上的每個演示動作可能都反映了臺下部分學(xué)生的思路，學(xué)生容易進(jìn)入狀態(tài)，上臺同學(xué)積極思考，臺下同學(xué)積極討論，遇到困難時，學(xué)生就自告奮勇地上臺來進(jìn)行糾正，討論氣氛完全達(dá)到了預(yù)期效果。參與度的提高帶來的是學(xué)習(xí)熱情的高漲。

2）貪心算法。

專題分為3個子題目：①背包問題的貪心算法實例演示；②0-1背包問題貪心法的失敗實例演示；③找零錢的貪心算法成功與失敗的實例演示。

該專題的子題目難度較低，學(xué)生參與度比較高，學(xué)生研究、討論得非常成功，在總結(jié)討論為何背包問題可以用貪心法求解，而0-1背包問題不一定能用貪心法得到最優(yōu)解時，大部分學(xué)生都能比較清晰地回答其關(guān)鍵所在。

3）迷宮問題。

被分解為3個子問題：①深度優(yōu)先的回溯解法；②廣度優(yōu)先的分支限界法；③針對后者的優(yōu)化手段有哪些？

學(xué)生對該問題表現(xiàn)了很大的興趣，前兩個學(xué)生分別演示了自己實現(xiàn)的程序，界面各有特色，并顯示了訪問路線，直觀地讓同學(xué)們看到了兩種方法的區(qū)別，優(yōu)劣一目了然。準(zhǔn)備優(yōu)化方法的學(xué)生雖然沒有講到重點上，但是在老師的提示下，臺下的學(xué)生最終提出了比較好的優(yōu)化方法。經(jīng)過這個專題的研討，學(xué)生對回溯法與分支限界法有了比較直觀的理解，增加了解決問題的自信心。在課堂討論過程中，涌現(xiàn)了一些有想法、有探索欲望的學(xué)生，還有一些學(xué)生展示了良好的表達(dá)能力，這些學(xué)生課下能夠主動與老師在線討論、交流課外學(xué)習(xí)的內(nèi)容，研討的氛圍逐步建立。

2.3 實驗環(huán)節(jié)的自發(fā)研討

以往在實驗課前，老師將上機(jī)題目布置下去，上機(jī)時由老師在實驗室輔導(dǎo)答疑，最后學(xué)生上交實驗報告，老師據(jù)此打分。這個過程中部分學(xué)生學(xué)習(xí)不夠認(rèn)真、抄襲現(xiàn)象頻發(fā)；還有一部分學(xué)生想獨立完成，但遇到問題沒有勇氣請老師來幫助，最終放棄。

將“研討”精神引入實驗室，激發(fā)學(xué)生想學(xué)習(xí)的潛在欲望。首先要求抽簽決定上機(jī)題目，老師貼近學(xué)生，及時發(fā)現(xiàn)學(xué)生的學(xué)習(xí)狀態(tài)，主動詢問引導(dǎo)，鼓勵他們相互討論和幫助。老師對每位學(xué)生實施一對一答辯，再據(jù)此打分。這一點對學(xué)生促動很大，在實驗環(huán)節(jié)中自發(fā)地形成小組，進(jìn)行討論，相互研討、學(xué)習(xí)的氣氛因而顯現(xiàn)。

打分是在答辯后進(jìn)行，學(xué)生如果希望得到一個高分，就必須平時多下工夫，在老師面前有一個好的表現(xiàn)，如：為了搞清一個問題，常有學(xué)生中午在實驗室加班調(diào)程序，也有學(xué)生自己感覺分?jǐn)?shù)低，經(jīng)過持續(xù)的努力，要求老師再次考核，這些現(xiàn)象都令老師感到欣慰，沒有比學(xué)生自己想要學(xué)更好的學(xué)習(xí)方法了。

3 課程考核

考核是檢驗教學(xué)方法優(yōu)劣和督促學(xué)習(xí)的一種有效手段。本次課程考核分為平時考核、實驗考核以及期末考核。實驗考核方法上面已有闡述，平時考核中增加了課堂測試環(huán)節(jié)。

3.1 課堂的測試環(huán)節(jié)

課內(nèi)研討的氣氛調(diào)動了大部分同學(xué)的積極性，但為了防止部分同學(xué)只看熱鬧，學(xué)習(xí)中不求甚解、浮于表面，在課堂上增加了測試環(huán)節(jié)，學(xué)生平時課堂的測試參與度及測試成績作為平時考核的一部分，計入課程最終考核。我們已在移動互聯(lián)網(wǎng)上提供課堂測試功能，有200道左右題目可供測試，在課堂上學(xué)生利用手機(jī)進(jìn)行回答，老師可以快速了解學(xué)生每個階段的知識掌握情況。課堂上增加過程檢查環(huán)節(jié)，督促和幫助學(xué)生及時進(jìn)行復(fù)習(xí)，同時促進(jìn)學(xué)生獨立地完成作業(yè)。

3.2 期末考核

計算機(jī)科學(xué)專業(yè)班沒有進(jìn)行研討課的試點，但是在課堂上對大部分的算法實例都采用研討式的講法，只是未進(jìn)行課外專題的研究和討論，同時也增加了課堂測試環(huán)節(jié)。全班人數(shù)30人，期末考核平均分為80.3，總分分布如圖1虛線所示。相比前二屆（前后試卷難度相當(dāng)）的成績（78分左右）有明顯提高。

軟件工程專業(yè)是研討課試點班，全班共45人，平均分81.4，總分的分布情況如圖1實線所示，成績相比前二屆的學(xué)生成績有較大提高，橫向比較，相比計算機(jī)科學(xué)專業(yè)班的成績也有些優(yōu)勢。軟件工程專業(yè)出現(xiàn)一個99分最高分，90分以上有9人，這部分學(xué)生知識掌握得很好，失分基本是由個別的填空或問答題的回答不準(zhǔn)確造成的。80分以上有18人，這部分學(xué)生對知識的掌握基本達(dá)到預(yù)期，在分析和設(shè)計題中有少量失分，基本概念部分（問答題或填空題）掌握較好。

圖1 計算機(jī)專業(yè)與軟件專業(yè)期末卷面分分布圖

4 結(jié) 語

從課內(nèi)專題研討的情況看，本次研討課的開展在提高學(xué)生學(xué)習(xí)興趣和學(xué)習(xí)參與度方面有明顯效果；期末考試中極低分?jǐn)?shù)明顯減少，同時80分以上同學(xué)的占比顯著提高，這些都說明，在實驗環(huán)節(jié)營造研討氛圍、在課堂測試環(huán)節(jié)保證學(xué)習(xí)熱情持久性等措施對于提高學(xué)習(xí)成績是有效果的。

培養(yǎng)應(yīng)用型人才，首要的是樹立學(xué)生的自信心和鼓勵學(xué)生探索的勇氣，這是培養(yǎng)任何能力和素養(yǎng)的前提，研討課的開展也必須遵循這個前提。要取得良好的教學(xué)效果，研討教學(xué)的形式不是最重要的，重要的是以下3個關(guān)鍵點：①內(nèi)容大于形式，研討課的內(nèi)容組織要能真正調(diào)動大部分學(xué)生的積極性；②態(tài)度決定成敗，貫徹教學(xué)始終的研討態(tài)度與習(xí)慣要能挖掘出學(xué)生潛在的學(xué)習(xí)欲望；③過程控制是保障，從每個教學(xué)環(huán)節(jié)督促與檢查是研討課取得成績的必要條件。本次研討課雖然取得了一些成績，但教學(xué)本身就是一個不斷研究與討論的過程，教學(xué)研討抑或是研討教學(xué)都將繼續(xù)進(jìn)行，因為研討本就是一種工作、學(xué)習(xí)態(tài)度，作為教師，我們要傳遞的就是，知識絕不僅僅是老師說的、書上寫的，更多的要通過自己的探究與檢驗才能得到。

參考文獻(xiàn)：

[1]陳翔. 面向算法設(shè)計與分析課程的翻轉(zhuǎn)課堂教學(xué)模式研究[J]. 計算機(jī)教育, 2016(8): 147-151.

[2]李志欣. 算法設(shè)計與分析課程的教學(xué)探索與實踐[J]. 教育教學(xué)論壇, 2013(13): 218-219.

[3]秦董洪, 陳智勇. 算法設(shè)計與分析課程教學(xué)研究[J]. 計算機(jī)教育, 2013(11): 98-101.

[4]林劼, 戴波. 項目驅(qū)動型算法設(shè)計與分析課程教學(xué)方法[J]. 計算機(jī)教育, 2014(9): 69-71.

[5]王曉東. 計算機(jī)算法設(shè)計與分析[M]. 4版. 北京: 電子工業(yè)出版社, 2012: 20-22.