2011/02/23 - by
Oneplus
• ACM Group
2011春季学期程序设计实践课程计划
本学期计划内容
| 大类 | 项目 | 先修 |
|---|---|---|
| 基础 | 时空复杂度分析 | 无 |
| 递推 | 无 | |
| 递归 | 无 | |
| 分治法 | 无 | |
| 二分法(数值计算) | 分治 | |
| 贪心 | 贪心法 | 堆 |
| 排序 | 快速排序 | 分治 |
| 堆排序 | 堆 | |
| 基数排序 | 无 | |
| 数据结构 | 线性表、栈、队列 | 无 |
| 二分堆、映射二分堆 | 分治 | |
| 并查集 | 无 | |
| 树状数组 | 分治 | |
| STL | 分治 | |
| 线段树 | 分治 | |
| 搜索 | 状态空间搜索 | 无 |
| BFS | 队列 | |
| DFS | 递归 | |
| 搜索剪枝 | 状态空间搜索 | |
| 启发式搜索 | 堆 | |
| 动态规划 | 状态和状态转移 | 递推 |
| 线性DP | 无 | |
| 环状DP | 无 | |
| 树状DP | 无 | |
| 状态压缩DP | 无 | |
| 四边形不等式 | 无 | |
| 斜率优化 | 无 | |
| 计算几何 | 向量基本运算 | 无 |
| 三点共线 | 无 | |
| 点在线段上 | 无 | |
| 两点在直线的同异侧 | 无 | |
| 点到直线、线段距离 | 无 | |
| 多边形面积 | 无 | |
| 线段相交 | 无 | |
| 凸包 | 无 | |
| 多边形切割 | 无 | |
| 图论 | 拓扑排序 | 无 |
| 无向图的双分量 | 搜索基础 | |
| 有向图的强分量 | 搜索基础 | |
| 最小生成树 | 堆 | |
| 最短路 | 堆 | |
| 二分图匹配 | 无 |
关于程序设计实践授课内容
本学期程序设计实践课的目标是培养参加课程同学的编程兴趣和编程能力。所以在本学期授课中难度将适当下调。同时，提高编码在课程中所占的比例。
第一课 - 课程介绍和基础知识
- 时空复杂度分析
- 递推和递归
- 分治
第二课 - 二分算法、贪心算法(一)和数据结构(一)
- 二分
- 贪心算法
- 堆
第三课 - 贪心算法(二)和排序
- 贪心算法
- 快速排序
- 堆排序
第四课 - 编码练习(一)
- 二维平面模拟
- 时间模拟
- 进制
- 打印
第五课 - 数据结构(二)
- 栈、队列
- 并查集基础
- STL
第六课 - 搜索基础
- 状态空间搜索基础
- BFS
- DFS
第七课 - 动态规划基础
- 状态与状态转移
- 递推、线性DP
第八课 - 编码练习(二) 第九课 - 计算几何基础
- 向量运算
- 三点共线
- 点与线段的关系
- 线段相交
第十课 - 图论基础
- 图的存储
- 拓扑排序
- 连通性判定
关于10级周赛
具体到各周的计划还没有制定。讲座内容就是上面程序设计实践没讲的内容。希望能够发动08级队员参与讲座组织，但不排除在08级普遍傲娇的情况下，征用09级队员。
关于09级队内讨论
这学期无论如何，也要把这件事做起来。
待补充
希望大家多提意见。