研究生算法課程的分層次多樣化教學研究

趙緒營，姜建錦，王志強，張曉昆

（北京電子科技學院 計算機系，北京 100070）

0 引 言

算法設計與分析是計算機專業課程體系中的主干課程，也是培養和提高學生計算思維能力的重要課程[1]。通過本課程的學習，學生能理解和掌握算法設計的主要方法，掌握算法復雜度分析的基本方法和技巧，掌握常用的算法策略及應用，理解具有代表性的算法實現案例，了解目前最新的算法研究動向，全面地理解經典算法體系和現代優化算法理論。課程目標是重點培養學生算法設計的基本能力，培養學生對算法時間與空間復雜度進行正確分析的能力，提高學生利用算法理論解決實際問題的能力，為獨立分析與設計算法及優化算法打下良好的基礎。

1 教學內容

算法的研究是計算機科學的核心問題之一，具有極大的應用價值和理論價值。算法的主要內容是研究計算機及其相關領域中一些非數值計算的常用算法，因此是計算機科學與技術專業限定選修的重要基礎課。

1.1 知識框架

算法課程體系的主要內容以經典算法和現代智能算法的分析與設計為主，兼顧NP完全理論和概率算法，并簡要介紹近似算法領域的研究成果和研究進展。算法課程的知識框架見圖1[2]。

圖1 算法知識框架

處于算法知識框架最底層的是算法基礎知識，包括離散數學、概率統計等數學課程以及數據結構等計算機課程。按照專業培養計劃，這些先導課程已經開設過。考慮到部分學生的先修課程基礎不同，有些內容需要在算法課程教學過程中予以簡要介紹，如離散數學課程為算法分析與設計的學習和理解打下一定的邏輯思維和數學分析的基礎；程序設計基礎是學生利用某種程序設計語言實現算法的基礎；算法設計，特別是大型問題的算法設計，經常要用到數據結構基礎等。在授課過程中，應使學生能夠有機結合并融會貫通這些前序課程中學到的知識。

在算法的知識框架中，核心內容是算法的設計技術和分析方法，經典的算法策略如分治法、動態規劃、貪心算法、回溯法、分支限界法等，是計算機本科專業學習的重點內容，在此基礎上進一步綜合與提高，在算法分析部分重點學習算法復雜度分析，簡要介紹NP完全理論相關的概念和理論框架。算法知識框架的最高層次是結合算法研究進展介紹智能優化算法、近似算法、并行算法以及最新研究熱點與研究動向。

1.2 重點內容

該課程重點講解算法設計的策略、技巧、常用的方法和基本的算法分析方法以及經典的算法實現案例，逐步培養學生設計與分析算法的思維方式，引導學生提高問題抽象和建模的能力。通過本課程的教學，要強化學生理解計算機算法分析、算法設計及算法復雜度理論涉及的基本概念和基礎知識，使學生掌握基本的算法分析方法和常用的算法設計方法；通過對算法實例的分析，進一步加深學生對算法設計方法的認識和理解；通過理論和實踐教學環節的學習，要求學生能夠應用課程介紹的方法設計軟件開發中常用的或較為復雜的實際問題的算法，努力做到讓算法運行快捷、求解問題有效、結果穩定，并能科學評估算法時空復雜度，提高軟件設計的質量，達到培養學生扎實的專業知識和基本技能以及從事應用軟件開發和測試能力的目標。

相對于本科教學，研究生算法教學的重點內容包括：①復雜性與可計算性理論，該部分內容是本科教學內容的擴展與提高；②現代優化算法，又稱智能算法。現代優化算法是20世紀80年代初興起的啟發式算法，包括模擬退火、遺傳算法、神經網絡、禁忌搜索、蟻群算法（1992年）、粒子群算法（1995年）等。這些算法模擬大自然和人類的智慧實現對NP問題的優化求解，因此被稱作計算智能優化算法[3]。智能算法或模仿生物界的進化過程，或模仿生物的生理構造和身體機能，或模仿動物的群體行為，或模仿人類的思維、語言和記憶過程的特性，或模仿自然界的物理現象，實現對問題的優化求解。智能算法在理論和實際應用方面已經得到了很大的發展，因此將其納入研究生算法課程的重點教學內容。

1.3 參考教材

算法課程依據上述知識框架和教學內容，面向不同的學習基礎，適用軟硬不同的選課方向，采用分層次、多樣化的課程學習結構，不指定固定的課程教材，僅給出主要的參考教材。例如王曉東的《計算機算法設計與分析》（第4版），該書是普通高等教育“十一五”國家級規劃教材和國家精品課程教材。全書以算法設計策略為知識單元，系統介紹計算機算法的設計方法與分析技巧。書中既涉及經典與實用算法及實例分析，又包括算法熱點領域追蹤[4]。

還有《算法導論》（第3版），作者是達特茅斯學院計算機科學系教授、系主任，目前的研究興趣包括算法工程、并行計算、具有高延遲的加速計算等。該教材將嚴謹性和全面性融為一體，深入討論各類算法，并著力使這些算法的設計和分析能為各個層次的讀者接受。全書各章自成體系，可以作為獨立的學習單元；算法以英語和偽代碼的形式描述，具備初步程序設計經驗的人就能看懂；說明和解釋力求淺顯易懂，不失深度和數學嚴謹性[5]。

2 教學過程

