ＡＣＭ竞赛与学生综合实践能力培养

孙大烈　车万翔

1ACM竞赛的背景

ACM国际大学生程序设计竞赛(ACM International Collegiate Programming Contest,ACM ICPC)始于1970年,作为一种全新的发现和培养计算机科学顶尖人才的途径,竞赛很快得到美国和加拿大各大学的积极响应。1977年,在ACM计算机科学会议期间,举办了首届总决赛,由此拉开了一年一度的国际大学生程序设计竞赛的帷幕。

30多年来,ACM ICPC由最初的美国、加拿大,拓展到了北美洲、拉丁美洲、欧洲、亚洲、大洋洲和非洲,成为世界性的赛事。2008年,参加各大洲预赛的队伍有来自88个国家(地区)1,838所大学的7,109支代表队,从中产生的100支队伍参加了2009年4月在瑞典斯德哥尔摩举行的世界总决赛。

中国大陆从1996年开始设立ACM ICPC亚洲区预赛赛区并参与此项赛事,越来越多的高校参与其中,尤其是2005年以后,参赛势头更是如火如荼。2008年,亚洲区预赛共设立15个赛区,中国大陆占5席,有近5000支队伍参加了各赛区的网络预赛,近480支队伍参加了现场赛,最终有15支队伍进入总决赛。

2ACM竞赛的价值

ACM ICPC的价值和意义主要体现在两个方面,一是竞赛模式新颖,有利于培养学生的编程实践能力,二是对参赛选手的综合素质要求高,有利于培养学生的创新实践意识。

ACM ICPC的竞赛模式如下:

(1) 题目类型比较杂,涉及知识面比较广,只要能够编程的问题都可以纳入竞赛题目范围。每个题目都需要经过研读、分析、确定算法,然后编程的过程。

(2) 采用在线测评系统进行评判,对提交程序的要求不仅包括正确性,还包括对运行时间、占用内存和输入输出格式的限制。

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

(4) 每个参赛队伍由3人组成,比赛时每个队使用一台机器解答问题。

(5) 比赛题目都是由专门机构负责制作的,每次赛事都由不同的人出题,题目的风格、类型、难易度都有很高的不确定性。

(6) 比赛时间5小时,一共10个题目,100支队伍同场竞技,看谁做出来的题数多、用时少。

ACM ICPC对参赛选手的素质要求有:

(1) 算法实现能力。即编写代码、调试程序的能力。根据ACM ICPC的规则,在5个小时内解题数最多、用时最少的为冠军,所以算法实现能力是基础。

(2) 通晓各种算法。熟悉各种算法,对常用的算法达到信手拈来的程度。

(3) 算法选择能力。面对实际问题,在最短时间内确定最优算法。

(4) 数学知识。包括图论、组合数学、数论、几何等,就目前的情况而言,数学知识对选手取得好成绩是很重要的。

(5) 英文阅读能力。

(6) 团队合作能力。每支参赛队由3人构成,共用1台机器。什么样的人组成一个队伍、如何分工、如何协作、如何决策等,都有很多学问。

(7) 创新能力。其他的都是基础,唯有创新能力才是根本,这是所有竞赛的特点。ACM ICPC的题目涉及各个领域,类型包罗万象。不是所有的问题都有现成的算法,更多的时候需要在现有算法的基础上进行创新,有时候甚至需要观念创新、思维创新。

正是ACM ICPC对提高学生综合能力尤其是创新能力的价值,深深地吸引了国内外高校和莘莘学子,他们以不同方式、不同程度地介入这项赛事,这也进一步提高了这项赛事的价值。

3我国参加ACM竞赛情况

3.1参赛学校的类型

我国高校开展ACM ICPC活动的情况各不相同,时间有先有后,程度有深有浅,广度有宽有窄,力度有大有小,成绩有高有低。但无论怎样,各高校的积极性越来越高,规模越来越大。以黑龙江省为例,2005年以前只有哈工大参与这项赛事,而从2006年开始,已经连续举行了三届省赛,省内几乎所有高校都参加了网络赛和现场赛。

在开展ACM ICPC的过程中,各校采取的模式不尽相同,这主要取决于学校的特点。有些学校有众多优秀的OI(信息学奥林匹克)选手,这些学生在高中阶段就参加信息竞赛,有良好的基础,自然就成为该校的ACM ICPC选手,他们要做的就是在大学继续高中阶段的竞争。这类学校的学生基础好,有助于在全校范围开展ACM ICPC活动,同时也是各种赛事中取得好成绩的保障。

另一些学校也有优秀的OI选手,虽然人数不多,但是犹如种子,可以生根、发芽、结果。他们可以影响和带动其他同学,使之成为和他们一样优秀的ACM竞赛选手。这类学校一般对ACM ICPC都比较重视,全校性的活动开展得很好,各种赛事的成绩也很突出。

更多的学校属于白手起家,没有优秀的OI选手,一切从零做起。这类学校开展ACM ICPC的基础比较薄弱,开展这项赛事的目标更多的不是取得成绩,而是拓展学生综合能力的空间。比较而言,虽然这类学校的成绩不是最好,但是进步是最大的。他们中许多人在上大学前从来没编过程序,通过ACM ICPC,他们可以参加赛区比赛,获得铜牌、银牌甚至金牌,对他们来说变化是巨大的。

3.2选拔和培养参赛队员的途径

