孫大烈　車萬翔

1ACM競賽的背景

ACM國際大學生程序設計競賽(ACM International Collegiate Programming Contest,ACM ICPC)始于1970年,作為一種全新的發(fā)現(xiàn)和培養(yǎng)計算機科學頂尖人才的途徑,競賽很快得到美國和加拿大各大學的積極響應。1977年,在ACM計算機科學會議期間,舉辦了首屆總決賽,由此拉開了一年一度的國際大學生程序設計競賽的帷幕。

30多年來,ACM ICPC由最初的美國、加拿大,拓展到了北美洲、拉丁美洲、歐洲、亞洲、大洋洲和非洲,成為世界性的賽事。2008年,參加各大洲預賽的隊伍有來自88個國家(地區(qū))1,838所大學的7,109支代表隊,從中產(chǎn)生的100支隊伍參加了2009年4月在瑞典斯德哥爾摩舉行的世界總決賽。

中國大陸從1996年開始設立ACM ICPC亞洲區(qū)預賽賽區(qū)并參與此項賽事,越來越多的高校參與其中,尤其是2005年以后,參賽勢頭更是如火如荼。2008年,亞洲區(qū)預賽共設立15個賽區(qū),中國大陸占5席,有近5000支隊伍參加了各賽區(qū)的網(wǎng)絡預賽,近480支隊伍參加了現(xiàn)場賽,最終有15支隊伍進入總決賽。

2ACM競賽的價值

ACM ICPC的價值和意義主要體現(xiàn)在兩個方面,一是競賽模式新穎,有利于培養(yǎng)學生的編程實踐能力,二是對參賽選手的綜合素質要求高,有利于培養(yǎng)學生的創(chuàng)新實踐意識。

ACM ICPC的競賽模式如下:

(1) 題目類型比較雜,涉及知識面比較廣,只要能夠編程的問題都可以納入競賽題目范圍。每個題目都需要經(jīng)過研讀、分析、確定算法,然后編程的過程。

(2) 采用在線測評系統(tǒng)進行評判,對提交程序的要求不僅包括正確性,還包括對運行時間、占用內(nèi)存和輸入輸出格式的限制。

(3) 所有的題目均采用英文命題。

(4) 每個參賽隊伍由3人組成,比賽時每個隊使用一臺機器解答問題。

(5) 比賽題目都是由專門機構負責制作的,每次賽事都由不同的人出題,題目的風格、類型、難易度都有很高的不確定性。

(6) 比賽時間5小時,一共10個題目,100支隊伍同場競技,看誰做出來的題數(shù)多、用時少。

ACM ICPC對參賽選手的素質要求有:

(1) 算法實現(xiàn)能力。即編寫代碼、調(diào)試程序的能力。根據(jù)ACM ICPC的規(guī)則,在5個小時內(nèi)解題數(shù)最多、用時最少的為冠軍,所以算法實現(xiàn)能力是基礎。

(2) 通曉各種算法。熟悉各種算法,對常用的算法達到信手拈來的程度。

(3) 算法選擇能力。面對實際問題,在最短時間內(nèi)確定最優(yōu)算法。

(4) 數(shù)學知識。包括圖論、組合數(shù)學、數(shù)論、幾何等,就目前的情況而言,數(shù)學知識對選手取得好成績是很重要的。

(5) 英文閱讀能力。

(6) 團隊合作能力。每支參賽隊由3人構成,共用1臺機器。什么樣的人組成一個隊伍、如何分工、如何協(xié)作、如何決策等,都有很多學問。

(7) 創(chuàng)新能力。其他的都是基礎,唯有創(chuàng)新能力才是根本,這是所有競賽的特點。ACM ICPC的題目涉及各個領域,類型包羅萬象。不是所有的問題都有現(xiàn)成的算法,更多的時候需要在現(xiàn)有算法的基礎上進行創(chuàng)新,有時候甚至需要觀念創(chuàng)新、思維創(chuàng)新。

正是ACM ICPC對提高學生綜合能力尤其是創(chuàng)新能力的價值,深深地吸引了國內(nèi)外高校和莘莘學子,他們以不同方式、不同程度地介入這項賽事,這也進一步提高了這項賽事的價值。

3我國參加ACM競賽情況

3.1參賽學校的類型

