计算机科学的基本结构

计算机科学的基本结构

 

W.A.伍尔夫   M.肖

P.N.希尔芬格 L.弗朗

 

译者的话

   

         本书是一本计算机科学与软件工程的基础教材。它是由美国著名计算机科学家W.A 伍尔夫等人经过多年的科学研究和教学实践，在原讲稿的基础上不断充实修改而成的。

 

       本书按照程序设计技术与基本数学概念相结合的原则，全面系统地论述了控制结构、数据结构及其相互作用。本书在内容和结构上，新颖实用、深入浅出、注重理论在实际中的应用，它不仅适宜作为计算机科学和计算机软件专业的大学生或研究生的教材，而且对于计算机科学的研究人员和从事程序设计的各行业的科技人员，也是一本理想的参考书。

 

       全书共分四部分。第一部分（第一章至第六章）讨论基本控制结构，包括有限状态自动机、框图、程序设计语言中的控制结构等控制模型、控制的表示、程序的形式描述与证明、计算效率的测定等。第二部分（第七章至第十二章）讨论基本数据结构，包括数据数学模型、数据类型、抽象数据结构、数据的表示及其正确性的空间分析等。第三部分（第十三章至第十八章）讨论控制与数据的相互作用，包括计算模型与文法、标识符的解释、高级语言的运行时表示、递归、递归程序的证明、递归算法的分析等。前三部分是按数学模型、程序设计语言概念、表示、正确性、效率这样的顺序来论述的。第四部分（第十九章至第二十三章）是实例研究，通过几个实例说明前三部分内容在实际程序设计中的应用。前三部分每章末都附有文献概述，供读者进一步研究用。全书每章后都附有习题，这些习题大多是有使用价值的。

 

 

                                                                      序

 

       本书是计算机科学方面的一本中等程度的教科书。它适用于至少有一至两学期的程序设计和解题实践并想要研究较高级的计算课题的学生，当然，最好还学过一学期的离散数学。

 

       本书的内容和组织基于这样一个前提——程序设计是一门工程学科。同别的工程学科一样，程序设计与所构造的事物有关，尤其是与具有重大实际价值的实在事物有关；同时，也同别的工程学科一样，好的程序设计来源于科学的应用。掌握这门学科，对于一个好的程序员来说是必不可少的。

 

       本书也是有关“好的程序设计科学”方面的一本入门书，它包含了许多数学概念。传统上，我们仅把程序组织、数据结构、性能分析等软件概念当作程序设计技术进行教学，而在本书中，我们把程序设计思想同自动机、形式语言、数据类型这些基本数学概念联系起来描述这些程序设计技术，并通过例子来说明这些数学概念与实际构造的关系，以及如何把这些概念应用到实际构造中去。

 

      尽管本书中的许多材料曾按传统的方式作为大学高年级和研究生的课程进行过教学(以较深的程度)，但是我们认为，在开始阶段介绍这些材料是必要和适宜的。就象学习计算和物理是大多数工程学科的必备课程一样，这里给出的材料为软件工程和高级计算机科学课程奠定了一个适当的基础。这些材料的组织，见第xviii页的课题组织表以及该表前面的说明。

 

                                                    本书的用法

 

      最初我们曾把本书设计为计算机科学的一门选修课，自1974年以来，把它的多种版本作为大学二年级一个学期的课程讲授。

 

 

 

                             目录

前言

 

                     第一部分 基本控制结构

第一章 有限状态模型

第二章 其它控制模型：框图和程序

第三章 其它控制结构

第四章 控制的表示

第五章 程序的形式描述与证明

第六章 计算效率的测定

 

                   第二部分 基本数据结构

第七章 数据的数学模型

第八章 程序设计语言中的数据

第九章 抽象构造类型

第十章 数据的表示

第十一章 数据表示的正确性

