课程教学大纲-算法竞赛（程序设计竞赛）

算法竞赛程序设计竞赛课程教学大纲 课程编号 课程性质 公共选修 课程名称 算法竞赛程序设计竞赛 学时/学分 64/3 英文名称 Programming Contest 考核方式 考试 算法竞赛入门到进阶经典罗勇军清华大 选用教材大纲执笔人 学出版社 先修课程C语言，C语言大纲审核人 适用专业 一、教学基本目标 “算法竞赛程序设计竞赛”是一门公共选修课。通过该课程的学习，使学生通过编程 竞赛的方式，深入学习C语言、C语言、数据结构、算法设计等内容，并提高实际编程能 力。本课程能激发学生学习算法和程序设计的兴趣，提升算法设计、逻辑推理、数学建模、 编程实现和英语阅读能力，激励学生运用计算机编程技术和技能解决实际问题，培养团队合 作意识、挑战精神和创新潜力。 二 课程涉及知识技能 本课把C/C语言、算法和解题有机地结合在了 一起，注重学习方法和实践技巧。课程 内容包括算法竞赛入门、算法复杂度与算法思想、数据结构、暴力求解和搜索技术、动态 规划、数学概念与方法、字符串处理、图论模型与算法、几何题与模板，覆盖了算法竞赛入 门所需的主要知识点。 三 相关能力培养 1 编码能力。编写大量代码，奠定杰出程序员的基本功。 2 算法知识。掌握数据结构、搜索技术、动态规划、数学、字符串、图论、几何等算 法知识。 3 计算思维和逻辑思维。 4 团队合作精神。 四 教学基本内容 章 教学内容 1 概述 第1节算法竞赛与创新能力 第2节算法竞赛入门知识 2 算法复杂度 第1节计算的资源 第2节算法的定义 第3节算法的评估 3 STL和基本数据结构 第1节容器vector、栈和stack 队列和queue、优先队列和priority_queue 链表和 list set map 第2节sort 第 3 节 next_permutation 4 搜索技术 第1节递归和排列 第2节子集生成和组合问题 第3节BFS BFS和队列、状态图搜索、A*算法、双向广搜 第4节DFS DFS和递归、回溯与剪枝、迭代加深搜索、IDA* 5 高级数据结构 第1节并查集 第2节二叉树 第3节线段树 第4节树状数组 6 基础算法思想 第1节贪心法 第2节分治法 7 动态规划 第1节基础DP 第2节递推与记忆化搜索 章 教学内容 第3节区间DP 第4节树形DP 第5节数位DP 第6节状态压缩DP 8 数学 第1节高精度计算 第2节数论 第3节组合数学 第4节概率和数学期望 第5节公平组合游戏 9 字符串 第1节字符串基本操作 第2节字符串哈希 第3节字典树 第4节KMP 第5节AC自动机 第6节后缀树和后缀数组 10 图论 第1节图的基本概念 第2节图的存储 第3节图的遍历和连通性 第4节拓扑排序 第5节欧拉路 第6节无向图的连通性 第7节有向图的连通性 第8节2-SAT问题 第9节最短路 第10节最小生成树 第11节最大流 第12节最小割 第13节最小费用最大流 第14节二分图匹配 11 计算几何 第1节二维几何基础 第2节圆 章 教学内容 第3节三维几何 五 建议教学进度 章 学时 1 4课时 2 2课时 3 2课时 4 6课时 5 8课时 6 4课时 7 8课时 8 8课时 9 6课时 10 10课时 11 6课时 六 教学方法 理论教学和课堂活动结合。 主要采用多媒体技术进行课堂教学。 七、考核方式 考勤，作业，考试。 八 成绩评定方法 采取百分制。（1）平时成绩30分；（2）机试30分；（3）笔试40分。 九、教学参考书 [1] 算法竞赛入门经典训练指南，刘汝佳，陈锋，清华大学出版社 [2] 算法竞赛入门经典（第2版），刘汝佳，清华大学出版社 [3] UCM/ICPC算法训练教程，余立功，清华大学出版社 [4] 挑战程序设计竞赛，秋叶拓哉，岩田阳一，北川宣稔著，巫泽俊等译，人民邮电 出版社 [5] ACM-ICPC程序设计系列计算几何及应用，金博，郭立，于瑞云，哈尔滨工业大 学出版社 [6] ACM国际大学生程序设计竞赛算法与实现，俞勇，清华大学出版社 [7] 算法设计与分析基础（第2版），Anany Levitin著，潘彦译，清华大学出版社 [8] 算法导论，Thomas H. Cormen, Charles E. leiserson等著，潘金贵等译，机械 工业出版社