算法設計與分析課程實驗教學改革的研究

[摘要]算法設計與分析是計算機本科專業的一門選修課，可對該課程的實驗教學內容、實驗教學方法、實驗教學手段和考核方法等四方面進行改革。

[關鍵詞]算法設計

實驗教學 教學方法教學改革

[文獻編碼]doi:10.3969/j.issn.0450-9889(C).2011.08.039

算法設計與分析課程既是計算機科學與技術本科專業的專業課，又是其他專業如信息管理、應用與計算數學的專業課，其前導課程主要有“程序設計”、“數據結構”等。該課程的實踐性強，各種經典算法思想如分治法、動態規劃法、回溯法等都是從一系列經典問題的解決方案中提煉出來的，算法思想晦澀難懂，實際運用較難。教學發現，多數本科生對該課程只注重理論學習，忽視實際運用，死記硬背算法思想，沒有將算法思想靈活運用于解決實際問題，導致實驗課無事可做或有事做不了，實驗課難上。這就要求教師思考如何根據學生情況設計實驗教學的內容、方法和手段，徹底改變實驗僅是簡單驗證算法思想的現狀，使實驗課成為充分理解和運用算法思想的主陣地。

一、優化實驗教學內容

計算機科學與技術本科專業的算法設計與分析課主要目的是講授應用軟件開發中的典型非數值計算問題的解法，重點講授各種算法的基本思想、設計方法與技巧，同時通過典型案例的設計與時空復雜度分析，建立計算機與應用問題之間的橋梁，要求學生在設計具體算法時能夠對其進行時空復雜度分析，并使所設計的算法時空復雜性最優，從而有能力編寫出高效程序、開發出優秀軟件。通過該課程的學習，學生應該掌握遞歸與分治、動態規劃、貪心算法、回溯法、分支限界法和概率等經典算法的設計和分析技巧，并能靈活地用于解決具體實際問題。為了配合理論教學，實驗內容選取應注重以下問題：

首先，根據學生情況選擇合適的內容。由于本課程的實踐性較強，實驗課尤為重要；設計實驗課內容成為本課程教學的重中之重，實驗課內容不僅要體現理論課的算法設計思想，還要有利于鍛煉學生的思維方法、提高不同層次學生的學習興趣、形成良好的思維習慣。經驗表明，實驗內容選取那些與生活、學習、工作、娛樂密切相關且通俗易懂的典型事例效果較佳。此外，實驗內容的選取應體現循序漸進、由簡到繁、由淺入深的思想，實驗指導書中的每次實驗應提供難易程度有一定梯度的多個實驗題供學生選擇，使不同層次學生都能找到適合自己解決的問題，這樣每個參加實驗的學生都有收益。比如遞歸與分治實驗選擇眾數問題、集合劃分問題，動態規劃算法的實驗選擇游艇租用問題、最小費用購物問題等，這些問題學生比較感興趣，易于理解和實現。

其次，適當拓寬知識面。算法的應用領域很廣，我們在實驗教學中應該適當介紹一些計算機其他領域的算法及其應用實例，如并行算法、路由選擇算法、優化算法，等等。由于時間關系，只作基本思想的粗略介紹，采用淺顯易懂的應用實例演示的方法進行介紹，目的是讓學生了解各個領域都有其獨特的算法，拓寬他們的專業知識面，讓學生體會算法的重要性，從而激發學習動力。

最后，融入研究新內容，提出新問題。為了激發學生的學習興趣，應密切關注計算機算法的業內發展動向，充分利用互聯網信息資源，跟蹤算法的最新發展動態，將新算法、新問題融入實驗教學之中。研究新動向融入實驗教學，使學生體會到所學的算法進行一定的改進便可有效地解決實際工作中遇到的新問題，這樣學生感到學有所用，達到增強學習興趣、培養創新能力的目的。這也是如何在有限的實驗時間內使學生真正掌握算法思想，進行本課程教改的關鍵所在。比如0-1背包問題，在理論講授時用圖解、遞推等多種方式，讓學生由淺入深逐漸理解動態規劃算法原理；在實驗課上，我們可以適當引入粒子群算法解決此問題，這樣以動態規劃算法基本設計方法為重點，穿插新的優化算法，在規定的課時內，既完成了教學任務，又提高了教學效果。

二、改進實驗教學方法

實驗教學方法主要采用“計算機+大屏幕”的授課模式。采用可動態演示算法的多媒體課件，在大屏幕上展示抽象算法的執行過程，從而大大增強實驗課堂的教師引導作用，有助于加速認識的升華以及相關技術的理解和靈活運用。

(一)采用啟發式教學

