第一章_newest

1、第一章 计算机与软件基础知识1.1 计算机的发明21世纪人类步入了信息社会，在信息社会里，通信技术是其特征，而计算机技术是基石。没有计算机技术的高速发展，就没有如今通信技术的辉煌成就。计算机技术的发展包含硬件方面的发展和软件方面的发展。人类产生用机器来帮助计算的想法由来已久。 古代的人们就开始用手指，结绳，算盘来辅助计数和计算。世界上最早的计算机实际上是一些简单的机械计算工具，中国的算盘可以说是最早的计算工具，而且使用周期之长无可比拟。在欧洲，17世纪出现了一种用于帮助计算乘法的骨质拼条，17世纪法国数学家帕斯卡（Pascal）和德国数学家莱布尼茨(Leibniz)曾设计出利用齿轮运算的手摇计

2、算机。这些都是计算机的雏形。在这些计算工具中，计算程式是一成不变的，使用者只能输入不同的数据，然后操作机器，等待输出。想要改变计算工具的计算程式，就只有重新设计制造一个计算工具。 到了19 世纪30年代，英国数学家巴贝齐(Babbage) 成功设计了由齿轮寄存器、运算器和控制器构成的分析机，其构成已经非常接近于现在的程序控制数字计算机。1944年美国人艾肯（Aiken）在IBM支持下利用继电器设计制造了一台通用程序计算机。后来法国科学家发明了一种齿轮式加减法器。而历史上第一台电子计算机ENIAC，在1946年2月诞生在美国宾西法尼亚大学的莫尔学院。 但学术界统一公认，电子计算机的理论和模型却是

3、由英国数学家图灵（Turing）在1936年发表的一篇名为“论可计算数及其在判定问题中的应用”的论文中提出的。在这篇本意是解决一个有关数理逻辑的纯粹数学问题的论文中，图灵提出了名为“图灵机”的抽象计算模型，现在看来， 它正是目前所有的数字计算机的基本原理性模型。在图灵思想的启发下，美国数学家冯·诺依曼几乎在与ENIAC发明的同一时期，设计了一种全新的程序存储式的数字计算机EDVAC。EDVAC方案的主要内容是确立了计算机由运算器、控制器、存储器、输入和输出五部分组成的设计思想， 明确反映出现代电子数字计算机的工作原理和基本结构，对以后计算机的发展产生了深远的影响。 今天人们把这种结构

4、称为“冯·诺依曼结构”或“指令存储结构”， 并把冯·诺依曼称为计算机的创始人。随着微电子技术的发展，出现了集成电路、大规模集成电路，微型处理器也被发明出来，计算机技术得到了迅猛的发展，计算机应用领域飞速拓宽。微型计算机的出现，一方面给自动控制领域注入了新的活力，使办公设备、家用电器电脑化；另一方面，个人计算机(PC机)的发明，解放了原本控制在大公司、大学和军事机构的计算能力，使普通大众受益于计算机。同时更加加速了计算技术的普及和发展。1.2 计算机的更新换代自世界上第一台计算机诞生后，计算机的发展速度异常迅猛，差不多每58年，计算机就要更新换代一次。每一次更新换代所带来的结

5、果是计算机的体积减小，速度加快，功能增强，价格下降，可靠性提高以及应用领域扩大。按照构成计算机的物理元件来区分的话，到目前为止，计算机可分为如下四代。第一代（19461958年），组成计算机的物理有源元件为电子管。计算机使用机器语言或汇编语言；计算机的应用主要面向科学计算。第二代（19591964年），组成计算机的物理有源元件为晶体管。操作系统开始引入，计算机软件编程开始采用高级语言；计算机的应用不仅面向科学计算，还能进行数据处理。第三代（19651970年），组成计算机的物理有源元件为集成电路。在程序设计中高级语言得到广泛地采用；计算机的结构趋于标准化；计算机的应用趋于通用化；它不仅可以进行

6、科学计算、数据处理，还可以进行实时控制。第四代（1971现在），组成计算机的物理有源元件为大规模、超大规模集成电路。计算机运行有了丰富的软、硬件环境；尤其是计算机网络与多媒体技术的实现，使得计算机成为现代化的多用途的计算和办公娱乐工具。进入90年代以后，计算机技术的发展进入了一个新时代，由于Internet的迅速发展，开放式的网络计算模式成为新的特点。计算机与网络已经密不可分，建立信息高速公路成为时代特征，人类迅速跨入信息时代。在计算机发展经历了四代的几十年中，尽管微电子技术的进步使得整机体积缩小，速度变快，新的应用领域不断拓展，但是基本的设计思想和工作原理一直限于图灵理论和冯·诺依

