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

劉少兵+周婭+繆裕青

（桂林電子科技大學 計算機與信息安全學院，廣西 桂林 541004）

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

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

中圖分類號：G642.41 文獻標志碼：A 文章編號：1674-9324（2017）18-0172-02

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

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

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

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

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

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

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

目前的實驗指導書不完整，內(nèi)容少，啟發(fā)性的東西較少，學生難以完成，做完后收獲不能達到預期。撰寫指導書，從問題→模型→算法→程序，讓學生容易接受和掌握，并能由點及面，解決一類相似問題。比如，在講分治算法時，會重新學習幾種常見的通用排序算法：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ǔ)上，得出找一個隨機集合中第k小的元素算法：kth（A，k）：（1）Sort A.（2）return the kth value in A.

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

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

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

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

三、實驗教學形式的革新

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

四、結(jié)論

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

參考文獻：

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

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

收稿日期：2016-11-30

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

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