培训课件非计算04稿

1、第一章 计算与计算机科学引论1，什么是计算、什么是计算科学？一、概念： Mathematical Theory of ComputationZ.Manna： “什么是计算？我相信，世界上没有两个计算机科学家会就这一概念给出相同的定义。”一个也许是最容易理解的定义： 计算科学是使用数学语言对信息进行描述与处理的系统理论应用的科学。计算不等于数学，但数学确源于计算。计算科学不等于信息科学，但信息科学必须基于计算科学。二、内容 1，基础构造性数学（数理逻辑、代数系统、图论、集合论）历史：数学的三次飞跃。解析几何：由于笛卡尔坐标系的发明, 把数与形联系在一起；微积分：将数学引人无穷小分域；群论：代数系

2、统的整体结构研究。数学基础问题： 集合论悖论（B.Russell） 定义集合 S=x | x S） 数学公理体系的相容性。*特别关于“无矛盾与完备证明”以及“无穷总体的存在与真实性”的讨论导致三个数学派别的明确形成。数学的逻辑主义学派 B.Russell 核 A.N.Whitehead 为代表，认为数学从逻辑推导而来，是逻辑的扩展。数学与逻辑是一个主题，逻辑先于数学。也就是说，数学可以不通过外加入新的概念而纯逻辑得到。罗素的数学原理。D.Hilbert，认为数学是形式系统。每一个数学分支有自己的概念、公理和推导定理的法则以及自己的定理。把数学演绎系统通过形式的逻辑推理方式建立数学分支，而产生的

3、数学分支将不存在悖论。数学的形式主义学派数学的直觉主义学派 十九世纪末，由对数系与几何的严密化，代表人物 L.E.J.Brouwer。强调数学先于逻辑，而逻辑是从数学思维中总结出来的规律。主张数学中所有概念和证明都必须是构造性的，排中律只有在有限论域中是正确的，对无穷论域就不一定正确。一个数学名题除了正、反两面之外，还有一种可能不可解。对数学 证明中普遍使用的反证法，直觉主义学派只限于证明否定命题。三种数学学派都在现代数学中存在且各有利弊。 从直觉主义学派的观点产生的构造性数学是计算科学的基础。计算必须建立在可构造的逻辑推理基础上。2，计算的数学理论计算理论、高等逻辑、形式语言与自动机、形式语

4、义学、Petri网论、通信顺序进程（CSP）、通信系统演算、演算、进程代数（PA）、分布式事件代数（DEA）等。计算理论可计算性理论：抽象的计算模型及其性质，可计算 函数以及之间关系；算法理论：抽象模型上的算法设计与算法复杂度；计算复杂性：算法复杂性，可计算函数的复杂性。高等逻辑模型论：形式语言及其解释之间的关系；非经典逻辑：时序逻辑、模态逻辑、概率逻辑、非单调逻辑、归纳逻辑、模糊逻辑。形式语言与自动机理论 形式语言理论是用数学方法研究语言的语法（词法与文法），研究语言的构造性结构的学问； 自动机理论，主要研究各种能自动处理符号的数学机器； 当将自动机看成是一种符号接受器或识别器的时候，文法与

5、自动机可以证明是等价的。形式语言学 用数学方法研究语言的语义或语言的含义。特别是研究程序设计语言的语义。例：操作语义、指称语义、公理语义和代数语义。 3, 计算机组成原理、器件与体系结构 根据计算模型研究计算机的工作原理，并按照器件、设备、工艺条件设计，制造具体的计算机。 由于硬件的极限，当前重在分布式网络计算机系统和并行计算机系统。同时产生了对解问题的分布式算法与并行算法。可变结构与开放式系统是有希望的方向。 算法基础、程序设计、数据结构、数据库基础、微机原理与接口技术。算法基础是研究数值算法与非数值算法的基本设计方法与分析。数据结构主要研究数据表示与存储的方法、抽象的逻辑结构以其上定义的各

