基于完全案例覆蓋的專業(yè)碩士生算法教學(xué)方法

摘要：針對與計(jì)算機(jī)相關(guān)的專業(yè)碩士研究生算法理論基礎(chǔ)相對薄弱和授課學(xué)時(shí)數(shù)較少的狀況，在實(shí)踐基礎(chǔ)上，提出以大量案例多重覆蓋知識(shí)點(diǎn)的算法設(shè)計(jì)與分析課程教學(xué)方法，同時(shí)介紹相應(yīng)的教學(xué)案例庫的構(gòu)建和完善。

關(guān)鍵詞：專業(yè)碩士；算法設(shè)計(jì)；算法分析；案例覆蓋；案例庫

0、引言

作為我國人才發(fā)展規(guī)劃的重要組成部分和支撐手段，我國專業(yè)碩士學(xué)位正處于高速發(fā)展的機(jī)遇期。高校正在抓住機(jī)會(huì)，采取積極措施，大力促進(jìn)碩士專業(yè)學(xué)位教育的全面發(fā)展。教育部在2010年要求進(jìn)一步調(diào)整優(yōu)化教育結(jié)構(gòu)，積極穩(wěn)妥地推動(dòng)我國碩士研究生教育的戰(zhàn)略轉(zhuǎn)變，從以培養(yǎng)學(xué)術(shù)型人才為主，逐漸轉(zhuǎn)變?yōu)橐耘囵B(yǎng)應(yīng)用型人才為主。這意味著擴(kuò)大全日制專業(yè)碩士研究生的培養(yǎng)規(guī)模成為研究生培養(yǎng)的一個(gè)趨勢。

區(qū)別于側(cè)重理論和研究的科學(xué)碩士學(xué)位，專業(yè)碩士學(xué)位教育主要培養(yǎng)滿足特定職業(yè)需求和有特定職業(yè)背景的高級(jí)專門人才。專業(yè)學(xué)位教育具備專業(yè)性、綜合性和開放性三大特點(diǎn)。

算法設(shè)計(jì)與分析是專業(yè)碩士研究生課程，是多個(gè)專業(yè)和方向的必修課程，這些專業(yè)包括計(jì)算機(jī)科學(xué)與技術(shù)、計(jì)算機(jī)應(yīng)用、計(jì)算機(jī)軟件與理論、軟件工程等。該課程同時(shí)還是一門與計(jì)算機(jī)有關(guān)的非計(jì)算機(jī)專業(yè)的專業(yè)課程，包括管理科學(xué)與工程、系統(tǒng)工程、應(yīng)用數(shù)學(xué)與計(jì)算數(shù)學(xué)等專業(yè)。本課程的前驅(qū)課程包括離散數(shù)學(xué)、程序設(shè)計(jì)基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)等，與計(jì)算方法和計(jì)算機(jī)圖形學(xué)等課程關(guān)系緊密，既具有鮮明的理論體系，也具有很強(qiáng)的實(shí)踐性。

專業(yè)碩士研究生的算法設(shè)計(jì)與分析課程的主要目標(biāo)是通過講授不同類型算法的基本原理、解決方法、實(shí)現(xiàn)技術(shù)等，分析不同算法的時(shí)間復(fù)雜度和空間復(fù)雜度，使學(xué)生通過該課程的學(xué)習(xí)，能夠?qū)ο到y(tǒng)軟件和應(yīng)用軟件開發(fā)過程中的實(shí)際問題設(shè)計(jì)出高效、優(yōu)化的算法，為開發(fā)出優(yōu)秀的軟件奠定基礎(chǔ)。該課程涵蓋的主要內(nèi)容有常用數(shù)學(xué)工具、窮舉法、貪心算法、分治法、減治法、動(dòng)態(tài)規(guī)劃、并查集、回溯法、分支限界法、計(jì)算幾何、隨機(jī)算法、NP理論等12個(gè)方面。

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

大量教學(xué)實(shí)踐證實(shí)：純粹的理論灌輸會(huì)使學(xué)生很快失去學(xué)習(xí)課程的興趣，不能堅(jiān)持課堂學(xué)習(xí)，更沒有意愿在課后的練習(xí)和實(shí)踐環(huán)節(jié)投入時(shí)間和精力。

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

1、案例選取的原則