7、曼结构。现有的计算机虽然可以执行复杂的数学运算， 却无法有效的完成许多在人看来很简单的任务， 比如识别人脸，听懂语音等等。 一种理由是认为这些是图灵和冯·诺依曼结构的自身局限。在70年代虽然有人试图突破这一传统，一直没有获得真正的成功。但是到了80年代，在超大规模集成电路技术快速发展和各种应用背景的支持下，非冯·诺依曼结构的计算机体系智能计算机机的研究得到开展。与此同时，非图灵计算模型的研究也受到重视。有人把这些统统称为所谓的“第五代计算机”。 日本是“五代机”研制的积极倡导者和实践者。日本通产省于80年代初制订了宏伟的“五代机计划”，希望籍此使日本的科学技术进入国际领先地

8、位。 然而由于现代日本在重视发展工业技术和经济发展的同时， 忽略了基础科学理论的研究， 因缺乏先进的理论指导， 日本的计划最终宣告失败了，这当中的教训值得很多国家借鉴。 五代机计划失败后， 人们并没有放弃对新的计算模型和计算机结构进行探索。比如神经网络计算机、生物计算机、量子计算机等。有人也把它们称为“第六代机”， 仅仅是反映出它们希望用不同于冯·诺依曼的结构实现新型的计算机，能完成以前尚不能有效完成的任务。1.3 计算机的应用领域1科学计算最初计算机的发明纯粹是为了满足单纯计算的需要。第一台计算机ENIAC的主要使命是计算美国陆军的弹道参数。现在科学计算仍然是计算机的主要任务之一。

9、现代的生命科学、天体物理、大气科学、地球科学、物理学、化学、乃至数学和技术科学等的研究，都离不开计算机的帮助。利用计算机，可以在屏幕上试验核爆炸，或者仿真全球气候变暖等，这已经成为了非常有效的“第三种科学方法”。目前的研究热点在于实现并行分布式大规模的科学计算。2 事务数据处理 从科学计算到（事务）数据处理是计算机应用领域的第一次拓展。今天银行计算机系统每时每刻在处理大量的票据，商场管理系统有条不紊地管理着营销、库存和订货；图书情报系统不停的接待查询和处理。所有这一切都要经历数据的接收、产生、加工处理等手续。计算机已经是（事务）数据处理方面不可缺少的得力工具。3.计算机辅助设计与制造（CAD/

10、CAM） CAD/CAM 被评为20世纪后五十年中人类25个意义最重大的工程技术成就之一。由于CAD/CAM技术的发展和普及。在建筑工程、飞机制造、服装工业、电子工业等领域的产品设计和制造中，都已广泛使用这类系统，结果是大大提高了生产效率和产品质量。4.工业过程控制 今天许多的工厂、水电站、电网、城市交通、住宅小区等都采用了自动控制系统。许多先进的仪器仪表，家用电器等中也采用了以微处理器为中心的控制机构，并时时刻刻为人类的生产生活服务。5.网络与通信通过网络把分布在不同地理位置的计算机联系在一起， 这一方面加速了信息的共享和交流，另一方面从逻辑上形成了一台巨大的“计算机”，每台独立的计算机都是

11、这台大计算机的计算部件。不夸张的说，没有计算机网络技术和 Internet 的发展，就没有今天信息时代的到来。难怪以网络产品和工作站产品见长的SUN公司说：网络就是计算机。6家庭信息化与办公自动化 办公和家庭信息化自动化是与我们关系最密切的计算机的应用领域之一， 也是计算机技术普及的动力源泉之一。7 人工智能 人工智能是计算机应用的一个重要方向。早在发明计算机之前，图灵就讨论过了机器是否可能具有智能的问题。人工智能是研究使机器具有类似高等生物的智能的学科，研究如何才能使计算机模拟生物的智能行为。 在过去的几十年中， 人工智能在知识表达、自动推理、自然语言理解、机器学习、计算机视觉、机器翻译、机