对于很多学校来说,如何挖掘有潜力的ACM参赛队员,是要解决的第一个问题。众所周知,数据结构和算法是ACM ICPC的核心,但如何发掘从没有接触过这方面知识的人的潜力呢?本质上看,数据结构和算法都是数学范畴的知识,所以数学成绩好要比数学成绩不好的学生潜力大,但并不否认某些特例。现今ACM ICPC中有一类题目是直接的数学题,与其说是考察学生的程序设计和算法,不如说是考察数学水平。这类数学问题大多涉及组合数学、数论等知识,没有接触过这些知识的人很难完成这样的题目。另外,良好的抽象思维及严密的逻辑思维也能反映出这个人在数据结构和算法上的潜力。因此,学校可以通过测试学生数学水平和逻辑抽象能力选拔队员,也可以根据每个人的性格特点或思维习惯辅助选拔。

队员经过选拔后面临的问题是怎样进行训练。因为教师的参赛经验并不丰富,所以可行的办法是高年级带低年级,形成一个团队,队员之间鼓励相互学习,相互分享知识和经验。不仅让学生学到知识,更要让他们知道要学什么,怎样学以及自己怎样提高,学会解决问题,独立探索,吃苦耐劳,这对学生的发展和综合能力的提高是大有裨益的。我们以上总说数据结构和算法,而不直接说ACM ICPC,因为ACM ICPC从根本上还是一个竞赛,而竞赛不免会包含很多不确定因素,队员的成绩未必就代表队员的水平,所以平时的心理素质训练也是不可或缺的。

如何培养参赛选手是第二个要解决的问题。大多数参赛选手大学前没有接触过这些知识,所以他们首先要适应ACM ICPC编程比赛。ACM ICPC比赛追求的是速度、准确、创新,这就要求选手的思维和编程速度都很快。平时的训练大家不仅要攻克难题,提高能力,还要适当模拟正式比赛,让选手能够适应正式比赛的紧张气氛。比赛策略的训练也很重要,如三个人的配合问题、题目完成的顺序问题等。选手的知识储备不仅要广博,而且要有自己的“杀手锏”,即每个人都要有自己的专长,达到一看这些知识的题目就能立即完成的水平。当然,随着大赛的普及,题目的类型不再可以明确区分,这就更要求选手有足够多的知识储备、足够强的个人能力及一定的分析融合能力。在题目的选择上也应有取舍,选择有研究价值的题目训练。

在ACM ICPC中,学生是永恒的主角,他们承担培训、集训、宣传、选秀等工作,教师永远是做引导、服务工作的配角。很多学校已经形成了以老带新的传统,一年一年下来,形成一种机制,这正是ACM ICPC培养学生综合能力的核心,而在这种机制中,老队员和新队员都得到了很好的自我锻炼和提高的机会。

4我校将ACM竞赛融入教学

和体育运动类似,要想在ACM ICPC中获得好成绩,必须有广泛的群众基础,尽可能让更多的学生受益,提高学生的整体编程水平。从2004年起,哈工大便将ACM ICPC引入计算机学院本科一年级的程序设计课程中,激发学生对ACM ICPC的兴趣,吸引更多学生投身到此项活动中。

我们的具体做法是:

(1) 将ACM ICPC题目作为实验,加大实验成绩比重

在百分制评定中,将实验(共10次)成绩的比重加大到50分,督促学生重视每次实验。实验题目以ACM ICPC题目为主,有一定的实际背景,但都没有标准答案,学生要根据所学知识做出解答,每个题目的解决方法有很多。

多数题目的解决过程是这样的:首先使用最常规、最自然的思维方式解决实际问题,然后考虑时间效率较低或空间占用较大的情况,如果新方法不是最好的,还有没有更好的方法呢?这往往需要花费更多的时间和精力,也是学生收益最多的地方。对于教学管理来讲,这种具有明确输入、输出形式的实验可以由机器自动评判成绩,减轻了教师的工作量,使这项工作得以顺利开展。

为了保证学生实验的质量,避免雷同情况的发生,我们引入了Moss(Measure of Software Similarity)雷同判别程序,促使学生通过自己的思考和努力独立完成实验。另外,如何从解题思路、程序风格等方面细致评判学生的实验完成情况,给出个性化的实验评语,也是亟待解决的一个问题。为此,需要大量的学生TA(Teaching Assistant)辅导实验,即每半个班级安排一名学生TA,对其负责的学生进行实验课上实时答疑,课下登录课程论坛随时答疑。同时,学生TA还对所负责同学的实验进行评判,做到仔细阅读每行代码,公正评判,给出详细的扣分原因及程序改进建议。学生TA由编程经验丰富的博士生、硕士生甚至本科生担任。

学生实验情况调查显示,39.4%的学生认为“作业偏难,需要花费大量精力完成,但是从中收获很多”,有35.2%的学生认为“作业难度适中,较好地锻炼了编程能力”。可见,大部分学生对这种实验方式表示认可,并通过实验锻炼了实际动手能力。

(2) 培养拔尖人才,给学有余力的学生“吃小灶”

仅通过完成实验培养出优秀的ACM ICPC选手困难较大,因此我们用多种精神和物质奖励刺激拔尖人才的快速进步。完成大量的题目是取得优异成绩的基础,所谓熟能生巧,量变引起质变。我们引入竞争机制,将学生在HOJ(HIT Online Judge)上的做题数进行实时排序,如图1所示,学生做题数目稳步增长,最终形成一种你追我赶的良好态势。为了保证充足的上机时间,刺激学生力争上游,我们给排名靠前(60名)的学生提供免费上机机会,还向综合表现优异的同学发放编程和算法方面的书籍。

5结束语

参与ACM竞赛不仅使学生提高了计算机编程水平,提升了综合素质,还促进了相关课程的教学改革,提高了教学效果。目前,我校开展这项赛事活动还处于起步阶段,局限于少数院系的参与,今后将在全校范围内推广这项活动,让更多的学生参与其中,得到锻炼提高。