算法設計與分析課程教學改革探索

□南京理工大學 孫廷凱 於東軍余立功 劉傳才 金忠

算法設計與分析課程教學改革探索

□南京理工大學 孫廷凱 於東軍余立功 劉傳才 金忠

本文從算法設計與分析的課程特點出發，結合課程教學組的教學實踐經驗，在教學內容、教學方法、教學手段和考核方法等幾方面進行了探討，總結了幾點教學改革經驗。教學實踐表明，這些教學經驗在教學中收到了良好效果。

算法設計策略；問題分析；多方位考核

算法設計與分析課程（下文簡稱“算法課程”）是計算機專業的一門重要的專業基礎課，基于現代計算機技術的算法研究從其萌芽階段到成為一門獨立的學科分支，是和計算機科學及其軟硬件技術的發展緊密相關、互相促進的。著名的超級計算機“深藍”擊敗國際象棋世界冠軍卡斯帕羅夫就是一個家喻戶曉的例子。學習算法課程，有助于學生日后在實際生產或科研工作中，面對復雜的應用問題時，能夠根據問題本身的性質，利用已學習的算法設計技巧，編寫出優質高效的程序來解決實際問題，或者針對已有的算法，分析其時間和空間復雜度，進行適當的算法優化，從而對問題的解決帶來質的提升。

隨著信息技術的發展，算法課程日益成為計算機科學技術中處于核心地位的一門專業基礎課，同時，也是電子信息等其他理工科專業學生必需掌握的。許多高校的計算機相關專業都將算法從數據結構中獨立出來，將其列為必修課，并給予越來越多的重視。

算法課程是我校的軟件工程專業、計算機科學與技術專業的主干課程之一。一方面，它與數據結構、程序設計等課程，構成了這兩個本科專業學生課程體系的重要組成部分，并在教學過程中，逐漸建立了一支算法課程教學團隊。另一方面，國內高校盛行的大學生數學建模大賽和著名國際賽事ACM競賽的蓬勃開展，也對本課程的建設起到了積極的推動作用[1]。然而，在實際操作中，學生們普遍反映本課程學習吃力。究其原因主要是：首先，它需要學生具有扎實的先修課程基礎；其次，它也不像很多其它課程那樣大部分依靠記憶，而是更多地依靠理解，并且要求能夠靈活應用；第三，教學內容繁多、涉及面廣，但課時有限；第四，傳統的課程教學內容過多側重于理論，忽視應用案例和實踐教學，難以跟上當今科技發展步伐。因此，如何上好算法課程，給本課程的教學團隊帶來了挑戰和考驗。在教學實踐中，我們努力嘗試了一些教學改革舉措，得到了一些成功的經驗。本文擬從教學內容、教學方法、教學手段、考核方式等幾方面分別進行探討。

一、教學內容的選擇

建立科學合理的教學內容體系，對于豐富充實教學內容、提高教學效果起著不容置疑的重要作用。一方面，算法設計與分析所涉及的內容非常廣泛，與先修課程離散數學、數據結構的某些經典內容有交叉（如圖的最短路徑算法、排序算法）而又各有側重，選擇恰當的內容有助于算法課程在整個專業課程體系中的準確定位[2]，加上有針對性的講解，可以讓學生既學習到算法設計的思想和分析方法，又不至于讓學生覺得“已經學過，沒意思”。而教學的困難則在于：先修課程的某些經典內容恰恰是闡述某類算法設計思想的最佳案例，因此常常有學生發問：算法與數據結構兩門課程是什么關系？我們認為：二者本身密不可分，在數據結構課程里，重點是靜態的數據結構定義，輔助以動態的有關算法使之“活”起來；而在算法課程里，算法設計思想是核心，而數據結構成為算法的基石。在教學實踐中，我們也身體力行了這一點，努力讓學生對經典內容不但知其然，更知其所以然，從算法設計思想的角度，使學生將經典內容理解得更加深刻。另一方面，算法設計與分析本身是一門年輕的學科，正在不斷地發展之中，教學內容需要與時俱進，不斷注入新鮮血液和活力，讓學生在學習知識的時候，思想深處受到鼓舞，進而激發他們進一步探索學習的愿望。

