以ACM-ICPC競賽為依托的算法設計與分析課程改革

林玉娥 梁興柱

摘要：針對提高算法設計與分析課程教學效果的問題，本文給出了以ACM-ICPC為依托的算法設計與分析的課程改革方法.本文通過分析算法分析與設計課程教學中存在的問題,提出了建立興趣小組,構建ACM-ICPC在線測評系統(tǒng),以及新的考核方式促進學生自主學習的教學方法。改革方法能夠有效地挖掘學生的潛能，在實際的教學中取得了良好的教學效果。

關鍵詞：算法設計與分析；ACM-ICPC；教學改革；在線測評系統(tǒng)

中圖分類號：G642文獻標識碼：A文章編號：1009-3044(2012)07-1708-02

Curriculum Reform of Algorithm Design and Analysis Based on ACM-ICPC

LIN Yu-e, LIANG Xing-zhu

(Anhui University of Science and Technology Institute of Computer Science and Technology, Huainan 232001, China)

Abstract: To improve the teaching effect of algorithm design and analysis course, this paper proposed curriculum reform of algorithm design and analysis based on ACM-ICPC .Analyzing the existing problem on real teaching process, the teaching methods of the establishment of interest groups, building ACM-ICPC online evaluation system, and new assessment methods are given, which can promote students independent learning. This teaching method can mine students potentiality, and it has achieved better effect in real teaching.

Key words: algorithm design and analysis; ACM-ICPC; curriculum reform; online judge system

算法設計與分析是計算機科學與技術專業(yè)、軟件工程等專業(yè)的必修課，課程具有很強的理論性，課程涉及的領域廣、應用性強，不能機械記憶，而是要理解性地學習掌握它的理論基礎，并靈活運用，這就要求學生有很扎實的數(shù)學和一定的程序設計能力。而課程本身又具有極強的可擴展性、可開發(fā)性，學生必須善于思考，勤于練習，才能真正掌握[1]。

ACM國際大學生程序設計競賽（ACM International Collegiate Programming Contest, ACM- ICPC）是由美國計算機協(xié)會（Association of Computer and Machinery, ACM）主辦的一項旨在展示大學生創(chuàng)新能力、團隊精神和在壓力下編寫程序、分析和解決問題能力的年度競賽，現(xiàn)已發(fā)展成為最具影響力的大學生計算機競賽[2]。近年來，ACM-ICPC在我國得到了大規(guī)模的推廣，我國上海交通大學獲得三次總冠軍，浙江大學在2011年獲得總冠軍。各知名高校均成立ACM-ICPC訓練基地，上海交通大學、哈爾濱工程大學等還選拔綜合能力強的學生單獨成立ACM實驗班，以培養(yǎng)高精尖IT人才。競賽涵蓋的范圍包括：計算幾何，數(shù)論，組合數(shù)學，搜索技術算法，動態(tài)規(guī)劃，圖論和其他。可使用的計算機語言有C/C++，JAVA[3]。因此嘗試了將競賽與教學結合在一起的教學改革方案，取得了較好的教學效果。

1算法設計與分析課程現(xiàn)存的問題

1.1適合教材匱乏

考慮到實際學時，多數(shù)的算法設計與分析課程配套的教材普遍偏難，公式多，詳細講解少，內容枯燥。書中的代碼基本為偽代碼，沒有一定編程基礎，動手能力差的學生很難實現(xiàn)，一定程度影響學生的積極性。

1.2重理論，輕實踐

一方面，算法設計課程與分析課程理論課時多實驗課時少；另一方面，受到傳統(tǒng)教學理念的影響,教學條件和實驗條件的限制。所以，教師在教學過程中更加重視基本理論和原理的講授，沒有很好地研究如何將有限的實驗時間利用起來培養(yǎng)學生的應用能力，忽略了對學生程序設計能力和分析問題能力的培養(yǎng)，結果使學生陷入枯燥的理論和數(shù)學公式中，造成理論和實踐相脫節(jié)，實際教學實效較差。

1.3學生應用能力差

學生在學習時，常常能明白理論，但是使用算法解決實際問題的能力很弱。究其原因，一方面，學時少，內容多，舉例較少，沒有感性認識；另一方面，學生沒有編程實現(xiàn)程序，對算法的理解還是沒有吃透。

2算法設計與分析課程改革

2.1建立興趣小組，提升學習興趣

