基于ACM—ICPC模式的算法分析與設(shè)計(jì)課程的建設(shè)與實(shí)踐

劉曉璐

摘 要：針對算法分析與設(shè)計(jì)課程的教學(xué)實(shí)際，文章分析了該課程教學(xué)模式的局限性和傳統(tǒng)的實(shí)踐教學(xué)中存在的問題，提出將ACM-ICPC競賽模式引入該課程教學(xué)的觀點(diǎn)，開發(fā)了一個基于ACM-ICPC模式的程序測評系統(tǒng)，并應(yīng)用在算法分析與設(shè)計(jì)課程的實(shí)踐教學(xué)中，取得了良好的教學(xué)效果。

關(guān)鍵詞：ACM-ICPC；算法分析與設(shè)計(jì)；實(shí)踐教學(xué)

中圖分類號：G642 文獻(xiàn)標(biāo)志碼：B 文章編號：1673-8454（2015）10-0065-03

一、引言

算法分析與設(shè)計(jì)是面向設(shè)計(jì)的計(jì)算機(jī)專業(yè)核心課程，主要通過對經(jīng)典算法的學(xué)習(xí)和研究，使學(xué)生掌握算法的設(shè)計(jì)策略和算法復(fù)雜度的分析方法，培養(yǎng)學(xué)生分析和解決實(shí)際問題的能力，為開發(fā)高效的軟件系統(tǒng)奠定了堅(jiān)實(shí)的基礎(chǔ)。該課程教學(xué)內(nèi)容繁多，涉及的知識面很廣，主要內(nèi)容包括算法分析方法、遞歸算法、分治算法、貪心算法、動態(tài)規(guī)劃、回溯算法、分支限界、近似算法、概率算法等經(jīng)典的算法，覆蓋了多項(xiàng)式、數(shù)論、矩陣、集合、圖論、幾何、模式匹配等數(shù)值和非數(shù)值計(jì)算問題。

目前，各高校該課程分配的課時普遍較少，教學(xué)方法也都是以講解為主，即使設(shè)置了實(shí)驗(yàn)課，在實(shí)踐環(huán)節(jié)通常也只是一味地對算法進(jìn)行驗(yàn)證，很少考慮到算法的運(yùn)行效率分析、測試數(shù)據(jù)的規(guī)模以及實(shí)際的應(yīng)用場景。學(xué)生對算法的學(xué)習(xí)主要以理解和記憶為主，缺乏對知識的重構(gòu)和對算法的靈活運(yùn)用，遇到實(shí)際問題便無從下手。而且，在傳統(tǒng)實(shí)踐教學(xué)中，學(xué)生抄襲代碼的情況嚴(yán)重，不能有效提高學(xué)生的實(shí)踐能力，無法體現(xiàn)實(shí)踐教學(xué)的真正作用。在這種教學(xué)模式下，學(xué)生缺乏對實(shí)際問題進(jìn)行抽象和分析的能力，思維創(chuàng)新和實(shí)踐能力難以得到有效提高。本文結(jié)合我校實(shí)際教學(xué)情況，將ACM-ICPC競賽模式與算法分析與設(shè)計(jì)課程的建設(shè)相結(jié)合，達(dá)到了良好的教學(xué)效果。

二、課程現(xiàn)狀

算法分析與設(shè)計(jì)課程的建設(shè)在我校起步較晚，我校從2010年開始招收計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科學(xué)生，從2012年開始為計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)生開設(shè)算法分析與設(shè)計(jì)課程。第一屆課程只有理論課，學(xué)生缺少實(shí)踐機(jī)會。該課程的開設(shè)是面向計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)大三的學(xué)生，學(xué)生在學(xué)習(xí)該課程之前，已經(jīng)學(xué)習(xí)了C/C++程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、Java程序設(shè)計(jì)、高等數(shù)學(xué)和離散數(shù)學(xué)等課程，但是由于學(xué)生欠缺良好的計(jì)算思維，邏輯分析能力相對不足，編程實(shí)踐能力仍然比較弱，學(xué)生在學(xué)習(xí)該課程時倍感吃力。

目前，我校在算法分析與設(shè)計(jì)課程信息化建設(shè)方面有許多不足，主要體現(xiàn)在以下幾點(diǎn)：

（1）課程之間的聯(lián)系不夠緊密

