计算机学科的根本问题.ppt

从字源上考察：计：从言从十，有数数或计数的含义；算：从竹从具，指计算工具。现代汉语词典对计算的定义：根据已知数通过数学方法求得未知数。,什么是计算,直观的计算：数的加减乘除；函数的微分、积分；微分方程的求解；定理的证明推导等等。计算的实质：从一个符号串 f（输入）得出另一个符号串 g（输出）。数学概念 普适概念,什么是计算,计算的例子,从符号串“12+3”变换成符号串“15”加法计算符号串“x2”变换成符号串“2x”微分；f 表示一组公理和推导规则，g 是一个定理，那么从 f 到 g 的一系列变换定理g的证明；符号串 f 代表一个英文句子，符号串 g 为含义相同的中文句子，那么从 f 到 g 的变换英文翻译成中文；,这些变换有什么共同点？为什么他们都叫做计算？,图灵与巨人计算机,图灵模型,一条无限长的工作带：工作带上的每个单元可以存放一个符号；所有允许出现的符号属于一个预先规定好的字母表。,图灵模型,有限状态 控制器,工作带,一个读写头：读写头可以左移一个单元、右移一个单元或者保持不动。,图灵模型,有限状态 控制器,工作带,一个控制器：控制器在每个时刻处于一定的状态，当读写头从工作带上读出一个符号后，控制器就根据这个符号和当时的机器状态，指挥读写头进行读写或者移动，并决定是否改变机器状态。,计算与可计算,所谓计算就是计算者（人或机器）对一条可以无限延长的工作带上的符号串执行指令，一步一步地改变工作带上的符号串，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。,什么样的任务才是可计算的任务？这是计算机科学必须要回答的一个最基本的问题。这是关系到计算机能做什么、不能做什么的根本问题。类比：什么样的衣服才是洗衣机可洗的？,构造一个识别符号串anbn（n1）的图灵机基本思想：使读写头往返移动，每往返移动一次，就成对地对输入符号串左端的一个a和右端的一个b匹配并做标记x。如果恰好把输入符号串的所有符号都做了标记，说明左端的符号a和右端的符号b的个数相等；否则，说明左端的符号a和右端的符号b的个数不相等，或者符号a和b交替出现。,用图灵模型来计算,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),程序,假定n2，输入符号串aabb,用图灵模型来计算,控制器,工作带,B a a b b B,读写头,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,字母表：a,b,B,用图灵模型来计算,控制器,工作带,B a a b b B,读写头扫描到符号a，则继续往右走,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B a a b b B,读写头扫描到符号a，则继续往右走,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B a a b b B,读写头扫描到符号b，将当前单元写入字符x，并使读写头往左走，转移到状态q1。,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B a a x b B,读写头扫描到符号b，将当前单元写入字符x，并使读写头往左走，转移到状态q1。,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B a a x b B,读写头扫描到符号a，则把a改为标记x，并使读写头往右走，转移到状态q2,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B a x x b B,读写头扫描到符号a，则把a改为标记x，并使读写头往右走，转移到状态q2,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B a x x b B,读写头扫描到标记x，则继续往右走,(q2,b x L q1)(q2,B B L q3)(q3,x x L q3)(q3,a a H qN)(q3,B B H q4),读写头,程序,用图灵模型来计算,控制器,工作带,B a x x b B,若读写头扫描到符号b，则把b改为标记x，并使读写头往左走，转移到状态q1,读写头,程序,用图灵模型来计算,控制器,工作带,B a x x x B,若读写头扫描到符号b，则把b改为标记x，并使读写头往左走，转移到状态q1,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B a x x x B,读写头扫描到标记x，则继续往左走,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B a x x x B,读写头扫描到符号a，则把a改为标记x，并使读写头往右走，转移到状态q2；,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x B,读写头扫描到标记x，则继续往右走,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x B,读写头扫描到标记x，则继续往右走,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x B,读写头扫描到标记x，则继续往右走,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x B,读写头扫描到空白符B，说明符号b已处理完毕，则把状态改为q3，并使读写头往左走,(q2,b x L q1)(q2,B B L q3)(q3,x x L q3)(q3,a a H qN)(q3,B B H q4),读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x B,读写头扫描到空白符B，说明符号b已处理完毕，则把状态改为q3，并使读写头往左走,(q2,b x L q1)(q2,B B L q3)(q3,x x L q3)(q3,a a H qN)(q3,B B H q4),读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x B,读写头扫描到标记x，则继续往左走,(q2,b x L q1)(q2,B B L q3)(q3,x x L q3)(q3,a a H qN)(q3,B B H q4),读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x B,读写头扫描到标记x，则继续往左走,(q2,b x L q1)(q2,B B L q3)(q3,x x L q3)(q3,a a H qN)(q3,B B H q4),读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x B,读写头扫描到标记x，则继续往左走,(q2,b x L q1)(q2,B B L q3)(q3,x x L q3)(q3,a a H qN)(q3,B B H q4),读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x B,读写头扫描到空白符B，说明符号a和b已成对标记，转移到状态q4，达到接受状态。,(q2,b x L q1)(q2,B B L q3)(q3,x x L q3)(q3,a a H qN)(q3,B B H q4),从图灵机我们看到了什么？,图灵机在一定程度上反映了人类最基本的、最原始的计算能力，它的基本动作非常简单、机械、确定。因此，有条件用真正的机器来实现图灵机。程序并非必须顺序执行，指令中关于下一状态的指定，实际上表明指令可以不按程序中所表示的顺序执行。这意味着，虽然程序只能按线性顺序来表示指令序列，但程序的实际执行可以与表示的顺序不同。计算的对象、中间结果和最终结果都在带上，程序则在控制器中。这意味着什么？,思考：将做一件复杂事情的过程分解成许多简单的、机械的步骤，你是否有过成功的经验？,计算机科学的研究目标是用计算机来求解人类所面临的各种问题，问题本身的内在复杂性决定了求解这个问题的算法的计算复杂性。如何判定一个问题的复杂性？如何区分一个问题是“易解”的还是“难解”的？许多情况下，问题的内在复杂性是很困难确定的，人们对许多问题至今无法确切地了解其内在的计算复杂性。,易解问题与难解问题,将多项式时间复杂性作为易解问题和难解问题的分界线。将存在多项式时间算法的问题看作是易解问题，例如排序问题、串匹配问题等。将需要指数时间算法解决的问题看作是难解问题，例如汉诺塔问题、TSP问题等。,易解问题与难解问题,计算复杂性理论有两个基本的论题：Turing论题和Cook论题，前者利用图灵机指出了哪些问题是可计算的，后者则指出在可计算的问题中，只有在多项式时间内可计算的问题才是实际可计算的。Turing论题中“有限次计算”是一个相当宽松的条件，即使需要计算几个世纪的问题，在理论上也都是可计算的。Cook论题将可计算问题进一步划分成两类，一类是实际可计算的，称为P 类问题，另一类是实际不可计算的，称为NP类问题。,P类问题与NP类问题,【定义1】设A是求解问题的一个算法，如果在算法的整个执行过程中，每一步只有一个确定的选择，则称算法A是确定性算法。【定义2】可以用多项式时间的确定性算法来判定或求解的问题称为P类问题。理解起来，确定性算法在执行过程中，每一个步骤都有一个确定的选择，如果重新用同一输入实例运行算法，所得的结果严格一致。例如我们前面介绍过的排序算法、欧几里德算法等都属于P类问题。事实上，P类问题就是易解问题。,P类问题与NP类问题,【定义3】设A是求解问题的一个算法，如果算法A以如下猜测并验证的方式工作，则称算法A是非确定性算法：（1）猜测阶段：对问题的输入实例产生一个任意字符串y，在算法的每一次运行时，串y的值可能不同，因此，猜测以一种非确定的形式工作。（2）验证阶段：用一个确定性算法验证两件事：首先，检查在猜测阶段产生的串y的形式是否合适，如果不合适，则算法停下来并得到no；另一方面，如果串y是合适的形式，那么算法验证它是否是问题的解，如果是问题的解，则算法停下来并得到yes，否则，算法停下来并得到no。,P类问题与NP类问题,【问题描述】在图G=(V,E)中，从某个顶点出发，求经过所有顶点一次且仅一次再回到出发点的回路。哈密顿回路问题的判定形式可叙述为：在图G=(V,E)中，是否有一个回路经过所有顶点一次且仅一次然后回到出发点。,非确定性算法的例子哈密顿回路问题,P类问题与NP类问题,（1）猜测阶段（不确定）：生成图中所有顶点的一个线性排列；（2）验证阶段（确定性算法）：考察这个排列是否满足 相邻顶点之间存在边；最后一个顶点和第一个顶点之间存在边。如果满足这两个条件，则算法停下来得到yes，否则算法停下来得到no。,非确定性算法的例子哈密顿回路问题,P类问题与NP类问题,【定义4】可以用多项式时间的非确定性算法来判定或求解的问题称为NP类问题。,哈密顿回路问题可以用多项式时间的非确定性算法来判定或求解，因此属于NP类问题。事实上，NP类问题是难解问题的一个子集，并不是所有难解问题都存在非确定性算法可以判定或求解，例如汉诺塔问题就不存在非确定性算法，虽然可以猜测一个移动序列，但无法在多项式时间内验证这个移动序列是否是问题的解。,P类问题与NP类问题,