算法设计与分析 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 Data 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 NPComputation 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, 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算法与计算模型的关系?非形式地说，算法是为实现某个任务而构造的简单指令 集。这是一个非严格的算法定义。?1900年，Hilbert在巴黎举行的世界数学家大会上提出 了23个数学问题，其中第10个问题是要设计一个算法来 测试多项式是否有整数根，他没有用算法这个术语，而 用这样一句短语：“通过有限多次运算就可以决定的过 程”。?该问题是算法上不可解的，1970年由Yuri Matijasevic解决。?关键在于算法的精确定义，后来由Church和Turing分别解决， 从此称为丘奇-图灵论题。?Church使用演算定义算法和Turing使用图灵机定义算法。?现在严格地讲，一个问题算法可解的等于该问题在图灵 机上可解(可判断)。2010-11-1算法设计与分析7计算模型的作用?对于一个计算任务，有两个问题要解决:?该计算任务能否在一个计算机上实现？?该计算任务在一个计算机上实现的复杂度？?计算模型可以帮助我们解决上述问题，本课程 我们主要学习图灵机模型。?计算模型的主要作用：?可计算性：将问题按计算模型的可计算性进行分类。 也就是回答一个问题在某种计算模型上是否可计算， 而不计较其计算时间的长短。?计算复杂性：将问题按计算模型的计算复杂性(时间 和空间)进行分类。?可编程性：在计算模型下算法的实现。2010-11-1算法设计与分析8图灵机与语言识别问题（1）?语言识别问题和包含关系：Type 0 短语结构文法Type 1 上下文相关文法 Type 2 上下文无关文法Type 3 正则文法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 machine?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 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 one 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 图灵机模型?确定型图灵机?确定型图灵机计算示例?非确定型图灵机2010-11-1算法设计与分析14确定型图灵机DTM（1）?图灵机模型(Turing 1936)：最通用的计算模型?能做现代计算机所能做的一切；?但实现的效率和方式有所不同。?思想源于：模仿人在一个无限长的带格子的纸带 上写字?人使用一个带橡皮头的铅笔来写字；?写字从某个格子开始，或者仅仅读取该格子中的符号 ，或者擦取该格子中的符号并写上一个新的符号；?写字以这种连续方式进行：沿着纸带的两个方向，向 相邻的格子进行写字和读字。2010-11-1算法设计与分析15确定型图灵机DTM（2）?两端无限长的带子，带子可读可写，带子作为输入设 备、存储设备和输出设备；?有限状态控制器只含有限个状态，其中有开始状态、 接受状态和拒绝状态；?读写头可左移右移，取决于当前状态和当前格子中的 符号；?一个单步移动的构成：当前格子中读或写，改变状态 ，根据状态确定左移/右移/停机；有限状态控制器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 blank 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)-(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+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问题与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问题：?在非确定型图灵机上多项式时间可解的问题；?在确定型图灵机上多项式时间可验证的问题；