《算法設(shè)計與分析》的理論研究與教學(xué)實踐

田翠華,王偉杰,許衛(wèi)平

（1.廈門理工學(xué)院 計算機(jī)科學(xué)與技術(shù)系，福建 廈門 361024；2.沈陽工業(yè)大學(xué) 軟件學(xué)院，遼寧 沈陽 110023）

《算法設(shè)計與分析》的理論研究與教學(xué)實踐

田翠華1,2,王偉杰1,許衛(wèi)平1

（1.廈門理工學(xué)院 計算機(jī)科學(xué)與技術(shù)系，福建 廈門 361024；2.沈陽工業(yè)大學(xué) 軟件學(xué)院，遼寧 沈陽 110023）

通過對《算法設(shè)計與分析》的理論進(jìn)行深入研究，并結(jié)合自己實際的教學(xué)實踐，充分地認(rèn)識到這門課的重要性、了解這門課的特點.并對存在的問題進(jìn)行分析，在此基礎(chǔ)上提出了更好的教授這門課程的方法與更能促進(jìn)這一學(xué)科發(fā)展的策略，形成自己的特色教學(xué).

算法；游戲教學(xué)；特色教學(xué)

《算法設(shè)計與分析》是計算機(jī)科學(xué)的一個重要分支，是計算機(jī)科學(xué)的基礎(chǔ)，更是程序設(shè)計的核心[1].所以，算法課程對計算機(jī)系學(xué)生來說非常重要，是計算機(jī)系軟件、硬件等專業(yè)必修的基礎(chǔ)課程.而且，算法所涉及的范圍十分廣泛[2]，從理論到各種實際問題的解決，無一不與算法有密切關(guān)系，都需要研究方法.同時，算法研究又是實現(xiàn)計算機(jī)解決問題的方法，十分的抽象與復(fù)雜，這些都導(dǎo)致學(xué)生對這門課的學(xué)習(xí)非常困難.

1 理論研究與教學(xué)實踐

在沒教《算法設(shè)計與分析》這門課程的時候，只聽說它與多門課程教學(xué)緊密相連，所以，針對教這門課的教師來說，其教學(xué)理論基礎(chǔ)必須深厚，教學(xué)實踐經(jīng)驗必須豐富.教過之后，才知道它涉及的又何止是教學(xué)的理論基礎(chǔ)與實踐？還需要工程實踐經(jīng)驗[3-4].幸虧在軟件公司搞軟件開發(fā)工作多年，有實際的編程經(jīng)歷.想起接這門課的時候，人們都說這門課不好講，當(dāng)時，還不能理解這句話的份量，直到現(xiàn)在通過實際教學(xué)親身體驗后，才明白其中的道理.

1.1 相關(guān)知識多

學(xué)這門課的學(xué)生，要求具備很多學(xué)科的知識：高等數(shù)學(xué)、離散數(shù)學(xué)、線性代數(shù)、概率論、數(shù)據(jù)結(jié)構(gòu)、C語言等等.這樣由于對以上某些學(xué)科有些薄弱的學(xué)生，學(xué)起這門課就會有些吃力.例如，如果數(shù)學(xué)基礎(chǔ)不好，邏輯思維不清晰，學(xué)生往往對數(shù)學(xué)比較抽象的運用，如某些證明，就會感到難以理解.再比如，學(xué)生對數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)也不夠扎實，對遞歸技術(shù)、堆排序、搜索等技術(shù)掌握不夠牢靠，學(xué)習(xí)起來也不能順利，例如，留作業(yè)：寫出用遞歸技術(shù)實現(xiàn)兩個八項式相乘的過程，其實只是規(guī)模稍微大了一點、復(fù)雜度高了一點，就沒有一個能給出完全正確的答案.學(xué)生不知道遞歸到底是如何進(jìn)行的，只知道一層一層的調(diào)用，調(diào)用到最后一層，再一層層的返回，簡單的問題學(xué)生理解沒問題，但復(fù)雜了就不知道具體怎么執(zhí)行了，特別是每一層返回到哪里、繼續(xù)執(zhí)行哪里，就都不清楚了；也不知道堆是如何建立、如何排序的.這樣，他們怎么能對具體問題提出算法并對算法進(jìn)行很好的分析并設(shè)計呢？

