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

计算复杂性及算法分析课程内容纲要

主要参考书:

课程内容的安排:

第六讲 (4学时) 度

主要参考书3-第5章-5.3,5.3.1 最优排序(一) 第七讲 (4学时)

主要参考书2-第1章-2.3.4.1,2.3.4.5 树的基本数学性质:克希霍夫定律

一种一般的程序执行时间估算的方法,以及以后要研究的内容中经常要出现的内容:通路长由于这门课程的内容来自两个不同的领域:计算复杂性和算法分析.所以有必要划分课时的1次课4学时用于计算复杂性(第一讲) 6次课20学时用于算法分析(第二讲..第七讲) 2学时用于复习

主要参考书1-第8章-8.2,8.3,8.4;第10章-10.1 主要内容是介绍图灵机.以及P与NP的一些相关概念 主要参考书1-第10章-10.1,10.2

主要内容是介绍NP完全问题,Cook定理的证明

主要参考书2-第1章-1.2.1,1.2.3,1.2.5,1.2.6,1.2.8,1.2.9

算法分析所会用到许多数学知识,高老师在1.2中给出了一些介绍.为了简洁我们引用这里

主要参考书2-第1章-1.2.10 一个算法的分析,和数学有关的分析

安排.

1.主要参考书1 J.E.Hopcroft 等 <自动机理论,语言和计算导论> 2.主要参考书2 D.E.Knuth V1 3.主要参考书3 D.E.Knuth V3 4.主要参考书4 G&K&P

第一讲 (4学时)

第二讲 (4学时)

第三讲 (4学时)

的内容.更好的选择是主要参考书4 第四讲 (4学时)

第五讲 (4学时)

主要参考书2-第1章-1.3.3 对排列的应用,和程序有关的分析

复习 (2学时)

第一讲 (4学时)

计算复杂性和算法分析是两个内容.关于计算复杂性我们以介绍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).主要涉及形式化定义,分析(也称计算)过程的瞬时描述和ID

3.确定性图灵机.一种非常简单的计算模型,图灵机.相比之下,C程序的状态太复杂,不能给出可以理解的形式证明.参见主要参考书1第8章-8.2,8.2.2

4.图灵机的瞬时描述.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.发明了不确定性图灵机,它不是一种真实的计算机,仅仅是一个计算模型,而且现阶段也不可能实现,但是并不妨碍我们用它来思考.充分多的转移分支保证了恰当方式描述的问题得以充分的遍历.有些在DTM M上没有得到多项式解的问题可以在这样的计算模型上得到多项式时间解.可以这样解决的问题被称为NP问题.

主要参考书1 第8章-8.2,8.3,8.4;10.1

主要内容是介绍图灵机以及P和NP的一些概念.为介绍Cook定理做准备

也就是非确定性多项式时间解.说到底,DTM M和难题们ZHIJIAN的关系就想是用定理来解决问题还是用搜索来解决问题.

6.停机概念:没有移动就是停机了.接受状态一定可以等价于停机状态,但是不接受不一定停机.这个与语言有关,也与判定问题有关,不属于我们约定的内容.停机与接受没有直接的关系,但是停机对复杂度有关.

7.非确定性图灵机

非确定性图灵机拥有想象中的并行处理能力. 如果对树进行搜索,NTM M只需要最长树支的时间,但是树有指数阶的节点. 参见主要参考书1第八章-8.4.4

8.实际工作中更容易碰到的是难解问题.例如求解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)的确定型TM M,使得L=L(M),则说语言L属于P类.关于P类问题的例(290页10.1.2),这个例子提出了几个与之相关的问题.如果存在某个多项式T(n)和某个时间复杂性T(n)的非确定型NTM M,使得L=L(M),则说语言L属于NP类.关于NP类问题的例

(293页10.1.4).同样是多项式时间,但是由于采用了不同的计算模型导致有极大的差别.

13.从P和NP来看,由于DTM M 就是没有转移选择的NTM M.于是属于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完全的问题得到DTM M的多项式时间解,那么所有的NP完全问题都能够有DTM M下的多项式解.这样的研究使得事半功倍.但是在NP?=P解决之前,这个研究是没有实际的效果的.目前解决NP完全问题最多的手段是近似算法,拥有多项式时间复杂性的DTM M算法.虽然不能作到100%的解决NP完全问题,但是在一定的范围内,其解的精度足以应付应用的需要了.

16.确定一个问题是否是NP的不是一件轻松的事情.欧拉回路就很好判断,但是H回路就很难判断.这里我们还没有计较计算复杂性.一般来讲有了充分性的描述就容易得到确定性的解决方案,也就是可以采用DTM M;但是只有必要条件或者连必要条件也没有,那只能利用NTM M作为计算模型了.在我们确认NP完全问题中一定要确认该问题是属于NP的.这在很多介绍中用的是判定实例.

17.对基于比较排序算法的下限问题是通过比较树来完成的.对于这样的问题用了这样一个问题的求解结构使得我们有可能形成对比较树的分支长度有一个度量的机会.于是我们得到了该解决该问题算法的复杂性下限.尽管现在还没有介绍该内容,但是可以肯定这样的工作是已经完成了的.在这里我们并不是要介绍这个内容,但是给我们的一个启发是NTM M计算模型相当于是比较这样的二元运算,基于这样的二元运算得到了比较树.于是我们解决了这个问题.是否也可以为NPC问题中的一个(如SAT问题)确定一种恰当的运算,也基于这样的运算构建一个相关的问题结构,如果能够找到该结构上的算法下限,就可以确定P?=NP了.不过这只是一种想法,没有真正的思考过.

第二讲 (4学时)

