林玉娥 梁興柱

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

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

中圖分類號：G642文獻標(biāo)識碼：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

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

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

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

1.1適合教材匱乏

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

1.2重理論，輕實踐

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

1.3學(xué)生應(yīng)用能力差

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

2算法設(shè)計與分析課程改革

2.1建立興趣小組，提升學(xué)習(xí)興趣

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

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

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

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

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

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

2.4改革考核形式

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

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

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

3結(jié)束語

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

參考文獻：

[1]劉波.算法設(shè)計與分析教學(xué)探討[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]徐本柱,王浩,胡學(xué)鋼. ACM/ICPC的教學(xué)與實踐[J].合肥工業(yè)大學(xué)學(xué)報:社會科學(xué)版,2008 (6):133-137.

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