[理学]计算机导论：计算机模型和算法.ppt

计算机导论(Introduction to Computers) 计算模型和算法 控制器 程序 用图灵机来进行计算 例2： 1 1 1 1 1 1 1 读写头 1 当前机器状态：q2 带 q1 q2 q3 q1 q2 q3 1 1 1 b b b 1 1 b 1 b b R R H R L H q1 q2 q3 q2 q3 q3 控制器 程序 用图灵机来进行计算 例2： 1 1 1 1 1 1 1 读写头 1 当前机器状态：q2 带 q1 q2 q3 q1 q2 q3 1 1 1 b b b 1 1 b 1 b b R R H R L H q1 q2 q3 q2 q3 q3 控制器 程序 用图灵机来进行计算 例2： 1 1 1 1 1 1 1 读写头 1 当前机器状态：q2 带 q1 q2 q3 q1 q2 q3 1 1 1 b b b 1 1 b 1 b b R R H R L H q1 q2 q3 q2 q3 q3 控制器 程序 用图灵机来进行计算 例2： 1 1 1 1 1 1 1 读写头 1 当前机器状态：q2 带 q1 q2 q3 q1 q2 q3 1 1 1 b b b 1 1 b 1 b b R R H R L H q1 q2 q3 q2 q3 q3 控制器 程序 用图灵机来进行计算 例2： 读写头 1 1 1 1 1 1 1 1 当前机器状态：q3 带 q1 q2 q3 q1 q2 q3 1 1 1 b b b 1 1 b 1 b b R R H R L H q1 q2 q3 q2 q3 q3 控制器 程序 用图灵机来进行计算 例2： 1 1 1 1 1 1 读写头 1 当前机器状态：q3 带 q1 q2 q3 q1 q2 q3 1 1 1 b b b 1 1 b 1 b b R R H R L H q1 q2 q3 q2 q3 q3 我们还看到了什么？ 计算的对象、中间结果和最终结果都在带上，程序则在控制器中。这意味着什么？ 如果把这样的图灵机做成一台计算机，由于程序是固定的，那么这样的计算机就只能完成规则固定的计算（但输入可以多样化），因此是一台专用计算机。 于是想到，把计算用的程序也放在带上，而控制器中的程序能够从带上把计算用的程序中的指令逐条地读进来，再按照其要求进行计算（这个过程叫做解释（Interpretation），以后的《计算机组成原理》和《编译原理》等课程中会学到）。 具有这种能力的图灵机叫做通用图灵机。 这就是 von Neumann 体系结构的基本思想。 对图灵机例子的进一步分析 在刚才那个例子中，字母表是 { 1, b }，其中符号 b（空白（Blank），在计算机领域中通常叫空格）的作用是什么？ 它是被加数、加数、和的边界符号，表示着计算对象和计算结果的边界。 因此，真正用来表示被加数、加数与和的数值的，只有符号 1。 那么，数值 1,000,000 就应当由一百万个 1 来表示。读入这一个数，读写头就要移动一百万次。 在设计真正的计算机时，这显然是不合理、不实际的。 对图灵机例子的进一步分析 如果这个字母表中一共有11个符号： { 0, 1, …, 9, b }，那么就可以用十进制来表示数值。 但是，这时的程序要长得多。 确定当前指令自然要花更多的时间。 q1 q1 q2 q2 q3 q3 1 b 1 b 1 b 1 1 1 b b b R R R L H H q1 q2 q2 q3 q3 q3 q1 0 0 R q1 q1 1 1 R q1 … … q1 9 9 R q1 … … q3 b b H q3 读被加数 如果是通用图灵机，还会付出什么代价？（请大家自己思考） 控制器 程序 例3： 1 0 9 0 读写头 当前机器状态：q1 带 对图灵机例子的进一步分析 q1 0 0 R q1 q1 1 1 R q1 … … q1 9 9 R q1 … … 字 母 表： { 0, 1, …, 9, b } 机器状态： { q1, q2, q3, … } 北京语言大学 信息科学学院 计算机导论 - Introduction to Computers 北京语言大学 信息科学学院 北京语言大学 信息科学学院 徐燕 这次课的主要内容 什么是计算与可计算？ 计算模型 算法思想 什么是计算与可计算？ 什么是计算（Computing）？ 直观的计算：数的加减乘除；函数的微分、积分；微分方程的求解；定理的证明推导；等等。 计算的实质：从一个符号序列 A（输入）得出另一个符号序列 B（输出）。 计算的例子： A：1