6、种基本操作。 4, 计算机应用基础 微机接口技术研究计算机之间及与外部设备仪器之间的数据连接问题。 5， 计算机应用技术 数值计算、信号处理技术、图形学与图象处理技术、网络技术、多媒体技术、计算可视化与虚拟现实技术、人工智能技术、辅助设计、测试、制造、教学等辅助技术等。6， 软件基础 高级语言、数据结构、程序设计、编译原理、数据库原理、操作系统原理、软件工程。2， 计算机原理一、历史1623年: Wilhelm Schikard 在给开普勒的信中提出了加 法器、乘法器和记录中间结果机构等三步分组成 的机械式计算机的设想。1642年：法国人B.Pascal基于齿轮技术制造了一台能够进 行加法和乘

7、法运算的计算器,以后成为手摇计算 机的原理. Pascal 语言是为纪念他而起名的.1672年：G.W.Leibniz提出了不用连续相加而进行机械乘 法的思想,并制成样机,成为手摇计算机例子.同 时提出二进制计算在机械计算中作用. 一百年后,C.Thomas 研制成机械计算器并批量生产.18世纪：英国数学家C.Babbage提出了用程序控制计算的思想,并且用齿轮式寄存器、运算装置和专门控制操作顺序的结构组成的通用数字计算机的设计方案，1972年在美国明尼苏达大学建立了巴贝治信息处理研究所。 19世纪：英国G.Bool系统研究了逻辑思维的一般规律,将形式逻辑归结为一种代数运算Boll代数，成为现

8、代计算机的理论基础。 20世纪初：希尔伯特提出“希尔伯特计划”，认为数学可以从少数几条公理出发推理产生所有数学定理及其证明。但是哥德尔定理使这一计划破灭；具有一定复杂程度的完备的数学系统是不存在的。 同时，丘奇、波斯特、图灵从不同角度考察什么样的数学问题是机械可解的？ 1936年，丘奇发表了关于递归函数的论文，给出可计算函数的概念，从可计算函数的结构与构造出发讨论计算的概念；而图灵从理想化的数学机器的改造来研究计算，以过程形式比较准确地刻画了计算的概念。2，存储程序式计算机的基本结构与工作原理 图灵机提供了存储数据与程序的功能，从而在冯.诺依夏的设计下，完成现代计算机的工作原理。 控制器控制器

9、 存储器 输入输出控制部件 反馈信息 输入输出设备 反馈信息(1)输入设备 计算机与外部交互部件，用于输入，基本数据以二进制，优点在于只需要两件稳定状态以供计算，比多种稳定状态的多进制易于实现；缺点是字长变得很长。（2）存储器 数据与信息的存储部件，每个存储单元编有地址。内存储器直接读取数据，存取速度快，但停电后信息消失。 外存储器不能直接读取，速度慢，但可以永久保留信息。（3）运算器 运算器是计算机对数据或信息进行技术运算或逻辑运算的主要部件，由很多逻辑电路组成，包括寄存器，加法器，移位器和一些控制电路。（4）输出设备 计算机与外部交互部件，用于数据输出，形成数字、字符、图形、图象声音等等。

10、 （5） 控制器 计算机的中枢，控制整个计算机各部分由序工作，由时序电路和逻辑电路组成，通过输出电压与脉冲信号来实现对计算机的控制。 运算器与控制器整合成一个中央处理器或CPU；输入输出与外存储器为外部设备，内存储器为内存部件。3，Boolean代数 1854年George Boole在The Laws of Thought一书中第一次给出了逻辑的推理规则。1938年Claude Shannon 揭示出如何用逻辑的基本规则设计电路数字逻辑电路，从而形成今天的Boole代数。 一个布尔函数对每个输入集合均给出确定的输出值，而电路的操作结果由布尔函数定义。而布尔函数只是给出输入输出值，必须有确定的

