《算法設計與分析》的理論研究與教學實踐

田翠華,王偉杰,許衛平

（1.廈門理工學院 計算機科學與技術系，福建 廈門 361024；2.沈陽工業大學 軟件學院，遼寧 沈陽 110023）

《算法設計與分析》的理論研究與教學實踐

田翠華1,2,王偉杰1,許衛平1

（1.廈門理工學院 計算機科學與技術系，福建 廈門 361024；2.沈陽工業大學 軟件學院，遼寧 沈陽 110023）

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

算法；游戲教學；特色教學

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

1 理論研究與教學實踐

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

1.1 相關知識多

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

1.2 學時少

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

1.3 缺少實踐

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

2 特色教學

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

2.1 明確學習算法意義

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

2.2 激發學生興趣

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

2.3 提高學生主觀能動性

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

2.4 實例法

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

2.5 分組大作業

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

3 結束語

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

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

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

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

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

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

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

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

TP301.6

A

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

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