大学计算机基础(第2版)(txt+pdf+epub+mobi电子书下载)

作者：吴宁

出版社：电子工业出版社

格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT

大学计算机基础(第2版)试读：

前言

本次再版，既考虑了目前全国高等学校入校新生在计算机基础知识方面的一般现状，更考虑了创新型人才必须具备利用计算机求解问题的能力这一需求。力求使读者通过本书的学习，能够在了解计算机基础知识的基础上，较为深入地理解微型计算机的基本工作原理，能够初步建立起利用计算机解决问题的思路、掌握求解问题的一般方法，并了解利用计算机解决问题的一般过程，以及了解哪类问题是计算机不可解决的。

全书在组织架构上主要分为四个部分，共8章。

四部分内容：一是计算与可计算性理论；二是计算机中的信息表示；三是微型计算机系统组成和基本工作原理；四是算法和数据结构设计和实现。

第1章为引论，主要介绍了计算与可计算性理论、计算工具的发展、计算机问题求解过程、当前计算机科学研究的前沿技术等。第2章～第4章为计算机基础知识、系统组成、操作系统和网络技术等系统平台知识。第5章～第7章保持了第1版的主要内容，以“建立利用计算机解决问题的思路和方法”为宗旨，主要介绍利用VB程序语言进行数据结构和简单算法的设计及算法描述方法等。第8章仍然是一些综合案例设计。

本书配备同步修订的实验指导书大学计算机基础实验教材（Windows7+Office 2010）（第2版），新的实验指导教程也随着技术的发展及教学研究的成果做了一定的修订。为方便教学，本书还免费提供电子课件，可以登录华信教育资源网（www.hxedu.com.cn）注册下载。

本书由吴宁主编并统稿，参与编写的有吴宁（第1～3章）、陈文革（第4章）、崔舒宁（第5～8章）、李威威整理了附录并负责全书的校对；程向前和贾应智二位老师提供了部分案例。本书由首届国家级教学名师冯博琴教授主审，他为本书提出了许多宝贵的意见和建议，藉此表示衷心的感谢。

虽然经两年多的教学体会，使此次修订较第1版在内容安排、编写风格等方面都有一些改进，但作为一门新兴的课程，“大学计算机基础”的教学内容及相应教材的编写依然是难点，加之作者水平所限，书中错误和不妥之处在所难免，恳望师生不吝指正，十分感谢。作者E-mail：wun＠mail.xjtu.edu.cn。

编者

于西安交通大学

2013年8月

第1章 引论

引言

1991年，美国施乐公司PARC研究中心的Mark Weiser在Scientific American上发表的题为“Computer for the 21th Century”的文章中，提出了“无处不在的计算（Ubiquitous Computing）”（又译[1]为“普适计算”）的理念，开创了计算领域的第三次浪潮。无处不在的计算设备，无处不在的网络和通信，彻底改变了人类数千年的生活习惯。人们希望通过无处不在的计算，能随时随地获得自己希望的服务，且不用关心这些服务是怎样得到的。由于提供这些服务或计算的重要载体是计算机，因此，现代信息社会的每个人，都需要了解计算机，学习计算机科学。而作为未来的工程计算机人员和科学家，更需要具备利用计算机解决相关问题的能力，以及判断什么样的问题可以由计算机解决的能力。作为全书的“引论”，本章将从什么是计算开始，简要介绍可计算性理论、计算机中的信息表示、基于计算机的问题求解过程，以及当前计算机科学研究的一些前沿技术。

教学目的

• 了解计算与可计算性。

• 理解图灵机模型及其工作过程。

• 了解计算机的发展。

• 了解计算机中的信息表示及信息的处理过程。

• 了解基于计算机的问题求解过程。

• 了解当前计算机科学研究的前沿技术。

1.1 计算与可计算性

今天，计算机已深入到生活的各个角落，几乎每个人都知道计算机能做很多事，并且似乎是什么事都能做。在各类关于机器人的影视作品中，人“机”大战也成为眩目的看点。计算机真的什么都能做吗?是否真的会出现地球被机器人统治的那一天呢?

答案是否定的。20世纪30年代，图灵（Turing）就已经证明了计算机能力的极限性，即存在计算机不能解决的问题。这类问题又称为不可计算问题。

作为学习计算机科学的入门教材，首先使读者了解“不是任何问题都是计算机可解的”这一概念是非常必要的。虽然在现代科学研究中，没有计算机是万万不能的，但计算机确实不是万能的。

[1]计算的第一次浪潮是主机计算，人们通过字符终端共享主机计算；第二次浪潮是桌面计算时代，即个人计算机网络通信时代。1.1.1 计算与计算科学

1.计算

计算的行为由来已久，考古研究说明，在远古时代，古人类就有了计算问题的需要和能力。人类最初的计算工具就是人类的双手，掰着指头数数就是最早的计算方法。一个人天生有十个指头，因此，十进制就成为人们最熟悉的进制计数法。

由于双手的局限性，人类开始学习用小木棍、石子、“结绳”等方法进行计算。英文中的计算一词“Calculation”来自拉丁文中的“Calculus”，其本意就是用于计算的小石子。在2000多年前古代中国人发明的算筹是世界上最早的计算工具，而具有十进制计数法和一整套计算口诀的算盘，则可以认为是最早的“数字计算机”，珠算口诀就是最早的体系化的算法。

但到底什么是“计算”?这个问题直到20世纪30年代人们才从哥德尔（K.Godel）、丘奇（A.Church）、艾伦·麦席森·图灵（A.M.Turing）等科学家的研究中弄清楚是计算的本质，更重要的是弄清楚了什么问题是可计算的，什么问题是不可计算的。

计算，抽象地讲，就是从一个符号串X变成另一个符号串Y的过程。例如：（1）从符号串5+8-4变换为9，是进行了加减计算。2（2）将X=a变换为Y=2a，进行了微分计算。（3）将一段英文（符号串X）翻译为中文（符号串Y），也是进行了计算。

