文档介绍：该【计算学科导论计算科学的基本概念和基本知识 】是由【1485173816】上传分享，文档一共【53】页，该文档可以免费在线阅读，需要了解更多关于【计算学科导论计算科学的基本概念和基本知识 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。,但数学确实起源于对计算的研究。数学、计算模型(计算方法、数学机器)、形式化与形式化方法我们说,形式是事物的内容存在的外在方式、形状和结构的总和。所谓形式化是将事物的内容与形式相分离,用事物的某种形式来表示事物。形式化方法是在对事物描述形式化的基础上,通过研究事物的形式变化规律来研究事物变化规律的全体方法的总称。,而算法是对计算过程步骤(或状态的一种刻第二页,共54页。划,是计算方法的一种能行实现方式。在计算机科学中,我们通常所说的计算模型,并不是指在其静态或动态数学描述基础上建立求解某一(类)问题计算方法的数学模型,而是指具有状态转换特征,能够对所处理的对象的数据或信息进行表示、加工、变换、输出的数学机器。由于观察计算的角度不同,产生了各种不同的计算模型。递归函数、机等(1)s(x)=x+1(后继函数)(2)o(x)=0(零函数)(3)(n)(x1,x2,…,)=(射影函数)由初始函数和有限次使用算子可以构造各种复杂的递归函数,或者可计算函数。图灵机的示意图第三页,共54页。控制器的命令可表示为:(状态,符号)→(写符号,移动,状态);┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬──│0│0│0│1│1│1│0│1│1│1│┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴──↑┌─┐││┌┘└┐│控制器│└───┘一旦图灵机在运行中进入了一个状态,而且这个状态是一个结束状态,则,图灵机就停机,计算任务宣告完成,此时带上的内容就是计算的输出结果。第四页,共54页。例1M的字母表A={0,1,b},b表示空格。状态集Q={q1,q2,q3},其中,指定q1是开始状态,q3是终止状态。M的程序(控制器的命令)如下:q101Rq1;q110Rq1;q1bbRq2;q2bbLq3;q200Hq1;q211Hq1;对图灵机的工作过程从不同的角度考察,可以给予不同的解释。第一,把图灵机看作识别器,即判断带子上最初的内第五页,共54页。容能否被图灵机所接受。假定图灵机从左向右扫描完带子上的内容后停机则为接受,否则为不接受。例2一台图灵机可以设计成识别下面的序列:1000110,10011101,010101011。第二,把图灵机看作生成器,对给定的输入集合,考察输出集合,并研究输入输出集合性质之间的关系,这就研究了图灵机的生成能力。例3设一台图灵机的输入集合为={1n0n│n∈N},可设计一台图灵机,对给定的输入集合,得到输出集合={0n1n│n∈N}。其中,N是全体自然数的集合。第三,把图灵机看作计算器,相当于一个函数。图灵机的输入是函数的自变量的值,图灵机的输出是函数的值。例4图灵机可以计算下列函数:第六页,共54页。(1)s(x)=x+1;(2)o(x)=0;(3)A(0,y)=y+1,A(x+1,0)=A(x,1),A(x+1,y+1)=A(x,A(x+1,y))。第一和第二个函数读者不难从图灵机的定义出发感悟到它们是图灵机可以计算的函数,而第三个函数就比较复杂,一时难于判断。顺便提一下,第三个函数叫做阿克曼函数,它是阿克曼()在研究原始递归函数和递归函数的关系时给出的。这个函数在计算理论中具有重要价值。事实上,图灵机还可以计算形式上比第三个函数更复杂的函数。沿着这样一种思路,图灵机被证明具有很强的计算能力,它与30年代发展的递归函数论(一种能行可计算性理第七页,共54页。论)中一类最一般的可计算函数(部分递归函数或部分可计算函数)在计算表达能力上是等价的。然而,图灵机简洁的构造和运行原理隐含了存储程序的原始思想,深刻地揭示了现代通用电子数字计算机最核心的内容。,在当时的技术条件下,从便于元器件的设计和制造考虑,计算机的研制很自然地选择了二进制。后来的实践也证明了这种选择具有极大的优点。十进制数的表示例如,:=1×103+9×102+9×101+7×100+6×10-1+3×10-2+0×10-3第八页,共54页。图灵奖图灵奖(.),由美国计算机协会()于1966年设立,又叫".图灵奖"。专门奖励那些对计算机事业作出重要贡献的个人。其名称取自计算机科学的先驱、英国科学家阿兰·麦席森·图灵()。由于图灵奖对获奖条件要求极高,评奖程序又是极严,一般每年只奖励一名计算机科学家,只有极少数年度有两名合作者或在同一方向作出贡献的科学家共享此奖。因此它是计算机界最负盛名、最崇高的一个奖项,有"计算机界的诺贝尔奖"之称。从1966年到2015年,50届,共64名得主,按国籍分,美国学者最多,欧洲学者偶见之,华人学者目仅有2000年图灵奖得主姚期智(现在清华大学)。据统计,截止2016年4月,美国著名学府加州大学伯克利分校的图灵奖人数(校友或教职工)位列世界第一(22位),斯坦福大学的图灵奖人数位列世界第二(20位),排名世界第三的是美国麻省理工学院(19位);哈佛大学(13位)和卡耐基梅隆大学(12位)分列世界第四和第五名。第九页,共54页。一般地,任何一个十进制数S都可以表示为:S=1…k0.…=×10n+1×101+…+k0×100+…+×10=∑×10ii=n其中,10称为十进制的基数∈{0,1,2,3,4,5,6,7,8,9},m,n为正整数。小数点的位置不言自明。二进制和十进制一样,是一种数制,它用于表示数的符号(数字)由于在书写中的位置不同而具有不同的值。二进制表示数的符号只有两个,即0和1,其数值与十进制中的0和1相同。此外,与十进制不同之处在于二进制数是逢二进一。第十页,共54页。例如,十进制数与二进制数中的一些可作如下对应:十进制二进制(0)(0)(1)(1)(2)(10)(3)(11)(4)(100)(5)(101)………(9)(1001)(10)(1010)………一般地,任何一个二进制数S都可以表示为:第十一页,共54页。