算法設計與分析課程教學方法

導語：算法設計與分析課程教學方法一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

摘要：“算法設計與分析（雙語）”是北京林業大學計算機科學與技術專業的專業核心課程。根據課程的教學目標，提出“以賽啟教”的教學實踐思路，從教學內容、教學方法和考核方式３個方面加以實施。在教學內容方面，對國內外知名院校相關課程進行了調研分析，并參考了競賽常用算法，精選了教學內容；在教學方法方面，利用競賽平臺在線評判系統，在教學的每個環節都貫徹了“實踐最重要”的教學理念；在考核方式方面，結合競賽形式提出了一套有效的考核評價體系。“以賽啟教”的教學實踐促進“算法設計與分析（雙語）”課程完成從知識型向能力型教學的轉變，并反哺了競賽。

關鍵詞：算法設計與分析；程序設計競賽；能力型課程；工程實踐；過程化考核

在計算機科學與技術領域，算法至關重要［１］。正如經典巨著《ＴｈｅＡｒｔｏｆＣｏｍｐｕｔｅｒＰｒｏｇｒａｍ－ｍｉｎｇ》的作者、１９７４年圖靈獎獲得者ＤｏｎａｌｄＥＫｎｕｔｈ［２－３］所說“Ｍｙｆａｖｏｒｉｔｅｗａｙｔｏｄｅｓｃｒｉｂｅｃｏｍ－ｐｕｔｅｒｓｃｉｅｎｃｅｉｓｔｏｓａｙｔｈａｔｉｔｉｓｔｈｅｓｔｕｄｙｏｆａｌｇｏ－ｒｉｔｈｍｓ”（計算機科學就是算法的研究），而算法研究的核心就是算法設計與分析。北京林業大學計算機科學與技術專業在２０１９級本科人才培養方案中設置了“算法設計與分析（雙語）”專業核心課程，該課程強調夯實編程基礎，提升學生的專業能力和素養［２］，為各行各業輸送工程應用創新型人才［３］。

一、“以賽啟教”的“算法設計與分析

（雙語）”課程教學的思路近１０年來，北京林業大學每年都組織學生參加國際大學生程序設計競賽，這是一項已經舉辦５０余年的全球大學生頂級程序設計競賽，該賽事的核心是考察學生的算法水平。受競賽的啟發，“算法設計與分析（雙語）”課程組提出了在該課程教學中開展“以賽啟教”的教學構想。首先，充分考慮“算法設計與分析（雙語）”課程與先修課程“數據結構”的銜接，調研分析國內外知名院校相關課程教學內容的安排，精選教學內容，并增加競賽中出現頻率最高的算法內容。其次，鑒于競賽的形式是使用計算機編程解題，“算法設計與分析（雙語）”課程組在教學方法上注重實踐教學，在每個教學環節都始終貫徹“實踐最重要”的理念。最后，在實驗、期中考試和期末考試的評分標準上參考競賽中的排名方案，增設大作業考核。

二、“以賽啟教”的“算法設計與分析（雙語）”課程教學的實踐

（一）優化教學內容

北京林業大學“算法設計與分析（雙語）”課程組調研了國內外知名高等院校計算機專業該門課程的教學內容設置情況，這些高等院校包括２０２１年度ＱＳ全球大學計算機專業排名前三［４］的Ｍａｓｓａｃｈｕ－ｓｅｔｔｓＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ［５］、ＳｔａｎｆｏｒｄＵｎｉｖｅｒｓｉ－ｔｙ［６］、ＣａｒｎｅｇｉｅＭｅｌｌｏｎＵｎｉｖｅｒｓｉｔｙ［７］和國內的北京大學、北京航空航天大學和中山大學，見表１。同時，參考了競賽中出現最頻繁的算法，確定了適合北京林業大學計算機科學與技術專業本科生的“算法設計與分析（雙語）”課程教學內容，見表２。教學內容優化主要考慮了以下５點。①納入所有高等院校都會涉及的內容，這些也是“算法設計與分析（雙語）”課程最基本的內容，包括算法分析、分治、動態規劃、貪心和ＮＰ完備性等［８］；②增加其他在競賽中出現頻率很高的算法內容，包括并查集、線段樹和字符串算法（字典樹、ＡＣ自動機）［９－１０］；③對照“數據結構”課程，對教學內容進行排重，“數據結構”課程涉及的最小生成樹、排序和查找、二叉（平衡）查找樹和圖基礎算法內容，在“算法設計與分析（雙語）”課程教學中不再重復講授［１１］；④增加智能算法模擬退火內容，目的是讓學生對隨機算法有一個初步的認識；⑤刪除難度較高或者其他課程涉及的內容，比如網絡流、密碼學相關算法、博弈論、近似算法、計算幾何、快速傅里葉變換和遺傳算法等。