算法課程通常應包括如下幾個方面[3]：一是算法的基本概念、算法的數學基礎和復雜度分析方法；二是迄今人們所設計和歸納的幾大類經典算法策略，包括分治策略、動態規劃策略、貪心策略、圖搜索算法、回溯策略、分支限界策略等；三是可計算性理論和問題復雜性方面的研究，如計算模型、NP完全問題等；四是近年來發展起來的隨機算法、近似算法、智能優化算法（如啟發式搜索、遺傳算法、人工免疫算法等）等最新研究進展。其中，前三個方面是重點內容，第四方面可做有選擇、有重點的講解。

目前，國內外關于算法設計與分析的教材很多，但水平不一。國內教材內容選題較為陳舊，分別定位于不同層次本科院校和不同專業，而采用合適的國外教材是快速改革優化教學內容的合理途徑之一。國外教材內容大多從ABC起步，內容浩繁（如T.Cormen的《算法導論》，潘金貴等譯），但并不適合用做教材。結合我校實際情況，我們選擇了M.Alsuwaiyel所著《算法設計技巧與分析》（吳偉昶等譯）為基礎（其特點是內容豐富、難度適中、加強數學基礎、用偽代碼描述算法思想），T.Cormen的《算法導論》（其特點是許多經典算法和重要知識點獨立成章，講解細致）為主要參考，以王曉東編著《計算機算法設計與分析》（其特點是應用案例豐富、C語言直接描述便于實現）、呂國英的《算法設計與分析》（其特點是由淺入深、同類算法策略中有更細微的區別策略）為參考的教學內容選擇方案，輔之以教師所關注的最新科研進展成果。上述方案較好地兼顧了經典內容的知識性、理論方面的嚴謹性、應用案例的趣味性、“時尚元素”的現代性等因素。

二、教學方法的改革

從算法設計本身而言，其目的是實際問題求解，而實現過程是：根據問題本身固有的性質，選擇合適的算法設計策略，通過一系列算法過程，使問題得到解決。不難看出，分析問題性質是基礎，求解過程是關鍵，也是算法最注重的，而算法策略是某一類算法過程的思想總結。俗話說，條條大路通羅馬。同一個問題也應有多種求解策略，而其時間和空間復雜度各有千秋。在教學實踐中，我們始終從這一原則出發，不是急于灌輸給學生一套算法過程，而是從分析問題性質入手，通過不同的求解過程，實現算法設計、分析、優化的統一。

1.從樸素思想到止于至善

算法思想是前人智慧的總結，簡單灌輸給學生固然快捷，然而，授人以魚，不如授人以漁，簡單灌輸會讓學生失去探索的樂趣，失去思維能力提升的寶貴機會，這樣做的后果是學生面對新問題時，依然不知道從何下手。因此，面對一個待求解的問題，我們首先讓學生利用自己腦海中固有的樸素思想給出求解思路，再分析其利弊（主要是時間和空間復雜度，以及是否利用了充分問題的性質特點），然后，啟發學生分析問題本身的性質，利用已有的數據結構知識，勾畫出更為高效的算法的“梗概草圖”，最后，加以細化，設計出具體算法過程，這樣，算法復雜度分析也會迎刃而解。茲舉兩例說明之。

介紹算法概念時，以二分查找為例，啟發學生“基于樸素思想的順序查找沒有充分利用數據有序的固有特點”，而利用中間元素（由于數據有序，剛好居于中值附近）做閾值，不斷拋棄大約一半元素，不斷縮小問題規模，可迅速定位找到該元素，加以細化，不難寫出具體算法。由于該算法利用了數據本身的有序性，求解隱含利用了樹結構，不難得到其復雜度為O（logn），比順序查找的復雜度O（n）低。通過這個簡單而又熟悉的例子引起學生的興趣。而再次啟發學生“是否還有別的方法拋棄元素，減小復雜度？”從而為本課程的隨機化方法埋下伏筆，這無形中提高了學生帶著問題學習的求知欲。

