基于ACM—ICPC的算法設(shè)計(jì)與分析課程改革

李華　趙建平　李奇　武巖

摘要：通過分析算法設(shè)計(jì)與分析課程的教學(xué)狀況和教學(xué)形式，結(jié)合國內(nèi)外教學(xué)模式的對(duì)比情況，提出有效的教學(xué)改革方法。該方法提倡理論與實(shí)踐相結(jié)合，競賽與考試改革相結(jié)合，教師講解與課程討論相結(jié)合，提供給學(xué)生一個(gè)綜合的實(shí)踐鍛煉平臺(tái)，并建立適合長春理工大學(xué)學(xué)生的測評(píng)系統(tǒng)和習(xí)題庫，進(jìn)行嚴(yán)格規(guī)范的訓(xùn)練，達(dá)到真正提高學(xué)生競賽水平的目的。

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

文章編號(hào)：1672-5913（2013）07-0088-04

中圖分類號(hào)：G642

0 引言

算法分析與設(shè)計(jì)課程是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的專業(yè)基礎(chǔ)課程。該課程要求學(xué)生具備良好的數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)和程序設(shè)計(jì)語言基礎(chǔ)，是一門面向設(shè)計(jì)的計(jì)算機(jī)學(xué)科核心教育課程。該課程通過對(duì)算法設(shè)計(jì)策略的系統(tǒng)學(xué)習(xí)與研究，使學(xué)生理解和掌握算法設(shè)計(jì)的主要方法，培養(yǎng)學(xué)生對(duì)算法的計(jì)算復(fù)雜性進(jìn)行正確分析的能力，為學(xué)生獨(dú)立地設(shè)計(jì)算法和對(duì)給定算法進(jìn)行復(fù)雜性分析奠定堅(jiān)實(shí)的理論基礎(chǔ)。這對(duì)從事計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)、系統(tǒng)軟件和應(yīng)用軟件研究與開發(fā)等工作是非常重要的。

ACM國際大學(xué)生程序設(shè)計(jì)競賽（ACM International Collegiate Programming Contest，簡稱ACM-ICPC或ICPC），是由美國計(jì)算機(jī)協(xié)會(huì)（ACM）主辦的，是一項(xiàng)旨在展示大學(xué)生創(chuàng)新能力、團(tuán)隊(duì)精神以及編寫程序、分析和解決問題能力的年度競賽，是目前計(jì)算機(jī)行業(yè)唯一公認(rèn)的高水平競賽。

近幾年，ACM國際大學(xué)生程序設(shè)計(jì)競賽在全國范圍內(nèi)得到公認(rèn)，尤其在研究生復(fù)試、知名企業(yè)面試常時(shí)采用ACM程序設(shè)計(jì)大賽的試題模式進(jìn)行。各大高校也積極開展這方面的教育和培訓(xùn)。算法分析與設(shè)計(jì)課程作為程序設(shè)計(jì)類競賽的理論基礎(chǔ)課，其教學(xué)模式和教學(xué)方法改革也在不斷的探討中。學(xué)生普遍認(rèn)為這門課程屬于偏難理解、動(dòng)手困難的課程。因此，如何更有效地提高大學(xué)生獨(dú)立設(shè)計(jì)算法和分析算法的本領(lǐng)，提升實(shí)踐能力，成為算法分析與設(shè)計(jì)課程改革的主要方向。

與其他課程不同的是算法設(shè)計(jì)問題千變?nèi)f化，學(xué)生即使理解了知識(shí)點(diǎn)和設(shè)計(jì)策略仍需要結(jié)合大量有效的實(shí)踐才能真正掌握算法。所以實(shí)踐環(huán)節(jié)是至關(guān)重要的。針對(duì)這種狀況，本文首先對(duì)目前一些高校的算法分析與設(shè)計(jì)課程的教學(xué)情況進(jìn)行了分析和對(duì)比，然后提出一種基于ACM-ICPC模式的教學(xué)方法，旨在有效提高實(shí)踐水平，促進(jìn)教學(xué)效果和競賽水平的提升。

1 國內(nèi)外課程情況對(duì)比

1.1國內(nèi)課程情況

