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