基于MOOC的競(jìng)賽機(jī)制實(shí)驗(yàn)教學(xué)改革

葛芳，蔡紹峰

摘 要：算法設(shè)計(jì)與分析實(shí)驗(yàn)課是培養(yǎng)學(xué)生動(dòng)手能力的重要手段。文章首先分析了實(shí)驗(yàn)教學(xué)中的問(wèn)題，然后提出引入計(jì)算機(jī)程序類競(jìng)賽激勵(lì)機(jī)制，同時(shí)改革考核方式，提高學(xué)生根據(jù)問(wèn)題設(shè)計(jì)算法、優(yōu)化算法的能力，旨在提高教學(xué)質(zhì)量，為培養(yǎng)工程化應(yīng)用型人才提供技術(shù)支撐。

關(guān)鍵詞：算法設(shè)計(jì)與分析；課程教學(xué)；競(jìng)賽

中圖分類號(hào)：G642 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：2096-000X（2017）18-0128-03

Abstract： The experimental lesson of algorithm design and analysis is the important means to improving students' manipulative ability. This paper proposes a method that adds programming contest incentive mechanism to the experimental course， and meanwhile puts forwards an examination mode intended to improve students' initiative and creative learning， aiming to improve the quality of teaching and provide environmental support for cultivating engineering talents.

Keywords： algorithm design and analysis； course teaching； competition

引言

《算法分析與設(shè)計(jì)》是計(jì)算機(jī)相關(guān)專業(yè)的專業(yè)進(jìn)階課，該課程可以鍛煉學(xué)生設(shè)計(jì)實(shí)際問(wèn)題的解題思路，此外，還能夠進(jìn)一步幫助學(xué)生優(yōu)化解題思路，是專業(yè)核心課程[1]。同時(shí)，該課程具有非常強(qiáng)的應(yīng)用性，是程序編寫、數(shù)據(jù)結(jié)構(gòu)和軟件設(shè)計(jì)的中間課程[2]。編寫程序，不僅需要程序代碼編寫能力，更需要良好的數(shù)據(jù)結(jié)構(gòu)組織能力，高效算法的設(shè)計(jì)能力。該實(shí)驗(yàn)課中不但要求學(xué)生掌握經(jīng)典的算法設(shè)計(jì)與實(shí)現(xiàn)，更要求學(xué)生在掌握基本算法的基礎(chǔ)上，針對(duì)實(shí)際問(wèn)題，優(yōu)化算法，進(jìn)而分析算法的時(shí)空復(fù)雜度。為學(xué)生從事計(jì)算機(jī)軟件開(kāi)發(fā)、算法設(shè)計(jì)等工作提供扎實(shí)的理論和實(shí)踐基礎(chǔ)。

在“工程化”的人才培養(yǎng)教育背景下，本文以“算法設(shè)計(jì)與分析”為例，探究一種將混合式教育、程序設(shè)計(jì)競(jìng)賽、及考核方式改革等方面相結(jié)合的新型教學(xué)模式。該模式汲取各自的優(yōu)勢(shì)，在混合式教學(xué)模式下，引入程序設(shè)計(jì)大賽等賽事的參賽激勵(lì)機(jī)制，旨在提高教學(xué)質(zhì)量，為培養(yǎng)工程化應(yīng)用型人才提供環(huán)境支撐。

一、實(shí)驗(yàn)課程改革必要性

（一）實(shí)驗(yàn)?zāi)繕?biāo)

在實(shí)驗(yàn)課時(shí)教學(xué)中，學(xué)生在老師的引導(dǎo)下，將課程中的經(jīng)典算法依次還原，學(xué)生可以使用C、C++，Java或C#等編程語(yǔ)言。舉一反三，教師提出相似實(shí)際問(wèn)題，要求學(xué)生在算法的基礎(chǔ)上，根據(jù)實(shí)際問(wèn)題，修改、優(yōu)化算法。通過(guò)不同數(shù)據(jù)的輸入，驗(yàn)證算法的魯棒性。分別分析經(jīng)典算法與優(yōu)化后算法的時(shí)空復(fù)雜度。教師根據(jù)學(xué)生完成的情況，分別評(píng)價(jià)算法修改的合理性。

（二）存在問(wèn)題

1. 在教學(xué)過(guò)中，教師一般會(huì)講解較為經(jīng)典的算法，如貪心算法、分治法、動(dòng)態(tài)規(guī)劃算法、搜索法等，每種算法的講解均需要較多的課程，學(xué)生在相對(duì)較短的時(shí)間內(nèi)被灌輸較多較難理解的內(nèi)容，這往往導(dǎo)致學(xué)生未經(jīng)過(guò)消化和理解，從而導(dǎo)致較難按要求編程實(shí)現(xiàn)相應(yīng)的算法。