所謂的案例教學(xué)法，就是利用案例作為教學(xué)媒介和教學(xué)手段，以提高學(xué)生綜合能力為目標(biāo)的教學(xué)方法。案例的選取至關(guān)重要，因?yàn)榘咐前咐虒W(xué)的核心，直接影響著學(xué)生的興趣和對知識(shí)的接受程度，從而最終影響著案例教學(xué)法的實(shí)際效果。

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

1.1 多重覆蓋原則

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

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

最大子段和問題雖然描述簡單，容易理解，但它有多種解法，涉及的知識(shí)點(diǎn)包括窮舉法、分治法、動(dòng)態(tài)規(guī)劃、NP理論等，其計(jì)算復(fù)雜度涵蓋了O（n3），O（n2），O（nlogn），O（n）等4個(gè)層次。因此，該問題是一個(gè)典型的多重覆蓋的案例，在案例選取時(shí)可以優(yōu)先選擇。

1.2 難易平衡的原則

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

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

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

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

2、案例庫建設(shè)

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

2.1 案例來源

案例庫中的案例有3個(gè)主要來源：經(jīng)典問題、科研開發(fā)問題和公司面試題。

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

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

各大IT公司的面試題也是重要的案例來源。這些公司的研發(fā)部門為了招聘到具有發(fā)展?jié)摿Φ难邪l(fā)人員，面試題目的重點(diǎn)已經(jīng)不在程序的語法和具體的編程技巧上，而是把重點(diǎn)放在算法設(shè)計(jì)上，以考察所面試學(xué)生的算法水平和解決實(shí)際問題的能力。結(jié)課后1～3年的時(shí)間內(nèi)，通過回訪調(diào)查，可以獲取這方面的案例，同時(shí)也可以掌握業(yè)界的研究動(dòng)態(tài)和方向，以便在課程中有所涉及和傾向，為學(xué)生的就業(yè)奠定更好的基礎(chǔ)。

2.2 部分案例總結(jié)和列表

經(jīng)過長時(shí)間的收集、整理和建設(shè)，案例庫已初見規(guī)模，形成了經(jīng)典案例、研發(fā)案例和面試案例共同構(gòu)成的案例體系。表1展現(xiàn)了部分案例的來源以及它們與算法設(shè)計(jì)的各個(gè)知識(shí)點(diǎn)之間的覆蓋關(guān)系。

2.3 完善案例相關(guān)的授課技巧

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

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

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

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

3、課堂效果

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

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

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

（3）促進(jìn)了部分學(xué)生的研究和開發(fā)。這是因?yàn)椴糠职咐齺碜詫W(xué)生的科研和開發(fā)實(shí)踐，案例在入庫之前已經(jīng)得到了充分討論和有效解決。

（4）使學(xué)生在就業(yè)市場取得了一定的優(yōu)勢。由于部分案例來源于IT公司的面試題，這就讓學(xué)生對就業(yè)有更充分的準(zhǔn)備。而這些題目也是業(yè)界發(fā)展的風(fēng)向標(biāo)，因此對學(xué)生就業(yè)后的工作也有支持作用。事實(shí)上，在教學(xué)實(shí)踐中，學(xué)生最感興趣的案例就是公司面試題，這應(yīng)該與越來越嚴(yán)峻的就業(yè)形勢有關(guān)。

4、結(jié)語

專業(yè)碩士研究生的學(xué)制更改為兩年，區(qū)別于科學(xué)碩士研究生的三年學(xué)制。為此，需要將專業(yè)碩士研究生的自主學(xué)習(xí)能力、實(shí)踐動(dòng)手能力和團(tuán)隊(duì)精神部分前移到課程教學(xué)中，以此彌補(bǔ)專業(yè)碩士研究生研究時(shí)間縮短、研究能力訓(xùn)練和綜合素質(zhì)培養(yǎng)不足的問題。如何在有限的學(xué)時(shí)內(nèi)使專業(yè)碩士生既能快速理解算法的理論，又能讓他們掌握算法的設(shè)計(jì)技巧，是擺在算法設(shè)計(jì)與分析課程教師面前的重要問題。

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

但是，需要針對教學(xué)大綱要求、市場需求和學(xué)生的實(shí)際情況從案例庫中優(yōu)選相關(guān)教學(xué)案例，服務(wù)于專業(yè)碩士的算法教學(xué)活動(dòng)。案例庫的建設(shè)是一個(gè)長期積累、不斷更新和發(fā)展變化的過程，需要大量的時(shí)間和精力的投人才能起到良好的效果。