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

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

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

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

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

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

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

（一）優(yōu)化教學內(nèi)容

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

（二）采用注重理論聯(lián)系實踐的教學方法

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

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

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

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

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

（一）由知識型課程教學轉(zhuǎn)向能力型課程教學

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

（二）課程教學反哺競賽

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

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