图灵机模型一个图灵机 T 包括 : 一个有穷状态转换系统, 也称控制器 ; 一条两端无穷包含无穷多个格子的存储带, 每个格里可以存一个符号 ; 一个读写头, 每时刻定位于某存储格 ; 执行 : 控制器以存储带的 ( 读写头所指 ) 当前符号为输入做状态转换, 可能将一个符号写入当前格, 并可能令

Size: px

Start display at page:

Download "图灵机模型一个图灵机 T 包括 : 一个有穷状态转换系统, 也称控制器 ; 一条两端无穷包含无穷多个格子的存储带, 每个格里可以存一个符号 ; 一个读写头, 每时刻定位于某存储格 ; 执行 : 控制器以存储带的 ( 读写头所指 ) 当前符号为输入做状态转换, 可能将一个符号写入当前格, 并可能令"

硬却
5 years ago
Views:

1 计算机基本原理通用电子数字计算机 (General - Purpose Electronic Digital Computer) 其中 : 通用 : 通用设备, 能完成各种 ( 信息处理 ) 工作电子 : 计算机硬件实现的物理基础, 计算机的活动最终通过电子电路中的电流电位等实现数字化 : 信息表示方式一切信息, 无论原为数值文字图形声音等, 都统一到二进制的数字化表示上数字化是计算机的基本特征, 是通用性的基础计算机 : 做计算的机器计算机能做的基本动作如加减乘除等, 非常简单但它可根据程序瞬间完成数以万亿计的动作, 因此可能在有限时间内完成大的工作我们看到的是大量动作的综合效果计算机基本结构不很复杂, 它能按指挥行事, 做得快更重要的东西是程序软件, 每个程序都是特殊的, 是针对具体需要专门实现的电脑木手铁脚? 信息处理的普适性, 远不能与人脑相比有穷状态转换系统有穷状态转换系统 M = <S, A, h, s 0, F>; ( 一种简单计算模型 ) S 是 M 的有穷状态集, 初始状态 s 0 S, 结束状态 F S M 总处在某个状态, 开始时在 s 0 ; A 是有穷符号集,h : S A S (A { _ }) 是转换函数 ( 部分函数 ),_ 表示无输出若 M 在状态 s 接到输入 a A, 假设 h(s, a) = <s', b>, (s' S, b A),M 就转到状态 s' 并产生输出 b 当 M 能将输入序列 I 用完并且达到某结束状态, 则说 M 对 I 成功结束, 否则为失败若 M 对 I 成功结束且输出序列为 O, 则记 M(I) = O 转换图有穷状态转换系统的一种直观表示方法每个状态用一个小圆圈表示 ; 若 M 在状态 s1 遇到输入 a 时应转到状态 s2 并输出 b(h(s1, a) = <s2, b>) 时, 就画一条从状态 s1 到状态 s2 的弧线, 并在线上标出 (a, b); s1 (a, b) s2 完成除 2 的有穷状态转换系统 s1 是初始状态, 终止状态集 {s1, s2}; 它在输入 n 个 a 时输出 n/2 个 a( 除 2 ) 定义一个有穷状态转换系统, 它成功结束当且仅当读入了 k 个的 abc(k = 0,1,...) 输入字符集 :{a, b, c} 状态 s1, s2, s3 初始状态 s1 终止状态 :{s1} s1 (a, _) s2 状态转换图 : s1 (a, _) s2 (a, a) (c, _) (b, _) s3

