面向ACM—ICPC競(jìng)賽的計(jì)算機(jī)人才培養(yǎng)教學(xué)與實(shí)踐方法

梁冰+馮林

摘要：針對(duì)目前大學(xué)計(jì)算機(jī)學(xué)科教學(xué)與實(shí)踐在培養(yǎng)計(jì)算機(jī)人才上的不足，提出了以ACM-ICPC競(jìng)賽為依托的計(jì)算機(jī)科學(xué)方向的理論教學(xué)內(nèi)容和實(shí)踐教學(xué)方法，引入ACM-ICPC競(jìng)賽注重學(xué)生思維能力和計(jì)算機(jī)實(shí)現(xiàn)算法的考核方式，強(qiáng)化以賽代練的實(shí)踐環(huán)節(jié)，培養(yǎng)學(xué)生的算法設(shè)計(jì)能力、編程技巧、邏輯思維能力以及良好的協(xié)作精神，實(shí)踐證明通過ACM-ICPC競(jìng)賽的模式及其培訓(xùn)能切實(shí)提升學(xué)生的程序設(shè)計(jì)和實(shí)現(xiàn)能力，培養(yǎng)社會(huì)真正需要的創(chuàng)新型計(jì)算機(jī)科學(xué)人才。

關(guān)鍵詞：計(jì)算機(jī)科學(xué)；ACM國際大學(xué)生競(jìng)賽；教學(xué)方法

TP3-4；G652

一、引言

ACM國際大學(xué)生程序設(shè)計(jì)競(jìng)賽（ACM International Collegiate Programming Contest，ACM-ICPC）是由美國計(jì)算機(jī)協(xié)會(huì)（ACM）主辦的，一項(xiàng)旨在展示大學(xué)生創(chuàng)新能力、團(tuán)隊(duì)精神和在壓力下編寫程序、分析和解決問題能力的年度競(jìng)賽。該項(xiàng)競(jìng)賽從1970年舉辦至今已歷31屆，因歷屆競(jìng)賽都薈萃了世界各大洲的頂尖計(jì)算機(jī)人才，競(jìng)賽采取ACM/ICPC程序設(shè)計(jì)競(jìng)賽評(píng)測(cè)系統(tǒng)pc2評(píng)判，實(shí)時(shí)發(fā)布各賽隊(duì)解題結(jié)果，避免人為的主觀因素的影響，ACM/ICPC競(jìng)賽的公正性與公平性得到充分的肯定，備受國際上的知名大學(xué)和各著名信息技術(shù)公司如Microsoft （微軟公司）、GOOGLE、IBM 等的高度關(guān)注，成為世界各國大學(xué)生最具影響力的國際級(jí)計(jì)算機(jī)的賽事[1]。

創(chuàng)新實(shí)驗(yàn)學(xué)院于2009年成立ACM實(shí)踐班，依托于校創(chuàng)新實(shí)踐基地，以培養(yǎng)創(chuàng)新人才為目標(biāo)，近年來在省賽全國賽中獲得多項(xiàng)大獎(jiǎng)，并于2012年獲得了我校首枚區(qū)域賽金牌[2]。目前，計(jì)算機(jī)人才培養(yǎng)的專業(yè)課程存在以下問題，專業(yè)課程廣度和深度都不夠，學(xué)生對(duì)算法理解的不深入。教學(xué)內(nèi)容理論性強(qiáng)，而缺乏實(shí)際應(yīng)用問題，內(nèi)容枯燥，學(xué)生缺乏學(xué)習(xí)興趣。實(shí)踐教學(xué)環(huán)節(jié)時(shí)間較少，形式不夠豐富，實(shí)踐活動(dòng)不具有連貫性和持續(xù)性，學(xué)生的編程能力弱。