1.2 學(xué)時少

安排32學(xué)時，16次課，在去掉教師節(jié)、中秋節(jié)、十一放假與運動會，作為教師除了講些基本的理論知識內(nèi)容外，就無法深入挖掘出學(xué)生的算法這方面的的天分與資質(zhì)，也無法激發(fā)學(xué)生的熱情而使之投入到算法的研究中去.因為，學(xué)生的時間也很緊，要修學(xué)分，要修專業(yè)課，要面對英語過級考試，要參加各種活動，要找實習(xí)工作準(zhǔn)備畢業(yè).所以，對于算法這門范圍廣、內(nèi)容豐富學(xué)的學(xué)科，32學(xué)時顯得很不夠用.

1.3 缺少實踐

這門課程沒有安排上機(jī)學(xué)時，學(xué)生不能將學(xué)到的東西在機(jī)器上運行驗證，以加深對某些具體算法的理解與分析，因而也難以提出新的見解與方法，更不能設(shè)計出具有突破性的優(yōu)秀算法.當(dāng)然，這需要良好的環(huán)境，需要有資金的投入.

2 特色教學(xué)

發(fā)現(xiàn)了上述所存在的問題以后，開始研究實際教學(xué)，不斷尋找解決問題的方法.下面給出自己的實際操作過程中運用的方法與策略.

2.1 明確學(xué)習(xí)算法意義

首先要關(guān)心這一學(xué)科的發(fā)展，大量收集有關(guān)資料，使學(xué)生明白學(xué)習(xí)算法意義重大.在算法的發(fā)展史上，關(guān)于平面圖判斷問題曾經(jīng)困擾人們很長時間.雖然這個問題在教學(xué)上早在1930年就由波蘭數(shù)學(xué)家Kuratowshi解決，但是，實現(xiàn)起來確實很難.對于有100個頂點的圖，用普通的算法，計算機(jī)需要1萬億步才能確定其是否為平面圖.因此，尋找高效的平面圖測試算法成為擺在當(dāng)時計算機(jī)科學(xué)家面前的一大難題.正因為解決此難題才使John和Robert獲得了1986年的圖靈獎，他們創(chuàng)造了“深度優(yōu)先搜索算法”（depth–first search algorithm）.利用這種算法對圖進(jìn)行搜索時，節(jié)點擴(kuò)展的次序是向某一個分支縱深推進(jìn)，到底后再回溯，這樣就能保證所有的邊在搜索過程中都經(jīng)歷過一次，并且只經(jīng)過一次，從而大大提高了效率.新算法的運行時間是線性的，大小翻一倍，求解問題所需的時間也只翻一倍.相比之下，若用Kuratowshi判斷的老算法，那么當(dāng)圖的大小翻一倍時，所需時間要增加60倍以上.利用他們創(chuàng)造的新算法，Robert用Algolw為一個包含900個節(jié)點和2694條邊的圖編制一個測試其平面性的程序，程序只有500行，在IBM360/67上運行，只用了12秒就得到了結(jié)果.John和Robert把他們的研究成果寫成論文在《Journal of the ACM》上發(fā)表，引起學(xué)術(shù)界很大的轟動.而他們創(chuàng)造的深度優(yōu)先算法則被推廣到信息檢索、國際象棋比賽程序、專家系統(tǒng)中的沖突消解策略等許多方面.不久，他們又提出了一種新的數(shù)據(jù)結(jié)構(gòu)叫“雙堆棧疊”（pile of twin stacks），這種新的數(shù)據(jù)結(jié)構(gòu)被深度優(yōu)先搜索算法的優(yōu)點更加發(fā)揚光大.Robert的一個學(xué)生用這種新的數(shù)據(jù)結(jié)構(gòu)和算法編寫了一個Algolw程序，只有250行，在IBM 370/168上測試有8000個節(jié)點的圖的平面性只用了8秒鐘.

2.2 激發(fā)學(xué)生興趣