2 图灵机模型一个图灵机 T 包括 : 一个有穷状态转换系统, 也称控制器 ; 一条两端无穷包含无穷多个格子的存储带, 每个格里可以存一个符号 ; 一个读写头, 每时刻定位于某存储格 ; 执行 : 控制器以存储带的 ( 读写头所指 ) 当前符号为输入做状态转换, 可能将一个符号写入当前格, 并可能令读写头左 / 右移一位置结束 : 有许多等价定义方式图灵机的图示有穷状态控制器初始时存储带上的符号序列是输入 I; 运行结束时存储带上的符号序列是输出 O; 图灵机 T 实现的计算就是 T(I) = O ( 从符号序列到符号序列的函数 ) 通用图灵机带字符集至少包含两个符号 ; 确定一种编码方式 c, 使每台图灵机 T 对应于符号序列 c(t),t 的编码通用图灵机 G 是一台图灵机, 对任意图灵机 T 和输入序列 I, 如果 T(I) = O, 那么有 : G(c(T) ^ I) = O c(t) ^ I 表示将 c(t) 和 I 并置在输入带上通用图灵机可以实现任意图灵机的功能通用图灵机放在 G 的存储带上的 c(t) 就是指挥 G 如何工作的程序 ; G 的活动就是按程序 c(t) 工作 ( 模拟图灵机 T), 处理输入 I, 最终得到输出 O 图灵还得到另一个深刻结论 : 存在着不可计算的函数这意味着计算机不是万能的! 状态转换与计算一个计算过程可以看作是一个状态转换序列一个计算从某个状态 s 0 开始, 输入可以看作是这个状态的一部分计算过程形成一个状态序列 : s 0, s 1, s 2, s 3, s n,... 如果计算经过 n 步结束, 所需要的输出包含于最终的状态里存在着永不终止的计算可计算性理论研究计算的模型 ( 人们还定义了一些不同于图灵机的计算模型 ) 和可计算性计算复杂性理论研究一个或者一类计算所历经的状态转换次数因为实际的计算步骤需要花时间程序理论在通用计算机制 ( 如通用图灵机 ) 基础上, 完成具体计算只需给出程序程序理论研究程序的描述规律和程序的意义

3 现实的计算机现实的电子数字计算机是用超大规模集成电路 (VLSI) 和其他元器件构造起来的一种复杂电子设备它可以看成是图灵机的一种实现现实的计算机由一些部分构成 : 输入设备键盘鼠标器输入中央处理部件控制器 CPU 运算器主存储器输出输出设备显示器打印机辅助 ( 外部 ) 存储设备输出输入磁盘机磁带机光盘机等计算机主要部件 CPU( 中央处理器 ) 负责处理信息, 由控制器和运算器组成控制器解释指令 ( 脑 ), 运算器执行指令 ( 手 ) 主存储器又称内存, 用于存储计算机运行时用的程序和数据对应于图灵机存储带外部存储器 ( 外存 ) 保存备用信息 : 备用程序与数据需要时可装入内存使用各种输入输出设备实现计算机与外部的信息交换与人其他计算机系统或者设备 CPU 与存储程序原理对应于通用图灵机的控制器是核心处理部件, 用集成电路技术制造结构非常复杂, 包含数以百万千万计的元件能执行一组操作 : 取数据, 由几个数据算出一个结果 ( 加减乘除等 ), 送出数据等每个动作对应一条指令,CPU 按指令动作程序是一系列指令, 指挥 CPU 完成许多动作问题 : 指令从何而来? ENIAC: 程序由插板等表示 ( 硬件 ), 速度受限, 换程序很困难冯诺依曼提出存储程序原理, 为现代意义的计算机结构奠定了基础原来存储器里只保存数据,CPU 执行指令时由存储器取数据, 计算结果存回存储器冯诺依曼的方案 : 把程序也存入存储器, 由 CPU 自动提取指令并执行, 循环工作计算机摆脱了外界拖累, 以自己的速度 ( 电子电路的速度 ) 自动运行按此原理造的计算机称为存储程序计算机 ( 冯诺依曼计算机 ) 到目前为止, 所有主流计算机都是这种计算机计算机运行是两步循环,CPU 基本循环每次从存储器取出要下一条指令, 然后按指令完成动作循环到程序完成 ( 遇到停止指令 ), 或永取指令执行指令远运行下去图 CPU 基本执行循环