目前，國內(nèi)的計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)基本都開設(shè)了算法分析與設(shè)計(jì)課程。近10年，該課程的網(wǎng)絡(luò)資源變得越來越豐富。在國內(nèi)的普通高校，該課程普遍的教學(xué)模式是一名教師授課、一名實(shí)驗(yàn)教師配合實(shí)驗(yàn)教學(xué)。通過對(duì)國內(nèi)10所高校的課程情況進(jìn)行調(diào)查，該課程的理論學(xué)時(shí)分配為32～48學(xué)時(shí)不等，課內(nèi)實(shí)驗(yàn)學(xué)時(shí)一般為16學(xué)時(shí)。根據(jù)筆者多年教學(xué)經(jīng)驗(yàn)來看，這種教學(xué)模式只能達(dá)到一般的教學(xué)要求，即介紹幾種典型解決問題的策略，包括分治法、動(dòng)態(tài)規(guī)劃、貪心選擇、回溯法、分支限界法、概率算法等。講授內(nèi)容通過對(duì)經(jīng)典算法問題的分析，給出解決問題的最優(yōu)算法和時(shí)間、空間復(fù)雜性、正確性證明。而實(shí)驗(yàn)題目一般是對(duì)應(yīng)某種算法設(shè)計(jì)策略的練習(xí)。目前的實(shí)驗(yàn)環(huán)境可以檢驗(yàn)結(jié)果的正確與否，對(duì)于時(shí)間復(fù)雜性等要求無法準(zhǔn)確檢驗(yàn)。同時(shí)，由于課內(nèi)時(shí)間有限，使得綜合性設(shè)計(jì)的題目比例偏少，這就只能靠學(xué)生的興趣在課后進(jìn)行更多的練習(xí)，也在一定程度上制約了動(dòng)手能力的鍛煉。

1.2國外課程情況

由于國內(nèi)外教學(xué)體制的不同，我們無法準(zhǔn)確的對(duì)比分析國內(nèi)外的計(jì)算機(jī)算法課程，但是國外一些知名大學(xué)對(duì)算法導(dǎo)論類的課程教學(xué)模式是值得借鑒的，具體總結(jié)，主要有以下幾方面。

1）課程主要由3部分構(gòu)成：理論課、課程專題討論、習(xí)題及作業(yè)課。

2）課堂講授。由淺入深，推導(dǎo)出理論方法，傳授算法設(shè)計(jì)技巧。

3）課程專題討論。每周安排至少2小時(shí)的討論。討論內(nèi)容是所學(xué)課堂知識(shí)的一個(gè)擴(kuò)展。每次討論設(shè)置一個(gè)專題，現(xiàn)場分發(fā)討論題目，而且有些討論的內(nèi)容會(huì)直接出現(xiàn)在期末考試中，所以缺席討論會(huì)對(duì)成績?cè)斐芍匾挠绊憽?/p>

4）習(xí)題及作業(yè)課。重要的課程內(nèi)容都有相關(guān)的作業(yè)。學(xué)生必須在規(guī)定的時(shí)間內(nèi)獨(dú)立完成文檔。學(xué)校開放實(shí)驗(yàn)室，學(xué)生就可以自愿在指定的實(shí)驗(yàn)室和時(shí)間里集中完成作業(yè)，并得到助教的解答。此外我們還允許團(tuán)隊(duì)協(xié)作討論作業(yè)，但學(xué)生必須獨(dú)自完成在指定的時(shí)間內(nèi)提交的文檔，并能夠在討論課上對(duì)作業(yè)過程進(jìn)行闡述。

顯而易見，國外的課程教學(xué)安排更周密，詳盡。從學(xué)生的角度來看，這種做法的優(yōu)點(diǎn)是學(xué)生有自由的時(shí)間支配來完成實(shí)驗(yàn)以及作業(yè)，對(duì)學(xué)生給予更個(gè)性化的發(fā)展空間。

2 課程教學(xué)模式改革措施

按照上述分析，不難得出國內(nèi)學(xué)生在遇到新問題的時(shí)候仍是束手無策的原因。筆者根據(jù)多年的教學(xué)經(jīng)驗(yàn)，對(duì)算法分析與設(shè)計(jì)課程提出以下幾點(diǎn)思考。

2.1引入信息學(xué)競賽問題，采用啟發(fā)式教學(xué)

