《ACM程序设计》教学大纲

一、 课程基本信息

课程编号:

课程英文名称:ACM programming

授课对象:计算机科学与技术专业

课程类型（指公共基础课、专业必修课、专业选修课等）:专业选修课

建议学时:48

学分:3

与相关课程的衔接:数据结构、离散数学、高级程序设计

考核方式:考查

二、 教学目标和要求

《ACM程序设计》是专门培养ACM国际大学生程序设计竞赛思想，课程详细讲解了ACM国际大学生程序设计竞赛(ACM/ICPC)编程、调试方法，以及提高时间、空间性能的策略。第1章讲解了ACM程序设计入门知识；第2章讲解了字符串处理问题；第4章讲解了简单数学问题的处理；第8章讲解了高级数据结构并查集；第3、5、6、7章分别讲解了常用的ACM程序设计基本编程技巧，包括蛮力、贪心、分治递归、动态规划等；配备了原版ACM竞赛题的解题思路、编程参**和英文题目中文翻译。

通过本学科的教学，使学生能掌握ACM竞赛的基本知识，掌握与了解计算机专业英语、高级数据结构、离散数学、初等数论、数值计算、计算机算法、人工智能、时空权衡、图算法、计算几何等等内容。并能综合运用这些知识，利用程序语言进行ACM竞赛题目的设计与编写。

三、 教学内容、教学方式与课时分配

（一）ACM程序设计概述

教学基本内容:

1、ACM竞赛

2、GDCPC竞赛

3、蓝桥杯大赛

4、信息学奥赛

5、入门基础与技巧

教学方式:多媒体教学、讲授演示、讨论启发及课后OJ练习

（二）字符串处理

教学基本内容:

1、字符串函数

2、字符串操作

3、字符串匹配

教学方式:多媒体教学、讲授演示、讨论启发及课后OJ练习

（三）蛮力法与简单模拟

教学基本内容:

1、蛮力法的基本原理

2、查找问题中的蛮力法

3、排序问题中的蛮力法

4、图论问题中的蛮力法

5、简单模拟问题

教学方式:多媒体教学、讲授演示、讨论启发及课后OJ练习

（四）简单数学问题处理

教学基本内容:

1、数学模拟

2、数论

3、几何

4、组合

教学方式:多媒体教学、讲授演示、讨论启发及课后OJ练习

（五）贪心算法

教学基本内容:

1、贪心法基本原理

2、背包问题

3、图论问题中的贪心法

教学方式:多媒体教学、讲授演示、讨论启发及课后OJ练习

（六）分治与递归法

教学基本内容:

1、分治基本思想

2、递归基本思想

3、排序问题中的分治递归

4、查找问题中的分治递归

教学方式:多媒体教学、讲授演示、讨论启发及课后OJ练习

（七）动态规划法

教学基本内容:

1、动态规划法的基本思想

2、图论问题中的动态规划法

3、查找问题中的动态规划法

教学方式:多媒体教学、讲授演示、讨论启发及课后OJ练习

（八）并查集

教学基本内容:

1、并查集基本原理

2、并查集基本操作

3、并查集的优化

4、图论问题中的并查集

教学方式:多媒体教学、讲授演示、讨论启发及课后OJ练习

四、 实践环节

按照人才培养计划，本课程在学时内无实践环节。但本课程实践性较强，需要学生在课外OJ平台进行在线练习。

五、 教材

吴涛，张立敏，《ACM程序设计基础讲义》，自编教材讲义，2014.12。

六、 参考资料

（1）郭嵩山，崔昊，吴汉荣，陈明睿著，《国际大学生程序设计竞赛辅导教程》，北京大学出版社，2001年12月第1版。

（2）俞经善，《ACM程序设计竞赛基础教程》，清华大学出版社，2010年10月第1版。

七、 必要的说明

① 本课程选用教材为自编文字教材讲义，是学生学习的主要用书，它是教和学的主要依据。

② 为确保本课程教学活动正常有效地开展，保证课程的教学质量，组织由开设本课程的教师开展教研活动，不断提高教学质量。布置课程的教学任务，研究落实课程实施方案。

③ 本课程是一门实践性较强、内容有深度的综合课程，因此，要求教师认真钻研教学大纲，认真备课，仔细批改作业并对作业中存在的问题认真讲解。

④ 本课程由于学时所限，特别没有设置实践学时，因此，学生必须多做练习题来加深理解和掌握，从而达到消化、掌握所学知识的目的。