第1章图灵机模型及数据编码.ppt
《第1章图灵机模型及数据编码.ppt》由会员分享,可在线阅读,更多相关《第1章图灵机模型及数据编码.ppt(56页珍藏版)》请在三一文库上搜索。
1、第1章 图灵机模型及数据编码,图灵机模型理论是计算学科最核心的理论之一 图灵机模型为计算机设计指明了方向 图灵机模型是算法分析和程序语言设计的基础理论。,本章主要内容,1.1 图灵机 1.2 位的存储 1.3 存储器 1.4 数据在计算机中的表示 1.5 数据压缩 1.6 数据传输误码及对策,图灵机的直观描述,3个部件:有穷控制器、无穷带和读写头 3个动作:改写当前格、左移或右移一格,图灵机的形式化描述,图灵机是一个五元组(K,s,H),其中: K 是有穷个状态的集合; 是字母表,即符号的集合; s K是初始状态; HK 是停机状态的集合,当控制器内部状态为停机状态时图灵机结束计算; 是转移函
2、数,即控制器的规则集合。,计算“x+1”的图灵机,目标:利用二进制来设计一个专门计算“x+1”的图灵机,要求计算完成时,读写头要回归原位 状态集合K:start,add,carry,noncarry,overflow,return,halt; 字母表:0,1,*; 初始状态s:start; 停机状态集合H:halt;,计算“x+1”的图灵机,规则集合:,“51”的计算过程(1),“51”的计算过程(2),“51”的计算过程(3),“51”的计算过程(4),通用图灵机(1),编码方案:,通用图灵机(2),通用图灵机蕴含的计算思想,“x+1”图灵机功能是固定的,相当于一个程序 通用的图灵机功能根据
3、输入编码的不同而变化 程序也是数据 存储程序和程序控制 通用图灵机模型是计算机的计算能力的极限 计算机系统应该有存储器(相当于存储带)、中央处理器(控制器及其状态),并且其字母表可以仅有0和1两个符号;为了能将数据保存到存储器并将计算结果从存储器送出来展示给用户,计算机系统还应该有输入设备和输出设备如键盘、鼠标、显示器和打印机等。,1.2 位的存储,如果用0-1作为编码的基本元素的话,那么存储的最小单位为1位(bit),要么是0要么是1。可见只要存储装置有两种不同的稳定状态就能可以表示和存储这两个元素,其中一个状态表示1,则另一种状态就表示0,逻辑运算,门,可以设计出进行逻辑运算的装置,比如用
4、继电器或者齿轮等,把这种能完成逻辑运算的装置称为门(Gate)。现代电子计算机中的门是用电子线路实现的,其中1和0分别用电平的高和低来表示。,触发器,其他存储技术,磁芯 电容 磁介质 有机玻璃或聚酯树酯等材料制作的介质,1.3 存储器,1 Byte 8 Bit 1 KB(kilobyte) 1024 Byte 1 MB(megabyte) 1024 KB 1 GB(gigabyte) 1024 MB 1 TB(terabyte) 1024 GB,存储器,主存储器 地址 辅助存储器 软盘、硬盘和光盘等,1.4 数据在计算机中的表示,二进制 数值的表示 字符的表示 图形和图象的表示 音频数据的表示
5、,数制,进位计数的方法即数制 在采用进位计数的数字系统中,如果只用r个数码,则称其为基r数制(Radix-r Number System)或 r 进制,r 便称为该数制的“基数”(Radix) 二进制:B(Binary),如 (11101)B; 八进制:O(Octal),如 (35)O; 十进制:D(Decimal),如 (29)D; 十六进制:H(Hexadecimal),如 (1D)H;,二进制与其他数制的转换(1),二进制与十进制的转换 十进制转换成二进制:将整数部分和小数部分分别转换,然后再拼接起来 整数部分,采用除2取余法; 小数部分,采用乘2取整法。 二进制转换为十进制:直接按权展
6、开即可 小数点后的权分别为2的-1、-2、-3、次幂,二进制与其他数制的转换(2),十进制转换成二进制:,二进制与其他数制的转换(3),二进制转换为十进制:,二进制与其他数制的转换(4),二进制与十六进制的转换 16124,4位二进制数刚好可以表示0F这16个数码,也就是说二进制的4位数正好可以用1位十六进制数表示 将二进制数 10110101111011.011101 转换为十六进制: (0010 1101 0111 1011.0111 0100)B(2 D 7 B.7 4)H 将十六进制数 2C1D.A1 转换为二进制: (2 C 1 D. A 1)H(0010 1100 0001 110
7、1.1010 0001)B 二进制与八进制的转换类似,数值的表示(1),机器数 把在机器内存放的正负号数码化的数称为机器数,把机器外部由正负表示的数称为真值数 若一个数占8位,真值数(0101100)B的机器数为10101100,数值的表示(2),整数和实数 整数,数值的表示(3),整数和实数 实数,数值的表示(4),若要考虑符号位的处理,则运算变得复杂:,为了解决此类问题,在机器数中,负数有三种表示法:原码、反码和补码。,数值的表示(5),原码: 数符位以0表示正1表示负,数值部分就是绝对值的二进制表示,不便于加减运算 反码: 对于正数与原码相同;对于负数,数符位为1,其数值部分为绝对值取反
8、 补码: 对于正数与原码相同;对于负数,数符位为1,其数值部分为绝对值取反最右加1,即为反码加1 可方便地实现正负数的加法运算,符号位如同数值一样参加运算,也允许产生最高位的进位,字符的表示(1),西文字符 最常用的是ASCII字符编码,即American Standard Code for Information Interchange (美国信息交换标准代码),用7位二进制编码,它可以表示27 即128个字符 EBCDIC码,即Extended Binary Coded Decimal Interchange Code(扩展的二-十进制交换码),主要用在大型机器中,采用8位二进制编码,有2
9、56个编码状态,但只选用其中一部分 存放和使用数据的软件会以其他方式保存有关类型的信息,指明这个数据是何类型,不致引起混淆,字符的表示(2),汉字编码 用户用输入码输入汉字,输入码比较容易学习和记忆;系统由输入码找到相应的内码,内码是计算机内部对汉字的表示;要在显示器上显示或在打印机上打印出用户所输入的汉字,需要汉字的字形码,系统由内码找到相应的字形码,字符的表示(3),汉字编码 汉字国标码 全称是GB231280信息交换用汉字编码字符集基本集,1980年发布,是中文信息处理的国家标准,也称汉字交换码,简称GB码。根据统计,把最常用的6763个汉字分成两级:一级汉字有3755个,按汉语拼音排列
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图灵机 模型 数据 编码
链接地址:https://www.31doc.com/p-2908440.html