根據啟發式教學的基本思想，在試驗教學中通過理論課堂上講解的算法典型應用與實驗問題進行對比，尋找它們與算法基本思想相關的共同點，將算法具體應用過程中出現新問題的解決過程和方法展現出來，讓學生思考、模擬和研究，變機械模擬式實驗教學為主動探索創新式教學。對一組相關的算法，分析各自的優缺點，啟發學生大膽探索新的設計思路，從而激發學生的創造性，達到培養創新能力和提高教學效果的目的。為此，要求學生實驗前盡量吃透算法的基本思想、充分理解典型問題的實現技巧，同時要求教師多了解算法的最新應用，在如何引導學生分析解決實際問題方面多下工夫。比如，游艇租用問題，通過比較分析引導學生如何根據動態規劃算法設計要求，結合矩陣連乘問題最優表達式的推倒過程定義其最優表達式。此外，在講課方式上，注重探索啟發技巧，啟發并引導學生積極探索，給學生營造一個創新的發散思維氛圍。

(二)注重理論聯系實際

算法設計與分析本身比較枯燥，計算機科學與技術專業本科生畢業后多數從事生產實踐，所以更應注重實際應用，教學內容與實際應用的密切聯系，能使學生學習興趣倍增。算法思想的具體應用是實驗教學的重點及難點，實驗前，重點講授算法思想的實際應用技巧及其關鍵所在，由簡單有趣的典型應用過渡到復雜難懂的個性化問題解決，使學生循序漸進地接受算法的基本思想和應用技巧。為了讓學生對算法有較完整的認識，引導學生思考對于同一問題選擇不同算法，其結果是否一樣。如會場安排問題，用貪心算法和動態規劃求解時結果會有差異，貪心算法簡單，可用于處理最優化問題，但貪心算法解決問題時優化測度要根據具體問題進行選取，具體實現方式依賴于問題本身，而且貪心算法不一定得到全局最優解。這種教學方式不再是紙上談兵，而與實際密切相聯，讓學生帶著新鮮感去實驗，不僅提高了實驗興趣，更重要的是培養了發現問題、分析問題及解決問題的能力。

(三)強化互動教學

針對理論課教學中的疑問，在實驗教學中不僅應鼓勵學生相互討論，更應鼓勵師生之間開展辯論，鼓勵學生大膽提出自己的想法。所選實驗內容應有代表性、典型性，應有討論引申的余地。討論某一問題時，引導和鼓勵學生大膽提出新問題、新思想，從而使學生在討論和解決問題的過程中能夠培養和鍛煉獨立思考能力。以漢諾塔問題為例，首先講清N=3時的三種解法，鼓勵學生提出新的解法，根據時間復雜度選取最佳解法，這一步是問題的關鍵，由此引導學生思考當N=4，N=5，……時怎么辦?問題解決之后再引申出雙色漢諾塔問題。這樣的共同商討不僅能能培養學生獨立和善于思考的能力，而且起到教學相長的效果。

(四)強調因材施教

實驗內容的選取應有一定的循序漸進，由簡到繁、由淺入深，初學時或程度較差的學生選取簡單且易于模仿的問題。簡單問題解決后鼓勵和引導學生沖擊復雜問題。比如動態規劃算法，可先選擇相對簡單的游艇租用問題，然后可選擇m處理機問題等。這樣通過對不同層次的學生提出不同難度級別的問題，配合不同級別的提示來調動所有學生的積極性。

三、改革實驗教學手段

充分利用現代化教學手段是實驗教學改革的發展趨勢。實驗前抽出一定的時間剖析實驗內容的難點和要點，把抽象難懂的關鍵點和編程技巧直觀形象地展現出來，提高實驗效果。為此引入多媒體教學手段，將實驗涉及的算法設計步驟或設計技巧以直觀和形象的方式展示給學生，便于學生理解和模擬。例如，利用概率算法求解集合相等問題時，利用多媒體課件讓學生清楚地了解概率算法求解集合相等的過程及結果，有利于學生模擬解決實驗中的概率算法問題。這樣實驗課堂就輕松活躍了，實驗效果會大大增加。

此外，開設算法設計與分析課程網站。網站在不同時間提供配套的理論課和實驗課多媒體課件，實驗內容的參考答案、學生提交作業及其他相關課程資源，提供師生交流平臺，方便學生疑難問題的解答。同時，網站還經常更新一些生活和工作中遇到的真實問題，鼓勵學生踴躍參與更新。對那些提出有一定價值的問題及其解決方案的學生給予適當獎勵，這樣可以真正做到寓教于樂。同時網站不僅方便實驗室內沒有按時完成任務的同學利用課余時間完成實驗，而且方便其他專業的學生參與實驗，方便學生自學與復習。采取這種教學手段是改革傳統教學手段的重要舉措之一。

四、改革實驗考核方法

對這門課的考核方式進行改革，將傳統、單一的閉卷考核方式，改為平時課堂學習占10％、實驗完成情況占30％，最后的大作業占50％、網絡互動占10％的綜合考核辦法；最后的大作業主要以算法設計為主，教師提供多個設計題目供學生選擇，學生也可以相互出題，但不能與實驗題重復或過于簡單。逐漸加大對算法設計和程序開發能力的考核力度，激發學生自主學習、自主訓練的興趣和熱情，避免產生“高分低能”現象。

通過幾年的實踐，我們進行了實驗教學的內容選取、組織形式、教學方法、教學手段、教學評價與考核等多個環節的改革，大大提高了該課程的實驗效果，有力地配合了該課程的理論教學，取得了較好的實驗教學效果。

(責編 黎原)