P和NP,有必要加深对NP问题的理解,NP完全问题,Cook定理的证明 课程纲要上的主要参考书1相对粗糙,主要是介绍了这个证明过程中间的主要线索,尽管如此还是显得含糊不清.所以这里结合了另外一本教材中的介绍,以及Cook的原文章.但是需要相当高的水平才能完全看懂,所以就是这样也还是一个纲要性的介绍.

1.设语言L属于NP,并且NP中的每个语言都可以在多项式时间里规约到L(用多项式复杂性的算法把属于NP的一个问题的描述转换成对另一个属于NP问题的描述),则L是NP完全的.如果从问题的角度了讲,语言L所描述的问题就是NP完全的问题. 附注:需要解释如何确认一个问题是属于NP的.见<计算复杂性106页例7-6>

2.一个简单的推论:把所有属于NP的语言在多项式时间里规约到语言L是一件麻烦的事情.既然在确认第一个NP完全问题的时候已经作过这样的规约,那么以后只要把已经存在的NP完全问题在多项式时间里规约到指定的问题就足以保证该问题是NP完全的了.

3.Cook做的事情是依据NP完全问题的定义确定第一个NP完全问题.由此可以得到两个好处.第一是新的NP完全问题的确定就没有那么困难了;第二是只要有一个NP完全问题得到确定性图灵机上的多项式解,则所有的NP完全问题都得到这样的解.这一点可以从第一个好处中得到说明.

4.介绍可满足性问题(也叫SAT问题):给定布尔表达式,这个表达式是可满足的吗?举个例子以说明此问题.图灵机用识别语言的方式来处理问题,所以必须要为SAT问题确定一个编码方案,看看这样的一个表达:x1&!(x10|x11),这样的表达方式可以用确定性的PDA来识别.于是可以肯定用这样的方式描述的表达式可以在DTM M上用多项式时间解析.

Cook定理:命题逻辑的可满足性是NP完全的.

证明概要:假定非确定性图灵机M在多项式时间内接受一个串的集合S,每个串s都是属于NP问题的一个描述.给该图灵机一个输入w,接受的过程会给出一个NTM M

主要参考书1第10章-10.1,10.2,S.A.Cook的文章

Theorem-Proving Procedures>以及<计算复杂性>7.5

的计算路.依据该计算路可以构造出合取形式的谓词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的问题一定会被NTM M接受,所以为了使讨论简单,可不失一般性的假设:不管M是否已经进入接受格局,都让M继续\计算\下去,但对于已进入接受格局时,其下面的\计算\将不移动扫描头也不改变已进入的接受状态,直到第p(n)个格局为止.只要不会生成指数复杂性的问题一律都简化.这一点也可以并且也应该用于该证明的其他地方.由此可以认为第p(n)个格局一定是停机格局.这个假设会用在下面第7个命题变元上.

这里需要定义几个谓词:

(1) C 取值1当且仅当M在时刻t(即第t步)时第i个方格里有符号xi (2) S 取值1当且仅当M在时刻t处于状态qk

(3) H 取值1当且仅当M在时刻t时读写头扫描着第i个方格

附注:上一讲把状态嵌入到要接受语言的中间.像...XiqXi+1....尽管在Xi,Xi+1之间加入了状态q,但是仍旧保持了下标之间的连续性.可以理解为当前关注的带方格中有状态.这个想法在主要参考书1-8.3.1中有明确的描述.表明状态的概念是用元组来承载的,于是当前需要的信息都存在这里.所以才能保证扫描头能够同时关注当前状态和带符号.

另外计算路是用步来计量的,从一个格局转换到下一个格局就算是一步,一个时刻前进一步,那么用时刻t到时刻t+1也就相当于从格局t到格局t+1.这样的描述方便理解.

另外为了书写方便再定义一个谓词U(x1, x2, ...,xr).当x1, x2, ... xr 中恰有1个为1它取值为1

U(x1, x2, ...,xr) = (x1 | x2 | ... | Xr)&(& i!=j (!xi | !xj)) 附注:

(1)这样的谓词用来确定扫描头的工作是正常的,是符合对图灵机的定义的.这样的子表达式是究竟真还是假需要用当前的状态来认定.如r=2为例可以很清晰的描述出应该得到的效果.

(2)这些谓词的定义来自于Cook的文章.但是Cook的文章并没有提到如何具体实现这4个谓词.如果是定长的谓词应该没有问题,前面就有对SAT公式的描述,但是没有如何实现用p(n)作为界限的公式描述方式.一点个人的想法是从逻辑上能够形成对这个问题的理解,但是不容易给出具体的实现.不过对于任何一个实例来讲接受步长p(n)总是确定的整数,所以还是能够接受能理解不容易实现的说法.就好象能够理解NTM,但是无法实现NTM那样.从Cook的文章中有证明的过程,但是实在是难以理解.这里介绍的内容就作为一个入门,进一步的深入理解还需要完整的阅读Cook的原文才是.

下面可以用7个命题变元A, B, C, D, E, F, G 来构成A(w).它判断了

Q0,

Q1, ... Qp(n)是一条接受w的计算路.在Cook的原文中这里是8个谓词.在众多对该原文的解释中对这里使用的谓词的个数和意义有不同的版本.原文中基本上是基于谓词实施证明的.

判断Q0, Q1,...Qp(n)是一条接受w的计算路等同于判断如下7个事实:

1.在每个格局中,扫描头只扫描1个带方格.检查它的目的是保证这样的证明与介绍的NTM M一致.

2.每个格局中的每个带方格里只有1个带符号.检查它的目的是保证这样的证明与介绍的NTM M一致.

3.每个格局中只有1个状态.检查它的目的是保证这样的证明与介绍的NTM M一致.