算法分析與設(shè)計(jì)課程與其他課程的關(guān)系是很密切的，如數(shù)據(jù)結(jié)構(gòu)，它們之間相互作用，從而提高計(jì)算機(jī)專業(yè)學(xué)生的實(shí)踐能力，為學(xué)院培養(yǎng)高素質(zhì)的應(yīng)用型人才。由于這些課程的前后都沒有很好地銜接，課程之間的重點(diǎn)和難點(diǎn)沒有對應(yīng)上，所以學(xué)生在上算法分析與設(shè)計(jì)課程時需要重新復(fù)習(xí)之前所學(xué)的課程，從而增加了學(xué)生學(xué)習(xí)的工作量。

（2）教學(xué)資源不足

當(dāng)前課程并沒有信息化系統(tǒng)的支持。學(xué)生只能通過網(wǎng)絡(luò)搜索所需的資源，獲取教師的PPT也只能通過教師，教學(xué)資源沒有實(shí)現(xiàn)整合和共享。

（3）編程競賽平臺不多

程序設(shè)計(jì)能力的提升需要學(xué)生多思考多編程，而這方面實(shí)踐能力的獲取最有效的方式就是競賽活動。在參加或舉辦程序設(shè)計(jì)類競賽方面，學(xué)生只參與了國內(nèi)的“藍(lán)橋杯”這一個程序設(shè)計(jì)類競賽，學(xué)院內(nèi)部并沒有開展此類競賽活動。

三、ACM-ICPC模式下的課程建設(shè)

1.ACM-ICPC在課程中的作用

ACM國際大學(xué)生程序設(shè)計(jì)競賽（ACM-ICPC）是由美國計(jì)算機(jī)協(xié)會（ACM）主辦的，是一項(xiàng)旨在展示大學(xué)生創(chuàng)新能力、團(tuán)隊(duì)精神和在壓力下編寫程序、分析和解決問題能力的年度競賽。經(jīng)過40多年的發(fā)展，ACM-ICPC已經(jīng)發(fā)展成為最具影響力的大學(xué)生計(jì)算機(jī)競賽。競賽時間為5個小時，重點(diǎn)考察選手的算法和程序設(shè)計(jì)能力。選手通過網(wǎng)絡(luò)提交程序，評委負(fù)責(zé)將結(jié)果（正確或出錯的類型）通過網(wǎng)絡(luò)盡快返回給選手。

將ACM-ICPC競賽模式引入算法分析與設(shè)計(jì)的教學(xué)中，可以激發(fā)學(xué)生的主動學(xué)習(xí)積極性，鼓勵學(xué)生勤思考、多實(shí)踐，相對于傳統(tǒng)的實(shí)踐教學(xué)具有以下幾方面的優(yōu)勢：

（1）在網(wǎng)上進(jìn)行實(shí)踐教學(xué)，沒有時間和空間的局限性。教師可以在測評系統(tǒng)中對同一個實(shí)驗(yàn)項(xiàng)目布置多個難度各異的題目，學(xué)生可以根據(jù)自己的掌握情況，從易到難選擇合適的時間完成訓(xùn)練題目。學(xué)生完成編程提交代碼后可以立刻得到評測結(jié)果，這樣可以激發(fā)學(xué)生的學(xué)習(xí)熱情。教師也可以分析學(xué)生提交程序是否正確或錯誤，并進(jìn)行針對性的講解。

（2）對創(chuàng)造校園的學(xué)術(shù)交流氛圍有良好的促進(jìn)作用。學(xué)生在課余時間通過在網(wǎng)上提交自己編寫的程序源代碼，自主進(jìn)行算法和程序的交流，有利于培養(yǎng)學(xué)生的學(xué)術(shù)修養(yǎng)，實(shí)現(xiàn)學(xué)生與教師、學(xué)生與學(xué)生之間的交流和互動。

（3）減輕教師實(shí)踐教學(xué)時的指導(dǎo)負(fù)擔(dān)。傳統(tǒng)的實(shí)踐教學(xué)在機(jī)房進(jìn)行，教師需要在整個機(jī)房進(jìn)行巡視，為有疑問的同學(xué)進(jìn)行解答。這讓教師在實(shí)踐教學(xué)中的指導(dǎo)負(fù)擔(dān)非常繁重，教師的指導(dǎo)范圍也不能全面覆蓋整個班級，在一定程度上打擊了學(xué)生的積極性。而ACM-ICPC競賽模式的在線測評系統(tǒng)可以對學(xué)生提交的作業(yè)進(jìn)行評測，大大減輕了教師的負(fù)擔(dān)。