11、算法用布尔代数的基本运算改造出布尔表达式来表示布尔函数。一、布尔函数1，布尔运动： 在集合0，1上定义三种布尔运算，一元运算布尔补一；两个二元运算，布尔和V，+，OR ； 1+1=1 ， 1+0=1 ， 0+1=1 ， 0+0=0布尔积 ， AND。 11=1 ， 1 0=1 ， 0 1=1 ， 0 0=0若补对应逻辑算子 ，而0F（假），1T（真），则布尔运算对应到逻辑推理。2，布尔表达式与布尔函数B0，1，称从B中取值的变元为布尔变元。n度布尔函数（Boolean function of degree n）：BnB。其中Bn=（x，x2，xn）|xiB， 1in。布尔表达式（递归定义）：1

12、） 0，1，x1，xn 是布尔表达式；2） 若E1，E2是布尔表达式则 3，布尔代数中恒等式4，布尔代数：定义：集合B上有两个二元运算，及元素0，1，以及一个一元运算，且对 x，y，z B：5，布尔函数表示： 显然小项值为 1 每个变元值为1。问题：给定一个布尔函数（函数值表），怎样找到表示这个布尔函数的布尔表达式？有没有最小的算子集合可表示所有布尔函数？xyzFG1111000011001100101010100010000001000100 xyzx+y111100001100110010101010111111000101010101010100从而用布尔和的布尔积表示一个布尔函数称函数

13、的合取范式或和之积展开式。二、逻辑门电路 根据布尔代数的规则可以设计成电路，所有复杂的运算由简单的逻辑电路组合实现。三种基本元件（电路）： 反相器 或门 与门 x 0 0 x+y 0 x+yxyxy例加法器： 不考虑以前的进位，输入x，y为 0，1，输出 s （和位），c（进位），则称半加器；则输入、输出表与电路如下：输入输出xysc1100101001101001输入x，y及进位ci，输出 s， ci+1如表输入输出xycisci+11111000011001100101010101001011011101000第二章 计算模型与形式语言计算模型：形式语言文法、有限状态机、图灵机。由于计算是

14、可以用语言来描述的，因此语言的文法象一台计算机一样给出结论。1， 形式语言 在语言的翻译过程中产生了语言的抽象形式：形式语言。短语结构文法 定义1，字母表（也称字汇表）V是一个有限非空集，其元素为符号。V上的一个词或句子是指V中元素组成的有限长度的字符串。空串是没有字符的串（不是空集），记为。V上所有词的集合记为V*，V上的语言是V*的一个子集。 定义2， 一个短语结构文法G=（V，T，S，P）由四部分组成：字母表（或词汇表）V，由V的所有终结符组成的V的子集T，V的初始符S，和产生式集合P。集合V-T=N称为非终结字符集，P中的每个产生式的左边必须至少包含一个非终结符。 语言有子字表V及词汇

15、表及所有短语语句的集合。例如汉字“句”“子”，及英语字母表。如果终结符是所有英文字母，而所有汉字为非终结符，则由产生式最后得到的是英文。例如生成式产生。句子名词动词，则这些汉字还可以通过生成式代换成英文。 例1，设G=（V，T，S，P），其中V=a，b，A，B，S，T=a，b，S是初始符，Ps=Aba，ABB，Bab，Abb，构成短语文法结构。 定义3，设G=（V，T，S，P），是一个短语结构文法，w0=lz0r， w=lz1r是V中串。若z0z1是G的一个产生式，则称w0w1称直接派生。如果V上串w0， w1 ， wn（n0）满足： w0w1 ， w1w2 ， wn-1wn ，则称由w0可派

16、生，记为w0*wn。由w0到wn 的序列称为派生。 例2，在例1的文法中，ABB，Bab，可以派生：ABa Aaba BBaba Bababa abababa 定义4，设G=（V，T，S，P），是一个短语结构文法由G生成的语言是初始符S能够派生的所有终结符串构成的集合，记为L（G）： L（G）=wT*|S*w 习题1：设G是一个文法，其字母表V=S，A，a，b，终结符集T=a，b，初始符为S，产生式为P=SaA，Sb，Aaa，求这文法生成的语言 L（G）。 习题2：设G是一个文法，字母表V=S，0，1，终结符 T=0，1，初始符为S，产生式为P=S11S，S0，求这文法的语言 L（G）。 例3