2. 在以往的實(shí)驗(yàn)課中僅僅要求學(xué)生還原或驗(yàn)證已有實(shí)驗(yàn)，學(xué)生缺少創(chuàng)造性學(xué)習(xí)的機(jī)會(huì)，并且整個(gè)實(shí)驗(yàn)過(guò)程枯燥無(wú)味。學(xué)生往往會(huì)出現(xiàn)不愿意去做，或者直接拷貝其他同學(xué)已完成的代碼，這便失去了實(shí)驗(yàn)課的目的。

3. 算法設(shè)計(jì)與分析作為與應(yīng)用實(shí)踐密切相關(guān)的課程，學(xué)生應(yīng)該能夠通過(guò)這門課程了解到學(xué)習(xí)的知識(shí)能有哪些應(yīng)用，能解決哪類實(shí)際問(wèn)題。如若將理論與實(shí)踐相分離，大部分學(xué)生會(huì)認(rèn)為學(xué)習(xí)算法無(wú)用，從而便逐漸失去學(xué)習(xí)的興趣。

二、改革措施

（一）引入競(jìng)賽

程序設(shè)計(jì)類競(jìng)賽對(duì)學(xué)生的智力具有相當(dāng)?shù)奶魬?zhàn)性，有助于促進(jìn)學(xué)生學(xué)以致用，使用學(xué)習(xí)的基礎(chǔ)算法理論去解決實(shí)際問(wèn)題，并且在團(tuán)隊(duì)合作的前提下，創(chuàng)造性地考慮和解決問(wèn)題。參與此類競(jìng)賽不僅能夠增加學(xué)生在有限時(shí)間內(nèi)的編程經(jīng)歷，為從事該方面工作打下基礎(chǔ)，此外良好的學(xué)習(xí)風(fēng)氣能夠促進(jìn)整個(gè)學(xué)校形成更好的校風(fēng)。

近些年，計(jì)算機(jī)程序編寫競(jìng)賽越來(lái)越多，如ACM-ICPC（ACM International Collegiate Programming Contest）[3]，百度之星，安徽省“合財(cái)杯”大學(xué)生程序設(shè)計(jì)大賽[4]，google挑戰(zhàn)賽等，詳細(xì)信息見(jiàn)表1。

該類競(jìng)賽綜合考察在校大學(xué)生的分析實(shí)際問(wèn)題，針對(duì)問(wèn)題設(shè)計(jì)算法，并編程實(shí)現(xiàn)。通常需要使用一種編程語(yǔ)言，如C、C++、Java或Pascal，在幾個(gè)小時(shí)內(nèi)，綜合運(yùn)用數(shù)據(jù)結(jié)構(gòu)、組合數(shù)學(xué)、概率論、計(jì)算幾何、圖論、人工智能、操作系統(tǒng)、算法設(shè)計(jì)與分析、計(jì)算機(jī)圖形學(xué)、數(shù)理邏輯等方面的知識(shí)，編程實(shí)現(xiàn)搜索、字符串處理、貪心算法、分治法、動(dòng)態(tài)規(guī)劃算法、幾何等類問(wèn)題。在該模式下，學(xué)生用所學(xué)算法解決問(wèn)題的意識(shí)和能力得到提升。

（二）MOOC教學(xué)資源

MOOC（Massive Open Online Courses）[5]突破了大學(xué)學(xué)歷、區(qū)域的限制，對(duì)傳統(tǒng)教育的人才培養(yǎng)模式和教學(xué)方式將被迫改革。此間，國(guó)內(nèi)外許多從事網(wǎng)絡(luò)在線教育和遠(yuǎn)程教育培訓(xùn)的專家學(xué)者們，一直都在尋求一種新的教育模式用以適應(yīng)MOOC的到來(lái)。

目前，大多數(shù)高等院校都存在師資匱乏、大班教學(xué)質(zhì)量不高、無(wú)法滿足學(xué)生的個(gè)性化需求以及學(xué)習(xí)受時(shí)間和空間限制等問(wèn)題。以MOOC發(fā)展為契機(jī)，國(guó)內(nèi)高等教育需要加快教學(xué)和管理的根本改革，以積極的姿態(tài)加入此場(chǎng)改革中，化危為機(jī)。有學(xué)者認(rèn)為，實(shí)體大學(xué)急需要解決資源共享和學(xué)習(xí)模式兩方面的問(wèn)題。通過(guò)MOOC可以共享全世界的優(yōu)質(zhì)課程資源，而大學(xué)需要思考的是：如何利用此模式，資源如何與傳統(tǒng)教育教學(xué)模式結(jié)合。因此，思考如何改變傳統(tǒng)教學(xué)方法，更新教育教學(xué)理念。

