第4章计算学科中的基本概念.ppt
《第4章计算学科中的基本概念.ppt》由会员分享,可在线阅读,更多相关《第4章计算学科中的基本概念.ppt(234页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第4章计算学科中的基本概念 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望4.1计算模型与二进制计算模型与二进制4.1.1计算模型与图灵机计算模型与图灵机计算模型与图灵机计算模型与图灵机计算模型与图灵机oo计算模型:计算模型:计算模型:计算模型:n n刻刻刻刻画画画画计计计计算算算算这这这这一一一一概概概概念念念念的的的的一一一一种种种种抽抽抽抽象象象象的的的的形形形形式式式式系系系系统统统统或或或或数数数数学学学学系统。系统。系统。系统。n n在在在在计计计计算
2、算算算科科科科学学学学中中中中,是是是是指指指指具具具具有有有有状状状状态态态态转转转转换换换换特特特特征征征征,能能能能够够够够对对对对所所所所处处处处理理理理的的的的对对对对象象象象的的的的数数数数据据据据或或或或信信信信息息息息进进进进行行行行表表表表示示示示、加加加加工工工工、变变变变化、接收、输出的数学机器。化、接收、输出的数学机器。化、接收、输出的数学机器。化、接收、输出的数学机器。oo计算模型的层次:计算模型的层次:计算模型的层次:计算模型的层次:n n计算某个(类)具体问题的计算方法;计算某个(类)具体问题的计算方法;计算某个(类)具体问题的计算方法;计算某个(类)具体问题的计
3、算方法;n n按按按按照照照照计计计计算算算算方方方方法法法法对对对对应应应应的的的的程程程程序序序序完完完完成成成成某某某某类类类类问问问问题题题题特特特特定定定定计计计计算算算算所需要的平台。所需要的平台。所需要的平台。所需要的平台。n n 在计算能力上具有某种等价性的形式系统。在计算能力上具有某种等价性的形式系统。在计算能力上具有某种等价性的形式系统。在计算能力上具有某种等价性的形式系统。n n 计算模型的模型(一切计算模型所内含的机理)计算模型的模型(一切计算模型所内含的机理)计算模型的模型(一切计算模型所内含的机理)计算模型的模型(一切计算模型所内含的机理)计算模型与图灵机计算模型与
4、图灵机计算模型与图灵机计算模型与图灵机oo图灵的观点及结论:图灵的观点及结论:n n凡凡是是能能用用算算法法方方法法解解决决的的问问题题,也也一一定定能能用用图图灵灵机机解解决决;凡凡是是图图灵灵机机解解决决不不了了的的问问题,任何算法也解决不了。题,任何算法也解决不了。oo与图灵机等价的计算模型:与图灵机等价的计算模型:n n递归函数递归函数n n-演算演算n nPOST规范系统规范系统oo图图灵灵机机是是从从过过程程这这一一角角度度来来刻刻画画计计算算的的本本质质,其其结结构构简简单单、操操作作运运算算规规则则也也较较少少,从从而而为为更多的人所理解。更多的人所理解。图灵机图灵机图灵机图灵
5、机oo图图灵灵机机由由一一条条两两端端可可无无限限延延长长的的带带子子、一一个个读写头以及一组控制读写头工作的命令组成,读写头以及一组控制读写头工作的命令组成,图灵机图灵机图灵机图灵机oo写在带子上的符号为一个有穷字母表:写在带子上的符号为一个有穷字母表:S0,S1,S2,Sp。n n可以认为这个有穷字母表仅有可以认为这个有穷字母表仅有S0、S1两个两个字符,字符,n n其中其中S0可以看作是可以看作是“0”,S1可以看作是可以看作是“1”,n n由由“0”和和“1”组成的字母表可以表示任组成的字母表可以表示任何一个数。何一个数。oo由于由于“0”和和“1”只有形式的意义,因此,只有形式的意义
6、,因此,也可以将也可以将S0改称为改称为“白白”,S1改称为改称为“黑黑”,甚至,还可以改称为甚至,还可以改称为“桌子桌子”和和“老虎老虎”,这样改称的目的在于割断与直觉的联系,并这样改称的目的在于割断与直觉的联系,并加深对布尔域中的值加深对布尔域中的值真,假真,假,以及二进制,以及二进制机器本质的理解。机器的控制状态表为:机器本质的理解。机器的控制状态表为:q1,q2,qm。n n将一个图灵机的初始状态设为将一个图灵机的初始状态设为q1,在每一在每一个具体的图灵机中还要确定一个结束状态个具体的图灵机中还要确定一个结束状态qw。一个给定机器的一个给定机器的“程序程序”oo机器内的五元组(qiS
7、jSkR(或L或N)ql)形式的指令集,五元组定义了机器在一个特定状态下读入一个特定字符时所采取的动作。5个元素的含义如下:n nqi表示机器目前所处的状态;n nSj表示机器从方格中读入的符号;n nSk表示机器用来代替Sj写入方格中的符号;n nR、L、N分别表示向右移一格、向左移一格、不移动;n nql表示下一步机器的状态。oo一个机器计算的结果是从机器停止时带子上的信一个机器计算的结果是从机器停止时带子上的信息得到的。容易看出,息得到的。容易看出,q q1 1S S2 2S S2 2RqRq3 3指令和指令和q q3 3S S3 3S S3 3LqLq1 1指令如果同时出现在机器中,当
8、机器处于状态指令如果同时出现在机器中,当机器处于状态q q1 1,第一条指令读入的是,第一条指令读入的是S S2 2,第二条指令读入的是,第二条指令读入的是S S3 3,那么机器会在两个方块之间无休止地工作。,那么机器会在两个方块之间无休止地工作。oo另外,如果另外,如果q q3 3S S2 2S S2 2RqRq4 4和和q q3 3S S2 2S S4 4LqLq6 6指令同时出现在指令同时出现在机器中,当机器处于状态机器中,当机器处于状态q q3 3并在带子上扫描到符并在带子上扫描到符号号S S2 2时,就产生了二义性的问题,机器就无法判时,就产生了二义性的问题,机器就无法判定。定。例子
9、:例子:例子:例子:oob b表示空格,表示空格,表示空格,表示空格,q q1 1表示机器的初始状态,表示机器的初始状态,表示机器的初始状态,表示机器的初始状态,q q4 4表示机器的表示机器的表示机器的表示机器的结束状态,设带子上的输入信息是结束状态,设带子上的输入信息是结束状态,设带子上的输入信息是结束状态,设带子上的输入信息是1010001010100010,读入头,读入头,读入头,读入头位对准位对准位对准位对准最右边最右边最右边最右边第一个为第一个为第一个为第一个为0 0的方格,状态为初始状态的方格,状态为初始状态的方格,状态为初始状态的方格,状态为初始状态q q1 1。规则如下:规则
10、如下:规则如下:规则如下:n nq q1 10101L L q q22q q1 11010L L q q33q q1 1 b b b b N N q q4 4n nq q2 20000L L q q22q q2 21111L L q q22q q2 2 b b b b N N q q4 4n nq q3 30101L L q q22q q3 31010L L q q33q q3 3 b b b b N N q q4 4计算结果是10100011,即对给定的数加1。以上命令计算的是这样一个函数:S(x)x1。当没有输入时,即初始状态所指的方格为空格(b)时,不改变空格符,读写头不动并停机。图灵机
11、的计算能力图灵机的计算能力图灵机的计算能力图灵机的计算能力o第一第一,把图灵机看作识别器,即判断带子上最,把图灵机看作识别器,即判断带子上最初的内容能否被图灵机所接受。假定图灵机从初的内容能否被图灵机所接受。假定图灵机从左向右扫描完带子上的内容后停机则为接受,左向右扫描完带子上的内容后停机则为接受,否则为不接受。否则为不接受。o例例2一台图灵机可以设计成识别下面的序列:一台图灵机可以设计成识别下面的序列:1000110,10011101,010101011。图灵机的计算能力图灵机的计算能力图灵机的计算能力图灵机的计算能力oo第二,第二,把图灵机看作生成器,对给定的输入集把图灵机看作生成器,对给
12、定的输入集合,考察输出集合,并研究输入输出集合性质合,考察输出集合,并研究输入输出集合性质之间的关系,这就研究了图灵机的生成能力。之间的关系,这就研究了图灵机的生成能力。oo例例3设一台图灵机的输入集合为设一台图灵机的输入集合为In1n0nnN,可设计一台图灵机,对给定的,可设计一台图灵机,对给定的输入集合输入集合In,得到输出集合,得到输出集合Out0n1nnN。其中,。其中,N是全体自然数的集合。是全体自然数的集合。图灵机的计算能力图灵机的计算能力图灵机的计算能力图灵机的计算能力o第三第三,把图灵机看作计算器,相当于一个函数。,把图灵机看作计算器,相当于一个函数。图灵机的输入是函数的自变量
13、的值,图灵机的图灵机的输入是函数的自变量的值,图灵机的输出是函数的值。输出是函数的值。例例4图灵机可以计算下列函数:图灵机可以计算下列函数:(1)s(x)x1;(2)o(x)0;(3)A(0,y)y1,A(x1,0)A(x,1),A(x1,y1)A(x,A(x1,y)。图灵机的计算能力图灵机的计算能力图灵机的计算能力图灵机的计算能力o第一和第二个函数读者不难从图灵机的定义出第一和第二个函数读者不难从图灵机的定义出发感悟到它们是图灵机可以计算的函数,而第发感悟到它们是图灵机可以计算的函数,而第三个函数就比较复杂,一时难于判断。顺便提三个函数就比较复杂,一时难于判断。顺便提一下,第三个函数叫做一下
14、,第三个函数叫做阿克曼函数阿克曼函数,它是阿克,它是阿克曼(曼(W.Ackermann)在研究原始递归函数和)在研究原始递归函数和递归函数的关系时给出的。这个函数在计算理递归函数的关系时给出的。这个函数在计算理论中具有重要价值。论中具有重要价值。o事实上,图灵机还可以计算形式上比第三个函事实上,图灵机还可以计算形式上比第三个函数更复杂的函数。数更复杂的函数。图灵机的计算能力图灵机的计算能力图灵机的计算能力图灵机的计算能力oo图灵机可以计算图灵机可以计算n nS(x)x1(后继函数),后继函数),n nN(x)0(零函数),零函数),n nUi(n)(x1,x2,xn)xi,1in(投影函数)投
15、影函数)n n上述上述3个函数的任意组合。个函数的任意组合。oo从递归论中,我们知道这从递归论中,我们知道这从递归论中,我们知道这从递归论中,我们知道这3 3个函数属于个函数属于个函数属于个函数属于初始递归函数初始递归函数初始递归函数初始递归函数,n n任何原始递归函数都是从这任何原始递归函数都是从这任何原始递归函数都是从这任何原始递归函数都是从这3 3个初始递归函数经有个初始递归函数经有个初始递归函数经有个初始递归函数经有限次的复合、递归和极小化操作得到的。限次的复合、递归和极小化操作得到的。限次的复合、递归和极小化操作得到的。限次的复合、递归和极小化操作得到的。n n从可计算理论可知每一个
16、原始递归函数都是图灵从可计算理论可知每一个原始递归函数都是图灵从可计算理论可知每一个原始递归函数都是图灵从可计算理论可知每一个原始递归函数都是图灵机可计算的。机可计算的。机可计算的。机可计算的。4.1计算模型与二进制计算模型与二进制4.1.2二进制计算机的数字系统计算机的数字系统计算机的数字系统计算机的数字系统oo计算机采用的是二进制数字系统。计算机采用的是二进制数字系统。oo基本符号:基本符号:0 0、1 1oo进位原则:逢二进一进位原则:逢二进一oo优点:优点:n n易于物理实现易于物理实现n n二进制数运算简单二进制数运算简单n n机器可靠性高机器可靠性高n n通用性强通用性强oo缺点:
17、对人来说可读性差缺点:对人来说可读性差十进制数的表示十进制数的表示十进制数的表示十进制数的表示各位数字与它的权相乘,其积相加。各位数字与它的权相乘,其积相加。各位数字与它的权相乘,其积相加。各位数字与它的权相乘,其积相加。例如例如例如例如:27997.63=21*1027997.63=21*104 4+7*10+7*103 3+9*10+9*102 2+9*10+9*101 1+7*10+7*100 0+6*10+6*10-1-1+3*10+3*10-2-2 对于任意的十进制数:对于任意的十进制数:对于任意的十进制数:对于任意的十进制数:S=S=k kn n*10*10n n+k kn-1n-
18、1*10*10n-1n-1+k k1 1*10*101 1+k k0 0*10*100 0+k k-1-1*10*10-1-1+k k-m+1-m+1*10*10-m+1-m+1+k k-m-m*10*10-m-m(n1,m1)(n1,m1)其中,其中,其中,其中,1010称为十进制的基数称为十进制的基数称为十进制的基数称为十进制的基数,ki,ki0,1,2,3,4,5,6,7,80,1,2,3,4,5,6,7,899,mm,n n为正整数。小数点的位置不言自明。为正整数。小数点的位置不言自明。为正整数。小数点的位置不言自明。为正整数。小数点的位置不言自明。计算机的数字系统计算机的数字系统计算
19、机的数字系统计算机的数字系统oo计算机采用的是二进制数字系统。二进制和十进计算机采用的是二进制数字系统。二进制和十进计算机采用的是二进制数字系统。二进制和十进计算机采用的是二进制数字系统。二进制和十进制一样,是一种数制,它用于表示数的符号(数制一样,是一种数制,它用于表示数的符号(数制一样,是一种数制,它用于表示数的符号(数制一样,是一种数制,它用于表示数的符号(数字)由于在书写中的位置不同而具有不同的值。字)由于在书写中的位置不同而具有不同的值。字)由于在书写中的位置不同而具有不同的值。字)由于在书写中的位置不同而具有不同的值。oo基本符号:基本符号:基本符号:基本符号:0 0 0 0、1
20、1 1 1oo进位原则:逢二进一进位原则:逢二进一进位原则:逢二进一进位原则:逢二进一oo优点:优点:优点:优点:n n易于物理实现易于物理实现易于物理实现易于物理实现n n二进制数运算简单二进制数运算简单二进制数运算简单二进制数运算简单n n机器可靠性高机器可靠性高机器可靠性高机器可靠性高n n通用性强通用性强通用性强通用性强oo缺点:对人来说可读性差缺点:对人来说可读性差缺点:对人来说可读性差缺点:对人来说可读性差二进制数二进制数 Sknkn-1k0.k-mkn2nkn-12n-1k020k-m2-m-mki2iin其中,其中,2称为二进制的基数,称为二进制的基数,ki0,1,m,n为正整
21、数。为正整数。进一步,读者可从十进制数和二进制数的一般表示进一步,读者可从十进制数和二进制数的一般表示公式得到启发,将这种表示推广到更一般的任意进制,公式得到启发,将这种表示推广到更一般的任意进制,不同之处只是基数不一样。不同之处只是基数不一样。二进制数二进制数 二二进进制制的的运运算算规规则则比比十十进进制制的的运运算算规规则则简简单单得得多多。只只要要建建立立两两种种进进制制的的数数据据之之间间的的转转换换方方法法,那那么么,二二进进制制将将具具有有更更多多的的优优势势。计计算算机机的的理理论论基基础础是是逻逻辑辑和和代代数数。当当二二进进制制与与同同样样只只使使用用“真真”和和“假假”两
22、两个个值值的的逻逻辑辑代代数数建建立立了了联联系系后后,这这就就为为计计算算机机的的逻逻辑辑设设计计提提供供了了便便利的工具。利的工具。不同进位计数制间的转换不同进位计数制间的转换不同进位计数制间的转换不同进位计数制间的转换 R R 进制进制进制进制十进制十进制十进制十进制各位数字与它的权相乘,其积相加。各位数字与它的权相乘,其积相加。例如例如:(11111111.11)2=1*27+1*26+1*25+1*24+1*23+1*22+1*21+1*20+1*2-1+1*2-2=(255.75)10(3506.2)8=3*83+5*82+0*81+6*80+2*8-1=(1862.25)10(0
23、.2A)16=2*16-1+10*16-2=(0.1640625)10二进制与十进制间的转换二进制与十进制间的转换二进制与十进制间的转换二进制与十进制间的转换 十进制十进制十进制十进制 二进制二进制二进制二进制十进制整数转换成二进制的整数十进制整数转换成二进制的整数“除除R取余取余”法,例如:法,例如:268268余余余余 数数数数 23423400低位低位低位低位 2172170 028281 124240 022220 02121000011高位高位高位高位所以所以所以所以 68681010100010010001002 2二进制与十进制间的转换二进制与十进制间的转换二进制与十进制间的转换
24、二进制与十进制间的转换十进制十进制十进制十进制 二进制二进制二进制二进制十进制小数转换成二进制小数十进制小数转换成二进制小数“乘乘R取整取整”法,例如:法,例如:高位高位0.31252=0.6250.6252=1.250.252=0.50.52=1.0所以所以0.312510=0.01012不同进位计数制间的转换不同进位计数制间的转换不同进位计数制间的转换不同进位计数制间的转换二、八、十六进制的相互转换二、八、十六进制的相互转换二、八、十六进制的相互转换二、八、十六进制的相互转换oo每位八进制数相当于三位二进制数每位八进制数相当于三位二进制数oo每位十六进制数相当于四位二进制数每位十六进制数相
25、当于四位二进制数(1011010.10)2=(001011010.100)2=(132.4)8(1011010.10)2=(01011010.1000)2=(5A.8)16(F7)16(11110111)2(11110111)2信息的存储单位信息的存储单位信息的存储单位信息的存储单位oo位位(bit):度量数据的最小单位,表示一位二:度量数据的最小单位,表示一位二进制信息。进制信息。oo字节字节(byte):由八位二进制数字组成:由八位二进制数字组成(1byte=8bit)。K字节字节1K=1024byteM字节字节1M=1024KG字节字节1G=1024MT字节字节1T=1024G非数值信息
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算 学科 中的 基本概念
限制150内