劉少兵+周婭+繆裕青
(桂林電子科技大學(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é)議。