愛因斯坦說過：“興趣是最好的教師”。沒有興趣必然無法學習好課程。成立ACM興趣小組，鼓勵和組織學生參加，培養(yǎng)創(chuàng)新精神和能力，在實踐環(huán)節(jié)中培養(yǎng)和發(fā)現(xiàn)優(yōu)秀人才。通過周末論壇、賽前講座、月賽、校賽、寒暑假集訓等活動，學生不僅得到鍛煉，也為參加相關競賽打下了良好的基礎。

2.2強化課堂討論教學環(huán)節(jié)

引入參與式教學。模仿ACM-ICPC競賽模式,將3至4名學生分成一個小組，讓他們自己選擇教師指定的題目,給他們充分的時間進行精心準備,讓他們就此在課堂上為其他同學進行講解。在學生分組時，將基礎好的學生和基礎差的學生編在一組，利用基礎好的學生帶動基礎差的學生學習，增強了差生的自信心。通過課堂討論鍛煉了學生的自學能力，同時也培養(yǎng)了學生的團隊合作意識。在實際教學過程中，學生在諸多方面提出了創(chuàng)造性想法,充分展現(xiàn)了自身的思維活力。

2.3以ACM-ICPC在線測評系統(tǒng)為平臺實踐教學

實踐教學仿照ACM-ICPC競賽模式，把它組織成一次比賽。設定好開始、結束時間，以及每次錯誤提交的罰時時間。題目一般每次4題與理論課程相關的知識。學生可以隨時看到自己做了幾題，在班級排名如何。這樣學生在一個競賽的環(huán)境中上機實驗，有一定的緊張感，會充分發(fā)揮各自的潛力，杜絕了在上機時上網聊天或玩游戲，因為這樣他就完不成任務。將課后作業(yè)和實驗移植到在線測評系統(tǒng)，課時安排課內12學時，課外20學時，鼓勵學生在線做題。在線測評系統(tǒng)特別能鍛煉學生的計算機動手能力，通過做題,學生普遍反應計算機動手能力有了很大的提高。曾今枯燥的離散數(shù)學、圖論、數(shù)值分析等課程，一旦與ACM競賽內容結合，學習起來就很有動力，也很輕松[4]。

為了做到基于ACM-ICPC的算法設計與分析的成功改革，首先必須保證實踐平臺ACM-ICPC在線測評系統(tǒng)能穩(wěn)定運行。ACM-ICPC在線測評系統(tǒng)實現(xiàn)可以學校自行開發(fā)或者使用已有成功在線測評系統(tǒng)?，F(xiàn)今，國內規(guī)模較大、開放性較好的是杭州電子科技大學的在線測評系統(tǒng)。系統(tǒng)可以為外校教師提供ACM競賽，提供在線算法設計、程序設計課程考試。

2.4改革考核形式

傳統(tǒng)的高校該課程的考核基本上分為平時成績（20%～30%）和期末考試（70%～80%）。這樣的考核方式偏重學生的記憶能力，忽視平時的學習過程，很難鍛煉學生實踐能力。課程的考核應注重算法設計策略的靈活應用及效率分析，而不是死記硬背。

課程的考核方式改革如下：課程考核分為三部分，分別為課堂討論考核(10%)、上機ACM競賽模式實踐考核（50%）和期末閉卷筆試(40%)。

課堂討論考核主要考核學生的學習積極性，包括對提問的回答、學生提問及討論，給出相應的分數(shù)。ACM競賽模式的實踐考核分為平時實驗成績（50%）和期末綜合實踐成績（50%），均為開卷考試，學生可以翻書查閱相關資料，考核學生實際編程能力、程序調試和解決問題能力。期末閉卷考試主要考核學生的算法時間和空間的效率分析，側重工科學生的分析問題能力。

3結束語

以ACM-ICPC競賽為依托的算法設計與分析課程改革，打破傳統(tǒng)的算法設計與分析課程教學模式和考核方式，將理論教學和實踐教學充分結合，注重培養(yǎng)學生的分析問題、解決問題、編程能力，引入競爭、討論、團隊機制，激發(fā)了學生自主研究性學習的興趣。通過課程改革，取得了明顯的效果，提高了教學質量和教學水平。

參考文獻：

[1]劉波.算法設計與分析教學探討[J].高等理科教育,2004(4):78-80.

[2] What is ACM ICPC[EB/OL].http://acm.hit.edu.cn/about-acm-icpc/what-is-acm-icpc

[3]徐本柱,王浩,胡學鋼. ACM/ICPC的教學與實踐[J].合肥工業(yè)大學學報:社會科學版,2008 (6):133-137.

[4]楊春明.算法分析與設計任務驅動教學模式改革與實踐[J].計算機教育,2009 (19):97-99.