算法分析與復(fù)雜性理論課程案例化教學(xué)改革

田衛(wèi)新

（三峽大學(xué) 計(jì)算機(jī)與信息學(xué)院，湖北 宜昌 443002）

0 引言

算法分析與復(fù)雜性理論是面向計(jì)算機(jī)專(zhuān)業(yè)研究生開(kāi)設(shè)的一門(mén)理論與實(shí)用性并重的課程，本課程是在計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)本科課程算法設(shè)計(jì)與分析基礎(chǔ)上，加強(qiáng)對(duì)算法分析方法的學(xué)習(xí)，通過(guò)對(duì)經(jīng)典算法的深入分析，提高學(xué)生算法設(shè)計(jì)能力。同時(shí)通過(guò)對(duì)算法復(fù)雜性理論的介紹，加深學(xué)生對(duì)計(jì)算機(jī)原理的理解，為今后從事相關(guān)理論和應(yīng)用研究打下堅(jiān)實(shí)的基礎(chǔ)。原課程在算法分析部分側(cè)重于以分治法、動(dòng)態(tài)規(guī)劃法、回溯法、貪心法等經(jīng)典算法為例進(jìn)行分析，由于這些算法與當(dāng)前學(xué)生感興趣的機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘技術(shù)等計(jì)算機(jī)熱門(mén)領(lǐng)域難以建立直接關(guān)聯(lián)，造成學(xué)生認(rèn)為算法分析與設(shè)計(jì)技術(shù)已經(jīng)過(guò)時(shí)的誤解。另一方面由于課程內(nèi)容本身的抽象性，為教學(xué)帶來(lái)了一定的挑戰(zhàn)。學(xué)生的學(xué)習(xí)興趣不高、知識(shí)掌握不牢固，學(xué)生的主動(dòng)性較低，導(dǎo)致多數(shù)學(xué)生對(duì)算法不能深入理解，只能靠機(jī)械記憶，應(yīng)用能力不足。探索根據(jù)學(xué)生的知識(shí)基礎(chǔ)，合理設(shè)計(jì)教學(xué)過(guò)程，激發(fā)學(xué)生學(xué)習(xí)興趣，參與課堂教學(xué)，有機(jī)結(jié)合課內(nèi)教學(xué)和課外學(xué)習(xí)，達(dá)成課程的教學(xué)目標(biāo)，需要在教學(xué)過(guò)程中不斷思考和改進(jìn)[1]。

近年來(lái)隨著人工智能、大數(shù)據(jù)技術(shù)的迅猛發(fā)展，基于數(shù)據(jù)集的學(xué)習(xí)算法展現(xiàn)了巨大的優(yōu)性，越來(lái)越受到重視。相比之下，傳統(tǒng)經(jīng)典算法的應(yīng)用領(lǐng)域有逐漸退化的趨勢(shì)。為了適應(yīng)這種新的變化，并且在教學(xué)中展現(xiàn)算法設(shè)計(jì)技術(shù)從傳統(tǒng)經(jīng)典算法向智能、學(xué)習(xí)型算法發(fā)展演變的脈絡(luò)關(guān)系，結(jié)合案例教學(xué)方法，借鑒已有教學(xué)案例建設(shè)的成功經(jīng)驗(yàn)[2-4]，對(duì)算法分析與復(fù)雜度理論課程進(jìn)行了案例教學(xué)設(shè)計(jì)。在案例教學(xué)基礎(chǔ)上，增強(qiáng)研討環(huán)節(jié)，要求學(xué)生在課前進(jìn)行分組準(zhǔn)備，在課堂上圍繞案例算法進(jìn)行討論，從而將課堂與課外學(xué)習(xí)有機(jī)結(jié)合，改變?cè)瓉?lái)單一課堂講授的教學(xué)模式，提高課堂互動(dòng)性，提高教學(xué)質(zhì)量。

1 案例設(shè)計(jì)思路

1）案例設(shè)計(jì)成體系。