第十二章 空间要求

 

 

                                前言

 

                     程序设计是一种工程活动

 

      程序设计是一种工程活动。因此，同其它好的工程一样，好的程序设计来源于把科学精心地应用到实际问题中去。然而，为了了解本书特有的内容和组织的理论基础，我们首先需要研究程序设计与其它工程相似及不同的方法。

 

      当然，计算机只是一种工具，但它是一种“通用”工具。因为它不仅仅是为解决某一个问题而设计的，而是专门用程序(计算机执行的一系列指令)来解决一个特定问题的。程序设计是编写程序的活动，实际上，它是构造一种专用工具的活动。正式这种对“构造事物”的腔调引出了我们的前提。

 

    然而，软件工程与其它各种工程质监有着重要的差别。

 

                           复杂性和抽象

 

    程序不是人类必须处理的唯一的或最复杂的系统。例如，国民经济就更复杂，即使一个简单物体中分子的运动也比最复杂的程序复杂得多。然而，人不能完全了解国民经济或分子结构的全部细节。为了处理复杂的情况，使用一个强有力的方法——抽象。我们情愿忽略复杂系统的细节，而建立只反映某些重要的宏观行为性质的模型。

 

                          抽象和结构

 

    在明确了抽象和模型的必要性以后，我们需要考虑如何构造好的抽象或模型。

 

 

                          好的程序设计方法

 

    构造一个好的程序是没有绝对规则可循的，而只有好的工程设计都必须具备的一般性质：它必须很好地完成它所要求的功能，而且必须是合算的。然而，有一组通常导致一个好的工程程序的一般准则。这些准则经常称为(1)结构程序设计学，(2)程序设计方法学，或(3)软件工程学。本书中的许多材料在于为这些学科提供坚实的基础。这是本书的主要观点。

 

 

 

                          第一部分  基本控制结构

 

      这是本书的第一部分，也是本书的主要部分。它涉及到程序中的控制概念。一个算法最基本的性质之一是按某种规定的次序安排所要执行的步骤。这种次序通常称为控制或控制流。首先，我们考虑有关控制的几个数学模型，证明所有这些模型都是“等价的”，而且我们可以对特定问题使用最佳模型。然后，我们讨论两个大家熟悉的程序设计概念——框图和程序设计语言的控制语句。它们也与控制的数学模型是“等价的”，而且我们可以用这种等价性来设计和解释实际的程序。

 

      第一部分的后几章提出了表示、正确性和效率的问题。第四章是关于表示，说明如何用机器语言来表示高级程序设计语言的控制结构。第五章是关于正确性，说明如何形式地定义语言的语义或意义。以及如何从数学上证明程序的正确性。第六章是第一部分的最后一章，说明如何分析程序的性能。

 

                            第一章 有限状态模型

 

      本章讨论一类简单的计算，它们是由术语“有限状态”来概括描述的。描述这类计算的结构有两种标准的方法：一种是把它描述为可运行的理想化机器。另一种是把它描述为可接受的输入集——称为“语言”。尽管看起来这两者有着本质的区别，但它们实际上是密切相关的。此外，从目前对控制的研究来看，这两种描述都具有不显含“存贮器”、“存贮”或“变量”概念的优点。

 

                           1.1 有限状态机

 

      考虑一个没有变量、过程调用或函数调用的程序。计算机执行这个程序唯一变化的信息是与程序的控制流有关的部分，即与它的步骤序列有关。确切地说，计算机只需记住程序中的当前步骤。程序本身决不改变，而是通过所提供的其它必要的信息来决定下一步做什么。我们把这样简单的程序稍加推广，就得到下列类似计算机的装置：有限状态机、有限自动机或时序机。

 

      考虑图1.1所示的装置。由于我们不知道它的内部结构，所以称它为“黑箱”。这个装置有一个输入机构和一个输出机构。它每次输入一项数据，并产生一个相应的输出项。

 

      我们称提供给输入机构的数据序列为输入流或输入带。类似的，我们称结果序列为输出流或输出带。单个的输入输出项称为符号，所有可能的输入项的集合称为输入字母表，所有可能的输出项的集合称为输出字母表。我们暂且把输入输出字母表限制在集合{0, 1}中，但并非必须这样限制不可。

 

      假定我们注视这个装置(我们称它为M1)在一段时间内的操作，并观察如下动作：

            输入：1101110101000...

            输出：0100110000000...

 

 

      状态不仅是贯穿于本书的最基本的概念之一，而且也是整个计算机科学中最基本的概念之一。它很值得详细讨论，以确保我们能直观地理解其含义。非形式的说，所谓“状态”我们是指情况或情形的一种概括。例如，美国总统每年提交一份国情咨文给国会，用以总结他所看到的国家情况。程序中的一个状态也是它的“情况”，这个“情况”是由程序的所有变量的值及其正在执行的点组成的。在后面各节理我们给出这一概念的更形式的定义，但这个形式行医是建立在更一般、更直观定义的基础上的。

     

1.1.1 状态转换函数

 

1.1.2 状态转换图

 

1.1.3 特殊的FSM：识别器和生成器；空转换

 

1.1.4 扩大输入和输出

 

                        1.2 非确定FSM

 

                        1.3 语言和正规表达式

 

1.3.1 语言

1.3.2 正规表达式

 

                        1.4 正规表达式与FSM的等价性

     

      这一节，我们证明一个可能使人感到意外的定理。

 

      定理 1.2 能用正规表达式表示的任何语言一定能被一个FSR所识别。

     

      碰巧，我们甚至还可以证明，由RE表示的语言类也等同于FSR所识别的语言类。为了证明这一点，也要求我们证明定理1.2的逆定理。就是说，我们必须证明对任意的FSR，都存在一个RE，它桥好描述由该FSR接受的语言，但我们对此并不很感兴趣，而且又感到相当棘手。

 

      这种构造证明法是程序员工具箱的一个重要部分。我们想通过下述证明使大家学会使用这种证明方法。

 

     

 

 

1.4.1 例子：从RE构造NDFSR

 

                        1.5 计算模型“能力”的描述

 

      在这节以至整本书中，我们不时涉及到象FSM这样的计算模型的“能力”问题。所谓模型的能力，我们只是指一个机器可实现的计算类，这个机器与这个模型的限制是一致的。

 

      在1.2节中，我们论述了FSR可以做NDFSR所能做的任何事情。

 

1.5.1 FSM的局限性

 

                         1.6 文献概述

 

      有限自动机与正规表达式已形成了一个重要的研究领域。这些主要的理论和结论以及大多数其它著作的文献目录，都可以在Minsky(1967), hopcroft(1969), Ullman(1969)和Salomaa(1973)中找到。在本书的第十九章中，读者将可以找到对有限自动机理论在程序设计中的一个传统应用的描述——词法分析。

     

      有限自动机和词法分析的进一步讨论可以在Aho和Ullman(1977)中找到。

 

                        习题

1.1 构造一个FSM，它具有输入字母表{0, 1}和输出字母表{0, 1}。它的动作如下：