12、器下棋等方面开展了大量研究，也取得了较多技术成果。但从本质上来说，图灵提出的问题还是一个悬而未决的谜题。但是无论如何，对智能问题的探索至少已经极大地促进了计算机学科的发展。 8 图形图象和多媒体技术从80年代中后期， 随着计算机一些分支学科的发展和计算机应用的普及，人们已经不满足只对字符、数据的处理。希望设法能对图形、图象、视频、文本等多媒体的数据同时处理，这成为计算机重要的新的应用方向。它涉及对多媒体数据有效的表示、识别、存储、加工和传输技术。图形学，虚拟现实，视频通信方面的研究日益受到重视。 1.4 计算机系统组成现在的计算机同第一台计算机相比，其组成和配置都发生了很大的变化。面对用户的不

13、止是简单的由电子线路组成的机器，而是一个复杂的计算机系统。一个完整的计算机系统包括硬件系统和软机系统，二者缺一不可。硬件（Hardware）是构成计算机系统的电子或机械的设备和部件的总称。一个计算机硬件系统，从功能角度而言可分为五大功能部件：运算器、控制器、存储器、输入设备和输出设备。硬件是计算机能够运行的物质基础，计算机的性能，如计算速度、存储容量和计算精度等，很大程度上都取决于硬件的配置。软件（Software）是为运行、维护、管理、应用计算机而编制的所有程序及相关文档的总称，一般认为软件是由程序、数据和文档三部分内容组成。计算机软件通常分为两类，一类是系统软件，另一类是应用软件。系统软件

14、是在计算机中配置的支撑计算机工作、提高计算机使用效率、实现计算机功能的基础软件，它为用户提供多种服务；应用软件是用户为解决各种实际问题而编写的软件。只用硬件而没有任何软件的计算机称为“裸机”。在裸机上只能运行机器语言程序，使用非常不方便，效率也低，所以早期只有少数专业人员才能够使用计算机。正是由于有了内容丰富、种类繁多的软件，使用户面对的不仅是一部“实实在在”的计算机，而且是包含许多软件的一台抽象的逻辑机（通常称之为“虚拟机”）。这样，人们可以采用更加灵活、方便、有效的手段使用计算机。从这个意义上，软件是用户和机器之间的接口，是软件在用户和计算机之间架起了桥梁。综上所述，计算机的硬件和软件共同

15、组成计算机系统，硬件是计算机的物质基础，没有硬件的支持根本谈不上软件的编制和执行；软件是建立在硬件基础上的，是计算机的灵魂，没有软件，计算机就无法工作，只有执行某种程序，才能使计算机发挥它的功能。计算机的硬件与软件相互依存，二者之间并没有一条明确的界限。一般来说，任何一个由软件完成的操作也可以直接由硬件来完成，而任何一个硬件所执行的指令也能够用软件来模拟实现。而且二者之间的界限也是经常变化的，随着大规模集成电路技术的发展，硬件更容易被用到对计算速度要求实时的场合。 与此同时，软件的类别和应用场合也在扩大。随着计算机技术的发展，软件与硬件相互融合、渗透，相互促进的趋势将愈来愈明显。计算机系统的组

16、成如图1-1所示。计算机系统硬件系统主机外设中央处理器(CPU)存储器内存RAM/ROM硬磁盘运算器控制器输入设备：键盘、鼠标、图形扫描仪等输出设备：显示器、打印机、绘图仪等外存储器：软磁盘、光盘等软件系统系统软件应用软件文字处理软件表格处理软件辅助设计软件实时控制软件操作系统DOSWndows 95/98/2000UNIX，Netware语言处理系统编译程序解释程序汇编程序系统服务程序监控测试程序连接编辑程序连接装配程序调试程序其它服务程序数据库系统OracleSybaseIBM DB2图1-1 计算机系统的组成图1.5 计算机硬件系统1946年，冯·諾依曼提出的“指令存储结构”工

17、作原理不仅使计算机能够自动连续运算，同时也确定了现代计算机的雏形。依照冯·諾依曼的思想，一台计算机主要有运算器、控制器、存储器、输入设备和输出设备五大部件组成。1. 运算器（processing unit）运算器是对数值型数据进行数学计算，对非数值型信息进行加工、处理的部件。经常进行的运算主要是算术计算和逻辑运算。因此运算器的核心是算术逻辑运算部件（Arithmetic and Logic Unit: ALU）。运算器中通常还包括若干寄存器，用于暂存数据。2. 控制器（Control Unit）控制器是控制、监督、协调各个功能部件的工作，使计算机本身运行过程自动化的控制部件。控制器从