例如，在介紹解動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)策略的時(shí)候，教材中常用矩陣的連乘為例。該問題較為抽象，不易理解，而一般的信息學(xué)競賽題目富含一個(gè)故事，所以我們可以先利用信息學(xué)競賽題目的內(nèi)容，通過故事引出一個(gè)問題，這樣很容易喚起學(xué)生的興趣，學(xué)生自然也就渴望了解問題的解決辦法，主動(dòng)探求知識(shí)了。與此同時(shí)，我們用啟發(fā)式的教學(xué)方法，潛移默化的引出建立數(shù)學(xué)模型的過程，引出動(dòng)態(tài)規(guī)劃解決問題的基本思想和基本步驟。

例如，方塊消除問題：N個(gè)帶顏色的方格排成一列，相同顏色的方塊連乘一個(gè)區(qū)域（即如果連個(gè)相鄰方塊顏色相同，則這兩個(gè)方塊屬于同一區(qū)域）。游戲時(shí)，我們可以任選一個(gè)區(qū)域消去，并得到區(qū)域方塊個(gè)數(shù)平方的分?jǐn)?shù)。方塊消除問題的兩種情況如圖1所示，方塊消去之后將產(chǎn)生空列，此時(shí)其右邊的所有方塊就會(huì)向左移，直到所有方塊連在一起，要求確定不同消除方案下的最高得分方案。

2.2結(jié)合課程需要，引入全新實(shí)踐模式

算法分析與設(shè)計(jì)與其他程序設(shè)計(jì)類課程不同的一個(gè)重要特征是，要分析問題的復(fù)雜性，包含時(shí)間復(fù)雜度和空間復(fù)雜度兩方面。而一般的程序設(shè)計(jì)實(shí)驗(yàn)環(huán)境，只能檢驗(yàn)運(yùn)行結(jié)果的正確與否，無法確切的讓學(xué)生體會(huì)到運(yùn)算時(shí)間的概念。從這個(gè)角度講，算法問題的執(zhí)行必須結(jié)合嚴(yán)謹(jǐn)?shù)某绦蛟u(píng)判系統(tǒng)，而ACM-ICPC的在線判別系統(tǒng)OJ正具備這樣的判別機(jī)制，將ACM-ICPC模式引入到算法設(shè)計(jì)與分析的課堂教學(xué)中來也是勢在必行。

結(jié)合ACM-ICPC，學(xué)校建立了長春理工大學(xué)ACM-ICPC網(wǎng)站（網(wǎng)址為http：//acm.cust.edu.cn/），使課堂與實(shí)踐緊密地結(jié)合。在教學(xué)過程中，競賽的算法題目引入課堂，并把OJ系統(tǒng)作為實(shí)踐教學(xué)、檢驗(yàn)學(xué)生成績的手段。課后作業(yè)讓學(xué)生在規(guī)定的時(shí)間內(nèi)把答案提交到OJ系統(tǒng)，成績由系統(tǒng)自動(dòng)評(píng)判，系統(tǒng)會(huì)列出運(yùn)行每個(gè)學(xué)生程序的相關(guān)信息。教師根據(jù)系統(tǒng)信息了解學(xué)生的學(xué)習(xí)狀況，同時(shí)還能進(jìn)行運(yùn)行時(shí)間的統(tǒng)計(jì)，給出公平、公正的成績。這對(duì)于算法分析與設(shè)計(jì)來講至關(guān)重要，同時(shí)提高了教學(xué)效率和教學(xué)質(zhì)量。再者，很多算法問題既有趣，又有挑戰(zhàn)性，極大地提高了學(xué)生的興奮點(diǎn)。

2.3增加課程討論，加強(qiáng)學(xué)生間交流

每學(xué)期提供給學(xué)生9～10個(gè)題目，定期開展課程討論。課程討論過程中由學(xué)生講述算法設(shè)計(jì)思路，教師進(jìn)行啟發(fā)式引導(dǎo)，并進(jìn)行討論。經(jīng)過一個(gè)學(xué)期的鍛煉，學(xué)生的動(dòng)手能力得到鍛煉，思考問題更加縝密，團(tuán)隊(duì)協(xié)作能力也得到提升。

2.4開放實(shí)驗(yàn)室，適當(dāng)增加學(xué)時(shí)

