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

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

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

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

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

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

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

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

一、教學內容的選擇

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

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

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

二、教學方法的改革

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

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

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

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

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

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

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

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

3．從學會到會學

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

三、教學手段的改革

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

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

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

2．網(wǎng)絡教學方式的運用

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

四、考核方式的改革

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

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

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

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

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

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

G642

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