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