2.測評系統(tǒng)的設(shè)計(jì)與開發(fā)

我們將基于ACM-ICPC競賽模式的在線測評技術(shù)引入算法分析與設(shè)計(jì)課程的教學(xué)中，開發(fā)了一個程序在線測評系統(tǒng)。該系統(tǒng)基于Java EE，是一個程序在線評判、程序設(shè)計(jì)競賽和交流的平臺，可不斷擴(kuò)展題庫供學(xué)生進(jìn)行程序設(shè)計(jì)練習(xí)，系統(tǒng)自動對提交的程序源代碼進(jìn)行編譯、運(yùn)行并評判程序的正確性。系統(tǒng)可供課程日常訓(xùn)練和網(wǎng)上實(shí)時競賽使用，也具備站內(nèi)交流和站內(nèi)全文檢索功能?？紤]到后期改進(jìn)和后續(xù)開發(fā)的需要，系統(tǒng)的開發(fā)采用的是目前主流的MVC架構(gòu)，使用的是Struts框架。系統(tǒng)有兩個版本的評判模塊，一個基于純Java，另一個基于C++，兩者均可在Windows平臺下運(yùn)行。

學(xué)生在系統(tǒng)提交程序后，系統(tǒng)先將程序保存至數(shù)據(jù)庫，再寫入評判隊(duì)列，由系統(tǒng)評判內(nèi)核進(jìn)行編譯、運(yùn)行并返回結(jié)果，返回的結(jié)果類型有AC、WA、RTE、TLE、PE、MLE、CE。每個題目可能有多個測試數(shù)據(jù)，內(nèi)核在讀取主系統(tǒng)傳遞給它的參數(shù)后，編譯程序，生成可執(zhí)行文件，之后對于每個測試數(shù)據(jù)運(yùn)行一次“驗(yàn)證測試數(shù)據(jù)”的操作，只有當(dāng)所有測試數(shù)據(jù)均驗(yàn)證無誤，才返回AC，如果在某次驗(yàn)證返回錯誤，則返回相應(yīng)的錯誤信息，在任何時候遇意外終止將返回RTE。評判內(nèi)核的程序流程如圖1所示。

系統(tǒng)用戶分為四種：普通用戶、高級用戶、論壇版主及系統(tǒng)管理員。任何學(xué)生都可注冊成為普通用戶。普通用戶可以做練習(xí)題，提交程序并得到系統(tǒng)的評判和結(jié)果反饋；可以根據(jù)程序提交情況參與用戶排名；擁有并可使用自己的站內(nèi)信箱；可以查看、保存和管理自己提交的源代碼；可以在論壇發(fā)帖，參與問題討論；可以參加程序設(shè)計(jì)競賽，并查看比賽結(jié)果和統(tǒng)計(jì)數(shù)據(jù)。任何解答題目超過20道的普通用戶，可自動升級為高級用戶。高級用戶擁有普通用戶的所有權(quán)限，還可以上傳題目和測試數(shù)據(jù)，并可對自己上傳的題目進(jìn)行管理、修改等。高級用戶上傳的題目，經(jīng)管理員確認(rèn)后，便可加入系統(tǒng)的正式題庫，系統(tǒng)在題目信息中記錄上傳題目者的相關(guān)信息。論壇版主為系統(tǒng)管理員授予，擁有普通用戶的所有權(quán)限，同時對相應(yīng)的論壇板塊擁有管理權(quán)。系統(tǒng)管理員管理系統(tǒng)的日常運(yùn)行，擁有所有的管理權(quán)限，需要對題目和測試數(shù)據(jù)進(jìn)行篩選，檢查系統(tǒng)運(yùn)行情況，組織程序設(shè)計(jì)競賽。

3.課程設(shè)置

結(jié)合我校實(shí)際情況，我們在算法分析與設(shè)計(jì)課程的實(shí)踐教學(xué)內(nèi)容上設(shè)計(jì)了遞歸算法、分治算法、動態(tài)規(guī)劃算法、貪心算法、回溯算法、分支界限算法共6個經(jīng)典算法的實(shí)驗(yàn)項(xiàng)目。由于實(shí)踐教學(xué)課時有限，傳統(tǒng)的教學(xué)方式每個實(shí)驗(yàn)項(xiàng)目只能設(shè)計(jì)2-3道題目。引入ACM-ICPC模式之后，學(xué)生可以利用課余時間通過網(wǎng)絡(luò)完成程序設(shè)計(jì)，每個實(shí)驗(yàn)項(xiàng)目題量增加到6-8個，題目難度各異，學(xué)生可以根據(jù)自己的知識掌握程度和能力選擇合適的時間完成。較容易的題目可以先完成，具有一定的綜合性、難度較大的題目，可以在有相當(dāng)?shù)挠?xùn)練量之后完成。

