数理逻辑10-2.2 算法复杂性

1、数理逻辑 Mathematical Logic 第二章 算法、整数和矩阵 Chapter 2 Algorithm、Integer and Matrix 复习 算法具有的若干共有的性质 输入、输出、确定性、正确性、有限性、 有效性、通用性 求整数序列最大元算法 线性搜索算法 对分搜索算法 复习 三分搜索法 练习题 求一个序列中所有整数之和的算法； Procedure sum (a1,an: 整数) sum :=a1; for i :=2 to n sum :=sum+ai sum 为所有整数的和 练习题 给出一个算法，逐一检查位串中每个字位是否为1，计算 其中1的个数； Procedure on

2、es (a=a1an, a:位串) ones :=0 for i :=1 to n if ai :=1 then ones :=ones+1 ones为位串a中1的个数 练习题 给出一个求有限自然数序列中最小整数 的算法； Procedure min (a1,a2,an:自然数) min :=a1 for i :=2 to n if minai then min :=ai min是最小整数 练习题 确定有限整数序列中最大元素首次出现的位置的算法， 其中的整数不必互不相同； Procedure first largest (a1,an: 整数) max :=a1 location :=1 for

3、 i :=2 to n if maxai, then 练习题 确定有限整数序列中最大元素首次出现的位置的算法， 其中的整数不必互不相同； if maxai, then begin max :=ai location :=i end location为最大元素首次出现的位置 2.2 算法的复杂性 Complexity of Algorithms 一、引言 什么时候算法对问题提供令人满意的解？ 它必须给出正确的答案； 它必须有效率。 怎样分析算法的效率呢？ 计算机按此算法解题所花的时间； 计算机实现这一算法需要多大内存（假定 输入值的规模是一定的）。 一、引言 算法的计算复杂性 算法的时间复杂性

4、算法的空间复杂性 了解算法是1微秒、一分钟还是一亿年才能 给出答案 必须能提供所需的内存 空间复杂性与实现算法时使用的特定数据 结构紧密相关。 二、算法的时间复杂性 时间复杂性可以在输入规模一定的情况 下用算法使用的运算次数来表示； 使用的运算包括整数比较、整数加法、 整数乘法、整数除法等基本运算； 不用计算机实际使用时间来表示 不同的计算机需要的时间不同； 把运算分解成基本字位运算相当复杂。 二、算法的时间复杂性 例1：描述求集合最大元素的算法的时间 复杂性。 用比较的次数作为其时间复杂性的度量； 让临时最大元素等于列表中的初始项； 做一次比较后判断尚未达到列表的终点； 临时最大元素和第二项

5、比较，如果第二项 大，就用第二项的值更新临时最大元素； 二、算法的时间复杂性 例1：描述求集合最大元素的算法的时间 复杂性。 继续该过程，对表中的第二项到第n项都要 做两次比较：一次判断尚未达到列表终点， 一次判断是否需要更新临时最大元； 这一算法使用的比较次数为2(n-1)； 因此，求n元集合最大值的算法的时间复杂 性是O(n)。 二、算法的时间复杂性 例2：描述线性搜索的时间复杂性。 用比较的次数作为其时间复杂性的度量； 每次循环都做两次比较：一次判断是否已 到表的终点，一次比较x和表中的一个项； 最后还要在循环外做一次比较； 于是，当x=ai时，需要做2i+1次比较； 当x不在表中时，需

6、要2n+2次比较（多了一 次用于脱离循环的比较）； 二、算法的时间复杂性 例2：描述线性搜索的时间复杂性。 所以当x不在表中时，共用了2n+2次比较； 所以线性搜索最多需要2n+2次比较； 其算法复杂性是O(n)。 这类复杂性分析是最坏情况分析。 把算法应用于一定规模的问题时最多需要 多少次运算 二、算法的时间复杂性 例3：描述对分搜索的时间复杂性。 为了简化，设表a1,a2,an中有n=2k个元素， k=logn； 对于算法的每一阶段，首先判断i是否小于j， 如果i1，就说它 有指数复杂性 如果时间复杂性是O(nb)，就说它有多项式复杂性 二、算法的时间复杂性 能用具有多项式最坏情况复杂性的