4.在该计算路中,从1个格局到下一个格局,最多只能修改上一格局中被扫描方格中的符号.检查它的目的是保证这样的证明与介绍的NTM M一致.

5.正确的转移.因为NTM M就是以转移作为\计算\的.所以转移是这个仿制过程的关键.

6.Q0是M在输入w后还没有开始\计算\前的初始格局

7.该计算路的最后一个格局是停机状态

现在来构成与判断1-7相对应的命题变元A-G

(1)令At=U(H<1,t>, H<2,t>, ...H).At表示在时刻t, M的扫描头恰好扫

描着某一带方格.置A = A0 & A1 & ... Ap(n)表述了判断(1).U谓词需要O(p^2(n)),则A需要O(p^3(n)).

(2)令Bit=U(C, C, ...C).Bit表示在时刻t, 第i个带方格内只有1个带符号. B = & 0<=i,t<=p(n) Bit 表述了判断(2).这里由于i和t分别是从0到p(n),所以二维的长度是O(p^2(n)).

(3)令C=& 0<=t<=p(n) U(S<1,t>, S<2,t>, ... S). C表述了判断(3).因为DTM M的状态是常数,所以C的长度为O(p(n)).

(4)令D=& i,j,t [(C=C) | H].由于是两部分的析取,分别表示在时刻t和t+1,方格i中的带符号xj没有改变;以及当前扫描头扫描第i个带方格.根据这样2个子断言的析取,不容易形成对判断(4)的理解.具体举个例来说如果i=5,j=6,t=7,如果C=C,表示第i方格的符号没有改变,因为析取,所以结果是真;如果C!=C,表示第i方格的符号改变,尽管这个子表达式为假,也因为析取,所以结果还是真.又因为NTM M中只有当前的i,j,t的值,所以依据这样的表达式的组织,其余的只能为假,因为i,j,t的值不对.这样就保证了事实4的成立.

附注:在Cook的原文中没有这样的断言,由于该构造并不容易理解,所以当无法理解Cook的原意时,就会有许多的发明.这里就是一种发明. (5)令E

i,j,k,t=!(C&H&S)||l[C&H&S].关于正确的移动要表明只有在时刻t状态k位置i关注着带符号xj,那么才有后面的不确定转移产生的多项转移中的一项为1.如果时刻t不是前面那么严格的判定,那么后面也不会作这样的转移.

附注:这里没有做真正的转移,只是形成了正确移动的为真(1)判断.这里不像NTM M会作转移,仅仅是判断这一步的转移是否正确.同样可以像对事实4的解释那样形成具体的实例.

(6)令F=S<1,0>&H<1,0>&(& 1<=i<=n C)&(& n).它表示时刻0时的M情景.时刻0表示刚好完成M的初始工作,一次都还没有计算.注意时刻和状态是两个不同的概念,尽管它们之间有关系.

(7)令G=S.在前面已经做了的假设之下,是能够正确的判定停机.

令A(w)=A&B&C&D&E&F&G

附注:该表达式来自于<计算复杂性>,Cook文章中是8个子式的合取.可以感觉到意会的含义.

给定一个属于NP问题的语言w,就可以在多项式时间内依据NTM M的\计算\规则下构造出A(w),当w在NTM M下形成一个可接受的计算路Q0,Q1,...Qp(n).则这个计算路就可以使在A(w)中的各个命题变元中相应式子的指派为真从而使得A(w)满足,反之若有一个使得A(w)满足的指派,则可以由此找到可接受的计算路.

上述结论就是Cook定理的基本内容,细节请参看Cook本人的文章

最后提一个问题,为什么总要强调多项式时间内的转换呢?

第三讲 (4学时)

这里涉及到许多内容,不过总归起来只有一点,那就是了解各种变换的手法.熟能生巧,多能生熟.另外我们把这里所讨论的内容都局限在正整数的范围内,这样可以减少边界对学习的影响.高老师探讨了正整数之外的边界,所以如果你有这样的需要,就请做进一步的学习.

一.递归方程(1学时)(主要参考书4-第一章-1.1,网络上有该书中文版的扫描版下载)

1.递归方程是算法分析过程中的重要形式.通过这种形式可以把算法逐步得到的行为一方程的形式表达出来,从而可以得到对算法计算强度的一个度量.这样的度量会给出精确的结果.算法分析的很重要的一个部分就是求解递归方程的解.主要涉及到如下的3个方面.

(1)看看小的情况,这使得我们深入了解问题

(2)求出和证明关心的量的一个数学表达式,用归纳法证明. (3)求出和证明该数学表达式的一个闭形式 2.该章的内容容易看,建议继续看下去.

二.求和(1学时) 主要参考书2-1.2.3 1.求和的作用和表示 (1)对于和数之积的分配律

(2)改变变量:第1种:改变下标变量的名称.第2种:在范围不便的前提下改变排列.

(3)交换求和的顺序 (4)处理作用域 2.四个简单的代数运算 3.基本技术的运用

附注:高老师说的好清楚,我实在没有什么需要写的了.照着说就行

三.二项式系数(1学时)

主要参考书2-第1章-1.2.1,1.2.3,1.2.6,1.2.8,1.2.9

算法分析所会用到许多数学知识,高老师在1.2中给出了一些介绍.为了简洁

我们引用这里的内容.更好的选择是主要参考书4

1.二项式系数的定义以及形式 2.对二项式系数进行运算的基本技术 (A)用阶乘来表示: 公式(5)直接来自于定义 (B)对称条件: (D)加法公式: (E)求和公式:

公式(6) 公式(9)

公式(10),公式(11)

(C)移进和移出括弧: 公式(7)