从以上这几个简单示例可以看出，计算是按照一定的、有限的规则和步骤（算法），将输入转换为输出的过程。

从数学的角度，计算主要可以分为数值计算和符号推导两大类。数值计算包括各种算术运算、方程求解等，如上例的（1）和（2）；符号推导包括各种函数的等式或不等式的证明、几何命题证明等。上例中的（3）可以归为符号推导。

2.计算科学

随着计算机技术的发展，计算这个原本专门的数学概念已经泛化到了人类的整个知识领域，并成为一种普适的科学概念。计算不再仅是数学的基础技能，而且是整个自然科学的工具。今天，人类的研究领域越来越广，每个领域的研究都会涉及大量的计算。作为各门学科研究的基础，在现代计算工具的支撑下，计算也逐渐形成体系，成为一门独立的学科，即计算科学，它是涉及数学模型构建、数值分析方法及计算机实现方法的研究领域。

数学模型（Mathematical Model）是用数学符号、数学公式、程序、图形等对客观问题本质属性的抽象而又简洁的刻划，它或能解释某些客观现象，或能预测未来的发展规律，或能为控制某一现象的发展提供某种意义下的最优策略或较好策略。数学模型的建立首先需要对现实问题进行深入细致的观察和分析，抽象出各种关键因素并确立它们之间的关系，再灵活巧妙地利用各种数学知识，表述这些关系。例如，学生综合素质测评、股市变化分析和气象综合预测等问题，都可以建立成一个数学模型。通过研究对象特征，分析对象的内在规律，确定影响变化规律的因素，利用适当的数学工具，构造出各因素间的关系。

这种应用相关领域知识从客观问题中抽象、提炼出数学模型的过程就称为数学建模（Mathematical Modeling）。数学建模的核心是分析和抽象，即要能从复杂的客观现实中抽取出反映其变化规律的各种因素，并建立它们之间的关系。因此，建立数学模型的目的，就是为了便于分析和研究各种客观现象的运动规律，从而确立最佳的问题解决方案。

数值分析（Numerical Analysis）是关于数值近似算法的研究。古巴比伦人曾利用巴比伦泥板（数值分析的最早作品之一）来计算近似值，而不是精确值。引入数值分析的原因是因为在许多实际问题中，常常无法求得精确值，或是无法用有理数表示结果。数值分析的目的就是在合理误差范围内，求得满足精度要求的近似结果。数值分析方法在所有工程和科学领域中得到应用。例如，数值天气预报、太空船的轨迹计算、股票市值及其变异程度分析、保险公司的精算分析等。

计算机实现方法可以描述为利用计算机求解问题的方法。在模型建立的前提下，“计算机实现”的核心就是算法设计和程序设计。

虽然计算科学不完全等同于计算机科学，但计算科学，以及其他各学科的研究都离不开计算机。因此，“利用计算机分析和解决相关问题”的能力成为每一位科学工作者应具备的基本素质。这种能力又[1]称为计算思维（Computational Thinking）能力。

计算机科学（Computer Science）是主要研究计算理论、计算机及信息处理的学科。半个多世纪来，计算机科学得到飞速发展和普及，作为现代科学体系的主要基石之一，它已逐渐超出一门单独学科的范围，演变为一种与社会、经济、能源、材料和健康等多个领域相结合的横向型科学技术。

有关计算机科学的详细定义有多种，但不论哪种定义，都强调了算法的研究。算法描述了解决某个特定问题的确切、无歧义、有限的动作序列。例如，按照某些准则获取一个年级中综合成绩最好的学生的过程，就是一种算法。遵照菜谱一步步做出一道好菜的过程，也是一种算法。计算机科学既要研究算法分析与设计理论，也同时要考虑如何在计算机上实现算法并解决实际问题。1.1.2 可计算性理论

要利用计算机解决问题，或者说完成某项任务，首先需要使计算机明确按照什么样的方法和步骤工作，即确定算法。计算机能不能完成一项任务，取决于能不能设计出完成这项任务的算法。人类很早就已开始研究算法，我国的珠算口诀、求两个正整数的最大公约数所用的辗转相除法等，都可以称为算法。

可计算性理论（Computability Theory）是研究计算的一般性质的数学理论。由于计算的过程就是执行算法的过程，因此，可计算理论的中心课题就是将算法这一直观概念精确化，建立计算的数学模型，研究哪些是可计算的，哪些是不可计算的，以此揭示计算的实质。由于计算与算法联系在一起，因此，可计算性理论又称为算法理论。

直观上说，求解一类问题的算法是一组规则，这组规则条数有限，每一条都是可执行的（可操作的），并且这种操作性是绝对机械的，即不论何人何时对之进行操作，只要输入数据相同，其结果都是一样的。作为算法的一组规则，至少还应包含一条有关终止计算的条目。因此，从直观上看，算法具备的特征是有限性、可执行性、机械性、确定性和终止性。

在20世纪以前，对“算法”、“计算”这些概念似乎并不存在什么问题，人们普遍认为所有的问题都是有算法的，至少是一切数学命题都存在算法。但是20世纪初，人们发现有许多问题虽已经过长期研究，但仍然找不到算法，如希尔伯特第10问题及半群的字的问题等。于是人们开始怀疑，是否对某些问题根本就不存在算法?即存在不可计算的问题?

于是，数学家们开始了对算法概念及可计算性的精确化研究。1934年，哥德尔（Godel）提出了一般递归函数的概念，并指出：凡[1]算法可计算函数都是一般递归函数，反之亦然。这一定义后来被称为埃尔布朗·哥德尔·克林定义。同年，丘奇证明了他提出的λ可定义函数与一般递归函数是等价的，并提出算法可计算函数等同于一般递归函数或λ可定义函数，即著名的“丘奇论点”。用一般递归函数虽给出了可计算函数的严格数学定义，但在具体的计算过程中，就某一步运算而言，选用什么初始函数和基本运算仍有不确定性。为消除所有的不确定性，图灵和E·波斯特各自独立地提出了抽象计算机的概念。图灵在他的“论可计算数及其在判定问题中的应用”（on Computable Numbers，with an Application to the Entscheidungsproblem）一文中，从一个全新的角度定义了可计算函数，他全面分析了人的计算过程，把计算归结为最简单、最基本、最确定的操作动作，从而用一种简单的方法来描述那种直观上具有机械性的基本计算程序，使任何机械（能行）的程序都可以归结为这些动作。这种简单的方法以一个抽象自动机概念为基础，并已证明：这种自动机能计算的函数是可计算函数，而这种自动机不能计算的函数则是不可计算的函数。这种抽象自动机被后人称为图灵机。

