大学计算机基础ch1 引论

1大学计算机基础吴宁西安交通大学计算机教学实验中心2第1章引论3主要内容课堂主要讲授内容：计算模型计算机中的信息表示自学习内容：基于计算机的问题求解过程计算机前沿技术4一、计算模型1.计算与可计算性5计算机可以做什么？计算机不能够做什么？1）计算与计算科学计算按确定的、有限的规则和步骤，将输入转换为输出的过程。计算科学模型构建从客观现实中抽取、提炼必要的元素，并确定元素间关系数值分析数值近似算法的研究。在合理误差范围内，获取满足精度要求的近似结果。计算机实现利用计算机求解问题的方法——算法和程序设计6算法计算机科学

——主要研究计算理论、计算机及信息处理的学科计算机科学的核心——算法2）计算与可计算性可计算性理论（ComputabilityTheory）研究哪些问题为可计算，哪些问题为不可计算。可计算性理论也称为算法理论可计算理论的中心课题是将算法精确化.7计算与可计算性算法（Algorithm）：用于解决一类问题的、按照要求设计好的、有限的、确切的、无歧义的计算序列和步骤。算法的特征：有限性可执行性机械性和确定性输入相同，结果则相同终止性8计算与可计算性不是所有问题都存在算法。算法可计算函数：能够在抽象计算机上编出程序计算出值的函数哥德尔(K.Godel）理论：一般递归函数都是算法可计算函数，反之亦然。Alan•Turing把计算归结为简单、基本、确定的操作动作，提出和设计了一种抽象自动机。并证明：该自动机能计算的函数是算法可计算函数，而自动机不能计算的函数则是不可计算的函数。92.

图灵模型图灵（Alan•Turing）的主要贡献提出利用某种机器实现逻辑代码的执行，以模拟人类的各种计算和逻辑思维过程。将计算归结为最基本和确定的操作。10将计算与自动进行的机械操作联系在一起图灵机模型用机器来模拟人用纸笔进行数学运算的过程。组成：一条无限长的纸带Type一个读写头Head一套控制规则Table一个状态寄存器11图灵机模型12纸带单元格带符3个动作：改写当前格左移1格或右移1格。包含一组固定的状态和规则（程序）图灵机模型图灵机可以用一个五元组表示：M=（Q，Σ，δ，B，H）其中：Q：有穷个状态集合Σ：输入符合的集合δ：控制器规则集合B：初始状态。有B∈QH：H∈Q，是停机状态的集合。当控制器内部状态为停机状态时，图灵机结束计算。13图灵机的工作过程根据读写头内部程序的命令及内部状态进行纸带的读写和移动。在初始状态下，读写头位于输入的最左边单元上。每移动一次，图灵机将：改变状态下一状态可以是任何状态或与当前状态相同。在扫描的单元中写带符号。所写符号可以是任意带符号或与当前单元相同的符号。取代原符号。向左或向右移动带头。14图灵机工作过程的通俗描述读写头从纸带上读出一个方格中的信息；根据内部的状态查规则表Table（程序）；确定输出动作——选择以下三个动作之一：向纸带上写信息；使读写头向前移动一个方格；使读写头向后移动一个方格。说明下一时刻内部状态的变化。15图灵机示例设计计算“X+1”的图灵机，要求计算结束后读写头回到原位。设计该图灵机五元组的元素分别为：状态集合Q={Start，add，carry，noncarry，overflow，return，halt}输入符号集合Σ={0，1，*}初始状态B=Start停机状态集合H={Halt}16图灵机示例δ：控制器规则的集合17输入响应当前状态当前符号新符合读写头移动新状态Start**LeftAddAdd01LeftNoncarryAdd10LeftCarryAdd**RightHaltCarry01LeftNoncarryCarry10LeftCarryCarry*1LeftOverflowNoncarry00LeftNoncarryNoncarry11LeftNoncarryNoncarry**RightReturnoverflow0或1*RightReturnReturn00RightReturnReturn11RightReturnReturn**stayHalt图灵机示例设初始时，纸带上存储的内容为5，读写头指向起始位置。18*10*1Start图灵机示例19*10*1Add按照规则表，读写头向左移动一位，并进行“加”运算输入响应当前状态当前带符号新符号读写头移动新状态Start**LeftAdd*10*1Start图灵机示例20*00*1Carry做加法，若当前方格中为内容为“1”，则使其变为“0”，然后读写头向左移动一位，并有进位。输

入响

应当前状态当前带符号新符号读写头移动新状态Start**LeftAddAdd10LeftCarry*10*1Add图灵机示例21*01*1Noncarry若当前状态为“Carry”、方格中符号为“0”，则使其变为“1”，然后读写头向左移动一位，变为“无进位”状态。输

入响

应当前状态当前带符号新符号读写头移动新状态Start**LeftAddAdd10LeftCarryCarry01LeftNoncarry*00*1Carry图灵机示例22*01*1Noncarry若当前状态为“Noncarry”、方格中符号为“1”，则使其保持“1”，读写头向左移动一位，状态不变。输

入响

应当前状态当前带符号新符号读写头移动新状态Start**LeftAddAdd10LeftCarryCarry01LeftNoncarryNoncarry11LeftNoncarry*01*1Noncarry图灵机示例23*01*1Return按规则表操作：输

入响

应当前状态当前带符号新符号读写头移动新状态Start**LeftAddAdd10LeftCarryCarry01LeftNoncarryNoncarry11LeftNoncarryNoncarry**RightReturn*01*1Noncarry图灵机示例24输入响应当前状态当前带符号新符号读写头移动新状态Start**LeftAddAdd10LeftCarryCarry01LeftNoncarryNoncarry11LeftNoncarryNoncarry**RightReturnReturn**stayHalt按规则表操作：*01*1Halt小结计算机不可能解决世界上所有的问题。这种“不可解决性”主要反映在：不能在有限步骤内被解决不能为图灵模型解决的问题，无确定算法。虽然有可能解决，但因过于复杂而不能在可接受的时间内解决。算法的复杂度过高25二、计算工具的发展261.计算工具的发展和演变计算机的史前时代算筹，算盘，计算尺，…计算机的机械时代制表机，差分机，…计算机的电子时代电子管时代晶体管时代集成电路时代（超）大规模集成电路时代计算机的未来生物计算机，量子计算机，光计算机272.电子计算机的发展方向巨型化微型化网络化智能化2829三、计算机中的信息表示1.计算机与二进制计算机中使用二进制编码，为什么？二进制的灵感来自于中国的《易经》1二进制运算规则简单，且容易在物理上实现2二进制的理论基础是逻辑（真，假）3两仪生四象：太阴、少阳、少阴、太阳；四象生八卦：乾、兑、离、震、巽、坎、艮、坤用6位0和1，就可以表示八卦图的六十四个卦象——宇宙万物计算机由成千上万个可表示“0”和“1”的器件构成。计算机与二进制结论：计算机能够直接识别的信息只有二进制。所有需要计算机存储、处理的信息都必须转换为二进制。31计算机为什么能够处理文字、图像、视频、音乐？322.

文字信息的表示文字：西文汉字33西文字符ASCII码（美国信息交换标准代码）用7位二进制码表示（最高位默认为0）；可表示128个字符。扩展ASCII码（ANSI）用8位表示一个字符。其他编码 Unicode码、UTF-8等通用字符编码，可满足跨语言和平台的文本转换。34汉字码外码输入码机内码国标码、BIG5等字形码以点阵形式表示一个汉字。矢量汉字35机内码国标码用于计算机之间或与终端之间信息交换时的汉字代码（GB2312，GBK，GB18030）由连续的两个字节组成，每个字节七位有效，最高位为1。36字形码和矢量汉字字形码确定一个汉字字形点阵的代码汉字字形点阵中的每个点对应一个二进制位。矢量汉字矢量字库保存对每一个汉字的描述信息，比如一个笔划的起始、终止坐标，半径、弧度等等。在输出时要经过一定的数学运算。矢量汉字可随意放大、缩小而不变形。Windows使用的字库为以上两类。在FONTS目录下，扩展名为FON的文件为点阵字库；扩展名为TTF为矢量字库。37■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■点阵字模示意图38汉字信息处理代码转换过程输入码国标码机内码字形码汉字输入汉字输出Unicode码393.多媒体信息表示多媒体信息图形矢量图图像静态图像——位图视频图像音频波形音频文件（WAV）数字音频文件（MIDI）40声音信号的数字化与数字音频声音是连续变化的模拟信号。模拟信号：在时间和幅度上都是连续变化的信号数字信号：在时间和幅度上都是离散的信号要使声音能够被计算机处理，首先要使声音数字化。声音数字化的过程包括：采样量化编码模拟声音信号数字声音信号41采样在某些特定的时刻对这种模拟信号进行测量叫做采样（Sampling）；采样所得到的信号称为离散时间信号离散时间信号的特点：时间上离散，幅度上连续42量化把信号幅度取值的数目加以限定，由有限个数值组成的信号就称为离散幅度信号

43声音的采样和量化

44编码编码用预先规定的方法将文字、数字或其他对象编成数码，或将信息、数据转换成规定的电脉冲信号。是用少量的基本符号，通过简单的组合规则来表示大量复杂的信息。计算机能够惟一识别的编码是二进制码。为什么要编码？在计算机内部，信息只有经过数字化编码后才能表示、存放和传递。45声音文件的存储格式WAVWindows采用的波形声音文件存储格式，主要用于自然声的保存与回放。MP3主要应用于因特网上的声音传输。MP3主要格式。高达96:1的压缩比，有较好的音质。

RM、RA是RealNetworks公司制定的声音文件格式，有较高的压缩比，可采用流媒体方式在网络上实时播放。46图像文件格式是图像数据在文件中的存放形式，不同的软硬件厂商可能定义不同的文件格式。主要的图像文件格式有：位图文件(Bitmap-File，BMP)一种不压缩的格式，占有较大存储空间，但图像质量较高，没有数据损失。GIF(GraphicsInterchangeFormat)文件压缩效率高、占用的存储空间很