18、主存中逐条取出指令进行分析、翻译指令码，安排操作顺序并向系统各部件发出响应的指令信号，指挥输入设备进行信息输入，指挥运算器对信息加工，指挥存储器对信息存储，指挥输出设备输出处理结果。当运行出现异常时，控制器将根据情况，控制转入相应的处理。3. 存储器（Memory）内存储器是设置在计算机内部存储数据和程序的部件，也称为主存贮器，简称内存。凡是需要在计算机中进行运算、加工处理的信息以及运算、处理的中间结果和最后结果都可以存储在这里，从计算机的运行速度和造价考虑，内存储器的容量是有一定限度的。为了扩大计算机的存储量，一般要在计算机外部再设置一个存储器，称为外存储器，也叫辅助存储器，比如软盘驱动器、

19、光盘驱动器等。4. 输入设备。 包括键盘、鼠标器、数字化仪、手写板、扫描仪、摄像机、语音话筒等。5. 输出设备。 例如 显示器 、打印机、绘图仪等。它们的关系如图1-2。输入设备存储器输出设备运算器控制器CPU程序数据运行结果数据数据指令控制信号数据信号图1-2 计算机系统硬件功能部件关系图这五大部件关系图及工作过程如下：（1）通过输入设备输入原始数据，计算程序以及给控制器的控制命令等。在控制器控制下，将有关部分存入存储器（存储程序）。（2）在控制器的控制下，从存储器读出一条指令到控制器，经译码分析发出控制信息，需要的话，还要从存储器读出数据到运算器。（3）运算器在控制器的控制下完成规定操作，

20、并将结果送回存储器或送到输出设备。（4）从存储器取出下一条指令，重复2、直至程序中包含结束指令为止。总结一下，目前的各种计算机系统，无论是简单的单片机、单板机系统，还是较复杂的个人计算机( P C 机)系统，以至超级计算机，从硬件体系结构来看，采用的基本上是计算机的经典结构冯·诺依曼结构。这种结构的要点是：l 由运算器、控制器、存储器、输入设备和输出设备五大部分组成。l 数据和程序以二进制代码形式不加区别地存放在存储器中，存放位置由地址码指定，地址码也为二进制。l 控制器是根据存放在存储器中的指令序列即程序来工作的，并由一个程序计数器(即指令地址计数器)控制指令的执行。控制器具有判断

21、能力，能根据计算结果的不同，选择不同的动作流程。1.6 计算机软件系统40年代50年代，计算机软件开发主要是用计算机的机器语言编程，机器语言是以处理机系统能够识别处理的指令系统中的指令作为逻辑语言的。而指令是由布尔量（“0”或“1”）组成的序列，用于直接控制处理机硬件的动作。指令系统一般是设备相关的，即每一类处理机都有它自己的指令系统，而且指令的设置没有任何规律可言，因而在这一阶段，针对某一处理机编写的程序，往往只能用于该类处理机系统，不能直接移植到另一种处理机的系统中去。而且由于指令没有具体含义，编写的程序一般是很难看懂的。要调试程序也是非常困难的。因此，这一阶段，程序的规模一般很小，指令的

22、数量较少。后来，人们发现可以采用比较易懂易记的符号来表示机器指令，即助记符，助记符编写的程序称为汇编语言，同时开发了把助记符编写的程序翻译成机器指令的汇编程序，才使程序的开发变得比较容易。但由于助记符与指令系统一一对应，不同的处理机系统的助记符集合和汇编程序都各不相同，因此机器语言和汇编语言都属于“面向机器的语言”，在编程时程序员必须清楚知道计算机系统的硬件资源情况，必须由专业人员从事开发，也没有软件开发技术这一概念的存在。这一阶段软件主要应用于科学计算等应用领域。60年代，出现了高级语言，所谓高级语言是指按一定的“语法规则”，由一些关键字符和数字及变量名称等字符串组成编程语言。这种语言是面向

23、应用的，即语言本身并不跟机器相关。程序员只要按照规定的法则，用字符串符号描述出他想计算机完成的处理步骤，就可以完成程序编写，剩下的事情都由编译程序或解释程序来完成。虽然高级语言的编译程序和解释程序仍然是机器相关的，但是只要为每一种机器类型都开发出一套维护这种高级语言的所有语法的编译程序或解释程序，那么用这种语言编写的程序就可以畅通无阻地运行在不同的处理机系统上面。因此，称这种语言是平台无关的。这一段时间里，计算机的应用范围大大扩充，大量进入商业应用。计算机的任务也已不单单是科学计算了，更多的用于数据和信息的处理。编程语言是汇编语言和高级语言并重。软件技术的发展方向是日益扩大系统规模，从而需要越