7、算法 解决的问题称为易处理的（P问题）； 不能用最坏情况多项式时间复杂性的算 法求解的问题称为不易处理的； 通常不求问题的精确解，而以近似解代替 没有解题算法存在的问题称为不可解的 （停机问题）； 二、算法的时间复杂性 许多可解的问题都没有多项式最坏情况 时间复杂性算法能解答他们，但是一旦 有了一个解答，却可以以多项式时间来 验证。 能以多项式时间验证解的问题称为NP问 题。 二、算法的时间复杂性 算法的时间复杂性 如果算法使用的所有运算都归结为计算机 使用的字位运算，每次字位运算需要的时 间是10-9秒 图灵 第一个证明存在不可解问题的是英国数 学家和计算机科学家图灵。 艾伦麦席森图灵，（A

8、lan Mathison Turing），1912年6月23日1954年6月7 日，英国数学家、逻辑学家，他被视为 “计算机之父”、 “人工智能之父” 。 图灵 冯诺依曼不止一次地说过，图灵是现代 计算机设计思想的创始人。当有人将电 子计算机之父的头衔戴在冯诺依曼头 上时，他谦逊地说，真正的计算机之父 应该是图灵。当然，冯诺依曼问之无愧， 而图灵也有“人工智能之父”的桂冠。 他俩是计算机历史浩瀚星空中相互映照 的两颗巨星。 图灵 1931年图灵进入剑桥大学国王学院，毕 业后到美国普林斯顿大学攻读博士学位， 二战爆发后回到剑桥，后曾协助军方破 解德国的著名密码系统Enigma，帮助盟 军取得了二

9、战的胜利。（密码迷情 英文名是enigma就是根据图灵当时 破译德国密码的故事改编的。） 图灵 图灵对于人工智能的发展有诸多贡献，例如图灵曾写过 一篇名为机器会思考吗？（Can Machine Think?）的 论文，其中提出了一种用于判定机器是否具有智能的试 验方法，即图灵试验。至今，每年都有试验的比赛。 此外，图灵提出的著名的图灵机模型为现代计算机的逻 辑工作方式奠定了基础。 图灵 图灵这个人很古怪，只喜欢自己一个人 闷头研究，不喜欢与别人交流。并且据 说他还是一个同性恋者。要知道在当时 的英国，同性恋行为可是大逆不道的。 最后，在他事业刚刚达到顶峰的时候， 他自杀了。 为了纪念这个伟大的

10、学者，计算机界设 立了最高荣誉奖：图灵奖。 图灵试验 一个人在不接触对方的情况下，通过一种特殊的方式， 和对方进行一系列的问答，如果在相当长时间内，他无 法根据这些问题判断对方是人还是计算机，那么，就可 以认为这个计算机具有同人相当的智力，即这台计算机 是能思维的。 问：34957加70764等于多少？ 答：（停30秒后）105721 问：你会下国际象棋吗？ 答：是的。 图灵试验 从表面上看，要使机器回答按一定范围提出的问题 似乎没有什么困难，可以通过编制特殊的程序来实 现。然而，如果提问者并不遵循常规标准，编制回 答的程序是极其困难的事情。 问：你会下国际象棋吗？ 答：是的。 问：你会下国际

11、象棋吗？ 答：是的。 问：请再次回答，你会下 国际象棋吗？ 答：是的。 问： 你会下国际象棋吗？ 答：是的。 问：你会下国际象棋吗？ 答：是的，我不是已经说过了吗？ 问：请再次回答，你会下国际象棋吗？ 答：烦不烦，干嘛老提同样的问题。 图灵机 这个装置包括：一个无限长的纸带， 一个读写头，内部状态，另外，还 有一个程序对这个盒子进行控制。 这个装置就是根据程序的命令以及 它的内部状态进行磁带的读写、移 动。 从读写头在纸带上读出一个方格的 信息，并且根据它当前的内部状态 开始对程序进行查表，然后得出一 个输出动作，也就是是否往纸带上 写信息，还是移动读写头到下一个 方格。程序也会告诉它下一时刻

12、内 部状态转移到哪一个。 图灵机 具体的程序就是一个列表，也叫做规则 表，是这样的： 当前内部状态s 输入数值i 输出动作o 下一 时刻的内部状态s B 1 前移 C A 0 往纸带上写1 B C 0 后移 A 图灵机 图灵机就是这么简单！不可思议吧？而只要你变化它的 程序（也就是上面的规则表），那么它就可能为你做任 何计算机能够完成的工作。因此可以说，图灵机就是一 个最简单的计算机模型！ 也许，你会觉得图灵机模型太简单，怎么可能完成计算 机的复杂任务呢？问题的关键是如何理解这个模型。 图灵机 假设一个小虫在地上爬，那么我们应该怎样从小虫 信息处理的角度来建立它的模型？ 首先，我们需要对小虫所

