算法分析與復雜性理論課程案例化教學改革

田衛新

（三峽大學 計算機與信息學院，湖北 宜昌 443002）

0 引言

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

近年來隨著人工智能、大數據技術的迅猛發展，基于數據集的學習算法展現了巨大的優性，越來越受到重視。相比之下，傳統經典算法的應用領域有逐漸退化的趨勢。為了適應這種新的變化，并且在教學中展現算法設計技術從傳統經典算法向智能、學習型算法發展演變的脈絡關系，結合案例教學方法，借鑒已有教學案例建設的成功經驗[2-4]，對算法分析與復雜度理論課程進行了案例教學設計。在案例教學基礎上，增強研討環節，要求學生在課前進行分組準備，在課堂上圍繞案例算法進行討論，從而將課堂與課外學習有機結合，改變原來單一課堂講授的教學模式，提高課堂互動性，提高教學質量。

1 案例設計思路

1）案例設計成體系。

選擇案例時，根據算法設計技術的發展邏輯，與本科階段課程具有一定的銜接，由淺入深、循序漸進介紹基本算法思想，最優化問題及求解算法，基于數據集學習算法的基礎、發展過程及核心思想，相應產生了算法分析評價方法的改進，使學生對算法領域有整體把握，達到以案例學習促進算法分析、以分析促進提高算法設計水平的目標。

2）以培養創新思維為目標。

算法分析與復雜性理論課程的主要目的是通過對算法分析評價技術的學習，培養研究生算法設計能力、程序實現與計算思維能力。算法作為計算機科學與技術專業的核心對象，集中體現了原創者的創新思維。作為計算機科學與技術專業研究生，圍繞算法的創新思維能力是在校期間需要著力培養的重要內容。算法創新思維能力的培養過程不能脫離實際應用獨立存在，需要結合實際算法設計案例，經過學習、理解、掌握到精通的過程后，由學生自己總結領會才會最終習得。因此，在算法相關的案例教學中，必須強化學生主動參與，提供實踐機會。

3）以課堂交互為手段。

良好的課堂交互要求教師和學生都要精心做好課堂準備，在圍繞案例展開研討時，學生需要預先對分配的課題有較深入的理解，查閱資料并完成設計及講解準備，對學生課下的學習提出了較高的要求。教師在課堂教學的討論環節，需要發揮引導作用，控制討論節奏，充分調動學生的學習積極性，增大開放式問題的討論范圍，鼓勵創新性思維，并做好分析和總結，提高教學效果。

4）相應的考核辦法。

為了促進課程案例化教學的成功實施，需要設計相應的課程考核方法，對學習效果和過程進行評價，以適應案例教學各環節如課前準備情況、課堂參與度等方面的具體要求。

2 案例化教學實施

1）教學目標。

算法分析與復雜性理論課程目標是掌握算法評價的基本理論，掌握算法分析的基本方法，理解算法復雜性理論體系并熟悉復雜性理論的基本結論。理解經典算法設計思想，具備應用經典算法解決問題的能力；了解最優化問題及其分類，熟悉常見最優化問題的求解算法；理解機器學習與最優化問題的聯系；掌握常見的分類及聚類算法。通過引入算法分析和復雜性理論的實際應用場景，提高學生理論與實踐相結合的能力；通過對案例的學習，提高算法分析與設計能力。案例化教學改革的目的是圍繞上述課程目標，建立以學習為中心、以學生為主體、以教師為主導，建立促進學生發展核心素養和培養應用能力的課堂教學模式。

2）教學內容及安排。

算法分析與復雜性理論教學內容與安排見表1。

表1 算法分析與復雜性理論教學內容與安排

3）教學組織。

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

課堂講授是最為傳統的教學模式，具有目標明確，教學效率高等優點。算法分析和復雜性理論課程內容中的算法評價、算法分析的基本方法、數學基礎、經典算法設計思想、最優化問題及求解、機器學習問題的形式化及求解、復雜性理論等，需要學生建立相關領域的知識體系和術語系統，是課程屬于要求“知”“懂”的內容，對該部分內容采用課堂講授的方式，同時對理論講授中涉及的重要、復雜的知識點進行梳理、總結，歸納成疑難問題組織課堂討論，幫助厘清概念、理解原理并對容易混淆的方程形式及判別條件等進行區分辨識。

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

4）考核體系。

為鼓勵學生對課程內容及案例展開深入研究，通過交流研討掌握算法分析設計理論及應用，同時對教學過程進行反饋優化，對課程評價采用了多元化的綜合評價法。多元化綜合評價法綜合考核學生的知識點掌握情況、應用能力、創新能力、協作能力、溝通能力等方面，具體見表2。

表2 課程考核體系

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

3 結語

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