24、来越多的程序员投入到共同的项目中去。开发过程中的矛盾日益尖锐，由于系统庞大，程序开发人员之间的通讯、交流及后勤工作变得极其复杂，开发成功率大受影响。为此,人们开始考虑软件开发过程中的管理问题，并按照工程学的方法，提出了软件工程的概念。70年代，人们开始对经常碰到的一些编程要求进行总结，形成了数据结构和算法两个软件设计中的重要概念。通过对常用数据结构和算法的深入研究，使之达到最佳效率，即时间复杂度和空间复杂度的比例相对平衡，并形成一套完善的理论，从而可以为广大程序员直接利用，减少在程序开发中存在的大量重复操作。在软件设计方法方面，提出了瀑布模型等结构化设计方法。80年代软件技术的主要发展是关系数

25、据库的广泛应用，数据库技术的发展使得数据的存储和维护变得非常方便，数据的复用率也大大提高。数据库的应用也使得计算机的应用进一步扩展，包括银行、保险、民航及各种商业事务都把他们各自的问题转化为数字化形式，存储到计算机的数据库中进行处理。面向对象技术在这一时期开始成熟，为进一步扩大软件系统规模作出了巨大贡献。90年代是Internet时代，这一时代以信息高速公路为主要特点，计算机的处理对象面向多媒体发展。90年代初WWW技术的出现及URLs、HTML和HTTP等标准的诞生，使得Internet技术逐渐走向成熟并得到广泛应用。人们发现Internet蕴涵了巨大的商业价值，软件厂商们开始在Intern

26、et的新天地中争夺自己的领地，Internet相关软件大量诞生，推动人类社会迅速进入到信息时代。传统上把计算机软件分为两大类：系统软件和应用软件。1.6.1 系统软件系统软件是指管理、控制和维护计算机主机及外部设备，提供用户与计算机界面，以及各种服务性程序等支持计算机正常运作的通用软件。系统软件的功能和目的主要有以下几项 ： 提高硬件使用效率的功能；提供各种通用服务功能；提供与其他计算机或设备进行通信控制功能；提供系统监控、异常处理功能；提供软件编制环境功能等。常见的系统软件包括各种操作系统软件、数据库管理系统、网络支持软件、各种语言编译/解释程序。但是，也有不同的划分方式。比如有人就认为数据

27、库管理系统和语言编译/解释程序应该属于应用软件的范畴。1. 操作系统在计算机系统中，操作系统是最基本的、核心的系统软件。它是现代计算机系统中不可缺少的组成部分，是其他各种软件运行的基础。 操作系统的职能是控制和管理计算机资源，合理组织计算机的工作流程，使计算机系统发挥出更大效力，同时为用户提供一个功能强、使用便捷的工作环境。常见的操作系统有UNIX, Linux, DOS, Windows, OS/2 等。2. 数据库管理系统数据库管理系统（Data-Base Manage System, DBMS）是数据库及其管理系统的总和，其目标是针对大量需要在计算机中处理的数据，解决如何进行合理存储、科

28、学管理，保证数据的安全性、完整性和保密性，并为使用者提供便捷的使用途径和方法。它和操作系统一样具有同等重要的地位，是管理数据资源，使之发挥更高效益，并达到资源共享的有利工具，常见的DBMS有 Oracle, Sybase, Informix, SQL server, mySQL 等。3. 解释与编译系统用汇编语言和高级语言编写的程序是不能在计算机上直接执行的， 必须先将它们翻译成机器码才能在计算机上执行。高级语言的翻译执行方式主要有两种， 一是解释执行，二是编译执行。 前者是对高级语言一边逐句翻译， 一边逐句执行。 后者则借助编译程序把高级语言书写的程序进行整体上的识别与理解， 然后再统一执行

29、。1.6.2 应用软件应用软件是指专门为解决某个领域的具体问题而编制的软件。应用软件是多种多样的，在每个领域都有自己的应用特点。从技术特点可分为以下几类：1. 科学计算软件实现计算机最基本的功能，传统的应用领域注重数值算法的速度和精度，目前已经趋向网络多机协作计算，并行计算等新技术的开发应用。2. 文字处理软件进行非数值型数据的处理工作，具有文字输入、编辑、排版、存储和打印等功能。常用的文字处理软件有WORD, WPS等。3. 信息管理软件用于管理信息的输入、存储、修改、检索和打印等。其特点是有一个或多个数据库，存放各种数据信息，其技术重点是数据库应用，并构成一个完整、高效的管理信息系统（Ma