引入game-to-teach理念，提出游戲教學(xué)方法，即針對教學(xué)內(nèi)容知識點設(shè)計游戲.例如，在我在最后引導(dǎo)學(xué)生了解前沿技術(shù)平行算法的時候，為了更好地講解為什么需要算法并行化的過程中，設(shè)計一家五口三代人夜晚提燈來到獨木橋前過河回家的游戲.游戲描述：一天夜晚，毛毛一家人提著一盞油燈，來到河岸邊.河面上有一個到達(dá)對岸的獨木橋，只能支撐兩個人提燈過河.之后，還要有人把燈送回來，使得其他人可以提燈照明繼續(xù)過河.每個人過河速度不同，毛毛、爸爸、媽媽、爺爺奶奶過河的速度分別是1秒、3秒、6秒、8秒、12秒.每次過河的兩個人速度以最慢的計，燈的油可以燃燒30秒.怎么安排過河，才能在有限的時間30秒內(nèi)使全家安全通過呢？如果超時，燈熄滅了，沒了燈光，看不見，在橋上的人則掉到河中，就會過河失敗.給同學(xué)思考過河方法5分鐘，其間我在黑板上畫出游戲場景，沒有任何思考地按順序安排過河，先是毛毛提燈和爸爸過河，毛毛送燈回來；毛毛提燈和媽媽過河，毛毛送燈回來；毛毛提燈和爺爺過河，毛毛送燈回來；毛毛提燈和奶奶過河，時間到，毛毛和奶奶都掉河里啦，過河失??！然后問大家：為什么沒成功？學(xué)生回答：沒有合理搭配的不同速度的人過河.怎么搭配？馬上有同學(xué)站起來說：第一步：選擇1秒鐘過橋的人與3秒鐘過橋的人同時過橋，這樣就能夠?qū)?秒鐘過橋的人給并掉，時間只用了3秒鐘；第二步：讓3秒鐘過橋的人回去，用時3秒.選擇8秒鐘過橋的人與12秒鐘過橋的人同時過橋，這樣就能夠?qū)?秒鐘過橋的人給并掉，時間只用了12秒鐘；第三步：讓1秒鐘過橋的人回去，用時1秒.選擇1秒鐘過橋的人與6秒鐘過橋的人同時過橋，這樣就能夠?qū)?秒鐘過橋的人給并掉，時間只用了6秒鐘；第四步：讓1秒鐘過橋的人回去，用時1秒.選擇3秒鐘過橋的人與1秒鐘過橋的人同時過橋，這樣就能夠?qū)?秒鐘過橋的人給并掉，時間只用了3秒鐘.總共用時29秒，過河才成功！游戲短小精悍，過程生動有趣.最后，我用多媒體總結(jié)：成功的關(guān)鍵是使用并行化設(shè)計技術(shù)！算法的并行化是非常必要的，是真正提高速度的根本，是我們非常需要的！經(jīng)過這樣實際演練學(xué)習(xí)，學(xué)生的興趣極高，同時，對并行性的理解再深刻不過，達(dá)到了教與學(xué)的最佳境界.

2.3 提高學(xué)生主觀能動性

不管教的有多好，關(guān)鍵還在于學(xué)生主動學(xué)習(xí).所以，讓學(xué)生知道當(dāng)前還有很多重大問題有待解決這很重要.在講到希爾排序所存在的問題時，結(jié)合算法目前存在的問題進(jìn)行全面分析：一是有些問題跟本就沒有算法；二是有算法但欠缺完善的分析，希爾問題就屬于這種情況；三是有些問題尚有算法但已過時滿足不了要求是針對內(nèi)存小而借助外設(shè)來實現(xiàn)的算法，已不適合現(xiàn)在內(nèi)存大外設(shè)更大的實際情況.所以，結(jié)論是需要大量的優(yōu)秀算法.那么這些任務(wù)有誰來完成呢？當(dāng)然是現(xiàn)在學(xué)習(xí)的學(xué)生，是正在學(xué)習(xí)算法又了解算法非常需要他們的學(xué)生.特別是，我國在這方面的發(fā)展還不夠，更需要他們不斷地努力以便能在這個領(lǐng)域中做出更大的貢獻(xiàn).通過這些工作，讓學(xué)生了解到這一學(xué)科的重要性，激發(fā)他們的興趣，是他們意識到自身的責(zé)任重大，促使學(xué)生能在主觀上下決心學(xué)好這門課，進(jìn)而才能更好地發(fā)展這一學(xué)科.

