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

李華　趙建平　李奇　武巖

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

關鍵詞：ACM-ICPC；算法設計與分析；教學改革

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

中圖分類號：G642

0 引言

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

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

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

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

1 國內外課程情況對比

1.1國內課程情況

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

1.2國外課程情況

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

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

2）課堂講授。由淺入深，推導出理論方法，傳授算法設計技巧。

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

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

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

2 課程教學模式改革措施

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

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

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

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

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

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

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

2.3增加課程討論，加強學生間交流

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

2.4開放實驗室，適當增加學時

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

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

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

2.6考試改革

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

3 結語

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

（見習編輯：劉麗麗）