選擇案例時(shí)，根據(jù)算法設(shè)計(jì)技術(shù)的發(fā)展邏輯，與本科階段課程具有一定的銜接，由淺入深、循序漸進(jìn)介紹基本算法思想，最優(yōu)化問(wèn)題及求解算法，基于數(shù)據(jù)集學(xué)習(xí)算法的基礎(chǔ)、發(fā)展過(guò)程及核心思想，相應(yīng)產(chǎn)生了算法分析評(píng)價(jià)方法的改進(jìn)，使學(xué)生對(duì)算法領(lǐng)域有整體把握，達(dá)到以案例學(xué)習(xí)促進(jìn)算法分析、以分析促進(jìn)提高算法設(shè)計(jì)水平的目標(biāo)。

2）以培養(yǎng)創(chuàng)新思維為目標(biāo)。

算法分析與復(fù)雜性理論課程的主要目的是通過(guò)對(duì)算法分析評(píng)價(jià)技術(shù)的學(xué)習(xí)，培養(yǎng)研究生算法設(shè)計(jì)能力、程序?qū)崿F(xiàn)與計(jì)算思維能力。算法作為計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的核心對(duì)象，集中體現(xiàn)了原創(chuàng)者的創(chuàng)新思維。作為計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)研究生，圍繞算法的創(chuàng)新思維能力是在校期間需要著力培養(yǎng)的重要內(nèi)容。算法創(chuàng)新思維能力的培養(yǎng)過(guò)程不能脫離實(shí)際應(yīng)用獨(dú)立存在，需要結(jié)合實(shí)際算法設(shè)計(jì)案例，經(jīng)過(guò)學(xué)習(xí)、理解、掌握到精通的過(guò)程后，由學(xué)生自己總結(jié)領(lǐng)會(huì)才會(huì)最終習(xí)得。因此，在算法相關(guān)的案例教學(xué)中，必須強(qiáng)化學(xué)生主動(dòng)參與，提供實(shí)踐機(jī)會(huì)。

3）以課堂交互為手段。

良好的課堂交互要求教師和學(xué)生都要精心做好課堂準(zhǔn)備，在圍繞案例展開(kāi)研討時(shí)，學(xué)生需要預(yù)先對(duì)分配的課題有較深入的理解，查閱資料并完成設(shè)計(jì)及講解準(zhǔn)備，對(duì)學(xué)生課下的學(xué)習(xí)提出了較高的要求。教師在課堂教學(xué)的討論環(huán)節(jié)，需要發(fā)揮引導(dǎo)作用，控制討論節(jié)奏，充分調(diào)動(dòng)學(xué)生的學(xué)習(xí)積極性，增大開(kāi)放式問(wèn)題的討論范圍，鼓勵(lì)創(chuàng)新性思維，并做好分析和總結(jié)，提高教學(xué)效果。

4）相應(yīng)的考核辦法。

為了促進(jìn)課程案例化教學(xué)的成功實(shí)施，需要設(shè)計(jì)相應(yīng)的課程考核方法，對(duì)學(xué)習(xí)效果和過(guò)程進(jìn)行評(píng)價(jià)，以適應(yīng)案例教學(xué)各環(huán)節(jié)如課前準(zhǔn)備情況、課堂參與度等方面的具體要求。

2 案例化教學(xué)實(shí)施

1）教學(xué)目標(biāo)。

算法分析與復(fù)雜性理論課程目標(biāo)是掌握算法評(píng)價(jià)的基本理論，掌握算法分析的基本方法，理解算法復(fù)雜性理論體系并熟悉復(fù)雜性理論的基本結(jié)論。理解經(jīng)典算法設(shè)計(jì)思想，具備應(yīng)用經(jīng)典算法解決問(wèn)題的能力；了解最優(yōu)化問(wèn)題及其分類(lèi)，熟悉常見(jiàn)最優(yōu)化問(wèn)題的求解算法；理解機(jī)器學(xué)習(xí)與最優(yōu)化問(wèn)題的聯(lián)系；掌握常見(jiàn)的分類(lèi)及聚類(lèi)算法。通過(guò)引入算法分析和復(fù)雜性理論的實(shí)際應(yīng)用場(chǎng)景，提高學(xué)生理論與實(shí)踐相結(jié)合的能力；通過(guò)對(duì)案例的學(xué)習(xí)，提高算法分析與設(shè)計(jì)能力。案例化教學(xué)改革的目的是圍繞上述課程目標(biāo)，建立以學(xué)習(xí)為中心、以學(xué)生為主體、以教師為主導(dǎo)，建立促進(jìn)學(xué)生發(fā)展核心素養(yǎng)和培養(yǎng)應(yīng)用能力的課堂教學(xué)模式。