根據算法知識框架和教學內容的安排，在教學過程中需要兼顧算法設計與分析兩方面的內容，經典算法與現代算法內容形成互補，特別注重理論與應用相結合。算法策略與算法分析以及現代算法理論的內容以課堂講授為主，算法實例和應用問題分別以教師講述（學時比例占四分之一）、學生討論（學時比例占二分之一）加教師點評（學時比例占四分之一）的方式進行。通過提出若干討論問題，學生分組開展專題研究，課堂展示成果等方法，加強學生自學能力、理論聯系實踐能力的培養。通過實踐教學環節進一步加強學生應用算法設計方法解決具體問題能力的訓練，特別注意培養學生問題分析、算法設計、算法分析、算法實現、算法測試等方面的綜合能力。為了配合理論和實踐教學，在經典算法和現代算法學習結束后，分別布置大作業。課程作業和實驗內容盡量針對不同知識基礎和層次的學生給出不同的題目和要求。

2.1 注重能力培養，將計算思維滲透于課堂教學之中

算法作為一門專業基礎課程，責無旁貸地擔負起培養學生計算思維能力的任務。計算思維是指運用計算機科學的基礎概念和方法對問題進行描述、建模和求解的思維方式，是一種普適性的科學思維方法[6]。計算思維方式不僅限于解決計算問題，還包括系統設計、人類行為的理解等問題，如何選擇合適的方式陳述這些問題，以及對問題的相關方面建模并用最有效的方法實現問題求解。計算思維已經對各門學科產生了不同程度的影響，作為一個信息類的高校，計算思維能力的培養應當貫穿于大學學習的全部過程中，滲透在各門計算機相關課程里。但是，如何在具體的課程教學中培養學生的計算思維能力，目前尚沒有成熟的教學指導體系。筆者努力將計算思維滲透于算法課堂教學中，在課堂講解算法設計的策略、技巧、常用的方法和基本的算法分析方法以及經典的算法實現案例的教學過程中，注重培養學生設計與分析算法的思維方式，引導學生提高問題抽象和建模的能力。講解經典算法實例時，通過課堂作業或提問的方式，讓學生舉例說明用同樣的算法策略能夠解決的實際問題。同一個經典問題，可以思考幾種算法策略得到不同的解決方案，還要注重思考不同算法之間的區別和聯系，有時還可以通過提問讓學生思考在極端或特例數據的情況下某一種算法策略的適用性問題，可能超出了教材講述的內容，但是這種方式能夠激發學生的想象和創新能力。另外，根據學生的程度布置不同的任務、開展分組討論、選取學生容易接受的課程實例等，都是算法教學值得借鑒的多樣化教學模式。

2.2 以學生為主體，分層次開展實踐教學

在實踐教學過程中，實驗性質要設置必做實驗與選做實驗，注意區分對待不同程度的學生，針對本科計算機課程基礎或程序設計能力不同的學生，實驗題目提供不同的選項和要求。信息類相關專業選修本課程的研究生自由選擇實驗內容以及考核形式，分別給出不同的題目和成績評價標準。實驗教學以學生為主體，教師為主導，對實驗過程中出現的問題一般由學生自主研究解決，教師僅作啟發性提示和引導。通過不同層次的實驗內容和要求，從個性化發展的角度培養學生的計算思維能力。

2.3 開展教學科研實踐活動

學校的科研與教學相結合，經常開展課外實踐活動，能夠為具有研究興趣和探索精神的學生提供一個可拓展的空間。該活動適合程度較高的學生，根據個人興趣和專長進行分組，活動的內容、目標及成果提交形式見表1。

3 課程考核

目前理論考核占課程成績的70%，課程實踐考核占20%，課程綜述或最新研究進展論文占10%。為了引導學生理論聯系實際，激發學生的創新能力和系統設計能力，下一步將建立更加科學的考核體系。算法課程實踐部分成為課程學習與考核的重點內容，實踐環節安排在課外進行，分為個人作業和團隊作業兩個層次，實踐考核分為實踐報告和課堂答辯兩部分進行。個人作業是算法實踐考核環節的最低要求，要求學生針對某一個問題，必須獨立完成算法設計、程序實現、測試及結果分析，主要是為了培養學生基本的算法設計與分析以及實踐能力。團隊作業要解決的是綜合性較強的問題，需要2～4人的團隊協作，從建模到測試結果分析需要較強的理論和實踐能力，重點培養學生的算法設計能力和團隊合作精神。

4 結 語

作為特需行業的專業碩士研究生教育開展的時間較短，算法沒有作為計算機應用專業研究生的核心課程，上好這門課程無疑是一個較大的挑戰。目前在本科算法教學過程中取得一定的教學經驗的基礎上，研究生算法教學基于較高的目標進行了改進和提高。在計算機專業碩士研究生的教學與實踐過程中，筆者對計算思維培養的方法進行了初步探索，將這種思維方式融入到教學的各個環節之中，并且結合專業碩士研究生的特點，提出基于分層次、多樣化訓練的計算思維培養方法，以提高教學效率，挖掘學生潛能，培養學生利用計算思維方式自主分析與解決實際問題的能力。

表1 教學科研實踐活動分組表

參考文獻：

[1]張巖, 姜建錦, 張克君. 計算機學科專業學位碩士研究生特色課程體系建設[J]. 計算機教育, 2016(12): 91-94.

[2]屈婉玲, 王捍貧, 段莉華. 面向軟件工程學科的算法課程建設[J]. 中國大學教學, 2012(12): 55-57.

[3]梁旭. 現代智能優化混合算法及其應用[M]. 2版. 北京: 電子工業出版社, 2014(7): 242.

[4]王曉東. 計算機算法設計與分析[M]. 4版. 北京: 電子工業出版社, 2012(2): 306.

[5]Cormen T H, Leise C E. 算法導論[M]. 3版. 北京: 機械工業出版社, 2012(12): 780.

[6]Jeannette M W. Computational thinking[J]. Communications of the ACM, 2006(3): 33-35.