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

趙緒營，姜建錦，王志強(qiáng)，張曉昆

（北京電子科技學(xué)院 計(jì)算機(jī)系，北京 100070）

0 引 言

算法設(shè)計(jì)與分析是計(jì)算機(jī)專業(yè)課程體系中的主干課程，也是培養(yǎng)和提高學(xué)生計(jì)算思維能力的重要課程[1]。通過本課程的學(xué)習(xí)，學(xué)生能理解和掌握算法設(shè)計(jì)的主要方法，掌握算法復(fù)雜度分析的基本方法和技巧，掌握常用的算法策略及應(yīng)用，理解具有代表性的算法實(shí)現(xiàn)案例，了解目前最新的算法研究動向，全面地理解經(jīng)典算法體系和現(xiàn)代優(yōu)化算法理論。課程目標(biāo)是重點(diǎn)培養(yǎng)學(xué)生算法設(shè)計(jì)的基本能力，培養(yǎng)學(xué)生對算法時間與空間復(fù)雜度進(jìn)行正確分析的能力，提高學(xué)生利用算法理論解決實(shí)際問題的能力，為獨(dú)立分析與設(shè)計(jì)算法及優(yōu)化算法打下良好的基礎(chǔ)。

1 教學(xué)內(nèi)容

算法的研究是計(jì)算機(jī)科學(xué)的核心問題之一，具有極大的應(yīng)用價(jià)值和理論價(jià)值。算法的主要內(nèi)容是研究計(jì)算機(jī)及其相關(guān)領(lǐng)域中一些非數(shù)值計(jì)算的常用算法，因此是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)限定選修的重要基礎(chǔ)課。

1.1 知識框架

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

圖1 算法知識框架

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

在算法的知識框架中，核心內(nèi)容是算法的設(shè)計(jì)技術(shù)和分析方法，經(jīng)典的算法策略如分治法、動態(tài)規(guī)劃、貪心算法、回溯法、分支限界法等，是計(jì)算機(jī)本科專業(yè)學(xué)習(xí)的重點(diǎn)內(nèi)容，在此基礎(chǔ)上進(jìn)一步綜合與提高，在算法分析部分重點(diǎn)學(xué)習(xí)算法復(fù)雜度分析，簡要介紹NP完全理論相關(guān)的概念和理論框架。算法知識框架的最高層次是結(jié)合算法研究進(jìn)展介紹智能優(yōu)化算法、近似算法、并行算法以及最新研究熱點(diǎn)與研究動向。

1.2 重點(diǎn)內(nèi)容

該課程重點(diǎn)講解算法設(shè)計(jì)的策略、技巧、常用的方法和基本的算法分析方法以及經(jīng)典的算法實(shí)現(xiàn)案例，逐步培養(yǎng)學(xué)生設(shè)計(jì)與分析算法的思維方式，引導(dǎo)學(xué)生提高問題抽象和建模的能力。通過本課程的教學(xué)，要強(qiáng)化學(xué)生理解計(jì)算機(jī)算法分析、算法設(shè)計(jì)及算法復(fù)雜度理論涉及的基本概念和基礎(chǔ)知識，使學(xué)生掌握基本的算法分析方法和常用的算法設(shè)計(jì)方法；通過對算法實(shí)例的分析，進(jìn)一步加深學(xué)生對算法設(shè)計(jì)方法的認(rèn)識和理解；通過理論和實(shí)踐教學(xué)環(huán)節(jié)的學(xué)習(xí)，要求學(xué)生能夠應(yīng)用課程介紹的方法設(shè)計(jì)軟件開發(fā)中常用的或較為復(fù)雜的實(shí)際問題的算法，努力做到讓算法運(yùn)行快捷、求解問題有效、結(jié)果穩(wěn)定，并能科學(xué)評估算法時空復(fù)雜度，提高軟件設(shè)計(jì)的質(zhì)量，達(dá)到培養(yǎng)學(xué)生扎實(shí)的專業(yè)知識和基本技能以及從事應(yīng)用軟件開發(fā)和測試能力的目標(biāo)。

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

1.3 參考教材

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

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

2 教學(xué)過程

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

2.1 注重能力培養(yǎng)，將計(jì)算思維滲透于課堂教學(xué)之中

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

2.2 以學(xué)生為主體，分層次開展實(shí)踐教學(xué)

在實(shí)踐教學(xué)過程中，實(shí)驗(yàn)性質(zhì)要設(shè)置必做實(shí)驗(yàn)與選做實(shí)驗(yàn)，注意區(qū)分對待不同程度的學(xué)生，針對本科計(jì)算機(jī)課程基礎(chǔ)或程序設(shè)計(jì)能力不同的學(xué)生，實(shí)驗(yàn)題目提供不同的選項(xiàng)和要求。信息類相關(guān)專業(yè)選修本課程的研究生自由選擇實(shí)驗(yàn)內(nèi)容以及考核形式，分別給出不同的題目和成績評價(jià)標(biāo)準(zhǔn)。實(shí)驗(yàn)教學(xué)以學(xué)生為主體，教師為主導(dǎo)，對實(shí)驗(yàn)過程中出現(xiàn)的問題一般由學(xué)生自主研究解決，教師僅作啟發(fā)性提示和引導(dǎo)。通過不同層次的實(shí)驗(yàn)內(nèi)容和要求，從個性化發(fā)展的角度培養(yǎng)學(xué)生的計(jì)算思維能力。

2.3 開展教學(xué)科研實(shí)踐活動

學(xué)校的科研與教學(xué)相結(jié)合，經(jīng)常開展課外實(shí)踐活動，能夠?yàn)榫哂醒芯颗d趣和探索精神的學(xué)生提供一個可拓展的空間。該活動適合程度較高的學(xué)生，根據(jù)個人興趣和專長進(jìn)行分組，活動的內(nèi)容、目標(biāo)及成果提交形式見表1。

3 課程考核

目前理論考核占課程成績的70%，課程實(shí)踐考核占20%，課程綜述或最新研究進(jìn)展論文占10%。為了引導(dǎo)學(xué)生理論聯(lián)系實(shí)際，激發(fā)學(xué)生的創(chuàng)新能力和系統(tǒng)設(shè)計(jì)能力，下一步將建立更加科學(xué)的考核體系。算法課程實(shí)踐部分成為課程學(xué)習(xí)與考核的重點(diǎn)內(nèi)容，實(shí)踐環(huán)節(jié)安排在課外進(jìn)行，分為個人作業(yè)和團(tuán)隊(duì)作業(yè)兩個層次，實(shí)踐考核分為實(shí)踐報(bào)告和課堂答辯兩部分進(jìn)行。個人作業(yè)是算法實(shí)踐考核環(huán)節(jié)的最低要求，要求學(xué)生針對某一個問題，必須獨(dú)立完成算法設(shè)計(jì)、程序?qū)崿F(xiàn)、測試及結(jié)果分析，主要是為了培養(yǎng)學(xué)生基本的算法設(shè)計(jì)與分析以及實(shí)踐能力。團(tuán)隊(duì)作業(yè)要解決的是綜合性較強(qiáng)的問題，需要2～4人的團(tuán)隊(duì)協(xié)作，從建模到測試結(jié)果分析需要較強(qiáng)的理論和實(shí)踐能力，重點(diǎn)培養(yǎng)學(xué)生的算法設(shè)計(jì)能力和團(tuán)隊(duì)合作精神。

4 結(jié) 語

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

表1 教學(xué)科研實(shí)踐活動分組表

參考文獻(xiàn)：

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

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

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

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

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

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