算法設(shè)計與分析課程教學(xué)改革探索

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

算法設(shè)計與分析課程教學(xué)改革探索

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

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

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

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

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

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

一、教學(xué)內(nèi)容的選擇

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

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

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

二、教學(xué)方法的改革

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

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

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

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

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

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

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

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

3．從學(xué)會到會學(xué)

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

三、教學(xué)手段的改革

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

1．多媒體教學(xué)和板書相結(jié)合

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

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

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

四、考核方式的改革

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

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

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

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

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

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

G642

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