我國高校開展ACM ICPC活動的情況各不相同,時間有先有后,程度有深有淺,廣度有寬有窄,力度有大有小,成績有高有低。但無論怎樣,各高校的積極性越來越高,規(guī)模越來越大。以黑龍江省為例,2005年以前只有哈工大參與這項賽事,而從2006年開始,已經(jīng)連續(xù)舉行了三屆省賽,省內(nèi)幾乎所有高校都參加了網(wǎng)絡賽和現(xiàn)場賽。

在開展ACM ICPC的過程中,各校采取的模式不盡相同,這主要取決于學校的特點。有些學校有眾多優(yōu)秀的OI(信息學奧林匹克)選手,這些學生在高中階段就參加信息競賽,有良好的基礎,自然就成為該校的ACM ICPC選手,他們要做的就是在大學繼續(xù)高中階段的競爭。這類學校的學生基礎好,有助于在全校范圍開展ACM ICPC活動,同時也是各種賽事中取得好成績的保障。

另一些學校也有優(yōu)秀的OI選手,雖然人數(shù)不多,但是猶如種子,可以生根、發(fā)芽、結果。他們可以影響和帶動其他同學,使之成為和他們一樣優(yōu)秀的ACM競賽選手。這類學校一般對ACM ICPC都比較重視,全校性的活動開展得很好,各種賽事的成績也很突出。

更多的學校屬于白手起家,沒有優(yōu)秀的OI選手,一切從零做起。這類學校開展ACM ICPC的基礎比較薄弱,開展這項賽事的目標更多的不是取得成績,而是拓展學生綜合能力的空間。比較而言,雖然這類學校的成績不是最好,但是進步是最大的。他們中許多人在上大學前從來沒編過程序,通過ACM ICPC,他們可以參加賽區(qū)比賽,獲得銅牌、銀牌甚至金牌,對他們來說變化是巨大的。

3.2選拔和培養(yǎng)參賽隊員的途徑

對于很多學校來說,如何挖掘有潛力的ACM參賽隊員,是要解決的第一個問題。眾所周知,數(shù)據(jù)結構和算法是ACM ICPC的核心,但如何發(fā)掘從沒有接觸過這方面知識的人的潛力呢?本質上看,數(shù)據(jù)結構和算法都是數(shù)學范疇的知識,所以數(shù)學成績好要比數(shù)學成績不好的學生潛力大,但并不否認某些特例?，F(xiàn)今ACM ICPC中有一類題目是直接的數(shù)學題,與其說是考察學生的程序設計和算法,不如說是考察數(shù)學水平。這類數(shù)學問題大多涉及組合數(shù)學、數(shù)論等知識,沒有接觸過這些知識的人很難完成這樣的題目。另外,良好的抽象思維及嚴密的邏輯思維也能反映出這個人在數(shù)據(jù)結構和算法上的潛力。因此,學?？梢酝ㄟ^測試學生數(shù)學水平和邏輯抽象能力選拔隊員,也可以根據(jù)每個人的性格特點或思維習慣輔助選拔。

隊員經(jīng)過選拔后面臨的問題是怎樣進行訓練。因為教師的參賽經(jīng)驗并不豐富,所以可行的辦法是高年級帶低年級,形成一個團隊,隊員之間鼓勵相互學習,相互分享知識和經(jīng)驗。不僅讓學生學到知識,更要讓他們知道要學什么,怎樣學以及自己怎樣提高,學會解決問題,獨立探索,吃苦耐勞,這對學生的發(fā)展和綜合能力的提高是大有裨益的。我們以上總說數(shù)據(jù)結構和算法,而不直接說ACM ICPC,因為ACM ICPC從根本上還是一個競賽,而競賽不免會包含很多不確定因素,隊員的成績未必就代表隊員的水平,所以平時的心理素質訓練也是不可或缺的。

如何培養(yǎng)參賽選手是第二個要解決的問題。大多數(shù)參賽選手大學前沒有接觸過這些知識,所以他們首先要適應ACM ICPC編程比賽。ACM ICPC比賽追求的是速度、準確、創(chuàng)新,這就要求選手的思維和編程速度都很快。平時的訓練大家不僅要攻克難題,提高能力,還要適當模擬正式比賽,讓選手能夠適應正式比賽的緊張氣氛。比賽策略的訓練也很重要,如三個人的配合問題、題目完成的順序問題等。選手的知識儲備不僅要廣博,而且要有自己的“殺手锏”,即每個人都要有自己的專長,達到一看這些知識的題目就能立即完成的水平。當然,隨著大賽的普及,題目的類型不再可以明確區(qū)分,這就更要求選手有足夠多的知識儲備、足夠強的個人能力及一定的分析融合能力。在題目的選擇上也應有取舍,選擇有研究價值的題目訓練。