17、：给出生成集合0n1n| n=0，1，2， 的一个短语结构文法，G=（V，T，S，P），V=0，1，S终结符集T=0，1，初始符为S，产生式为S0S1，S 。 例4：给出生成集合0m1n| m和n均为非负整数 的一个短语结构文法解：可以构造两个文法G1，G2来生成这个集合。 G1：V=S，0，1，终结符集T=0，1 产生式 S0S，SS1，S 。 G2：V=S，A，0，1，终结符集T=0，1 产生式 S0S，S1A，S1，A1A，A1和S 。 例5：生成集合0n1n2n | n=0，1，2， 。一个文法G=（V，T，S，P），其中V=0，1，2，S，A，B ，终结符T=0，1，2，初始符为S，

18、产生式为 S0SAB，S ，BAAB，OA01，1A11，1B12，2B22 二、短语结构文法类型 诺姆：齐姆斯基（Avram Noam Chomsky）的文法分类，不同文法也就定义了不同的语言，对应于不同计算模型能识别的语言。0型文法：没有限制产生式。1型文法只有两种产生式：a，w1w2，L（w2L（w1）； b，w1 。 1型文法是一种O型文法，对文法lw1rlw2r也称1型文法，此时必须有相同的包 lr 。也称上下相关文法。2型文法只有产生式：w1w2 且：w1=A 且：w2 =aB或 w 2=a0 其中A，B是非终结字符而a是终结符。或者， w1 =S，w2 = 0 3型文法全是2型文

19、法。例6，G 2文法是正则文法。例7，由S0S1, S从而是上下文无关文法, 但不是3型。例8，是上下文相关文法但不是2型文法。 2,有限状态机包括一个有限的状态集合(含初试态)，一个输入字母表和一个转移函数（对每个状态和输入指定下一个状态）。自动售货机、整数加法器及许多计算机部件的数学模型。 一、带输出有限状态机状态下 一 个 状 态输 出输 入5 10 25 O R输 入5 10 25 O Rs0s1s2s3s4s5s6s1 s2 s5 s0 s0 s2 s3 s6 s1 s1 s3 s4 s6 s2 s2 s4 s5 s6 s3 s3 s5 s6 s6 s4 s4s6 s6 s6 s5

20、s5s6 s6 s6 s0 s0n n n n nn n n n nn n 5 n nn n 10 n nn n 15 n nn 5 20 n n 10 25 OJ AJ 定义1：有限状态机M=（S，I，O，f，g， s0 ）由如下部分组成：有限状态集S，有限输入字母表I，有限输出字母表O，转移函数。：每个状态及输入对指定一个新状态，输出函数g：每个状态和输入对指定一个输出，一个初始状态。例1，一个有限状态机，其中S=S0 ， S1， S2， S3，I=a，1且O=0，1。f 与g的值由表给出。也可以用状态图表示：状态fg输入1输出1s0s1s2s3s1s3s1s2s0s0s2s1110001

21、10例2，试构造一个有限状态机，使其利用整数二进制展开式将两个整数相加。 解：初始位令是0（xn，yn）=（0，0）。S0前进位0，S1前进位1；两位输入（第一个数，第二个数），只有四种：00，01，10，11。转移与输出根据下面两因素构造的输入所表示的两个二进制数之和；另一个是状态S0，S1表示的进位情况。 此机器的状态图：二、不带输出的有限状态机 有限状态机最重要的应用是语言识别，这在设计编译器时有实际用途。带输出的有限状态机可以识别语言，但可以专门设计不带输出的有限状态机以供识别语言。 定义1，设V是一个字母表（或词汇表），A，B是V*的子系。A和B的连接是所有形如xy的串构成的集合，记