13、在的环境进行建模。 假设小虫所处的世界是一个无限长的纸带，这个纸带上被 分成了若干小的方格，而每个方格都仅仅只有黑和白两种 颜色。 小虫要有眼睛或者鼻子或者耳朵等等感觉器官来获得世界 的信息，我们不妨把模型简化，假设它仅仅具有一个感觉 器官：眼睛，而且它的视力短得可怜，也就是说它仅仅能 够感受到它所处的方格的颜色。 因而这个方格所在的位置的黑色或者白色的信息就是小虫 的输入信息。 图灵机 另外，我们还需要为小虫建立输出装置，也就是说 它能够动起来。我们仍然考虑最简单的情况：小虫 的输出动作就是往纸带上前爬一个方格或者后退一 个方格。 仅仅有了输入装置以及输出装置，小虫还不能动起 来，原因很简单

14、，它并不知道该怎样在各种情况下 选择它的输出动作。 我们还需要给它指定行动的规则，这就是程序！假 设我们记小虫的输入信息集合为I=黑色，白色，它 的输出可能行动的集合就是：O=前移，后移，那 么程序就是要告诉它在给定了输入比如黑的情况下， 它应该选择什么输出。 图灵机 程序1： 输入 输出 黑色 前移 白色 后移 小虫所处的世界的一个片断是：黑黑黑 白白黑白 图灵机 然而，现实世界中的小虫肯定不会这样傻的在那里无限 循环下去。我们还需要改进这个最简单的模型。 我们知道小虫除了可以机械地在世界上移动以外，还会 对世界本身造成影响，因而改变这个世界。 比如虫子看到旁边有食物，它就会把那个东西吃掉了

15、。 在我们这个模型中，也就相当于小虫可以改写纸带上的 信息。因而，小虫可能的输出动作集合就变成了：O=前 移，后移，涂黑，涂白。 图灵机 程序2： 输入 输出 黑 前移 白 涂黑 纸带是黑黑白白黑，小虫会怎样行动呢？ 图灵机 你还可以设计出其他的程序来，然而无论你的程序怎么 复杂，也无论纸带子的情况如何，小虫的行为都会要么 停留在一个方格上，要么朝一个方向永远运动下去，或 者就是在几个方格上来回打转。 无论怎样，小虫比起真实世界中的虫子来说，还有一个 致命的弱点：那就是如果你给它固定的输入信息，它都 会给你固定的输出信息！因为我们知道程序是固死的。 图灵机 我们进一步更改小虫模型，至少在给定相

16、同输入的情况 下，小虫会有不同的输出情况。这就是加入小虫的内部 状态！ 假设黑色方格是食物，虫子可以吃掉它，而当吃到一个 食物后，小虫子就会感觉到饱了。当读入的信息是白色 方格的时候，虽然没有食物但它仍然吃饱了，只有当再 次读入黑色时候它才会感觉到自己饥饿了。 小虫具有两个内部状态，并把它内部状态的集合记为： S=饥饿，吃饱。 图灵机 这样小虫行为的时候就会不仅根据它的输入信息， 而且也会根据它当前的内部状态来决定它的输出动 作，并且还要更改它的内部状态。 程序3： 输入 当前内部状态 输出 下时刻的内部状态 黑 饥饿 涂白 吃饱 黑 吃饱 后移 饥饿 白 饥饿 涂黑 饥饿 白 吃饱 前移 吃

17、饱 图灵机 虫子在读入黑白白黑白这样的纸带的时候，会怎样？ 小虫的行为比以前的程序复杂了一些。尽管从长期来看， 它最后仍然会落入机械的循环或者无休止的重复。然而 这从本质上已经与前面的程序完全不同了，因为当你输 入给小虫白色信息的时候，它的反应是你不能预测的！ 图灵机 它有可能涂黑方格也有可能前移一个。当然前提是你不 能打开小虫看到它的内部结构，也不能知道它的程序， 那么你所看到的就是一个不能预测的满地乱爬的小虫。 如果小虫的内部状态数再增多呢，那么它的行为会更加 的不可预测！ 从本质上讲，最后的小虫模型就是一个图灵机！ 图灵机 相信你的第一个反映就是，这样的模型太简单了！ 他根本说明不了现实

