复习《计算机导论》复习提纲

《计算机导论》复习纲要2010/6/2108:52第1章绪论1、第一台计算机；2、计算机发展的五个阶段；第一代（1945~1957）：电子管计算机（VacuumTubes）第二代（1958~1963）：晶体管计算机（Transistor）第三代（1964~1969）：小规模集成电路计算机IntegratedCircuits第四代（1970~1990）：以微处理器（Microprocessors）为标志的大规模/超大规模集成电路（LSI/VLSI）计算机（Large-scaleIntegratedCircuits）第五代（1991~目前）：以互联网（Internet）为标志的信息系统3、计算学科的定义计算学科是对描述和变换信息的算法过程，包括对其理论、分析、设计、效率、实现和应用等进行的系统研究。4、计算学科的根本问题计算学科的根本问题是：什么能被（有效地）自动进行。计算学科所有分支领域的根本任务就是进行计算，其实质就是字符串的变换。5、计算学科的5个分支学科计算机科学（ComputerScience，简称CS）信息系统（InformationSystem，简称IS）软件工程（SoftwareEngineering，简称SE）计算机工程（ComputerEngineering，简称CE）信息技术（InformationTechnology，简称IT）6、学科知识体计算机科学知识体由以下3个层次构成：（1）最高层是分支领域（area），它代表一个特定的学科子领域。（2）分支领域之下又分为更小的知识单元（unit），它代表该领域中的主题模块。（3）知识单元又被细分为众多的知识点（topic），这些知识点构成了知识体结构的最底层。7、计算机科学二维定义矩阵三个过程主领域抽象理论设计离散结构(DiscreteStructures)

程序设计基础(ProgrammingFundamentals)

算法和复杂性(Algorithms&Complexity)

计算机结构与组织(Architecture&Organization)

操作系统(OperatingSystems)

网络计算(NetworkComputing)

程序设计语言(ProgrammingLanguages)

人-机交互(Human-ComputerInteraction)

图形学与可视计算(Graphics&VisualComputing)

智能系统(IntelligentSystems)

信息管理(InformationManagement)

软件工程(SoftwareEngineering)

社会和职业问题(Social&ProfessionalIssues)

科学计算(ComputationalScience)