22、AB，其中xA，yB。 例1， A=0，11，B=1，10，110， 则 AB=01，010，0110，111，1110，11110， BA=10，111，100，1011，1100，11011 注意 ABBA！ 定义2，设A是V*的子集。A的克莱因闭包是A中任意多个串的连接组成的集合，记为A*： 定义3，有限状态自动机M=（S，I，f，s0，F）：有限状态集合S，有限输入字母表I，转移函数 f ，初始状态S0，由终结状态构成的S的子集F。 有限自动机也可以用状态图表示，终结符用双圈表示。 例2，构造有限自动机M=（S，I，f，s0，F）的状态图，其中 S=（ s0 ， s1， s2， s3）

23、，I=0，1，F=（ s0 ， s1）状态f输入 01s0s1s2s3s0 s0 s0 s2s1 s2 s0 s1 看这自动机可识别的语言终结符只有 s0 ， s3，可将s0 变为s0的只有串，0，00，0n ；将 s0 s3 ： 0n 10后跟任意x，从而语言： L= 0n ，0n 10 x | n=0，1，x 是任意串了。 如果状态的转移是不确定的，也就是不是唯一的转移，称非确定型的有限状态自动机。 定义4，非确定型有限状态自动机M=（S，I，f，S0，F）由以下五部分组成：一个状态的集合S，一个输入字母表I，一个转移函数f（f 为每个状态和输入对指派一个状态集合），一个初始状态S0和一个

24、由终结状态构成的S的子集F。 例4，一个非确立性有限状态自动机的状态表与状态图：状态f 01输入s0s1s2s3 s4s01 s2 s3 s3 s3s1 s4s4 s3 非确定性自动机所确定的语言，就是这个机所识别的所有串的集合。 上述自动机所能识别的集合： 1），S0是终结字符，可见所有On可识别； 2）S4是终结字符，从S0到S4的所有可能串：0n01，0n11 从而可识别的语言L=0n，0n01，0n11 | n0 定理1，如果语言L可以由非确定型的有限自动机M0识别，也可以由一个确定型有限自动机M1识别。三、 语言的识别 以下严格叙述：定义1，集合I上的正则表达式的递归定义如下： 符号

25、是一个正则表达式； 符号是一个正则表达式； 若xI，符号x是一个正则表达式； 当A，B是正则表达式时，符号（AB），（AB）和A*都是正则表达式。这里A*式A代表的集合的克莱因闭包。 克莱因在1956年首先证明了：一个集合能够被一个有限状态自动机识别当且仅当这个集合是这样得到的：以任意顺序通过对空集、空串和单字符串的连接，并或克莱因闭包构造出来。以这种方法构造出来的集合称为正则集合。 例 以下正则表达式表示的集合 10*：1 后任意多个 0 （10*）：10的任意多次复制（包括空串） 0 01：串 0 或 01 0（0 1）*：以 0 开头的任意 0 和 1 生成的串。 （0*1）*：不以 0

26、 结尾的任意串。 克莱因定理：一个集合是正则的，当且仅当它可由一个有限状态自动机识别。 定理：一个集合可以由正则文法生成，当且仅当它是一个正则集合。 每个正则表达式表示一个由下列规则指出的集合： 表示空集； 表示集合 ； x表示由单个符号x赞成的串； （AB）表示A和B表示的集合的连接； （AB）表示A和B代表的集合的并。正则表达式表示的集合称为正则集合。 3图灵机 带有存贮功能的计算模型，更强大的计算功能。一、图灵机： 定义1，图灵机T=（S，I，f，S0）：有限状态集S，含有空白符B的字母表I，从SIR，L的部分函数 f 及初始状态S0。所谓部分函数 f 是对定义域内有些有定义，有些无定义

27、。 当控制头读当前符号x，处于状态S，且部分函数 f在（x，S）处由f（S，x）=（S，x，d）定义，则控制头 1，进入状态 S； 2，当前格中檫取x1写上x； 3，若d=R 则图灵机的运行方法是给出一个正元组 （S，x，S，x，d）的有序集合。B 1 1 0 1 B 0 1 BS0S1S2S1 S3 二、识别集合（语言） 定义2，设V是字母表I的子集。T=S，I，f，S0识别V*中带x当且仅当：若将x 写在带上，T从初始位置开始运行，则T能在一个终结状态停机。称T能识别V*的子集A，若x能被T识别当且仅当xA。 注意：1，识别xV* ，可以使用不在V中但在I中符号； 2，所谓不能识别xV*，

