《算法設(shè)計與分析》啟發(fā)式實驗教學(xué)方法探討

劉少兵+周婭+繆裕青

（桂林電子科技大學(xué) 計算機(jī)與信息安全學(xué)院，廣西 桂林 541004）

摘要：《算法設(shè)計與分析》課程是計算機(jī)軟件類專業(yè)的一門核心課程，旨在培養(yǎng)學(xué)生用算法解決實際工程問題的能力，實驗部分更突出強調(diào)學(xué)生實際動手能力的培養(yǎng)。提出教學(xué)內(nèi)容革新：以啟發(fā)式實際問題為主，增加綜合實驗和選做實驗，增加以小組形式完成的實驗項目；提出實驗指導(dǎo)書撰寫思路上的革新：從問題→模型→算法→程序的思路撰寫實驗指導(dǎo)書；提出了在教學(xué)形式上革新：制作6個常用算法的微課視頻供學(xué)生參考等。通過這些方法來切實提高學(xué)生的實際動手能力。

關(guān)鍵詞：算法；實驗教學(xué)改革；啟發(fā)式問題設(shè)計

中圖分類號：G642.41 文獻(xiàn)標(biāo)志碼：A 文章編號：1674-9324（2017）18-0172-02

《算法設(shè)計與分析》課程是我校的省級精品課程。這門課程的理論課的師資力量雄厚，然而該課程的實驗教學(xué)師資、教學(xué)水平相對薄弱，實驗內(nèi)容近些年沒有更新和補充，因此，對《算法設(shè)計與分析》實驗進(jìn)行革新，豐富區(qū)精品課程的薄弱部分、培養(yǎng)學(xué)生用算法解決問題的實踐動手能力具有很現(xiàn)實的意義。然而經(jīng)過近3年的教學(xué)實踐，卻發(fā)現(xiàn)如下問題：（1）學(xué)生對算法知識的理解和掌握不夠；（2）不能按要求完成實驗內(nèi)容。過半數(shù)的學(xué)生不能按時獨立完成實驗，收獲較?。唬?）實驗抄襲現(xiàn)象嚴(yán)重，導(dǎo)致教學(xué)目的失敗。本文主要討論實驗教學(xué)部分，希望能夠給同行提供一點借鑒之處。

一、實驗教學(xué)內(nèi)容上的改革

本課題組認(rèn)為，對待《算法設(shè)計與分析》這門特別強調(diào)學(xué)生的動手能力的課程，要有更高的要求：學(xué)生應(yīng)該具備解決綜合問題的編程能力。而限于實驗學(xué)時有限，學(xué)生很難在規(guī)定的2個學(xué)時內(nèi)完成實驗內(nèi)容，從而使教師不能客觀地評價學(xué)生。這樣導(dǎo)致很多實驗內(nèi)容顯得知識點單一，考核內(nèi)容單一，不能充分調(diào)動學(xué)生的學(xué)習(xí)積極性，學(xué)生最后的動手能力不能得到充分的挖掘和開發(fā)。這里舉例說明，下面是我院《算法設(shè)計與分析》實驗指導(dǎo)書中貪心算法一章中要求完成的實驗內(nèi)容：

實驗內(nèi)容：（1）編程實現(xiàn)背包問題貪心算法。

（2）背包問題的實驗數(shù)據(jù)如表1：N=8，M=110，即8種物品，最大負(fù)載110。

應(yīng)該說上面的實驗題基本滿足了對貪心算法的學(xué)習(xí)和實踐編程要求。不足之處也是顯而易見的：一是考核的知識點單一；二是考核的題目太模型化；三是不適合小組形式合作完成，如果學(xué)生不能完成，必然導(dǎo)致抄襲過關(guān)；四是題目太少，一人做出，全班做出的局面很常見。為了較好地解決上述不足，課題組提出每次實驗的內(nèi)容至少包含一道綜合實驗題，一個綜合題包括2—3個模塊，由一個小組（建議每個小組2—3人）來共同完成。比如可以引入“數(shù)列極差問題”作為一道綜合實驗題。問題要求：在黑板上寫了N個正整數(shù)組成的一個數(shù)列，進(jìn)行如下操作：每次擦去其中的兩個數(shù)a和b，然后在數(shù)列中加入一個數(shù)a×b+1，如此下去直至黑板上剩下一個數(shù)，在所有按這種操作方式最后得到的數(shù)中，最大的為max，最小的為min，則該數(shù)列的極差定義為M=max-min。這個實驗選題就比以前的題目要好，一是它主體還是用貪心算法，但又和霍夫曼樹構(gòu)造類似；二是用到了兩個獨立的求最大、最小值，都需要用到貪心算法。這樣把一個大的問題分成2個小的模塊，該題可以由2個同學(xué)協(xié)作完成，一人完成一個模塊，由于絕對工作量的減少，學(xué)生能夠在實驗時間完成；團(tuán)隊合作，使學(xué)生的自信心會明顯增強。既培養(yǎng)了大學(xué)生之間的協(xié)作能力，又有效地降低了學(xué)生大面積抄襲行為。這里可能有的任課老師會提出，到哪里去找那么多綜合性強但難度又不是很大的題目來讓學(xué)生來完成呢？筆者認(rèn)為可以這樣來解決：一是合理利用網(wǎng)絡(luò)資源；二是任課老師將實際項目、畢設(shè)、課設(shè)或工作等拆解而來；三是最重要的一點，就是需要任課老師多花點時間和精力在教學(xué)上，這是業(yè)界良心。

