《计算模型和NP问题ch》由会员分享，可在线阅读，更多相关《计算模型和NP问题ch（28页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析 Design and Analysis of Algorithms算法设计与分析算法设计与分析 Design and Analysis of AlgorithmsDesign and Analysis of Algorithms主讲人主讲人徐徐 云云Fall 2010Fall 2010, USTC, USTCPart 1 FoundationPart 1 Foundation Part 2 Sorting and Order StatisticsPart 2 Sorting and Order Statistics Part 3 Data StructurePart 3 Dat
2、a Structure Part 4 Advanced Design and Analysis TechniquesPart 4 Advanced Design and Analysis Techniques Part 5 Advanced Data StructuresPart 5 Advanced Data Structures Part 6 Graph AlgorithmsPart 6 Graph Algorithms Part 7 Selected TopicsPart 7 Selected Topics chap 34 chap 34 Computation Models and N
3、PComputation Models and NP- -CompletenessCompleteness Part 8 SupplementPart 8 Supplement第第3434章章 计算模型和计算模型和NPNP完全完全 34.1 34.1 引言引言 34.2 34.2 图灵机模型图灵机模型 34.3 NP34.3 NP完全问题完全问题2010-11-1算法设计与分析434.1 引言?早期的计算模型?算法与计算模型的关系?计算模型的作用?图灵机与语言识别问题?通用的图灵机2010-11-1算法设计与分析5早期的计算模型?Recursive Function Theory Kleene
4、, Church, Turing, Post, 1930s?Turing Machines Turing, 1930s?RAM Machines von Neumann, 1940s?Cellular Automata von Neumann, 1950s?Finite-state machines, pushdown automata various people, 1950s?VLSI models 1970s?Parallel RAMs, etc. 1980s2010-11-1算法设计与分析6算法与计算模型的关系?非形式地说，算法是为实现某个任务而构造的简单指令 集。这是一个非严格的算法
5、定义。?1900年，Hilbert在巴黎举行的世界数学家大会上提出 了23个数学问题，其中第10个问题是要设计一个算法来 测试多项式是否有整数根，他没有用算法这个术语，而 用这样一句短语：“通过有限多次运算就可以决定的过 程”。?该问题是算法上不可解的，1970年由Yuri Matijasevic解决。?关键在于算法的精确定义，后来由Church和Turing分别解决， 从此称为丘奇-图灵论题。?Church使用演算定义算法和Turing使用图灵机定义算法。?现在严格地讲，一个问题算法可解的等于该问题在图灵 机上可解(可判断)。2010-11-1算法设计与分析7计算模型的作用?对于一个计算任务
6、，有两个问题要解决:?该计算任务能否在一个计算机上实现？?该计算任务在一个计算机上实现的复杂度？?计算模型可以帮助我们解决上述问题，本课程 我们主要学习图灵机模型。?计算模型的主要作用：?可计算性：将问题按计算模型的可计算性进行分类。 也就是回答一个问题在某种计算模型上是否可计算， 而不计较其计算时间的长短。?计算复杂性：将问题按计算模型的计算复杂性(时间 和空间)进行分类。?可编程性：在计算模型下算法的实现。2010-11-1算法设计与分析8图灵机与语言识别问题（1）?语言识别问题和包含关系：Type 0 短语结构文法Type 1 上下文相关文法 Type 2 上下文无关文法Type 3 正
7、则文法2010-11-1算法设计与分析9图灵机与语言识别问题（2）?有限状态自动机能够识别正则文法生成的语言 ；?下推自动机能够识别上下文无关文法生成的语 言；?线性有界自动机能够识别上下文相关文法生成 的语言；?然而上述自动机不能识别短语结构文法生成的 语言。图灵机能够识别短语结构文法生成的所 有语言，是一种能力很强的计算模型。2010-11-1算法设计与分析10通用的图灵机（1）?TMs we saw executed a specific algorithm?A different TM needed for a different alg.?Or, re-wire the machin
8、e?Turing (in 1936) foresaw the stored-program computer?Flexibility to execute different algorithms?Turing describes a Universal TM?“a TM is a general model of computation”?Means: any algorithmic procedure that can be carried out (by a human or a computer) can be carried out by a TM?First formulated
9、by Alonzo Church (1936)?Referred to as Churchs thesis also?Not a precise statement because “algorithmic procedure” is undefined ? cannot prove2010-11-1算法设计与分析11通用的图灵机（2）?The thesis is generally accepted, because?Nature of model indicates all steps crucial to human computation can be carried out?No o
10、ne has proposed an “algorithmic procedure” that cannot be implemented in TM ?Various enhancements do not enhance the computing power?Other theoretical models have been shown to be equivalent to a TM第第3434章章 NPNP完全完全 34.1 34.1 引言引言 34.2 34.2 图灵机模型图灵机模型 34.3 NP34.3 NP完全问题完全问题2010-11-1算法设计与分析1334.2 图灵机
11、模型?确定型图灵机?确定型图灵机计算示例?非确定型图灵机2010-11-1算法设计与分析14确定型图灵机DTM（1）?图灵机模型(Turing 1936)：最通用的计算模型?能做现代计算机所能做的一切；?但实现的效率和方式有所不同。?思想源于：模仿人在一个无限长的带格子的纸带 上写字?人使用一个带橡皮头的铅笔来写字；?写字从某个格子开始，或者仅仅读取该格子中的符号 ，或者擦取该格子中的符号并写上一个新的符号；?写字以这种连续方式进行：沿着纸带的两个方向，向 相邻的格子进行写字和读字。2010-11-1算法设计与分析15确定型图灵机DTM（2）?两端无限长的带子，带子可读可写，带子作为输入设 备
12、、存储设备和输出设备；?有限状态控制器只含有限个状态，其中有开始状态、 接受状态和拒绝状态；?读写头可左移右移，取决于当前状态和当前格子中的 符号；?一个单步移动的构成：当前格子中读或写，改变状态 ，根据状态确定左移/右移/停机；有限状态控制器111 111000000 0BBB12010-11-1算法设计与分析16确定型图灵机DTM（3）?图灵机的形式定义：A TM is T=(S, I, f, s0 , saccept, sreject) ，where?S : a finite set of states?I: a finite input alphabet (excluding blan
13、k B)?f: is the transition function: S I ?S I R, L fmay not be defined for some points?s0: the start state?saccept: the accept state?sreject: the reject state2010-11-1算法设计与分析17确定型图灵机计算示例?示例：构造一个图灵机求两个非负整数n1与n2的和 解：初始带上的数据如下：通过状态变化五元组(即f)，使得停机时带上产生连续的n1+n2+1个1 下面设计状态变化五元组有： (s0,1,s1,B,R) /当前状态和数据(s0,1
14、)-(s1,B)，并右移 (s1,*,s3,B,R) /s3不定义状态转移函数，使得机器停机 (s1,1,s2,B,R) (s2,1,s2,1,R) /当前状态和数据为(s2,1)时，右移 (s2,*,s3,1,R) /当前状态和数据为(s2,*)变换到(s3,1) 开始时机器读写头指向最左端的1，状态为s0，以后状态变化序列为： n10: (s0,1,s1,B,R), (s1,1,s2,B,R), (s2,1,s2,1,R),(s2,1,s2,1,R), (s2,*,s3,1,R) n1=0: (s0,1,s1,B,R), (s1,*,s3,B,R)B11B11*B1111Bn n1 1+1
15、+1n n2 2+1+12010-11-1算法设计与分析18非确定型图灵机NTM有限状态控制器111 111000000 0BBB1猜想模块?分为猜想阶段和验证阶段；?不现实的计算?现实中的计算方式都是确定的 ?解SAT问题的一个非确定型算法?第一步：猜测一个变量的真值赋值； ?第二步：检查该赋值是否满足 ?非确定型算法的计算时间：?各种可能的计算过程的最短时间第第3434章章 NPNP完全完全 34.1 34.1 引言引言 34.2 34.2 图灵机模型图灵机模型 34.3 34.3 NPNP完全问题完全问题2010-11-1算法设计与分析2034.3 NP完全问题?算法与好的算法?P问题与
16、NP问题?计算难度的比较规约?NP完全问题?P?=NP（P-NP问题）?如何处理NP完全问题2010-11-1算法设计与分析21算法与好的算法?算法：?非严格的说，算法为实现某个任务而构成的简单指 令集，有穷的计算良过程；?严格的说，算法是一个图灵机。?好的算法：多项式时间算法?指数时间算法往往在实际中不可接受；?好的算法在各种计算模型上是多项式时间等价的；?是否所有的问题都有好的算法？?SAT问题，和?TSP（Traveling salesman problem) 等，?猜测没有多项式时间算法（J.Edmonds 1965）2010-11-1算法设计与分析22P问题和NP问题?判定问题：只有肯定和否定两种答案?优化问题可以化作判定问题处理；?P问题：?具有多项式时间算法的判定问题类；?NP问题：?在非确定型图灵机上多项式时间可解的问题；?在确定型图灵机上多项式时间可验证的问题；
