6计算机学科的根本问题

1、从字源上考察：从字源上考察：计：从言从十，有数数或计数的含义；计：从言从十，有数数或计数的含义；算：从竹从具，指计算工具。算：从竹从具，指计算工具。 现代汉语词典现代汉语词典对计算的定义：对计算的定义：根据已知数通过数学方法求得未知数。根据已知数通过数学方法求得未知数。什么是计算什么是计算 直观的计算：数的加减乘除；函数的微分、积直观的计算：数的加减乘除；函数的微分、积分；微分方程的求解；定理的证明推导等等。分；微分方程的求解；定理的证明推导等等。计算的实质：从一个符号串计算的实质：从一个符号串 f（输入）得出另（输入）得出另一个符号串一个符号串 g（输出）。（输出）。数学概念数学概念 普适概

2、念普适概念什么是计算什么是计算 计算的例子计算的例子从符号串从符号串“12+3”变换成符号串变换成符号串“15”加法计加法计算算符号串符号串“x2”变换成符号串变换成符号串“2x”微分；微分； f 表示一组公理和推导规则，表示一组公理和推导规则，g 是一个定理，那么是一个定理，那么从从 f 到到 g 的一系列变换的一系列变换定理定理g的证明；的证明；符号串符号串 f 代表一个英文句子，符号串代表一个英文句子，符号串 g 为含义相为含义相同的中文句子，那么从同的中文句子，那么从 f 到到 g 的变换的变换英文翻英文翻译成中文；译成中文；这些变换有什么共同点？这些变换有什么共同点？为什么他们都叫做

3、计算？为什么他们都叫做计算？图灵与巨人计算机图灵与巨人计算机图灵模型图灵模型有限状态有限状态 控制器控制器工作带工作带 一条无限长的工作带：工作带上的每个单元可以一条无限长的工作带：工作带上的每个单元可以存放一个符号；所有允许出现的符号属于一个预先存放一个符号；所有允许出现的符号属于一个预先规定好的字母表。规定好的字母表。 图灵模型图灵模型有限状态有限状态 控制器控制器工作带工作带 一个读写头：读写头可以左移一个单元、右移一一个读写头：读写头可以左移一个单元、右移一个单元或者保持不动。个单元或者保持不动。图灵模型图灵模型有限状态有限状态 控制器控制器工作带工作带 一个控制器：控制器在每个时刻处

4、于一定的状态，一个控制器：控制器在每个时刻处于一定的状态，当读写头从工作带上读出一个符号后，控制器就根当读写头从工作带上读出一个符号后，控制器就根据这个符号和当时的机器状态，指挥读写头进行读据这个符号和当时的机器状态，指挥读写头进行读写或者移动，并决定是否改变机器状态。写或者移动，并决定是否改变机器状态。计算与可计算计算与可计算所谓计算就是计算者（人或机器）对一条可以无所谓计算就是计算者（人或机器）对一条可以无限延长的工作带上的符号串执行指令，一步一步限延长的工作带上的符号串执行指令，一步一步地改变工作带上的符号串，经过有限步骤，最后地改变工作带上的符号串，经过有限步骤，最后得到一个满足预先规

5、定的符号串的变换过程。得到一个满足预先规定的符号串的变换过程。 什么样的任务才是可计算的任务？这是计算机科什么样的任务才是可计算的任务？这是计算机科学必须要回答的一个最基本的问题。这是关系到学必须要回答的一个最基本的问题。这是关系到计算机能做什么、不能做什么的根本问题。计算机能做什么、不能做什么的根本问题。类比：类比：什么样的衣服才是洗衣机可洗的？什么样的衣服才是洗衣机可洗的？构造一个识别符号串构造一个识别符号串anbn（n1）的图灵机）的图灵机基本思想：使读写头往返移动，每往返移动一基本思想：使读写头往返移动，每往返移动一次，就成对地对输入符号串次，就成对地对输入符号串左端的一个左端的一个a

6、和右和右端的一个端的一个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，输入符号串，输

7、入符号串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)读写头读写头程序程序字母表：字母表：a, b, b用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带b a a b b b读写头扫描到符号读写头扫描到符号

8、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)读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带

9、工作带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 q

10、0) (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)读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制

11、制器器工作带工作带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

12、 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

13、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，并使读写头往右走，并使读写头往右走，

14、转移到状态转移到状态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)读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工

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 x r q2)读写头读写头

16、程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带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，并使读写头往左走

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读写头扫描到标记读写头扫描到标记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，则继

18、续往左走则继续往左走 (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读写头扫描到空白符读写头扫描到空白符

19、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) 图灵机在一定程度上反映了人类最基本的、最原始的图灵机在一定程度上反映了人类最基本的、最原始的计算能力，它的基本动作非常简单、机械、确定。因计算能力，它的基本动作非常简单、机械、确定。因此，有条件用真正的机器来实现图灵机。此，有条件用真正的机器来实现图灵机。 程序并非必须顺序执行，指令中关于下一状态的指定，程序并非必须顺序执行，指令中关于下一状态的

