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

上海交通大学工程硕士算法总结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后标记postpost最大点在源点强连通部件中(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/割原理/集合覆盖(注意:老师很喜欢集合覆盖类问题,但是没有讲要考,比较危险)剩下提到要考的但是和已知章节冲突,第三梯队:背包