（二）采用注重理論聯系實踐的教學方法

“算法設計與分析（雙語）”課程的教學主要包括理論教學和實驗教學。為了對學生進行綜合性實踐訓練并提高學生的工程素養，“算法設計與分析（雙語）”課程組在每個教學環節都始終貫徹“實踐最重要”的教學理念。１．以問題為驅動的理論教學方法“算法設計與分析（雙語）”課程教學的一個普遍現象是重知識、輕能力，理論與實踐脫節，導致許多學生雖然掌握了算法的理論知識，但代碼量嚴重不足、寫程序非常生澀、編程求解問題時依然無從下手。為了打破這樣的現狀，“算法設計與分析（雙語）”課程組設計了以問題驅動的理論教學方法，見圖１。下面以動態規劃專題為例詳細介紹以問題驅動的理論教學方法的實施流程：首先，用比較簡單的尋寶問題（又名數塔問題，見圖２）作為引例展開思維挖掘，從最優子結構到重疊子問題到狀態遷移方程再到遞歸和遞推，逐步介紹動態規劃的核心思想。其次，在學生理解了這些思想之后，在課堂上提出若干道經典的動態規劃問題，包括嵌套盒子問題、硬幣問題、地鐵里的間諜、單向旅行商、０－１背包、最長上升子序列和最長公共子序列等。之后，帶領學生閱讀這些題目，分析問題并設計滿足題目要求的算法。最后，編程求解這些問題，使得學生能夠掌握這些經典動態規劃問題的解法。２．基于競賽的實驗教學方法在國際大學生程序設計競賽和中國大學生程序設計競賽中，參賽隊伍需要使用給定的電腦，在５個小時內編程求解１１～１３道題目，比賽過程中選手提交解題代碼到在線評判（ＯｎｌｉｎｅＪｕｄｇｅ，簡稱ＯＪ）系統，在線評判系統實時返回評判結果（包括ａｃｃｅｐｔ－ｅｄ，ｗｒｏｎｇａｎｓｗｅｒ，ｒｕｎｔｉｍｅｅｒｒｏｒ，ｔｉｍｅｌｉｍｉｔｅｘｃｅｅ－ｄｅｄ，ｍｅｍｏｒｙｌｉｍｉｔｅｘｃｅｅｄｅｄ等）。選手可以實時看見所有隊伍的排名，解題越多的隊伍排名越靠前，解題數相同時，解題用時越少排名越靠前。為了支撐北京林業大學程序設計競賽集訓隊的訓練，集訓隊在２０１０年建設了北京林業大學在線評判系統（ｗｗｗ．ｂｊｆｕａｃｍ．ｃｏｍ），該系統已經歷３次迭代更新。“算法設計與分析（雙語）”課程的實驗教學在該系統上開展。每次講完課程的理論知識之后，教師在系統上創建對應的專題實驗，專題實驗包括５～８道難度不等的題目。實驗開始后，學生在系統上提交代碼求解這些題目，實驗過程中學生能實時看見自己的解題排名（和競賽規則一樣，解出題目越多排名越靠前；當解題數相同時，用時越少排名越靠前）。實時排名能起到很好的激勵作用，激發學生探究進取的精神。此外，在線評判系統還集成了代碼查重功能，再結合人工查重，很大程度上避免了實驗抄襲現象。使用計算機編程解決問題要求代碼百分百精確，不精確的代碼不能通過在線評判系統的評判，這有助于培養學生縝密的邏輯思維和細致的觀察能力，讓學生感悟到程序設計的優美，促進學生養成良好的編程習慣。另外，教師還會在每次實驗結束后給出各大知名在線評判系統上和本次實驗專題知識點相近的題目編號，這些題目可以作為課后訓練和拓展使用，有助于學生對所學知識融會貫通舉一反三。３．綜合性工程實踐訓練方法“算法設計與分析（雙語）”課程教學的另一個問題是不能將知識串聯起來。為了進一步培養復合型、工程型和創新型人才，該課程增設了大作業，以訓練學生的綜合性工程實踐能力。為了增加趣味性，大作業一般為游戲類工程項目，比如“貪吃蛇”等。在大作業環節，教師首先給出用英語描述的大作業任務書和大作業報告模板；然后，學生按照任務書的要求，查閱中英文資料，分析、設計一系列算法解決工程問題，再編寫界面封裝算法，實現和用戶的交互，并把整個過程用文檔描述出來；最后，學生提交工程的源文件、用英語寫的說明文檔及大作業報告。