4 CPU 绝对服从指挥, 严格按照指令工作一个 CPU 的指令一般只有几十到一二百种实际领域里的需要千差万别错综复杂计算机怎么能满足所有的计算需要呢? 答案 : 通过程序通过指令的不同排列, 能够写出的程序是无穷的类似于数字和数, 汉字和中文文章的关系程序对应于 ( 通用图灵机存储带上 ) 的特定图灵机的编码, 指挥计算机完成特定计算计算机的工作原理带来两方面优势 : 通用性 : 不多几种计算机就能满足社会需要采用大工业生产方式, 提高性能, 减低成本专用性 : 在运行不同的程序时, 一台计算机将表现为不同专用信息处理机, 如计算器文字处理器记事本资料浏览检索机帐目处理机游戏机等等甚至可以同时表现为多种信息处理机 ( 只要同时运行多个不同程序 ) 这种通用性和专用性的完美统一, 使计算机成为人类走向信息时代的过程中最锐利的武器 CPU 原理不复杂而最先进的 CPU 却极端复杂, 是有史以来人制造的最复杂产品原因 : 1, 需要计算机完成的工作日趋复杂, 需要用更多指令才能完成执行指令需要时间 ( 本质弱点 ), 要求更高性能的 CPU 提高 CPU 速度依赖于复杂技术, 也大大增加 CPU 的复杂性 2, 早期计算机主要处理数值, 指令种类较少今天广泛用于其他信息形式的处理理论上说 CPU 可以不变 ( 只要写程序 ) 但增加些新指令可能提高效率这也增加了 CPU 的复杂性过去常见到说计算机经历了电子管晶体管集成电路和大规模集成电路 4 个阶段, 称为第代计算机这种分类已经没有价值电子器件改变不是根本性的 ( 虽然很有意义 : 降低成本减小体积等 ), 是探索计算机制造方式和工艺的过程, 历经二十余年人们一直在研究真正新型的计算机提出的有 : 光计算机量子计算机生物计算机等从本质上与今天计算机不同的信息处理工具会出现吗? 能取代目前流行的这种电子计算机吗? 我们拭目以待数字化图灵理论的一个基本要求是所有信息都可用符号编码, 包括图灵机本身用计算机处理信息, 需要 : 在计算机里存储和处理信息 : 就要求确定信息在计算机内部的表示方式, 将信息送给计算机, 并能取得处理结果 : 能完成外部信息和计算机内部信息间的转换实际需要处理的信息丰富多彩, 怎么办? 计算机处理信息的基础是数字化, 为此需要 : 为数值确定一种计算机内部的表示方式 ; 一切信息都用数字表示, 以便用计算机处理信息的数字化形式也称为信息的编码万物皆为数在自然界不真, 在计算机里成立问题 : 怎样数字化? 怎样编码?