而面向ACM-ICPC競(jìng)賽的計(jì)算機(jī)科學(xué)人才培養(yǎng)的教學(xué)與實(shí)踐方法能夠解決以上在計(jì)算機(jī)科學(xué)人才培養(yǎng)上存在的不足與弊端。ACM國際大學(xué)生程序設(shè)計(jì)競(jìng)賽需要參賽隊(duì)員具備數(shù)據(jù)結(jié)構(gòu)、排序算法、搜索技術(shù)、數(shù)論、組合數(shù)學(xué)、搜索技術(shù)、動(dòng)態(tài)規(guī)劃、計(jì)算幾何等多方面的知識(shí)。學(xué)生要想具備參加ACM-ICPC競(jìng)賽的能力，需要學(xué)習(xí)大量的算法知識(shí)，而且ACM-ICPC競(jìng)賽更要求算法的效率，因此學(xué)生對(duì)算法的理解更加深入。參賽學(xué)生需要要在國內(nèi)外的網(wǎng)站的OJ系統(tǒng)（online judge，OJ）上完成ACM競(jìng)賽涉及到的多個(gè)專題的競(jìng)賽題目，一個(gè)參加ACM競(jìng)賽的合格學(xué)生在一年中的編寫代碼數(shù)量至少是計(jì)算機(jī)專業(yè)同學(xué)大學(xué)4年完成的平均編程量的數(shù)十倍數(shù)百倍的量[3]。因此，ACM實(shí)踐班培養(yǎng)出來的計(jì)算機(jī)人才具有編程基礎(chǔ)過硬、算法設(shè)計(jì)能力強(qiáng)、邏輯思維縝密和良好的合作精神，因此在就業(yè)和保研中有著優(yōu)異的表現(xiàn)，獲得了來及微軟、google等知名信息企業(yè)以及國內(nèi)各重點(diǎn)院校的青睞。

二、ACM-ICPC彌補(bǔ)計(jì)算機(jī)教學(xué)不足

目前，大學(xué)計(jì)算機(jī)專業(yè)的教學(xué)中存在著理論教學(xué)與實(shí)踐運(yùn)用的嚴(yán)重脫節(jié)。一方面，理論教學(xué)內(nèi)容不能指導(dǎo)實(shí)踐的運(yùn)用，學(xué)生掌握了理論，卻無法用計(jì)算機(jī)語言實(shí)現(xiàn)。計(jì)算機(jī)專業(yè)課程包括C語言程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計(jì)采用筆試的方式考核學(xué)生的知識(shí)掌握能力，考試能得高分的學(xué)生，，卻不能編寫一條簡(jiǎn)單的程序，這完全背離的計(jì)算機(jī)專業(yè)對(duì)人才培養(yǎng)的目標(biāo)。雖然，目前，國內(nèi)計(jì)算機(jī)專業(yè)的實(shí)踐環(huán)節(jié)已經(jīng)得到了強(qiáng)化，但是實(shí)驗(yàn)課程中的程序設(shè)計(jì)題目單調(diào)枯燥，考察知識(shí)點(diǎn)單一，實(shí)際應(yīng)用意義不大，不利于學(xué)生對(duì)知識(shí)的深入理解和靈活應(yīng)用，更不利于創(chuàng)新能力的培養(yǎng)。現(xiàn)在的實(shí)驗(yàn)系統(tǒng)，老師對(duì)學(xué)生的編程結(jié)果的考核幾乎是不現(xiàn)實(shí)的，很難評(píng)價(jià)實(shí)驗(yàn)課學(xué)生的編程結(jié)果，因此也不能保證學(xué)生的實(shí)驗(yàn)課效果。引入ACM-ICPC競(jìng)賽的PC2判題系統(tǒng)就可以解決以上問題，各大高校的OJ，如北大、杭電上的編程題目知識(shí)點(diǎn)綜合性很強(qiáng)，題目貼近生活且趣味性很強(qiáng)，同學(xué)們非常有興趣去做題，每道題目都由測(cè)試樣例，PC2系統(tǒng)可以自動(dòng)評(píng)判程序的運(yùn)行結(jié)果[4]。對(duì)程序的時(shí)間復(fù)雜度也有限制，同樣一道題目，只有效率最優(yōu)的算法才能滿足題目的時(shí)間復(fù)雜度要求，這樣思考問題，才能對(duì)知識(shí)深入理解并靈活運(yùn)用，這樣的編程過程能有效的培養(yǎng)學(xué)生的創(chuàng)新能力的培養(yǎng)和實(shí)踐能力。但目前國內(nèi)的計(jì)算機(jī)專業(yè)的實(shí)踐課還尚未引入ACM-ICPC的PC2系統(tǒng)。