20、指定，实际上表明指令可以不按程序中所表示的顺序执行。实际上表明指令可以不按程序中所表示的顺序执行。这意味着，虽然程序只能按线性顺序来表示指令序列，这意味着，虽然程序只能按线性顺序来表示指令序列，但程序的实际执行可以与表示的顺序不同。但程序的实际执行可以与表示的顺序不同。 计算的对象、中间结果和最终结果都在带上，程序则计算的对象、中间结果和最终结果都在带上，程序则在控制器中。这意味着什么？在控制器中。这意味着什么？思考：思考：将做一件复杂事情的过程分解成许多简将做一件复杂事情的过程分解成许多简单的、机械的步骤，你是否有过成功的经验？单的、机械的步骤，你是否有过成功的经验？ 计算机科学的研究目标是

21、用计算机来求解人类所面临的各计算机科学的研究目标是用计算机来求解人类所面临的各种问题，问题本身的内在复杂性决定了求解这个问题的算法种问题，问题本身的内在复杂性决定了求解这个问题的算法的计算复杂性。的计算复杂性。 如何判定一个如何判定一个问题的复杂性问题的复杂性？ 如何区分一个问题是如何区分一个问题是“易解易解”的还是的还是“难解难解”的？的？ 许多情况下，问题的内在复杂性是很困难确定的，人们对许多情况下，问题的内在复杂性是很困难确定的，人们对许多问题至今无法确切地了解其内在的计算复杂性。许多问题至今无法确切地了解其内在的计算复杂性。 将多项式时间复杂性作为易解问题和难解问题的分界线将多项式时间

22、复杂性作为易解问题和难解问题的分界线。 将存在将存在多项式时间多项式时间算法的问题看作是易解问题，例如排序算法的问题看作是易解问题，例如排序问题、串匹配问题等。问题、串匹配问题等。 将需要将需要指数时间指数时间算法解决的问题看作是难解问题，例如汉算法解决的问题看作是难解问题，例如汉诺塔问题、诺塔问题、tsp问题等问题等 。 计算复杂性理论有两个基本的论题：计算复杂性理论有两个基本的论题：turing论题和论题和cook论论题，前者利用图灵机指出了哪些问题是可计算的，后者则指题，前者利用图灵机指出了哪些问题是可计算的，后者则指出在出在可计算可计算的问题中，只有在多项式时间内可计算的问题才的问题中

23、，只有在多项式时间内可计算的问题才是是实际可计算实际可计算的。的。 turing论题中论题中“有限次计算有限次计算”是一个相当宽松的条件，即是一个相当宽松的条件，即使需要计算几个世纪的问题，在使需要计算几个世纪的问题，在理论上也都是可计算理论上也都是可计算的。的。 cook论题将可计算问题进一步划分成两类，一类是论题将可计算问题进一步划分成两类，一类是实际可实际可计算计算的，称为的，称为p 类问题，另一类是实际不可计算的，称为类问题，另一类是实际不可计算的，称为np类问题。类问题。【定义【定义1】 设设a是求解问题是求解问题的一个算法，如果在算法的整个的一个算法，如果在算法的整个执行过程中，每

24、一步只有一个确定的选择，则称算法执行过程中，每一步只有一个确定的选择，则称算法a是确是确定性算法。定性算法。【定义【定义2】可以用多项式时间的确定性算法来判定或求解的可以用多项式时间的确定性算法来判定或求解的问题称为问题称为p类问题。类问题。 理解起来，确定性算法在执行过程中，每一个步骤都有理解起来，确定性算法在执行过程中，每一个步骤都有一个确定的选择，如果重新用同一输入实例运行算法，所得一个确定的选择，如果重新用同一输入实例运行算法，所得的结果严格一致。例如我们前面介绍过的排序算法、欧几里的结果严格一致。例如我们前面介绍过的排序算法、欧几里德算法等都属于德算法等都属于p类问题。事实上，类问题

25、。事实上，p类问题就是易解问题。类问题就是易解问题。【定义【定义3】 设设a是求解问题是求解问题的一个算法，如果算法的一个算法，如果算法a以如下以如下猜测并验证的方式工作，则称算法猜测并验证的方式工作，则称算法a是非确定性算法：是非确定性算法：（1）猜测阶段：对问题的输入实例产生一个任意字符串）猜测阶段：对问题的输入实例产生一个任意字符串y，在算法的每一次运行时，串在算法的每一次运行时，串y的值可能不同，因此，猜测以的值可能不同，因此，猜测以一种非确定的形式工作。一种非确定的形式工作。（2）验证阶段：用一个确定性算法验证两件事：首先，检）验证阶段：用一个确定性算法验证两件事：首先，检查在猜测阶段产生的串查在猜测阶段产生的串y的形式是否合适，如果不合适，则的形式是否合适，如果不合适，则算法停下来并得到算法停下来并得到no；另一方面，如果串；另一方面，如果串y是合适的形式，是合适的形式，那么算法验证它是否是问题的解，如果是问题的解，则算法那么算法验证它是否是问题的解，如果是问题的解，则算法停下来并得到停下来并得到yes，否则，算法停下来并得到，