计算机组成原理第1章剖析优秀PPT.ppt

计算机算法设计与分析（第计算机算法设计与分析（第4版）版）王晓东王晓东 编著编著 电子工业出版社电子工业出版社周德华周德华 tzhoudhjnu.edu tzhoudhjnu.edu 教学支配教学支配1.1.1.1.课时支配课时支配课时支配课时支配讲授课（含探讨课讲授课（含探讨课讲授课（含探讨课讲授课（含探讨课 第第第第5 5 5 5周后）周后）周后）周后）316=48 316=48 316=48 316=48 学时学时学时学时 1-16 1-16 1-16 1-16周周周周试验课（周三）试验课（周三）试验课（周三）试验课（周三）29=18 29=18 29=18 29=18 学时学时学时学时 1-16 1-16 1-16 1-16周周周周总复习及答疑总复习及答疑总复习及答疑总复习及答疑 17-18 17-18 17-18 17-18周周周周2.2.成果总评成果总评n n 期末考试期末考试期末考试期末考试 60 60 60 60n n 平常成果平常成果平常成果平常成果 40 40 40 40点名及课堂表现点名及课堂表现点名及课堂表现点名及课堂表现(10%)(10%)(10%)(10%)平常作业及探讨平常作业及探讨平常作业及探讨平常作业及探讨(15%)(15%)(15%)(15%)试验及报告（试验及报告（试验及报告（试验及报告（15%15%15%15%）3.3.前导课程前导课程n n C/C+C/C+C/C+C/C+程序设计程序设计程序设计程序设计n n 数据结构数据结构数据结构数据结构教学支配教学支配3.3.3.3.习题探讨课习题探讨课习题探讨课习题探讨课 本学期内任选一道习题或试验题讲解自己的本学期内任选一道习题或试验题讲解自己的本学期内任选一道习题或试验题讲解自己的本学期内任选一道习题或试验题讲解自己的算法，要求：算法，要求：算法，要求：算法，要求：主动报讲解题号（至少提前一周）主动报讲解题号（至少提前一周）主动报讲解题号（至少提前一周）主动报讲解题号（至少提前一周）讲主要思路和创新点讲主要思路和创新点讲主要思路和创新点讲主要思路和创新点 有有有有pptpptpptppt 5 5 5 5分钟以内分钟以内分钟以内分钟以内 多人讲同一道题留意突出与别人的差别多人讲同一道题留意突出与别人的差别多人讲同一道题留意突出与别人的差别多人讲同一道题留意突出与别人的差别 讲完后相关文档、程序或讲完后相关文档、程序或讲完后相关文档、程序或讲完后相关文档、程序或demodemodemodemo提交服务器提交服务器提交服务器提交服务器算法在计算机科学中的地位算法在计算机科学中的地位Computer science is the Computer science is the study of algorithmsstudy of algorithms,including:including:1.Their formal and mathematical properties1.Their formal and mathematical properties2.Their hardware realizations2.Their hardware realizations3.Their linguistic realizations3.Their linguistic realizations4.Their applications4.Their applicationsGibbs,N.E.,and Tucker,A.B.“A Model Curriculum for a Liberal Arts Degree in Computer Science,”Comm.of the ACM,vol.29,no.3(March 1986).课程目标和内容课程目标和内容设设设设计计计计算算算算法法法法表表表表示示示示算算算算法法法法分分分分析析析析算算算算法法法法实实实实现现现现算算算算法法法法测测测测试试试试算算算算法法法法确确确确认认认认算算算算法法法法驾驭算法困难性和常用算法的基本理论学问驾驭算法困难性和常用算法的基本理论学问驾驭算法困难性和常用算法的基本理论学问驾驭算法困难性和常用算法的基本理论学问驾驭算法分析和设计的基本方法驾驭算法分析和设计的基本方法驾驭算法分析和设计的基本方法驾驭算法分析和设计的基本方法熬炼逻辑思维实力，培育运用算法理论解决实际熬炼逻辑思维实力，培育运用算法理论解决实际熬炼逻辑思维实力，培育运用算法理论解决实际熬炼逻辑思维实力，培育运用算法理论解决实际问题的实力问题的实力问题的实力问题的实力课程目标和内容课程目标和内容1.算法概述算法概述2.递归与分治策略递归与分治策略3.动态规划动态规划4.贪心算法贪心算法5.回溯法回溯法6.分支限界法分支限界法7.随机化算法随机化算法8.近似算法近似算法课程参考书目课程参考书目算法设计与分析（第算法设计与分析（第算法设计与分析（第算法设计与分析（第2 2版）版）版）版）王晓东王晓东王晓东王晓东 编著编著编著编著清华高校出版社（清华高校出版社（清华高校出版社（清华高校出版社（JavaJava描述）描述）描述）描述）算法导论（第算法导论（第算法导论（第算法导论（第2 2版）版）版）版）Thomas H.Cormer,Charles E.LeisersonThomas H.Cormer,Charles E.Leiserson等著等著等著等著潘金贵潘金贵潘金贵潘金贵 顾铁成等译顾铁成等译顾铁成等译顾铁成等译机械工业出版社机械工业出版社机械工业出版社机械工业出版社第第1章章 算法概述算法概述学习要点学习要点:理解算法的概念。理解算法的概念。理解什么是程序，程序与算法的区分和内在联系。理解什么是程序，程序与算法的区分和内在联系。驾驭算法的计算困难性概念。驾驭算法的计算困难性概念。驾驭算法渐近困难性的数学表述。驾驭算法渐近困难性的数学表述。驾驭用驾驭用C+语言描述算法的方法。语言描述算法的方法。了解了解NP类问题的基本概念。类问题的基本概念。第第1章章 算法概述算法概述1.1 基本概念基本概念1.2 算法困难性分析算法困难性分析1.3 用用c+描述算法描述算法1.4 算法分析方法算法分析方法1.5 NP完全性理论完全性理论1.1 基本概念基本概念-算法算法(Algorithm)算法是指解决问题的一种方法或一个过程。算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：算法是若干指令的有穷序列，满足性质：(1)输入：有外部供应的量作为算法的输入。输入：有外部供应的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性：算法中每条指令的执行次数是有限的，执行有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。每条指令的时间也是有限的。1.1 基本概念基本概念-程序程序(Program)程序是算法用某种程序设计语言的具体实现。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质程序可以不满足算法的性质(4)。例如操作系统，是一个在无限循环中执行的程序，因例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。该子程序得到输出结果后便终止。Algorithm+Data Structure=Program -Nikiklaus WirthAlgorithm+Data Structure=Program -Nikiklaus Wirth1.1 基本概念基本概念-问题求解问题求解(Problem Solving)证明正确性证明正确性分析算法分析算法设计程序设计程序理解问题理解问题精确解或近似解精确解或近似解选择数据结构选择数据结构算法设计策略算法设计策略设计算法设计算法1.2 算法困难性分析算法困难性分析 算法困难性算法困难性=算法所须要的计算机资源算法所须要的计算机资源算法的时间困难性算法的时间困难性T(n)；算法的空间困难性算法的空间困难性S(n)。其中其中n是问题的规模（输入大小）。是问题的规模（输入大小）。1.2.1 算法的时间困难性算法的时间困难性（1）最坏状况下的时间困难性）最坏状况下的时间困难性 Tmax(n)=max T(I)|size(I)=n（2）最好状况下的时间困难性）最好状况下的时间困难性 Tmin(n)=min T(I)|size(I)=n（3）平均状况下的时间困难性）平均状况下的时间困难性 Tavg(n)=其中其中I是问题的规模为是问题的规模为n的实例，的实例，p(I)是实是实 例例I出现的概率。出现的概率。1.2.2.1 算法渐近困难性算法渐近困难性T(n),as n;(T(n)-t(n)/T(n)0，as n;t(n)是是T(n)的渐近性态，为算法的渐近困难性。的渐近性态，为算法的渐近困难性。在数学上，在数学上，t(n)是是T(n)的渐近表达式，是的渐近表达式，是T(n)略去低阶略去低阶项留下的主项。它比项留下的主项。它比T(n)简洁。简洁。1.2.2.2 渐近分析的记号渐近分析的记号在下面的探讨中，对全部在下面的探讨中，对全部n，f(n)0，g(n)0。（1）渐近上界记号）渐近上界记号O O(g(n)=f(n)|存在正常数存在正常数c和和n0使得对全部使得对全部n n0有：有：0 f(n)cg(n)比如：比如：3N+10=O(N),4N2+3N-1=O(N2),logN=O(N)（2）渐近下界记号）渐近下界记号 (g(n)=f(n)|存在正常数存在正常数c和和n0使得对全部使得对全部n n0有：有：0 cg(n)f(n)比如：比如：3N+10=(1),4N2+3N-1=(N2),NlogN=(logN)（3）非紧上界记号）非紧上界记号o o(g(n)=f(n)|对于任何正常数对于任何正常数c0，存在正数和，存在正数和n0 0使得对全部使得对全部n n0有：有：0 f(n)0，存在正数和，存在正数和n0 0使得对全部使得对全部n n0有：有：0 cg(n)f(n)等价于等价于 f(n)/g(n)，as n。f(n)(g(n)g(n)o(f(n)比如：比如：4N2+3N-1=(N),N!=(N2)（5）紧渐近界记号 (g(n)=f(n)|存在正常数c1,c2和n0使得对全部n n0有：c1g(n)f(n)c2g(n)比如：4N2+3N-1=(N2),logN2+2=(logN)定理1：(g(n)=O(g(n)(g(n)f(n)=(g(n)的准确意义是：f(n)(g(n)。一般状况下，等式和不等式中的渐近记号(g(n)表示(g(n)中的某个函数。例如：2n2+3n+1=2n2+(n)表示 2n2+3n+1=2n2+f(n)，其中f(n)是(n)中某个函数。等式和不等式中渐近记号O,o,和的意义是类似的。渐近分析记号在等式和不等式中的意义渐近分析记号在等式和不等式中的意义渐近分析中函数比较渐近分析中函数比较f(n)=O(g(n)a b;f(n)=(g(n)a b;f(n)=(g(n)a=b;f(n)=o(g(n)a b.1.2.2.3 渐近分析记号的若干性质渐近分析记号的若干性质（1）传递性：）传递性：f(n)=(g(n)，g(n)=(h(n)f(n)=(h(n)；f(n)=O(g(n)，g(n)=O(h(n)f(n)=O(h(n)；f(n)=(g(n)，g(n)=(h(n)f(n)=(h(n)；f(n)=o(g(n)，g(n)=o(h(n)f(n)=o(h(n)；f(n)=(g(n)，g(n)=(h(n)f(n)=(h(n)；（2）反身性：）反身性：f(n)=(f(n)；f(n)=O(f(n)；f(n)=(f(n).（3）对称性：）对称性：f(n)=(g(n)g(n)=(f(n).（4）互对称性：）互对称性：f(n)=O(g(n)g(n)=(f(n)；f(n)=o(g(n)g(n)=(f(n)；（5）算术运算：）算术运算：O(f(n)+O(g(n)=O(maxf(n),g(n)；O(f(n)+O(g(n)=O(f(n)+g(n)；O(f(n)*O(g(n)=O(f(n)*g(n)；O(cf(n)=O(f(n)；g(n)=O(f(n)O(f(n)+O(g(n)=O(f(n)。规则O(f(n)+O(g(n)=O(maxf(n),g(n)的证明：对于随意f1(n)O(f(n)，存在正常数c1和自然数n1，使得对全部n n1，有f1(n)c1f(n)。类似地，对于随意g1(n)O(g(n)，存在正常数c2和自然数n2，使得对全部n n2，有g1(n)c2g(n)。令c3=maxc1,c2，n3=maxn1,n2，h(n)=maxf(n),g(n)。则对全部的 n n3，有f1(n)+g1(n)c1f(n)+c2g(n)c3f(n)+c3g(n)=c3(f(n)+g(n)c32 maxf(n),g(n)=2c3h(n)=O(maxf(n),g(n).1.2.3 算法渐近困难性分析中常用函数算法渐近困难性分析中常用函数（1）单调函数）单调函数单调递增：m n f(m)f(n);单调递减：m n f(m)f(n);严格单调递增：m n f(m)f(n);严格单调递减：m f(n).（2）取整函数）取整函数 x ：不大于x的最大整数；x ：不小于x的最小整数。取整函数的若干性质取整函数的若干性质 x-1 x x x 0，有：，有：n/a /b =n/ab ;n/a /b =n/ab ;a/b (a+(b-1)/b;a/b (a-(b-1)/b;f(x)=x ,g(x)=x 为为单调递增函数。单调递增函数。（3）多项式函数）多项式函数 p(n)=a0+a1n+a2n2+adnd；ad0;p(n)=(nd);f(n)=O(nk)f(n)多项式有界；多项式有界；f(n)=O(1)f(n)c;k d p(n)=O(nk);k d p(n)=(nk);k d p(n)=o(nk);k 0:a0=1;a1=a;a-1=1/a;(am)n=amn;(am)n=(an)m;aman =am+n;a1 an为单调递增函数;a1 nb=o(an)ex 1+x;|x|1 1+x ex 1+x+x2;ex=1+x+(x2),as x0;（5）对数函数）对数函数 log n=log2n;lg n=log10n;ln n=logen;logkn=(log n)k;log log n=log(log n);for a0,b0,c0|x|1 for x -1,for any a 0,logbn=o(na)（6）阶乘函数）阶乘函数1.2.4 算法分析中常见的困难性函数算法分析中常见的困难性函数小规模数据小规模数据中等规模数据中等规模数据1.3 用用c+描述算法描述算法（1）选择语句：）选择语句：（1.1)if 语句：语句：（1.2)？语句：？语句：if(expression)statement;else statement;exp1?exp2:exp3 y=x9?100:200;等价于：if(x9)y=100;else y=200;switch(expression)case 1:statement sequence;break;case 2:statement sequence;break;default:statement sequence;（1.3)switch语句：语句：（2）迭代语句：）迭代语句：（2.1)for 循环：循环：for(init;condition;inc)statement;（2.2)while 循环：循环：while(condition)statement;（2.3)do-while 循环：循环：do statement;while(condition);（3）跳转语句：）跳转语句：（3.1)return语句：语句：return expression;（3.2)goto语句：语句：goto label;label:（4）函数：）函数：return-type function name(para-list)body of the function int max(int x,int y)return xy?x:y;template Type max(Type x,Type y)return xy?x:y;int i=max(1,2)；double x=max(1.0,2.0)；（5）模板）模板template：（6）动态存储安排）动态存储安排（6.1）运算符）运算符new 运算符运算符new用于动态存储安排。用于动态存储安排。new返回一个指向所安排空间的指针。返回一个指向所安排空间的指针。例：例：int x；y=new int；y=10；也可将上述各语句作适当合并如下：也可将上述各语句作适当合并如下：int y=new int；y=10；或或 int y=new int(10)；或或 int y；y=new int(10)；（6.2）一维数组）一维数组 为了在运行时创建一个大小可动态变更的一维浮点数组x，可先将x声明为一个float类型的指针。然后用new为数组动态地安排存储空间。例：float x=new floatn；创建一个大小为n的一维浮点数组。运算符new安排n个浮点数所需的空间，并返回指向第一个浮点数的指针。然后可用x0，x1，xn-1来访问每个数组元素。（6.3）运算符）运算符delete 当动态安排的存储空间已不再须要时应刚好释放所占用的空间。用运算符delete来释放由new安排的空间。例：delete y；delete x；分别释放安排给y的空间和安排给一维数组x的空间。（6.4）动态二维数组）动态二维数组 创建类型为Type的动态工作数组，这个数组有rows行和cols列。template void Make2DArray(Type*&x,int rows,int cols)x=new Type*rows;for(int i=0;irows;i+)xi=new Typecols;当不再须要一个动态安排的二维数组时，可按以下步骤释放它所占用的空间。首先释放在for循环中为每一行所安排的空间。然后释放为行指针安排的空间。释放空间后将x置为0，以防接着访问已被释放的空间。template void Delete2DArray(Type*&x,int rows)for(int i=0;irows;i+)delete xi;delete x;x=0;1.4 算法分析方法算法分析方法例：依次搜寻算法例：依次搜寻算法templateint seqSearch(Type*a,int n,Type k)for(int i=0;in;i+)if(ai=k)return i;return-1;（1）Tmax(n)=max T(I)|size(I)=n=O(n)（2）Tmin(n)=min T(I)|size(I)=n=O(1)（3）在平均状况下，假设：(a)搜寻成功的概率为p(0 p 1)；(b)在数组的每个位置i(0 i n)搜寻成功的概率相同，均为 p/n。1.4 算法分析的基本法则算法分析的基本法则非递归算法：非递归算法：（1）for/while 循环循环循环体内计算时间循环体内计算时间*循环次数；循环次数；（2）嵌套循环）嵌套循环循环体内计算时间循环体内计算时间*全部循环次数；全部循环次数；（3）依次语句）依次语句各语句计算时间相加；各语句计算时间相加；（4）if-else语句语句if语句计算时间和语句计算时间和else语句计算时间的较大者。语句计算时间的较大者。templatevoid insertion_sort(Type*a,int n)Type key;/cost times for(int i=1;i=0&ajkey)/c4 sum of ti aj+1=aj;/c5 sum of(ti-1)j-;/c6 sum of(ti-1)aj+1=key;/c7 n-1 在最好状况下，ti=1,for 1 i n;在最坏状况下，ti i+1,for 1 i n;对于输入数据ai=n-i(逆序),i=0,1,n-1，算法insertion_sort 达到其最坏情形。因此，由此可见，Tmax(n)=(n2)最优算法最优算法问题的计算时间下界为(f(n)，则计算时间困难性为O(f(n)的算法是最优算法。例如，排序问题的计算时间下界为(nlogn)，计算时间困难性为O(nlogn)的排序算法是最优算法。堆排序算法是最优算法。递归算法困难性分析递归算法困难性分析 int factorial(int n)if(n=0)return 1;return n*factorial(n-1);递归的蒙娜丽莎递归的蒙娜丽莎1.5.1P类与NP类问题n易处理的问题:可由多项式时间算法求解的问题n 难处理的问题:须要超多项式时间才能求解的问题n 不行解问题：任何计算机无论耗费多少时间也不能解决的问题n 例如：“图灵停机问题”n “Keyboard not found.press F1 to continue”n有很多问题，从表面上看似乎并不比排序或图的搜寻等问题更困难，然而至今人们还没有找到解决这些问题的多项式时间算法，也没有人能够证明这些问题须要超多项式时间下界。在图灵机计算模型下，这类问题的计算困难性至今未知。1.5 NP完全性理论完全性理论图灵机图灵机1.5 NP完全性理论完全性理论图灵机M的时间困难性T(n)是它处理全部长度为n的输入所需的最大计算步数。假如对某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义。图灵停机问题图灵停机问题(The Halting Problem)(The Halting Problem)存在一些不行解问题：图灵停机问题(The Halting Problem)图灵机停机问题的不行判定性:能否给出一个推断随意一个图灵机是否停机的一般方法?答案是NO.这个问题事实上是问:是否存在一台万能的图灵机 H,把随意一台图灵机 M 输入给 H,它都能判定 M 最终是否停机,输出一个明确的 yes 或 no 的答案?可以利用反证法来证明这样的H不行能存在.假定存在一个能够判定随意一台图灵机是否停机的万能图灵机H(M),假如M最终停机,H输出 halt;假如M不停机,H输出 loop.我们把H当作子程序,构造如下程序P:function P(M)if(H(M)=loop)return halt;else if(H(M)=halt)while(true);/loop forever 因为 P本身也是一台图灵机,所以我们可以把 P 输入给它自己,然后问 P(P)是否停机.依据程序P的流程,假如P不停机无限循环,那么它就停机,输出halt;假如P停机,那么它就无限循环,不停机;这样无论如何我们都将得到一个冲突,所以假设前提不成立,即不存在这样的H.或者说,图灵机停机问题是不行判定的(undecidable).图灵停机问题图灵停机问题(The Halting Problem)(The Halting Problem)另外还有两个本质上相像的悖论：理发师悖论：村子里有个理发师，这个理发师有条原则是，对于村里全部人，当且仅当这个人不自己理发，理发师就给这个人理发。假如这个人自己理发，理发师就不给这个人理发。无法回答的问题是，理发师给自己理发么？停机测试悖论：计算机里有个测试程序，这个测试程序的原则是，对于计算机里全部程序，当且仅当这个程序不递归调用自己(输出停机)，测试程序就调用它(对应不停机)。假如这个程序递归调用自己（对应不停机），测试程序就不调用它（对应停机）。无法回答的问题是，测试程序递归调用自己么？图灵停机问题图灵停机问题(The Halting Problem)(The Halting Problem)1.5.1P类与NP类问题n 非确定性问题：有些问题的答案无法干脆计算得到，只能通过间接的“猜算”来得到结果。n 而这些问题的通常有个算法，它不能干脆告知你答案是什么，但可以告知你，某个可能的结果是正确的答案还是错误的。这个可以告知你“猜算”的答案正确与否的算法，假如可以在多项式时间内算出来，就叫做多项式非确定性问题。而假如这个问题的全部可能答案，都是可以在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题。旅行售货员问题旅行售货员问题（Traveling Salesman Problem）n最优化形式的最优化形式的TSP问题：问题：n n判定形式的判定形式的TSP问题：问题：n 对于给定的带权图对于给定的带权图G=(V,E)的一个正数的一个正数d，要求判定图，要求判定图G中是否存在总费用不超过中是否存在总费用不超过d的周游路途。的周游路途。101234302065410设G=(V,E)是一个带权图。图中各边的费用（权）为正数。图的一条周游路途是包括V中的每个顶点在内的一条回路。TSP要求在图G中找出费用最小的周游路途。较难较难较易较易n P类问题：可以在多项式时间内求解的判定问题。类问题：可以在多项式时间内求解的判定问题。n 确定性计算模型下的易解问题类。确定性计算模型下的易解问题类。n 非确定性算法：将问题求解分为揣测和验证两个阶段。非确定性算法：将问题求解分为揣测和验证两个阶段。n揣测：给出问题的一个揣测揣测：给出问题的一个揣测非确定性非确定性n验证：验证揣测阶段给出解的正确性验证：验证揣测阶段给出解的正确性确定性确定性n NP类问题：非确定性多项式时间可解的判定问题。类问题：非确定性多项式时间可解的判定问题。n 非确定性计算模型下的易验证问题类。非确定性计算模型下的易验证问题类。n 非确定性图灵机计算模型非确定性图灵机计算模型NDTM(Nondeterministic Turing Machine)：在：在NDTM模型下，很多问题可以在多项式时间内求模型下，很多问题可以在多项式时间内求解解NP问题问题(Nondeterministic Polynomial)1.5.1 P类与类与NP类问题类问题PNPNPCNP-Hard关系nP：可以在多项式时间解决的问题nNP：目前没有多项式时间解决的算法，但是假如给出一个候选答案，可以在多项式时间里验证这个答案是不是正确的。nNPC：满足两特性质：1.可在多项式时间验证候选答案（是NP问题）；2.任何一个NP问题可在多项式时间内规约到该问题。nNP-Hard：任何一个NP问题可在多项式时间内规约到该问题，但无法证明问题本身是NP问题。NP-Hard至少和NP问题一样难。1.5.2NP完全问题（完全问题（NPC）nPNP。n直观上看，P类问题是确定性计算模型下的易解问题类，而NP类问题是非确定性计算模型下的易验证问题类。n大多数的计算机科学家认为NP类中包含了不属于P类的语言，即PNP。nNP完全问题有一种令人惊异的性质，即假如一个NP完全问题能在多项式时间内得到解决，那么NP中的每一个问题都可以在多项式时间内求解，即P=NP。n目前还没有一个NP完全问题有多项式时间算法。逻辑电路问题-给定一个逻辑电路，问是否存在一种输入使输出为True。一个逻辑电路由若干个输入，一个输出，若干“逻辑门”和导线组成。1.5.3 一些典型的NP完全问题存在输出不行能为True的逻辑电路：1.5.3 一些典型的NP完全问题逻辑电路问题明显属于NP问题，并且可以干脆证明全部的NP问题都可以约化到它（不要以为NP问题有无穷多个将给证明造成不行逾越的困难）。证明过程相当困难，其或许意思是说随意一个NP问题的输入和输出都可以转换成逻辑电路的输入和输出（想想计算机内部也不过是一些 0和1的运算），因此对于一个NP问题来说，问题转化为了求出满足结果为True的一个输入（即一个可行解）。1.5.3 一些典型的NP完全问题 定理定理8-7(Cook8-7(Cook定理定理)：布尔表达式的可满足性问题：布尔表达式的可满足性问题SATSAT是是NPNP完完全的。全的。-第一个第一个NPCNPC问题问题证明：SAT的一个实例是k个布尔变量 ，的m个布尔表达式 ，若存在各布尔变量 (1ik)的0，1赋值，使每个布尔表达式 (1im)都取值1，则称布尔表达式 是可满足可满足的。SATNP是很明显的。对于任给的布尔变量 ，的0，1赋值，容易在多项式时间内验证相应的 的取值是否为1。因此，SATNP。现在只要证明对任意的LNP有LpSAT即可（略）一些典型的NP完全问题1.5.3 一些典型的NP完全问题部分NP完全问题树布尔表达式的可满足问题布尔表达式的可满足问题合取范式的可满足问题合取范式的可满足问题三元合取范式的可满足问题三元合取范式的可满足问题哈密顿回路问题哈密顿回路问题旅行售货商问题旅行售货商问题团问题团问题顶点覆盖问题顶点覆盖问题子集和问题子集和问题65（1）合取范式的可满足性问题（CNF-SAT）问题描述：给定一个合取范式，判定它是否可满足。如果一个布尔表达式是一些因子和之积，则称之为合取范式，简称CNF(Conjunctive Normal Form)。这里的因子是变量 或 。例如：就是一个合取范式，而 就不是合取范式。（2）3元合取范式的可满足性问题（3-SAT）问题描述：给定一个3元合取范式，判定它是否可满足。1.5.3 一些典型的NP完全问题66（3）团问题（CLIQUE）问题描述：给定一个无向图G=(V，E)和一个正整数k，判定图G是否包含一个k团，即是否存在，VV，|V|=k，且对随意u，wV有(u，w)E。（4）顶点覆盖问题（VERTEX-COVER）问题描述：给定一个无向图G=(V，E)和一个正整数k，判定是否存在VV，|V|=k，使得对于随意(u，v)E有uV或vV。假如存在这样的V，就称V为图G的一个大小为k顶点覆盖。1.5.3 一些典型的NP完全问题 67（5）子集和问题（子集和问题（SUBSET-SUMSUBSET-SUM）问题描述问题描述：给定整数集合S和一个整数t，判定是否存在S的一个子集SS，使得S中整数的和为t。例如，若S=1，4，16，64，256，1040，1041，1093，1284，1344且t=3754，则子集S=1，16，64，256，1040，1093，1284是一个解。（6）哈密顿回路问题（哈密顿回路问题（HAM-CYCLE）问题描述：问题描述：给定无向图G=(V，E)，判定其是否含有一哈密顿回路。1.5.3 一些典型的NP完全问题（7）旅行售货员问题（旅行售货员问题（TSP）问题描述：问题描述：给定一个无向完全图G=(V，E)及定义在VV上的一个费用函数c和一个整数k，判定G是否存在经过V中各顶点恰好一次的回路，使得该回路的费用不超过k。迄今为止，全部的NP完全问题都还没有多项式时间算法。对于这类问题，通常可实行以下几种解题策略。(1)只对问题的特殊实例求解(2)用动态规划法或分支限界法求解(3)用概率算法求解(4)只求近似解(5)用启发式方法求解 NP完全问题的近似算法A joke:nThe boss wants to produce programs to solve the following two problemsn Euler circuit problem:n given a graph G,find a way to go through each edge exactly once.nHamilton circuit problem:n given a graph G,find a way to go through each vertex exactly once.nThe two problems seem to be very similar.nPerson A takes the first problem and person B takes the second.nOutcome:Person A quickly completes the program,whereas person B works 24 hours per day and is fired after a few months.Euler Circuit and Hamilton Circuit A joke(continued):nWhy?nobody in the company has taken this course.nExplanation:nEuler circuit problem can be easily solved in polynomial time.nHamilton circuit problem is proved to be NP-hard.nSo far,nobody in the world can give a polynomial time algorithm for a NP-hard problem.nConjecture:there does not exist polynomial time algorithm for this problem.