30、nagement Information System：MIS）。4. 计算机辅助软件主要包括计算机辅助设计（CAD）计算机辅助制造（CAM），计算机辅助教学（CAI），以及计算机辅助分析（CAA）以及决策支持系统(DSS)等方面的软件。5. 多媒体软件用于处理图像、图形和语音等多媒体信息的软件，比如Media-Player, PHOTOSHOP, AutoCAD, 3DMAX 等。6. 实时控制（Real time Control）软件用于监控、分析、控制实时事件的软件。它包括从外部环境收集信息，经分析后按应用要求转移信息，并在处理后响应到外部的输出，以监控部件保证按时间要求做出反应。一般多

31、用于工业控制系统。7. 网络软件以网络技术中心的数字化革命正在引起一场新的社会和经济的高速发展，引发了以知识和信息为基础的信息时代的到来。网络通信软件，如TCP/IP, Internet的软件发展成重要的软件。8. 人工智能软件用计算机实现模仿人的智能的软件，使之成为聪明的灵活的计算机。例如实现模式识别功能的软件，自然语言理解的软件，专家系统软件，计算机下棋，机器人软件，神经网软件，自动推理软件等。 1.7 信息、数据与数据处理1.7.1 信息、数据、数据处理的概念 数据是指能够输入计算机并能被计算机处理的数字、字母和符号。数据对象的表示形式是多种多样的，可以是数值、图形、图像、声音等。它是用

32、来描述人们所看到的景象和听到的客观情况的某种物理符号的序列。数据有两种形态。一种是人们可读形式的数据，简称人读数据；另一种形态为机器可读形式的数据，简称机读数据。数据是由人类首先进行收集、整理、组织和使用的，从而形成了人们特有的语言、文字、数字以及图像等。例如，图书、资料、声像制品等，都是特定的人群才能理解的数据。信息是事物状态及其运动方式的表现形式。信息和数据是两个不可分离又有区别的概念。数据是信息的载体，而信息是对数据的解释，是消化了的数据。信息不随载荷它的物理设备的改变而改变，而数据往往和所用的计算机系统有关。信息是经过加工整理并对人类社会实践、生产和经营活动产生决策影响的数据。所以，只

33、有通过对数据的去粗取精、去伪存真的加工整理，数据才能发生质的变化而成为信息，给人以新的知识和智慧，从而影响着人类的精神文明和物质文明活动。数据处理是对各种类型的数据进行收集、存储、分类、加工、检索、优化和传输的过程。通常，人们将数据处理也称为信息处理。数据处理的数学基础来自于离散数学和数理逻辑等相关课程的知识。 其中以集合论、布尔代数、关系运算和图灵机和数学归纳法最为重要。 关于前面三者， 已经在有关课程中学过了， 这里重点介绍图灵机和数学归纳法的概念。1.7.2 计算模型与图灵机所谓计算模型是描述计算这一概念的一种抽象的形式系统或数学系统，而算法是对计算机过程步骤（或状态）的刻划，是计算方法

34、的一种可行的实现方式。由于观察计算的角度不同，产生了各种不同的计算模型。例如，递归函数是将可以计算的问题用函数来表示，从考察可以计算的函数应具有怎样的构造入手研究计算，而图灵机则是从计算的一般化过程来研究计算。在递归函数的研究中，从少数几个初始函数出发，通过有穷次的使用函数的代入运算、复合运算、以及原始递归等运算，就可以构造出大量复杂的函数。初始函数可以采用下面的几个简单的函数：l s(x) = x + 1 (后继函数)；l o(x) = 0 （零函数）l U j (n) ( x 1 , x2 , , x n ) = x j (投影函数)。由于初始函数十分简单，它们显然都是可以计算的（即是用笔

35、和纸经有穷次运算就可以求得函数值）。因此，如果能够保证今后使用的函数的代入运算、复合运算、以及原始递归等运算都是可行的可计算的（比如使用笔和纸进行计算，或用图灵机可计算），那么，我们就可以构造出大量可以计算的函数。换言之，我们希望把一个函数是否可计算的判定问题归结为对函数的构造性的研究。早期，可计算性理论中关于递归函数理论的研究是先于图灵机建立的，但后来，在图灵机出现之后，关于可计算性理论的研究更多转向对以图灵机为基础的可计算性研究。 至50年代，后人已经比较完整的建立了图灵机与递归函数之间的对应关系。下面，我们简单介绍图灵机的基本概念。图灵机是由20世纪英国数学家图灵创造的一种计算模型，它可

