基于完全案例覆蓋的專業碩士生算法教學方法

摘要：針對與計算機相關的專業碩士研究生算法理論基礎相對薄弱和授課學時數較少的狀況，在實踐基礎上，提出以大量案例多重覆蓋知識點的算法設計與分析課程教學方法，同時介紹相應的教學案例庫的構建和完善。

關鍵詞：專業碩士；算法設計；算法分析；案例覆蓋；案例庫

0、引言

作為我國人才發展規劃的重要組成部分和支撐手段，我國專業碩士學位正處于高速發展的機遇期。高校正在抓住機會，采取積極措施，大力促進碩士專業學位教育的全面發展。教育部在2010年要求進一步調整優化教育結構，積極穩妥地推動我國碩士研究生教育的戰略轉變，從以培養學術型人才為主，逐漸轉變為以培養應用型人才為主。這意味著擴大全日制專業碩士研究生的培養規模成為研究生培養的一個趨勢。

區別于側重理論和研究的科學碩士學位，專業碩士學位教育主要培養滿足特定職業需求和有特定職業背景的高級專門人才。專業學位教育具備專業性、綜合性和開放性三大特點。

算法設計與分析是專業碩士研究生課程，是多個專業和方向的必修課程，這些專業包括計算機科學與技術、計算機應用、計算機軟件與理論、軟件工程等。該課程同時還是一門與計算機有關的非計算機專業的專業課程，包括管理科學與工程、系統工程、應用數學與計算數學等專業。本課程的前驅課程包括離散數學、程序設計基礎、數據結構等，與計算方法和計算機圖形學等課程關系緊密，既具有鮮明的理論體系，也具有很強的實踐性。

專業碩士研究生的算法設計與分析課程的主要目標是通過講授不同類型算法的基本原理、解決方法、實現技術等，分析不同算法的時間復雜度和空間復雜度，使學生通過該課程的學習，能夠對系統軟件和應用軟件開發過程中的實際問題設計出高效、優化的算法，為開發出優秀的軟件奠定基礎。該課程涵蓋的主要內容有常用數學工具、窮舉法、貪心算法、分治法、減治法、動態規劃、并查集、回溯法、分支限界法、計算幾何、隨機算法、NP理論等12個方面。

但是，在教學實踐過程中，大部分的專業碩士研究生并不能很好地理解該課程的理論部分，對算法設計也只是機械地記憶法的步驟，而不能靈活地解決碰到的新問題。這些問題對教師提出了挑戰：如何根據學生的知識基礎，讓他們以樂意接受的方式，在有限的課堂時間內掌握算法設計方法，以應對今后工作實踐中無限變化的實際問題。

大量教學實踐證實：純粹的理論灌輸會使學生很快失去學習課程的興趣，不能堅持課堂學習，更沒有意愿在課后的練習和實踐環節投入時間和精力。

基于完全案例覆蓋的教學方法因此提出，也就是讓每個案例覆蓋多個知識點，每個知識點有多個案例與之對應；讓案例教學貫穿于理論講授、算法設計講授和編程技巧講授的整個過程。該教學法涉及案例選取、案例庫建設、案例授課技巧等內容，下面將分別闡述。

1、案例選取的原則

所謂的案例教學法，就是利用案例作為教學媒介和教學手段，以提高學生綜合能力為目標的教學方法。案例的選取至關重要，因為案例是案例教學的核心，直接影響著學生的興趣和對知識的接受程度，從而最終影響著案例教學法的實際效果。

根據所講授算法分析與設計課程的實際，案例的選取要遵循兩個原則：其一是多重覆蓋原則，其二是難易平衡原則。

1.1 多重覆蓋原則

科學碩士授課時間通常分為3個學期、一年半左右的時間，課時量充足，課程覆蓋知識點全面而細致，傳授知識的信息量更大。而專業碩士的課堂授課大多集中在前兩個學期，用一年時間完成，相對科學碩士，課時量相對不足。就算法設計與分析這門課而言，科學碩士的授課學時數為48，而專業碩士授課32學時。較少的課時量對案例的選取提出了嚴格的要求。一個案例并不能只為一個知識點設計，而必須為多個知識點設計。只有這樣，當所有的案例教學完成后，每個知識點可以從多個不同的角度進行講解，學生也可以從多個角度對其進行學習和理解，完成了解→熟悉→鞏固的學習過程。

例如，最大子段和問題就具有多重覆蓋的性質。最大子段和問題可以描述為：給定n個整數（可以是0、可正、可負）組成的序列，求該序列能夠取得最大連續子段的和。如果序列是{-2，6，-5，13，-5，4}，則滿足要求的子段是{6，-5，13}，其元素和是14，這也是該問題的解。