(F)二项式定理:主要是了解二项式的形式 (G)把上标取负: 公式(17) (H)简化乘积 (I)乘积的和: 3.例 问题1:

附注:斯特林公式会在第四讲中用到的时候再介绍

四.生成函数(1学时) 参见主要参考书2-第1章1.2.9 1.生成函数的定义

有序列a0, a1, a2,... 则可以形成如下的无穷和 G(z) = a0 + a1z^1 + a2z^2 + ... 2.生成函数的定义以及意义

在分析的过程中会经常遇到递归方程.由此产生了一系列的数值,这些数值在某种规则的作用下形成了一个序列.尽管是针对同一个递归方程产生的数值,但是因为不同的层次导致相互之间好象没有关系.这对我们利用递归方程是很不利的.生成函数很好的解决了这一个问题.

(1)用生成函数来表示一个序列的完整信息.这样拥有许多值的一个序列就变成了一个单一的变量.另外在需要的时候还可以回收获得的序列.我们可以这样来理解.算法分析->递归方程->递归方程的解序列(可以用递归方程以及初始条件来描述)->形成对应的生成函数->施加需要的分析导致的运算->形成新的生成函数->回收获得的新序列(在该新序列中包含我们需要的特征).

(2)不必关心收敛的问题.就像是2个多项式的运算并不需要知道多项式的值一样.

2.使用生成函数的主要技术 (1)加法 (2)移位:

公式(20) 公式(21)

Fn表示该序列是 a0 a1 a2 ... an,

Fn-1表示该序列是 0 a0 a1 ... an-1

例:斐波那契序列 还可参见主要参考书2-第1章-1.2.8

(3)乘法 (4)微分与积分

例:求解序列1,2,3,...的前n项和

(5)回收:一般采用查表的方法.当然也可以自己推导.(这是我说的)

第四讲 (4学时)

1.面临的问题.

算法M(求极大值):并且对该算法做解释

n是端点, j是记录最大值下标的变量, k是循环变量, m保存到目前为止的最大值.

2.把克希霍夫定律用于算法M的流程图

由此得到各个步骤相应的运算次数.其中有一个量是不清楚的.这就是分析的对象

3.需要分析的目标,也就是我们要分析出被分析对象的什么特性?一般而言有以下几种 (1)极小值 (2)极大值 (3)平均值

附注:在概率和统计学中，一个随机变量的期望值（或期待值）是变量的输出值乘以其机率 的总和，换句话说，期望值是该变量输出值的平均数。期望值并不一定包含于变量的 输出值集合里。

例如，美国赌场中经常用的轮盘上有38个数字，每一个数字被选中的几率都是相等 的。赌注一般压在其中某一个数字上，如果轮盘的输出值和这个数字相等，那么下赌 者可以将相当于赌注35倍的奖金和原赌注拿回（总共是原赌注的36倍），若输出值和

下压数字不同，则赌注就输掉了。因此，如果赌注是1

美元的话，这场赌博的期望值 是：( -1 × 37/38 ) + ( 35 × 1/38 ), 结果是 -0.0526。也就是说，平均起来 每赌一次就会输掉5美分。 (4)标准离差

附注:标准离差是以绝对数来衡量待决策方案的风险，在期望值相同的情况下，标准离差越 大，风险越大；相反，标准离差越小，风险越小。

4.一个关于A的直接计算.引出概率Pnk=(n个对象的排列中满足A=k者之排列数)/n!

主要参考书2-第1章-1.2.10

一个算法的分析,看看我们要做的事情是什么

5.关于中值(期望值)的定义:实际上就是前面提供的平均值

6.方差以及计算.同时给出了离差

7.确定Pnk,给出了相应的递归方程以及初始条件:需要解释:

(1)原理性的解释:如果x1的值是n,则A的值+1.因为n是x1x2...xn中间最大的一个.它在x1位置的出现一定会改变m,并且之后只需要判定x2...xn的A值,即用掉1个n值判断出1个A值.所以以后的行为范围是(n-1)(k-1).同样可以解释后面的一半.就算是用掉1个n值也没有判断出1个A值.

(2)n个范围中发生和n-1个范围中发生的两个事件是互不相容事件,于是就可以把它们都发生的概率简单的描述成分别的乘积.

9.用上面的例来说明Pnk的求解过程

10.我们可以用一次一次的计算来获得Pnk.但是这里采用的是利用生成函数来求解.我们可以利用该生成函数形成代表Pnk的系数.

需要注意的是Pn-1,k和Pn-1,k-1都表示成Gn-1(z).由于k的值最多只能是n-1,范围是n的时候.同样但范围n-1的时候,k的值只能是n-2,所以这里就是写表示范围为n时的k仍旧是也只有前面k-1个有效,后面的结果是0.所以这2项的生成函数一样.

之后的求解过程就相对的简单.

11.得到Pnk的封闭表达形式.这里涉及到斯特林数,有2类斯特林数.第一类是把用二项式系数的形式表示出来的多项式转换成乘幂的和形式(即多项式形式).第二类斯特林数把乘幂转换成二项式系数形式.可以做个例子看看.

12.用斯特林数来表示Pnk.这里有一个需要解释的地方.即n-1和n的转换.虽然显得牵强.但是还算合理.

13.对于我们要求的特征可能是没有具体的数值,而是一种表示.于是用具体的值是不方便的,甚至根本没法算.所以这里介绍的是通过生成函数来计算平均值和方差. 14.结论 结束语

一个令人无法想象的分析过程.但是具有良好的示范效果.

第五讲 (四学时)

1.对排列的应用 排列的变换 循环记号

2.排列的乘积

一般意义下的排列乘积 循环形式的乘积以及算法:

