Hooray's profileHooray's TrashboxPhotosBlogListsMore  |  Tools Help |
|
7/30/2007 算法考试复习笔记（三）几何算法 8.1 引言 点，直线，线段，及多边形 注意特例 路径由一组点和依次连接它们的线段组成 封闭路径：起点和终点相同的路径，又称多边形 简单多边形：路径不自相交的多边形 凸多边形：连接多变性内部两点的任何线段，其本身全部为与多边形的内部 8.2 判断点是否在多变形内部 问题：给定简单多边形P和点q，判定该点是否在多边形内部 向一个方向走到边界，看和多少条路径相交 特殊：和顶点相交。。 8.3 构造简单多边形 问题：给定平面中n个点的集合，将他们连接起来形成一条简单的封闭路径 方案：考虑一个圆心，从0度到360度扫描 存在问题：相邻两点可能会超过180度，这样可能导致非简单 解决：先找三个点，选取三角形的内部一点作为圆心，这样可以确保不超过180度 8.4 凸包 凸包：包围所有点的最小凸多边形 问题：计算平面中给定n个点的凸包 直接方法：归纳，假设n-1个可做，但是最后一个点的选取不可以随便 选取最大x坐标的点（如果多个点有相同的最大x，则取其中y最小的点），显然此点为凸包顶点，然后以此为圆心扫描，会找到一个小于90度的角，对应的两个顶点和此点连接即为凸包 O(n^2) 礼品包裹算法：归纳假设：给定平面中n个点的集合，可以找到长度k<n的凸路径，使它成为该点集合闭包的一部分 寻找支撑线，找相邻点，延长线并旋转扫描 O(n^2) Graham扫描算法：归纳假设：给定平面中n个点的集合，可以在前k个点中找到一条凸路径，所对应的凸多边形包围了前k个点 从最大x坐标点（如果x相同，取y最小）进行扫描，每扫到一个，就可以做出一个凸包
代数和数值算法 9.1 引言 9.2 求幂运算 传统算法：n*n*n*n…. 重复平方法：n^2^2^2…，时间复杂度O(logk)，但是数值越来越大，乘法开销也变大 密码学中的应用（乘法开销不变大的场合） RSA：选取两个很大的素数p和q并计算乘积n=pq，然后选择另一个很大的整数d，使得d和(p-1)(q-1)没有公因数，根据p,q,d可以计算出满足条件d*e = 1(mod (p-1)(q-1))，然后e作为加密密钥，d作为解密密钥 加密E(M) = M^e (mod n)，M是1~n之间的数字 解密D(C) = C^d (mod n)，C是1~n之间的数字 9.3 欧几里得算法 寻找两个给定正整数m和n的最大公约数 辗转相除，求余,O(log(n+m)) 规约 10.2 规约的例子 简单字符串匹配 设两个长度为n的字符串A=a0a1…a(n-1)及B=b0b1….b(n-1)，判断B是否为A的循环平移 即判断B是否为AA的子串 特殊代表集 一组集合S1, S2, …, Sk，集合R={r1, r2, …,rn}若满足ri属于Si(注意，ri必须相异，故而不一定都存在)，则R是Si的特殊代表集 问题：给定一个由有穷个有穷集合组成的组，找出该组的任意一个SDR，或判断SDR不存在 Hall定理：S1, S2, …, Sk，其存在SDR当且仅当 card (Si1 并 Si2 并 … 并 Sim) >= m，对于1,2,…,k的每个子集{i1, i2, …, im}，换句话说，任意m个集合的并必须至少包含m个不同的元素，对所有的1<=m<=k 利用Hall定理验证：双相匹配问题：设G=(V,U,E)是一个双向图，使得对每个集合Si均在V中存在一个顶点vi 关于序列比较的规约 在无向图中寻找三角形 算法考试复习笔记（二） 有一得有二。。。尽管考完了，还是得要做完
基于归纳的算法设计 5.1 引言 数学归纳法：解决一个小规模事例，每个问题的解答都可以由更小规模的解答构造出来 5.2 多项式求值 传统方式：n(n+1)/2次乘法和n次加法 Pn(x) = x*Pn-1(x) + a0的方式：n次乘法和n次加法 5.3 最大导出子图 导出子图：令G=(V,E)是一个无向图，G的导出子图H=(U,F)满足U包含于V且U中两定点若在E中有边，则此边也在F中 顶点的度：与该顶点相连的其他顶点的个数 最大导出子图：给定G=(V,E)和整数k，G的最大规模导出子图满足其中所有顶点的度大于或等于k 删除所有度小于k的点，并依次删除删除一次后度数减少小于k的点，直到剩余所有的点度数都大于或等于k（数学归纳法证明） 5.4 寻找一对一映射 令f是一个把有限集映射到自身的函数，如果对于每一个元素j，至多存在一个元素i映射到j，则称f是一个一对一的函数 寻找：给定一个集合A和一个从A映射到自身的映射f，寻找元素个数最多的一个子集S，使得f把S中每一个元素映射到S中另一元素且一对一 实现：寻找没有被映射的元素，删除（数学归纳法证明） 5.5 社会名流问题 在n个人中，被所有人知道，但却不知道别人的人，被定义为社会名流 问A是否认识B，如果认识，则删除A，如果不认识，则删除B，最终剩余一个人是否被所有的人认识 5.6 分治算法：轮廓问题 一组矩形建筑的合并轮廓 分成n/2和n/2两组，分别计算，复杂度O(nlogn) 5.7 在二叉树中计算平衡因子 给定一棵n个节点的二叉树T，计算其所有节点的平衡因子 假设：已知如何计算节点数小于n的二叉树的全部节点的平衡因子和高度 5.8 寻找最大连续子序列 给定一个实数序列x1,x2,…,xn(不必是正数)，寻找一个连续子序列xi,x(i+1),…,xj，使得其数值之和在所有连续子序列之和中是最大的 假设：已知如何找到规模小于n的序列的最大子序列 更强假设：已知如何找到规模小于n的序列的最大子序列，以及作为后缀的最大子序列 实现：比较三个子序列： n-1个序列的最大自序列 n-1个序列的后缀最大子序列 + xn Xn 5.9 增强归纳假设 P(<n) ==> P(n)很难推断的时候，增加一个Q，[P and Q](<n) ==> [P and Q](n) ==> p[n]，但是Q也需要相应的证明 序列和集合的算法 6.1 引言 序列与集合的区别在于序列需要考虑元素的顺序，而集合不必，集合中的元素不可重复出现，而序列可以 6.2 二叉搜索的几种形式 目标：一次查询将搜索空间（大致）减半 纯二叉搜索：给定实数序列x1,x2,…,xn满足x1<=x2<=…<=xn。对于某个实数z，试确定z是否在该序列中出现，若z出现，试确定下标i使xi=z （寻找相同位置） 循环序列的二叉搜索：对某个已知的循环排序的链表，找出其中最小元素的位置 （寻找突变位置 aj < ai, j>i） 二叉搜索特殊下标：给定一个由不同整数a1,a2,…,an组成的序列，试确定是否存在某个下标i使得ai=I （寻找突变位置 aj <j） 二叉搜索长度未知序列：加倍搜索 重叠子序列问题：给定两个序列A,B，试确定i的最大值，使得B的i次重叠序列是A的子序列 解方程：连续函数f(x)，f(a)*f(b)<0，求f(x)=0的解 6.4 排序 桶排序和基数排序 0(kn) 归纳假设：知道怎样用小于k位对元素排序 插入排序和选择排序 O(n^2) 插入排序归纳假设：知道如何对n-1个数进行排序 选择排序：取出最大的一个数作为第n个数，剩余的n-1个数排序 归并排序 O(nlogn) (分治) 归纳假设：知道如何对n/2个数进行排序 需要额外的空间 快速排序 O(nlogn) (分治) 分区 用两个指针L和R分别指向数组的左右两侧，然后指针相向而行 归纳假设：在算法的第k步，对任意i<L,都有支点pivot >= xi，对任意j, j<R，都有支点pivot < xj 两区再分别快速排序 堆排序 自底向上比自定向下节省一半的归纳过程，从n/2开始向前 排序问题的下界 时间复杂度 O(nlogn) 所有基于比较的排序算法平均运行时间都是O(nlogn) 6.5 顺序统计 最大数和最小数：在已知的某个序列中找到最大数和最小数，归纳假设：对n-1个元素的序列知道其最大数和最小数 查找第k小的数：类似快速排序，分区，然后看区域大小，决定第k小的数在哪一区 6.6 数据压缩 霍夫曼编码：已知某文本文件（字符串序列），为期设计一种编码方式使之满足前缀限制，且使编码后文本长度最短 找两个最小的建树，依次进行
图算法 7.1 引言 一个图G=(V,E)包括顶点（节点）集合V和边集合E 多重图：相同的顶点对之间有若干条边 简单图：相同的顶点对之间最多一条边 顶点的度：与顶点相连接的边的数目 从v1到vk的一条路径是一顶点序列，通过边相连接 简单路径：路径中每个顶点至多出现一次 顶点v到u可达：v到u中存在一条路径 回路：起点与终点为同一顶点的路径 闭链(简单回路)：除了起点和终点，其他顶点至多出现一次 一个有向图G=(V,E)的无向型：与G相同的图，但其中的边没有方向性 连通：图的无向型，若任意两个顶点间都存在一条路径，则图被称为连通的 森林：不包含闭链的图 树：连通的森林 根树：有向树，其中一颗特定的顶点被称为根，所有的边都远离这个根延伸 子图：G=(V,E)的子图H=(U,F)满足U包含于V，F包含于E 生成树：无向图G的生成树是G的一个子图，是一棵树并包含G中所有节点 生成森林：无向图G的生成森林是G的一个子图，是一个森林并包含G中所有节点 导出子图(顶点导出子图)：包含两个顶点属于子图的所有边 连通分支：如果图不是连通的，可以用唯一的方式划分成一些连通子图的集合，最大连通子图 偶图：定点集合可以划分为两个集合的图，所有边都关联属于不同集合的顶点，同一集合顶点间无边 加权图：边附有权重的图 7.2 欧拉图 七桥问题 归纳假设：对于边数小于m的连通图，其所有顶点的度为偶数，则存在一条包含每条边仅一次的封闭路径，且知道如何找到 7.3 图的遍历 深度优先搜索DFS ==> 构造DFS树 无向DFS树的性质：无向图中的每一条边或者属于生成树，或者连接两个在生成树中直系关系的两个顶点 有向DFS树的性质：如果(v,w)是有向图G的生成树T中一条边，且v.DFS_Number<w.DFS_Number，则w是v在T中的一个后代 问题：给定一个有向图G=(V,E)，确定它是否含有一个（有向）闭链 当且仅当G含有一条后退边 广度优先搜索BFS 如果边(u,w)属于一棵BFS树，其中u是w的父节点，则在具有导向w的边的顶点中，u具有最小的BFS数 对于每一个顶点w，在T中从根到w的路径是在G中从根到w的最短路径 如果(v,w)是E中的一条边且不属于T，则它连接的两个顶点的层数至多相差1 7.4 拓扑排序 给定一个有向非循环图G=(V,E)，它有n个顶点，把顶点按照1到n作标记，满足，若v被标记为k，则通过有向路径从v出发可以到达所有顶点的标记大于k 归纳假设：已知如何根据以上条件对顶点数小于n的有向非循环图做标记 推断：留一个入度为0的顶点，剩余n-1标记好 引理：一个有向非循环图总有一个入度为0的点 （如果没有，那么可以无限遍历，必然有循环） 7.5 单源最短路径 给定一个有向图G=(V,E)及一个顶点v，寻找从v到达G中各项点的最短路径 非循环 归纳假设：给定一个拓扑排序，已知如何找到从v出发到前面(n-1)个顶点的最短路径的长度 删除第n个节点z，然后求剩余的前面(n-1)个节点最短路径，最后把所有直接连到z的边(w,z)作比较，取min(w.SP + len(w,z)) 一般情况 归纳假设：给定一个图和顶点v，已知与v最近的k个顶点，以及到达他们的最短路径长度 每一次迭代中增加一个顶点w，满足min(u.SP + len(u,w)) (u属于Vk)是所有不属于Vk的w中最小的 优化：w增加到Vk中后，寻找更好最短路径的唯一方法是经过w，所以，只需要检查从w出发，指向不属于Vk顶点的所有边，对每条这样的边(w,z)检查w.SP + len(w,z)，并在需要的情况下更新z.SP 7.6 最小代价生成树 一个固定的连通子图，包含所有的顶点，并且子图中边的代价总和是最小的 给定一个无向连通图G=(V,E)，找出G的具有最小代价的生成树T 归纳假设1：已知如何为边数小于m的连通图找到MCST 归纳假设2：给定一个连同G=(V,E)，如何找到G的一个(k<|V|-1)条边的子图T，其满足T是一棵树，且是G的MCST的一个子图 MCST中至少有一条边，把属于T和不属于T的顶点相连，这条边是所有把属于T和不属于T的顶点相连的最小代价边 反证法，如果不是，则这两个顶点通过另外一条属于T和不属于T的顶点相连，这条边代价比最小边高 7.7 全部最短路径 给定一个（有向或无向）加权图G=(V,E)，权值非负，要找到所有顶点对之间的最小长度路径 一般的，假定图有向 从1到|V|对顶点进行标记（无所谓顺序），从u到w的路径被称为k-path，是指除了u和w，在路径上最大的顶点被标记为k 归纳假设：已知任意一对顶点间k-path的最短路径长度，k<m 每次m ==> m+1，考虑m-path路径，在u和w之间最短的m-path=min(u和vm之间的s-path(s<m) + vm和w之间的t-path(t<m)) 7.8 传递闭包 给定一个有向图G=(V,E)，传递闭包C=(V,F)是一个有向图，若满足当且仅当在G中存在一条从v到w的路径，则在C中存在一条边(v,w) 问题：给定一个有向图G=(V,E)，找到它的传递闭包 规约成全部最短路径问题，考虑G的完全有向图G'=(V',E')，如果E'中的e属于E，则代价为0，否则为1，只需求全部最短路径中长度为0的顶点对 7.10 匹配 定义 给定一个无向图G=(V,E)，匹配是边的一个集合，其中任意两条边没有公共顶点 一个与匹配中任何边都无关的点成为无匹配的，或称不属于该匹配 完美匹配：所有点都具有匹配的匹配 最大匹配：具有最大边数的匹配 极大匹配：无法再增加边数的匹配 非常稠密图中的完美匹配 非常稠密图：令G=(V,E)是一个无向图，其中|V|=2n，且每个点的度至少为n 非常稠密图的完美匹配 对匹配规模m进行归纳，假设可以找到m条边的匹配M，m<n 检查所有不在M中的边，看是否其中的一条可以加入到M中，如果可以，完成 否则M是一个极大匹配，由于M非完美，至少有两个顶点v1,v2不属于M，这两个顶点至少向外伸出2n条各不相同的边，指向被M覆盖的顶点，否则，就可以找到一条边加入M。由于M边数小于n其从v1,v2出发有2n条边与它相连，至少有一条M中的边(u1,u2)，与来自v1和v2的两条边相连，这样，从M中去除(u1,u2)，加上那两条边即可 偶图匹配 在偶图中找到一个最大匹配 对于一个给定的匹配，一个交互路径P是一个从V中顶点v出发到达U中顶点u的路径，而v和u都没有在M中被匹配，且P中的边在E-M和M中交互进行 这样利用一条交互路径就可以找到多一对匹配 问题转化为寻找交互路径的问题，将M中边方向从U到V，而E-M中边方向相反，做出的有向图G'进行遍历，找到一条从入度为0的顶点到出度为0的顶点的路径，通过图搜索算法 DFS: 复杂度O(|V|+|E|)，故算法复杂度O(|V|(|V|+|E|)) BFS: 抽取G'中顶点不相交路径的极大集合，找到任何一个路径后删除其顶点，然后找另一条路径，再删除节点，算法复杂度O(|V|^0.5 * (|V|+|E|)) 7.11 网络流量 令G=(V,E)是一个有两个特殊顶点的有向图，一个是入度为0的s（源点），一个是出度为0的t（汇点），E中每条边e被赋予一个正的权值c(e)，称为e的容量。 流量是作用在网络的边上的函数f，满足两个条件 0<= f(e) <= c(e)，流量不超过容量 对于V中除了s和t的所有顶点，Sigma f(u,v) = Sigma f(v,w)，进入一个顶点的流量之和等于离开这个顶点的流量之和 增量路径：一个从s到t的有向路径，由G的边组成，但是边的方向不必相同，每条边(v,u)满足下列两个条件之一 在G中(v,u)是相同方向，且f(v,u)<c(v,u)，边(v,u)被称为前向边，可以容下多个流量，c(v,u)-f(v,u)称为松弛度 在G中(v,u)是相反方向（即(u,v)属于E），且f(u,v)>0，边(v,u)被称为后向边，从一条后向边有可能借用（减少）一些流量 一个流量f是最大的，当且仅当它不存在增量路径 割：令A是V中一个子集，B=V-A，割是一个边集合((v,w)属于E)，其中v属于A，而w属于B 割的容量 = 各边容量之和 网络中最大流的值，等于割的最小容量 算法：从一个值为0的流量开始，搜索增量路径，并对流量作相应的扩充，直到不存在增量路径。 找增量路径：定义余图R=(V,F)，与G有着相同的顶点、源点和汇点，以及相同的边，但是可能有不同的方向和容量，余图中的边对应于一个增量路径中可能的边，他们的容量对应于这些边可能的流的增量的值。确切地说，一个边(v,w)属于F，如果它是个前向边，此时他的容量是c(v,w)-f(v,w)，如果是个后向边，容量是f(v,w)，然后一个增量路径就是一条在余图中从s到t的正规有向路径 7.13 小结 DFS和BFS 7/27/2007 《瓦尔哈拉骑士》全流程攻略(PSP)简单流程 任务: 通关后可以存档继续玩，但工会没有任务更新的了，（一共也就3９个任务）不归之庭右边喷泉后的门可以回到过去的世界,不知道还会有什么新要素不．只知道在大圣堂还可以去和最终ＢＯＳＳ战斗 7/26/2007 主题：自７月２６日后办公室提供冷饮主题：自７月２６日后办公室提供冷饮 从今日起，三四五楼将提供冷饮给大家，每个楼层每天提供１００块，提供时间为每天下午２点前后，欢迎大家品尝 其它: 如您对冷饮供应有任何宝贵意见请随时拨打 FM helpdesk 5555。
7/25/2007 算法考试复习笔记（一）数学归纳法 2.1 引言 n=1时成立，对n>1, n-1时成立，n也成立 2.2 三个简单的例子 自然数等式和不等式应用数学归纳法的证明 2.3 平面内区域的计数 n条一般位置直线将平面分为n(n+1)/2+1个区域 <== 每增加一条会多出N个区域（数学归纳法） 2.4 简单着色问题 直线构成的区域可以用两种颜色进行着色 <== 第N条直线割开后一方不变，另一方换色 2.5 复杂一些的加法题 类似2.2 2.6 一个简单的不等式 Sigma 1/(2 ^ n) < 1 2.7 欧拉公式 任意一张连同平面图的节点数(V)、边数(E)和面数(F)满足等式V+F=E+2 <== (对面归纳) 有n个节点的树有n条边(V+1=E+2)
算法分析
3.1 引言 时间评估，n无限增长后的时间的开销 3.2 符号O 指数函数要比多项式函数增长的快 f(n) = O(s(n)) 且 g(n) = O(r(n))，则 f(n) + g(n) = O(s(n) + r(n)) f(n) = O(s(n)) 且 g(n) = O(r(n))，则 f(n) * g(n) = O(s(n) * r(n)) 3.3 时间与空间复杂度 时间复杂度：时间开销 空间复杂度：临时存储空间的开销 3.4 求和 求复杂度的基础 3.5 递推关系 F(n) = g (F(n-1))，或者 F(n) = g (F(n-1), F(n-2)) …如斐波那契数列 分治关系 问题分割为多个子问题，每个子问题也被递归求解，得到结果后，再用一个操作来组合字问题的解 a和b为整数常数，a>=1，b>=2且c和k为正常数，则递推关系T(n) = a*T(n/b) + cn^k的解是 O (n^ log(b, a)) 如果a>b^k O (n^k * log n) 如果a=b^k O (n^k) 如果a<b^k 设计全部历史的递推关系 依赖此前所有的函数 T(n) = c + Sigma T(i), i from 1 to n-1 用历史消除法 T(n+1) - T(n) = T(n)，即T(n+1) = 2T(n)，故T(n+1) = 2^(n-1) (T(1) + c) 3.6 一些有用的证明论据 算术级数 Sigma n = n(n+1)/2 几何级数 Sigma c^(n-1) = (c^n - 1) / (c - 1)，如果0<c<1，则无穷几何级数为1/(1-c) 平方和 Sigma n^2 = n(n+1)(2n+1) / 6 调和级数 Sigma 1/n = ln n + γ + O(1/n)，其中γ=0.577...是欧拉常数 对数和 Sigma lb n = O(nlogn)
数据结构简介
4.1 引言 抽象数据类型 4.2 基本数据结构 元素：可以比较相等、可以比较大小、可被复制 数组：大小固定、连续存放、顺序固定、类型相同 记录：大小固定、连续存放、顺序固定、类型不必相同 链表：大小不定、非连续存放、顺序固定、类型不必相同 4.3 树 树的表示 显式：节点间用指针连接 隐式：利用存放位置来表示连接关系 堆 一种二叉树，满足任意节点关键字都大于或等于子节点 Insert(X) 在最后一个节点后增加节点a[n]=x 将x向上移动，比较其与父节点的大小，如果大于父节点，则与父节点交换 直到它不大于父节点或者无父节点 RemoveMax() 删除最大的根节点a[1] 将最后一个节点a[n]=x移到a[1] 将x向下移动，比较其与子节点的大小，如果不是最大的，将其与三个中最大的交换 直到它是最大的或者无子节点 二叉搜索树 一种二叉树，满足任意节点的左子树上任意节点均小于此节点，右子树上任意节点均大于此节点 Search(X) 与根比较，如果相同则结束，小则走向左节点，大则走向右节点，直到找到相同或者无节点 Insert(X) 查找x，如果找到则中止，否则，搜索在某叶子节点中止，在此叶子节点下插入这个关键字 Delete(X) 如X是叶子节点，直接删除 如X是只有一个子节点的节点，将父节点直接连接上子节点 如X是有两个子节点的节点，找到X的前驱节点B，然后删除B，将B的值赋给X节点 AVL树 每个节点左右子树高度差最多为1的二叉搜索树 插入和删除后通过旋转使树平衡 4.4 散列 如何找到冲突概率最小的散列函数 如何处理冲突 4.5 合并-查找问题 用间接的数据结构来改善算法性能 4.6 图 图G=(V,E)由节点的集合V和边的集合V组成 图的表示：邻接矩阵和邻接表 4.7 小结 动态数据结构和静态数据结构 一维结构和多维结构 |
|
|