2）教學(xué)內(nèi)容及安排。

算法分析與復(fù)雜性理論教學(xué)內(nèi)容與安排見(jiàn)表1。

表1 算法分析與復(fù)雜性理論教學(xué)內(nèi)容與安排

3）教學(xué)組織。

將算法分析與復(fù)雜性理論課程內(nèi)容按照“知”“懂”“會(huì)”“熟”等幾方面要求進(jìn)行分類(lèi)，課堂教學(xué)根據(jù)不同的類(lèi)別綜合采用課堂講授、課堂討論、示范講解、分組研討等組織形式。

課堂講授是最為傳統(tǒng)的教學(xué)模式，具有目標(biāo)明確，教學(xué)效率高等優(yōu)點(diǎn)。算法分析和復(fù)雜性理論課程內(nèi)容中的算法評(píng)價(jià)、算法分析的基本方法、數(shù)學(xué)基礎(chǔ)、經(jīng)典算法設(shè)計(jì)思想、最優(yōu)化問(wèn)題及求解、機(jī)器學(xué)習(xí)問(wèn)題的形式化及求解、復(fù)雜性理論等，需要學(xué)生建立相關(guān)領(lǐng)域的知識(shí)體系和術(shù)語(yǔ)系統(tǒng)，是課程屬于要求“知”“懂”的內(nèi)容，對(duì)該部分內(nèi)容采用課堂講授的方式，同時(shí)對(duì)理論講授中涉及的重要、復(fù)雜的知識(shí)點(diǎn)進(jìn)行梳理、總結(jié)，歸納成疑難問(wèn)題組織課堂討論，幫助厘清概念、理解原理并對(duì)容易混淆的方程形式及判別條件等進(jìn)行區(qū)分辨識(shí)。

對(duì)于算法分析和復(fù)雜性理論課程內(nèi)容中要求“會(huì)”和“熟”的部分，如經(jīng)典算法設(shè)計(jì)、最優(yōu)化算法設(shè)計(jì)、典型聚類(lèi)算法設(shè)計(jì)和典型分類(lèi)算法設(shè)計(jì)等應(yīng)用要求較高的內(nèi)容，需要學(xué)生多做練習(xí)才能達(dá)到教學(xué)效果。為了促進(jìn)學(xué)生較好完成相關(guān)的練習(xí)，采用基于案例的示范講解和分組研討的方式組織教學(xué)。首先按照前述原則設(shè)計(jì)相關(guān)案例，并在課堂上對(duì)案例進(jìn)行示范講解，規(guī)范研論內(nèi)容和形式。然后設(shè)計(jì)與案例相關(guān)的練習(xí)，以作業(yè)形式提前布置，學(xué)生按每組2～3 人進(jìn)行分組，以組為單位完成研討準(zhǔn)備，包括編寫(xiě)算法程序、制作介紹程序原理的PPT 等。課堂研討由每個(gè)小組依次按照PPT 介紹，包括程序運(yùn)行演示、交流提問(wèn)和教師歸納總結(jié)等環(huán)節(jié)。要求在PPT 介紹中按照分析問(wèn)題、問(wèn)題的形式化、算法設(shè)計(jì)、結(jié)果展示與分析、算法復(fù)雜度分析及可能的改進(jìn)建議等內(nèi)容進(jìn)行。教師引導(dǎo)課堂研討的正常進(jìn)行，糾正錯(cuò)誤，然后收集和分析不同的觀點(diǎn)，最后歸納補(bǔ)充。

4）考核體系。