A1.[第一遍] 对所有左圆括弧加标记,并且以加标记复写该元素替换所有的A2.[开括弧] 从左到右进行检索,找头一个未曾标记过的输入元素(如果所右圆括弧紧跟着使之与左圆括弧相对.

有元素都加了标记,则这个算法就结束).置START等于它,输出一个左圆括弧;输出此元素,并标记此元素.

3.MIX程序

基本的工作对象以及工作方式

实现该功能的MIX程序(是一种汇编程序) 4.计时

计算程序执行的总时间.这里需要把指令时间转换成基本的时钟时间.这样才能得到正确的计时.关于这一点,高老师也在115页的表中给出了指令的执行时间.可以用更为简单的程序来测试.

总执行时间 = (7+5A+6B+7C+2D+E+3F+4G+8H+6J+3K+4L+3P+5Q+6R+2S)u

主要参考书2-第1章-1.3.3 MIX程序以及对应的时间分析

A3.[置CURRENT] 置CURRENT等于公式的下一元素.

A4.[扫描公式] 向右进行直到或者是公式末了,或者找到一个等于CURRENTA5.[CURRENT=START?] 如果CURRENT!=START,则输出CURRENT并返回步骤A4A6.[关括弧] (已经找到输出中的一个完整的循环).输出一右圆括弧,并返回

的元素;在后一种情况,对它加标记并返回步骤A3. 再次由公式左边开始(从而继续扩展输出中的一个循环) 步骤A2.

前面通过克希霍夫定律给出的方程,但是这样的方程一般都不会是独立的.

从行

我们导出

23,35 30,25 40,41 62,41

A = 1 + (C - 1) C = B + (A - B)

E = 1 + R F = E + (G - 1) H = F - G

J = H + (K - (L - J)) K = (L - P) + Q

39,83,85

65,58,71 70,74,80 81,76

R = P - Q

第一和第二个方程是等价的,A=C,C=A.这里需要把这些不独立的量找出来.这个过程并不是自动化的.有碰巧的含义. 最后得到

A = C E = R + 1 H = R K = L - R

F = R + G Q = P - R

于是剩下来的变量有B,C,D,G,J,L,P,R,S 后面还会对此做严密的分析

试图以数据的重要特征来匹配这些变量.这样可以由数据特征得到执行时间.

B + C = 输入字的个数 = 16X - 1

(其中X是输入的卡片数,每张卡片包含16个MIX字) B = 输入中'('的个数 = 输入中循环的个数 D = 输入中')'的个数 = 输入中循环的个数

这里给出了未能由克希霍夫定律导出的事实

B = D

H = 输出中循环(包括单个元素的循环)的个数 J = Y - 2B

(其中Y是在输入的排列中出现的非空白字的个数,从程序中可以看出J是

除了\和\之外的那些非空白字的个数.有B个输入循环,每个循环有1个\和1个\故共2B个.所以J = Y - 2B)

P = H + Q = 输入中不同元素的个数(应该包括了单一元素循环的元素) S = 输出中单个元素的循环个数

这里B,C,H,J,P,S都是独立的参数,这些参数是预期要参与程序只之计时的. 通过分析可以得到

G + J + L = (B + C)(P + 1) 来源还没有弄清楚.

因为F=R+G,K=L-R.加在一起有F+K=G+L.所

以...+3F+4G+...+3K+4L+...=...3(F+K)+...+4(G+L)+....因为F+K=G+L,所以3(F+K)=3(G+L).所以有...+7G+...+7L+...成立.这里给出的是一个暗示.告诉我们可以通过这样的方式来组合前面给出的总执行时间公式.

按照可以统计的数据特征来描述的总执行时间: (112NX + 304X + N - 2M - Y +10U + 2V - 11)u 其中:

X = 输入卡片的张数