二、實驗指導(dǎo)書撰寫組織思路：從問題→模型→算法→程序

目前的實驗指導(dǎo)書不完整，內(nèi)容少，啟發(fā)性的東西較少，學(xué)生難以完成，做完后收獲不能達(dá)到預(yù)期。撰寫指導(dǎo)書，從問題→模型→算法→程序，讓學(xué)生容易接受和掌握，并能由點及面，解決一類相似問題。比如，在講分治算法時，會重新學(xué)習(xí)幾種常見的通用排序算法：SORT（A）：（1）If small，just return A.（2）Split A into A1 and A2.（3）S1 is Sort（A1）.（4）S2 is Sort（A2）.（5）Return combine（S1，S2）.

在排序的基礎(chǔ)上，得出找一個隨機(jī)集合中第k小的元素算法：kth（A，k）：（1）Sort A.（2）return the kth value in A.

然后進(jìn)行如下啟發(fā)式問題設(shè)計：Consider A containing the values 1，2，…，10.

（1）對該特殊數(shù)組排序后，第k小的元素位置？

（2）進(jìn)行一次劃分后的數(shù)組如下：Charles Hoot 5/30/12 7：16 PM（3）如果我們在找第4小的元素，那么它會在哪個部分？劃分元素的前面還是后面？（4）如果有n個元素的集合，我們要找到第k小的元素，所有查找比較次數(shù)？（5）給出各種算法所花的時間，完成表格。

在設(shè)計以上啟發(fā)式問題之后，然后學(xué)生理解了該怎么做，也真正理解了分治算法的本質(zhì)，也有信心寫出代碼，不至于導(dǎo)致實驗培養(yǎng)目的失效（限于篇幅，只設(shè)計了幾個啟發(fā)式問題，實際的時候一個算法實驗至少設(shè)計6—10個啟發(fā)式問題以上較好）。

三、實驗教學(xué)形式的革新

目前隨著網(wǎng)絡(luò)資源豐富，教師的權(quán)威性在學(xué)生眼里大幅降低，教師所講的內(nèi)容學(xué)生都會從網(wǎng)絡(luò)中去求證或者比對。這本無可厚非，也是學(xué)生尋求真知灼見的好方面，但問題是學(xué)生的學(xué)習(xí)時間也有限，在查找一些沒有太多實際意義的小問題上花了太多時間，這是消極影響。既然這樣，還不如我們?nèi)握n教師有的放矢，針對自己學(xué)生實際水平制作微課視頻，有針對性地講清楚幾個常用算法——窮舉算法、分治算法、貪心算法、動態(tài)規(guī)劃、回溯算法、分支限界算法、隨機(jī)算法等?！端惴ㄔO(shè)計與分析》實驗通常涉及到后面的6個算法，因而建議實驗教師錄制6個常用算法微課視頻供學(xué)生碎片時間里學(xué)習(xí)，為順利和有效地完成實驗做準(zhǔn)備。

四、結(jié)論

增加啟發(fā)式問題是學(xué)生深入學(xué)習(xí)理解算法的關(guān)鍵，也能夠增加算法的印象和完成實驗的信心，適當(dāng)增加綜合性實驗和小組合作實驗，能夠為學(xué)生在實際工作中解決復(fù)雜工程問題和團(tuán)隊協(xié)作能力打下基礎(chǔ)；提供6個常用算法的微課視頻是理論教學(xué)的良好補充。當(dāng)然，每門課程都有各自的特點，因材施教，因課施教，是不斷摸索和積累的過程。

參考文獻(xiàn)：

[1]劉少兵，等.《程序設(shè)計與問題求解》理論教學(xué)方法研討[J].科學(xué)時代，2010，（22）：106-107.

[2]繆裕清，等.《程序設(shè)計與問題求解》實驗教學(xué)方法探討[J].教育教學(xué)論壇，2015，（20）：158-159.

收稿日期：2016-11-30

基金項目：2015年廣西高等教育本科教學(xué)改革工程項目，（項目編號2015JGB211）；本文受國家級實驗教學(xué)示范中心——桂林電子科技大學(xué)計算機(jī)實驗教學(xué)中心項目資助，項目號：ZJW43010

作者簡介：劉少兵（1973-），男，湖北荊州人，講師，碩士，主要研究方向：算法優(yōu)化與算法理論、網(wǎng)絡(luò)底層通信協(xié)議。