為鼓勵(lì)學(xué)生對(duì)課程內(nèi)容及案例展開(kāi)深入研究，通過(guò)交流研討掌握算法分析設(shè)計(jì)理論及應(yīng)用，同時(shí)對(duì)教學(xué)過(guò)程進(jìn)行反饋優(yōu)化，對(duì)課程評(píng)價(jià)采用了多元化的綜合評(píng)價(jià)法。多元化綜合評(píng)價(jià)法綜合考核學(xué)生的知識(shí)點(diǎn)掌握情況、應(yīng)用能力、創(chuàng)新能力、協(xié)作能力、溝通能力等方面，具體見(jiàn)表2。

表2 課程考核體系

作業(yè)隨堂布置，要求學(xué)生在課后完成，主要涉及算法分析的數(shù)學(xué)基礎(chǔ)和方法、復(fù)雜性理論等教學(xué)內(nèi)容，作業(yè)量不大，難度較小，目的是鞏固課堂學(xué)習(xí)內(nèi)容。課堂研討是此次教學(xué)改革新增的考核內(nèi)容，通過(guò)對(duì)課堂研討考核指標(biāo)細(xì)化和設(shè)置，引導(dǎo)學(xué)生協(xié)作學(xué)習(xí)，培養(yǎng)良好的溝通能力，鼓勵(lì)學(xué)生發(fā)表不同見(jiàn)解，提高課程教學(xué)的達(dá)成度。主要考察小組任務(wù)分解是否合理，研討匯報(bào)時(shí)各部分成果展示銜接是否良好，演示制作是否認(rèn)真，是否采用了新的實(shí)現(xiàn)方法、總結(jié)建議，是否具有創(chuàng)新性以及對(duì)其他小組成果是否提出了有效見(jiàn)解等。課程論文作為本課程的綜合考核，要求學(xué)生結(jié)合自己的研究領(lǐng)域，完成某個(gè)問(wèn)題的分析、建模、算法設(shè)計(jì)和分析評(píng)價(jià)。根據(jù)課程論文中這幾個(gè)步驟的完成情況，對(duì)學(xué)生的基礎(chǔ)知識(shí)、應(yīng)用能力和創(chuàng)新能力進(jìn)行綜合評(píng)價(jià)。

3 結(jié)語(yǔ)

計(jì)算思維、創(chuàng)新思維能力是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)研究生所需具備的核心能力，建立相關(guān)的培養(yǎng)機(jī)制當(dāng)前已引起高校的廣泛重視。算法分析與復(fù)雜性理論課程作為能力培養(yǎng)的重要載體，在教學(xué)過(guò)程貫徹落實(shí)培養(yǎng)目標(biāo)意義重大。通過(guò)對(duì)算法分析與復(fù)雜性理論課程進(jìn)行案例化教學(xué)改革，將相關(guān)理論和實(shí)際應(yīng)用結(jié)合，圍繞解決實(shí)際應(yīng)用問(wèn)題建立教學(xué)體系，鼓勵(lì)學(xué)生主動(dòng)學(xué)習(xí)，激發(fā)學(xué)生學(xué)習(xí)積極性，形成教師與學(xué)生、學(xué)生與學(xué)生之間交流研討的教學(xué)氛圍。訓(xùn)練研究生面臨實(shí)際問(wèn)題時(shí)，主動(dòng)利用已有知識(shí)對(duì)問(wèn)題進(jìn)行合理分析和形式化，最后設(shè)計(jì)求解算法思維習(xí)慣和應(yīng)用能力。在教學(xué)過(guò)程中逐漸讓學(xué)生成為教學(xué)活動(dòng)的主體，教師結(jié)合具體問(wèn)題進(jìn)行知識(shí)講解，引導(dǎo)學(xué)生獨(dú)立思考，自主解決問(wèn)題，有意識(shí)地培養(yǎng)研究生計(jì)算思維能力和創(chuàng)新能力。算法分析與復(fù)雜性理論課程案例化教學(xué)改革具有很強(qiáng)的示范價(jià)值，未來(lái)將逐步推廣到其他課程，為計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)培養(yǎng)更多更高質(zhì)量的研究隊(duì)伍。