2.4 實例法

在講到貪心法的作業(yè)調(diào)度[5-7]的時候，講了作業(yè)的順序選擇法和最大期限選擇法兩種.當(dāng)時，覺得前一種很簡單就直接講了選擇思想及其實現(xiàn)算法，而后一種覺得有些難就多加了例子，結(jié)果學(xué)生非常明白后者反倒覺得前者很難.從中看出，空講理論實效并不大，結(jié)合實例具體化更容易接受.從那以后，就多準(zhǔn)備例題，效果很好.而且，把這些積累下來，還有每次上課的材料，就形成了自己的講義教案與習(xí)題集.這對以后講這門課，做多媒體課件，都方便多了；對學(xué)生，有習(xí)題集做輔導(dǎo)材料，學(xué)起來更輕松、學(xué)的效果也更好.

2.5 分組大作業(yè)

在講完每一章之后，給同學(xué)們布置作業(yè)，希望他們做作業(yè)的同時能看看書，起到復(fù)習(xí)鞏固強(qiáng)化教學(xué)效果的作用，而且要求同學(xué)們做作業(yè)的時候要相互研究交流，拓展思路，提高效率.根據(jù)作業(yè)量的不同將同學(xué)分成不同的組，多時分十幾個組，每組十多個同學(xué)做同樣的作業(yè)；少時則分幾個組每組幾十個同學(xué)做同樣的作業(yè).通常每組留1～2道題，實際上每個同學(xué)也就做一道，簡單時就做兩道.但當(dāng)任務(wù)特別重時，因為要將布置的作業(yè)先形成答案，然后在輸入計算機(jī)，運行驗證，再形成文檔，這樣才能將收上來的作業(yè)進(jìn)行仔細(xì)的評改，再發(fā)下去.而上的是大課，四個班大約一百二十人左右.所以，工作量很大.但我覺得值，雖然我很辛苦，因為在考試驗收時學(xué)生通過率明顯提高.

3 結(jié)束語

以上，就是我通過對算法領(lǐng)域的研究與對《算法設(shè)計與分析》這門課程的實際教學(xué)而得到的體會與經(jīng)驗.當(dāng)然，由于我教學(xué)時間還不夠長，還有很多工作沒有做，我會繼續(xù)努力去完成的.我也相信，通過自己的不懈努力，我和學(xué)生會有更大收獲與成果的.

〔1〕田翠華.算法設(shè)計與分析[M].北京:冶金工業(yè)出版社，2007.

〔2〕王曉東.算法設(shè)計與分析[M].北京:清華大學(xué)出版社，2011.

〔3〕朱慧爽.關(guān)聯(lián)規(guī)則挖掘算法初探[J].科技信息(科學(xué)教研),2008(13).

〔4〕袁萬蓮,鄭誠,翟明清.一種改進(jìn)的 Apriori算法[J].計算機(jī)技術(shù)與發(fā)展，2008(05).

〔5〕陳慧南.算法設(shè)計與分析:C++語言描述[M].北京:電子工業(yè)出版社，2006.

〔6〕古德里奇,塔瑪西亞.算法設(shè)計與分析[M].北京:人民郵電出版社，2006.

〔7〕沙特M.H.Alsuwaiyel.算法設(shè)計技巧與分析[M].電子工業(yè)出版社，2003.

TP301.6

A

1673-260X（2012）08-0044-02

廈門理工學(xué)院科學(xué)技術(shù)研究項目(No:YKJ11012R);廈門理工學(xué)院科學(xué)技術(shù)研究項目(No:YKT10037R);廈門理工學(xué)院學(xué)院創(chuàng)新創(chuàng)業(yè)教育改革與建設(shè)項目(JGCX201117);國家自然科學(xué)基金項目（61103246）