導(dǎo)語(yǔ)：算法設(shè)計(jì)與分析課程教學(xué)方法一文來(lái)源于網(wǎng)友上傳，不代表本站觀點(diǎn)，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

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

關(guān)鍵詞：算法設(shè)計(jì)與分析；程序設(shè)計(jì)競(jìng)賽；能力型課程；工程實(shí)踐；過(guò)程化考核

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

一、“以賽啟教”的“算法設(shè)計(jì)與分析

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

二、“以賽啟教”的“算法設(shè)計(jì)與分析（雙語(yǔ)）”課程教學(xué)的實(shí)踐

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

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

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

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

（三）完善課程考核評(píng)價(jià)體系

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

三、“以賽啟教”的“算法設(shè)計(jì)與分析

（雙語(yǔ)）”課程教學(xué)實(shí)踐的效果經(jīng)過(guò)一年多的探索，“以賽啟教”的“算法設(shè)計(jì)與分析（雙語(yǔ)）”課程教學(xué)實(shí)踐初見(jiàn)成效。

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

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

（二）課程教學(xué)反哺競(jìng)賽

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

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