当前位置:
文档之家› 第2章计算机科学的基本概念和基本知识精品PPT课件
第2章计算机科学的基本概念和基本知识精品PPT课件
S=knkn-1 … k0.… k-m
=kn×10n+kn-1×10n-1+…+k0×100+…+k-m×10-m
-m
= ∑ ki×10i
i=n
其n为中正,整10数称。为小十数进点制的的位基置数不,k言i∈自{明0,1。,2,3,4,5,6,7,8,9},m,
二进制和十进制一样,是一种数制,它用于表示数的符号 (数字)由于在书写中的位置不同而具有不同的值。二进制 表示数的符号只有两个,即0和1,其数值与十进制中的0和1 相同。此外,与十进制不同之处在于二进制数是逢二进一。
第二章 计算机科学的基本概念和基本知识
2.1 计算模型与二进制 数学不等于计算,但数学确实起源于对计算的研究。 数学、计算模型(计算方法、数学机器)、形式化与形 式化方法 我们说,形式是事物的内容存在的外在方式、形状和结 构的总和。所谓形式化是将事物的内容与形式相分离,用事 物的某种形式来表示事物。形式化方法是在对事物描述形式 化的基础上,通过研究事物的形式变化规律来研究事物变化 规律的全体方法的总称。 1.1.1 计算模型与图灵机 所谓计算模型是刻划计算这一概念的一种抽象的形式系 统或数学系统,而算法是对计算过程步骤(或状态的一种刻
在当时的技术条件下,从便于元器件的设计和制造考虑, 计算机的研制很自然地选择了二进制。后来的实践也证明 了这种选择具有极大的优点。
十进制数的表103+9×102+9×101+7×100
+6×10-1+3×10-2+0×10-3
一般地,任何一个十进制数S都可以表示为:
例1 M的字母表A={0,1,b},b表示空格。状态集Q ={q1,q2,q3},其中,指定q1是开始状态,q3是终止状 态。
M的程序(控制器的命令)如下:
q1 0 1 R q1; q1 1 0 R q1; q1 b b R q2; q2 b b L q3; q2 0 0 H q1; q2 1 1 H q1; 对图灵机的工作过程从不同的角度考察,可以给予不同 的解释。
沿着这样一种思路,图灵机被证明具有很强的计算能力, 它与30年代发展的递归函数论(一种能行可计算性理
论)中一类最一般的可计算函数(部分递归函数或部分可 计算函数)在计算表达能力上是等价的。然而,图灵机简 洁的构造和运行原理隐含了存储程序的原始思想,深刻地
揭示了现代通用电子数字计算机最核心的内容。 图灵奖 2.1.2 二进制 也许是图灵机读写带上只出现两个符号启发了研究者,
划,是计算方法的一种能行实现方式。在计算机科学中,我 们通常所说的计算模型,并不是指在其静态或动态数学描述 基础上建立求解某一(类)问题计算方法的数学模型,而是指
具有状态转换特征,能够对所处理的对象的数据或信息进行 表示、加工、变换、输出的数学机器。由于观察计算的角度 不同,产生了各种不同的计算模型。
递归函数、Turing机等 (1) s(x)=x+1 (后继函数) (2) o(x)=0 (零函数)
(3) Uj(n)(x1,x2,…,xn)=xj (射影函数) 由初始函数和有限次使用算子可以构造各种复杂的递归函 数,或者可计算函数。 图灵机的示意图
控制器的命令可表示为:
(状态,符号)→(写符号,移动,状态);
┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬── │0│0│0│1│1│1│0│1│1│1│
┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴── ↑
┌─┐ ││ ┌┘ └┐ │控制器│ └───┘
一旦图灵机在运行中进入了一个状态,而且这个状态 是一个结束状态,那么,图灵机就停机,计算任务宣告完 成,此时带上的内容就是计算的输出结果。
第一,把图灵机看作识别器,即判断带子上最初的内
容能否被图灵机所接受。假定图灵机从左向右扫描完带子上 的内容后停机则为接受,否则为不接受。
例2 一台图灵机可以设计成识别下面的序列:
1000110, 10011101, 010101011。 第二,把图灵机看作生成器,对给定的输入集合,考察输 出集合,并研究输入输出集合性质之间的关系,这就研究了 图灵机的生成能力。 例3 设一台图灵机的输入集合为In={1n0n│n∈N},可设 计一台图灵机,对给定的输入集合In,得到输出集合Out= {0n1n│n∈N}。其中,N是全体自然数的集合。 第三,把图灵机看作计算器,相当于一个函数。图灵机的 输入是函数的自变量的值,图灵机的输出是函数的值。 例4 图灵机可以计算下列函数:
=kn×2n+kn-1×2n-1+…+k0×20+…+k-m×2-m
-m
= ∑ ki×2i i=n
其中,2称为二进制的基数,ki∈{0,1},m,n为正整数。 进一步,读者可从十进制数和二进制数的一般表示公式
得到启发,将这种表示推广到更一般的任意进制,不同之 处只是基数不一样。
二进制的运算规则比十进制的运算规则简单得多。只要 建立两种进制的数据之间的转换方法,那么,二进制将具 有更多的优势。计算机的理论基础是逻辑和代数。当二进 制与同样只使用“真”和“假”两个值的逻辑代数建立了 联系后,这就为计算机的逻辑设计提供了便利的工具。
例如,十进制数与二进制数中的一些可作如下对应:
十进制 二进制 (0) (0) (1) (1) (2) (10) (3) (11) (4) (100) (5) (101) ……… (9) (1001) (10) (1010)
………
一般地,任何一个二进制数S都可以表示为:
S=knkn-1 … k0. … k-m
(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))。
第一和第二个函数读者不难从图灵机的定义出发感悟到 它们是图灵机可以计算的函数,而第三个函数就比较复杂, 一时难于判断。顺便提一下,第三个函数叫做阿克曼函数, 它是阿克曼(W.Ackermann)在研究原始递归函数和递 归函数的关系时给出的。这个函数在计算理论中具有重要 价值。事实上,图灵机还可以计算形式上比第三个函数更 复杂的函数。