36、以确切地表达计算、可计算函数和计算复杂度等基本概念，也是描述NP复杂性问题的基本工具。图灵机由一条两端都无限延伸的带子， 一个读写头和一组控制读写头的命令集（控制器）所组成，如图1-3所示，这条带子上划分了无穷多个可写、可擦的小格子，读写头可以沿带子的方向左右移动并且在格子上读写，（类似录音机中的磁头与磁带的关系） 每个图灵机有一个状态集Q, 其中包含一个开始状态， 一个结束状态， 还有一个符号集S, 一般只用0和1 两个符号 ，其中一个是空白符号，用 0 表示。读写磁头符号带 图1-3 图灵机模型图灵关于计算的精确定义实质上是模拟人的动作，它有几个限制条件，但是这并不影响问题的实质。（1）

37、将运算介质确定为一维的线性带子（不是二维的纸），带子可想象为磁带，并且被划分为无穷多个方格。（2） 规定一次只注视一个符号，“注视”由读写磁头执行。有一组运算法则存放在“有限状态控制器”中。 控制器根据当前“状态”和磁头注视的“符号”决定下一步动作。磁头每次只能动一步，并只能移动左右相近方格上。图灵机的计算步骤如下： 根据有限控制器的当前状态，以及每次磁头所注视的带上的符号，执行以下操作。（1）改变有限控制状态。（2）在磁头所指的单元内，擦去当前的符号，印上新的符号。（3）磁头不相关地向左移动一格（L）或向右移动一格（R）或保持不动（S）。因此可以用七元组 （Q, T, I, F, b, qo

38、, qf）形式表示图灵机其中，l Q是状态的有限集合；l T是带上的符号的有限集合；l I是输入符号的集合，IÍT;l b 是空白符，bT - I;l qo是初始状态；l qf 是最后（接受）状态；l F 是转移函数 我们前面提过，所有的现代数字计算机都是以这样一个看似十分简单的图灵模型为理论基础。无论任何多么复杂的问题，只要能在现有的某种型号的数字计算机上实现， 都可以用图灵机这样一个简单的计算机构实现，这多少有些令人吃惊，但也正是图灵的研究的意义所在。1.7.3 图灵机与自然数传统的图灵机计算模型是定义在非负整数集上的一种计算机器，是现代数字计算机的理论基础。 现代的数字计算机虽

39、然能够处理包括有理数，实数等在内的大得多的数域， 然而其运算的根本基础还是图灵模型。 特别是有关自然数集和定义在自然数上的运算是许多计算方法的基础。由所有的自然数组成的集合称为自然数集，即 1，2，3，4，5， ， 自然数集是一个无限集。 由自然数组成的数的集合都是自然数集的子集， 它们可以是有限集，或者无限集。与自然数集对等（即具有相同浓度）的集合称为可列集（可枚举集(Enumable), 或可数集（Countable）。 任何一个可列集中的元素排列时可标以正整数下标，即M = a1, a2, a3, a4, a5, , an, 关于自然数集及其子集， 有以下两个命题成立。命题1 ：在自然数

40、集的任一非空子集M中，必定有一个最小的数。即在M中存在一个不大于其他任何数的数。证明 ：因为M非空，所以在M中可取得一自然数n , 显然， M中所有不大于n的自然数形成的非空集 N 包含在M中。如果N 中有最小数， 则此最小数就是M的最小数。而N中最多有n个自然数，从小到大的标号为1 到n , 因此N 中存在最小数。综上，M 中一定存在最小的书， 命题得证。 命题2 ：假定M 是由自然数组成的集合， 如果它含有1, 2, 3, k, 并且当它含有 n-1, n-2, n-3, , n-k , (n>k) 时， 也含有n, 则它含有全体自然数， 即 M 是自然数集。 证明：假设M 不包含全