ACM-ICPC競(jìng)賽內(nèi)容以大學(xué)計(jì)算機(jī)學(xué)科理論課程為基礎(chǔ)，內(nèi)容往往涉及離散數(shù)學(xué)，數(shù)據(jù)結(jié)構(gòu)與算法，高等數(shù)學(xué)，高等代數(shù)，組合數(shù)學(xué)，圖論，網(wǎng)絡(luò)優(yōu)化與線性規(guī)劃，數(shù)論，計(jì)算幾何等多個(gè)領(lǐng)域，一些競(jìng)賽題目是多個(gè)領(lǐng)域知識(shí)的結(jié)合，掌握的知識(shí)需要融會(huì)貫通，才能解答出來。目前，關(guān)于計(jì)算機(jī)課程的講授還是獨(dú)立的，沒能很好的結(jié)合起來，可以通過ACM-ICPC競(jìng)賽和培訓(xùn)模式將多門計(jì)算機(jī)理論課內(nèi)容融合起來并能夠運(yùn)用于程序設(shè)計(jì)當(dāng)中。

三、面向ACM-ICPC的教學(xué)實(shí)踐方法

1.ACM程序設(shè)計(jì)競(jìng)賽實(shí)際問題的案例教學(xué)方法

在課程的理論教學(xué)中嵌入具有實(shí)際問題背景的ACM-ICPC賽題。ACM競(jìng)賽題目涉及的知識(shí)面非常廣，如果按照知識(shí)點(diǎn)一一講授，二年的課程時(shí)間學(xué)習(xí)難以講授完，且傳統(tǒng)的教學(xué)方法，學(xué)生感覺課程枯燥，對(duì)算法理解不夠深入，在競(jìng)賽中難以獲得好成績。

采用acm競(jìng)賽題目的實(shí)際問題案例教學(xué)方法，通過計(jì)算機(jī)編程語言實(shí)現(xiàn)算法巧妙的解決生活中遇到的有趣且有一定難度的問題，首先這些案例問題都非常的引人入勝，比如旅行商問題、背包問題、圖著色問題，acm競(jìng)賽中解決這些問題的算法復(fù)雜度要求都很高，因此解決這些問題算法都具有一定的數(shù)學(xué)思想和理論深度，在解決實(shí)際問題的同時(shí)，學(xué)生對(duì)算法和數(shù)學(xué)思想理解深度、掌握和運(yùn)用的熟練程度都有了非常大的提升。而且在解決每一道實(shí)際問題過程中，遇到的數(shù)據(jù)結(jié)構(gòu)、算法、數(shù)學(xué)的知識(shí)點(diǎn)有若干個(gè)，學(xué)生能夠在短時(shí)間內(nèi)吸收到大量的知識(shí)。

2.以賽代練的實(shí)踐教學(xué)方法

課程的實(shí)驗(yàn)教學(xué)以程序設(shè)計(jì)競(jìng)賽的形式實(shí)施，在實(shí)踐課環(huán)節(jié)通過在OJ系統(tǒng)上完成ACM的競(jìng)賽題目。實(shí)ACM競(jìng)賽對(duì)學(xué)生編程和算法的基本功要求非常高，對(duì)算法理解不深入、編程基礎(chǔ)不扎實(shí)、知識(shí)點(diǎn)不全面都難以在要求的時(shí)間復(fù)雜度下完成題目。因此，實(shí)踐教學(xué)部分至關(guān)重要，實(shí)踐教學(xué)需要全方位、各層次的組織，保證實(shí)踐教學(xué)的時(shí)間和深度，在實(shí)踐中提升學(xué)生的能力，發(fā)現(xiàn)自身知識(shí)結(jié)構(gòu)的欠缺，促使學(xué)生發(fā)揮自主學(xué)習(xí)精神，自學(xué)所需算法和相關(guān)知識(shí)。