计算机科学二维定义矩阵是学科概念的认知模型。“纵向”关系，即计算机科学的研究领域。这些内容蕴含在学科3个过程中，并将学科各分支领域结合成一个完整的体系，而不是互不相关的领域。“横向”关系，即抽象、理论和设计3个过程的关系，是定义矩阵中最为重要的内容。它反映的是，人们在计算领域的认识规律，即是从感性认识（抽象）到理性认识（理论），再由理性认识（理论）回到实践（设计）的过程。“横向”关系还蕴含着学科中的基本问题。抽象、理论和设计3个过程（1）理论源于数学。应用数学家们认为科学的进展都是建立在数学基础之上。它的研究内容表现在两个方面：一方面是建立完整的理论体系，另一方面是在现有理论的指导下，建立具体问题的数学模型，从而实现对客观世界的理性认识。（2）抽象源于现实世界。抽象建模是自然科学的根本。（3）设计源于工程。设计是工程的根本。8、摩尔定律和“贝尔定律”在体系结构方面，有所谓“摩尔定律”（Moore’sLaw）和“贝尔定律”（Bell’sLaw）。前者断定微处理器的速度会每18个月提升一倍，而后者则认为如果保持计算能力不变，微处理器的价格和体积每18个月缩减一倍。第2章计算学科的基本问题什么是科学问题？科学问题是指一定时代的科学认识主体，在已完成的科学知识和科学实践的基础上，提出的需要解决且有可能解决的问题。它包含一定的求解目标和应答域，但尚无确定的答案。罗素悖论罗素悖论的表现形式：在对结果的观察中同时包含了观察者自身的行为，就会出现悖论。也就是说，理性无法回答关于自身的问题。希尔伯特纲领希尔伯特在数学基础的研究中提出了一个设想：将每一门数学的分支形式化，构成形式系统或形式理论，并在以此为对象的元理论即元数学中，证明每一个形式系统的相容性，从而导出全部数学的相容性。他企图寻找通用的形式逻辑系统，在该系统中，可以机械地判定任何给定命题的真伪，即该系统是完备的。任何系统的完备和一致性，可以由系统本身得到证明。希尔伯特这一设想，就是所谓的“希尔伯特纲领”。库尔特·哥德尔（K．Godel）提出的关于形式系统的“不完备性定理”中指出：形式系统不能穷尽全部数学命题，任何形式系统中都存在着该系统所不能判定其真伪的命题。没有一种公理系统可以导出数论中所有的真实命题，除非这种系统本身就有悖论。“哥德尔第一定理”，即哥德尔的“不完备性定理”：一个形式系统，如果是一致的（=相容的=无矛盾的），那么，就一定存在一个命题，这个命题在该系统中不能被证明，也不能被否证。换一种说法，这个命题在该系统中不能被证明，它的反命题在该系统中也不能被证明。“哥德尔第二定理”，即：任何一个被认为是一致的系统，它的一致性是不能在系统内部得到证明的。因此：形式系统是不完备的2.2哥尼斯堡七桥问题欧拉回路欧拉给出了哥尼斯堡七桥问题的证明，还用数学方法给出了三条判定规则(判定每座桥恰好走过一次,不一定回到原点,即对欧拉路径的判定)：（1）如果通奇数座桥的地方不止两个，满足要求的路线是找不到的。（2）如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线。（3）如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。根据第3点,可以得出,任一连通图存在欧拉回路的充分必要条件是所有顶点均有偶数度。哈密尔顿回路问题：在某个图G中，能不能找到这样的路径，即从一点出发不重复地走过所有的结点，最后又回到原出发点。这个问题也被称作周游世界问题。“哈密尔顿回路问题”与“欧拉回路问题”的不同点“哈密尔顿回路问题”是访问每个结点一次，而“欧拉回路问题”是访问每条边一次。对图G是否存在“欧拉回路”前面已给出充分必要条件，而对图G是否存在“哈密尔顿回路”至今仍未找到满足该问题的充分必要条件。计算问题可以分为可计算问题与不可计算问题。可计算问题：存在可解的算法。不可计算问题：不存在可解的算法。梵天塔问题说明了：理论上可以计算的问题，实际上并不一定能行，这属于算法复杂性方面的研究内容。算法复杂性中的难解性问题、P类问题和NP类问题算法复杂性包括算法的空间以及时间两方面的复杂性问题。在计算复杂性理论中，将所有可以在多项式时间内求解的问题称为P类问题，而将所有在多项式时间内可以验证的问题称为NP类问题。证比求易算法在计算机科学中，一般认为求解一个问题往往比较困难，但验证一个问题就比较简单。顺序算法和并行算法当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行执行的操作，从而大大地限制了并行计算机系统的加速能力。阿达尔定律（参看书本）一个不可计算问题：停机问题停机问题（HaltingProblem）是1936年图灵在其著名论文《论可计算数及其在判定问题上的应用》中提出，并用形式化方法给予证明的一个不可计算问题。停机问题引出了一个悖论——当一个程序无限循环时才会停机，并且当它停机时才会无限循环。什么是形式化方法：引入表达形式结构的符号语言,用符号与符号之间的联系表达命题或推理的形式结构。找零问题、背包问题与贪婪算法一类可以用启发式的贪婪算法来处理的典型问题。1.找零问题2.背包问题“哲学家共餐”问题与计算机资源管理计算机的资源分软件资源和硬件资源。硬件的资源主要指CPU、存储器以及输入和输出设备等；软件资源则是指存储在存储设备里面的各类文件。在计算机中，操作系统负责对计算机软硬资源进行控制和管理，要使计算机系统中的软硬件资源得到高效的使用，就会遇到由于资源共享而产生的问题。“哲学家共餐”问题哲学家进餐问题在计算机科学中所反映的问题实际上是程序并发执行时进程同步的问题：为了提高系统的处理能力和机器的利用率，并发程序被广泛地使用，因此必须彻底解决并发进程中的死锁和饥饿问题。并行处理并行计算时的完整性和同步性出现了问题。生产者－消费者问题一个生产者和一个消费者以及一个硬件资源。所谓消费者是指使用某一软硬件资源时的进程，而生产者是指提供（或释放）某一软硬件资源时的进程。一个重要的概念，即信号灯，它借用了火车信号系统中的信号灯来表示进程之间的互斥。生产者－消费者问题例如：大型数据库的共享、联网的售票系统、火车（航班）进出管理系统2.6“两军问题”与计算机网络计算机网络的定义计算机网络是将分散在不同地理位置上的，具有独立功能的多台计算机系统、各种终端设备、外部设备及其它附属设备，通过通信设备和通信线路连接起来，在网络协议和网络操作系统的管理和控制下，实现数据通信、资源共享和分布处理的系统。计算机网络发展的四个阶段计算机网络的发展，大致经历了四个阶段：1.远程终端联机阶段2.计算机网络阶段3.网络互连阶段4.信息高速公路（互联网）阶段计算机网络的功能资源共享、信息传输、提高系统的可靠性、分布处理，系统便于扩充。计算机网络的分类1.根据组成计算机网络的地理范围大小的不同，可分为广域网（WAN）、城域网（MAN）和局域网（LAN）三种。2.按网络的使用范围划分，可将计算机网络分为公用网和专用网。计算机网络的组成计算机网络由计算机通过通信线路互连而成，用户通过终端访问网络。从组成网络的设备或系统功能看，计算机网络由通信子网和资源子网构成。计算机网络的拓扑结构局域网中，构成网络服务器、工作站（又称节点）等设备通过电缆在物理上互连的几何构形，称为网络的拓扑结构。信道信道是指信号的传输通道，可分为物理信道和逻辑信道。其中，物理信道是指用来传递信号的一条物理通道，由传输介质和相关设备组成。按照传输方式分，信道可分为两类：点到点信道和广播信道。按使用的传输介质不同，信道可分为有线信道和无线信道。有线信道可以是架空明线、同轴电缆、光钎电缆及微波导管等信道。无线信道可以是微波信道、短波信道等。信道所能传送信号的频率宽度（即可传送信号的最高频率和最低频率之差）称为信道的带宽。网络协议计算机网络为了进行网络中的数据交换而建立的规则、标准或约定称为网络协议。网络协议规定了有关功能部件在通信过程中的操作，规定了传输数据的格式和有关的同步问题。网络的标准化组织为计算机网络制定标准的组织主要有三个：⑴国际标准化组织ISO⑵国际电子电器工程师协会IEEE⑶ARPA（AdvancedResearchProjectsAgency）参照计算机系统多层体系结构的原理，网络系统的通信结构也采用分层结构的方法。开放性系统互连（OSI）的参考模型局域网协议的标准IEEE802局域网的标准是由IEEE802制定的。IEEE802的标准只定义到最低两层，即物理层与数据链路层，较高层的功能则留给网络厂商决定。其中，数据链路层中又可分成两个子层：①逻辑连接控制LLC（LogicLinkControl）：让上层的网络在使用网络服务器时不必去考虑其下层是如何设置的。②介质存取控制MAC（MediumAccessControl）：定义多种不同的存取控制方法，以决定如何控制实际传送介质的使用。TCP/IP通信协议TCP/IP（TransmissionControlProtocol/InternetProtocol）是美国国防部早期为开发ARPANET的协议，提供连接不同厂家计算机主机的通信协议。TCP/IP主要有两个协议：①网际协议（IP）：制定所有在网络上流通的包标准，提供跨越多个网络的单一包传送服务。②传输控制协议（TCP）：在网际协议（IP）的上面，提供面向连接的可靠数据传输服务。确保所有送到某个系统的数据能正确无误的到达该系统。互联网软件的分层结构第3章3个学科形态信息系统模型信息系统是一个人造系统，它由人、计算机硬件、软件和数据资源组成，目的是及时和正确地收集、加工、存储、传递和提供决策所需的信息。与系统模型类似，信息系统包括输入、处理、输出和反馈4个部分。数据库系统数据库系统：DatabaseSystem构成数据库系统的有四个部分：数据、数据库管理系统、应用软件和用户DBMS，DatabaseManagerSystem，数据库管理系统DBMS由以下几个部分构成1．物理数据库2．数据库引擎3．数据库模式 DBMS支持的功能数据定义数据操纵：一般是指用来查询、添加、修改和删除数据库中数据数据控制：设置或者更改数据库用户或角色权限系统存储过程：目的在于能够方便地从系统表中查询信息，或完成与更新数据表相关的管理任务，包括系统管理任务DBMS还包括数据字典数据库体系结构和数据库模型数据库的体系结构——建立数据库的一个框架，这个框架用于解释数据库，也用于描述数据库的概念。而组织数据库中的数据，是数据库管理系统的核心，即DBMS所采用的数据库模型数据库的三级体系结构计算学科中理论、抽象和设计3种主要形态（过程）抽象形态包括以下4个步骤的内容：（1）形成假设；（2）建造模型并作出预测；（3）设计实验并收集数据；（4）对结果进行分析。理论形态包括以下4个步骤的内容：（1）表述研究对象的特征（定义和公理）；（2）假设对象之间的基本性质和对象之间可能存在的关系（定理）；（3）确定这些关系是否为真（证明）；（4）结论。设计形态包括以下4个步骤的内容：（1）需求分析；（2）建立规格说明；（3）设计并实现该系统；（4）对系统进行测试与分析。设计、抽象和理论3个形态针对具体的研究领域均起作用，在具体研究中，就是要在其理论的指导下，运用其抽象工具进行各种设计工作，最终的成果将是计算机的软硬件系统及其相关资料（如需求说明、规格说明和设计与实现方法说明等）。计算机语言的发展1.低级语言：机器语言汇编语言2.高级程序设计语言FORTRAN语言BASIC语言COBOL语言Pascal语言C语言语言处理程序1.汇编程序汇编语言翻译系统汇编语言翻译系统的主要功能是将用汇编语言书写的程序翻译成用二进制码0或1表示的等价的机器语言，形成计算机可以执行的机器指令代码。2.编译程序编译程序以高级程序设计语言书写的源程序作为输入，而以汇编语言或机器语言表示的目标程序作为输出。3.解释程序解释程序是按照源程序中的语句的动态顺序逐条翻译成机器代码并立即执行相应功能的处理系统。也称为高级程序设计语言解释系统由于解释程序它的方便性和交互性较好，早期一些高级语言采用这种方式，如BASIC、dBASE。但它的弱点是运行效率低，程序的运行依赖于开发环境，不能直接在操作系统下运行。自然语言自然语言是某一社会发展中形成的一种民族语言。例如，汉语、英语、法语和俄语等。其最基本、最普遍的形式是文字，文字是人类最普遍使用的自然语言符号系统。自然语言符号系统的基本特征：歧义性、不够严格和不够统一的语法结构。高级语言的歧义性问题高级程序设计语言也有语义的歧义性问题，但是高级程序设计语言存在较少的歧义性。形式语言人们在自然语言符号系统的基础上，逐步建立起了人工语言符号系统（也称科学语言系统），即各学科的专门科学术语（符号），使语言符号保持其单一性、无歧义性和明确性。人工语言符号系统发展的第二阶段叫形式化语言，简称形式语言。图灵机图灵的观点及结论：凡是能用算法方法解决的问题，一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。与图灵机等价的计算模型：递归函数、λ-演算、POST规范系统从可计算理论可知每一个原始递归函数都是图灵机可计算的。冯•诺依曼型计算机：从原来对程序和数据的严格区别到一样看待，这个观念上的转变是计算机史上的一场革命，它反映的正是计算的本质，即符号串的变换。按照冯▪诺依曼原理构造的计算机又称冯▪诺依曼计算机，其体系结构称为冯▪诺依曼结构。冯▪诺依曼计算机的基本工作原理是存储程序和程序控制，其特点如下：将计算过程描述为由多条指令按一定顺序组成的程序，并放入存储器保存。指令按其在存储器中存放的顺序执行；控制器控制整个程序和数据的存取以及程序的执行；冯·诺依曼计算机的体系结构冯·诺依曼计算机的体系结构，即存储程序式计算机的体系结构，是将程序与数据一样看待，对程序像数据那样进行适当的编码，然后与数据一起共同存放在存储器中。这样，计算机就可以通过改变存储器中的内容，对数据进行操作。(1)计算机由运算器、控制器、存储器、输入设备和输出设备5大部分组成。控制器和运算器是其核心。(2)按存储程序原理进行工作。数据和程序以二进制代码形式不加区别地存放在存储器中，存储器是按线性编址的唯一结构进行地址访问，每个单元的位数是固定的。(3)机器以运算器为中心，输入输出设备与存储器间的数据传送都经过运算器。通过执行指令直接发出控制信号控制计算机的操作。(4)控制器根据存放在存储器中的指令序列（程序）进行工作，并由一个程序计数器控制指令的执行。(5)指令由操作码和地址码组成。指令同数据一样可以送到运算器进行运算，由指令组成的程序是可以修改的。冯·诺依曼型计算机体系结构图如下所示：输入设备和输出设备作用：是将信息输入计算机和输出计算机。存储器存储器是一种数据或信息的存储部件，它分成很多存储单元，并按照一定的方式进行排列。每个单元都编了号，称为存储地址。指令和数据存放在存储器中,对指令和数据同等对待，都不加区别地送到运算器中运算。指令在存储器中基本上是按执行顺序存储的，由指令计数器指明要执行的指令在存储器中的地址。存储器一般分为内存储器与外存储器两大类。内存一般安装在主机板上，根据材料和工作原理的不同，内存可分为随机存储器（RAM）和只读存储器（ROM）两种。控制器和运算器只能接受在内存中存放的指令和数据。外存一般安装在主机板之外，外存上面的信息可长久保存，但这些信息必须读入内存之后才能被控制器和运算器所利用。磁盘就是一种常用的外存。半导体存储器半导体存储器（semiconductormemory）是一种能存储大量二值信息(或称为二值的数据)的半导体器件。从存取功能上可以分为只读存储器(ROM，即ReadOnlyMemory)和随机存储器(RAM，即RandomAccessMemory)两大类。随机存储器RAM又分为静态随机存储器SRAM和动态随机存储器DRAM两大类非易失性存储器非易失性存储器，是指那些断电后数据仍然能保留的半导体存储器。对这类存储器，业界统称为非易失性随机访问存储器（NVRAM，Non-VolatileRandomAccessMemory）。在NVRAM产品中，“闪存”被广泛用在PC机的主板上，用来保存BIOS程序，便于进行程序的升级。其另外一大应用领域是用来作为硬盘的替代品，具有抗震、速度快、无噪声、耗电低的优点。磁存储器光盘存储系统CPU(运算器和控制器)中央处理器（CentralProcessingUnit,CPU）由控制器、运算器和寄存器组成，是整个计算机的核心，计算机的运算处理功能主要由它来完成。同时,它还控制计算机的其他零部件，从而使计算机的各部件协调工作。总线总线：CPU与主存储器之间通过总线连接，CPU通过总线提供存储单元目标地址以及读信号来选择、读取数据CPU通过总线提供存储单元目标地址以及写信号来放置、写入信号指令系统CPU能够解码并执行的机器指令集合CISC最初人们采用的是进一步增强原有指令的功能，并设置更为复杂的指令的方法，采用这种设计思路的计算机被称为复杂指令系统计算机（CISC）。RISC通过减少指令总数和简化指令的功能来降低硬件设计的复杂度，从而提高指令的执行速度。优点:与CISC技术相比，简化了指令系统，适合超大规模集成电路的实现；提高了机器执行的速度和效率；降低了设计成本，提高了系统的可靠性；提供了直接支持高级语言的能力，简化了编译程序的设计。机器指令机器指令系统——每台数字电子计算机在设计中，都规定了一组指令。机器语言——用机器指令形式编写的程序。在裸机级，计算机语言关于算法的描述采用的是实际机器的机器指令，它的符号集是{0，1}，支撑实际机器的理论是图灵机等计算模型；在图灵机等计算模型理论的指导下，有关设计形态的主要成果有冯·诺依曼型计算机等具体实现思想和技术，以及各类数字电子计算机产品。计算机语言在裸机级所取得的主要成果汇编语言：采用字符和十进制数来代替二进制代码的思想。汇编语言源程序经汇编程序翻译成机器指令，再在实际的机器中执行。从汇编语言的用户角度来看，机器是可以直接识别汇编语言的，从而产生了一个属于抽象形态的重要概念，即虚拟机的概念。虚拟机:抽象的计算机由软件实现，并与实际机器一样，都具有一个指令集并可以使用不同的存储区域。例如，一台机器上配有C语言和Pascal语言的编译程序，对C语言用户来说，这台机器就是以C语言为机器语言的虚拟机，对Pascal用户来说，这台机器就是以Pascal语言为机器语言的虚拟机。高级语言虽然与机器语言相比，汇编语言的产生是一个很大的进步，但是用它来进行程序设计仍然比较困难。于是人们着手对它进行改进。一是发展宏汇编，即用一条宏指令代替若干条汇编指令，从而提高编程效率。现在人们使用的汇编语言，大多数都是宏汇编语言。二是创建高级语言，使编程更加方便。3.7.6应用语言一般将计算机语言划分为5代：第一代为机器语言；第二代为汇编语言；第三代为高级语言；第四代为“非过程性语言”；第五代为自然语言。3.7.7自然语言计算机对自然语言的处理划分为四个层次：第一层次是文字和语音，即基本语言信息的构成；第二层次是语法，即语言的形态结构；第三层次是语义，即语言与它所指的对象之间的关系；第四层次是语用，即语言与它的使用者之间的关系。第4章计算学科中的核心概念（重点）本章介绍学科中最具方法论性质的概念——算法及数据结构、程序、软件、硬件、计算机中的数据等。二、八、十、十六进制之间的转换；原码、反码、补码的计算；ASCII码基础；汉字编码基础。算法算法定义：“解某种问题的任何专门的方法”。欧几里德算法给定两个正整数m和n，求它们的最大公因子，即能同时整除m和n的最大正整数。欧几里德算法如下：（1）以n除m，并令所得余数为r（r必小于n）；（2）若r=0，算法结束，输出结果n；否则继续步骤（3）；（3）将n置换为m，r置换为n，并返回步骤（1）继续进行。例4.3设m=56，n=32，求m、n的最大公因子。算法的执行过程如下：（1）32除56余数为24；（2）24除32余数为8；（3）8除24余数为0，算法结束，输出结果8。答：m、n的最大公因子为8。欧几里德算法既表述了一个数的求解过程，同时，它又表述了一个判定过程，该过程可以判定“m和n是互质的”（即除1以外，m和n没有公因子）这个命题的真假。4.2.2算法的定义和特征1．算法的非形式化定义一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型问题的运算序列。2．算法的重要特性算法的规则序列须满足如下五个重要条件：1,有穷性。算法必须总是在执行有穷步之后结束；2,确定性。算法的每一个步骤必须是确切地定义的；3,输入。算法有零个或多个输入；4,输出。算法有一个或多个输出；5,能行性。算法中有待执行的运算和操作必须是相当基本的，它们都是能够精确地进行的，算法执行者甚至不需要掌握算法的含义即可根据该算法的每一步骤要求进行操作，并最终得出正确的结果。算法实例例4.4求1+2+3+…+100例4.5求解调和级数Hn。例4.6求解斐波那契数算法的表示方法表示算法的语言主要有自然语言、流程图、伪代码、计算机程序设计语言等。它们的优缺点算法分析解一个问题，往往有若干不同的算法，这些算法决定着根据该算法编写的程序性能的好坏。在保证算法正确性的前提下，如何确定算法的优劣？在算法的分析中，一般应考虑以下3个问题：（1）算法的时间复杂度；（2）算法的空间复杂度；（3）算法是否便于阅读、修改和测试。通常用以下几个标准来评价算法的优劣：正确性：算法必须能正确解决问题。易读性：算法应当便于阅读和理解，以利于修改和改写成程序。健壮性：当输入非法数据时，算法也能做出特殊处理，不会继续操作或死机。高效率：算法的效率主要从时间和空间两个方面考虑。解决一个问题的算法如果使用时间少和占用空间少，则是算法高效率的体现。算法的研究算法：定义一项工作如何完成的步骤的集合在一台机器可以完成一个任务之前，必须找到完成这个任务的算法并且用与机器兼容的方式来描述数据结构数学模型可分为定量模型和定性模型两类。定量模型指的是可以用数值方程表示的一类模型，而定性模型则是指非数值性的数据结构（如表、树和图等）及其运算。在计算领域中，数据结构（DataStructure）指的是一类定性数学模型，它是计算机算法设计的基础，它在计算科学中占有十分重要的地位。数据结构的基本概念1．数据结构的组成数据结构是一类定性的数学模型，它由数据的逻辑结构、数据的存储结构（或称物理结构）及其运算3部分组成。数据的存储结构数据的存储结构是指在反映数据逻辑关系的原则下，数据在存储器中的存储方式。数据存储结构的基本组织方式有顺序存储结构和链式存储结构。（1）顺序存储结构：借助元素在存储器中的相对位置来表示数据元素的逻辑关系。（2）链式存储结构：借助指针来表示数据元素之间的逻辑关系，通常在数据元素上增加一个或多个指针类型的属性来实现这种表示方式。4．数据结构的基本运算内容（1）建立数据结构；（2）清除数据结构；（3）插入数据元素；（4）删除数据元素；（5）更新数据元素；（6）查找数据元素；（7）按序重新排列；（8）判定某个数据结构是否为空，或是否已达到最大允许的容量；（9）统计数据元素的个数。常用的几种数据结构1．线性表线性表是n个数据元素的有限序列，即（X[1]，X[2]，X[3]，…，X[i]，…，X[n]）。插入、删除和存取数据元素是所有数据结构的基本操作，若对线性表的这些基本操作加一定的限制，则形成下面几种特殊的线性表：（1）栈：也称为后进先出表（LIFO：LastIn,FirstOut）。它的所有插入、删除和存取都是在线性表的表尾进行的；进行删除和插入的一端称栈顶，另一堆称栈底插入一般称为进栈（Push），删除则称为退栈（Pop）。（2）队列：先进先出（FirstInFirstOut，简称FIFO）的线性表。它是限定在一端进行插入，另一端进行删除和存取的特殊线性表。通常把队列的删除和插入分别称为出队和入队。允许出队的一端称为队头，允许入队的一端称为队尾。所有需要进队的数据项，只能从队尾进入，队列中的数据项只能从队头离去。总是先入队的元素先出队，也称为先进先出（FirstInFirstOut，简称FIFO）。（3）链表：链表用一组任意的存储单元来依次存放线性表的数据元素，在存储每个结点值的同时，必须存储指示其后继（或前趋）结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。如果链表的每一个结点只有一个指针域，则这种链表称为单链表结点结构，如果链表的每一个结点有两个指针域，则这种链表称为双链表结点结构。一个指针域指向其前趋结点，一个指针域向其后继结点。2．数组数组是线性表的推广形式之一。如在一个mn的二维数组中，每个元素A[i,j]都分别属于两个线性表，即（A[i,1]，A[i,2]，…，A[i,n]）和（A[1,j]，A[2,j]，…，A[m,j]）。3．树和二叉树树和二叉树是一种具有层次关系的非线性结构，尤其以二叉树最为常用。（1）树树（Tree）是由n（n≥0）个结点组成的有限集合。若n=0，则称为空树，任何一个非空树均满足以下两个条件：①仅有一个称为根的结点；②当n>0时，其余结点可分为m（m≥0）个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。（2）二叉树二叉树是n（n≥0）个结点组成的有限集合，它或者是空集（n0），或者由一个结点及两棵互不相交的子树组成，且这两个子树有左、右之分，其次序不能任意颠倒。要求：会写出某个二叉树的前序、中序、后序遍历4．图图是由结点和连接这些结点的边所组成的集合。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。程序“程序”一词，从广义上讲可以认为是一种行动方案或工作步骤。计算机的程序也是一种处理事务的时间顺序和处理步骤。由于组成计算机程序的基本单位是指令，因此，计算机程序就是按照工作步骤事先编排好的、具有特殊功能的指令序列。一个程序具有一个单一的、不可分的结构，它规定了某个数据结构上的一个算法。沃思（NikiklausWirth）提出这样一个公式：算法+数据结构=程序算法和数据结构是计算机程序的两个最基本的概念。计算机软件的定义：计算机软件是在计算机上运行的各种程序、要处理的各类数据以及有关文档的总称。程序+文档+数据=软件软件系统的分层结构计算机软件系统是一个分层的软件结构，包括系统软件层、支撑软件层和应用软件层，其最底层是计算机硬件。（1）系统软件是计算机系统中最靠近硬件层次的软件。如操作系统、编译程序等。（2）支撑软件是支撑其他软件的开发与维护的软件。如数据库管理系统、网络软件、各种接口软件和开发工具等。（3）应用软件是特定应用领域的专用软件。如商业会计软件、教学软件等。软件的性质软件同传统的工业产品相比，有其独特的性质：1.表现形式不同2.生产方式不同3.维护方式不同4.软件的复杂性和规模不断增加操作系统的任务及功能定义：操作系统是管理软硬件资源、控制程序执行，改善人机界面，合理组织计算机工作流程和为用户使用计算机提供良好运行环境的一种系统软件。任务：操作系统的任务是管理好计算机的全部软硬件资源，提高计算机的利用率；担任用户与计算机之间的接口，使用户通过操作系统提供的命令或菜单方便地使用计算机功能：从资源管理的角度来看，操作系统的功能分为处理机管理、存储管理、I/O设备管理、文件系统和用户接口等。操作系统的主要特性1.并发性（Concurrence）是指两个或两个以上的运行程序在同一时间间隔段内同时执行。2.共享性。指操作系统中的资源（包括硬件资源和信息资源）可被多个并发执行的进程所使用。3.异步性。在多道程序环境中，允许多个进程并发执行，由于资源有限而进程众多，多数情况，进程的执行不是一贯到底，而是“走走停停”操作系统的分类1.单用户操作系统2.批处理操作系统（BatchSystem）3.实时操作系统4.分时操作系统5.网络操作系统6.分布式操作系统7.微机操作系统应用软件1.科学和工程计算软件2.字表处理软件3.图形图像处理软件4.网络应用软件5.应用数据库软件计算机系统是由计算机硬件和计算机软件组成的。硬件是计算机的“躯体”，软件是计算机的“灵魂”。广义的计算机硬件包含硬件本身（构成计算机系统的所有物理器件、部件、设备）及其工程技术（工作原理与设计、制造、检测等技术）两部分。计算机系统的物理元器件包括：集成电路、印制电路板，以及其他磁性元件、电子元件等。计算机系统的部件和设备包括：控制器、运算器、存储器、输入输出设备、电源等。硬件工程技术包括：印制电路板制造、高密度组装、抗环境干扰、抗恶劣环境破坏等技术，以及在设计和制造过程中为提高计算机性能所采取的措施等。数据存储和表示计算机用位的形式来表示数据。位（binarydigit，二进制数字，缩写为bit）是存储在计算机中的最小数据单位，位表示二进制数字的0或1，8位表示1个字节（byte）。在计算机中，数据和指令都是用二进制代码来表示的。对数值、字符、图像、声音的数据，需要进行相应的编码。在需要呈现给用户时，再对它们进行解码。数制转换在实际的程序中，由于二进制数不直观。因此：在程序的输入和输出中，一般仍采用十进制数；而在分析计算机内部工作时，常用十六进制（Hexadecimal）数。这样，就要进行相应的转换。1.十进制数与二进制数之间的转换（1）十进制数转换为二进制数（2）二进制数转换为十进制数2.八进制数与二进制数之间的转换（1）八进制数转换为二进制数（2）二进制数转换为八进制数3.十六进制数与二进制数之间的转换（1）十六进制数转换为二进制数（2）二进制数转换为十六进制数原码、反码、补码及其转换1.原码原码是一种最简单而又直观的编码方法。数的符号用一位数码表示，0表示正号，1表示负号，其余的数位与数值本身相同。原码的优点：表示简单，与真值间的转换很容易。缺点：由于只是简单地将符号数值化，而没有与数值统一编码，作加减运算时很不方便。2.反码反码是机器数的另一种编码表示法。它是一种正数与原码相同，负数将原码除符号位外其余各位求反的表示法。求反就是0变1，1变0的操作。3.补码负数的补码就是对反码加一，而正数的原码反码补码是一样的。4.原码、反码和补码的转换对正数来说，原码、反码和补码的表示形式是相同的；对负数来说，原码与反码的互换，“除符号位不变外，按位求反”，原码与补码的互换：“除符号位不变外，按位求反再加1”。字符、字符串和汉字1.字符ASCII码ASCII扩展2.字符串字符串是由字符序列所组成的，字符串可以表示成一系列字节，每个字节对应ASCII码中的一个特定字符。3.汉字对ASCII码进行扩展，使其区分不同汉字。汉字机内码是计算机内部存储和处理汉字的编码。常用两个字节表示，每个字节的最高位都设置为1。内码是以汉字拼音的顺序排序的。4.Unicode为了支持不同国家的语言字符集，ASCII码正在被Unicode码所代替，Unicode是一个16位的编码系统。它用16位二进制来表示每一个符号，这样Unicode就有216（65536）种不同的二进制编码。4.7.4图像在计算机中表示图像的技术两种：位图和矢量图。1.位图在位图技术中，图像被看作是点的集合，每一个点叫做一个像素。2.矢量图与位图不同，矢量图是以指令来描述图像的。它用指令来描述直线，曲线，矩形，圆形的形状、大小、材质等等。4.7.5声音计算机如何存储和处理是模拟信号的声音呢？将连续的模拟波形转换为一系列离散的数值。这一转换的过程包括“采样”和“量化”，然后进行“编码”。“采样”就是等时间间隔地读取波形的幅值“量化”是把读取声波的幅值表示为数字值“编码”是将量化得到的数字值进行编码。第5章学科中的数学方法重点：布尔代数与数字逻辑电路、递归和迭代、公理化方法。在计算学科中的数学方法，主要是离散数学的方法。数学的基本特征1.高度的抽象性2．逻辑的严密性3．普遍的适用性数学方法的作用数学方法是指解决数学问题的策略、途径和步骤。数学方法在科学技术方法论中的作用主要表现在以下3个方面：1.为科学技术研究提供简洁精确的形式化语言。2.为科学技术研究提供数量分析和计算的方法。3.为科学技术研究提供逻辑推理的工具5.4计算学科中常用的数学概念和术语5.4.1集合1．集合的概念2．集合的描述方法描述集合的方式主要有以下3种：（1）枚举法：列出所有元素的表示方法。（2）外延表示法：（3）谓词表示法：用谓词来概括集合中元素的属性。3．集合的运算传统的集合运算是二目运算，包括并、交、差、广义笛卡尔积四种运算。集合运算的论域参与运算的集合A和集合B具有相同的属性，且相应的属性取自同一个域。（1）集合的并（2）集合的差（3）集合的交（4）集合的乘积5.4.2函数和关系1．函数函数又称映射，是指把输入转变成输出的运算，该运算也可理解为从某一“定义域”的对象到某一“值域”的对象的映射。2．关系关系是一个谓词，其定义域为k元组的集合。通常的关系为二元关系，其定义域为有序对的集合，在这个集合中，我们说有序对的第一个元素和第二个元素有关系。3．等价关系在日常生活中，常常碰到对一些对象进行分类的问题。任意一个分类法总是在某一观点下把一些元素看做是同样的，并且希望每一个元素在这种分类法下都必定属于而且仅仅属于某一类，具有这种功能的分类法，在数学上就叫做一个等价关系。5.4.3代数系统从两个数确定第三个数，而且第三个数是由前两个数惟一确定的．这就是“代数运算”的最本质特点。代数运算的严格意义：对于一个非空集合A，可以定义，任意一个由AA到A的映射称为集合A上的一个二元运算，An到A的映射则称为集合A上的一个n元运算。由集合A以及连同若干定义在该集合上的运算f1，f2，fn所组成的系统称为代数系统，该系统可以形式化的描述为：<A，f1，f2，，fn>。群、环、格、布尔代数是4种最基本的代数系统。布尔代数布尔代数是一种特殊的格，它由0和1组成的集合以及定义在其上的“3个运算”构成。1.与逻辑（与运算）与逻辑的定义：与运算：决定事件的全部条件都满足时，事件才发生--这就是与逻辑关系。在函数式中，用“•”表示与运算，记做Y=A•B或Y=AB2.或逻辑（或运算）或逻辑的定义：或运算：决定事件的全部条件至少有一个满足时，事件就发生，称为或逻辑关系。在函数式中，用“＋”表示或运算，其函数表达式为：Y=A＋B。3.非逻辑（非运算）非逻辑指的是逻辑的否定。决定事件的条件满足时，事件不发生；条件不满足，事件反而发生。在函数式中，用“–”表示非运算。三种基本逻辑关系都可以由具体电路来实现。通常把实现"与"逻辑运算的单元电路称为"与门"；把实现"或"逻辑运算的单元电路称为"或门"；把实现"非"逻辑运算的单元电路称为"非门"（或称为反相器）。表5.1布尔代数三个基本的逻辑运算ABA·BA+B

