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

李華　趙建平　李奇　武巖

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

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

文章編號：1672-5913（2013）07-0088-04

中圖分類號：G642

0 引言

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

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

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

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

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

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

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

1.2國外課程情況

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

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

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

3）課程專題討論。每周安排至少2小時的討論。討論內(nèi)容是所學(xué)課堂知識的一個擴展。每次討論設(shè)置一個專題，現(xiàn)場分發(fā)討論題目，而且有些討論的內(nèi)容會直接出現(xiàn)在期末考試中，所以缺席討論會對成績造成重要的影響。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.5鼓勵競賽與課程成績互補

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

2.6考試改革

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

3 結(jié)語

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

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