41、体自然数， 设 N 是由不在M 中的全部自然数组成。 则设 N 非空， 由命题1， 得知N 中存在最小数c, 因此c-1, c-2, ,必不属于N , 因而c-1, c-2,必属于M。 而根据本命题的前提，c 应该属于M , 导出矛盾。 于是假设是错误的， 即 M 应包含全体自然数，命题得证。以上两个命题是自然数的数学归纳法的基础，也是图灵机计算的理论基础之一。1.8 算法、程序与软件根据上面的讨论我们知道软件是计算机科学的重要组成部分。 计算机科学是研究信息描述和信息变换的算法的科学， 这当中包括理论分析、设计、效率分析、实现和应用系统的研究。算法问题被认为是计算机科学的核心问题。算法的定义

42、是：一个算法，就是一个有穷规则的集合，其中的规则定义了一个解决某一特定类型问题的运算序列。此外，算法的规则序列必须要满足如下五个条件：（1）有穷性：算法必须在执行有限步后结束。（2）确定性：算法的每一个步骤必须有确切的定义 。（3）输入：算法有零个和多个输入。（4）输出：算法有零个和多个输出， 该输出要和输入有一定的关系。（5）可行性：算法中的运算和操作必须是足够基本的， 就是说， 它们原则上能够被计算机精确的执行。有穷性和可行性是算法最重要的两个特征。对有些问题来说，如果我们给出了一个类似于算法的有穷运算序列，而它对某些输入可能不停机，那么，我们就称这样的运算序列为一个过程。算法与过程都满足

43、可行性和确定性，唯一的本质区别是算法具有有穷性，而过程可以永不停机。需要指出的是，在高级程序设计语言中，也有“过程”这一术语，但与这里提到的过程不同，那里实际指的是子程序的概念。 一般来说，对一个问题，如果已经有了解决问题的算法，就可以编制相应的程序。所谓程序，就是一种事先被编制好的具有特定功能的指令序列。这里的指令序列可以是机器指令序列，也可以是高级语言序列。 最初程序设计是一种个人的技艺。但随着问题的复杂化和设计方法的变化，产生了研究如何提高程序设计的效率， 并验证程序正确性的学问，这就是程序设计方法学。为解决不同的问题，实现不同的应用，人们编制了各种各样的计算机软件。所谓软件，是对事先被

44、编制好具有特定用途的程序（代码和数据），及其说明文档的通称。 软件本身也是一个动态发展的概念。1983年，IEEE 组织给软件下了一个新颖的定义：软件是计算机程序、方法、规范及其响应的文档以及在计算机上运行所必须的数据的全体。19 软件基础的内容组成1.计算机语言计算机发明最初，程序是用机器码编制。所以人们普遍感到，这样要求程序员对不同的机器要记忆复杂的机器指令，编程效率十分低下，而且难以交流和维护，调试程序也十分困难。后来改进为汇编语言，主要用类似英文单词的指令助记符和宏扩展（Macro）来方便记忆，这得到了广泛的应用，（甚至今天仍然在使用， 因为汇编代码与机器码对应， 因而执行效率高） ，

45、但是它仍然没有摆脱与机器码一一对应的本质。软件开发急需用一种类似人类语言的方式来实现人机交流，这导致了高级语言的发明。 1952年第一个高级语言ShortCode发明，随后著名的FORTRAN 语言被发明出来，在世界范围获得普遍的应用。Algol-60的出现把计算机语言确立为专门的计算机学科。在接下来的时间里，又发明了结构化的Pascal、C 语言，用于人工智能研究的LISP、Prolog, 面向对象的SmallTalk, C+ 等。今天，高级语言的设计和使用已经成为计算机软件学科中重要的基本内容之一。在大学阶段，我们主要通过“程序设计”和“算法语言”等课程来学习相关知识。2.数据结构与算法数

46、据结构是计算机软件设计和应用的重要基础。它主要研究数据的表示与存贮的方法、抽象的数据结构， 以及定义在上面的操作。 数据的逻辑结构通常用抽象的离散数学结构来描述，比如用串、表、链、树和图等结构来实现抽象逻辑操作和具体的物理存储操作。数据结构的研究要同作用在其上的算法研究结合起来进行。算法包括以科学计算为目的的数值算法和与数据结构相关的非数值算法。在软件基础课程中我们主要学习后者。要学习常用的基本的数据结构的操作、数据排序、查找等内容，同时学会对算法时空性能（复杂度）的分析方法。 著名的 计算机科学家 Knuth 的名著计算机程序设计的艺术是这方面的重要参考书。3.程序设计与软件工程在计算机发展早期，编程基本上是个人行为，编程更象是一种个人的技艺，不同人设计的程序差异很大，很难被别人读懂，更难于维护。直到六七十年代，关