基于ACM模式的离散数学实验探究

陈宇　臧美英　李林辉

【摘要】离散数学是计算机及相关专业核心课程，本文在介绍离散数学、ACM及ACM在线评测系统的基础上，提出了基于ACM模式的离散数学实验探究，探讨了教学方式与手段及实验教学的改革。这种改革将提高离散数学课程的教学质量和教学水平，有助于培养学生的抽象思维、逻辑思维、心理素质及团队协作能力。

【关键词】离散数学 实践教学 ACM

【中图分类号】G642.0 【文献标识码】A 【文章编号】2095-3089（2015）04-0032-02

The reform and exploration of Discrete Mathematics practice teaching model based on ACM

Chen Yu，Meiying Zang， Linhui Li，

（School of information and computer engineering， Northeast Forestry University，Harbin 150040， China）

【Abstract】 Discrete Mathematics is the core courses of the computer and the related majors， This article describes the basic Discrete Mathematics， ACM and ACM on-line evaluation system ，in addition ，it puts Discrete Mathematics practice teaching reform measures based on ACM model ，it explores the ways and means of teaching and reforms the experimental teaching .This reformation will improve the teaching quality and teaching level of the Discrete Mathematics ，it can help to cultivate students abstract thinking ，logical thinking ，psychological quality and team cooperation ability.

【Key words】 Discrete Mathematics； Practical Teaching； ACM

1.ACM及ACM在线评测系统简介

ACM國际大学生程序设计竞赛是由美国计算机协会（ACM）主办的，简称ACM / ICPC，自从1977年开始至今已经连续举办31届[1]。其宗旨是提供一个让大学生向IT界展示自己分析问题和解决问题的能力的绝好机会，让下一代IT天才可以接触到其今后工作中将要用到的各种软件，展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。ACM成立于计算机诞生次年，是目前计算机学界中历史最悠久、最具权威性的组织。该赛事分高校校内赛、地区赛、大洲预赛和世界决赛四个级别。每一届的赛事在秋季学期举行各大洲预赛，在春季学期举行世界总决赛。ACM/ICPC比赛的赛题有实际背景，趣味性和实用性较强，分不同水平的题，考查的知识范围较全面并具有层次性。而且绝大部分题没有定解，留有广阔的思维空间，有益于培养创造性。学生在激烈的竞赛中感受数学思维与算法艺术的结合之美，提升编程能力和解决实际问题能力[2]。

自2006年我校第一次参与ACM大赛黑龙江省赛至今每年都组织团队参与比赛，并取得不错成绩，并成立ACM实验室，让学生以精通编程为荣，让程序编织梦想，形成了一个积极向上的自主学习氛围，一些高校已经将ACM在线评测系统运用到计算机课程的教学环节之中并取得了不错的效果。

我校ACM在线评测系统界面如图一所示：

图1.ACM/ICPC在线评测平台

它是集程序设计竞赛、竞赛训练、课程实验、平时练习于一身的网上实时提交系统[3]。该系统提供了大量供学生练习和竞赛的竞赛题目，学生在线提交解决相关练习和竞赛题的程序代码，系统可以自动编译程序代码，生成可执行文件，并根据已存储的测试用例，从程序的正确性、程序运行总时间、耗费内存、单用例执行时间、程序返回结果等各方面评测程序代码，并精确返回各方面的评测结果。不但支持C、C++、PASCAL以及JAVA语言的编译，还定义了一套具有充分可扩展性的编辑器扩充规则，可以在不修改系统任何实现的情况下，通过管理配置文件增加系统可以支持的语言和编译器。ACM在线测评系统功能模块图如图二所示：

图2.ACM评测系统功能模块图

ACM在线评测系统性能上的稳定快速为计算机专业各门编程课程提供有效的实验环境。

2.结合ACM模式探索离散结构课程实践教学

“离散数学”课程是计算机专业核心基础课程之一，是由数理逻辑、代数结构、集合论、图论四个部分组成[4]。它是把非连续对象的数量和空间关系作为研究对象的若干数学分支的总称。随着计算机技术的发展，离散数学的地位逐渐提高。该课程为数据结构、操作系统、数据库原理、编译原理、人工智能等专业课程提供必备的基础知识，对离散数学的学习无论是对学生们学习后续的专业课程，还是对以后参加工作，都有着重要的意义。通过对离散数学的学习有助于培养学生的学科素质，使学生的抽象思维能力和严格逻辑推理能力有所提高。但由于其内容多、理论性强、抽象、解题思路严谨，传统的离散数学教学不能提高学生的学习兴趣，教学效果不理想。ACM竞赛拥有着较长的历史，它的方法成熟，把ACM模式应用于离散数学的教学过程中，通过运用现代教学技术改进传统教学方法是非常必要的。

2.1 建立基于ACM的离散结构教学模式的意义

1.ACM模式是让学生三个人共用一台电脑，通过团队合作在短时间内解决问题的方法。有利于提高学生的个体思维能力，增强学生们的团队合作意识，增进学生们之间的学术交流。

2.学生们通过建立的基于ACM竞赛的网络教学平台进行学习，每个人都可以注册ID，在平台上学习离散数学的相关课程，不受时间和地域的限制。

3.通过ACM模式竞赛式学习，校园之间形成竞争，为此，学校会营造浓厚的学习氛围，在课余时间对学生进行培训，旨在让学生在课余时间对离散数学知识进行钻研 学习。