最大子段和問題雖然描述簡單，容易理解，但它有多種解法，涉及的知識點包括窮舉法、分治法、動態規劃、NP理論等，其計算復雜度涵蓋了O（n3），O（n2），O（nlogn），O（n）等4個層次。因此，該問題是一個典型的多重覆蓋的案例，在案例選取時可以優先選擇。

1.2 難易平衡的原則

依照教育學理論，案例教學法要把實際教育過程中真實的情景加以典型化處理，引導學生思考和決斷，使得相同或類似場景再現時，學生能夠根據學習時處理案例的經驗和技巧，有效處理新出現的情況和問題。因此，一方面，課堂上使用的案例要具有一定的難度和挑戰性，使得學生有興趣跟隨教師的思路去思考解決方案；另一方面，案例的難度又不能超出學生的能力范圍，否則學生會失去信心，與教學過程脫節。

最能體現案例選取的難易平衡原則的兩個問題是多段圖的最短路徑問題和最長公共子列問題。前者描述的是一個圖分為多個段，每個段有若干個節點，這些節點只與前一段的節點和后一段的節點之間有路徑，要求找到起點到終點距離最短的路徑。而最長公共子列問題描述的是在兩個字符序列中找到共同的但又最長的那個子列。

雖然這兩個問題都是動態規劃的典型案例，但難度是不一樣的。多段圖的最短路徑問題的求值過程和回溯求路徑（求解）的過程形象而直觀，因此可以作為動態規劃算法的入門案例。最長公共子列問題雖然描述起來簡單，但要建立遞推公式比較困難，也比較難以理解的，因此，可以作為動態規劃算法的提高案例。

但有些問題因為過難或過易不適合作為案例。樓層扔雞蛋問題講的是一個雞蛋從n層樓上摔下來不破，但從n+1層樓上摔下來必摔破，對有限的樓層數和雞蛋數，求最壞情況下至少要經過多少次實驗才能把n求出來。這個問題雖然也可以用動態規劃算法解決，但不易理解，因此由于受到學時數的限制，不適合作為專業碩士生算法教學案例。

2、案例庫建設

在基于完全案例覆蓋的算法教學法中，案例并不是孤立的、只服務于各章節和知識點的，相反，它們彼此間有緊密的關系，甚至可以說案例集合可以成為一個完整的體系。為了便于案例的選取和利用，需要把案例整理成庫，并在教學過程中不斷完善和發展。案例庫并不是一個個案例的簡單羅列，而是以數據庫系統的形式組織起來，便于從難度、涉及知識點、彼此關系等方面查詢，也便于添加、修改和刪除。

2.1 案例來源

案例庫中的案例有3個主要來源：經典問題、科研開發問題和公司面試題。

經典問題在案例庫中占有大部分的比例。經過前人的總結和積累，算法設計與分析的各個知識點都有一個或多個的經典問題可以作為案例。經典問題作為案例具有多方面的優勢。首先，這些問題已經被大多數學生熟悉，便于學生理解和掌握。例如漢諾塔問題，雖然學生尚不清楚案例涉及的分治和計算復雜度理論，但很容易被案例吸引，產生興趣。其次，問題解決方法研究得比較透徹，且一般有多種解法。第三，學生更容易在課后找到相應的學習資料，對所學知識加深理解。

案例的第2個主要來源是學生在科研和開發中碰到的問題。這部分問題更具有前沿性和實踐性，與實際聯系緊密，更能使學生掌握解決實際問題的方法。例如，在教學過程中有學生提出其導師的課題中如何用GPS快速準確地測量林地面積的問題。如果用傳統的林地分割法解決，不但數據收集困難，而且在計算中容易出現負面積和面積重復計算等嚴重的問題，但采用計算幾何的手段可以解決這些問題，而且計算過程簡單高效。因此，這個實際問題也成為計算幾何知識點的主要案例之一。通過鼓勵學生在課堂上通過提問和發電子郵件的形式獲取這些問題，幫助他們解決問題，同時豐富案例庫。

各大IT公司的面試題也是重要的案例來源。這些公司的研發部門為了招聘到具有發展潛力的研發人員，面試題目的重點已經不在程序的語法和具體的編程技巧上，而是把重點放在算法設計上，以考察所面試學生的算法水平和解決實際問題的能力。結課后1～3年的時間內，通過回訪調查，可以獲取這方面的案例，同時也可以掌握業界的研究動態和方向，以便在課程中有所涉及和傾向，為學生的就業奠定更好的基礎。

2.2 部分案例總結和列表