實(shí)踐教學(xué)分一下幾個(gè)方面組織，日常訓(xùn)練：根據(jù)課堂教學(xué)的內(nèi)容，為學(xué)生挑選acm競(jìng)賽中相關(guān)的題目，加強(qiáng)訓(xùn)練，真正掌握相關(guān)的知識(shí)點(diǎn)和擴(kuò)展內(nèi)容。周賽：每周周末舉辦周賽，督促學(xué)生對(duì)算法的持續(xù)學(xué)習(xí)，提高學(xué)生的學(xué)習(xí)熱情，鞏固學(xué)生成果。校賽：每學(xué)期舉辦一次校賽，春季學(xué)期為個(gè)人賽，秋季學(xué)習(xí)為團(tuán)隊(duì)賽，校賽考察學(xué)生知識(shí)點(diǎn)全面，提升學(xué)生競(jìng)技狀態(tài)，團(tuán)隊(duì)賽培養(yǎng)學(xué)生的團(tuán)隊(duì)精神和配合。暑期集訓(xùn)：暑期集訓(xùn)是大幅度提升學(xué)生能力的關(guān)鍵時(shí)期，暑期時(shí)間集中，學(xué)生集中，學(xué)生學(xué)習(xí)效率高，學(xué)生學(xué)習(xí)氛圍濃厚。省賽、四省賽、區(qū)域賽：更高級(jí)別的acm-icpc競(jìng)賽，與全國高校中的出類拔萃的計(jì)算機(jī)人才同場(chǎng)競(jìng)技，也是為高級(jí)別的acm比賽選拔隊(duì)員。這樣高層次的比賽可以激發(fā)學(xué)生的潛能，在準(zhǔn)備各級(jí)賽事的短時(shí)間內(nèi)，吸收、鞏固大量的知識(shí)。

實(shí)踐教學(xué)通過ACM/ICPC在線評(píng)判系統(tǒng)為教學(xué)實(shí)訓(xùn)平臺(tái)，輔助完成日常訓(xùn)練和模擬競(jìng)賽，增加上機(jī)考核方式，實(shí)現(xiàn)對(duì)學(xué)生程序的自動(dòng)運(yùn)行和測(cè)試，增強(qiáng)學(xué)生的程序調(diào)試能力。并通過分析比賽結(jié)果，更加精細(xì)地評(píng)估學(xué)生對(duì)教學(xué)知識(shí)點(diǎn)的掌握程度，這些信息進(jìn)一步反饋到課程的理論教學(xué)中，可以確定課程教學(xué)的實(shí)際難點(diǎn)和重點(diǎn)。

四、結(jié)語

大連理工大學(xué)創(chuàng)新實(shí)驗(yàn)學(xué)院經(jīng)過多年培養(yǎng)面向ACM國際大學(xué)生競(jìng)賽的學(xué)生發(fā)現(xiàn)，這部分學(xué)生的計(jì)算機(jī)專業(yè)素質(zhì)較高，表現(xiàn)在編程能力強(qiáng)、知識(shí)面廣、具有良好的團(tuán)隊(duì)合作能力、創(chuàng)新能力和臨場(chǎng)應(yīng)變能力，因此在畢業(yè)時(shí)能獲得名校和名企的青睞。這主要與ACM-ICPC競(jìng)賽的一些良好的競(jìng)賽規(guī)則和競(jìng)賽環(huán)境有關(guān)，本文提出了面向ACM-ICPC競(jìng)賽的計(jì)算機(jī)人才培養(yǎng)教學(xué)與實(shí)踐方法提升計(jì)算機(jī)專業(yè)人才的素質(zhì)，包括以下幾個(gè)方面：1、理論課按專題講授，包括：圖、動(dòng)態(tài)規(guī)劃、搜索、計(jì)算幾何、數(shù)論等案例教學(xué)；2、實(shí)踐課引入PC2自動(dòng)判題系統(tǒng)，趣味綜合性題目選自國內(nèi)外著名OJ：3、周賽、月賽、校賽、省賽、區(qū)域賽培養(yǎng)學(xué)生綜合素質(zhì)、加深理論知識(shí)理解與實(shí)際運(yùn)用能力。

參考文獻(xiàn)

[1] 趙 龍，李貝貝，王喜鳳ACM/ICPC競(jìng)賽對(duì)培養(yǎng)大學(xué)生綜合能力的作用.安徽工業(yè)大學(xué)學(xué)報(bào)（社會(huì)科學(xué)版）.2013， 30（5）：110-111

[2] ACM/ICPC競(jìng)賽人才培養(yǎng)模式的研究與實(shí)踐——以大連理工大學(xué)ACM/ICPC創(chuàng)新實(shí)踐班為例.內(nèi)蒙古師范大學(xué)學(xué)報(bào)（教育科學(xué)版）.2012，25（3）：141-144

[3] 郭嵩山，王磊，張子臻.ACM/ICPC 與創(chuàng)新性IT 人才的培養(yǎng)[J].實(shí)驗(yàn)室研究與探索，2007，（12）6：181-185

[4] 韓建民，鐘發(fā)榮，趙相福.基于 ACM-ICPC 訓(xùn)練模式的數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)探索. 計(jì)算機(jī)教育.2013，（10）： 103-107