Y = 输入中非空白的场的个数(不包括最后的\M = 输入中循环的个数 N = 输入中不同元素的个数 U = 输出中循环的个数 V = 输出中单个元素的个数

现在需要从用15个未知变量描述的总执行时间公式得到用这6个变量描述的总执行时间 混乱开始...

这里是以能够重现高老师的变换为主,所以有很强烈的凑的意思.但是在凑的过程中能够对可检测数据特征作为公式的自变量有所理解.

原公式 = (7+5A+6B+7C+2D+E+3F+4G+8H+6J+3K+4L+3P+5Q+6R+2S)u 第一步:因为已经去掉了6个变量,代入总执行时间公式得到:

= (7+5C+6B+7C+2D+R+1+3R+3G+4G+8R+6J+3L-3R+4L+3P+5P-5R+6R+2S)u = (8+12C+6B+2D+10R+7G+6J+7L+8P+2S)u 第二步:已知B=D,代入得到:

= (8+12C+6B+2B+10R+7G+6J+7L+8P+2S)u = (8+12C+8B+10R+7G+6J+7L+8P+2S)u

第三步:因为G+J+L=(B+C)(P+1),以及J=Y-2B.现在的公式中有7G+6J+7L,缺1个J.等价变换:

= (8+12C+8B+10R+7G+6J+7L+8P+2S)u = (8+12C+8B+10R+7G+7J+7L-Y+2B+8P+2S)u = (8+12C+8B+10R+7(G+J+L)-Y+2B+8P+2S)u = (8+12C+8B+10R+7(B+C)(P+1)-Y+2B+8P+2S)u = (8+12C+8B+10R+7(16X-1)(P+1)-Y+2B+8P+2S)u = (8+12C+8B+10R+112XP-7P+112X-7-Y+2B+8P+2S)u

= (1+12C+10B+10R+112XP+112X-Y+P+2S)u = (1+12C+12B-2B+10R+112XP+112X-Y+P+2S)u = (1+12(B+C)-2B+10R+112XP+112X-Y+P+2S)u = (1+12(16X-1)-2B+10R+112XP+112X-Y+P+2S)u = (1+192X-12-2B+10R+112XP+112X-Y+P+2S)u = (-11+304X-2B+10R+112XP-Y+P+2S)u = (112PX+304X+P-2B-Y+10R+2S-11)u 其中:

X = X = 输入卡片的张数

Y = Y = 输入中非空白的场的个数(不包括最后的\B = M = 输入中循环的个数 P = N = 输入中不同元素的个数 R = U = 输出中循环的个数 S = V = 输出中单个元素的个数

采用前述命名,重新排列总执行时间公式

(112NX + 304X + N - 2M - Y +10U + 2V - 11)u 混乱结束.

附件:需要的一段程序 01 CARDS 02 PRINTER 03 ANS 05 PERM 07 08 10 11 12 13 14 15 16 17

EQU 16 EQU 18

*+24

卡片输入机设备号 打印机设备号 答案的位置

用于复写输入 输入排列

读第一张卡片

ORIG

*+1000

04 OUTBUF ORIG 06 BEGIN

ORIG

0

*+1000

IN PERM(CARDS)

ENT2 JBUS CMPA

LDA EQUALS

*(CARDS) PERM+15,2

是最后一张卡片?

等待循环完成

09 1H

JE *+2 ENT1 JBUS MOVE INC2

IN PERM+16,2(CARDS) 否,读另一张

OUTBUF *(PRINTER) PERM,2(16) 16

打印输入卡

OUT OUTBUF(PRINTER)

18 19 *

*

20 21 22 23 2H 24 25 26 27 28 29 30 1H 31 32 33 34 35 36 * 37 38

39 OPEN 40 1H 41 42 43 44

45 * 46 DONE 47 48 49 50 51

JNE 1B 重复直到输入完成

在这里,(rI2)个输入字是在

PERM,PERM+1,... DEC2 1 1 ST2 SIZE

1

ENT3 0

1 A1,第一遍

LDAN PERM,3

A 取输入的下一个元素

CMPA

LPREN(1:5)

A 是\吗?

JNE 1F

A

STA PERM,3

B 给它加标记 INC3 1

B 置下一个非空白的与元素 LDXN PERM,3

B 于rX中

JXZ *-2 B CMPA

RPREN(1:5)

C

JNE *+2

C

STX PERM,3

D 以已加标记的rX代替\INC3 1 C CMP3

SIZE

C 所有的元素都处理过了?

JL 2B

C LDA LPREN 1 为住程序做准备 ENT1 ANS

1 rI1=存后面答案的位置 ENT3

0

E A2 开括弧 LDXN PERM,3 F 寻找未加标记的元素 JXN GO

F INC3 1 G CMP3 SIZE

G

JL 1B

G

全部都加了标记,现在输出

CMP1

=ANS=

答案是恒等排列?

JNE *+2 若是,变成(1)

MOVE LPREN(3) MOVE = 0 =

在答案之后防止32个空白字MOVE -1,1(32) ENT3

0

52 53 54 55 56 58

OUT ANS,3(PRINTER) INC3 LXNZ HLT

ALF

1

) =

H

J 标记一个元素 J 向右移一步

J A3.置CURRENT(即rX) H 为输出中的一个循环开括弧

ALF

(

程序中使用的常数

ALF

24 *-3

按需要来打印诸行

LDX ANS,3

57 LPREN 59 RPREN 61 * 62 GO 63 64 66 67 68 69 71 73 74 75 76 77 78 79 80 82 83 84 85 86

60 EQUALS ALF

MOVE LPREN MOVE PERM,3 STX START INC3 LDXN

1

STX PERM,3

H

65 SUCC

PERM,3(1:5)

0

JXN 1F JMP *-3 CMPX INC3 CMP3 CMPX JE SUCC

J 跳过空格

K A4.扫描公式

70 4H 72 1H

PERM,3(1:5)

L

1 SIZE

K 元素=CURRENT? L 向右移

L 公式末了?

P A5.CURRENT=START?

JL 4B

START(1:5)

P Q

JE CLOSE STX 0,1 INC1 ENT3

1 0

Q 否,输出CURRENT

Q 再次扫描公式

R A6.关括弧

JMP 4B

MOVE CMPA INC1

Q 返回A4.

R

S 删去单个元素的循环 S

R 注意:rA=\

81 CLOSE RPREM

-3,1 -3

JNE OPEN JMP OPEN END BEGIN

第六讲 (四学时)

知道大家学过图论.但是直接的把图论的内容放到算法分析上在图论课程中没有的,更不要说这里可以是一个延展.如果实际要用,还请认真阅读细节.

树的基本数学性质

图形:定义为顶点和以及连接不同顶点的边的集合.为了分析方便,才这样定义

连通图形(不计方向):也是为了分析方便,才这样定义

自由树(生成树):n个节点,n-1条边

在第五讲中采用过的方法非常简单和直观.但是有两个不足.一个是会弄出不少非独立的变量.另一个是还漏掉了一些关系.这在电路原理的内容中有过系统的介绍.不过现在不大记得了.要完整的独立方程必须列出全部独立的节点和回路方程.然而这样的方法太费事.于是高老师给我们了一个相对简单点的方法.

将自由树直接用于分析计算机算法,从而确定(不是减少)独立的未知量.并且给出一个系统的寻找它们的方法.

1.构造程序的框图

2.求出该框图的自由树(生成树)

3.用每一条属于该图形,但是不属于自由树的边ei构成一个回路Ci. 4,按照ei的方向写出回路Ci的代数表达(书中没有给出方程的形式,不知为什么?)

5.这里形成的方程全部是独立的(注意,后面不独立的是程序中的变量,如A..S中的某些)

6.在给定的图形有n个框和m条边,见下面对定理K的注释1.于是一共有

m-(n-1)=m-n+1条不属于自由树的边.这些就是独立变量.其余的边可以通过这些独立变量的线性变换来表示.具体的表达方式有:

主要参考书2-第2章-2.3.4.1-自由树 主要参考书2-第2章-2.3.4.5-通路长度

主要参考书3-第5章-5.2-5.2.2-通过交换进行排序-算法B(冒泡排序)

(1)用线性代数的方法来解(尽管有相当的计算量,但是求解过程规范) (2)用节点方程来构造回路方程(麻烦而且混乱)

(3)用(1)的变形来完成(简洁).看看具体怎么做.因为e3出现在C0,C2,和C8中.所以描述e3这条边上遍历的次数E3=E0(C0中在e3上的贡献)-E2(C2在e3上的贡献)+E8(C8在e3上的贡献).也即ej出现在哪个Ci中,就把它带符号抄过来. 7.到此所有的边都有了基于独立变量的描述,于是就可以求A,B,...,S这样一组与具体程序紧密相关的方程了.基于的原理是进入方框的诸E之和 = 框中之值 = 离开方框的诸E之和.着就是克希霍夫定律.

8.把由程序所表示的A,B,...,S的含义代数化(如上一讲中的B+C=16X-1)并代入.得到执行时间的表示.

这里的做法比上一讲的方法规范.不必靠机灵找到需要的表示.由于这里独立变量有9个,也就是有9条属于图形但是不属于自由树的边.所以A,B,...,S中有6个变量是非独立的.由于分析程序的时候写出的变量并没有考证独立性,这里给出了系统的办法.不过在具体应用之前还需要进一步的理解和模仿.

应该把前面的例子用这里的方法再求解一遍,时间关系未能成行.

定理K注释

1. 一个图形有m条边,n个节点.构成自由树用了n-1条边,剩下的边都可以构成独立的回路.这样的边有m - (n - 1) = m - n + 1条. 附注:这样的例子.实际上前面的例子都满足这一点 2.定理K的作用是什么?不清楚

2.3.4.5 通路长度

在算法分析中,树形的\通路长度\概念很重要,因为这个量直接关系到执行的时间.我们主要关心的是二叉树的情形,因为它与计算机表示密切相关. 1.扩充的二叉树.

扩充的要么没有儿子,要么就有2个儿子.这样确实要方便的多.原来的节点是圆的,n个,扩充的节点是方的,s个.注意二叉树是自由树的一种.所以一棵树的边数比圆节点的点数少1.每扩充一个节点多一条边.有多少方节点又有多少条边.故一共n-1+s条边.

2.通路长度(处理过程中要保证是扩充的二叉树,于是才能够比较容易的明白高老师所说)

(1)外部通路长度E (2)内部通路长度I

(3)E = I + 2n 一个归纳的证明过程,添加一个内部节点,并且采用归纳法来证明.一个思路.每个内部节点连接2个外部节点.假设内部节点的通路长度是I,则外部节点的通路长度由两部分构成,一是内部通路长度本身,另一个是连接在每个内部节点的所有外部节点的边和.因为有n个内部节点,所以有2n的边和.所以等式成立.另外可以想象把在拥有n-1个内部节点的二叉树上的任意一个外节点改变成内部节点,再为该内部节点添加2个外部节点.把外节点改成内节点内部通路长度+1,本来的外节点变成内节点外部通路长度-1,但是又在新的内节点上添加了2个外节点,外部通路长度+4,实际上只多了3.于是有

3.极小通路长度的n个节点的二叉树

如果算法的计算时间可以用树来描述的话,那么最优的树形是本节的树.它使得各种各样的计算时间最小.得到该结论有一个前提,那就是遍历个树支的概率是一样的.否则就需要带权的最小通路长度,如Huffman编码.由于分析的对象一般都假设为等可能的分布,所以这里就没有再涉及带权通路长度.

这种二叉树拥有0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,...序列前n项的和的内部通路长度.单一树支的长度和内部通路长度是对计算效率的两种不同的评价依据.从完成一项任务不仅仅是完成一条树支的工作可以感到内部通路长度有更合理的应用依据.如尽管有些基于比较的排序的某一个局部的工作两可以用 lgn 来描述,但是我们仍旧用的是对该项任务的全体计算代价 nlgn.从这样的角度上来讲,这样的树对算法的分析是有用的.

通过交换进行排序

系统的交换反序的元素对偶,直到不再存在反序的对偶为止.对于n个元素的所有n!个排列,已经排好序的只有1个.这是唯一的一个顺序,其余的都是反序.因此在研究排序方法的过程中引入反序的概念是有用的.

设a1, a2, ..., an是集合[1, 2,...,n]的一个排列,如果i < j,且ai > aj,则对偶(ai, aj)称为排列的一个反序.例如3142有3个反序.(3,1),(3,2)和

En-1 = In-1 + 2(n-1)

= In-1 + 2n - 2 = In-1 + 2n - 3 + 1

En-1 + 3 = In-1 +1 + 2n En = In + 2n

(4,2).

令bj, 1 <= j <= n, 为位于j左边但大于j的元素个数.就得到排列 a1, a2, ..., an的反序表b1, b2, ..., bn.例如,排列591826473有反序表236402210.因为5和9在1的左边,5,9,8在2的左边.

算法B(冒泡排序) 适当地重新排列记录R1,...,RN;在排序完成之后,它们的键值将是有序的.即K1<=...<=KN.

B1.[初始化BOUND]置BOUND<-N(BOUND是尚不知其记录是否已处于最终位置上的最高下标; 这表示我们对此尚一无所知).

B2.[对j进行循环]置t<-0,对j=1,2 ...,BOUND-1执行步骤B3,然后转到步骤B4(如果BOUND=1,则意味着直接转到B4).

B3.[比较/交换Rj/Rj+1]如果Kj>Kj+1,则交换Rj<-->Rj+1,并置t<-j.

B4.[是否还要交换?]如果t=0,则此算法终止.否则置BOUND<-t,并返回到步骤B2.

在主要参考书3-101页有图-15

假定待排序的项目在INPUT+1到INPUT+N中,tI1存放t,tI2存放j 程序B 01 START 02 1H 03 04 05 07 08 09 10 11

ENT1

N

1 B1.初始化BOUND.t<-N

ST1 BOUND(1:2) A BOUND<-t ENT2 ENT1

1 0

A B2.对j进行循环.j<-1 A t<-0

A 如果j>=BOUND,则退出 C B3.比较/交换Rj:Rj+1

JMP BOUND LDA INPUT,2 CMPA JLE 2F

06 3H

INPUT+1,2 C

C 如果Kj<=Kj+1,则不交换

B ->Rj

LDX INPUT+1,2 B Rj+1 STX INPUT,2

STA INPUT+1,2 B (旧的Rj)->Rj+1

12 ENT1 INC2

0,2 1

B t<-j C j<-j+1

A+C rX<-j-BOUND(被修改的指令)

13 2H 15

14 BOUND 16 4H

ENTX -*,2

JXN 3B J1P 1B

A+C 对1<=j0,则转B2

这里给出一个c程序的函数,其功能应该与高老师的程序B是一样的 void bu(int a[], int n) {

int j, bound = n, t, x; do { t = 0;

for (j = 0; j < bound-1; j++) if (a[j] > a[j+1]) { x = a[j]; a[j] = a[j+1]; a[j+1] = x; t = j; }

bound = t + 1; } while (t!=0); }

用gcc -S 编译生成的汇编结果比高老师的汇编长多了,复杂多了.

冒泡程序的分析

在计时中涉及了3个量,扫描次数A,交换次数B,以及比较次数C.并且假设随机分布.因此可以假定它们形成[1,2,...,n]的一个随机排列.

一次扫描将反序表中每个非零项减1.用321->213这样依次扫描为例. 因此如果b1b2...bn是输入排列的反序表,则有

A = 1 + max(b1, b2, ..., bn) B = b1 + b2 + ... + bn C = c1 + c2 + ... + cn

//扫描次数,bj全部变成0了就结束了 //交换次数,所有的反序都要交换 //比较次数,需要单独说明

0<=j<=max(b1,b2,...,bn)

其中cj是在地j次扫描开始时BOUND-1的值.借助反序表来表示,有

cj = max{bi + i|bi>=j-1} - j

下面有例 i 元素 b0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

7 2 9 1 16 4 15 5 11 6 3 8 10 12 14 13 3 1 8 3 4 5 0 4 0 3 2 2 3 2 1 0

c1 max( 4 3 11 7 9 11 7 12 9 13 13 14 16 16 16 16)-1 = 15 c2 max( 4 3 11 7 9 11 X 12 X 13 13 14 16 16 16 X)-2 = 14 c3 max( 4 X 11 7 9 11 X 12 X 13 13 14 16 16 X X)-3 = 13 c4 max( 4 X 11 7 9 11 X 12 X 13 X X 16 X X X)-4 = 12 c5 max( X X 11 X 9 11 X 12 X X X X X X X X)-5 = 7 c6 max( X X 11 X X 11 X X X X X X X X X X)-6 = 5 c7 max( X X 11 X X X X X X X X X X X X X)-7 = 4 c8 max( X X 11 X X X X X X X X X X X X X)-8 = 3 c9 max( X X 11 X X X X X X X X X X X X X)-9 = 2 c10 max( X X X X X X X X X X X X X X X X)-10 = 不存在

因此有A=9, B=41, C=15+14+13+12+7+5+4+3+2=75.总的MIX排序时间是960u.

附注:每次扫描使得非零bj减1,公式后面的-j就是j次扫描后bj的修正结果.

第七讲 (4学时)

5.3.1 第2个自然段给出了很好的学习理由

不同键码之间基于比较的排序.用比较树来描述.一旦实施了一次比较,比较树就增长一层.所以比较树的最长树枝就是充分的比较次数

研究没有多余比较的比较次数极小化构成的比较树的树枝长度就是研究极少比较次数

一一对应导致了173页正数第3-4行结论的成立.一个想法是我们要做的事情就是找到构造这样比较次数极少化的算法.

利用斯特林公式的对数展开形成173页公式(2),但是只能得到一个大概,没有考虑上整符号.奇怪的是173页(2)也是这样的结果.展开的过程中要考虑对数的换底公式.

产生刚好n!外部节点的比较树,其上的最长树枝长度就是极少的比较次数.因此比较的次数以及比较的先后顺序就是产生极少比较的根本了.这也就是后面的基本内容.

于是我们就可以认为 lg n! 是终极的目标,需要做的是寻找恰当的比较顺序来达到这样的目标.knuth指出从是否仅仅用7次比较就可以完成对5个元素的排序.

175页公式(10)前面的不等式中21!是极少比较次数了,所以65次是不可能的.21! < 2^65.公式(10)成立

主要参考书4-第5章-5.3,5.3.1 最优排序(一)

本文来源：https://www.bwwdw.com/article/ie9w.html