啟發式思維驅動的研究生算法課程在線教學探索*

栗風永 畢忠勤

(上海電力大學計算機科學與技術學院，上海 201306)

0 引言

為應對新型冠狀病毒肺炎疫情，教育部提出“停課不停教、停課不停學”指導意見[1]，國內各個高校紛紛開展在線教學。作為碩士研究生的主干專業基礎課程，算法設計與分析(以下簡稱“算法課程”)不僅承載著算法基礎理論和經典算法設計的教學內容，同時也是培養和提升研究生科研思維能力的平臺[2]。

通過對算法課程的學習與研究，學生應具備以下兩方面能力：①掌握算法設計的主要思想，能夠對算法計算復雜性做出正確分析，同時結合經典的算法分析案例，理解算法的理論體系，并能夠利用現代分析方法對算法進行優化。②培養學生提出問題、分析問題、解決問題的能力，并將其融入到后續的科研工作中。因此，算法課程不僅要培養學生利用基礎算法理論解決實際問題的能力，同時要教學過程中進一步強化計算思維和創新意識，為后續科研工作奠定基礎。

1 教學內容

1.1 課程特點及存在的問題

作為計算機專業研究生的一門專業基礎課，算法課程在教學過程中需要注意以下幾個問題。首先，學生需要具備良好的數學和程序設計基礎，比如需要先修離散數學、程序設計基礎、數據結構等課程，但部分學生的先修課程基礎不同，因此一些內容還需要在教學過程中進行簡單介紹，如離散數學中的邏輯分析和數據結構中的典型樹形結構和鏈表等。其次，選修本門課程的研究生在本科階段并非全部來自計算機專業，還包括其他如通信、自動化、數學等跨專業學生，如何組織教學內容使學生的整體接受度達到最大，其難度顯而易見。最后，也是最重要的一點，受當前疫情影響，在線課程授課方式相比線下授課在師生互動方面有所減弱，而算法課程則需要學生結合典型算法的分析思想對部分算法實例進行實時互動反饋，如何在線上充分調動學生的互動積極性，這也是當前算法課程在線教學的一個難點。

1.2 應對在線教學的課程內容梳理

在綜合分析了以上問題的基礎上，筆者重新梳理了算法設計與分析課程的內容，并將其分為核心內容和拓展內容兩部分，以適應不同基礎的學生。相對于本科教學，研究生算法教學更側重于復雜性分析，以及針對復雜性的優化過程[3]，因此核心內容主要涵蓋了經典算法的設計思想和分析方法，如分治策略、動態規劃、貪心算法、回溯法、分支限界法以及隨機化算法等，這部分內容要求所有學生能夠針對每一種典型算法描述出基本的設計思想，熟悉復雜度分析過程，寫出復雜度遞推方程，并進行推導證明。拓展內容則是在每一種經典算法基礎上，針對不同算法案例進行實例分析，并提出可能改進的解決方案。由于每一種典型算法都包括了很多應用實例，每一種實例有不同的理解難度，筆者根據難易程度將眾多應用實例分成難、中、易三個等級，學生根據自己的基礎選擇不同案例進行線下拓展學習，進一步完成相關的實驗任務。整體的教學內容框架如圖1所示。

圖1 適應在線教學的課程內容梳理

1.3 課程采用的教材

受疫情影響，高校的大部分課程都采用在線教學形式。由于在線教學容易受到網絡環境的影響，在考慮在線授課特點的基礎上，結合算法課程的知識框架和教學內容，課程采用屈婉玲等編著的《算法設計與分析》(第2版)作為主講教材[4]。該教材除了具備完備的課程教學體系外，在中國大學慕課(MOOC)平臺上也發布了較為完善的線上教學視頻供學生在線學習[5]。輔助教材采用王曉東編著的《計算機算法設計與分析》(第4版)[6]，該教材也屬于國家精品課程教材。兩部教材都較為全面地涉及了經典算法與對應的實例分析，同時涵蓋了部分算法領域的熱點研究內容，比較適合作為研究生課程的配套教材。

2 教學過程

2.1 教學平臺