介紹基本數據結構“堆”（在數據結構課中未重點講解）時，關于堆的建立過程，學生會提出一種樸素的思想，即從空樹開始，逐個插入每個結點，調整建堆。我們提醒學生這種方法雖然可行，優點是簡單、直觀，但實例板書演示發現，每次插入新結點，可能導致徹底打破原堆的結構，結點交換次數過多，造成時間浪費。于是啟發學生：如何盡量減少結點交換次數？而啟發討論的結果使算法過程逐漸明晰，得到一種“先建立樹，再逐個調整子樹成堆”的方法。思想明晰之后，再運用數學知識分析后不難知道，后一種方法更為高效。在這個過程中，學生們真切地在腦海中感受到了“從樸素思想入手——分析問題性質——提出新的求解思路”的一個思維自我提升的過程。使算法設計——分析——優化的過程再次完美統一，此間，教師可不失時機地教育學生“大學之道……在親民，在止于至善”的理念，讓學生在學習知識的同時受到教育思想的熏陶。

在各種算法設計策略的教學中，我們基本都采用了這種教學方法。從中可以看出，這種循序漸進的啟發引導式方法，可以幫助學生從分析問題本身性質入手，從基于樸素思想的算法中尋找算法提升的空間，啟發學生運用已有的數據結構知識設計出高效的算法，可一攬子實現“算法設計—算法分析—算法優化”的過程，有助于學生解決問題能力的自我提升。

2.從舉一反三到觸類旁通

面對具體應用問題，既可以根據問題的性質特點采用不同的算法設計策略，在同一種算法策略內部，不同的問題求解方法之間也有具體而微小的差別，這一切都依賴于對問題性質的分析認識程度有多深。在教學中，我們根據這個特點，也采取了有針對性的教學方法。舉例來說，利用分治策略求解問題時，需要將規模為n的原問題分解為若干個規模較小的子問題，但如何分割是值得深入思考的。既可以是2個大小相等的子問題（如歸并排序），也可以是2個大小不等的子問題（如快速排序），或者是若干個大小不等的子問題（如求數組的最大最小元素），或者是不斷拋棄部分元素減小問題規模（如線性選擇第k小元素，類似于二分查找），或者是將原問題通過某種變換分解得到若干個子問題（如棋盤覆蓋問題）。這樣，學生學習之后，會覺得策略不是死的，而是可以具體情況具體分析、可以靈活運用的。此外，為了讓學生較好地掌握各種方法之間的聯系，我們選用同一個例子而采用多種方法來解決。如在講解貪心法、動態規劃法、回溯法和分枝限界法時，都采用了0/1背包問題，這樣，可以引導學生掌握課程內容的內在關聯性[4]，幫助他們站在更高的起點和視角審視學過的知識，避免只見樹木不見森林。

3．從學會到會學

有的算法策略實現過程的相似性較高，不同的算法策略之間也有內在的聯系。我們在有些章節中（如回溯策略），教師精講一種算法之后，對于其他算法過程，選擇一二先讓學生自學，然后鼓勵學生上臺試講。我們認為，從被動聽課到聽懂，再到給別人講明白，實際上是對算法的理解逐漸深刻的過程，同時也是對學生口頭表達能力的一種鍛煉。在結束幾章的授課之后，讓學生思考這些章節的算法策略之間的內在聯系（如分治策略、動態規劃策略、貪心策略之間的對比和聯系）并走上講臺與大家交流，對于能夠積極主動思考的學生而言，無疑是一種鍛煉和嘗試，而對于一般學生也是一種激勵和促進，這種方式本身也有利于督促學生回顧整理并深入思考已學過的知識，讓他們在“埋頭拉車”的時候，不要忘記“抬頭看路”，進而實現從“學會到會學”的飛躍。

三、教學手段的改革

將傳統教學手段與現代技術相結合，是本課程的主要特點之一。我們在教學過程中，將多媒體教學課件、板書和網絡教學方式相結合，充分利用多媒體課件多樣化的表現形式，利用豐富的網絡教學資源，構筑算法課程的現代教學模式。采用的教學手段包括以下幾種。

1．多媒體教學和板書相結合

