https://www.youtube.com/playlist?list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp
1. 1. Course Overview, Interval Scheduling
本课程内容包括:
本课程将在006基础上提高难度,探讨算法在理论和实际应用上的差异。
Hamilton环问题是NP完全问题的一个例子。
区间调度问题指在有限资源下安排多个任务的问题。
具体来说,问题设置如下:
问题目标是找到一组不重叠的任务进行安排,利用资源最大限度地完成任务。
随着问题设置的增加,问题的难度也在变化:
凸轮图是指包含所有点的最小凸多边形。给定平面上的一组点(x,y坐标),求解凸轮图就是找出形成凸轮图轮廓的所有线段。
线段表示为连接两个点形成的线。只有当线将平面分割成一个半平面内含所有点时,该线才是凸轮图的一部分。
直接穷举算法中,对每个点对生成线段,检查是否满足上一条件。时间复杂度为O(n^3)。
使用分治法可以提升效率:
合并阶段就是找到两个子图公共的线段,再添加横跨两子图的新线段。时间复杂度降低至O(nlogn)
中值问题是找出一个数据集合的中位数。
直接方法为先排序,然后输出中间元素。时间复杂度O(nlogn)
使用分治法:
两组中值就可以限定原问题中值的可能范围。重复上述过程可以在O(n)时间内求解。
矩阵乘法是将两个矩阵的元素相乘并求和得到新的矩阵。
具体来说,如果A是m行n列的矩阵,B是n行p列的矩阵,则A与B的乘积C是m行p列矩阵,其元素c_{i,j}计算为:
c_{i,j}=a_{i,1}b_{1,j}+a_{i,2}b_{2,j}+…+a_{i,n}*b_{n,j}
对于m行n列矩阵A和n行p列矩阵B,其时间复杂度为O(mnp),即需要mnp次的乘加操作。
主定理给出了递归算法时间复杂度的一般公式。
设递归问题可以分解成a个大小相同的子问题,每个子问题的规模是原问题的1/b分之一。解决每个子问题需要O(n^d)的时间。
则该递归算法的时间复杂度为:
其中a、b、d为问题固有的常数。
矩阵乘法将原问题分解成n/2个大小相同的子问题,每个子问题规模为原问题的1/2。解决每个子问题需要O(n^3)的时间。
这里a=b=2,d=3,满足d=log_b a条件。
根据主定理,矩阵乘法的时间复杂度为O(n^3logn)。
多项式可以用以下几种表示方法:
A. 系数向量表示法
用向量a=(a0,a1,…,an-1)表示多项式各项的系数。
B. 样本点表示法
用(x1,y1),(x2,y2),…,(xn-1,yn-1)表示多项式在各个点的取值。其中xi为采样点,yi为对应点的值。只需要n-1个样本点就能完全确定一个n次多项式。
多项式运算常见操作包括:
评估:给出多项式a(x)和一个点x0,计算a(x0)的值。利用Horner算法可以在O(n)时间内完成。
加法:给出两次多项式a(x)和b(x),计算它们和c(x),其中c(x)=a(x)+b(x)。直接相加对应的项即可,也是O(n)时间。
乘法:给出两次多项式a(x)和b(x),计算它们积c(x),其中c(x)=a(x)×b(x)。直接乘对应项会导致时间复杂度为O(n^2)。利用分治思想,可以设计出一个O(nlogn)的FFT算法来完成。
FFT算法的思想来源于多项式乘法与卷积运算之间的等价关系。卷积运算常用在数信号处理如MP3压缩等场景,也就是给出两个信号向量,计算它们在所有偏移量下的内积和。这等价于给出两次多项式,计算它们的积。FFT可以高效地计算卷积,从而解决了乘法问题。
2-3树和B树都是平衡搜索树,用于实现查找效率为O(logn)的字典型数据结构。
2-3树是一种近似平衡的多叉搜索树。每个节点至少有2个子节点,最多有3个子节点。
搜索过程与二叉搜索树类似,根据键值与节点中的键值进行比较,选择对应的子树继续搜索。
B树扩展了2-3树的概念,具有更高的节点容量和更宽松的平衡标准:
搜索过程与2-3树相同,按键值与节点内键值比较后选择对应的子树搜索。
B树相对二叉搜索树,能更好利用内存高速缓存,降低磁盘访问次数。因为B树节点容量大,每次从磁盘读取整个节点。
最后,2-3树和B树的搜索、插入和删除复杂度均为O(logn)。
万鬼·巴斯树结构将数据元素分离到宇宙里不同的簇(称为星系)。每个簇内部使用一个简单的数组来存储元素。数组的每个单元对应数据元素的值,存储0或1来表示该元素是否包含在集合中。
为每个簇建立一颗树,树的每个节点表示两个下级子节点对应的簇的并集。根节点表示所有簇的并集。通过计算节点的0/1值,可以快速排除不含元素的簇,实现 succeeds 查询的加速。
可以继续将每一个簇(星系)再细分为更小的簇,对新的簇重复上述构建树的过程。通过多次递归,实现问题规模从u逐步缩小为$\sqrt[2]{u}$的效果,从而将时间复杂度降低到O(loglogu)。
利用树结构进行二分搜索,先在顶层树中判断元素属于哪个更大簇,然后在该簇对应的子树中继续搜索。以O(loglogu)的时间复杂度支持前驱 predecessors 和后继 successors 查询。
万鬼·巴斯树适用于IP地址范围查询的路由表应用场景。IP范围划分为簇,利用树表示不同范围的“或”关系,快速定位包的发送端口。与平衡二叉搜索树O(logn)相比,万鬼·巴斯树大大降低了时间复杂度。
平均分析法是一种分析数据结构操作成本的方法。它允许某些操作的实际时间成本高于平均时间,只要所有操作的总时间负担在一个合理的界限内。
累计法是最简单的平均分析方法。它计算所有操作的总时间成本,然后将其除以操作数,得到每个操作的平均时间成本作为界定。
在哈希表中使用链地址法时,数组大小m如果小于元素数量n,需要扩容数组。扩容操作包括分配新数组、重新散列以及复制元素,时间成本为O(m)。但是如果每次扩容都翻倍m,总共只需要O(logn)次扩容,合计时间成本为O(n)。因此每个插入操作的平均时间成本是常数级。
假设2-3树上的操作包括:创建空树(常数时间)、插入(O(logn)时间)和删除(O(logn)时间)。我们可以认为删除的平均时间成本是0,因为删除元素数量不能超过插入元素数量。将三种操作的实际总时间成本加起来,最多为插入数量×O(logn),所以平均每个操作的时间成本是O(logn)级。
会计法将时间视为货币。操作可以向“银行账户”存入“钱”,以补偿将来可能出现的高成本。插入操作可以向账户存入一定数量的“钱”,以支付将来因为结构调整可能产生的额外成本。删除操作从账户中提取之前存储的“钱”来抵消实际成本。只要账户余额永远大于等于零,就可以确保平均每个操作的时间成本在一个合理的界限内。
平均分析法通过将操作划分为各种类型,并给每个类型操作指定一个时间界限作为其平均成本,从而管理结构中的成本,确保结构的整体时间效率。它允许个别操作的实际成本暂时超出平均成本,只要在长期内都在预期范畴内即可。这对许多算法和数据结构的设计和分析都很重要。
随机算法是会产生随机数的算法。随机数可以是海变率、实数或向量。算法会根据随机数的值作出决定。
随机算法可以是递归的。在每级递归中都会产生随机数。因此,不同执行可能得到不同结果或花费不同时间。
随机算法按正确性和效率可分为:
矩阵乘法校验:随机检查积矩阵中的一些项是否与输入矩阵相符,可以检验积矩阵是否正确。这是Monte Carlo算法。
快速排序:确保每次都可以得到有序数组结果。但平均运行时间是线性对数时间。这是Las Vegas算法。
矩阵乘法的简单算法时间复杂度是O(n^3)。它通过计算各行各列的乘积来得到积矩阵中的每个项。
在算法分析中,我们只考虑乘法次数,因为乘法在计算机中比加法更耗时。
Strassen算法用7次乘法取代8次乘法,将时间复杂度降低到O(n^{2.81})。
Coppersmith-Winograd算法时间复杂度达到2.376,之后有进一步提升。
但是这些算法常数极大,在实际应用中较难采用。
随机选择算法是采用随机化思想的中位数查找算法的一种广泛化版本。其工作原理如下:
由于选择划分点X是随机的,无法确定 problem size 的减小程度。因此我们分析其平均运行时间:
设 T(n) 为问题大小为 n 时的平均运行时间。可以写出递归关系:
T(n) = O(n) + Max{E[T(K-1)], E[T(n-K)]}
其中 K 是随机选择的划分点。将其展开为期望,得到T(n) = O(n)
随机快速排序算法与随机选择算法差异仅在于:
T(n) = O(n) + E[T(K-1)] + E[T(n-K)]
展开后也可以得到 T(n) = O(nlogn) 的平均运行时间。
总之,通过随机化选择划分点,随机选择算法和随机快速排序算法都获得了线性或对数线性的平均运行时间,比确定性算法有明显优势。
跳跃表是一种随机化的数据结构,它能在平均情况下实现对数级时间复杂度的搜索、插入和删除操作。
跳跃表的基本思想是:构建多个有序链表,高层链表包含了低层链表的部分节点。高层链表实现长距离跳跃,低层链表实现精细搜索。
构建跳跃表时,每个节点都有概率生成在高层链表中。生成方法是:给每个节点一个“层数”,层数符合几何分布。最底层为0层,向上层数增加。
这样一来,越往上层链表的节点越少,但范围越大,实现跳跃效果。最顶层可能只有个别节点,但可以使搜索跳过很大范围。
跳跃表的搜索算法如下:
从最高层链表最左端开始向右搜索。
找到第一个大于或等于目标值的节点位置,判断是否到达链表尽头。
如果没有超过,说明需要下跳,进入下一低层链表继续向右搜索。
如果超过了,说明需要返回,进入同层链表向左搜索。
按此方法,我们依次搜索各层链表,直到找到目标值或搜索失败为止。
插入和删除的具体实现方式也比较简单:
插入:找到插入位置,生成节点层数,依次在各层链表中插入节点
删除:依次在各层链表中删除节点
由于跳跃表采用随机方式构建,其基本操作时间复杂度是一个随机变量。
通过概率分析可以得到,当 n 个元素时,搜索的平均时间复杂度为O(logn)。
而且,我们可以通过进一步分析证明:对任意给定的常数c,当n足够大时,搜索时间小于c*logn的概率大于1-1/n^c。
这就是我们所说的“以很高概率”时间复杂度为O(logn)。这比平均时间强很多,提供了更强的保障。
总之,通过简单但有效的随机化技术,跳跃表实现了使用链表就能获得的最优对数时间搜索效率。而且证明也相对简单。它是一种非常优秀的动态数据结构。
字典问题规定了如下三个操作:
查找操作只是简单地判断该 key 是否存在,如果不存在则无法获取任何信息。
哈希表包含两个重要变量:
哈希函数会将 key 映射到 0 至 m-1 的槽位上,每个槽位形成一个链表存储哈希到该槽位的所有 item。
通过分析得到哈希表的平均搜索时间复杂度为 O(1 + α),其中 α 为负载因子 n/m。
6006 课程分析时假设哈希函数满足“简单统一哈希”,即:
但这是一个不切实际的平均案例假设。
保证不同 key 永远不会映射到同一槽位,此时复杂度为 O(1),但只适用于静态数据。
通过随机选择哈希函数来引入随机性。我们从一组哈希函数家族中随机选择一个函数作为映射函数。
此方法可以实现动态数据的 O(1) 之内时间复杂度,且不需要任何 average case 假设。
选择哈希函数家族使不同 key 映射到同一槽位的概率为1/m。
通过随机选择哈希函数,期望解决冲突的槽位链表长度为 O(1),从而实现期望时间复杂度为 O(1) 的插入、删除和查找操作。
动态规划的主要思想是将问题分解成子问题,并利用已经解决的子问题的结果。在课程中我们经常关注算法的时间复杂度。
给定一个M×N格子,一个机器人从(1,1)出发,每次只能向右或向上移动一格,求从起点到终点(M,N)有多少条不同的路径。
分解问题:每个点的路径数等于其左上角和上方点路径数之和。所以时间复杂度为O(MN)。
给定面额硬币{1,5,10,…}和一个金额N,找出组成N的最少硬币个数。
暴力解:尝试所有组合。若选择面额为s的硬币,则子问题为原问题减去s。时间复杂度O(MN)。
这个问题实际上等价于背包问题,但使用暴力解法得到的时间复杂度没有正常体现问题的真实复杂性。
给定N种不同大小的立方体块,每个块有长度、宽度、高度。能够将某块B放在块A上方的条件是B的长度和宽度均小于A。要求堆叠块的最大高度。
分解问题:对每个块,找到其兼容的剩余块集合,与之组成子问题。兼容块集合大小不超过N。时间复杂度O(N^2)。
数据结构增强技术可以将其他数据结构进行改造,增加额外功能。
边界树可以支持在有序数集合中快速查询哪些元素处于给定范围内。
边界树是一种平衡二叉搜索树,每个节点额外存储以该节点为根的子树中最小和最大元素的值。
插入:加入新元素,同时更新节点的最小和最大值。时间复杂度O(logN)
删除:删除元素,同时更新节点的最小和最大值。时间复杂度O(logN)
范围查询:给定一个范围[x, y],找出这个范围内的所有元素。首先定位范围[x, y]会包含哪些子树,然后在这些子树中递归查询。时间复杂度O(logN + K),K是查询范围内的元素个数。
实现边界树需要满足数据结构增强的条件:
节点额外存储其子树范围(最小值和最大值)
可以通过子节点信息高效计算父节点范围
更新只需要在结点路径上进行,不会影响其他分支
这样可以保证插入、删除和范围查询的时间复杂度都是O(logN + K)。
动态规划是一种算法技术,可以用来解决时间复杂度看似指数级的问题。它的核心思想是:
给一个字符串序列,找出其最长的回文子序列。
假设序列为 x1,…,xn,那么:
用 lij 表示子序列 xi,…,xj 中最长回文子序列的长度。
随着问题难度增加,状态定义和状态转移关系会更为复杂。但动态规划的基本思想:分解问题->表达子结构->避免重复计算仍然成立。
在有向图中,给定源点s到其他任意点v的最短路径权值定义为δ(s,v)。权值可能为正 infinity 或者负infinity:
如此定义可以使得最短路径问题在任何情况下都是良好定义的。
无权图:使用广度优先搜索BFS,时间复杂度O(V+E)
非负权图:使用Dijkstra算法,时间复杂度O(VlogV+E),使用斐波那契堆可以达到O(E+VlogV)
一般权图:使用贝尔曼-福特算法Bellman-Ford,时间复杂度O(VE)
有向无环图:使用拓扑排序后贝尔曼-福特算法,时间复杂度O(E)
给定有向图G(V,E)和权值函数w,找出对任意点对u,v都计算δ(u,v)。
分别从每个点运行单源算法,时间复杂度为:
对一般权图,可以通过Johnson算法在O(V^2logV+VE)时间内解决问题,优于直接运行V次单源算法。这证明了即使存在负权也可以使用与非负权相同的效率来解决问题。
贪心算法是解决一个问题时,总是做出在本地最佳的选择的算法。它常用于一些子问题具有最优子结构的问题。
最小生成树问题是找出一棵包含所有顶点的树形结构,且该树的边权和最小。
给出一个带权有向图G。权值函数W给出每条边的实数权值。目标是找出G的一个生成树,且其总边权和最小。
生成树即包含G所有顶点的连通无环图。
贪心算法一般需要满足以下两个性质:
最优子结构性(Optimal Substructure):如果子问题能够得到最优解,那么原问题就能得到最优解。
贪心选择性质(Greedy Choice Property):通过执行一系列本地最优选择,就能得到全局最优解。
假设知道最小生成树中的一条边e,则可以用以下方法简化问题:
删除边e后,图分成两个部件A和B
独立求出A和B中的最小生成树
将A和B的最小生成树通过边e连接起来,即为原问题的最小生成树
这说明如果子问题(A和B部分)能得到最优解,原问题也能得到最优解。
prim算法:从任意一个点开始,每次选择与已构造树相连并且权值最小的边,加入树中,直到构成一棵生成树。
Kruskal算法:按边权从小到大排序所有边,然后依次添加不形成回路的边,直到成为一棵生成树。
两种算法的时间复杂度均为O(ElogE),其中E为图中的边数。它们都满足贪心选择性质。
假设有n种金属,每种金属的价值以美元/千克表示。需要获得价值T美元的礼物。每种金属的数量有限制。问题是用最少的总重量获得价值T美元。
贪心算法:
按金属的单位价值从高到低排序
取价格最高的金属,计算采取的数量
如果数量大于限定值,则全部采取;如果小于限定值,则采取足够的数量
重复步骤2,直至价值累加达到T
证明:
如果不采用单位价值最高的金属,而采用单位价值次高的金属,则采集的总重量将更大。
给定n个进程,每个进程时间Ti(i=1~n)。问题是如何安排顺序,使平均完成时间最小。
平均完成时间定义为:所有完成时间之和/进程数
每个进程的完成时间定义为:前面所有进程耗时之和
贪心算法:
按进程时间从小到大排序
安排顺序依次为排序后的进程顺序
证明:
交换任意两次顺序,都可以减小平均完成时间。
给定一组事件区间。每个事件有开始时间和结束时间。问题是用最少的”人”或者”机器”完成所有事件。
贪心算法:
按结束时间从早到晚排序事件
依次安排第一个未安排事件到当前”人”或”机器”上
如果时间重合,则新建”人”或”机器”
重复2-3步,直至所有事件安排完毕
证明:
所得到解是最优解,因为贪心选择顺序不会使解变差。
流网络是一个有定向边的图,其中包含源点s和汇点t。每个有定向边(u,v)都有非负容量C(u,v)。如果(u,v)不在图中,则C(u,v)=0。
流是一个将源点s到汇点t的数字分配函数。对每个有定向边(u,v),流f(u,v)必须小于等于边的容量C(u,v)。对除s和t之外的任意点v,输入流与输出流之和必须相等,遵守流的守恒定律。
最大流问题是找到一种流函数,使源点s流出的数量最大,同时满足所有边和点约束。这是一个线性规划问题。
割面是将源点与汇点分离开来的一组边的集合。剪点是将图分成源点子图和汇点子图的一组点的集合。
最大流最小割定理指出在任何流网络中,最大流的量等于最小割的容量。它是流网络的一个重要定理。
最大流最小割定理导致第一个最大流算法 - 福特-福尔克森算法。它通过不断增量地从残余网络中增加流来求解最大流问题,直到无法再增加流时停止。
网络流是一个有向图,每个边都有两个数字相关联,一个流值和一个容量。
流网络满足以下几个规则:
流的大小不能超过边的容量。
除源点和汇点外,每个节点流入的流量等于流出的流量(流守恒)。
最大流问题是找到流网络中从源点到汇点的最大可能流量。
Ford-Fulkerson算法解决这个问题,它通过不断在残余网络中搜索增广路来增加流值,直到没有增广路为止。
残余网络Gf是一个依赖当前流f的新网络,它包含那些容量大于流值的边。
增广路是一个源点到汇点的路径在残余网络Gf中。如果存在增广路,流还未达最大,可以沿增广路增加流值。
增广路的残余容量定义为增广路上各边最小的残余容量。每次沿增广路增加的流值就是该残余容量。
Ford-Fulkerson算法初始化将所有边流值设为0,循环搜索Gf中的增广路,并使用增广路的残余容量来增加流值,直到找不到增广路为止,此时流就达到最大。
最大流最小割定理表明:最大流等于任意一个割(通过源点和汇点将图分为两部分的边集)的容量下限。这解释了为什么Ford-Fulkerson算法终止时流就是最大的。
网络流是一种算法模型,用于解决在图中从源点到汇点的最大流量问题。
最小价格流算法即弗朗绍夫算法可以解决这个问题。它的步骤如下:
弗朗绍夫算法的一个局限是,每次增广的路径可能很长,效率不高。
而额外克普拉算法可以解决这个问题。它每次都查找源点到汇点的最短路径来增广流。可以证明额外克普拉算法的时间复杂度是O(V^2E)。
网络流有两个重要的应用:
好处匹配问题:给定二部图,查找最大匹配。可以转化为网络流问题求解。
覆盖问题:给定有向图,求最少顶点覆盖所有边的子集。也可以转化为网络流问题求解。
额外克普拉算法可以高效地解决这两个问题。
线性规划是一种广泛应用于各种优化问题的技术,可以解决6.046课程和006课程前面看到的很多问题。
简单来说,线性规划采用线性限制条件和线性目标函数来描述最优化问题。它关注变量的值而不是变量本身,变量的值必须是实数。
假设我们要通过广告买下一次选举,目标是以最小花费获得三个群体(城市、郊区、农村)超过一半票数的胜利。
我们有四个广告主题:修路、枪支控制、农业补贴、汽油税。根据每一群体对不同主题的支持程度,我们得到了每1美元广告花费能获取的票数表。
此外,我们还需要知道每一群体的人口数量,以计算需要获取的最小票数。
我们将广告花费看作变量:$x_1$代表修路,$x_2$代表枪支控制,$x_3$代表农业补贴,$x_4$代表汽油税。
目标函数是最小化$x_1+x_2+x_3+x_4$
我们有三个不等式限制条件来表示在每个群体中需获胜:
对城市群体:-2$x_1$+8$x_2$+0$x_3$+10$x_4≥50000$
对郊区群体:5$x_1$+2$x_2$+0$x_3$+0$x_4≥100000$
对农村群体:3$x_1$-5$x_2$+10$x_3≥70000$
此外,$x_1,x_2,x_3,x_4≥0$,表示广告花费需为正数。
Simplex法是求解这类线性规划问题的经典算法。它以多项式时间内能求得最优解为概念框架,但实际运行时间可能是指数级的。
对这个例子,Simplex法可以找出使目标函数最小且满足所有约束的最优解:$x_1=20000/100,x_2=30000/100,x_3=0,x_4=40000/100$
总花费为$x_1+x_2+x_3+x_4=27000/100$,约等于$27000美元$。
P问题是那些我们知道可以在多项式时间内解决的问题。多项式时间指的是问题规模n的某个常数次方。
NP问题是那些不能确定在多项式时间内可以解决,但是可以在非确定性多项式时间内解决的问题。
在非确定性模型中,我们可以在常数时间内从多项式大小的选择集合中“猜测”一个答案。如果存在使问题答案为“是”的猜测,我们就能得到这样的猜测。
所以NP问题的答案可以通过“猜测+验证”的方式在多项式时间内得到。
3SAT问题是NP完全问题的代表。
给定一个公式,公式由多个子句组成,每个子句有3个词元,词元是变量或者变量的否定形。问题就是问是否存在一个变量赋值使得整个公式为true。
3SAT问题可以用以下非确定性算法解决:
如果公式为true,输出是;否则输出否。由于非确定模型会选择使问题答案为“是”的猜测,所以这个算法可以在多项式时间内解决3SAT问题。
可以把非确定性算法中的“猜测”看作是问题答案为“是”的“证书”。
如果一个问题存在多项式时间内的“验证算法”,这个算法可以在输入一个“certificate”后,多项式时间内判断这个证书是否正确证明问题答案为“是”,那么这个问题就是NP问题。
如果一个问题X满足:
那么问题X就是NP完全问题。
如果可以在多项式时间内将问题X转换为问题Y,那么问题X至少也不比问题Y更难。
如果一个问题X可以多项式时间内归约任何NP问题,那么X就是NP困难。
如果一个问题X既属于NP,同时也是NP困难,那么这个问题X就是NP完全问题。
NP完全问题代表的是计算理论中已知难度最高的问题。解开NP完全问题,就意味着解决P!=NP这个开放问题。
P问题是指可以在多项式时间内求解的决定性问题。NP问题是指在多项式时间内可以验证解是否正确,但未必能在多项式时间内找出解。
P是NP的子集。
NP难问题指的是至少与NP问题一样难解决的问题。
归约法可以用来证明一个问题的NP难性。如果已知问题A是NP难的,通过在多项式时间内将问题A转化成问题B,且问题A的答案等价于问题B的答案,那么问题B也是NP难的。
Hamilton回路问题要求在一个图中找出一个包含所有顶点且开始结束于同一顶点的回路。这是NP难问题。
Hamilton路径问题类似,但只要求包含所有顶点但无需开始结束于同一顶点。通过将一个顶点拆分成入边顶点和出边顶点,可以在多项式时间内将Hamilton回路问题转化成Hamilton路径问题,从而证明Hamilton路径问题也是NP难的。
clique问题要求在一个图中找出所有顶点都相连的完全子图。这是NP难问题。
独立集问题要求找出图中不相连的顶点集合。通过将是否存在k阶clique问题转化成是否存在大于等于k个元素的独立集问题,可以证明独立集问题也是NP难的。
NP完全问题是一类计算复杂度很高的问题。对它们来说,暂时还没有找到多项式时间的确切解法。
近似算法用于在多项式时间内找到子optimal但满足某些性质的解。
近似率用Row_n表示,定义为算法产生的解C到最优解Copt之间的比值。
Row_n可以是常数,也可以是输入大小n的函数。如果Row_n随n增大而增大,表示近似质量会下降。
近似算法工程包括:
定义一个NP完全问题。
想出一个简单启发式策略。
证明该策略的近似率Row_n。
PTAS(概率多项式时间近似方案)表示:
对任意ε>0,在多项式时间内找到(1+ε)近似率的解。
时间复杂度与n为多项式,与1/ε指数级增长。
FPTAS(完全PTAS)表示时间复杂度与n和1/ε均为多项式。
图覆盖问题是找到一个顶点集合,使其覆盖所有的边。它是一个NP完全问题。
简单贪心策略是选择每个邻边的一个顶点累加到解集中,可以得到2近似率。
参数化问题就是将一个问题和一个参数组合在一起。例如连边覆盖问题,将给定的图G和一个非负整数k作为参数。问题是是否存在一个大小不大于k的连边覆盖。
参数通常是问题的某个规模大小等量值,例如数组的长度、图中的顶点数或边数等。
固定参数可解性意味着算法的时间复杂度为O(f(k)n^c),其中n是问题输入的总大小,k是参数,f为仅与k有关的函数,c为常数。
这样算法的时间复杂度虽然随着整体问题规模n成长而增加,但如果参数k足够小,时间复杂度仍然可控。
连边覆盖问题的粗暴蛮力算法:
其时间复杂度为O(v^kE),依赖于参数k的指数项,且其中E和v为常数因子,因此不满足固定参数可解性定义。
固定参数算法是一种寻找NP难问题近似解的方法。它旨在将算法时间复杂度的指数项约束在问题的某个参数k上,从而在参数k足够小时仍保持高效。连边覆盖问题给出的粗暴算法时间复杂度依赖总问题规模,不满足固定参数可解性定义。
以上内容详细描述了使用MST构建TS问题的2近似算法以及其证明。
同步分布式网络模型描述了分布在网络中的多个节点(进程)在每一轮联合作业的计算模型。每个进程在每个轮回执行以下操作:
同步分布式算法的时间复杂度是指算法所需要的轮回数。算法的通信复杂度指发送的消息数或二进制位数。
破坏对称性问题(领导节点选择问题)的目的是在开始状态完全对称的多个进程中,选择唯一一个进程作为领导节点。
在完全连接的克利克图中(每个节点都直接连接到其他每个节点),如果进程起始状态完全相同且算法是确定性的,就无法破坏原始对称性选出唯一领导节点。因为每个进程都将采取相同行动。
同步分布式网络中最简单的问题之一是生成广度优先搜索树。每个节点通过广播消息,逐步获得整个网络的拓扑结构信息,并构建以自己为根的广度优先搜索树。
生成最短路径树问题与广度优先搜索树类似,但每个节点通过轮回交换信息,构建以自己为根的最短路径树,即从自己出发到每个其他节点的最短路径。
Luby 提出了一个基于随机性的最大独立集算法:
假设有一个根节点:
在带权图中,算法目标是构建以某节点为根的最短路径生成树:
异步算法中,每轮不再同步:
本文总结了同步和异步分布式算法 constructing shortest-paths spanning trees。
本例中使用环形网络进行领导选举。每个节点随机生成一个ID。
算法原理:
可以优化算法:
原理:
问题:环形网络无法真实进行分割
原理:
每轮规模越来越大,最终剩下的最大ID节点为领导
算法时间复杂度为O(nlogn),消息复杂度为O(nlogn)
原理:
最终所有节点计数器的值即为网络中的总节点数量
哈希函数是将任意长度的输入映射为固定长度的输出。它应当是确定性的,公开的和看起来随机的。
哈希函数将输入字符串映射到固定长度的二进制输出。输入可以是任意长度,输出通常为160位或者256位。
理想状态下,随机器可以将任意字符串作为输入,输出一个随机但确定的哈希值。它通过记录每次查询的输入输出来保持确定性。
确定性:对同一个输入,每次计算都能得到同样的哈希值。
公开性:算法和任何状态都公开透明,没有任何密钥。
伪随机性:计算结果应当看起来完全随机,难以预测两个不同输入的哈希是否重合。
冲突抗力:极难找到有相同哈希值的两个不同输入,即找到冲突。
多项时间计算:与输入长度成正比,通常需要100轮或更多的计算来提升安全性。
MD4、MD5、SHA-1、SHA-3都是基于迭代和混合设计的汉明距离和置换BOX强密钥哈希算法。随着计算能力的增加,算法复杂度不断提高以达到更高的安全等级。
对称密钥加密算法假设存在一个密钥K。密钥K可以是128位或256位数字。
加密公式:
C = e(K, m)
其中:
解密公式:
m = d(K, C)
其中:
对称密钥加密需要满足可逆性,即使用相同的密钥K和解密函数d可以将加密文本C恢复成原明文m。
对称密钥加密使用可逆操作构建加密函数e和解密函数d,例如置换、xor等操作都是可逆的。
AES是一种广泛使用的对称加密标准算法。它使用排列置换和xor操作,加密和解密实现方式相同。
对称密钥加密需要解决如何让Alice和Bob安全地交换密钥K的问题。
例如可以用海盗密码箱模型:
RSA算法是第一种保持安全的非对称加密算法。它使用大素数生成公钥和私钥,公钥用于加密,私钥用于解密。
如果不知道密钥,从加密文本推理明文应该是计算上很难的。这与NP完全问题的难度成正相关。一些密码系统就是根据NP完全问题如图着色问题设计的。
数字签名是用于验证消息正确性的机制。它由签名函数sign和验证函数verify构成。
sign函数使用密钥对消息进行签名,输出签名Σ。verify函数使用公钥、消息和签名,输出true或者false来接受或者拒绝这个签名。
我们希望数字签名具有以下属性:
正确性:如果Σ真的是通过sign函数产生的,那么verify应该输出true;否则输出false。
无法伪造:只有持有私钥的用户才能为消息签名。其他人即使看到了许多消息-签名对,也无法为之前未见过的消息生成验证通过的签名。
早期,研究人员曾提出使用公钥加密的逆函数来实现数字签名。以RSA为例:
签名函数sign: M^d mod n 验证函数verify: σ^e mod n = M
然而这个方案存在缺陷,它利用了RSA的乘法同态性,攻击者可以通过已知的消息-签名对生成新的签名。
为了解决这个问题,后来提出将消息哈希与RSA联合使用:
签名函数sign: hash(M)^d mod n 验证函数verify: σ^e mod n = hash(M)
这可以破坏乘法同态,然而由于哈希函数公开,仍可能存在其他攻击。
目前国际标准采用对哈希后的消息进行特定填充,再进行RSA运算。这保证功能但安全性无法严格证明。如何建立数字签名的理论基础仍是密码学研究的重要题目。
计算机中数据存储的层次结构包括:
随着数据存储位置的远离CPU,其访问时间也会显著增加。
当CPU访问主存单个字时,实际读入的不仅是该字,而是一个较大的块,称为阻塞。阻塞大小一般设置为使单个字访问时间与读取整个阻塞的平均时间相当。例如对于硬盘,阻塞大小可达兆字节级。
阻塞技术能将单次访问的开销平均到整个阻塞上,从而降低单字访问时间。
高效利用缓存需要满足:
算法应保证数据访问顺序满足以上两点,使得缓存命中率更高。
这类算法设计时不考虑实际缓存大小,但其访问顺序天然满足空间局部性和时间局部性,有利于缓存高效利用。后续会介绍一些代表性遗忘式缓存算法。
外部内存模型是一级隐形内存层次结构,CPU和Cache视为一个单元,内存传输速度极快。整个内存以块块的形式划分,块大小为b字节。问题规模n需要存储在磁盘上,磁盘也以块的形式划分。
算法只能读取或写入整个块,目的是最小化块内存传输次数。
Cache-oblivious模型中,算法不知道块大小b和Cache大小m,所有块读写都自动进行。当访问一个项时,如果其所在块不在Cache中会自动加载入Cache,如果Cache满会根据LRU策略淘汰最久未使用的块。
假设时间线可以划分为相对独立的相位。每个相位包含m/b个不同块的访问序列。
在每个相位中,LRU的块读取次数上限为m/b。OPT使用半数Cache(m/2)时,每个相位最少需要1/2m/b次块读取。
所以LRU算法在Cache大小m时,其块读取次数最多是OPT在Cache大小m/2时最优块读取次数的2倍。