18、世界中的任何问题！ 其实我们每一个会决策、会思考的人就可以被抽象 的看成一个图灵机。 首先我们可以考虑扩展刚才说的小虫模型。因为小 虫模型是以一切都简化的前提开始的，所以它的确 是太太简单了。然而，我们可以把小虫的输入集合、 输出行动集合、内部状态集合进行扩大，这个模型 就一下子实用多了。 图灵机 首先，小虫完全可以处于一个三维的空间中而不是 简简单单的纸带； 并且小虫的视力很好，它一下子能读到方圆500米的 信息； 当然，小虫也可以拥有其他的感觉器官，比如嗅觉、 听觉等等； 而这些改变都仅仅是扩大了输入集合的维数和范围， 并没有其他更本质的改变； 同样道理，小虫可能的输出集合也是异常的丰富，

19、 它不仅仅能移动自己，还可以尽情的改造它所在的 自然界。 图灵机 进一步的，小虫的内部状态可能非常的多，而且控制它 行为的程序可能异常复杂，那么小虫会有什么本事呢？ 这就很难说了，因为随着小虫内部的状态数的增加，随 着它所处环境的复杂度的增加，我们正在逐渐失去对小 虫行为的预测能力。 但是所有这些改变仍然没有逃出图灵机的模型：输入集 合、输出集合、内部状态、固定的程序！就是这四样东 西抓住了小虫信息处理的根本。 图灵机 我们人能不能也被这样的抽象呢？显然，输入集合就是 你所处的环境中能够看到、听到、闻到、感觉到的所有 一起，可能的输出集合就是你的每一言每一行，以及你 能够表达出来的所有表情动作

20、。内部状态集合则要复杂 得多。因为我们可以把任意一个神经细胞的状态组合看 作是一个内部状态，那么所有可能的神经细胞的状态组 合将是天文数字！ 图灵机 记忆问题 学习问题 情绪、情感 图灵相信：人脑也不会超越图灵机这个模型。 所以，人工智能也必然是可能的！ P、NP问题 P问题 易处理的问题 Polynomial NP问题 没有多项式最坏情况时间复杂度算法能解答 能以多项式时间验证解的问题 Non-Deterministic Polynomial 美国克雷（Clay）数学研究所于2000年宣布：对七个 “千僖年数学难题”的每一个悬赏一百万美元 P、NP问题 NP 完全问题， 郝治(Hodge)猜

21、想， 庞加莱(Poincare)猜想， 黎曼(Rieman)假设，杨-米尔斯 (Yang-Mills) 理论, 纳卫尔 斯托可(Navier-Stokes)方程， BSD(Birch and Swinnerton-Dyer)猜想。 NP完全问题，也即“NP COMPLETE”问题，简单的写法， 是 NP=P？的问题。问题就在这个问号上，到底是NP等 於P，还是NP不等於P。证明其中之一，便可以拿百万美 元大奖。 P、NP问题 在一个周六的晚上，你参加了一个盛大的晚会。由于感 到局促不安，你想知道这一大厅中是否有你已经认识的 人。你的主人向你提议说，你一定认识那位正在甜点盘 附近角落的女士罗丝。

22、不费一秒钟，你就能向那里扫视， 并且发现你的主人是正确的。然而，如果没有这 样的暗 示，你就必须环顾整个大厅，一个个地审视每一个人， 看是否有你认识的人。 P、NP问题 生成问题的一个解通常比验证一个给定的解时间花费要 多得多。 如果某人告诉你，数13,717,421可以写成两个较小的数的 乘积，你可能不知道是否应该相信他； 但是如果他告诉你它可以因子分解为3,607乘上3,803，那 么你就可以用一个袖珍计算器容易验证这是对的。 P、NP问题 问题的答案无法直接计算得到的，只能通过间接的 “猜算”来得到结果。这也就是非确定性问题。 而这些问题的通常有个算法，它不能直接告诉你答 案是什么，但可以告诉你，某个可能的结果是正确 的答案还是错误的。这个可以告诉你“猜算”的答 案正确与否的算