《数理逻辑102.2算法复杂性》由会员分享，可在线阅读，更多相关《数理逻辑102.2算法复杂性（61页珍藏版）》请在金锄头文库上搜索。
1、数理逻辑Mathematical Logic 第二章 算法、整数和矩阵Chapter 2 Algorithm、Integer and Matrix复习算法具有的若干共有的性质输入、输出、确定性、正确性、有限性、有效性、通用性求整数序列最大元算法线性搜索算法对分搜索算法复习三分搜索法练习题求一个序列中所有整数之和的算法；Procedure sum (a1,an: 整数)sum :=a1;for i :=2 to n sum :=sum+aisum 为所有整数的和练习题给出一个算法，逐一检查位串中每个字位是否为1，计算其中1的个数；Procedure ones (a=a1an, a:位串)ones
2、 :=0for i :=1 to n if ai :=1 then ones :=ones+1ones为位串a中1的个数练习题给出一个求有限自然数序列中最小整数的算法；Procedure min (a1,a2,an:自然数)min :=a1for i :=2 to n if minai then min :=ai min是最小整数 练习题确定有限整数序列中最大元素首次出现的位置的算法，其中的整数不必互不相同；Procedure first largest (a1,an: 整数)max :=a1location :=1for i :=2 to nif maxai, then练习题确定有限整数序列
3、中最大元素首次出现的位置的算法，其中的整数不必互不相同；if maxai, then begin max :=ai location :=i endlocation为最大元素首次出现的位置2.2 算法的复杂性Complexity of Algorithms一、引言什么时候算法对问题提供令人满意的解？它必须给出正确的答案；它必须有效率。怎样分析算法的效率呢？计算机按此算法解题所花的时间；计算机实现这一算法需要多大内存（假定输入值的规模是一定的）。一、引言算法的计算复杂性算法的时间复杂性算法的空间复杂性了解算法是1微秒、一分钟还是一亿年才能给出答案必须能提供所需的内存空间复杂性与实现算法时使用的特
4、定数据结构紧密相关。二、算法的时间复杂性时间复杂性可以在输入规模一定的情况下用算法使用的运算次数来表示；使用的运算包括整数比较、整数加法、整数乘法、整数除法等基本运算；不用计算机实际使用时间来表示不同的计算机需要的时间不同；把运算分解成基本字位运算相当复杂。二、算法的时间复杂性例1：描述求集合最大元素的算法的时间复杂性。用比较的次数作为其时间复杂性的度量；让临时最大元素等于列表中的初始项；做一次比较后判断尚未达到列表的终点；临时最大元素和第二项比较，如果第二项大，就用第二项的值更新临时最大元素；二、算法的时间复杂性例1：描述求集合最大元素的算法的时间复杂性。继续该过程，对表中的第二项到第n项都
5、要做两次比较：一次判断尚未达到列表终点，一次判断是否需要更新临时最大元；这一算法使用的比较次数为2(n-1)；因此，求n元集合最大值的算法的时间复杂性是O(n)。二、算法的时间复杂性例2：描述线性搜索的时间复杂性。用比较的次数作为其时间复杂性的度量；每次循环都做两次比较：一次判断是否已到表的终点，一次比较x和表中的一个项；最后还要在循环外做一次比较；于是，当x=ai时，需要做2i+1次比较；当x不在表中时，需要2n+2次比较（多了一次用于脱离循环的比较）；二、算法的时间复杂性例2：描述线性搜索的时间复杂性。所以当x不在表中时，共用了2n+2次比较；所以线性搜索最多需要2n+2次比较；其算法复杂
6、性是O(n)。这类复杂性分析是最坏情况分析。把算法应用于一定规模的问题时最多需要多少次运算二、算法的时间复杂性例3：描述对分搜索的时间复杂性。为了简化，设表a1,a2,an中有n=2k个元素，k=logn；对于算法的每一阶段，首先判断i是否小于j，如果i1，就说它有指数复杂性如果时间复杂性是O(nb)，就说它有多项式复杂性二、算法的时间复杂性能用具有多项式最坏情况复杂性的算法解决的问题称为易处理的（P问题）；不能用最坏情况多项式时间复杂性的算法求解的问题称为不易处理的；通常不求问题的精确解，而以近似解代替没有解题算法存在的问题称为不可解的（停机问题）；二、算法的时间复杂性许多可解的问题都没有多
7、项式最坏情况时间复杂性算法能解答他们，但是一旦有了一个解答，却可以以多项式时间来验证。能以多项式时间验证解的问题称为NP问题。二、算法的时间复杂性算法的时间复杂性如果算法使用的所有运算都归结为计算机使用的字位运算，每次字位运算需要的时间是10-9秒图灵第一个证明存在不可解问题的是英国数学家和计算机科学家图灵。艾伦麦席森图灵，（Alan Mathison Turing），1912年6月23日1954年6月7日，英国数学家、逻辑学家，他被视为“计算机之父”、 “人工智能之父” 。图灵冯诺依曼不止一次地说过，图灵是现代计算机设计思想的创始人。当有人将电子计算机之父的头衔戴在冯诺依曼头上时，他谦逊地说
8、，真正的计算机之父应该是图灵。当然，冯诺依曼问之无愧，而图灵也有“人工智能之父”的桂冠。他俩是计算机历史浩瀚星空中相互映照的两颗巨星。图灵1931年图灵进入剑桥大学国王学院，毕业后到美国普林斯顿大学攻读博士学位，二战爆发后回到剑桥，后曾协助军方破解德国的著名密码系统Enigma，帮助盟军取得了二战的胜利。（密码迷情英文名是enigma就是根据图灵当时破译德国密码的故事改编的。）图灵图灵对于人工智能的发展有诸多贡献，例如图灵曾写过一篇名为机器会思考吗？（Can Machine Think?）的论文，其中提出了一种用于判定机器是否具有智能的试验方法，即图灵试验。至今，每年都有试验的比赛。此外，图灵
9、提出的著名的图灵机模型为现代计算机的逻辑工作方式奠定了基础。图灵图灵这个人很古怪，只喜欢自己一个人闷头研究，不喜欢与别人交流。并且据说他还是一个同性恋者。要知道在当时的英国，同性恋行为可是大逆不道的。最后，在他事业刚刚达到顶峰的时候，他自杀了。为了纪念这个伟大的学者，计算机界设立了最高荣誉奖：图灵奖。图灵试验一个人在不接触对方的情况下，通过一种特殊的方式，和对方进行一系列的问答，如果在相当长时间内，他无法根据这些问题判断对方是人还是计算机，那么，就可以认为这个计算机具有同人相当的智力，即这台计算机是能思维的。问：34957加70764等于多少？答：（停30秒后）105721问：你会下国际象棋吗
10、？答：是的。图灵试验从表面上看，要使机器回答按一定范围提出的问题似乎没有什么困难，可以通过编制特殊的程序来实现。然而，如果提问者并不遵循常规标准，编制回答的程序是极其困难的事情。问：你会下国际象棋吗？答：是的。问：你会下国际象棋吗？答：是的。问：请再次回答，你会下国际象棋吗？答：是的。问： 你会下国际象棋吗？答：是的。问：你会下国际象棋吗？答：是的，我不是已经说过了吗？问：请再次回答，你会下国际象棋吗？答：烦不烦，干嘛老提同样的问题。图灵机这个装置包括：一个无限长的纸带，一个读写头，内部状态，另外，还有一个程序对这个盒子进行控制。这个装置就是根据程序的命令以及它的内部状态进行磁带的读写、移动。
11、从读写头在纸带上读出一个方格的信息，并且根据它当前的内部状态开始对程序进行查表，然后得出一个输出动作，也就是是否往纸带上写信息，还是移动读写头到下一个方格。程序也会告诉它下一时刻内部状态转移到哪一个。图灵机具体的程序就是一个列表，也叫做规则表，是这样的：当前内部状态s 输入数值i 输出动作o 下一时刻的内部状态sB 1 前移 CA 0 往纸带上写1 BC 0 后移 A 图灵机图灵机就是这么简单！不可思议吧？而只要你变化它的程序（也就是上面的规则表），那么它就可能为你做任何计算机能够完成的工作。因此可以说，图灵机就是一个最简单的计算机模型！也许，你会觉得图灵机模型太简单，怎么可能完成计算机的复杂
12、任务呢？问题的关键是如何理解这个模型。图灵机假设一个小虫在地上爬，那么我们应该怎样从小虫信息处理的角度来建立它的模型？首先，我们需要对小虫所在的环境进行建模。假设小虫所处的世界是一个无限长的纸带，这个纸带上被分成了若干小的方格，而每个方格都仅仅只有黑和白两种颜色。小虫要有眼睛或者鼻子或者耳朵等等感觉器官来获得世界的信息，我们不妨把模型简化，假设它仅仅具有一个感觉器官：眼睛，而且它的视力短得可怜，也就是说它仅仅能够感受到它所处的方格的颜色。因而这个方格所在的位置的黑色或者白色的信息就是小虫的输入信息。图灵机另外，我们还需要为小虫建立输出装置，也就是说它能够动起来。我们仍然考虑最简单的情况：小虫的
13、输出动作就是往纸带上前爬一个方格或者后退一个方格。仅仅有了输入装置以及输出装置，小虫还不能动起来，原因很简单，它并不知道该怎样在各种情况下选择它的输出动作。我们还需要给它指定行动的规则，这就是程序！假设我们记小虫的输入信息集合为I=黑色，白色，它的输出可能行动的集合就是：O=前移，后移，那么程序就是要告诉它在给定了输入比如黑的情况下，它应该选择什么输出。图灵机程序1：输入 输出黑色 前移白色 后移小虫所处的世界的一个片断是：黑黑黑白白黑白图灵机然而，现实世界中的小虫肯定不会这样傻的在那里无限循环下去。我们还需要改进这个最简单的模型。我们知道小虫除了可以机械地在世界上移动以外，还会对世界本身造成
14、影响，因而改变这个世界。比如虫子看到旁边有食物，它就会把那个东西吃掉了。在我们这个模型中，也就相当于小虫可以改写纸带上的信息。因而，小虫可能的输出动作集合就变成了：O=前移，后移，涂黑，涂白。图灵机程序2：输入 输出黑 前移白 涂黑纸带是黑黑白白黑，小虫会怎样行动呢？图灵机你还可以设计出其他的程序来，然而无论你的程序怎么复杂，也无论纸带子的情况如何，小虫的行为都会要么停留在一个方格上，要么朝一个方向永远运动下去，或者就是在几个方格上来回打转。无论怎样，小虫比起真实世界中的虫子来说，还有一个致命的弱点：那就是如果你给它固定的输入信息，它都会给你固定的输出信息！因为我们知道程序是固死的。图灵机我们
15、进一步更改小虫模型，至少在给定相同输入的情况下，小虫会有不同的输出情况。这就是加入小虫的内部状态！假设黑色方格是食物，虫子可以吃掉它，而当吃到一个食物后，小虫子就会感觉到饱了。当读入的信息是白色方格的时候，虽然没有食物但它仍然吃饱了，只有当再次读入黑色时候它才会感觉到自己饥饿了。小虫具有两个内部状态，并把它内部状态的集合记为：S=饥饿，吃饱。图灵机这样小虫行为的时候就会不仅根据它的输入信息，而且也会根据它当前的内部状态来决定它的输出动作，并且还要更改它的内部状态。程序3：输入 当前内部状态 输出 下时刻的内部状态黑 饥饿 涂白 吃饱黑 吃饱 后移 饥饿白 饥饿 涂黑 饥饿白 吃饱 前移 吃饱图
16、灵机虫子在读入黑白白黑白这样的纸带的时候，会怎样？小虫的行为比以前的程序复杂了一些。尽管从长期来看，它最后仍然会落入机械的循环或者无休止的重复。然而这从本质上已经与前面的程序完全不同了，因为当你输入给小虫白色信息的时候，它的反应是你不能预测的！图灵机它有可能涂黑方格也有可能前移一个。当然前提是你不能打开小虫看到它的内部结构，也不能知道它的程序，那么你所看到的就是一个不能预测的满地乱爬的小虫。如果小虫的内部状态数再增多呢，那么它的行为会更加的不可预测！从本质上讲，最后的小虫模型就是一个图灵机！图灵机相信你的第一个反映就是，这样的模型太简单了！他根本说明不了现实世界中的任何问题！其实我们每一个会决
17、策、会思考的人就可以被抽象的看成一个图灵机。首先我们可以考虑扩展刚才说的小虫模型。因为小虫模型是以一切都简化的前提开始的，所以它的确是太太简单了。然而，我们可以把小虫的输入集合、输出行动集合、内部状态集合进行扩大，这个模型就一下子实用多了。图灵机首先，小虫完全可以处于一个三维的空间中而不是简简单单的纸带；并且小虫的视力很好，它一下子能读到方圆500米的信息；当然，小虫也可以拥有其他的感觉器官，比如嗅觉、听觉等等；而这些改变都仅仅是扩大了输入集合的维数和范围，并没有其他更本质的改变；同样道理，小虫可能的输出集合也是异常的丰富，它不仅仅能移动自己，还可以尽情的改造它所在的自然界。图灵机进一步的，小
18、虫的内部状态可能非常的多，而且控制它行为的程序可能异常复杂，那么小虫会有什么本事呢？这就很难说了，因为随着小虫内部的状态数的增加，随着它所处环境的复杂度的增加，我们正在逐渐失去对小虫行为的预测能力。但是所有这些改变仍然没有逃出图灵机的模型：输入集合、输出集合、内部状态、固定的程序！就是这四样东西抓住了小虫信息处理的根本。图灵机我们人能不能也被这样的抽象呢？显然，输入集合就是你所处的环境中能够看到、听到、闻到、感觉到的所有一起，可能的输出集合就是你的每一言每一行，以及你能够表达出来的所有表情动作。内部状态集合则要复杂得多。因为我们可以把任意一个神经细胞的状态组合看作是一个内部状态，那么所有可能的
19、神经细胞的状态组合将是天文数字！图灵机记忆问题学习问题情绪、情感图灵相信：人脑也不会超越图灵机这个模型。所以，人工智能也必然是可能的！P、NP问题P问题易处理的问题PolynomialNP问题没有多项式最坏情况时间复杂度算法能解答能以多项式时间验证解的问题Non-Deterministic Polynomial美国克雷（Clay）数学研究所于2000年宣布：对七个“千僖年数学难题”的每一个悬赏一百万美元P、NP问题NP 完全问题， 郝治(Hodge)猜想， 庞加莱(Poincare)猜想， 黎曼(Rieman)假设，杨-米尔斯 (Yang-Mills) 理论, 纳卫尔斯托可(Navier-St
20、okes)方程， BSD(Birch and Swinnerton-Dyer)猜想。NP完全问题，也即“NP COMPLETE”问题，简单的写法，是 NP=P？的问题。问题就在这个问号上，到底是NP等於P，还是NP不等於P。证明其中之一，便可以拿百万美元大奖。P、NP问题在一个周六的晚上，你参加了一个盛大的晚会。由于感到局促不安，你想知道这一大厅中是否有你已经认识的人。你的主人向你提议说，你一定认识那位正在甜点盘附近角落的女士罗丝。不费一秒钟，你就能向那里扫视，并且发现你的主人是正确的。然而，如果没有这 样的暗示，你就必须环顾整个大厅，一个个地审视每一个人，看是否有你认识的人。P、NP问题生成
21、问题的一个解通常比验证一个给定的解时间花费要多得多。如果某人告诉你，数13,717,421可以写成两个较小的数的乘积，你可能不知道是否应该相信他；但是如果他告诉你它可以因子分解为3,607乘上3,803，那么你就可以用一个袖珍计算器容易验证这是对的。P、NP问题问题的答案无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式时间内算出来，就叫做多项式非确定性（NP）问题。而如果这个问题的所有可能答案，都是可以
22、在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定（NPC）问题。P、NP问题NPC问题存在着一个令人惊讶的性质，即如果一个NPC问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P=NP成立！这是因为，每一个NPC问题可以在多项式时间内转化成任何一个NP问题。NPC问题的历史并不久，cook在1971年找到了第一个NPC问题，此后人们又陆续发现很多NPC问题，现在可能已经有3000多个了。P、NP问题完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度，是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变
23、得不可计算了。人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们於是就猜想，是否这类问题，存在一个确定性算法，可以在多项式时间内，直接算出或是搜寻出正确的答案呢？这就是著名的NP=P？的猜想。P、NP问题解决这个猜想，无非两种可能，一种是找到一个这样的算法，只要针对某个特定NP完全问题找到一个算法，所有这类问题都可以迎刃而解了，因为他们可以转化为同一个问题。另外的一种可能，就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。复习算法的时间复杂性在输入规模一定的情况下用算法使用的运算次数来表示常数复杂性、对数复杂性、线性复杂性、nlogn复杂性、多项式复杂性、指数复杂性、阶乘复杂性