（三）完善課程考核評價體系

目前，國內算法課程的考核成績主要包括平時成績和期末考試成績。其中，平時成績占４０％，期末考試成績占６０％。期末考試一般為筆試，導致的結果往往是背得越好得分越高而不是編程越好得分越高。另外，期末考試成績占比過大，過程考核不足。為了使北京林業大學“算法設計與分析（雙語）”課程的考核結果能真正反映學生的編程水平，“算法設計與分析（雙語）”課程組完善了該課程考核評價體系，見表３。其中，期中考試和期末考試均為開卷考試，學生不需要死記硬背，而是要能夠運用學到的知識編程解決問題，這樣才能真正考核學生分析問題、設計算法以及編程實現算法的能力。表３中的實驗、期中考試和期末考試均在北京林業大學在線評判系統上進行，每位學生都能實時看到所有同學的解題情況和排名，真正做到了考核過程公平公正公開。在線評判系統考察的是學生的編程能力，因此考核結果能真實反映學生的編程水平。此外，除了分析和設計算法編程求解問題的考核，課程組還設置了大作業，這樣能更全面地考察學生利用算法知識開發工程項目的能力。

三、“以賽啟教”的“算法設計與分析

（雙語）”課程教學實踐的效果經過一年多的探索，“以賽啟教”的“算法設計與分析（雙語）”課程教學實踐初見成效。

（一）由知識型課程教學轉向能力型課程教學

通過貫徹“實踐最重要”的教學理念，在“算法設計與分析（雙語）”課程教學中，教師讓學生參與到每個教學環節，使學生掌握了所學算法的精髓并把算法應用到問題的求解中，提高了學生程序設計、算法設計與分析、邏輯推理、數學建模和工程實踐的能力。通過實施一套更注重編程實踐的過程化考核機制，使“背得越好得分越高”變成了“編程越好得分越高”，打破了課程重知識、輕能力的問題，促進了課程由知識型課程向能力型課程的轉變。圖３為北京林業大學２０２０—２０２１學年“算法設計與分析（雙語）”課程學生成績分布和做題數目的對應關系。可以看出，學生的成績和做題數目呈正比關系，做題數目直接反映了編程能力，這就印證了該課程的考核機制，即“編程越好得分越高”。經統計，平均每位學生在在線考評系統上做出的算法編程題（包括實驗題和課外練習題）數目為１１９道，較傳統教學模式有了很大提升，這說明考核機制能有效激勵學生的編程積極性。

（二）課程教學反哺競賽

通過“以賽啟教”的教學實踐，學生接受了基于競賽的實驗教學方法，學生在實驗中編寫程序，培養了對競賽的興趣，最終也反哺了競賽。近年來，北京林業大學參加國際大學生程序設計競賽、中國大學生程序設計競賽和團體程序設計天梯賽的學生人數明顯增加，也獲得了較好的成績。以２０２０—２０２１年為例，１７８名學生參加了上述３個程序設計競賽的校內初選，經過多輪選拔，５２名學生參加了正式比賽，共獲得國家級一等獎１次、國家級二等獎６次、國家級三等獎１９次和省部級二等獎３次。總之，“以賽啟教”的教學實踐有效提升了學生的算法設計與分析能力和編程能力，促進了課程教學由知識型課程向能力型課程的轉變。但和知識型課程的傳統教學模式相比，這種教學模式由于更加強調實踐，學生需要通過編程解決問題，這就要求學生具有一定的編程基礎。具體地說，學生需要在上課前預習教師提前發的課件，上課時認真聽講、參與討論，理解理論知識，掌握每道題目的解題思路，并在課后完成課上每道題目的代碼實現，這樣才能在實驗課上編程解出題目，學生也才能順利地通過考核。如果學生的編程訓練不夠，某個環節沒能跟上進度，那么學習該課程將會非常困難。針對這些問題，需要進一步強化課程的激勵導向，減少編程壓力帶給學生的懈怠情緒。為了打破“算法設計與分析（雙語）”課程重知識、輕能力的教學現狀，“算法設計與分析（雙語）”課程組提出了“以賽啟教”的教學實踐思路，激發了學生學習計算機領域專業知識與技能的興趣，培養了復合型、工程型和創新型專業人才。

作者：徐艷艷 李冬梅 陳志泊 單位：北京林業大學信息學院