以ACM-ICPC竞赛为依托的算法设计与分析课程改革

林玉娥 梁兴柱

摘要：针对提高算法设计与分析课程教学效果的问题，本文给出了以ACM-ICPC为依托的算法设计与分析的课程改革方法.本文通过分析算法分析与设计课程教学中存在的问题,提出了建立兴趣小组,构建ACM-ICPC在线测评系统,以及新的考核方式促进学生自主学习的教学方法。改革方法能够有效地挖掘学生的潜能，在实际的教学中取得了良好的教学效果。

关键词：算法设计与分析；ACM-ICPC；教学改革；在线测评系统

中图分类号：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

算法设计与分析是计算机科学与技术专业、软件工程等专业的必修课，课程具有很强的理论性，课程涉及的领域广、应用性强，不能机械记忆，而是要理解性地学习掌握它的理论基础，并灵活运用，这就要求学生有很扎实的数学和一定的程序设计能力。而课程本身又具有极强的可扩展性、可开发性，学生必须善于思考，勤于练习，才能真正掌握[1]。

ACM国际大学生程序设计竞赛（ACM International Collegiate Programming Contest, ACM- ICPC）是由美国计算机协会（Association of Computer and Machinery, ACM）主办的一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛，现已发展成为最具影响力的大学生计算机竞赛[2]。近年来，ACM-ICPC在我国得到了大规模的推广，我国上海交通大学获得三次总冠军，浙江大学在2011年获得总冠军。各知名高校均成立ACM-ICPC训练基地，上海交通大学、哈尔滨工程大学等还选拔综合能力强的学生单独成立ACM实验班，以培养高精尖IT人才。竞赛涵盖的范围包括：计算几何，数论，组合数学，搜索技术算法，动态规划，图论和其他。可使用的计算机语言有C/C++，JAVA[3]。因此尝试了将竞赛与教学结合在一起的教学改革方案，取得了较好的教学效果。

1算法设计与分析课程现存的问题

1.1适合教材匮乏

考虑到实际学时，多数的算法设计与分析课程配套的教材普遍偏难，公式多，详细讲解少，内容枯燥。书中的代码基本为伪代码，没有一定编程基础，动手能力差的学生很难实现，一定程度影响学生的积极性。

1.2重理论，轻实践

一方面，算法设计课程与分析课程理论课时多实验课时少；另一方面，受到传统教学理念的影响,教学条件和实验条件的限制。所以，教师在教学过程中更加重视基本理论和原理的讲授，没有很好地研究如何将有限的实验时间利用起来培养学生的应用能力，忽略了对学生程序设计能力和分析问题能力的培养，结果使学生陷入枯燥的理论和数学公式中，造成理论和实践相脱节，实际教学实效较差。

1.3学生应用能力差

学生在学习时，常常能明白理论，但是使用算法解决实际问题的能力很弱。究其原因，一方面，学时少，内容多，举例较少，没有感性认识；另一方面，学生没有编程实现程序，对算法的理解还是没有吃透。

2算法设计与分析课程改革

2.1建立兴趣小组，提升学习兴趣

爱因斯坦说过：“兴趣是最好的教师”。没有兴趣必然无法学习好课程。成立ACM兴趣小组，鼓励和组织学生参加，培养创新精神和能力，在实践环节中培养和发现优秀人才。通过周末论坛、赛前讲座、月赛、校赛、寒暑假集训等活动，学生不仅得到锻炼，也为参加相关竞赛打下了良好的基础。

2.2强化课堂讨论教学环节

引入参与式教学。模仿ACM-ICPC竞赛模式,将3至4名学生分成一个小组，让他们自己选择教师指定的题目,给他们充分的时间进行精心准备,让他们就此在课堂上为其他同学进行讲解。在学生分组时，将基础好的学生和基础差的学生编在一组，利用基础好的学生带动基础差的学生学习，增强了差生的自信心。通过课堂讨论锻炼了学生的自学能力，同时也培养了学生的团队合作意识。在实际教学过程中，学生在诸多方面提出了创造性想法,充分展现了自身的思维活力。

2.3以ACM-ICPC在线测评系统为平台实践教学

实践教学仿照ACM-ICPC竞赛模式，把它组织成一次比赛。设定好开始、结束时间，以及每次错误提交的罚时时间。题目一般每次4題与理论课程相关的知识。学生可以随时看到自己做了几题，在班级排名如何。这样学生在一个竞赛的环境中上机实验，有一定的紧张感，会充分发挥各自的潜力，杜绝了在上机时上网聊天或玩游戏，因为这样他就完不成任务。将课后作业和实验移植到在线测评系统，课时安排课内12学时，课外20学时，鼓励学生在线做题。在线测评系统特别能锻炼学生的计算机动手能力，通过做题,学生普遍反应计算机动手能力有了很大的提高。曾今枯燥的离散数学、图论、数值分析等课程，一旦与ACM竞赛内容结合，学习起来就很有动力，也很轻松[4]。

为了做到基于ACM-ICPC的算法设计与分析的成功改革，首先必须保证实践平台ACM-ICPC在线测评系统能稳定运行。ACM-ICPC在线测评系统实现可以学校自行开发或者使用已有成功在线测评系统。现今，国内规模较大、开放性较好的是杭州电子科技大学的在线测评系统。系统可以为外校教师提供ACM竞赛，提供在线算法设计、程序设计课程考试。

2.4改革考核形式

传统的高校该课程的考核基本上分为平时成绩（20%～30%）和期末考试（70%～80%）。这样的考核方式偏重学生的记忆能力，忽视平时的学习过程，很难锻炼学生实践能力。课程的考核应注重算法设计策略的灵活应用及效率分析，而不是死记硬背。

课程的考核方式改革如下：课程考核分为三部分，分别为课堂讨论考核(10%)、上机ACM竞赛模式实践考核（50%）和期末闭卷笔试(40%)。

课堂讨论考核主要考核学生的学习积极性，包括对提问的回答、学生提问及讨论，给出相应的分数。ACM竞赛模式的实践考核分为平时实验成绩（50%）和期末综合实践成绩（50%），均为开卷考试，学生可以翻书查阅相关资料，考核学生实际编程能力、程序调试和解决问题能力。期末闭卷考试主要考核学生的算法时间和空间的效率分析，侧重工科学生的分析问题能力。

3结束语

以ACM-ICPC竞赛为依托的算法设计与分析课程改革，打破传统的算法设计与分析课程教学模式和考核方式，将理论教学和实践教学充分结合，注重培养学生的分析问题、解决问题、编程能力，引入竞争、讨论、团队机制，激发了学生自主研究性学习的兴趣。通过课程改革，取得了明显的效果，提高了教学质量和教学水平。

参考文献：

[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].合肥工业大学学报:社会科学版,2008 (6):133-137.

[4]杨春明.算法分析与设计任务驱动教学模式改革与实践[J].计算机教育,2009 (19):97-99.