緊扣教學大綱，以教科書和教參為主要依據，精心選擇內容制作多媒體課件，課件每個學期都有更新，加入最新內容或對舊內容的新理解。其優點是課程容量大，動態直觀，節約了板書的時間。對于一些概念性強、演示性強的章節（如回溯策略、分支限界策略），宜多采取多媒體教學方式，其間輔以研究背景和名人小傳軼聞，以增強課堂的趣味性。對于一些算法，可利用電腦軟件計算平臺現場演示其效果。對于算法復雜性分析和算法解決問題的推導過程，我們仍采用傳統的黑板板書教學方式。由此，學生經歷了板書從無到有，思路從疑惑到逐漸清晰的過程，而教師的板書和講解過程，就是一個展示思維與學生交流和溝通的過程。

2．網絡教學方式的運用

網絡教學在時間和空間上將傳統教學進行了全方位的延伸，填補了過去傳統教學許多力不能及的地方。一方面，教師可以從網絡上獲知最新的研究成果(如NP理論、旅行商問題、蟻群算法的最新進展)、一些“高而可攀”的教學研究成果（如遞歸算法的非遞歸實現、最短路徑算法的最新研究成果）、在線算法論壇資源并將其推薦給學生。另一方面，利用網絡實現了師生信息交互，主要方式包括建立課程QQ討論群，建立課程網站將課件代碼上網，在線問答，建立在線作業代碼提交和批改系統等，將師生交流從課堂上拓展到隨時隨地的網絡溝通。

四、考核方式的改革

在傳統的考核方式下，期末閉卷考試成績占大部分，平時成績占小部分，這在一定程度上制約著教學效果，導致一些學生考前突擊復習，僅僅靠記憶獲取高分，這也會導致考核成績的不公平。我們嘗試改變這種現狀，加大了平時成績的權重，將平時成績從考勤、作業兩方面拓展為包括課程設計、在線作業、研究小論文、課堂表現等都納入到考核體系中。學生的代碼原創性、研究選題新穎性、課堂參與的積極性都是考量指標，通過這種方式，將積極愛好思考的優秀學生與其他學生區別開來，從多方位考核學生的表現。實踐表明，這樣做更能準確地反映學生平時的學習程度。另一方面，我們將考核與教改有機結合，在期末考試時增加一道主觀題，選題范圍可以是論述本課程的內容體系結構，或者是對某些算法策略之間內在關系的深層思考，或者是對本課程的教學提出寶貴意見或建議，這些題目均無固定答案，學生可見仁見智自由發揮，從而促使他們思考學習的內容，思考教學過程與學習過程本身存在的有待改進之處。實踐表明，這種為學生著想，以學生為中心的做法受到普遍歡迎，學生對我們的教學改革實踐也表現出普遍認可，同時還提出了很多合理化建議。

針對算法課程特點和我校的實際情況，為了提高學生的學習積極性，增強教學效果，我們在教學內容、教學方法、教學手段與考核方法等幾方面積極開展了教學改革研究和實踐，根據課程特點倡導并實踐了新的教學方法，通過利用豐富的網絡教學資源，將傳統的課堂講授模式和考核方式拓展為全方位的教學與考核模式。實踐結果表明，新的教學方法和教學實踐受到了學生的普遍認可，取得了令人滿意的效果。

[1]吳英杰，王一蕾，傅仰耿，等．依托程序設計競賽，推進“算法與數據結構”課程實踐教學改革[J]．計算機教育，2010（4）：53-55．

[2]於東軍,李勇智．算法設計與分析教學改革初探[J]．中國輕工教育，2005（3）：52-54．

[3]陳蕾，張怡婷，許建．基于創新能力培養的算法設計與分析課程教學改革[J]．計算機教育，2010（10）：27-29．

[4]李涵．“算法分析與設計”課程教學改革和實踐[J]．中國電力教育,2010（16）：74-75．

G642

項目名稱：南京理工大學高等教育教學改革研究重點課題（計算機專業基礎課程探究式教學的研究與實踐）項目號：2011-362-A5；項目名稱：南京理工大學高等教育教學改革研究課題（程序設計類課程體系與ICPC競賽教學模式研究）項目號：2011-362-B21；項目名稱：南京理工大學高等教育教學改革研究課題（本科生導師制教育管理模式創新研究）項目號：2011-362-C28。