基于ACM-ICPC模式的算法分析与设计课程的建设

◎张文达

针对算法分析与设计课程的教学实际，文章分析了该课程教学模式的局限性和传统的实践教学中存在的问题，提出将ACM-ICPC竞赛模式引入该课程教学的观点，开发了一个基于ACM-ICPC模式的程序测评系统，并应用在算法分析与设计课程的实践教学中，取得了良好的教学效果。

一、引言

算法分析与设计是面向设计的计算机专业核心课程，主要通过对经典算法的学习和研究，使学生掌握算法的设计策略和算法复杂度的分析方法，培养学生分析和解决实际问题的能力。该课程教学内容繁多，涉及的知识面很广，主要内容包括算法分析方法、递归算法、分治算法、贪心算法、动态规划、回溯算法、分支限界、近似算法、概率算法等经典的算法，覆盖了多项式、数论、矩阵、集合、图论、几何、模式匹配等数值和非数值计算问题。

目前，各高校该课程分配的课时普遍较少，教学方法也都是以讲解为主，即使设置了实验课，在实践环节通常也只是一味地对算法进行验证，很少考虑到算法的运行效率分析、测试数据的规模以及实际的应用场景。而且，在传统实践教学中，学生抄袭代码的情况严重，不能有效提高学生的实践能力，无法体现实践教学的真正作用。在这种教学模式下，学生缺乏对实际问题进行抽象和分析的能力，思维创新和实践能力难以得到有效提高。本文结合我校实际教学情况，将ACM-ICPC竞赛模式与算法分析与设计课程的建设相结合，达到了良好的教学效果。

二、课程现状

该课程的开设是面向计算机科学与技术专业大三的学生，学生在学习该课程之前，已经学习了C／C++程序设计、数据结构、Java程序设计、高等数学和离散数学等课程，但是由于学生欠缺良好的计算思维，逻辑分析能力相对不足，编程实践能力仍然比较弱，学生在学习该课程时倍感吃力。目前我校在算法分析与设计课程信息化建设方面有许多不足，主要体现在以下几点：

1.课程之间的联系不够紧密。算法分析与设计课程与其他课程的关系是很密切的，如数据结构，它们之间相互作用，从而提高计算机专业学生的实践能力，为学院培养高素质的应用型人才。

2.教学资源不足。当前课程并没有信息化系统的支持。学生只能通过网络搜索所需的资源，获取教师的P跗也只能通过教师，教学资源没有实现整合和共享。

3.编程竞赛平台不多。在参加或举办程序设计类竞赛方面，学生只参与了国内的"蓝桥杯"这一个程序设计类竞赛，学院内部并没有开展此类竞赛活动。

三、ACM-lCPC模式下的课程建设

1.ACM-ICPC在课程中的作用。

ACM国际大学生程序设计竞赛（ACM-ICPC）是由国计算机协会（ACM）主办的，是一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。经过40多年的发展，ACM-ICPC已经发展成为最具影响力的大学生计算机竞赛。竞赛时间为5个小时，重点考察选手的算法和程序设计能力。选手通过网络提交程序，评委负责将结果（正确或出错的类型）通过网络尽快返回给选手。

将ACM-ICPC竞赛模式引入算法分析与设计的教学中，可以激发学生的主动学习积极性，鼓励学生勤思考、多实践。相对于传统的实践教学具有以下几方面的优势：（1）在网上进行实践教学，没有时间和空间的局限性。教师可以在测评系统中对同一个实验项目布置多个难度各异的题目，学生可以根据自己的掌握情况。从易到难选择合适的时间完成训练题目。（2）对创造校园的学术交流氛围有良好的促进作用。学生在课余时间通过在网上提交自己编写的程序源代码，自主进行算法和程序的交流，有利于培养学生的学术修养。实现学生与教师、学生与学生之间的交流和互动。（3）减轻教师实践教学时的指导负担。传统的实践教学在机房进行，教师需要在整个机房进行巡视，为有疑问的同学进行解答。而ACM-ICPC竞赛模式的在线测评系统可以对学生提交的作业进行评测，大大减轻了教师的负担。

2.测评系统的设计与开发。

该系统基于Java EE，是一个程序在线评判、程序设计竞赛和交流的平台。可不断扩展题库供学生进行程序设计练习，系统自动对提交的程序源代码进行编译、运行并评判程序的正确性。系统可供课程日常训练和网上实时竞赛使用，也具备站内交流和站内全文检索功能。系统有两个版本的评判模块，一个基于纯Java，另一个基于C++，两者均可在Windows平台下运行。学生在系统提交程序后，系统先将程序保存至数据库，再写入评判队列，由系统评判内核进行编译、运行并返回结果。返回的结果类型有AC、WA、Rr砸、TLE、PE、MLE、CE。每个题目可能有多个测试数据，内核在读取主系统传递给它的参数后，编译程序，生成可执行文件，之后对于每个测试数据运行一次"验证测试数据"的操作。

系统用户分为四种：普通用户、高级用户、论坛版主及系统管理员。任何学生都可注册成为普通用户。普通用户可以做练习题，提交程序并得到系统的评判和结果反馈；可以根据程序提交情况参与用户排名：拥有并可使用自己的站内信箱；可以查看、保存和管理自己提交的源代码；可以在论坛发帖，参与问题讨论；可以参加程序设计竞赛，并查看比赛结果和统计数据。任何解答题目超过20道的普通用户。可自动升级为高级用户。高级用户拥有普通用户的所有权限。还可以上传题目和测试数据，并可对自己上传的题目进行管理、修改等。高级用户上传的题目，经管理员确认后，便可加入系统的正式题库。系统在题目信息中记录上传题目者的相关信息。论坛版主为系统管理员授予，拥有普通用户的所有权限，同时对相应的论坛板块拥有管理权。系统管理员管理系统的日常运行，拥有所有的管理权限，需要对题目和测试数据进行筛选，检查系统运行情况，组织程序设计竞赛。

3.课程设置。结合我校实际情况，我们在算法分析与设计课程的实践教学内容上设计了递归算法、分治算法、动态规划算法、贪心算法、回溯算法、分支界限算法共6个经典算法的实验项目。由于实践教学课时有限，传统的教学方式每个实验项目只能设计2-3道题目。引入ACM-ICPC模式之后，学生可以利用课余时间通过网络完成程序设计，每个实验项目题量增加到6-8个，题目难度各异，学生可以根据自己的知识掌握程度和能力选择合适的时间完成。较容易的题目可以先完成，具有一定的综合性、难度较大的题目，可以在有相当的训练量之后完成。这种循序渐进的训练方式，更有利于学生对算法原理的理解和掌握，也更有利于形成由浅入深的思维模式，有效提高学生的分析问题、解决问题的能力。

四、课程建设实践成果

实施ACM-ICPC竞赛模式的程序在线测评系统以后，学生的学习积极性得到了较大的提高。学生对经典算法的掌握程度和实践能力也大大提高了。学生在各种全国性考试和比赛中取得了较好的成绩。学生的自主学习能力有所提高，教师在实验课上的空闲率由原来的0.4%增长33.3%，学生对教师的依赖程度大大降低。

结语：基于ACM-ICPC模式的算法分析与设计课程将理论学习与实际操作相结合，注重培养和提高学生分析和解决实际问题的能力，以公平、公正、公开的竞争形式带动学生的自主学习，调动学生交流和研究的积极性，为课程的开展提供了良好的氛围。在后续的研究和开发中，我们将把基于ACM-ICPC模式的程序测评系统扩展到全系范围内的更多的程序设计类课程。