ACM程序设计

课程编号：CS0060022

课程名称：ACM程序设计                   英文名称：ACMProgramming

学分/学时：1/16                         课程性质：公共任选课

适用专业：理工类各专业                  建议开设学期：2

先修课程：程序设计基础，C语言程序设计   开课单位：计算机学院

一、课程的教学目标与任务

本课程作为ACM/ICPC竞赛的入门课程，首先介绍ACM/ICPC竞赛历史、赛制、规则等基本知识，然后通过大量例程讲授ACM/ICPC竞赛中用到的算法，包括：枚举、递归、搜索、贪心、数论、图论等。课程通过对例程的分析及对数据结构、算法的讨论，着重培养学生解决问题的思维方式，并在实际的问题的求解过程中提高解决问题的能力和对问题的应变能力，激发学生的学习兴趣，为后续课程的学习打下基础。

二、课程具体内容及基本要求

（一）ACM基础（1学时）

       数据结构与算法相关概念；ACM/ICPC简介、赛制、规则相关内容；ACM/ICPC意义及对参赛者的基本素质要求；ACM/ICPC涉及到的知识内容；ACM/ICPC例题介绍；ACM/ICPC学习资源。

1. 基本要求

（1）理解数据结构与算法相关概念

（2）了解ACM/ICPC的发展历史及现状。

（3）了解ACM/ICPC的赛制、规则及意义。

（4）了解ACM/ICPC涉及到的编程知识。

（5）掌握ACM/ICPC题型。

2. 重点、难点

重点：ACM/ICPC的赛制、规则；ACM/ICPC的编程知识；ACM/ICPC题型。

3．作业及课外学习要求

通过网络等手段学习数据结构与算法概念；了解ACM/ICPC竞赛相关内容；在poj.org在线答题系统上注册个人ID。

（二）基本数据结构（3学时）

基本数据结构的概念、特点、实现及例题示例。

1. 基本要求

（1）掌握线性表数据结构的概念、特点及实现方式。

（2）掌握树数据结构的概念、特点及实现方式。

（3）掌握图数据结构的概念、特点及实现方式。

（4）掌握并查集的主要操作。

2. 重点、难点

重点：线性表、树、图、并查集。

难点：线性表、树、图、并查集。

3. 作业及课外学习要求：

在poj.org上完成题目，参考题目：POJ1208 The Blocks Problem；POJ1363 Rails；

（三）高精度运算（1学时）

高精度数据的表达及存储方式；高精度数据的运算方法；高精度数据运算效率的改善。

1. 基本要求

（1）掌握高精度数据的表达及存储方式。

（2）掌握高精度数据的运算方法。

（3）掌握改善高精度数据运算效率的方法

2. 重点、难点

重点：高精度数据的表达及存储方式；高精度数据的运算方法；高精度数据运算效率的改善。

难点：高精度数据的表达及存储方式；高精度数据的运算方法；高精度数据运算效率的改善。

3. 作业及课外学习要求：

在poj.org上完成题目，参考题目：POJ1001 Exponentiation；POJ1131 Octal Fractions；POJ2109 Power of Cryptography；

（四）简单算法介绍（3学时）

模拟算法、枚举算法、贪心算法。

1. 基本要求

（1）掌握模拟算法。

（2）掌握枚举算法。

（3）掌握贪心算法。

2. 重点、难点

重点：模拟算法、枚举算法、贪心算法。

难点：模拟算法、枚举算法、贪心算法。

3. 作业及课外学习要求：

在poj.org上完成题目，参考题目：POJ1042 Gone fishing；POJ1573 Robot Motion；POJ1222 Extended Lights Out；

（五）广度优先搜索（2学时）

状态空间概念、广度优先搜索。

1. 基本要求

（1）理解状态空间的概念。

（2）了解搜索的一般方法。

（3）掌握广度优先搜索方法。

2. 重点、难点

重点：广度优先搜索方法。

难点：广度优先搜索方法。

3. 作业及课外学习要求：

在poj.org上完成题目，参考题目：POJ1915 Knight Moves；POJ1745 Divisibility；

POJ1324 Holedox Moving；

（六）深度优先搜索（2学时）

深度优先搜索、回溯。

1. 基本要求

（1）掌握深度优先搜索方法。

（2）掌握回溯。

2. 重点、难点

重点：深度优先搜索、回溯。

难点：深度优先搜索、回溯

3. 作业及课外学习要求：

在poj.org上完成题目，参考题目：POJ3239 Solution to the n QueensPuzzle；POJ1564 Sum It Up；POJ2558 GeneticCode