28、指x放在带子上，运行不停机或停机而不在终结状态终结状态是指在五元组中不是第一个的状态。 例：求一个图灵机，使之能识别第二位是1的二进制串构成的集合，即正则集合（01）|（01）* 解：从左边非空白格开始运行，向右移动并判断第二符号是否是1。若是则进入终结状态；若不是1则或不停止或停机于非终结状态。该第一符用两个五元组（S0，O，S1，0，R）或（S0，I，S1，1，R），后进入S1 。下一步是两个五元组（S1，O，S2，0，R）或（S1，I，S3，1，R）。由于当第二符号是0时S2不应是终结状态，从而进一步进入五元组：（S2，0，S2，R），而S3定义为终结状态。此外，空串及只有1位的串不当识

29、别，从而加入五元组（S0，B，S2，0，R）和（S1，B，S2，0，R） 以上7个五元组产生了图灵机识别完成任务。习题：求识别集合0n1n|n1的图灵机。 用辅助符号M作为标记可识别这种非正则集合的语言。令V=0，1，I=0，1，M，B。只识别V*中串，终结态为S6。用M替核串中最左边的0与最右边1，左右移动，能在一个终止状态终止当且仅当：这串的构成是一列0后跟一列相同个数1。五元组：（S0，O，S1，M，R），（S1，0，S1，0，R），（S1，1，S1，1，R），（S1，M1，S2，M，L），（S1，B，S2，B，L），（S2，1，S3，M，L），（S3，1，S3，1，L），（S3，O，S

30、4，0，L），（S3，M，S5，M，R），（S4，O，S4，0，L），（S4，M，S0，M，R），（S5，M，S6，M，R）。请说明每个五元组的功能且如何能识别该集合？三、计算函数： 例：构造一个图灵机将两个非负整数相加。解：f（n1,n2）= n1+ n2 ， n1表示成 n1+1个1，n2表示成 n2 +1个1，元素对（ n1,n2 ）表示成n1+1个1后跟*再n2+1个1作为输入，而输出当是n1+n2+1个1。以下五元组可实现（S0，1，S1，B，R）,（S1，*，S3，B，R),（S1，1，S2，B，R）,（S2，1，S2，1，R）,（S2，*，S3，1，R）。事实上一般的计算是用多带

31、图灵机实现的,但是多带与单带图灵机可计算的函数是相同的:由图灵机可计算的函数称为可计算函数.图灵机有许多种变形,但是它们的计算能力是一样的. 丘奇图灵机论题：对于任何有效算法的问题，都存在解该问题的图灵机。这不是定理，因为“可有效解决的问题”无法严格形式化定义，而图灵机是可以形式化定义的。第三章 计算复杂度理论计算机计算理论要解决以下三个问题： 可计算性问题； 计算复杂性问题 计算实现。一、问题 1， 计算复杂性基本概念 问题由两部分组成： 条件及其中参数的一般性描述；对需求回答的问题的特征说明。 问题的例子：是对问题中参数给定具体值描述。 例，旅行商问题是指一个城市的有限系 C=C1， C2

