计算机科学的基本概念和基本知识[1].ppt

第二章计算机科学的基本概念和基本知识 计算模型与二进制数学不等于计算,但数学确实起源于对计算的研究。数学、计算模型(计算方法、数学机器)、形式化与形式化方法我们说,形式是事物的内容存在的外在方式、形状和结构的总和。所谓形式化是将事物的内容与形式相分离,用事物的某种形式来表示事物。形式化方法是在对事物描述形式化的基础上,通过研究事物的形式变化规律来研究事物变化规律的全体方法的总称。 计算模型与图灵机所谓计算模型是刻划计算这一概念的一种抽象的形式系统或数学系统,而算法是对计算过程步骤(或状态的一种刻划,是计算方法的一种能行实现方式。在计算机科学中,我们通常所说的计算模型,并不是指在其静态或动态数学描述基础上建立求解某一(类)问题计算方法的数学模型,而是指具有状态转换特征,能够对所处理的对象的数据或信息进行表示、加工、变换、输出的数学机器。由于观察计算的角度不同,产生了各种不同的计算模型。递归函数、 Turing 机等(1) s(x) =x+1 (后继函数) (2) o(x) =0 (零函数) (3) U j (n)(x 1,x 2,…,x n)=x j(射影函数) 由初始函数和有限次使用算子可以构造各种复杂的递归函数,或者可计算函数。图灵机的示意图控制器的命令可表示为: (状态,符号) →(写符号,移动,状态); ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬──│0│0│0│1│1│1│0│1│1│1│┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴──↑┌─┐││┌┘└┐│控制器│└───┘一旦图灵机在运行中进入了一个状态,而且这个状态是一个结束状态,那么,图灵机就停机,计算任务宣告完成,此时带上的内容就是计算的输出结果。例1 M 的字母表 A={0,1,b},b 表示空格。状态集 Q= {q 1,q 2,q 3},其中,指定 q 1是开始状态, q 3是终止状态。 M的程序(控制器的命令)如下: q 1 0 1 R q 1; q 1 1 0 R q 1; q 1 b b R q 2; q 2 b b L q 3; q 2 0 0 H q 1; q 2 1 1 H q 1; 对图灵机的工作过程从不同的角度考察,可以给予不同的解释。第一,把图灵机看作识别器,即判断带子上最初的内容能否被图灵机所接受。假定图灵机从左向右扫描完带子上的内容后停机则为接受,否则为不接受。例2一台图灵机可以设计成识别下面的序列: 1000110, 10011101, 010101011 。第二,把图灵机看作生成器,对给定的输入集合,考察输出集合,并研究输入输出集合性质之间的关系,这就研究了图灵机的生成能力。例3 设一台图灵机的输入集合为 In={1 n0 n│n∈N}, 可设计一台图灵机,对给定的输入集合 In, 得到输出集合 Out = {0 n1 n│n∈N}。其中, N是全体自然数的集合。第三,把图灵机看作计算器,相当于一个函数。图灵机的输入是函数的自变量的值,图灵机的输出是函数的值。例4图灵机可以计算下列函数: (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年代发展的递归函数论(一种能行可计算性理论)中一类最一般的可计算函数(部分递归函数或部分可计算函数)在计算表达能力上是等价的。然而,图灵机简洁的构造和运行原理隐含了存储程序的原始思想,深刻地揭示了现代通用电子数字计算机最核心的内容。图灵奖 二进制也许是图灵机读写带上只出现两个符号启发了研究者, 在当时的技术条件下,从便于元器件的设计和制造考虑, 计算机的研制很自然地选择了二进制。后来的实践也证明了这种选择具有极大的优点。十进制数的表示例如, 这个数可以写成: =1×10 3+9×10 2+9×10 1+7×10 0 +6×10 -1+3×10 -2+0×10 -3 一般地,任何一个十进制数 S都可以表示为: S=k nk n-1… k 0.… k -m =k n×10 n+k n-1×10 n-1+…+k 0×10 0+…+k -m×10 -m -m =∑k