00011011000101111100表5.2与、或、非门电路图及相应的布尔表达式5.4.4字母表、字符串和语言字母表可以理解为计算机输入键盘上符号的集合。字母可以理解为键盘上的每一个英文字母、数字、标点符号、运算符号等。字符串指的是由字符组成的有限序列。语言指的是给定字母表上的字符串的集合。语言是字符串的集合，因此，传统的集合运算（如并、交、差、补、笛卡尔积）对语言都适用。除此之外，语言还有一种重要的专门的运算，即闭包运算。语言、文法以及自动机有着密切的关系。语言由文法产生，文法是一种数学模型，它是建立在有限集合上的一组变换（运算）。根据代数系统的定义，也可以将文法看作是一种代数系统，而语言正是由这种代数系统产生的。计算机使用的语言是一种形式语言，在形式语言与自动机理论中，自动机是识别语言的数学模型，各类文法所对应的自动机分别是图灵机、线性有界自动机、下推自动机和有限状态自动机。需要指出的是，语言与数学模型不是一一对应的关系，一种语言可以由不同的文法产生，也可以由不同的自动机识别。5.4.5定义、定理和证明定义定义是对一种事物的本质特征或一个概念的内涵与外延确切而简要的说明。1.定义的作用（1）综合作用：（2）分析作用：（3）交流作用：2.定义的规则（1）定义必须揭示被定义对象的区别性特征；（2）定义项和被定义项的外延必须相等；（3）定义不能恶性循环；（4）定义不可用含混、隐晦或比喻性词语来表示。定理1、通过真命题（公理或其他已被证明的定理）出发，经过受逻辑限制的演绎推导，证明为正确的结论的命题或公式，例如“平行四边形的对边相等”就是平面几何中的一个定理。2、一般来说，在数学中，只有重要或有趣的陈述才叫定理，证明定理是数学的中心活动。相信为真但未被证明的数学叙述为猜想，当它被证明为真后便是定理。它是定理的来源，但并非唯一来源。一个从其他定理引伸出来的数学叙述，可以不经过证明成为猜想的过程，成为定理。如上所述，定理需要某些逻辑框架，继而形成一套公理（公理系统）。同时，一个推理的过程，容许从公理中引出新定理和其他之前发现的定理。在命题逻辑中，所有已证明的叙述都称为定理。5.4.6必要条件和充分条件（不考）必要条件，用计算机的行话来说，就是找不到一个反例的条件。5.5证明方法5.5.1直接证明法和间接证明法1．直接证明假定p为真，通过使用公理或已证明的定理以及正确的推理规则证明q也为真，以此证明蕴含式p→q为真。这种证明方法为直接证明法。2．间接证明因为蕴含式p→q与其逆否命题¬q→¬p等价，因此可以通过证明¬q→¬p来证明蕴含式p→q为真。这种证明方法为间接证明法。5.5.2反证法首先假定一个与原命题相反的命题成立，然后通过正确的推理得出与已知（或假设）条件、公理、已证过的定理等相互矛盾或自相矛盾的结果，用来证明原命题的正确。这种证明方法就是反证法，也称归谬法，是一种常用的数学证明方法。5.5.3归纳法1．归纳法的定义所谓归纳法，是指从特殊推理出一般的一种证明方法。归纳法可分为不完全归纳法、完全归纳法和数学归纳法。2．不完全归纳法不完全归纳法是根据部分特殊情况作出推理的一种方法，该方法多用于无穷对象的论证，然而，论证的结果不一定正确。因此，不完全归纳法不能作为严格的证明方法。3．完全归纳法完全归纳法也称穷举法，它是对命题中存在的所有特殊情况进行考虑的一种方法，用该方法论证的结果是正确的，然而，它只能用于“有限”对象的论证。4．数学归纳法（1）数学归纳法的概念数学归纳法是一种用于证明与自然数有关的命题正确性的证明方法，该方法能用“有限”的步骤解决无穷对象的论证问题。数学归纳法广泛地应用于计算理论研究之中，如算法的正确性证明、图与树的定理证明等方面。5.5.4构造性证明数学是形式化的思想元素，数学讲究严密的形式推理和证明。首先，数学证明旨在核实真理，它用严格的、逻辑的过程得出令人可信的结论；其次，数学证明最重要的价值是增进理解，只有当你理解了一个定理的证明，才能真正深入体会该定理的内容。1．存在性证明存在一个x使命题P(x)成立可表示为：xP(x)。对形如xP(x)的命题的证明称为存在性证明。2．构造性证明构造性的证明方法，对于要解决的问题，不光要证明该问题解的存在，还要给出解决该问题的具体步骤，这种步骤往往就是对解题算法的描述。5.6递归和迭代构造性是计算机软硬件系统的最根本特征，而递归和迭代是最具代表性的构造性数学方法，它广泛地应用于计算学科各个领域。递归和迭代密切相关，实现递归和迭代的基础基于以下一个事实。不少序列项，常常可以用这样的方式得到：由an–1得到an，按这样的法则，可以从一个已知的首项开始，有限次地重复做下去，最后产生一个序列。该序列是递归和迭代运算的基础。5.6.1递归1．递归及其有关概念在计算技术中，与递归有关的概念有：递归关系、递归数列、递归过程、递归算法、递归程序、递归方法。（1）递归关系指的是：一个数列的若干连续项之间的关系。（2）递归数列指的是：由递归关系所确定的数列。（3）递归过程指的是：调用“自身”的过程。（4）递归算法指的是：包含递归过程的算法。（5）递归程序指的是：直接或间接调用“自身”的程序。（6）递归方法（也称递推法），是一种在“有限”步骤内，根据特定的法则或公式对一个或多个前面的元素进行运算，以确定一系列元素（如数或函数）的方法。2．递归与数学归纳法与数学归纳法相对应，递归由递归基础和递归步骤两部分组成。数学归纳法是一种论证方法，递归是算法和程序设计的一种实现技术，涉及递归定义的证明通常采用数学归纳法。3．递归的定义功能递归不仅应用于算法和程序设计之中，它还广泛地应用于定义序列、函数和集合等各个方面。（1）定义序列例5.22（2）定义函数例5.23（3）定义集合5.6.2迭代“迭”是屡次和反复的意思，“代”是替换的意思，合起来，“迭代”就是反复替换的意思。在程序设计中，为了处理重复性计算的问题，最常用的方法就是迭代方法，主要是循环迭代。可以证明，迭代程序都可以转换为与它等价的递归程序，反之，则不然。5.7公理化方法5.7.2公理化方法的基本概念1．什么是公理化方法公理化方法是一种构造理论体系的演绎方法，它是从尽可能少的基本概念、公理出发，运用演绎推理规则，推出一系列的命题，从而建立整个理论体系的思想方法。用公理化方法构建的理论称为“公理系统”。公理系统需要满足三个条件：公理系统需要满足无矛盾性、独立性和完备性三个条件。5.8.1形式系统的组成、基本特点和局限性1．形式系统的组成形式系统由下面几个部分组成：（1）初始符号。初始符号不具有任何意义。（2）形式规则。形式规则规定一种程序，借以判定哪些符号串是本系统中的公式，哪些不是。（3）公理。即在本系统的公式中，确定不加推导就可以断定的公式集。（4）变形规则。变形规则亦称演绎规则或推导规则。变形规则规定，从已被断定的公式，如何得出新的被断定公式。被断定的公式又称为系统中的定理。2．形式系统的基本特点（1）严格性（2）抽象性3．形式系统的局限性一个形式系统，如果它是无矛盾的，那么它就具有下面两个局限性：（1）不完备性（2）不可判定性形式化与公理化形式化不一定导致公理化，公理系统也不一定是形式系统。如欧氏几何公理系统就不是形式系统。第6章学科中的系统科学方法6.2.2系统科学遵循的一般原则1．整体性原则亚里士多德以:“整体大于部分之和”来表述整体涌现性。贝塔朗菲定律：“整体不等于部分之和”。2．动态原则动态原则是指系统总是动态的，永远处于运动变化之中。3．最优化原则运用各种有效方法，从系统多种目标或多种可能的途径中选择最优系统、最优方案、最优功能、最优运动状态，达到整体优化的目的。4．模型化原则模型化原则就是根据系统模型说明的原因和真实系统提供的依据，提出以模型代替真实系统进行模拟实验，达到认识真实系统特性和规律性的方法。6.2.3常用的几种系统科学方法1．系统分析法2．信息方法3．功能模拟方法4．黑箱方法5．整体优化方法6.3.3软件系统的复杂性然而，计算机的软、硬件系统存在大量不能化简的状态，这就使得构思、描述和测试计算机系统，不能依靠像物理学那样简单的定律来完成，而必须另外寻找能够控制和降低复杂性的方法。1.软件的复杂性关于软件的复杂性：复杂度、一致性、可变性、不可见性等说明了软件所固有的困难。2.软件系统开发的难点：概念结构的规格、设计和测试布鲁克斯认为，对于一个软件系统的开发来说，最为困难的是对其概念结构（概念模型）的规格、设计和测试，而不是对概念结构的实现，以及对这种实现的测试。当然，他也承认，在实现的过程中会出现语法的错误，但是，相对于概念结构方面的错误，则要小得多。6.3.4软件开发的系统化方法需要遵循的基本原则软件开发的系统化方法需要遵循的几个基本原则：（1）抽象第一的原则（2）层次划分的原则（3）模块化原则6.4结构化方法6.4.2结构化方法遵循的基本原则结构化方法的基本思想就是将待解决的问题看作一个系统，从而用系统科学的思想方法来分析和解决问题。结构化方法遵循以下基本原则。（1）抽象原则注重把握系统的本质内容，而忽略与系统当前目标无关的内容。（2）分解原则分解原则是结构化方法中最基本的原则，它是一种先总体，后局部的思想原则。在构造信息系统模型时，它采用自顶向下，分层解决的方法。（3）模块化原则模块化是结构化方法最基本的分解原则的具体应用，它主要出现在结构化设计阶段中，其目标是将系统分解成具有特定功能的若干模块，从而完成系统指定的各项功能。6.4.3结构化方法的核心问题建立模型（简称建模）是结构化方法的核心问题。建模通常是从系统的需求分析开始，在结构化方法中，就是使用SA方法构建系统的环境模型；然后使用SD方法，确定系统的行为和功能模型；最后使用SP方法，进行系统的设计，并确定用户的现实模型。1．环境模型环境模型包括需求分析、环境图和事件列表等内容。（1）需求分析需求分析是系统分析的第一步，它的主要任务是明确用户的各种需求，并对系统要做什么作一个清晰、简洁和无二义性的文档说明。需求分析阶段的用户一般是高级主管、人事主管和执行官，且基本上每个人都不直接参与新系统的开发。（2）环境图环境图是数据流图的一种特殊形式。环境图模拟系统的一个大致边界，并展示系统和外部的接口、数据的输入和输出以及数据的存储。（3）事件列表事件列表是发生在外部世界，但系统必须响应的叙述性列表。事件列表是对环境图的一个补充。2．行为和功能模型SD的主要任务就是要在系统环境模型的基础上建立系统的行为和功能模型，完成系统内部行为的描述。实现系统行为和功能模型的主要工具有：数据字典、数据流图、状态变迁图和实体—联系模型等。（1）数据字典数据字典是一个包含所有系统数据元素定义的仓库。数据元素的定义必须是精确的、严格的和明确的。一个实体一般应包括以下几个部分的内容：①名字；②别名；③用途；④内容描述；⑤备注信息。（2）数据流图数据流图是SA和SD的核心技术，它采用面向处理过程的思想来描述系统，它是一种描述信息流和数据从输入到输出变换的应用图形技术。（3）状态变迁图状态变迁图及时地描述了对象的状态，它着重系统的时间依赖行为。状态变迁图源于实时系统的建模，并被广泛应用于商业信息处理领域中。（4）实体－联系模型实体－联系模型被用来模拟系统数据部件之间的相互关系。实体－联系模型独立于当前的系统状态，并与具体的计算机程序设计语言无关。3．实现模型（1）处理器模型在多处理器系统和网络环境中，还需要将处理器分成不同的组，以便确定操作在哪个处理器上进行。（2）任务模型任务模型建立在处理器模型的基础之上，它将所有过程都划分成操作系统的任务。（3）结构图结构图是使用图形符号来描述系统的过程和结构的工具。结构图常由数据流图转换而来，它展示了模块的划分、层次和组织结构以及模块间的通信接口，从而有助于设计者和程序开发人员进行系统的设计。（4）模块设计在结构化方法中，SP阶段的目标就是将系统分解成更容易实现和维护的模块。SP方法要求每个模块执行单一的功能，而且不同模块间的依赖性要尽可能低。（5）实现阶段实现阶段包括系统的编码、测试和安装。这一阶段的产物主要是能够模拟现实世界的软件系统。除此之外，软件文档和帮助用户熟悉系统的客户培训计划也是这一阶段的产物。6.5面向对象方法面向对象（Object-Oriented，简称OO）方法是以面向对象思想为指导进行系统开发的一类方法的总称。这类方法以对象为中心，以类和继承为构造机制来抽象现实世界，并构建相应的软件系统。6.5.1面向对象方法的产生和发展6.5.2面向对象方法的基本思想《大英百科全书》描述了“分类学理论”中有关人类认识现实世界普遍采用的3个构造法则：（1）区分对象及其属性；（2）区分整体对象及其组成部分；（3）形成并区分不同对象的类。面向对象思想正是根据以上3个常用的构造法而建立起来的。1．面向对象模型及其特性一般认为面向对象模型应包括下面几个特性：（1）身份、状态、行为（2）分类（3）继承（4）多态2．面向对象模型遵循的基本原则面向对象模型遵循的基本原则有：抽象、封装、模块化以及层次原则等。面向对象的优点：1、可维护性2、可移植性和可扩展性面向对象方法中的类、封装、继承、聚合关系、关联，以及服务等重要概念。（1）类（2）封装（3）继承（4）聚合关系（5）关联（6）属性（7）服务4.5软件工程及其标准软件工程是将系统化的、规范的、可度量的方法应用于软件的开发、运行和维护的过程，即将工程化应用于软件中，并对以上所述的方法研究4.5.3CASE技术在软件工程活动中，软件工程师和管理员按照软件工程的方法和原则，借助于计算机及其软件工具的帮助，开发、维护、管理软件产品的过程，称为计算机辅助软件工程（Computer-AidedSoftwareEngineering，简称CASE）。CASE技术的两个突出特点，使开发支持工具与开发方法学统一和结合起来，通过实现分析、设计、程序开发与维护的自动化，提高整个软件开发工程的效率。第7章社会与职业问题7.6基于计算机系统的风险和责任影响软件质量的三个重要因素：正确性、可靠性和安全性7.5.3软件测试软件测试，就是以手工或自动方式，通过对软件是否满足特定的需求进行验证或识别软件的实际运行结果与期望值之间的不同，而对系统或系统部件进行评价的过程。1．软件测试的目标（1）测试是一个程序的执行过程，其目标是发现错误；（2）一个好的测试用例能够发现至今尚未察觉的错误；（3）一