32、， Cm和每两个城市间距离d（ Ci， Cj）。解是对城市的一个排序： 这里(C(1), C(2), C(m)是1,2,m的某个排序,使该排序为以下函数取最小值:而例子:C=(C1,C2 ,C3,C4), d(C1, C2)=10, d(C1，C3)=5, d(C1,C4)=9, d(C2，C3)=6, d(C2，C4)=9, d(C3，C4)3二、算法 算法（algori thm）是指可用来求解某一问题的，适用于所有例子的，带有一般性的过程。 算法定义：一个算法是一个有穷规则的集合，这些规则确定一个解决某一特定类型问题的运算序列。这些规则或运算序列满足： 1， 有穷性：算法必须总是在执行有穷

33、步之后结束。 2， 确定性：算法的每一个步骤必须是确切地定义的。 3， 输入：算法有零个或多个输入。 4， 输出：算法有一个或多个输出 5， 能行性：算法中的运算操作必须是基本的或可精 确实现的。 程序是一种事先编制好了具有特殊功能的指令序列。 程序=数据结构+算法。 算法的有效性决定于所需资源：运行时间与内存空间。 其中运行时间一般用基本操作的次数表示。 问题大小是指一个问题的确定的例子的大小的描述它所须的信息量。 当表示适当时，例子大小的值当与问题求解难度成正比。 这里适当是指一个好的编码策略：可解码性与简洁性。 例：字母表 C，1，0，1，2，9 中表示一个具体的旅行商问题：“C1C2C

34、3 C4/10/5/9/6/9/3”输入长度为32，这个例子大小为32。三、多项式时间算法与指数时间算法 时间复杂性：对某一问题和任一可能的输入长度n，称所给算法求解该问题的所有大小为n 的例子所需时间的最大值为该算法对输入长度n 的时间复杂度。 多项式时间算法：对以输入长度 n 为变量的多项式函数 P（n），使其时间复杂性函数为 0（pcn）的算法。 指数时间算法：是指任何其时间复杂性函数不不能用多项式函数界定的算法。2， 问题复杂性分类判定问题：任何一个问题可以化成两类统一的问题：可行性检验问题和判定问题。 一个判定问题可以由所有例子的集合 D与符合问题条件的子集Y D组成。 例：旅行商问

35、题中 C=C1，CI，Cm ,Ci，CjC 之间距离d（Ci，Cj）Z+ 及界 BZ+。问题：C 中存在一个总长不超过 B 的，通过所有城市的旅行路线吗？即，是否存在 C 的序 使得 一个判定问题可以由所有例子的集合 D与符合问题条件的子集Y D组成。三、P 类问题 以确定性单带 Turing 机 DTM 为计算模型，则一个DTM 程序M ： a）带中所用字符的一个有限集合，它应包括输入字符表子集和一个特别的空白符号 b-。 b）一个有限状态集Q，包括初始状态 q0 和两个特有的停机状态qY，qN。 C）一个转移函数:(Q-Qy,qN)QL, 当一个带有输入字符表的DTM程序M接受x*M 作用

36、于输入 x 时停机于状态 qY. 则 M 所识别的语言: LM=x|x*: M 接受 x 当一个M对定义于其输入字符表上的所有可能字符串均停机时,我们才称其为一个算法.相应地: 称一个DTM程序M在编码策略e之下求解判定问题,若M对定义于其输入字符表上所有输入字符串均停机且LM=L,e. 时间复杂度函数：对于一个对所有输入x*均停机的DTM程序M，定义其时间复杂性函数TM：Z+Z+ 为： TM（n）=maxm：存在一个x*，|x|=n，使得M对输入x 的计算需要时间m 若存在一个多项式P，使对所有 nZ+ 有 TM(n)P(n)，则称次序M为一个多项式时间DTM 程序. P类的第一类重要语言正

37、式定义: P=L：存在一个多项式时间 DTM 程序 M，使L=LM。此时不再强调编码策略，因为它们之间可以是等价的。 若存在一个多项式P，使对所有 nZ+ 有 TM(n)P(n)，则称次序M为一个多项式时间DTM 程序. 多项式时间可解的P类问题是在已知可解的条件下，通过 Turing 机可以达到停止状态qY。但是一般的问题并不知道是否可解，而且并无解法策略，而上述问题几乎类似于多项式时间可验证问题而非可解。因为为了找出解的某个猜测花去的时间也许不是多项式级的。四、NP 类问题 设计另一假想机：非确定性单带 Turing 机 NDTM，即在Turing 机模式上加一个猜想模块，猜想头将可以从-

38、1开始改写格中数据，而且可以无穷地猜想，于是计算变成两部分：猜想阶段与检验阶段： -5 4 3 2 1 0 1 2 3 4 5 猜想模块有限状态控制器猜想头读写头 一般来说，对于一个输入x，NDTM 的程序 M可能做无穷多个可能的计算，如果有一个可能计算（由猜想决定）停机于qr，则x称 M可接受的。 如果这样定义的 NDTM 程序 M 可接受计算的语言，则从 q0 到 qr所用时间为多项式所界，则定义了NP类语言： NP=L：存在一个多项式时间 NDTM 程序 M，使LM=L。显然我们也可以不计编码策略。 显然 PNP 定理：若问题NP，则存在多项式P 使可以用一个时间复杂性为O(2P(n)

39、的确定性算法求解. 对于一个长度为 n 的输入,通过 A 的确定性计算的检验其Kq(n)个可解猜测子符串中每一个,直到停止或运行完 q(n) 步,可以肯定判断该输入是否是一个可接受输入,从而对于判“是”与“非”来说,这里的一个确定性算法. 从而每个长度为 n 的可被 A接受的输入，必存在字符集上长度最当为 q（n）的某个猜想字符串，使算法 A的检验阶段在不多于q(n)步内回答“是”.从而若 |=K, 则所需考虑的可能猜测的数目最多Kq(n).这里长度小于 q(n)的猜想字符串可以用 b 填充为 q(n)长. 证明:设 A 为求解的一个多项式不确定算法,多项式 q(n)界定其复杂度.而 q 可在

40、多项式时间内被计算其值 q(n),即可计算出 C1,C2 使 q(n)=C1nC2。 试图找 NP 中一类与 P 问题有显著不同的一类问题，从而去证明 PNP ，这就是导致了 NP 完全性问题 （NPC）的出现。 上述定理说明，在非确定性 Turing 机上时间复杂度为q(n)Kq(n)的问题相当。直观上认为一定有问题是前者可解而后者不可解之问题，或人们一般认为 P 是 NP 的真子集。 已知 PNP，但P 是 NP的真子集吗？或者有 P=NP？这就是著名的数学难题 “P=NP？” 从而该算法的时间复杂度为q(n)K Kq(n)上界.有q(n)可被2Q所界而K 可写成2的幂,从而存在一个多项式

41、P使上界写成OC2P(w). 从语言L1 1*到另一语言 L2 2*的多项式变换是指满足下面两个条件的函数 f：1* 2* ： 1， 存在计算f 的一个多项式时间 DTM 程序。 2，对所有 x2* ，xL1f（x） L2。一、多项式变换 3， NP 完全问题“NP完全的”定义: 一个语言 L (判定问题) 为NP 完全的(NPC),如果 LNP(NP),且对所有别的语言LP(判定问题NP），均有LL（ ） 从问题角度看，从判定问题 2 的多项式变换是函数 f：D1 D2 满足： 1， f 可由多项式时间算法去计算。 2， 对所有的 I D1 ，IY1 f(I)Y2 记为 L1L2 或 12

42、因此为证明一个问题是NP完全的，必须证明NP中每个问题均可多项式地变换到它。 可满足性问题：给定布尔变量的一个集合 U=u1，u2，um，U 的一个真值分配是映射 t：U T，F，且若 t（ ui）=T，则称 ui 取真值，否则 t（ui）=F 称取假。定义在 U 上的一个子句ui是由一些布尔变量（或它的补）通过逻辑“或”而连接起来的布尔表示式。若存在对布尔变量 U 的一组真赋值，使该子句 ui 取值为真，即 ui 中至少有一个单元取真值，则称 ui 被满足。而子句的集合 C 是由所有包含的子句通过逻辑“与”连接组成。称该集合是可满足的，若存在布尔变量集之一组赋值，使 C 中的每一个子句均取真值。 但是，NP 问题完全存在吗？1971年 Cook 证明了第一个 NP 完全问题，可满足性问题，称为 Cook 定理。 Cook 定理：可满足性问题是 NP 完全的。 从 Cook 开创性工作至今，已经发现，证明了数千个 NP 完全问题，并总结出一些证明方法。 二、NP 困难问题 多项式时间图灵归约（Polynomial time Turing reduction）设1和2