我們需要完善課程教學(xué)體系，采取措施鼓勵(lì)教師開展多樣化教學(xué)手段，把課程討論、課程作業(yè)指導(dǎo)都納入計(jì)算課程總學(xué)時(shí)中。教師從加強(qiáng)學(xué)習(xí)效果人手，同時(shí)又使學(xué)生有更多的自由支配空間。這種“自由式”的學(xué)習(xí)方式，在國外是普遍被采納的，從實(shí)際效果看，好于灌輸式的學(xué)習(xí)方式。中國學(xué)生從小適應(yīng)教師灌輸，緊跟教師的節(jié)奏進(jìn)行被動(dòng)式學(xué)習(xí)，導(dǎo)致自己缺乏主動(dòng)思考問題的能力。若采用文章所述教學(xué)模式，學(xué)生的信心和主動(dòng)性被明顯帶動(dòng)加強(qiáng)。

2.5鼓勵(lì)競賽與課程成績互補(bǔ)

我們把學(xué)生參加OJ系統(tǒng)練習(xí)題的數(shù)量考慮到參賽隊(duì)員選拔指標(biāo)及成績考核中。由于每道題的完成情況在系統(tǒng)里都有記錄，教師可以適當(dāng)根據(jù)學(xué)生在系統(tǒng)中的習(xí)題完成情況，考查學(xué)生的平時(shí)成績，同時(shí)課程組教師參與競賽指導(dǎo)，對(duì)競賽和課程教學(xué)都深入了解，有利于教學(xué)和競賽的相互促進(jìn)。目前教學(xué)手段多樣化，很多課程都采用了多媒體授課。但是要因“課”而異。算法分析與設(shè)計(jì)課程的思路和思維方法很重要，學(xué)生必須有充分的思考時(shí)間，所以更適宜用傳統(tǒng)的板書教學(xué)。國外著名的算法課程多是這樣開展的，配以適當(dāng)?shù)耐队埃故具\(yùn)行結(jié)果，筆者認(rèn)為這是比較恰當(dāng)?shù)乃惴ㄊ谡n方式。我們還可以建立算法分析與設(shè)計(jì)課程網(wǎng)站，建立師生互動(dòng)平臺(tái)，進(jìn)行課后學(xué)習(xí)指導(dǎo)，發(fā)布課件信息、復(fù)習(xí)資料等。

2.6考試改革

與外國學(xué)生相比，中國學(xué)生理論基礎(chǔ)扎實(shí)，從教師和教材吸取的知識(shí)較多，對(duì)講授的內(nèi)容掌握牢靠；但創(chuàng)新能力較差，不善于發(fā)現(xiàn)問題、提出問題，缺乏實(shí)際解決問題的能力。這種現(xiàn)象的根源在于考試制度，包括考核形式與評(píng)分標(biāo)準(zhǔn)。目前，算法設(shè)計(jì)與分析課程的成績大多按兩部分計(jì)算：一部分是平時(shí)作業(yè)情況，占總成績的20%～30%；另一部分是閉卷考試，占總成績的70%～80%。這就導(dǎo)致學(xué)生對(duì)筆試的重視程度要高于實(shí)踐環(huán)節(jié)。因此改革課程考核方式是值得嘗試的。筆者認(rèn)為按照前述課程安排，平時(shí)實(shí)踐30%，作業(yè)報(bào)告20%，期末考試50%的比例是合理的。其中實(shí)踐環(huán)節(jié)的考核，均在OJ系統(tǒng)上實(shí)現(xiàn)，充分體現(xiàn)考試的公平公正。

3 結(jié)語

經(jīng)過一段時(shí)間，課程改革初見效果。學(xué)生參加ACM-ICPC競賽的成績逐年提高，除了連續(xù)3年獲得省內(nèi)、東北地區(qū)比賽一等獎(jiǎng)外，還獲得了全國大學(xué)生邀請(qǐng)賽及亞洲賽區(qū)銀獎(jiǎng)的好成績。今后，我們將進(jìn)一步探索算法分析與設(shè)計(jì)課程的教學(xué)模式改革，找出最能激發(fā)學(xué)生興趣的切入點(diǎn)，進(jìn)一步將課程教學(xué)與實(shí)踐環(huán)節(jié)有機(jī)地結(jié)合在一起，逐步提高學(xué)生的創(chuàng)新能力、動(dòng)手能力和團(tuán)隊(duì)協(xié)作能力。

（見習(xí)編輯：劉麗麗）