重庆大学《计算复杂性及算法分析》课程内容纲要(总)

计算复杂性及算法分析课程内容纲要主要参考书:1.主要参考书1J.E.Hopcroft等自动机理论,语言和计算导论2.主要参考书2D.E.KnuthTheArtOfComputerProgrammingV13.主要参考书3D.E.KnuthTheArtOfComputerProgrammingV34.主要参考书4G&K&PCONCRETEMATHEMATICS课程内容的安排:由于这门课程的内容来自两个不同的领域:计算复杂性和算法分析.所以有必要划分课时的安排.1次课4学时用于计算复杂性(第一讲)6次课20学时用于算法分析(第二讲..第七讲)2学时用于复习第一讲(4学时)主要参考书1-第8章-8.2,8.3,8.4;第10章-10.1主要内容是介绍图灵机.以及P与NP的一些相关概念第二讲(4学时)主要参考书1-第10章-10.1,10.2主要内容是介绍NP完全问题,Cook定理的证明第三讲(4学时)主要参考书2-第1章-1.2.1,1.2.3,1.2.5,1.2.6,1.2.8,1.2.9算法分析所会用到许多数学知识,高老师在1.2中给出了一些介绍.为了简洁我们引用这里的内容.更好的选择是主要参考书4第四讲(4学时)主要参考书2-第1章-1.2.10一个算法的分析,和数学有关的分析第五讲(4学时)主要参考书2-第1章-1.3.3对排列的应用,和程序有关的分析第六讲(4学时)主要参考书2-第1章-2.3.4.1,2.3.4.5树的基本数学性质:克希霍夫定律一种一般的程序执行时间估算的方法,以及以后要研究的内容中经常要出现的内容:通路长度第七讲(4学时)主要参考书3-第5章-5.3,5.3.1最优排序(一)复习(2学时)第一讲(4学时)主要参考书1第8章-8.2,8.3,8.4;10.1主要内容是介绍图灵机以及P和NP的一些概念.为介绍Cook定理做准备计算复杂性和算法分析是两个内容.关于计算复杂性我们以介绍Cook定理为界;关于算法分析我们以介绍G.D.Knuth的一些实际分析例子为界.这一讲介绍图灵计算模型.以及一些与NP完全问题有关的内容.目的是引出Cook的第一个NPC问题的证明.由此可以对图灵模型和NPC问题有一个入门的认识.0.难解问题比判定问题更为普遍,所以我们把计算复杂性的主要介绍定在难解问题上1.有穷状态自动机,(DFA主要参考书1-31页,2.2.1,33页,图2-4,NFA主要参考书1-37页,2.3.1,图2-9).主要涉及确定与不确定的概念2.从编译原理课程上下文无关文法的分析引出下推自动机(PDA主要参考书1-6.1.2,6.1.4).主要涉及形式化定义,分析(也称计算)过程的瞬时描述和ID3.确定性图灵机.一种非常简单的计算模型,图灵机.相比之下,C程序的状态太复杂,不能给出可以理解的形式证明.参见主要参考书1第8章-8.2,8.2.24.图灵机的瞬时描述.ID的内容(主要参考书1第8章-8.2.3)介绍一个图灵机的识别例子,仔细的研读这个例子,形成对图灵机的感性认识.还有一个自己认为成立的图灵机的计算例子.2+3=5.具体可表示为B110111B转变成B11111B.从而完成1进制的2+3=5.在主要参考书1第八章-8.2.4给出了一个做减法的例子.其行为特征类似.构造图灵机并不是一件容易的事情,主要参考书1-8.2.4给出了一种较为容易理解的状态转移图.并不难理解,可以从状态转移表得到,类似NFA,不过添加了一些图灵机必要的内容.5.发明了不确定性图灵机,它不是一种真实的计算机,仅仅是一个计算模型,而且现阶段也不可能实现,但是并不妨碍我们用它来思考.充分多的转移分支保证了恰当方式描述的问题得以充分的遍历.有些在DTMM上没有得到多项式解的问题可以在这样的计算模型上得到多项式时间解.可以这样解决的问题被称为NP问题.也就是非确定性多项式时间解.说到底,DTMM和难题们ZHIJIAN的关系就想是用定理来解决问题还是用搜索来解决问题.6.停机概念:没有移动就是停机了.接受状态一定可以等价于停机状态,但是不接受不一定停机.这个与语言有关,也与判定问题有关,不属于我们约定的内容.停机与接受没有直接的关系,但是停机对复杂度有关.7.非确定性图灵机非确定性图灵机拥有想象中的并行处理能力.如果对树进行搜索,NTMM只需要最长树支的时间,但是树有指数阶的节点.参见主要参考书1第八章-8.4.48.实际工作中更容易碰到的是难解问题.例如求解H回路,调度问题.主要参考书1第10章-8.2.读一下这一段话应该很有帮助.9.由于对这样的问题没有充分的解决方法,所以写不出来确定的图灵模型.一个搜索过程与非确定性图灵模型极为相似.如果我们假设我们有搜索分支那么多的处理器,于是我们就有了一个并行的问题解决能力.本来在串行搜索上需要指数时间的问题求解过程在这样想象的并行处理能力上就只要多项式时间就够了.因此串行多项式时间和并行多项式时间是不同的.10.现在有很多问题似乎都有前面例子的那种求解特征.没有充分的解决方法,只能通过搜索来求解.如可以用充分的方法寻求欧拉回路,但只能通过搜索寻求汉弥尔顿回路.这样的问题似乎还有串行多项式时间可以求解的可能,完全没有这种求解可能的有Hanoi塔问题.它就是一个串行指数复杂性的问题.11.问题的P类和NP类(即确定型TM和不确定型TM分别在多项式时间里能解答的问题).12.可在多项式时间内解答的问题:如果每当给定图灵机M长度为n的输入w时,M无论接受与否,都在至多移动T(n)步之后停机,则说M具有时间T(n),我们主要对T(n)是n的多项式的情形感兴趣.如果存在某个多项式T(n)和某个时间复杂性T(n)的确定型TMM,使得L=L(M),则说语言L属于P类.关于P类问题的例(290页10.1.2),这个例子提出了几个与之相关的问题.如果存在某个多项式T(n)和某个时间复杂性T(n)的非确定型NTMM,使得L=L(M),则说语言L属于NP类.关于NP类问题的例(293页10.1.4).同样是多项式时间,但是由于采用了不同的计算模型导致有极大的差别.13.从P和NP来看,由于DTMM就是没有转移选择的NTMM.于是属于P的也应该属于NP,所以NP比P大,于是就出现了NP-P.NP和P是否一样大是一个很难的问题.14.进一步需要了解的是NP-P究竟是什么?(1)可以很自然的感觉到NP-P中间的问题都一定是属于NP,这就是NP完全问题2个先决条件的第1个.这不是一个好回答的问题,下面还会做进一步的解释.(2)假定有一个问题L满足(1),并且如果所有的NP完全问题都能够在多项式时间内完成对问题L的规约(或者简化成问题的转换),那么问题L就是一个NP完全的问题.15.NP完全的问题有一个特征,只要一个NP完全的问题得到DTMM的多项式时间解,那么所有的NP完全问题都能够有DTMM下的多项式解.这样的研究使得事半功倍.但是在NP?=P解决之前,这个研究是没有实际的效果的.目前解决NP完全问题最多的手段是近似算法,拥有多项式时间复杂性的DTMM算法.虽然不能作到100%的解决NP完全问题,但是在一定的范围内,其解的精度足以应付应用的需要了.16.确定一个问题是否是NP的不是一件轻松的事情.欧拉回路就很好判断,但是H回路就很难判断.这里我们还没有计较计算复杂性.一般来讲有了充分性的描述就容易得到确定性的解决方案,也就是可以采用DTMM;但是只有必要条件或者连必要条件也没有,那只能利用NTMM作为计算模型了.在我们确认NP完全问题中一定要确认该问题是属于NP的.这在很多介绍中用的是判定实例.17.对基于比较排序算法的下限问题是通过比较树来完成的.对于这样的问题用了这样一个问题的求解结构使得我们有可能形成对比较树的分支长度有一个度量的机会.于是我们得到了该解决该问题算法的复杂性下限.尽管现在还没有介绍该内容,但是可以肯定这样的工作是已经完成了的.在这里我们并不是要介绍这个内容,但是给我们的一个启发是NTMM计算模型相当于是比较这样的二元运算,基于这样的二元运算得到了比较树.于是我们解决了这个问题.是否也可以为NPC问题中的一个(如SAT问题)确定一种恰当的运算,也基于这样的运算构建一个相关的问题结构,如果能够找到该结构上的算法下限,就可以确定P?=NP了.不过这只是一种想法,没有真正的思考过.第二讲(4学时)主要参考书1第10章-10.1,10.2,S.A.Cook的文章TheComplexityofTheorem-ProvingProcedures以及计算复杂性7.5P和NP,有必要加深对NP问题的理解,NP完全问题,Cook定理的证明课程纲要上的主要参考书1相对粗糙,主要是介绍了这个证明过程中间的主要线索,尽管如此还是显得含糊不清.所以这里结合了另外一本教材中的介绍,以及Cook的原文章.但是需要相当高的水平才能完全看懂,所以就是这样也还是一个纲要性的介绍.1.设语言L属于NP,并且NP中的每个语言都可以在多项式时间里规约到L(用多项式复杂性的算法把属于NP的一个问题的描述转换成对另一个属于NP问题的描述),则L是NP完全的.如果从问题的角度了讲,语言L所描述的问题就是NP完全的问题.附注:需要解释如何确认一个问题是属于NP的.见计算复杂性106页例7-62.一个简单的推论:把所有属于NP的语言在多项式时间里规约到语言L是一件麻烦的事情.既然在确认第一个NP完全问题的时候已经作过这样的规约,那么以后只要把已经存在的NP完全问题在多项式时间里规约到指定的问题就足以保证该问题是NP完全的了.3.Cook做的事情是依据NP完全问题的定义确定第一个NP完全问题.由此可以得到两个好处.第一是新的NP完全问题的确定就没有那么困难了;第二是只要有一个NP完全问题得到确定性图灵机上的多项式解,则所有的NP完全问题都得到这样的解.这一点可以从第一个好处中得到说明.4.介绍可满足性问题(也叫SAT问题):给定布尔表达式,这个表达式是可满足的吗?举个例子以说明此问题.图灵机用识别语言的方式来处理问题,所以必须要为SAT问题确定一个编码方案,看看这样的一个表达:x1&!(x10|x11),这样的表达方式可以用确定性的PDA来识别.于是可以肯定用这样的方式描述的表达式可以在DTMM上用多项式时间解析.Cook定理:命题逻辑的可满足性是NP完全的.证明概要:假定非确定性图灵机M在多项式时间内接受一个串的集合S,每个串s都是属于NP问题的一个描述.给该图灵机一个输入w,接受的过程会给出一个NTMM的计算路.依据该计算路可以构造出合取形式的谓词A(w),使得A(w)可满足当且仅当M接受w.这里的图灵机是单带的右端无限长,有左端头方格.用1,2,...n从左向右来命名这些方格.w属于S,其长度为n,M在多项式时间内接受w,假设有x1,x2,...,xm个带符号,q1,q2,...,qs个状态,其中q1是开始状态(这里要注意,和一般以q0为开始状态有区别,不过作为一般的理解,这个区别不算什么),qs是停机状态.注意,该计算路最多P(n)步,所以不会涉及该范围之外的方格.另外,由于问题的不同使得接受的计算路有长有短,就像多项式的阶有高有低一样,给思考带来麻烦.由于属于NP的问题一定会被NTMM接受,所以为了使讨论简单,可不失一般性的假设:不管M是否已经进入接受格局,都让M继续计算下去,但对于已进入接受格局时,其下面的计算将不移动扫描头也不改变已进入的接受状态,直到第p(n)个格局为止.只要不会生成指数复杂性的问题一律都简化.这一点也可以并且也应该用于该证明的其他地方.由此可以认为第p(n)个格局一定是停机格局.这个假设会用在下面第7个命题变元上.这里需要定义几个谓词:(1)Ci,j,t取值1当且仅当M在时刻t(即第t步)时第i个方格里有符号xi(2)Sk,t取值1当且仅当M在时刻t处于状态qk(3)Hi,t取值1当且仅当M在时刻t时读写头扫描着第i个方格附注:上一讲把状态嵌入到要接受语言的中间.像.