在ACM ICPC中,學生是永恒的主角,他們承擔培訓、集訓、宣傳、選秀等工作,教師永遠是做引導、服務工作的配角。很多學校已經(jīng)形成了以老帶新的傳統(tǒng),一年一年下來,形成一種機制,這正是ACM ICPC培養(yǎng)學生綜合能力的核心,而在這種機制中,老隊員和新隊員都得到了很好的自我鍛煉和提高的機會。

4我校將ACM競賽融入教學

和體育運動類似,要想在ACM ICPC中獲得好成績,必須有廣泛的群眾基礎,盡可能讓更多的學生受益,提高學生的整體編程水平。從2004年起,哈工大便將ACM ICPC引入計算機學院本科一年級的程序設計課程中,激發(fā)學生對ACM ICPC的興趣,吸引更多學生投身到此項活動中。

我們的具體做法是:

(1) 將ACM ICPC題目作為實驗,加大實驗成績比重

在百分制評定中,將實驗(共10次)成績的比重加大到50分,督促學生重視每次實驗。實驗題目以ACM ICPC題目為主,有一定的實際背景,但都沒有標準答案,學生要根據(jù)所學知識做出解答,每個題目的解決方法有很多。

多數(shù)題目的解決過程是這樣的:首先使用最常規(guī)、最自然的思維方式解決實際問題,然后考慮時間效率較低或空間占用較大的情況,如果新方法不是最好的,還有沒有更好的方法呢?這往往需要花費更多的時間和精力,也是學生收益最多的地方。對于教學管理來講,這種具有明確輸入、輸出形式的實驗可以由機器自動評判成績,減輕了教師的工作量,使這項工作得以順利開展。

為了保證學生實驗的質量,避免雷同情況的發(fā)生,我們引入了Moss(Measure of Software Similarity)雷同判別程序,促使學生通過自己的思考和努力獨立完成實驗。另外,如何從解題思路、程序風格等方面細致評判學生的實驗完成情況,給出個性化的實驗評語,也是亟待解決的一個問題。為此,需要大量的學生TA(Teaching Assistant)輔導實驗,即每半個班級安排一名學生TA,對其負責的學生進行實驗課上實時答疑,課下登錄課程論壇隨時答疑。同時,學生TA還對所負責同學的實驗進行評判,做到仔細閱讀每行代碼,公正評判,給出詳細的扣分原因及程序改進建議。學生TA由編程經(jīng)驗豐富的博士生、碩士生甚至本科生擔任。

學生實驗情況調(diào)查顯示,39.4%的學生認為“作業(yè)偏難,需要花費大量精力完成,但是從中收獲很多”,有35.2%的學生認為“作業(yè)難度適中,較好地鍛煉了編程能力”?？梢?大部分學生對這種實驗方式表示認可,并通過實驗鍛煉了實際動手能力。

(2) 培養(yǎng)拔尖人才,給學有余力的學生“吃小灶”

僅通過完成實驗培養(yǎng)出優(yōu)秀的ACM ICPC選手困難較大,因此我們用多種精神和物質獎勵刺激拔尖人才的快速進步。完成大量的題目是取得優(yōu)異成績的基礎,所謂熟能生巧,量變引起質變。我們引入競爭機制,將學生在HOJ(HIT Online Judge)上的做題數(shù)進行實時排序,如圖1所示,學生做題數(shù)目穩(wěn)步增長,最終形成一種你追我趕的良好態(tài)勢。為了保證充足的上機時間,刺激學生力爭上游,我們給排名靠前(60名)的學生提供免費上機機會,還向綜合表現(xiàn)優(yōu)異的同學發(fā)放編程和算法方面的書籍。

5結束語

參與ACM競賽不僅使學生提高了計算機編程水平,提升了綜合素質,還促進了相關課程的教學改革,提高了教學效果。目前,我校開展這項賽事活動還處于起步階段,局限于少數(shù)院系的參與,今后將在全校范圍內(nèi)推廣這項活動,讓更多的學生參與其中,得到鍛煉提高。