（三）考核方式

通常情況下，該課程的考核成績(jī)?yōu)椋浩谀┛荚?平時(shí)成績(jī)，比列通常為7：3，且一般情況下，平時(shí)成績(jī)：上課考勤+作業(yè)+實(shí)驗(yàn)報(bào)告成績(jī)，很難考察學(xué)生對(duì)算法改進(jìn)的思想創(chuàng)新性，故將平時(shí)成績(jī)部分的分值調(diào)整如表2所示。鼓勵(lì)學(xué)生積極參加計(jì)算機(jī)程序編寫類競(jìng)賽，增加程序設(shè)計(jì)的經(jīng)驗(yàn)。

三、實(shí)驗(yàn)課程改革方案

該課程的實(shí)驗(yàn)課時(shí)較少，因此在不增加課時(shí)的情況下，如何最大限度地利用現(xiàn)有課時(shí)，使學(xué)生在有限的課時(shí)內(nèi)學(xué)到最多的知識(shí)，這將是具有挑戰(zhàn)性的問(wèn)題。

1. 在所有實(shí)驗(yàn)課開(kāi)始前，盡量多地收集各類程序設(shè)計(jì)類競(jìng)賽的題目，并歸納總結(jié)，將考察的知識(shí)點(diǎn)相同或類似的題目歸為一類，并對(duì)應(yīng)到相應(yīng)的章節(jié)。

2. 每次實(shí)驗(yàn)課開(kāi)始前，教師將事前準(zhǔn)備好的題目展示給學(xué)生，讓其先思考題目所考察的知識(shí)點(diǎn)，并對(duì)應(yīng)到相應(yīng)的算法中。

3. 針對(duì)競(jìng)賽題目，根據(jù)已學(xué)算法基礎(chǔ)，設(shè)計(jì)算法，并根據(jù)輸入和輸出數(shù)據(jù)，分析算法的正確性和算法的健壯性。

4. 教師引導(dǎo)學(xué)生思考針對(duì)問(wèn)題，算法有無(wú)改進(jìn)措施，若有，編程實(shí)現(xiàn)，并驗(yàn)證改進(jìn)算法的正確性，進(jìn)而優(yōu)化問(wèn)題解決方式。

5. 在實(shí)驗(yàn)過(guò)程的任何環(huán)節(jié)，學(xué)生均可以通過(guò)MOOC課程群增加自身對(duì)算法的掌握程度，及時(shí)了解所學(xué)算法的應(yīng)用和改進(jìn)算法。

6. 教師在授課過(guò)程中，密切關(guān)注程序設(shè)計(jì)類競(jìng)賽的比賽時(shí)間，并組織學(xué)生積極備戰(zhàn)，最大限度幫助同學(xué)們將所學(xué)理論知識(shí)應(yīng)用于實(shí)踐。

四、結(jié)束語(yǔ)

在“工程化”人才培養(yǎng)教育背景下，本文嘗試著在MOOC

教學(xué)環(huán)境下，引入程序設(shè)計(jì)競(jìng)賽激勵(lì)機(jī)制，并將競(jìng)賽結(jié)果作為期末考核的組成部分，提高學(xué)生根據(jù)實(shí)際問(wèn)題，分析問(wèn)題、設(shè)計(jì)算法、優(yōu)化算法的能力，為培養(yǎng)工程化應(yīng)用型人才提供技術(shù)支撐。

參考文獻(xiàn)：

[1]趙曉麗.應(yīng)用型本科院?！端惴ㄔO(shè)計(jì)與分析》課程實(shí)踐教學(xué)改革研究[J].長(zhǎng)治學(xué)院學(xué)報(bào)，2016，33（2）：72-74.

[2]林 ，戴波.項(xiàng)目驅(qū)動(dòng)型算法設(shè)計(jì)與分析課程教學(xué)方法[J].計(jì)算機(jī)教育，2014（9）.

[3]Zhao L. Based on of ACM/ICPC Reform and Discussion on the Teaching Reform of the Program Design[J].Computer Knowledge & Technology，2015.

[4]戚爽.以大學(xué)生程序設(shè)計(jì)大賽為依托的創(chuàng)新人才培養(yǎng)模式研究[J].吉林省教育學(xué)院學(xué)報(bào)旬刊，2014，30（11）：78-79.

[5]常莎莎.MOOC的發(fā)展及其對(duì)高等教育的影響[J].教育：文摘版， 2015（9）：00289-00290.

[6]謝海燕.引進(jìn)MOOC對(duì)獨(dú)立學(xué)院人才培養(yǎng)質(zhì)量的提升[J].高教學(xué)刊，2015（09）：66-67.