1937年，图灵在他的“可计算性与λ可定义性”一文中证明了图灵机可计算函数与λ可定义函数是等价的，从而拓广了丘奇论点，得出：算法（能行）可计算函数等同于一般递归函数或λ 可定义函数或图灵机可计算函数，即“丘奇—图灵论点”，相当完善地解决了可计算函数的精确定义问题，对数理逻辑的发展起了巨大的推动作用。

虽然已经证明可计算函数就是图灵机可计算函数，而图灵机可计算函数是递归可枚举函数。但这样的定义或描述对初学者来讲似乎显得有点过于高深。事实上，由于图灵机与计算机可以相互模拟（见3.3.3节），所以，对“可计算性”问题我们也可以通俗地描述为就是可以用计算机来解决的问题。从广义上讲，如“请为我做一个汉堡”这样的问题是无法用计算机来解决的（至少目前还不行）。计算机本身的优势在于数值计算（很多如文字识别，图像处理等非数值问题都可以通过转化为数值问题），能够用计算机解决的问题一定是“可以在确定、有限步骤内被解决的问题”，即有确定算法。像哥德巴赫猜想这样的问题就不属于“可计算问题”之列，因为计算机没有办法给出数学意义上的证明。

有关可计算性理论的深入描述因篇幅及课程性质所限，不再在此做进一步的讨论。本节讨论可计算性问题的目的，是希望读者能初步了解：[计算机不可能解决世界上所有的问题。其“不可解决性”反映在两个方面：一是不能在有限步骤内被解决；二是虽然有可能解决，但因过于复杂而不能在可接受的时间内解决］（所有机械装置都存在复杂性的临界点）。关于后者见7.3节算法的复杂性评价。

分析某个问题的可计算性意义重大，它可以使人们不必把时间浪费在不可能解决的问题上，而将精力用于可以解决的问题中。

[1]“计算思维”是运用计算机科学的基础概念进行问题求解、系统设计，以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。

[1]可计算函数定义：能够在抽象计算机上编出程序计算其值的函数。1.1.3 图灵机模型

1.图灵机模型

图灵机（Turing Machine）是图灵1936年提出的一种抽象计算模型，其基本思想：用机器来模拟人用纸和笔进行数学运算的过程。

图灵将人的计算过程看作以下两个简单的动作：（1）在纸上写上或擦除某个符号；（2）将注意力从纸上的一个位置移动到另一个位置，而人每一次的下一步动作走向依赖于人当前所关注的纸上某个位置的符号及人当前的思维状态。

为了模拟人的这种运算过程，图灵构造出一台假想的（抽象的）机器（图 1-1），该机器由以下几个部分组成：

• 一条无限长的纸带Type。纸带被划分成一个个连续的方格。每个格子上可包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。纸带上的格子从左到右依此被编号为0，1，2，…，纸带的右端可以无限延长。

• 一个读/写头Head（图1-1中间的大盒子）。读/写头内部包含了一组固定的状态（盒子上的方块）和程序。该读/写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。

• 一套控制规则Table（即程序）。Table包括当前读/写头的内部状态，输入数值，输出数值，下一时刻的内部状态。在每个时刻，读/写头都从当前纸带上读入一个方格信息。根据当前机器所处的状态及读/写头所读入的格子上的符号来确定读/写头下一步的动作。同时，改变状态寄存器的值，令机器进入一个新的状态。

• 一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。图1-1 图灵机结构模型

图灵机根据程序的命令和内部的状态在纸带上进行移动和读/写，它的每一部分都是有限的，但它有一个潜在的无限长的纸带。因此，这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。

2.图灵机的工作过程

将图灵机模型画成二维平面图如图 1-2 所示。首先将输入符号串（有穷长度的从输入字母表中选择的符号串）从左到右依次填在纸带的格子（带单元）上（图1-2中用符号Xi表示），其他带单元保持空白（即填以空白符，用符号B表示）。空格是带符号，但不是输入符号，除了输入符号和空格之外，还可能有其他的带符号。若读/写头（带头）位于某个带单元之上，说明图灵机正在读/写这个单元。图1-2 图灵机模型示意图

图灵机的工作过程就是根据读/写头内部程序的命令及内部状态进行纸带的读/写和移动。在初始状态下，读/写头位于输入的最左边单元上（第 0 号格子）。每个图灵机都有一组变换规则，图灵机的移动是当前状态和扫描的带符号的函数，根据当前读/写头指向的带符号及其自身的状态，由规则确定读/写头是否移动及移动方向。每移动一步，图灵机将：

• 改变状态。下一状态可以是任何状态或与当前状态相同。

• 在扫描的单元中写带符号。这个带符号代替扫描的单元中任何符号。所写符号可以是任意的带符号或与当前单元的符号相同。

• 向左或向右移动带头。在本书中要求带头移动而不允许带头保持静止。这个限制并不约束图灵机的计算能力，因为包含静止带头的任何操作都可连同下一个带头移动一起被压缩成单个状态改变、写入新的带符号及向左或向右移动的操作。

例1-1 假设图灵机纸带上的每个方格内为a或b或空格B，控制规则Table用于表示当读入（输入）给定时（如读入a）读/写头的移动方向（向前、向后或停止）。

将输入信息集合表示为IN，输出信息集合表示为OUT，且有：

设图灵机纸带状态如图1-3所示。图1-3 程序示例

给定控制规则Table如下：

依据上述规则，移动 7 次后，将纸带上停止符B左端的符号均改为x，并停止。

因此，图灵机的工作过程可以简单地描述为读/写头从纸带上读出一个方格中的信息，然后根据它内部的状态对程序进行查表（规则表 Table），得出一个输出动作，确定是向纸带上写信息还是使读/写头向前或向后移动到下一个方格。同时，程序还会说明下一时刻内部状态转移到哪里。

图灵机只要根据每一时刻读/写头读到的信息和当前的内部状态，查表就可确定它下一时刻的内部状态和输出动作。只要改变规则Table，图灵机就可以做不同的工作。如果把图灵机的内部状态解释为指令，将规则解释为程序，都用二进制编码表示，与输出和输入信息（也可用二进制码表示）同样存储在机器里，编写不同的程序就会使机器做不同的动作。这就成为电子计算机了。所以，图灵机就是一个最简单的计算机模型。

3.图灵机的形式化描述

形式上，图灵机（TM）可以描述为一个七元组，即

其中：

Q：图灵机状态的有穷集合。

Σ：输入符号的有穷集合，不包含空白符。

Γ：带符号的完整集合；Σ是Γ的子集，有Σ∈Γ。

δ：转移函数。Δ（q，X）的参数是状态q和带符号X。δ（q，X）的值在有定义时是三元组（p，Y，D），其中：p是下一状态，属于集合Q；Y是在当前扫描的单元中写下的符号，属于Γ集合，代替原来单元里的符号；D是方向，非L即R，分别表示“向左”和“向右”，说明带头移动方向。

转移函数δ是一个部分函数，换句话说，对于某些q和X，δ（q，X）可能没有定义，如果在运行中遇到下一个操作没有定义的情况，机器将立刻停机。

q0：初始状态，属于Q，开始时图灵机就处于q0状态。

B：空格符号。这个符号属于Γ但不属于Σ，即不是输入符号。开始时，空格出现在除包含输入符号的有穷多个初始单元之外的所有单元中。

F：终结状态或接受状态的集合，是Q的子集。

今天，图灵机依然是计算理论研究的中心课题，图灵机的“停机[1]问题”更是研究许多判定问题的基础。“判定问题”是指判定无穷多个同类个别问题是否具有算法解，或者是否存在能行性的方法使得对该问题类的每一个特例都能在有限步骤内机械地判定它是否具有某种性质的问题。例如，“任给一个素数x，x是素数吗?”，这一问题就是判定问题。研究判定问题的意义：如果某问题不可判定，就意味着它是不可解的或不可计算的；相应的，若它是可计算的，则它是可判定的或可解的。由此，又归结到1.1.2节结尾处所述的研究可计算性理论的意义。

＊1.2 计算机的发展历程

在1946年之前，计算机的工作都是基于机械运行方式，没有进入逻辑运算领域。如果不是1906年美国人Lee De Forest发明了电子管，电子计算机是不可能出现的。正是电子技术的飞速发展，使计算机由机械式发展到电子时代。

计算机的发展至今经历了五个时代。第一代（1946年—1954年）称为“电子管计算机”时代，内部元件使用电子管。图 1-4 所示是第一台用电子管和继电器制作的通用电子计算机ENIAC，它于1946年2月15日在美国宾夕法尼亚大学问世，共使用了18800个电子管，6000多个开关和配线盘，重约30吨，占地170平方米，工作主频为0.1MHz。

美国数学家冯·诺依曼（J·Von Neumann）提出了解决此问题之道，这就是“程序存储方式”。通俗地讲，就是把原来通过切换开关和改变配线来控制的运算步骤，以程序方式预先存放在计算机中，然后让其自动计算。在以后的日子中，计算机的发展正是沿着“程序存储方式”这一光辉道路前进的。

虽然ENIAC在每次进行不同的计算时，都需要切换开关和改变配线，使当时从事计算的科学家看上去更像在干体力活。但无论如何，它的诞生，表示人类从此进入了电子计算机时代。从那一天至今的半个多世纪中，随着电子技术的发展，计算机经历了从电子管到晶体管、集成电路、大规模集成电路，以及超大规模集成电路等几代的发展，无论是在体积上、运行速度上，还是在智能性、可靠性及价格等多方面都有了迅猛的进步，成为20世纪发展最快的技术，计算机行业也成为20世纪最具活力的行业。图1-4 在第一台电子计算机ENIAC上编程

第一代计算机主要用于工程计算，其主要特点是采用电子真空管和继电器构成处理器和存储器，用绝缘导线实现互连。体积较为庞大，运算速度较低，运算能力有限。程序编写采用由“0”和“1”组成的二进制码表示的机器语言，只能进行定点数运算。由于电子管易发热，寿命最长只有3000h。因此，计算机运行时常会因电子管被烧坏而出现死机。

第二代计算机属于晶体管计算机（1960年—1964年）。世界上第一台全晶体管计算机TRADIC于1955年由贝尔实验室研制成功，它3装有800只晶体管，功率仅为100W，占地3ft，如图1-5所示。

第二代计算机采用晶体管逻辑元件及快速磁心存储器，彻底改变了继电器存储器的工作方式和与处理器的连接方法，大大缩小了体积。其运算速度也从第一代的每秒几千次提高到几十万次，主存储器的存储容量从几千字节提高到10万字节以上。另外，第二代计算机普遍增加了浮点运算，使数据的绝对值可达到2的几十次方或几百次方，同时有了专门用于处理外部数据输入/输出的处理机，使计算能力实现了一次飞跃。除科学计算外，开始被用于企业商务。

在软件方面，第二代计算机除机器语言外，开始采用有编译程序的汇编语言和高级语言，建立了子程序库及批处理监控程序，使程序的设计和编写效率大为提高。

采用集成电路作为逻辑元件是第三代计算机（1964年—1974年）的最重要特征。此时，微程序控制、流水线技术、高速缓存和先行处理机等技术开始出现并逐渐普及。第三代计算机的典型代表有1964年IBM公司研制出的IBM S/360、CDC 公司的CDC6600及CRAY公司的巨型计算机CRAY-1等，如图1-6所示。图1-5 TRADIC晶体管计算机图1-6 巨型计算机CRAY-1

随着集成电路技术的发展，出现了采用大规模和超大规模集成电路及半导体存储器的第四代计算机（1974年—1991年），同时，计算机也逐渐开始依据功能和性能的不同分为巨型机、大型机、小型机和微型机，出现了共享存储器、分布存储器及不同结构的并行计算机，并相应产生了用于并行处理和分布处理的软件工具和环境。第四代计算机的代表机型Cray-2和Cray-3巨型机，因采用并行结构而使运算速度分别达到每秒12亿次和每秒160亿次。

从1991年至今的计算机系统，都可以认为是第五代计算机。超大规模集成电路（VLSI）工艺的日趋完善，使生产更高密度、高速度的处理器和存储器芯片成为可能。这一代计算机的主要特点是大规模并行数据处理、系统结构的可扩展性、高性能的实时通信能力和智能性。随着集成电路技术的不断发展，现代计算机系统的运算速度和整体性能都得到不断提高。图1-7所示为中国在2004年研制的曙光4000A超级计算机，其运算速度达每秒8.061万亿次。图1-7 曙光4000A超级计算机

[1]停机问题是指是否存在一个算法，对于任意给定的图灵机都能判定任意的输入是否会导致停机?已证明图灵机的停机问题是不可判定的。停机问题的不可判定性成为了解决许多不可判定性问题的基础。1.2.2 微型计算机的发展

相对于高性能大型或巨型计算机系统，在20世纪70年代诞生的微型计算机（又称为PC，Personal Computer，个人计算机）则因其较高的性价比而在各行各业中得到了更为广泛的应用。

微型计算机的发展伴随的是微处理器的发展。世界上第一片微处理器是Intel公司1971年研制生产的Intel 4004（图1-8），是一个4位微处理器，可进行4位二进制的并行运算，拥有45条指令，速度为0.05MIPS（Million Instructions Per Second，每秒百万条指令）。

4004功能有限，主要用于计算器、电动打字机、照相机、台秤、电视机等家用电器上，一般不适用于通用计算机。而在同年末推出的8位扩展型微处理器8008，则是世界上第一片8位微处理器，也是真正适用于通用微型计算机的处理器。它可一次处理8位二进制数，寻址16KB存储空间，拥有48条指令系统。这些使它能有机会应用于许多高级的系统。

微处理器及微型计算机从1971年至今经历4位、8位、16位、32位、64位及多核芯6个时代。除上述主要用于袖珍式计算器的4004芯片外，其他具有划时代意义微处理器如下：

•1973年，Intel公司推出的8位微处理器Intel 8080。这是8位微处理器的典型代表。它的存储器寻址空间增加到64KB，并扩充了指令集，指令执行速度达到每秒50万条指令，同时它还使处理器外部电路的设计变得更加容易且成本降低。除Intel 8080外，同时期推出的还有Motorola公司的MC6800系列，以及Zilog公司的Z80等。

•1978年，Intel公司推出的Intel 8086/8088微处理器是16微处理器的标志。其内部包含29 000个3μm技术的晶体管，工作频率为4.77MHz，采用16位寄存器和16位数据总线，能够寻址1MB的内存储器。IBM PC采用的微处理器就是8088。同时代的还有Motorola公司的M68000和Zilog公司的Z8000。

•1985年，研制成功的32位微处理器80386系列。其内部包含27.5万个晶体管，工作频率为12.5MHz，后逐步提高到40MHz。可寻址4GB内存，并可管理64TB的虚拟存储空间。

•“奔腾（Pentium）”微处理器在2000年11月发布，起步频率为1.5GHz，随后陆续推出了1.4～3.2GHz的64位的P4处理器。

• 2006年，开始推出并得到迅速发展的多核处理器，是计算技术的又一次重大飞跃。多核处理器是指在一个处理器上集成两个或以上运算核心，从而提高计算能力。较之单核处理器，多核处理器能带来更高的性能和生产力优势，因而成为了一种广泛普及的计算模式。图1-9所示为Intel公司推出的双核处理器芯片。图1-8 Intel 4004微处理器芯片图1-9 Intel双核处理器芯片

世界上第一台微型计算机Altair8800在1975年4月由Altair的公司推出，它采用Zilog公司的Z80芯片作为微处理器。它没有显示器和键盘，面板上有指示灯和开关，给人的感觉更像一台仪器箱。

IBM公司在1981年推出了首台个人计算机IBM PC，1984年，又推出了更先进的IBM PC/AT，它支持多任务、多用户，并增加了网络能力，可联网1000台PC。从此，IBM彻底确立了在微机领域的霸主地位。

今天，微型计算机已真正进入到千家万户、各行各业，它在功能上、运算速度上都已超过了当年的大型机，而价格却只是大型机的几分之一。真正实现了其大众化、平民化和多功能化的设计目标。1.2.3 未来计算机的发展

未来充满了变数，未来的计算机将会是什么样?

21世纪是人类走向信息社会的世纪，是网络的时代，是超高速信息公路建设取得实质性进展并进入应用的年代。电子计算机技术正在向巨型化、微型化、网络化和智能化这四个方向发展。

巨型化不是指计算机的体积大，而是指具有运算速度高、存储容量大、功能更完善的计算机系统。巨型机的应用范围如今也日渐广泛，如航空航天、军事工业、气象、电子、人工智能等几十个学科领域发挥着巨大的作用，特别是在复杂的大型科学计算领域，其他的机种难以与之抗衡。

计算机的微型化得益于大规模和超大规模集成电路的飞速发展。现代集成电路技术的发展，已可将计算机中的核心部件：运算器和控制器集成在一块大规模或超大规模集成电路芯片上，作为中央处理单元，称为微处理器，因而才使计算机作为“个人计算机”变得可能。微处理器自1971年问世以来，发展非常迅速，伴随着集成电路技术的发展，以微处理器为核心的微型计算机的性能不断跃升。现在，除了放在办公桌上的台式微型机外，还有可随身携带的各种规格的笔记本计算机、可以握在手上的掌上电脑、可随时上网和进行文字处理的平板电脑、手机等。

据美国媒体报道，在2011年2月，美国科学家已成功研制出世界上最小的计算机——一种可以植入眼球的医用毫米级计算系统。这种计算机主要为青光眼患者研制，放置在患者眼球内可以监测眼压，3方便医生及时为病人缓解痛苦。据介绍，这种计算机只有 1mm大小，包括一个极其节能的微处理器、一个压力传感器、一枚记忆卡、一块太阳能电池、一片薄薄的蓄电池和一个无线收发装置。通过无线收发装置，这个计算机能够向外部装置发出眼压数据资料。

从20世纪中后期开始，网络技术得到快速发展，已经突破了只是“帮助计算机主机完成与终端通信”这一概念。众多计算机通过相互连接，形成了一个规模庞大、功能多样的网络系统，从而实现信息的相互传递和资源共享。今天，网络技术已经从计算机技术的配角地位上升到与计算机技术紧密结合、不可分割的地位。各种基于网络的计算机技术不断出现和发展，计算机连入网络已经如同电话机连入市内电话交换网一样方便，且网络信息传送的速度也随着“光纤”差不多铺到“家门口”而变得越来越快。今天，计算机技术的发展已离不开网络技术的发展，同时，网络也成为了人类生活的一部分。

计算机的智能化就是要求计算机具有人的智能，即让计算机能够进行图像识别、定理证明、研究学习、探索、联想、启发和理解人的语言等。目前，人工智能技术的研究已取得较大成绩，智能计算机（又称为“机器人”）已部分具有人的能力，能具有简单的“说”、“看”、“听”、“做”能力，能替代人类去做一些体力劳动或从事一些危险的工作，如日本福岛核电站出现核泄漏后，日本政府就曾“派”机器人进入核电站检测核泄漏的情况。

人工智能是目前以至未来可见的时间里计算机科学的研究热点。人工神经网络的研究，使计算机向人类大脑接近又迈出了重要的一步。今天，除了希望在软件技术上不断深入研究，人们还寄希望于全新的计算机技术能够带动人工智能的发展。至少有三种技术有可能引发全新的革命，它们是光子计算机、生物计算机和量子计算机。

光子计算机的运算速度据推测可能比现行的超级计算机快1000～10 000倍。而一台具有5000个左右量子位的量子计算机可以在大约30s内解决传统超级计算机需要100亿年才能解决的素数问题。相对而言，生物计算机研究更加现实，美国威斯康星－麦迪逊大学已研制出一台可进行较复杂运算的DNA计算机。据悉，一克DNA所能存储的信息量可与1万亿张CD光盘相当。这些推测，使人们有理由对人工智能的发展前景变得乐观。

计算机真的能达到人类的思维能力，模拟人类的行为动作吗?未来的计算机会像影视剧中描述的那样完全达到人的智力吗?

1.3 计算机中的信息表示

如今，信息是一个非常流行的词汇。人际社会中，每天都少不了信息交互，每个人都是信息的发布者，同时也都是信息的接收者。互联网上，更是每分每秒都有大量的信息在传送。信息交换和信息共享促进了新知识的传播、新价值的产生，也推动着社会的进步。

在这个“信息爆炸”的时代，对信息的传播、处理和存储都离不开计算机这个载体。本节就在给出“信息”一词一般描述的基础上，介绍计算机中的信息表示和基于计算机的信息处理过程。1.3.1 信息

对“信息”一词最早的解释见于哈特莱（Ralph V.L.Hartley）1928年发表在《贝尔系统技术杂志》上的“信息传输”一文中，他把信息理解为选择通信符号的方式，并用选择的自由度来计量这种信息量的大小。信息论（Information Theory）的开山鼻祖、美国数学家香农（C.E.Shannon）1948年在《贝尔系统技术杂志》上发表了一篇题为“通信的数学理论”论文，该文被认为是信息论诞生的标志。香农以概率论为工具，阐述了通信工程中的一系列基本理论问题，建立了信息从信源（发送方）通过信道（传输途径）传递给信宿（接收方）的通信系统模型，并给出了计算信源信息量和信道容量的方法和计算信息熵的公式。他对信息的解释：信息是用来减少随机不定性的东西。控制论创始人之一，美国科学家维纳（N.Wiener）指出：信息就是信息，既不是物质也不是能量，专门指出了信息是区别于物质与能量的第三类资源。《辞源》中将信息定义为“信息就是收信者事先所不知道的报道”。作为科学术语，可以简单地将信息理解为消息接收者预先不知道的报道”。我国学者钟义信从认识论的层次将信息定义为“主体关于某事物的认识论层次信息，是指主体所感知或表述的关于该事物的运动状态及其变化方式，包括状态及其变化方式的形式、含义和效用”。

对于信息的定义，至今仍是众说纷纭，莫衷一是。但人们对信息的共同认识：信息是一种宝贵的资源，信息、材料（物质）、能源（能量）是组成社会物质文明的三大要素。

相对于通信范围内的信息论（狭义信息论），广义信息论以各种系统、各门科学中的信息为对象，以信息过程的运动规律作为主要研究内容，广泛研究信息的本质和特点，以及信息的取得、计量、传输、储存、处理、控制和利用的一般规律，使得人类对信息现象的认识与揭示不断丰富和完善。所以，广义信息论又称为信息科学，它以信息为主要研究对象，是一门新兴的跨跃多个学科的科学。

在一般用语中，信息、数据、信号并不被严格区别，但从信息科学的角度看，它们是不能等同的。在用现代科技（计算机技术、电子技术等）采集、处理信息时，必须要将现实生活中的各类信息转换成智能机器能识别的符号（符号具体化即是数据，或者说信息的符号化就是数据），再加工处理成新的信息。数据可以是文字、数字或图像，是信息的具体表示形式，是信息的载体。而信号则是数据的电磁或光脉冲编码，是各种实际通信系统中，适合信道传输的物理量。信号可以分为模拟信号（随时间而连续变化的信号）和数字信号（在时间上的一种离散信号）。1.3.2 数值信息表示

现代计算机中所有的数都采用二进制，无论数的大小，都是1和0的组合。每位1或0称为1位二进制码。例如，8需要用4位二进制码表示（1000），100要用8位二进制码表示（1100100），而要表示1万，则至少需要用14位二进制码（10011100010000）。由此可见，同样大小的数，二进制要比对应的十进制数书写长度要长很多。

也许是人有10个手指的缘故，人类从结绳计数开始，就一直采用十进制。也就是说，我们已经很习惯于用十进制来表达数的大小及对数据的运算。那么，为什么人类发明的计算机却要采用二进制呢?

香农在他的“通信的数学理论”论文中曾首次指出，通信的基本信息单元是符号（Smmble），而最基本的符号是二值符号，又称为二进制码。

二进制的灵感据说来自于中国的太极八卦图，如图 1-10所示。1701年，德国数学家莱布尼茨（G·W·Leibniz）受中国八卦图的启发[1]，发明了二进制。图1-10 太极八卦图

太极（伏羲）八卦图分为“阴”、“阳”两仪组成。两仪生四象：太阴（00）、少阳（01）、少阴（10）、太阳（11）；四象生八卦：乾（111）、兑（110）、离（101）、震（100）、巽（011）、坎（010）、艮（001）、坤（000）。由此，通过阴阳引申，就可以表示宇宙万物。如果将“阴”视为0，将“阳”视为1，所有的卦象于是也就可以看成0和1的组合。例如：

太阴——00，少阳——01，少阴——10，太阳——11；

乾——111，兑——110，离——101，震——100，巽——011，坎——010，艮——001，坤——000。

这样，用6位0和1，就可以表示八卦图的64个卦象。

莱布尼茨的二进制，就是用0和1去表示一切数字，如000，001，010，011就分别代表0～3这4个数字。1848年，英国数学家乔治·布尔（George Boole）推出了二进制运算法则，为二进制计算机的诞生奠定了基础。

诞生于1946年的第一台电子计算机ENIAC采用的是十进制，可以同时处理10个十进制数。由于十进制有10个符号，意味着需要有10种稳定状态与之对应，不仅造成数据量大、工作速度低，更主要是用[1]电子器件实现起来很困难。因此，冯·诺依曼提出了在计算机中采用二进制。采用二进制主要有以下理由：（1）二进制只有0和1两个基本符号，任何两种对立的物理状态都可以归结为用二进制表示。例如，开关的“闭合”与“断开；电位的“高”和“低”；晶体管的“导通”与“截止”；电容的“满电荷”与“空电荷”等。如此，一切有两种对立稳定状态的器件都可以表示二进制的“0”和“1”。

我们可以用一个简单的示例来说明。在图1-11中，当图1-11（a）中的X端电位为0V时，晶体二极管导通，有电流流过电阻R；当X端电位为+5V时二极管将截止，R上将不会有电流流过。根据欧姆定理知，导通时a点电位≈0V（低电平）；截止时因电流i=0，则a点电位=+5V（高电平）。如果周期性地使X端呈现0V和+5V（如图1-11（b）所示的脉冲波），则二极管就会周期地导通和截止。如果将 0V 用“0”表示，5V 用“1”表示，则上述过程就与二进制编码对应了。图1-11 二极管电路与二进制编码

具有两种稳定状态的电子元件很容易找到，产生两种稳定状态的电路也易于设计。因此，计算机采用二进制的重要原因之一就是其非常容易用电子器件实现，可靠性也高。（2）二进制的另外一个主要优点是算术运算规则简单，且适合逻辑运算。二进制数的算术运算特别简单，加法和乘法各仅有3条运算规则（加法：0+0=0，0+1=1，1+1=10；乘法：0×0=0，0×1=0，1×1=1）。二减法和除法则可以通过一定的变换转换为加法和乘法运算[2]。[3]

计算机的基本运算是算术运算和逻辑运算。逻辑运算的对象是“真”和“假”，二进制数的“1”和“0”正好可与逻辑值“真”和“假”相对应，这就使计算机进行逻辑运算变得非常方便。图1-12分别给出了用二极管实现的“与”逻辑和“或”逻辑运算的电路示例。图1-12 二极管逻辑门电路

计算机可以说是由许许多多个类似图 1-12 这样的门电路组成的，它用“1”表示高电平，用“0”表示低电平。这样，就将电位状态与二进制编码一一对应起来。因此，二进制是计算机硬件唯一能够直接识别的编码。

[1]胡阳、李长铎在《莱布尼茨－二进制与伏羲八卦图考》一书中论证了莱布尼茨的二进制至少在某种程度上受到了八卦图的启发。

[1]有关冯·诺依曼的介绍见第3章。

[2]将减法运算转换为加法运算的原理见2.3节（二进制的表示和运算）。除法到乘法的转换请参阅有关计算机原理方面的书籍。

[3]关于逻辑运算的详细介绍见2.4节（逻辑运算与逻辑门）。1.3.3 文字信息表示

由上述分析已知，计算机能够直接识别的只有二进制码。所以，要让计算机保存或处理的所有信息都必须采用二进制码表示，文字信息也不例外。

文字由字符组成。计算机是美国人发明的，所以，计算机中的文字首先是西文字符，包括字母、数字、符号及特殊控制字符。西文字符编码方式很多，目前，国际上广泛使用的是ASCII码（American Standard Code for Information Interchange，美国标准信息交换码），分为标准ASCII码和扩展ASCII码两种。

标准ASCII码的用7位（bit）二进制码（bit～bit）表示，总共可60表示128个字符（知道为什么是128个吗?）。但由于计算机从诞生那天起，能够同时处理（专业上称为并行处理）的二进制数就是8位（从来没有7位）。因此，标准ASCII码实际上是用8位二进制码来表示的，8位二进制码又称为1B（Byte），在内存中占用1个单元（这些名词很陌生，没关系，先留着，后边就学到了）。最高位（bit）用作7奇偶校验位（默认情况下为0）。奇偶校验，是指在代码传送过程中用来检验是否出现错误的一种方法，分为奇校验和偶校验两种。奇校验规定：正确的代码一个字节中1的个数必须是奇数，若非奇数，则使最高位bit为1（补为奇数）；偶校验规定：正确的代码一个字节中71的个数必须是偶数，若非偶数，则使最高位bit为1。标准ASCII码表7示的128个字符（见附录B）中，包含10个阿拉伯数字，52个英文大小写字母，33个符号及33个控制符。一个字符对应一个编码。如字符“A”对应的ASCII码为65，而空格对应的ASCII码为32。

为了表示更多的欧洲常用字符（如德语中的字母ü），对标准ASCII进行了扩展。扩展ASCII由8位二进制数码组成，这样就可以表示256种不同的符号。

除ASCII码外，较常见的西文字符编码还有EBCDIC码，用8位二进制码表示，可表示256个字符。

为了使普通国人也能使用计算机，需要计算机能够处理汉字。数值和西文字符可以通过键盘直接输入（谁让计算机是人家发明的呢?），而汉字是象形文字，计算机处理汉字的关键首先是如何将每个汉字变成可以直接从键盘输入的代码——即汉字的外码，然后再将输入码转换为汉字机内码，之后才能对其处理和存储。在输出汉字时，则需进行相反的过程，将机内码转换为汉字的字型码。因此，汉字的编码包括外码、机内码、字形码和矢量汉字。

汉字的外码即它的输入码，目前，常见的编码法有拼音、五笔和搜狗等。

机内码主要有国标码、BIG5码（主要在中国台湾和香港地区使用）等。我国国家标准局于1981年颁布了“国家标准信息交换用汉字编码基本字符集”（GB2312—80），共收集了 6763 个汉字，682 个非汉字符号（外文、字母、数字和各种图形等），每个汉字对应一个国标码。

每个国标码用 2B 表示，为避免与ASCII 码冲突，规定汉字国标码每个字节的最高位为“1”，即首位是“0”为字符，首位是“1”为汉字。这样的“国标码”就是汉字在计算机中的表示，也就是机内码。

另一种可以在计算机中表示汉字的编码为Unicode编码（Universal Multiple Octet Coded Character Set）。Unicode是国际标准组织针对各国文字和符号进行的、在计算机上使用的统一性字符编码，它为每种语言中的每个字符设定了唯一的二进制编码，以满足跨语言、跨平台进行文本转换、处理的要求。

字形码是确定一个汉字字形点阵的代码，字形点阵中的每个点对应一个二进制位。每个汉字对应一个点阵，再编上代号存入存储器中，这就是字模库。汉字在显示时需要在汉字库中查找汉字字模并以字模点阵码形式输出。

汉字的另一种显示方式是矢量汉字。矢量字库保存每一个汉字的描述信息，如一个笔划的起始、终止坐标，半径，弧度等。在显示、打印这一类字库时，需经过一系列的数学运算才能输出结果。

点阵字库的汉字由若干个点组成，当字体放大时，点会随之放大，使得字看上去比较“粗”。矢量字库保存的汉字理论上可以被无限放大，笔划轮廓仍然能保持圆滑清晰。打印时使用的字库均为矢量字库。Windows 使用的字库为以上两类，在操作系统的“WINDOWS\Fonts”目录下，如果字体文件后的扩展名为FON，表示该文件为点阵字库；若扩展名为TTF，则表示是矢量字库。

汉字信息从输入到输出的处理过程如图1-13所示。图1-13 汉字代码的处理过程1.3.4 声音与图像信息表示

计算机中存储和处理的信息除数值和文字外，还有各类被称为多媒体的信息，包括声音、图像和视频等。与数值和字符信息不同，这些信息都是连续变化的模拟信号，无法直接用计算机进行存储和处理，必须要首先转换为由0和1组成的二进制位串，这一过程称为数字化。

1.声音信息的表示

声音是通过空气传播的一种连续的波（Sound Wave，声波），它的连续性体现为幅值大小是连续的，可以是实数范围内的任意值；在时间上是连续的，没有间断点。我们将这种在时间和幅值上都连续变化的信号称为模拟信号。相应的，将时间和幅值都不连续的信号称为离散信号，如图1-14所示。图1-14 模拟声音信号和数字声音信号

要使声音信号能够被计算机处理，首先需要对起进行数字化，即将时间和幅值均连续变化的模拟声音信号，通过采样（Sampling）和量化（Measuring），转换为时间和幅值均不连续的离散信号，这种离散的声音信号称为数字音频信号，也就是计算机能够存储和处理的信号。

数字声音在计算机存储器中的存放形式称为声音文件格式。相同的数据，可以有不同的存放形式，所以，也就有多种文件格式，不同的格式其文件的扩展名不同（如*.WAV），每种格式都具有特定的应用场合。计算机中广泛应用的数字化声音文件有两类，一类是采集各种声音的机械振动得到的数字文件（又称为波形文件），其中包括音乐、语音及自然界的效果音等，另一类是专门用于记录数字化乐声的 MIDI 格式文件。常见的波形声音文件格式有WAV文件、MP3、RealAudio等。

•WAV格式是微软公司开发的一种声音文件格式，又称为波形声音文件，是最早的数字音频格式，被Windows平台及其应用程序广泛支持。主要用于自然声的保存与回放，其特点是声音层次丰富，还原性好，表现力强。如果使用足够高的采样频率和采样精度，可以获得极好的音质，但文件的数据量比较大。该格式的文件可以被几乎所有

试读结束[说明：试读内容隐藏了图片]

下载完整电子书