转载自:http://cojs.tk/cogs/page/page.php?aid=38
ACM进阶计划
ACM队不是为了一场比赛而存在的,为的是队员的整体提高。
大学期间,ACM队队员必须要学好的课程有:
l C/C++两种语言
l 高等数学
l 线性代数
l 数据结构
l 离散数学
l 数据库原理
l 操作系统原理
l 计算机组成原理
l 人工智能
l 编译原理
l 算法设计与分析
除此之外,我希望你们能掌握一些其它的知识,因为知识都是相互联系,触类旁通的。
以下学习计划每学期中的内容不分先后顺序,虽说是为立志于学习ACM的同学列的知识清单,但内容不限于ACM的知识。英语之类与专业相距较远的课程请自行分配时间,这里不再列举。
大一上学期:
必学:
- C语言基础语法必须全部学会
a) 推荐“语言入门”分类20道题以上
b) 提前完成C语言课程设计
- 简单数学题(推荐“数学”分类20道以上)
需要掌握以下基本算法:
a) 欧几里德算法求最大公约数
b) 筛法求素数
c) 康托展开
d) 逆康托展开
e) 同余定理
f) 次方求模
- 计算几何初步
a) 三角形面积
b) 三点顺序
-
学会简单计算程序的时间复杂度与空间复杂度
-
二分查找法
-
简单的排序算法
a) 冒泡排序法
b) 插入排序法
-
贪心算法经典题目
-
高等数学
以下为选修:
- 学会使用简单的DOS命令(较重要)
a) color/dir/copy/shutdown/mkdir(md)/rmdir(rd)/attrib/cd/
b) 知道什么是绝对路径与相对路径
c) 学会使用C语言调用DOS命令
d) 学会在命令提示符下调用你自己用C语言编写的程序,并使用命令行参数给自己的程序传参(比如自己制作一个copyfile.exe实现与copy命令基本功能一致的功能)
e) 学会编写bat批处理文件
-
学会Windows系统的一些小知识,如设置隐藏文件,autoRun.inf的设置等。
-
学会编辑注册表(包括使用注册表编辑器regedit和使用DOS命令编辑注册表)
-
学会使用组策略管理器管理(gpedit.msc)组策略。
大一下学期:
-
掌握C++部分语法,如引用类型,函数重载等,基本明白什么是类。
-
学会BFS与DFS
a) 迷宫求解(最少步数)
b) 水池数目(NYOJ27)
c) 图像有用区域(NYOJ92)
d) 树的前序中序后序遍历
- 动态规划(15题以上),要学会使用循环的方法写动态规划,同时也要学会使用记忆化搜索的方法。
a) 最大子串和
b) 最长公共子序列
c) 最长单调递增子序列(O(n)与O(n log n)算法都需要掌握)
d) 01背包
e) RMQ算法
-
学会分析与计算复杂程序的时间复杂度
-
学会使用栈与队列等线性存储结构
-
学会分治策略
-
排序算法
a) 归并排序
b) 快速排序
c) 计数排序
- 数论
a) 扩展欧几里德算法
b) 求逆元
c) 同余方程
d) 中国剩余定理
- 博弈论
a) 博弈问题与SG函数的定义
b) 多个博弈问题SG值的合并
- 图论:
a) 图的邻接矩阵与邻接表两种常见存储方式
b) 欧拉路的判定
c) 单最短路bellman-ford算法dijkstra算法。
d) 最小生成树的kruskal算法与prim算法。
-
学会使用C语言进行网络编程与多线程编程
-
高等数学
-
线性代数
a) 明确线性代数的重要性,首先是课本必须学好
b) 编写一个Matrix类,进行矩阵的各种操作,并求编写程序解线性方程组。
c) 推荐做一两道“矩阵运算”分类下的题目。
以下为选修,随便选一两个学学即可:
-
(较重要)使用C语言或C++编写简单程序来调用一些简单的windows API,或者在linux下进行linux系统调用,其目的是明白什么是API(应用程序接口)。
-
网页设计
a) 学习静态网页技术(html+css+javascript)
b) 较具有艺术细胞的可以试试Photoshop
c) php或其它动态网页技术
- 学习matlab,如果想参加数学建模大赛的话,需要学这个软件。
大一假期(如果留校集训)
-
掌握C++语法,并熟练使用STL
-
试着实现STL的一些基本容器和函数,使自己基本能看懂STL源码
-
图论
a) 使用优先队列优化Dijkstra和Prim
b) 单源最短路径之SPFA
c) 差分约束系统
d) 多源多点最短路径之FloydWarshall算法
e) 求欧拉路(圈套圈算法)
-
进行复杂模拟题训练
-
拓扑排序
-
动态规划进阶
a) 完全背包、多重背包等各种背包问题(参见背包九讲)
b) POJ上完成一定数目的动态规划题目
c) 状态压缩动态规划
d) 树形动态规划
- 搜索
a) 回溯法熟练应用
b) 复杂的搜索题目练习
c) 双向广度优先搜索
d) 启发式搜索(包括A*算法,如八数码问题)
- 计算几何
a) 判断点是否在线段上
b) 判断线段相交
c) 判断矩形是否包含点
d) 判断圆与矩形关系
e) 判断点是否在多边形内
f) 判断点到线段的最近点
g) 计算两个圆的公切线
h) 求矩形的并的面积
i) 求多边形面积
j) 求多边形重心
k) 求凸包
选修
-
可以学习一种C++的开发框架来编写一些窗体程序玩玩(如MFC,Qt等)。
-
学习使用C或C++连接数据库。
大二一整年:
- 数据结构
a) 单调队列
b) 堆
c) 并查集
d) 树状数组
e) 哈希表
f) 线段树
g) 字典树
- 图论
a) 强连通分量
b) 双连通分量(求割点,桥)
c) 强连通分量与双连通分量缩点
d) LCA、LCA与RMQ的转化
e) 二分图匹配
i. 二分图最大匹配
ii. 最小点集覆盖
iii. 最小路径覆盖
iv. 二分图最优匹配
v. 二分图多重匹配
f) 网络流
i. 最大流的基本SAP
ii. 最大流的ISAP或者Dinic等高效算法(任一)
iii. 最小费用最大流
iv. 最大流最小割定理
-
动态规划多做题提高(10道难题以上)
-
数论
a) 积性函数的应用
b) 欧拉定理
c) 费马小定理
d) 威乐逊定理
- 组合数学
a) 群论基础
b) Polya定理与计数问题
c) Catalan数
- 计算几何
a) 各种旋转卡壳相关算法
b) 三维计算几何算法
-
理解数据库原理,学会SQL语句
-
学好计算机组成原理
-
学习Transact-SQL语言,学会使用触发器,存储过程,学会数据库事务等。
-
图论二
a) 网络流的各种构图训练(重要)
b) 最小割与最小点权覆盖等的关系(详见《最小割模型在信息学竞赛中的应用》一文)
c) 次小生成树
d) 第k短路
e) 最小比率生成树
-
线性规划
-
动态规划更高级进阶
-
KMP算法
-
AC自动机理论与实现
-
博弈论之Alpha-beta剪枝
选修,有相关兴趣的可以学一下:
-
自学C#或Java做一个项目,比如C++/C#/Java考试系统之类的。
-
先做一些小游戏玩玩,然后可以学一下DirectX或者OpenGL,或者可以试试XNA游戏框架。
-
了解一下游戏引擎相关的知识
其中的寒假假期最好:
-
自学完离散数学
-
自学概率论的部分章节
-
自学操作系统部分章节
大三、
-
巩固之前的知识,进行一遍大复习。
-
一些如蚁群算法,遗传算法,模拟退火算法等人工智能方面应用较广的随机性算法。
-
把编译原理上学的东西应用到编程中:如DFA,NFA,还有语法分析的各种方法等。
当你按上面那些一步步走过来时你已经是牛人了,后面要学的东西,就是由牛人自己来发掘的了。
2011年6月21日