5 数制以进制方式表示数是人类的重要智力发明任何十进制数 X 都可以表示为 : X=k n *10 n + + k 0 *10 0 +k -1 * k -m *10 -m 基数为 10, 系数 / 数字 k i Œ{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 例 : (10) = 数的进制 : 手指 / 十进制, 电子元件 / 二进制进制形式只是数值的表示形式数的常见形式 : 二进制, 八进制, 十进制, 十二进制, 十六进制, 六十进制计算机中用二进制数表示数值原因 : 理论 : 两个符号的序列能有效表示复杂信息 ( 一进制表达效率低, 表达能力不够 ) 实际 : 常规器件容易表示两种不同状态一个器件表示一个基本数据单位, 其状态可看成一位二进制数字 ; 一系列器件的状态可以看成一个二进制数, 可以表示复杂的数据二进制位 :bit(binary Digit),b / 位 / 比特 8 位二进制数 :Byte,B/ 字节存储量 / 数据量 :1KB = 1024B 1MB = 1024KB 1GB = 1024MB 1TB = 1024GB 二进制一般形式 : B = k n *2 n + + k 0 *2 0 +k -1 * k -m *2 -m 基数为 2, 系数 ( 数字 ) 属于 {0, 1} (2) = 1*2 5 +1*2 4 +0*2 3 +1*2 2 +1*2 1 +0*2 0 = = 54 (10) 运算规则 ( 加法和乘法 ): 0+0=0 0+1=1 1+0=1 1+1=10( 有进位 ) 0*0=0 0*1=0 1*0=0 1*1=1 二进制与八十六进制的对照 ( 转换 ) 二进制与八进制的对照 : 二进制与十六进制的对照 : 常用 A, B, C, D, E, F 作为数字表示 10 到 15 二进制与十进制之间的转换二进制到十进制的转换可直接使用二进制数的计值公式完成十进制到二进制的转换 : 整数 : 一般采用除余法, 反复整除 2, 收集起各次除法的余数小数 : 采用乘法, 反复乘 2, 收集并去掉整数位 ( 注意 : 有限位精度的十进制小数可能无法用有限位二进制小数精确表示 ) 包含整数和小数部分时, 两部分别计算二进制表示范围二进制数位数与整数表示范围的关系 : 位数 n 范围 0~1 0~7 0~255 0~ ~ 2 n -1 计算机里常用固定位数的方式表示整数 : 16 位 :0 ~ 位 :0 ~ ( 约 40 亿 ) 64 位 :0 ~ ( 约 1600 亿亿 ) 近似公式 : 2 10 =

数的符号与负数表示负数的符号也需要编码 ( 用固定位数编码 ) 通常以最高位表示符号, 其余位表示值为方便加减运算, 计算机中的有符号数一般用模 2 补码形式表示 k 位二进制数表示 : 正数 n 用原编码, 负数 -n 用 n 的编码 N 的补码 N ~, 满足 N + N ~ =2 k 求负数 -n 补码的方法 : 求出 n 的编码后各二进制位求反, 结果再加 1( 注意进位 )

6 数的符号与负数表示负数的符号也需要编码 ( 用固定位数编码 ) 通常以最高位表示符号, 其余位表示值为方便加减运算, 计算机中的有符号数一般用模 2 补码形式表示 k 位二进制数表示 : 正数 n 用原编码, 负数 -n 用 n 的编码 N 的补码 N ~, 满足 N + N ~ =2 k 求负数 -n 补码的方法 : 求出 n 的编码后各二进制位求反, 结果再加 1( 注意进位 ) 有符号数的表示范围用 n 位二进制数表示有符号整数, 范围 : 位数 8 16 n 范围 -128~ ~ n-1 ~ 2 n-1-1 计算机中常见的有符号整数及其表示范围 : 16 位 : ~ 位 :-2 31 ~ ( 约 -20 亿到 20 亿 ) 64 位 : ~ 小数与实数的编码科学记数法 :X = ±0.nnn 10 ±mm,nnn 尾数,mm 指数浮点编码方式浮点编码中尾数和指数都采用带符号的二进制数表示,X = ±0.BBB 2 ±bb 常见表示 (IEEE 754 标准 ) 单精度 :32 位,8 位指数 ( 表示 127~127),23 位尾数,1 个符号位范围约 ± (10-38 ~ ), 大约 7 位 10 进制有效数字双精度 :64 位, 11 位指数,52 位尾数, 表示范围约为 ± ( ~ ),16 到 17 位 10 进制有效数字浮点数实例 (IEEE 754 单精度数 ): 共计 32 位 s 符号 e 指数 ( 带符号数 ) 所表示的数 :s 1.f 2 e f 尾数文字信息的编码 ASCII 编码表文字信息是字符的序列, 基于字符编码字符集 : 计算机上可用的基本字符集合基本方式 : 把所有字符排一个顺序, 用各个字符的顺序编号作为编码 ( 是整数 ) 标准字符集 : 人们为交换信息而定义的字符编码标准如 ASCII 字符集是最常用 7 位字符集, 包含十进制数字字符英文大小写字母常用标点符号及一些特殊控制字符 ( 系统用 ) 字符常用一个字节编码 H 表示高位,L 表示低位编码 0~31 为控制字符,SP 是空格

中文编码与国际码中文字符 ( 中文字 ) 编码也存在几个编码标准 (GB,Big5) 中文字符数量大, 通常用两个字节编码一个字 ( 也可以用更多字节 ) 随着国际交流增加, 尤其是互联网, 人们迫切需要在更大范围中方便地共享信息国际码 Unicode 希望将世界各主要文字的字符统一起来, 建立一种统一的编码系统其他信息的编码, 转换

直接的图形编码将图形看成点的阵列黑白图形 :n m 个点的点阵图形需要用 n m 个二进制位编码, 每个位表示一个点的黑白状态例 : 字型编码灰度图形 : 图形里的每个点用多个位表示, 例如每个点用 8 个位表示 256 级灰度彩色图形 : 每个点用多个位表示色彩,16 色图形,256 色图形 24 位真彩色图形用 3 个字节分别表示一个点的红绿蓝

7 中文编码与国际码中文字符 ( 中文字 ) 编码也存在几个编码标准 (GB,Big5) 中文字符数量大, 通常用两个字节编码一个字 ( 也可以用更多字节 ) 随着国际交流增加, 尤其是互联网, 人们迫切需要在更大范围中方便地共享信息国际码 Unicode 希望将世界各主要文字的字符统一起来, 建立一种统一的编码系统其他信息的编码, 转换要将任何信息送进计算机处理, 只需要为它确定一种编码方式信息进入计算机, 需要从其外部形式转换后得到对应的内部形式这种转换一般由特殊硬件设备和软件合作完成例 : 字符输入转换 : 人按键盘键, 键盘硬件将产生一个表示该键字符的二进制序列数字照相机 : 将由镜头得到的光强度和色彩信息转换为一个很长的二进制序列例 : 点阵图形的编码直接的图形编码将图形看成点的阵列黑白图形 :n m 个点的点阵图形需要用 n m 个二进制位编码, 每个位表示一个点的黑白状态例 : 字型编码灰度图形 : 图形里的每个点用多个位表示, 例如每个点用 8 个位表示 256 级灰度彩色图形 : 每个点用多个位表示色彩,16 色图形,256 色图形 24 位真彩色图形用 3 个字节分别表示一个点的红绿蓝 (RGB) 色度的中文字型 ( 需要用 32 个字节表示 ) 程序的编码计算机中另一类最重要的信息是程序机器语言程序是机器指令序列指令编码的基础 : 内存存储单元顺序编号, 从 0 开始, 称为内存地址指令中要用某单元的数据时, 只需要给出数据的地址每种指令用一个数表示, 称为指令字指令字通常用固定位数的二进制码表示存取数据指令和运算指令给出数据的地址, 控制转移需指定转移目标地址

8 计算机的学习和使用计算机的使用了解微型机的基本部分和各部分的作用了解计算机的基本使用过程鼠标器和键盘基本使用方法和技能 ( 键盘输入 ) 与图形用户界面交互的基本方式一般文本编辑技术文件的使用和计算机磁盘信息管理常见计算机外部设备及其使用日常维护 ( 例如鼠标器等 ), 软件安装计算机网络 : 浏览电子邮件和网络信息发掘等文字处理系统的使用所见即所得的文字处理系统, 如 WORD 数学工作者和其他科学工作者使用最广泛的文字处理系统 :LATEX 基本程序设计技术和程序设计语言常用科学计算软件, 如 Maple,Mathematica, Matlab 等 ( 应该学习一种两种 ) 其他常用软件 ( 图形图像声音处理等 ) 学会使用软件系统的帮助系统, 学会阅读软件的说明书 ( 手册 ), 学会学习新的软件了解信息社会带来的新问题和挑战了解计算机安全问题和一般性的信息安全问题了解网络攻击的危险性了解计算机病毒防范和处理了解保证自己的信息安全的基本原则和基本技术了解计算机系统的可靠性问题软件产品质量目前, 软件产品的质量有很大问题以微软 Windows98 用户协议书为例, 其中说公司保证本软件产品自交货后九十日内大致符合随附书面材料所述的功能, 无论使用中出了什么问题, 其责任只是下述两者之一 (a) 退还你的全部货款 (b) 修正或更换不符合... 的软件产品而且该公司绝不就因使用或不能使用本软件产品所发生的其他损害... 负赔偿责任,... 不论任何情况,... 应付的责任总额, 以您就软件产品所实际已经支付的价款为限上机安排 (2 月 24 日开始, 每周二晚 7 点 ~9 点 ) 2003 级学号 : 4 号机房 ( 学号最后 3 位对应机器号 ) 2003 级学号 : 5 号机房 ( 学号最后 3 位对应机器号 ) 2003 级学号 137 以上和其他同学 : 6 号机房 ( 按学号, 其余同学另排 ) == 上机作业内容在课程主页上 ==

C. 大规模集成电路 D. 晶体管参考答案 B 8. 采用超大规模集成电路的计算机是计算机发展中的 A. 第 4 代 B. 第 3 代 C. 第 2 代 D. 第 1 代参考答案 A 9. 当前的计算机一般被认为是第四代计算机, 它所采用的逻辑元件是 A. 晶体管 B. 集成电路 C. 电子管

C. 大规模集成电路 D. 晶体管参考答案 B 8. 采用超大规模集成电路的计算机是计算机发展中的 A. 第 4 代 B. 第 3 代 C. 第 2 代 D. 第 1 代参考答案 A 9. 当前的计算机一般被认为是第四代计算机, 它所采用的逻辑元件是 A. 晶体管 B. 集成电路 C. 电子管计算机基础知识 1 1. 自计算机问世至今已经经历了四个时代, 划分时代的主要依据是计算机的 A. 规模 B. 功能 C. 性能 D. 构成元件参考答案 D 2. 一般认为, 世界上第一台电子数字计算机诞生于 A.1946 年 B.1952 年 C.1959 年 D.1962 年参考答案 A 3. 世界上第一台电子数字计算机采用的电子器件是 A. 大规模集成电路 B. 集成电路 C. 晶体管 D.