為了應對在線教學，算法設計與分析課程在疫情防控期間利用中國大學慕課(MOOC)平臺開展在線教學。中國大學慕課平臺提供三種課程授課方式：獨立SPOC(Small Private Online Course，小規模限制性在線課程)、異步SPOC、同步SPOC。結合線上教學的教材資料及精品課程開放情況，筆者采用異步SPOC模式實施在線教學，它可以根據本校實際教學情況刪改原有內容和新增補充內容，教學過程中的作業批改答疑等由任課教師提供，可以很好地構建師生的互動交流。同時，課程利用在線會議系統(如騰訊會議)組織算法課程的研討式教學，開展實時在線研討。

2.2 融入啟發式思維的在線教學過程

作為一門計算機專業的研究生基礎課程，算法設計與分析更多承擔了培養學生計算思維能力的重任，同時還要讓學生在算法教學過程中提升分析問題的能力。計算思維能力體現在針對具體問題的描述、建模、求解的科學思維方式，而分析問題的能力則主要體現在對問題深入思考的靈敏嗅覺。筆者通過總結線下課程教學經驗，將啟發式思維滲透到算法課堂教學中，在講解算法的設計思想和算法分析過程中，注重利用啟發式分析方法引導學生思考如何對模型進一步優化。針對一個具體問題，分析當前解決方案，考慮其中存在的問題，進一步思考如何解決該問題，最終找出應對方法。如此反復，直到學生掌握這種思考模式并能夠將其熟練應用到其他問題分析中。以算法課程中分治策略的整數乘法為例，啟發式的教學過程如表1所示。經過反復的啟發式分析訓練，學生的問題建模和分析能力得到較為明顯的提升，具備了針對問題進一步優化的靈敏嗅覺。

2.3 圍繞典型算法案例的研討式在線教學

在教學過程中，筆者利用騰訊會議系統組織研討式教學，進一步加深學生對典型算法案例的理解并提升團隊協作能力。研討內容以經典算法實例為主，通過實時在線講解和程序演示，讓學生就不同算法解決同一問題進行分析對比。小組研討過程中注意區分不同程度的學生，根據學生的能力安排小組任務。以三人小組研討0-1背包問題為例，讓學生思考分別使用動態規劃和回溯法得到不同的解決方案，同時分析不同方案的異同點。研討過程中，學生A負責總體講解問題模型、算法設計、核心代碼以及復雜性分析。學生B負責算法的程序實現，并實際測試運行時間。學生C則圍繞0-1背包問題檢索近年相關的科研論文，并就該主題做研究進展綜述。研討式教學結構如表2所示。騰訊會議系統可支持多人同時在線討論，相對于線下教學的小組研討，線上小組研討可以讓小組的每一位成員實時參與互動，激發學生創新能力的同時也培養了學生的團隊協作能力。

表2 0-1背包問題的小組研討式在線教學案例

2.4 實驗教學

在拓展教學內容的基礎上，圍繞每一個經典算法布置多個不同的算法實例，并將其分為難、中、易三個等級，實驗教學要求學生根據自身能力自由選擇不同難度的算法實例編程實現，并給出不同的參考和評價標準。實驗過程主要是線下完成，以學生為主，教師在線輔助指導，并對程序設計過程中的問題做啟發性提示，根據不同層次的實驗內容對學生進行個性化培養。

3 課程考核

綜合在線課程考核標準，算法課程的理論考核占總成績的60%，研討式教學過程小組表現占20%，在線答疑和討論參與度占10%，實驗教學占10%。由于線上教學難以全面掌握所有學生的課堂參與度，在未來的教學環節中將調整課堂參與度的分數占比，建立更加科學的考核體系。此外，小組研討過程中每一位成員都有自己的任務，同時還需要相互配合完成小組的團隊任務，且可以隨時參與展示自己的想法和完成的內容，整體上這一環節更能體現個人能力和團隊協作能力，因此考核分值占比較大。

4 結束語

結合在線教學特點，筆者對算法設計與分析課程教學模式進行了創新設計。針對不同程度學生的特點重新梳理了課程的重點內容和拓展內容，并對具體的教學方式進行設計，融入啟發式教學模式，逐步引導學生形成提出問題、分析問題、解決問題的思維方式。同時將研討式教學與線上教學有機融合，根據不同研究生的能力定制個性化教學任務目標，培養學生計算思維的同時，也顯著提升了學生自主分析和解決實際問題的能力。