這種循序漸進(jìn)的訓(xùn)練方式，更有利于學(xué)生對算法原理的理解和掌握，也更有利于形成由淺入深的思維模式，有效提高學(xué)生的分析問題、解決問題的能力。測評系統(tǒng)中的部分習(xí)題如表1所示。

課程的考核參考學(xué)生提交程序的次數(shù)、通過率、提交程序的難度等，作為學(xué)生平時成績的考核依據(jù)，這樣可以鼓勵和督促學(xué)生積極參與實(shí)踐。

四、課程建設(shè)實(shí)踐成果

實(shí)施ACM-ICPC競賽模式的程序在線測評系統(tǒng)以后，學(xué)生的學(xué)習(xí)積極性得到了較大的提高。學(xué)生對經(jīng)典算法的掌握程度和實(shí)踐能力也大大提高了。

學(xué)生在各種全國性考試和比賽中取得了較好的成績。以我校參加“藍(lán)橋杯”全國軟件專業(yè)人才設(shè)計(jì)與創(chuàng)業(yè)大賽的情況為例，不僅在報(bào)名人數(shù)上大幅增長，獲獎人數(shù)和獲獎等級也有了明顯的提高，具體如圖2所示。

在課程的實(shí)踐教學(xué)中，學(xué)生設(shè)計(jì)算法的訓(xùn)練量加大，平均每人每學(xué)期完成習(xí)題數(shù)量為34題，較實(shí)施前增長88.9%。學(xué)生的自主學(xué)習(xí)能力有所提高，教師在實(shí)驗(yàn)課上的空閑率由原來的0.4%增長到33.3%，學(xué)生對教師的依賴程度大大降低。

五、結(jié)語

基于ACM-ICPC模式的算法分析與設(shè)計(jì)課程將理論學(xué)習(xí)與實(shí)際操作相結(jié)合，注重培養(yǎng)和提高學(xué)生分析和解決實(shí)際問題的能力，以公平、公正、公開的競爭形式帶動學(xué)生的自主學(xué)習(xí)，調(diào)動學(xué)生交流和研究的積極性，為課程的開展提供了良好的氛圍。在后續(xù)的研究和開發(fā)中，我們將把基于ACM-ICPC模式的程序測評系統(tǒng)擴(kuò)展到全系范圍內(nèi)的更多的程序設(shè)計(jì)類課程。

參考文獻(xiàn)：

[1]龔宇平，梁麗.計(jì)算機(jī)專業(yè)大學(xué)生創(chuàng)新思維的培養(yǎng)[J].教育與職業(yè)，2014（8）.

[2]陸慧.應(yīng)用型本科高校創(chuàng)新型人才培養(yǎng)存在的問題與對策[J].教育與職業(yè)，2013（35）.

[3]趙春風(fēng).基于J2EE技術(shù)ACM競賽程序在線評測系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].廈門：廈門大學(xué)，2013.10.

[4]李華，趙建平，李奇等.基于ACM-ICPC的算法設(shè)計(jì)與分析課程改革[J].計(jì)算機(jī)教育，2013（7）.

[5]趙暉，付秀花.計(jì)算機(jī)語言程序設(shè)計(jì)課程的教學(xué)創(chuàng)新[J].教育與職業(yè)，2013（23）.

[6]王偉嘉，張洪萍，寧亞輝等.關(guān)于《數(shù)據(jù)結(jié)構(gòu)》課程與ACM-ICPC競賽結(jié)合的探討[J].計(jì)算機(jī)工程與科學(xué)，2014（S1）.

[7]芶生平，楊鵬，汪小平等.以ACM/ICPC競賽為載體 探索課程體系建設(shè)與創(chuàng)新人才培養(yǎng)新模式[J].中國大學(xué)教學(xué)，2010（7）.

[8]ZHU Jie-ao， SUN Mian， LIU Xue， LI Hao. Learning Software Engineering through Experience of ACM-ICPC Training and Practicing Exercises[C].Proceedings of 2010 Third International Conference on Education Technology and Training（Volume 1），2010.11.

（編輯：李曉萍）