上海交通大学工程硕士算法考试资料

上海交通大学工程硕士算法总结 a.知识点: 第一章: 复杂度(简单),欧几米德算法(中等), 模运算(中等),算数运算 第二章: 大师定理(简单,重要!) 第三章: DFS算法(简单,重要!), 寻找子部件(中等), 图的反转 第四章: BFS,Dijsktra算法( 中等,重要!),bellman-ford( 难 ) 第五章: 最小生成树(中等) 第六章: DAG(中等),背包问题( 中等,重要!),独立集 第七章: 线性规划的解(简单), 最大流(中等), 对偶(中等,重要!) b.作业(知识点): 第一章: 0.1(复杂度),0.2(复杂度),1.2(扩展欧几里得),1.31(复杂度) 难,1.35(逆/费马小定理/模运算) 难 第二章: 2.5(大师定理),2.19( 大师定理), 2.22(大师定理)难 第三章: 3.7(DFS),3.11(DFS),3.28(SAT)难, 第四章: 4.11(Dijkstra),4.12(Dijkstra),4.16(2分堆/d堆) 第五章: 5.20(完美匹配),5.23(最小生成树),5.26(约束问题) 第六章: 6.17(背包),6.21(最小覆盖/独立集),6.22(背包) 第七章: 7.6(简单规划),7.7(线性规划的解), 7.21(临界边 )难,7.23(归约问 题)难 红/黄/绿指重要度依次降低. 注意:作业并不涵盖所有考点. c.考试注意点 : 1.在图计算中运用了标记 ,删边 ,反向等技巧,结合最短路径和 DFS等进行计算. 2.贪心算法出题比较无规则. 3.大师定理,线性规划中的对偶,须理解背熟.几乎是必考 . 知识点详细: 1.复杂度如无特殊要求复杂度一般只要表示为大 O 即可. *常数系数忽略 *阶乘指数 多项式log *复杂度 的证明需要证明 O 和 2.加减的复杂度(n),乘除的复杂度(n2,或者 n x m),(乘法可以更加简化) 模运算(平方) *满足结合律,分配律,交换率 *指数运算可记 3.欧几里得算法 *辗转相除法求最大公因数(练习) *扩展欧几里得算法求逆元 4.逆元 *ax=1(modN)成立,则 x 是关于 a 模 N 的一个乘法逆元 *gcd(a,N)=1(互质)时,存在 x 和 y,使得 ax+Ny=1,x 就是要找的逆元(因为 y 是可以约掉的), 利用扩展欧几里得来 计算此逆元.(可能性大) *练习一遍很重要 5.大师定理 *把一个问题分解为相同的子问题,通过子问题的规模, 数量和合并子问题的代价可以计算 整个问题的复杂度,牢记 公式. *大师定理排列问题比较容易出到(归并排序). 6.无向图 *explore(重要) 不断寻找相邻的结点,会变例可到达部分, 不连通部分不访问 . *DFS(重要) 对图中每个点做前序和后序标记,然后运行 explore,不连通部分也访问. 前序和后序有些特殊性质. 7.有向图 *DFS(O(|V|+|E|) 有向图一般运行 DFS,运行后可以得到一颗树. 有树边 ,前向边,回边,横跨边 *强连通部件 特殊的在这里寻找强连通部件运用了 explore 算法,整个算法复杂度同 DFS. *输出图中所有强连通部件的步骤 DFS 后标记 post post 最大点在源点强连通部件中 (post 排序) 把图反转(每条边反转 ) explore 找到一个强连通部件, 也就是源点强连通部件 删除后可以寻找下一个(post 最大的) 8.最短距离 *BFS,用于距离的算法 ,对象无权图 无权图的最短路径(O(|V|+|E|) *Dijkstra(采用数组是 O(|V|2),BFS 扩展算法, 适合边正的有权图 迪杰斯特拉算法:预期不会有更长边 ,因而不适用于负边存在的情况 有权图的最短路径 *Bellman-ford,BFS 扩展算法 带负权值的最短路径,对比两点间全部可能的路径, 可以使用与负边情况,但是注意,负环 存在的情况下没有最短距离. *二分堆 上述算法的数据结构 9.最小生成树 *分割性质 两个点集间权重最轻的边总是可以加到最小生成树上(如果能连到树上) *Kruskal 算法 不断寻找最小边然后合并的过程,包括 makeset(x) find(x) union(x,y) 10.DAG 最短路径 *使用一维表计算 DAG 最短路径 11.DAG 最长递增子序列 *一维表(考试要求的是表达式 ) 12.背包问题 *多副本背包 一维表,每增加一点价值 v 为一格, 每个格有 n 种可能性,复杂度 nv.习题对应硬币问题. *单副本背包 二维表,价值和物品建立一个二维表可得 .习题中有对应 . 13.树的独立集 *同样只是个表达式,只能用于树而不能用于图 . 14.网络流 *最大流问题,利用剩余图来解决 ,即 explore 剩余图起点既可得到一个最大流的所有边. 最小分割最大流定理 15.二部图匹配 *增加源点和汇点并求最大流(归约),注意二部图的源点汇点是人工增加的,说明加点是一 种技巧. 16.对偶 *写出对偶表达式 对偶的写法: 题目(喜闻乐见): 必考题目,第一梯队: 1.大师定理相关( 遇题请先上公式) 2.有向图相关(涉及回边/横向边 /树边),注意和这有关系的是 DFS 的标记. 3.动态规划(20 分) 估计是二维表,形式可能类似于编辑距离的计算,和最长公共子序列/串相 关.(注意必须写出表达式,应该要比背包问题复杂) 4.线性规划之对偶 据说只有 3 题的剩余自由空间了,第二梯队: 可能性比较大的有: 第一章 = 复杂度/扩展欧几里得求逆元 选一或者一起 第四章 = Dijkstra/二分堆/bellman-ford (可以会一起出) 第五章 = Kruskal+Disjoint set/割原理/集合覆盖(注意 :老师很喜欢集合覆盖类问题,但是没 有讲要考,比较危险 ) 剩下提到要考的但是和已知章节冲突,第三梯队: 背包