4.在离散数学课程的学习中，计算思维是学生们学习的一大难点，计算思维的本质是抽象与自动化，而这些恰恰是ACM竞赛必备的素养。把ACM模式应用于离散数学的教学中，培养学生的计算机理论修养，提高学生们的实践能力，学以致用，通过实践使学生真正掌握离散数学的丰富知识和算法的精髓。

2.2基于ACM的离散结构教学模式的设计

ACM模式可以开阔学生的视野，培养学生的实践能力，团队合作能力，增强创新意识[5]。基于ACM模式的离散数学实践教学设计分为三个层次：基础型实验、综合型实验和创新型实验具体实现方法如下：

（1）基础型实验，主要内容是链表队列或堆栈，掌握命题逻辑中的真值表、联接词、主范式，进行真值计算、关系闭包计算，计算两点间长度为m的路的数目等。要求学生掌握基本的离散结构和方法，能运用离散结构描述实际对象并对其进行处理，有较好的问题分析和解决能力。

（2）综合型实验，主要内容有商品营销佣金问题、学生管理系统、物资管理系统穿衣排序、中国邮路问题、巡回售货员问题等[6]。需要学生具体掌握算法分析与设计，掌握数理逻辑、集合与关系理论、图论的知识，具有一定的综合素质，有对知识的实际运用能力。

（3）创新型实验，需要学生掌握基本的软件重用方法，运用面向过程和面向对象的设计方法。主要内容有创新的设计完成测谎仪、电梯系统、TSP问题、自动售货系统、环游世界问题电报码设计、着色问题、校园导游系统等问题。其中程序的测试采用ACM的模式进行，保证软件测试的质量。

创新型实验这一层次要求较高，对那些学有余力、创新性思维强、兴趣浓厚的学生，提供了一些难度较高的项目，有利于学生申请并完成本科生的科技创新项目，让他们初步形成软件从事者应具备的工作作风和严谨态度。

3.基于ACM的离散结构教学模式改革措施

（1）案例教学

案例教学通过模拟或重现实际生活中的某些场景，需要学生把自己纳入案例场景，通过研讨的方式来进行学习。离散数学涉及知识点多并且具有一定难度，学生很难对它产生兴趣。教师可以用ACM竞赛的形式展现课程内容，模拟ACM竞赛环境，从而提高同学们的学习兴趣，学习致用，使得学生能够充满热情地把每一个知识点理解透彻。

（2）作业形式考核

在学完一章节后，教师要布置一定的作业让学生课外完成。要求每个学生在规定时间内独立完成作业，提交作业。教师根据学生的课外作业制订考核标准。根据作业考核标准，教师给学生的作业予以考核评判。最后，根据每次作业的评判，教师最后给予综合评判。

（3）基于 ACM 模式的实验教学

离散数学的内容很多，为了解决实际教学中出现了课时少和教学内容多的矛盾，提高学生学习兴趣，加入实验教学环节。离散数学上机实验应侧重编程思想的掌握和运用，利用 VC++、Java 或其他语言完成这些实验，做到理论与应用的完美结合[7]。实验课程的加入帮助学生对相应知识点的深入理解与消化，并且引导学生运用所学离散数学知识分析和解决实际问题，进一步加深对离散数学在计算机解决问题中重要作用的理解，提高软件开发能力。将高度抽象的离散数学理论与编程等结合起来，能够极大地提高学生学习离散数学的积极性，增强解决实际问题的信心。

（4）跨學科的实训

在实训环节上，除了让学生做一些实验题目外，同时对学生在数据结构、JAVA、C++等其他课程上进行实训，运用不同的语言，与这些课程结合起来来完成教学内容。

4.结束语

ACM模式的实践教学可以夯实学生的程序设计基础，对于离散结构的学习有着重要意义。它把对理论知识的学习与实际的应用有机的结合起来，注重培养学生的编程能力，训练学生的解题思维，对于培养学生的创新能力具有很大的帮助。通过对离散结构实验教学的改革，取得了显著的效果，提高了教学质量和教学水平，对软件开发类课程的教学改革有一定的示范作用。

参考文献：

[1]金保华，闫红岩，张晓娟，徐红霞.基于ACM/ICPC的程序设计语言的教学改革与实践[J].中国电力教育，2011，20：79-80.

[2]武建华.基于ACM模式的数据结构实践教学改革与探索[J].计算机教育，2007，

24：114-116.

[3]房明磊，蒋利华.离散数学教学的探讨与思考[J].新西部（下半月），2007，01：239-240.

[4]肖利芳，段梅.离散数学教学模式的改进与创新[J].中国电力教育，2014，11：129-131.

[5]陈博.基于ACM模式的教学方案研究[J].咸宁学院学报，2010，09：131-132.

[6]常子楠.基于ACM模式的程序设计类课程实践教学探索[J].计算机教育，2010，1 6：144-146.

[7]何立群，廖慧芬.基于ACM模式的算法教学的探索[J].电脑知识与技术，2009，34：9 765-9766.

基金项目：

中央高校基本科研业务费专项资金项目（2013CBQ03）；黑龙江省教育厅科学技术研究项目（12513016）；黑龙江省自然科学基金项目（F201347）；哈尔滨市科技创新人才专项资金项目（2013RFQXJ100）；东北林业大学重点课程建设基金；