DSP

编程进阶

2019-07-13 15:16发布

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

热门文章