經過長時間的收集、整理和建設，案例庫已初見規模，形成了經典案例、研發案例和面試案例共同構成的案例體系。表1展現了部分案例的來源以及它們與算法設計的各個知識點之間的覆蓋關系。

2.3 完善案例相關的授課技巧

案例庫中的所有案例都具有一個重要的屬性：授課過程中使用該案例的技巧。這些技巧大致分為3類，分別是敘述故事、提出挑戰、破解懸疑。

敘述故事的技巧適合于知識點的引入環節，目的是吸引學生的注意力，激發其興趣。例如，在講解最小生成樹知識點時，可以講述以下蜘蛛建網的故事。一只大蜘蛛要結網了！結網之前首先要拉龍骨。龍骨的作用很重要，要確保每個關鍵點之間都有一段或多段蛛絲連接。這樣，可以保證一旦昆蟲落入網絡陷阱，蜘蛛能在第一時刻感受到。你的任務是：編寫一個程序，對一組輸入的固定點，能夠輸出一個方案，使得蛛絲的總長最小。通過這個故事，學生能夠迅速理解最小生成樹的定義，并饒有興趣地思考如何解決這個問題。

對于那些貌似容易解決，但實際需要大量理論和算法設計技巧作為支撐的案例，可以采用提出挑戰的方式授課，讓學生樂意嘗試。用GPS測算林地面積的問題就屬于這個類型。通過問題介紹，學生根據自己的知識積累很快就能想出三角形分割法、梯形分割法和小矩形分割法等方法。但這些方法都存在著實際計算方面的缺陷，因此可以提出挑戰：用所學過的計算幾何的知識和手段解決面積測算問題。而挑戰往往會帶來思考和行動的動力，讓學生在接受挑戰的過程中掌握相關的知識和技巧。

破解懸疑是懸疑影片最引人人勝的設計，而案例授課過程可以把這種手法引入課堂，使學生長時間保持課堂注意力，并使問題解決的過程給學生留下深刻的印象，從而強化知識點，強化算法設計技巧的教學效果。二部圖方面的婚配問題可以作為典型的破解懸疑的教學案例。在追求最大婚配數目標的過程中逐步講解什么是二部圖、什么是可增廣鏈、如何發現可增廣鏈、以及如何增加婚配數等，讓每一步都有一個具體的目標，讓學生圍繞該具體目標進行思考和設計。

3、課堂效果

通過長期的探索和積累，基于完全案例覆蓋的算法教學法取得了預期的效果。

（1）課堂出勤率有明顯的好轉。如果單純講解算法理論和算法技巧，課程開始階段還有很多學生堅持上課，但到課程中后期，很多學生就會以各種理由缺課。究其根本原因，是這部分學生認為自己無法跟上課程節奏，沒有課堂收獲。但采用了案例教學后，絕大部分學生能夠出勤，并且課程前期和中后期的出勤率大致相當。

（2）課堂氣氛有了很大提升。為了解決案例中的問題，學生會積極思考，參與課堂討論，能夠始終保持課堂注意力。

（3）促進了部分學生的研究和開發。這是因為部分案例來自學生的科研和開發實踐，案例在入庫之前已經得到了充分討論和有效解決。

（4）使學生在就業市場取得了一定的優勢。由于部分案例來源于IT公司的面試題，這就讓學生對就業有更充分的準備。而這些題目也是業界發展的風向標，因此對學生就業后的工作也有支持作用。事實上，在教學實踐中，學生最感興趣的案例就是公司面試題，這應該與越來越嚴峻的就業形勢有關。

4、結語

專業碩士研究生的學制更改為兩年，區別于科學碩士研究生的三年學制。為此，需要將專業碩士研究生的自主學習能力、實踐動手能力和團隊精神部分前移到課程教學中，以此彌補專業碩士研究生研究時間縮短、研究能力訓練和綜合素質培養不足的問題。如何在有限的學時內使專業碩士生既能快速理解算法的理論，又能讓他們掌握算法的設計技巧，是擺在算法設計與分析課程教師面前的重要問題。

基于完全案例覆蓋的算法教學法能夠提升學生學習算法的興趣，寓教于樂，通過示例實際問題的解決讓學生理解和掌握相關的知識點和理論，起到了良好的教學效果。其中的教學手法在為科學碩士研究生授課的過程中也有借鑒意義。

但是，需要針對教學大綱要求、市場需求和學生的實際情況從案例庫中優選相關教學案例，服務于專業碩士的算法教學活動。案例庫的建設是一個長期積累、不斷更新和發展變化的過程，需要大量的時間和精力的投人才能起到良好的效果。