资源描述：
《算法分析与设计2005春.课件.第14讲 清华大学：算法分析与设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、内容提要•计算模型与计算复杂度关系NP完全性理论介绍•问题分类：【P】与【NP】类•NP－难【hard】问题，NP完全集•第一个NPC问题和NPC问题集清华大学•如何证明一个问题是NPC问题宋斌恒清华大学宋斌恒1清华大学宋斌恒2引言NPC问题•脑力劳动机械化【吴文俊先生】•P－NP－NPC问题定义及其猜想：NPC是•图灵机的停机问题：是否存在一个图灵机，他一类不可以在多项式时间内计算的问可以回答其它图灵机是否停机【既算法是有界题。的】•如果在量子计算模型中上述问题又如•原则上是否存在一般数学问题的解题步骤的判何？决问题【希尔波特第十问题
2、变种】•图灵公理：凡是可计算的函数都可以用一台图灵机来计算清华大学宋斌恒3清华大学宋斌恒4明代数学家程大位著《算法统下面介绍计算机械化的进程宗》中关于珠算的插图清华大学宋斌恒5清华大学宋斌恒61机械式手动计算机机械计算机•法国数学家、哲学家帕斯卡在1642年发明了一种机械计算机，并与1649年取得专利。帕斯卡的计算机采用一种齿轮系统，其中一小轮转十个数字，下一个小轮便转动一个数字，通过齿轮系的联动，可以进行加法和减法的运算.清华大学宋斌恒7清华大学宋斌恒8图灵图灵机模型•大半个世纪以来，数学家、计算机科学家提出了各种各样的计算模型都被证
3、明是同图灵机器等价的。这一理论已被当成公理，它不仅是计算机科学的基础，也是数学的基础之一。为纪念英国数学家Turing(1912-1954)而设立的图灵奖成为计算机界的诺贝尔奖.清华大学宋斌恒9清华大学宋斌恒10图灵机模型图灵机定义•图灵机模型用一个无限长的带子作为无限存储,•一个图灵机是一个7元组(Q,∑,Γ,δ,q0,q1,q2),其中Q,∑,Γ都是有穷集合,并且它还有一个读写头,这个读写头能在带子上读,•1)Q是状态集.写和移动:开始时,带子上只有输入串,其它地•2)∑是输入字母表,不包括特殊空白符号︺.方都是空的.当它需要保存信
4、息时,读写头就把•3)Γ是带字母表,其中:︺∈Γ,∑是Γ的子信息写在带子上.为了读某个输入或写下的信集.息,带子可能将读写头往回移动到这个信息所•4)δ:Q×Γ→Q×Γ×{L,R}是转移函数.在的地方.这样读,写和移动,机器不停的计算,•5)q0∈Q是起始状态.直到产生输出为止.机器实现设置了两种状态:•6)q1∈Q是接受状态.接受或拒绝•7)q2∈Q是拒绝状态,且q2≠q1清华大学宋斌恒11清华大学宋斌恒122多带图灵机,非确定性的图灵机•和普通图•在计算的任何时刻,机器可以在多种可能灵机相似,性中选择一种继续进行【永远选择正确只是有
5、多的，可以理解为全部分支都计算完后选个带子,每出正确的】.它的计算是一课树,不同的分个带子都枝对应着机器不同的可能性.如果某个计有自己的算分枝导致接受状态,则接受该输入.与多读写头,用带图灵机相同的是,它的计算能力与普通于读和写.图灵机也是一样的.当然他的计算速度就如图不一样了。清华大学宋斌恒13清华大学宋斌恒14现代计算机模型随机存取机RAM•类似现代计算机，有一个只读输入带、只写输出带、指令计数器、内存储器、其零号寄存器用作累加器，内存不能写，每个内存可以存放任意大的整数。有12条指令：load、store、add、sub、mult
6、、div、read、write、jump、jgtz、jzero、halt。清华大学宋斌恒15清华大学宋斌恒16练习随机存取存储程序机RASP•利用RAM设计一个计算多项式函数求值•除了程序可以存储在存储器中并可以修的程序：其中多项式为，变改，其它与RAM都一样。量为x。•考虑问题：程序是什么？输入是什么？复杂度是多少？清华大学宋斌恒17清华大学宋斌恒183图灵机模型与RAM模型计算能力RAM、RASP复杂度耗费标准和复杂性关系•均匀耗费：不论计数器内整数多长，其•定理一、上述计算模型的计算能力等读写、运算耗费均相
7、等价：既能够用图灵机计算的问题一定能•对数耗费：耗费与其二进制表示的位数够用RAM计算，反之亦然。成正比：既与数字大小的对数成正比•定理二、在对数耗费标准下、图灵机与RAM的计算复杂度可在多项式时间内相互归约。清华大学宋斌恒19清华大学宋斌恒20问题变换与复杂性归约说明•利用变换和归约可以把一个问题的复杂A∝τ(n)B：是指在完成问题A到B性归结到另一个问题的复杂性的转换过程中的转换过程需要O(τ(n))•问题A变换到问题B是指：时间。–将问题A的输入变换为问题B的适当输入通常n表示问题A的规模，如果–求解问题Bτ(n)是多项式，则称问
8、题A可在多项–把问题B的输出变换为问题A的正确解式时间内变换为问题B清华大学宋斌恒21清华大学宋斌恒22P、NP类定义AFormal-languageframework•P＝{L
9、L是一个能够在多项式时间内