（七）动态规划（4学时）

动态规划的实现。

1. 基本要求

（1）理解动态规划的基本概念。

（2）掌握动态规划的步骤、状态转移方程及递推公式。

2. 重点、难点

重点：动态规划的步骤、状态转移方程及递推公式。

难点：动态规划的步骤、状态转移方程及递推公式。

3. 作业及课外学习要求：

在poj.org上完成题目，参考题目：POJ1163 The Triangle；POJ1050 To the Max；POJ1157 LITTLE SHOP OF FLOWERS；

三、教学安排及方式

总学时 16 学时，其中：讲授 16 学时，实验 0 学时，上机 0 学时，实践 0 学时，研讨 0 学时，线上 0学时。

序号

课程内容

学时

教学方式

1

ACM基础

1

讲授

2

基本数据结构

3

讲授

3

高精度运算

1

讲授

2

简单算法介绍

3

讲授

3

广度优先搜索

2

讲授

4

深度优先搜索

2

讲授

5

动态规划

4

讲授

注：教学方式包括面授和线上，其中面授包括： 讲授、实验、上机、实践、研讨五种。

四、考核及成绩评定方式

最终成绩由平时作业成绩、实践成绩和论文成绩组合而成。各部分所占比例如下：

平时作业成绩：60%。主要考核对每堂课知识点的复习、理解和掌握程度。

课程实践成绩：20%。主要考核学生利用所学知识编程解决题目的能力。

课程论文成绩：20%。主要考核学生在编程解决问题的过程中，对问题的分析能力、知识和技能的运用能力及论文的撰写能力。

过程成绩提交时间和总评成绩计算说明表

序号

成绩提交时间

名称或说明

C1

第三次上课前

第二部分作业

C2

第四次上课前

第三部分作业

C3

第五次上课前

第四部分作业

C4

第六次上课前

第五部分作业

C5

第七次上课前

第六部分作业

C6

第八次上课后一周内

第七部分作业

C7

第八次上课后一周内

实践成绩

C8

第八次上课后二周内

论文成绩

总评成绩＝C1*0.1+C2*0.1+C3*0.1+C4*0.1+C5*0.1+C6*0.1+C7*0.2+C8*0.2

详细评定方式见说明中的其他说明。

注：上表用于说明授课过程中分项成绩提交时间，教师应在规定的时间内提交对应成绩，提前或逾期无法提交，一旦提交无法修改。大纲可以根据需要自行定义提交成绩的次数、时间和名称或说明，总评成绩计算必须与考核和成绩评定方式中描述的一致。

五、教材及参考书目

参考书目：

1.《ACM/ICPC算法训练教程》，余立功著，清华大学出版社

2.《算法艺术与信息学竞赛》,刘汝佳等著，清华大学出版社

3.《算法导论（原书第三版）》,[美] Thomas H.Cormen等著；殷建平，徐云，王刚 等译，机械工业出版社

4．《实用算法的分析与程序设计》，吴文虎等著，电子工业出版社

六、说明

（一）与相关课程的分工衔接

由于课程内容讲授的是计算机编程相关知识，因此《程序设计基础》、《C语言程序设计》是本课程的先修课程。而课程作为入门课程，会对ACM/ICPC竞赛所需各编程知识要点做一般性讨论、分析，具体内容可待到相关课程学习时，进行详细的学习。

（二）其他说明

1．课程的平时作业成绩及实践成绩均以http://poj.org在线系统中，学生ID提交成功（获得Accepted评价）情况评定。

2．论文成绩以学生提交的解题报告情况评定。报告中应包括：姓名、学号、题目编号及名称、对题目的分析、采用的解题算法及算法描述、提交过程中出现的问题及解决方法、对本课程的意见和建议。

3．学生在规定时间期限内完成各部分参考题目中的任意一道题目，即可获得该部分的平时成绩。

4．学生在规定时间内完成除各部分参考题以外的其他题目至少四道，即可获得实践成绩。参考题目：POJ1376 Robot 1376；POJ1166 The clocks 1166；POJ1979Red and Black；POJ1485 Fast food；POJ3627 Bookshelf 3627；POJ3663 Costume Party 3663。

5．学生在规定时间内提交至少四道实践题目（不能是平时题目）的解题报告即可获得论文成绩。若学生提交成功（获得Accepted评价）的题目数量超过30道，未提交论文亦可获得论文成绩。

（执笔人：王煦       审核人：   ）

2018 年 8 月 25 日