教学课件-信息技术导论(第2版)-鄂大伟

第1章

信息、信息科学与信息技术

1.1探索信息的真谛1.2信息科学1.3信息技术1.4信息科学（技术）与相关学科的关系1.1探索信息的真谛1.1.1什么是信息？就一般意义而言，信息可以理解成消息、情报、知识、见闻、通知、报告、事实、数据等等。1.1.3香农对信息的定义什么是信息？信息能否度量？怎样度量？香农认为：信息是有秩序的量度，是人们对事物了解的不确定性的消除或减少。信息是对组织程度的一种测度，信息能使物质系统有序性增强，减少破坏、混乱和噪音。香农提出：信息的传播过程是“信源”（信息的发送者）把要提供的信息经过“信道”传递给“信宿”（信息的接收者），信宿接收这些经过“译码”（即解释符号）的信息符号的过程。并由此建立了通信系统模型。那么什么是信道呢？信道是在物理线路上划分的逻辑通道。1.1.4信息的度量由于信息源发出的消息是随机的，可以用随机变量来表示。如果用符号

表示信息源发出的信息，假设事件的基本空间

Ω包含m个元素，即

Ω={x1,x2,…,xm},且每一个等可能值的概率为：P（X=xi）=pi=1,2,…,m那么定义一个随机事件

所含的信息量称为x的自信息量，即：

（公式1-1）只能表示信息源发出的某一特定消息x的自信息量，而对于不同的消息则有不同的自信息量，所以不足以作为整个信息源的总体信息测度，那么可以定义平均信息量来作为信息总体的测度，即信息熵。设X为一离散随机变量，在集合

中取值，其概率分布为信息熵是从整个信息源的统计特性来考虑的，它从平均的意义上来表示信息源的总体信息测度，它表示信息源X在没有发出消息以前，信宿对信息源X存在着平均不确定性。香农的信息度量公式排除了对信息主观上的含意。根据上述公式，同样一个消息对任何一个收信者来说，所得到的信息量都是一样的。以上就是香农关于信息的度量。通常也称为概率信息。它是一个科学的定义，有明确的数学模型和定量计算。在公式中，对数的底数从理论上而言可以取任何数。当底数为2时，信息的计量单位为比特（bit），即二进制单位。为正确理解信息熵的概念，下面举例来说明。在试验甲和乙中，两种结果A和B出现的概率如下：那么，在试验之前，就试验甲而言，很难断定A和B中那个可能将出现（由于出现A与出现B的概率相等，就像投掷硬币一样，投之前很难判断正反面）；但就试验乙而言，就很大的把握断定A将出现。由此可见，在不同的试验中，其不肯定性是有大有小的，试验甲的不肯定性就比试验乙的来得大。熵就是描写不肯定性大小的量，熵越大不肯定性就越大。如果将信息熵的计算公式套用到类似本例的实验中，可以这样描述：设在试验中有N个可能出现的结果，

A(1)，A(2)

，…，A(n)

假如它们出现的概率分别是

P(1)，P(2)，…，P(n)

通常规定这个试验的熵为：1.1.5香农信息论的局限性首先，香农对信息的定义的出发点是假定事物状态可以用一个以经典集合论为基础的概率模型来描述。然而实际存在的某些事物运动状态要寻找一个合适的概率模型往往是非常困难的。对某些情况来讲，是否存在这样一个模型还值得探讨。其次，这个定义和度量考虑收信者的主观特性和主观意义，也撇开了信息的具体含义、具体用途、重要程度和引起后果等因素。这与实际情况不完全一致。以上问题的出现，主要是由于狭义信息论没有解决信息的语义问题和有效性问题。语义信息是指当认知主体在获得信息时，不仅要知道“是什么形式”，而且还要理解“是什么意思”。也就是说，信息的具体含义是什么。香农定义并没有解决语义信息的度量问题。这样，它的适用范围就受到严重的限制。1.1.6数据、消息、信号与信息的区别1.数据数据是对客观实体的一种描述形式，是信息的载体。数据（原材料木头）与信息（加工以形成的结构）的关系从这个意义上，信息和数据的区别可以理解为：数据是未加工的信息，而信息是数据经过加工以后的能为某个目的使用的数据，信息是数据的内容或诠释。将数据加工为信息的过程称为信息加工或处理。数据可分为模拟数据和数字数据两种形式。模拟数据是在某个区间内连续的值。2.消息信息是包含在消息中的抽象量，消息是具体的，其中蕴含着信息。

按照香农理论，在通信过程中，信息总是经过编码(符号化)成为消息以后，才能经由媒介传播的，而信息的接收者收到信息后，总是要经过译码(解读)才获取其中的信息的。3.信号把消息变换成适合信道传输的物理量，这种物理量称为信号。信号携带着消息，它是消息的运载工具。信号是数据的电磁或光脉冲编码。信号可以分为模拟信号和数字信号。模拟信号是一种随时间而连续变化的信号。数字信号则是在时间上的一种离散信号。1.2信息科学1.2.1科学的定义科学就是整理事实，从中发现规律，做出结论。科学要发现人所未知的事实，并以此为依据，实事求是，而不是脱离现实的纯思维的空想。规律，则是指客观事物之间内在的本质的必然联系。因此，科学是建立在实践基础上，经过实践检验和严密逻辑论证的，关于客观世界各种事物的本质及运动规律的知识体系。

1.2.2科学、技术与工程的界定“科学”是指探知事物的本质、特征、内在规律以及与其他事物的联系,是关于自然、社会和思维的发展与变化规律的知识体系。“技术”则是运用科学规律解决实现某一目的的手段和方法,泛指根据生产实践经验和科学原理而发展形成的各种工艺操作方法、技能和技巧。工程是指将科学原理应用到工农业等生产部门中去而形成的各门学科的总称。1.2.3信息科学信息和控制是信息科学的基础和核心。关于什么是信息科学（Informationscience），有着不同的定义：定义1：信息科学是研究信息的产生、获取、变换、传输、存储、处理、显示、识别和利用的科学，是一门结合了数学、物理、天文、生物和人文等基础学科的新兴与综合性学科”。定义2：以信息为主要研究对象，以信息的运动规律和应用方法为主要研究内容，以计算机等技术为主要研究工具，以扩展人类的信息功能为主要目标的一门新兴的综合性学科。1.2.4信息科学的研究内容与体系可将信息科学研究的基本内容归纳为五个方面：

(1)探讨信息的基本概念和本质。(2)研究信息的数值度量方法。(3)阐明信息感知、识别、变换、传递、存储、检索、处理、再生、表示、施效(控制)等过程的一般规律。(4)揭示利用信息来描述系统和优化系统的方法和原理(5)寻求通过加工信息来生成智能的机制和途径。从信息科学的研究内容来划分，我们可以将信息科学的基本科学体系分为三个层次（图1-6）：信息科学的哲学层次，其中包括信息的哲学本质、智能的哲学本质、信息与反映的关系、信息与认识的关系、人工智能与人类智能的关系等等。信息科学的基础理论层次，它的主要任务是研究信息的一般理论。信息科学的技术应用层次，主要研究如何应用信息科学理论在技术上拓展人类的信息功能（特别是其中的智力功能）的问题。图1-6信息科学体系的三个层次这样，信息哲学、基础理论和技术应用三者就构成了—个和谐的学科体系。1.3信息技术1.3.1信息技术的定义人们对信息技术的定义，因其使用的目的、范围、层次不同而有不同的表述：定义1：信息技术是指有关信息的收集、识别、提取、变换、存贮、传递、处理、检索、检测、分析和利用等的技术。定义2：现代信息技术“以计算机技术、微电子技术和通信技术为特征”。定义3：信息技术是指在计算机和通信技术支持下用以获取、加工、存储、变换、显示和传输文字、数值、图像以及声音信息，包括提供设备和提供信息服务两大方面的方法与设备的总称。定义4：信息技术指“应用在信息加工和处理中的科学，技术与工程的训练方法和管理技巧；上述方法和技巧的应用；计算机及其与人、机的相互作用，与人相应的社会、经济和文化等诸种事物。”定义5：信息技术包括信息传递过程中的各个方面，即信息的产生、收集、交换、存储、传输、显示、识别、提取、控制、加工和利用等技术。定义6：从技术的本质意义上讲，信息技术就是能够扩展人的信息器官功能的一类技术。1.3.2扩展人类的信息器官功能的信息技术1.人类的信息器官与功能人的信息器官主要包括以下四类：（如图1-7所示）感觉器官，包括视觉器官、听觉器官、嗅觉器官、味觉器官、触觉器官和平衡感觉器官等；传导神经网络；它又可以分为导入神经网络利导出神经网络等；思维器官，包括记忆系统、联想系统、分析推理和决策系统等；效应器官，包括操作器官(手)、行走器官(脚)和语言器官(口)等。2.信息技术的“四基元”根据上面给出的信息技术的定义和相应的分析，我们可以明确信息技术的四项基本内容，这就是“信息技术四基元”，即：(1)感测技术——感觉器官功能的延长。(2)通信技术——传导神经网络功能的延长。(3)计算机和智能技术——思维器官功能的延长。(4)控制技术——效应器官功能的延长。既然信息技术是人的信息器官功能的延长，信息技术四基元的关系也应当视作一个有机的整体，它们和谐有机地合作，共同完成扩展人的智力功能的任务。图1-8示出了它们之间的这种联系。于是，由上面给出的信息技术的定义6还可以引出两个比较具体的定义，即：

信息技术是指能够完成信息的获取、传递、加工、再生和施用等功能的—类技术；

信息技术是指感测、通信、计算机和智能以及控制等技术的整体。1.3.3信息技术的发展迄今为止，人类社会已经发生过四次信息技术革命。

第一次革命是人类创造了语言和文字，接着现出了文献。第二次革命是造纸和印刷术的出现。第三次革命是电报、电话、电视及其他通讯技术的发明和应用。第四次革命是电子计算机和现代通讯技术在信息工作中的应用。1.3.4信息技术的核心及支撑技术信息技术的核心技术就是它的“四基元”：计算机与智能技术、通信技术、感测技术及控制技术。1.计算机与智能技术2.通信技术现代通信技术主要包括数字通信、卫星通信、微波通信、光纤通信等。图1-11卫星通信3.传感技术4.控制技术图1-13控制系统框图智能控制技术当前主要包括以下几个方面：

模糊控制技术

专家控制技术

机器学习技术5.信息技术主要支撑技术──微电子技术信息技术的发展必须具备两个基本的条件：一是快速，即短时间里可收集或传输大量信息；二是体积小，携带起来方便，在任何场合都能使用。微电子技术诞生的标志是1947年发明的晶体管，但微电子产业的快速发展则是在1958年出现第一块集成电路（IC）以后。1.4信息科学（技术）与相关学科的关系1.4.1计算科学计算科学（或计算机科学）是对描述和变换信息的算法过程,包括其理论、分析、设计、效率分析、实现和应用的系统的研究。1.4.2系统科学

图1-16系统科学的层次结构1.4.3信息哲学：信息与哲学的联姻科学哲学的新范式-信息哲学1.4.4认知科学与认知心理学研究人脑或心智工作机制的认知科学

第2章计算与计算科学2.1计算的本质2.2人工智能2.3计算学科的专业方向与知识领域2.1计算的本质2.1.1探索计算之源计算就是符号串的变换。从一个已知的符号串开始，按照一定的规则，一步一步地改变符号串，经过有限步骤，最后得到一个满足预先规定的符号串，这种变换过程就是计算。算法是求解某类问题的通用法则或方法，即符号串变换的规则。2.1.2计算模型与图灵机图灵机是一种抽象计算模型（图2-2），用来精确定义可计算函数。图灵机由一个控制器，一条可以无限延伸的带子和一个在带子上左右移动的读写头组成。

带子──存贮设备

命令──相当于一组预先设计、存贮好的程序

控制器──决定读写头的每一步操作2.1.3计算的困惑——如何认识计算科学计算学科的研究包括从算法与可计算性的研究到根据可计算硬件和软件的实际实现问题的研究。这样，计算学科不但包括从总体上对算法和信息处理过程进行研究的内容，也包括满足给定规格要求的有效而可靠的软硬件设计—它包括所有科目的理论研究实验方法和工程设计。2.1.4计算机科学的研究领域目前，计算机科学的研究领域可以概括为以下七个方面：

1.计算机系统结构的研究2.程序设计科学与方法论的研究3.软件工程基础理论的研究4.人工智能与知识处理的研究

5.网络、数据库及各种计算机辅助技术的研究6.理论计算机科学的研究7.计算机科学史的研究2.2人工智能2.2.1无”心”的机器-计算机有智能吗？

图2-4正与”深蓝”

(DeepBlue)对弈的卡斯帕罗夫（左）2.2.2人工智能──“计算机像海参一样愚蠢”1.什么是人工智能人工智能是研究人类智能活动的规律，构造具有一定智能的人工系统，研究如何让计算机去完成以往需要人的智力才能胜任的工作，也就是研究如何应用计算机的软硬件来模拟人类某些智能行为的基本理论、方法和技术。图2-5日本研制的Asimo机器人(全身共30个自由度)2.有趣的图灵测验──判断机器具备智能的标准？图灵提出一个假想：一个人在不知情的条件下，通过一种特殊的方式，和一台机器进行问答，如果在相当长时间内，他分辨不出与他交流的对象是人还是机器，那么，这台机器就可以认为是能思维的。这就是著名的“图灵测试”（TuringTest）2.3计算学科的专业方向与知识领域2.3.1背景随着世界经济的多元化发展，以计算机为基础的信息技术迅速扩展到各个领域，社会和人类对信息的依赖迅速增长，计算机技术和基于计算机的应用技术已经成为信息社会的重要基础设施，计算机教育和培训也成为我国高等教育中一个重要的环节。2.3.2计算机专业培养规格分类2.3.3计算学科的领域及知识空间计算机学科逐渐形成了在“计算机科学与技术”一个专业之下分为计算机科学、计算机工程、软件工程、信息技术等四个专业方向的新格局。

计算机科学(ComputerScience-CS)

计算机工程(ComputerEngineering-CE)

软件工程(SoftwareEngineering-SE)

信息技术(InformationTechnology-IT)在CC2005（OverviewReport）中，为计算学科的知识空间给出了一个二维图解。2.3.4.计算机科学学科与知识领域

1.离散结构(DiscreteStructures)

2.程序设计基础(ProgrammingFundamentals)

3.算法和复杂性(Algorithms&Complexity)

4.程序设计语言(ProgrammingLanguages)

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

6.操作系统(OperatingSystems)

7.人-机交互(Human-ComputerInteraction)

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

9.智能系统(IntelligentSystems)

10.信息管理(InformationManagement)

11.网络计算(NetworkComputing)

12.软件工程(SoftwareEngineering)

13.数值计算科学(ComputationalScience)

14.社会和职业问题(Social&ProfessionalIssues)2.3.5计算机工程学科与知识领域计算机工程是反映现代计算系统和由计算机控制的设备的软件与硬件的设计、建造、实现的科学与技术。计算机工程的基础包含计算、数学、科学及工程的理论与原理，并运用这些理论与原理，解决在硬件、软件、网络的设计以及其他过程中的技术问题。计算机工程学科组于2004年6月8日公布了CCCE的学科报告，更新了CE学科的核心知识领域，重新给出了18个核心单元的知识领域，更新的CE知识领域如下：1.计算机体系结构和组织

2.计算机系统工程

3.电路和信号

4.数据库系统

5.数字逻辑

6.数字信号处理

7.电子学

8.嵌入式系统

9.算法和复杂性10.人机交互

11.计算机网络

12.操作系统

13.程序设计基础

14.社会和职业问题

15.软件工程

16.VLSI设计与构造

17.离散结构

18.概率和统计计算机工程学科组于2004年6月8日公布了CCCE的学科报告，更新了CE学科的核心知识领域，重新给出了18个核心单元的知识领域，更新的CE知识领域如下：2.3.6软件工程学科与知识领域CCSE2004报告强调了对软件工程的新定义，即软件工程是“以系统的、学科的、定量的途径，把工程应用于软件的开发、运营和维护；同时，开展对上述过程中各种方法和途径的研究”。CCSE2004报告强调了对软件工程的新定义，即软件工程是“以系统的、学科的、定量的途径，把工程应用于软件的开发、运营和维护；同时，开展对上述过程中各种方法和途径的研究”。这里明确提出了“把工程应用于软件”，明显地体现了软件工程领域内的两类重要的研究和应用方向：工程学和方法学。软件工程教育知识体系(CCSE)的知识领域覆盖点如下：

01.计算的本质

02.数学与工程基础

03.职业训练

04.软件建模与分析

05.软件设计

06.软件验证

07.软件进化08.软件过程

09.软件质量

10.软件管理

11.系统与应用专题2.3.7信息技术学科的知识领域信息技术学科的知识领域是：01.信息技术基础02.人机交互03.程序设计基础04.信息保障与安全05.信息管理06.集成程序设计技术07.计算机网络08.平台技术09.系统管理与维护10.系统集成和体系结构11.信息技术与社会环境12.系统和技术第3章信息处理机器：计算机系统3.1从历史走向未来──计算机的发展史3.2微型计算机系统与微处理器3.3计算机存储系统及工作原理3.4计算机输入/输出设备3.5微型计算机的总线及接口标准3.1从历史走向未来──计算机的发展史3.1.1现代计算机的“史前”时代（-1946）3.1.2冯·诺依曼型计算机的基本结构冯.诺依曼确定了现代存储程序式电子数字计算机的基本结构和工作原理。主要由5部分组成：存储器、运算器、控制器、输入设备、输出设备。今天，人们把具有这样一种工作原理和基本结构的计算机统称为“冯·诺依曼型计算机”。3.1.3第一台现代电子数字计算机的诞生1946年2月5日，世界上第一台真正的现代电子数字计算机“ENIAC"研制成功了（图3-5）。3.1.4现代计算机发展的四个阶段采用电子管计算机的第一代计算机（1946—1957）2.采用晶体管的第二代电子计算机（1958—1964）3.采用集成电路的第三代计算机（1965—1970）4.使用超大规模集成电路的第四代计算机（1970年至今）3.1.5巨型计算机与矢量计算

对多组数据（每组一般为两个数据）成批地进行同样的运算，得到一批结果的运算方法，即被称为“矢量运算”。3.2微型计算机系统与微处理器3.2.1计算机系统──硬件与软件硬件系统通常指机器的物理系统，硬件系统是指所有构成计算机的物理实体，它包括计算机系统中一切电子、机械、光电等设备。软件系统则是指管理计算机软件系统和硬件系统资源、控制计算机运行的程序、命令、指令、数据等，广义地说，软件系统还包括电子的和非电子的有关说明资料，说明书、用户指南、操作手册等。3.2.2微型计算机硬件系统微型计算机的硬件系统应由微处理器（运算器和控制器）、存储器、输入设备和输出设备组成（图3-15）。3.2.3微处理器--给你一颗奔腾的”芯”微处理器(Microprocessor)在微型计算机中又称为CPU（中央处理单元的缩写)，人们又经常简称为处理器(Processor)（图3-17）。随着微处理器设计、制造技术的不断提高和更新换代，推动了微机系统的迅猛发展（图3-18）。目前，微机的性能在某些方面已经达到甚至超过了小型机,并且普遍采用双核处理器。3.3计算机存储系统及工作原理3.3.1半导体存储器及其存储单元寻址半导体存储器（semiconductormemory）是一种能存储大量二值信息(或称为二值的数据)的半导体器件。从存取功能上可以分为只读存储器(ROM，即ReadOnlyMemory)和随机存储器(RAM，即RandomAccessMemory)两大类。RAM控制器负责向RAM芯片输出行地址还是列地址，行与列地址的信息由RAS（RowAddressSelect）或CAS(ColumnAddressSelect)信号确定。当CPU处理信息时，需要将信息存储到RAM中。如果需要将数据“写”到RAM中，则处理器会发出一个“写”信号到CPU中，通过系统总线，到达RAM单元。这些RAM单元然后就按行或列地址将这些信息数据存储到指点定的"栅格"中。当CPU需要读取RAM中的数据，则会向RAM发出请求信号，这些信号中包含地址信息，以确定数据在那些栅格中的位置。3.3.2只读存储器-ROMROM可分为掩模ROM、PROM、EPROM、E2PROM和快闪存储器等几种不同类型。掩模ROM是采用掩模工艺制作而成，在出厂时内部存储的数据就已经"固化"在里边了，所以数据不允许用户修改。PROM

指的是“可编程只读存储器”这样的产品只允许写入一次，所以也被称为“一次可编程只读存储器”EPROM

指的是“可擦写可编程只读存储器”。它的特点是具有可擦除功能，擦除后即可进行再编程，但是缺点是擦除需要使用紫外线照射一定的时间。EEPROM

指的是“电可擦除可编程只读存储器”，它的最大优点是可直接用电信号擦除，也可用电信号写入。Flashmemory指的是“闪存”，所谓“闪存”，它也是一种非易失性的内存，属于EEPROM的改进产品。目前“闪存”被广泛用在PC机的主板上，用来保存BIOS程序，便于进行程序的升级。其另外一大应用领域是用来作为硬盘的替代品，具有抗震、速度快、无噪声、耗电低的优点。3.3.3随机存储器-RAMRAM又分为静态随机存储器SRAM和动态随机存储器DRAM两大类1.静态随机存储器的工作原理计算机系统工作时，将运行时要经常存取的一些数据从系统内存读取到Cache中，而CPU会首先到Cache中去读取数据（或写入数据），如果Cache中没有所需数据（或Cache已满，无法再写入），则再对系统内存进行读写，另外Cache在空闲时也会与内存交换数据，如图3-22所示。2.动态存储器的工作原理动态随机存储器DRAM需要定时充电，即通常所说的刷新，来保持数据的完整性，通常用来组成大容量的内存储器。3.3.4非易失性存储器非易失性存储器，那就是指那些断电后数据仍然能保留的半导体存储器。对这类存储器，业界统称为非易失性随机访问存储器（NVRAM，Non-VolatileRandomAccessMemory）。在多种NVRAM产品中，以闪存（FlashMemory）技术最为引人注目。闪存具有关掉电源仍可保存数据的优点，同时又可重复读写且读写速度快、单位体积内可储存最多数据量，以及低功耗特性等优点。3.3.5磁存储器1.磁存储原理磁存储的关键部件是磁头，磁头的基本结构是在一个环形导磁体上绕上线圈，导磁体面向磁盘方向开一个漏磁缝隙，当磁头线圈中通以交变信号电流时，导磁体内的磁通量也跟着产生变化，这个交变的磁场从磁头缝隙中泄漏出去，使做匀速运动的磁盘表面上的磁介质感应磁化。磁化后在磁盘上的"磁化点"(磁元)就代表了所要记录的数据，这是做记录的基本工作原理。2.硬盘存储系统硬盘是一种采用磁介质的数据存储设备，数据存储在密封于洁净的硬盘驱动器内腔的若干个磁盘片上（图3-25）。3.磁盘阵列磁盘阵列是将若干个硬磁盘机按一定的要求组成一个快速、超大容量的存储系统，数据是分配存储在各个硬磁盘机上。磁盘阵列中针对不同的应用使用的不同技术,目前常用的标准是RAID0

RAID5。RAID1通常称为镜像结构。3.3.6光盘存储系统1.光存储介质的概念对光存储介质最基本的要求,就是存储单元的某种性质可以用某种方法改变以代表被存储的数据,同时这种性质可用光的方法检测出来。当前几乎所有的光存储器都检测反射光而不是透射光。最常用的方法是存储单元的光反射率代表存储的信号(1或0)，如图3-27所示。2.光盘与光盘存储系统通常意义上所说的光盘只是一个统称，用英文CD表示，意为高密盘。光盘可分成两类，一类是只读型光盘，另一类是可记录型光盘。微机上的光盘存储系统由光盘和光盘驱动器组成，对于大容量存储，还可以采用光盘库。3.只读光盘存储器只读光盘中的数据是用压模方法压制而成的，用户只能读取上面的数据，而不能写入或修改光盘中的数据。它适用于大量的、通常不需要改变的数据信息存储。为了提高存储容量，只读DVD盘（DVD-ROM）可分为单面单层、单面双层、双面单层和双面双层4种结构，如图3-29所示。DVD单面双层盘的最里层称为第一层，表层称为第二层，该层采用了一种新的半透明薄膜涂层，可让激光束透过表层到达第一层，如图3-30所示。通过采用这些技术，单面双层DVD盘的容量可达到8.5GB，双面双层DVD盘的容量可达到17GB。4.多次可写光盘存储器这种光盘允许用户一次或多次写入数据，并可随时往盘上追加数据，直到盘满为止。信息写入后则变成只读状态，不可再作修改，主要用于重要数据的长期保存。目前得到了广泛应用的CD-R就属于这类光盘。5.可重写光盘存储器可重写光盘具有磁盘一样的可重写性，可多次写入或修改光盘上的数据，更适合作为计算机的新型标准外存设备，目前有磁光（Magneto-Optical）和相变（Phase-Change）和两种类型。磁光型光盘工作原理如图3-32所示。相变光盘是利用激光使记录介质在结晶态和非结晶态之间的可逆相变结构来实现信息的记录和擦除。3.4计算机输入/输出设备3.4.1计算机输入设备1.键盘

2.鼠标

3.扫描仪4.触摸屏5.手写输入设备6.数码相机7.数字摄像机

3.4.2输出设备1.显示器2.打印机3.绘图仪3.5微型计算机的总线及接口标准3.5.1计算机总线总线（BUS）是计算机内部传输指令、数据和各种控制信息的高速通道，是计算机硬件的一个重要组成部分（图3-47）用于连接CPU、主存和I/O控制器的总线称为外部设备总线或外部总线，简称为总线。常见的总线有ISA（工业标准体系接口）总线、PCI（外部设备互连）总线、SCSI（小型计算机系统接口）总线等，它们的传输速度一个比一个快。3.5.2计算机与外部设备的接口及标准数据的传输方式基本分为两种，一种是用一条线（或一对线）用来传送数据，这种叫串行传输接口。在计算机行业中最早出现的串行接口标准是RS232标准。如果用几条线来同时传输数据，这就叫做并行接口。除了传统接口形式外，随着计算机技术的发展，现在又出现了许多新的接口标准。如SCSI，USB等。USB(UniversalSerialBus)是一种通用串行总线接口。第四章计算机软件系统4.1软件的性质及发展史4.2操作系统4.3应用软件4.4程序设计语言与语言处理程序4.5软件工程及其标准

4.1软件的性质及发展史4.1.1对计算机软件的理解定义：计算机软件是在计算机上运行的各种程序、要处理的各类数据以及有关文档的总称。这里提到的程序是按照事先设计的功能和性能要求执行的指令序列；数据是程序能正常操纵信息的数据结构；文档是与程序开发维护和使用有关的各种图文资料。文档是软件的“质”的部分，程序则是文档代码化的表现形式。4.1.2软件的性质软件同传统的工业产品相比，有其独特的性质：1.表现形式不同2.生产方式不同3.维护方式不同4.软件的复杂性和规模不断增加4.1.3软件技术的进化史软件技术发展的初期（20世纪50年代到70年代）2．软件技术发展的中期（20世纪80年代）3.网络计算时代的开始(20世纪90年代至今)4.软件之变----21世纪的软件技术4.1.4软件系统的分层结构计算机软件系统是一个分层的软件结构，包括系统软件层、支持软件层和应用软件层，其最底层是计算机硬件（图4-6）。1.系统软件2.支持软件3.应用软件4.软件分类的国家标准计算机软件的分类及代码可参照国家标准《计算机软件分类与代码》（GB/T13702-1992）有关规定确定，如表4.1所示。4.2操作系统4.2.1操作系统的任务及功能操作系统是管理软硬件资源、控制程序执行，改善人机界面，合理组织计算机工作流程和为用户使用计算机提供良好运行环境的一种系统软件。操作系统的任务是管理好计算机的全部软硬件资源，提高计算机的利用率；担任用户与计算机之间的接口，使用户通过操作系统提供的命令或菜单方便地使用计算机操作系统是怎样引导和控制计算机的呢？

从资源管理的角度来看，操作系统的功能分为处理机管理、存储管理、I/O设备管理、文件系统和用户接口等。4.2.2处理机（CPU）管理1.中断处理2.处理器调度3.理解进程及状态变化4.理解线程4.2.3存储管理

存储管理的主要功能包括：

存储分配

存储共享。

存储保护。

存储扩充。4.2.4设备管理

设备管理的主要任务有：1．选择和分配输入/输出设备以便进行数据传输操作；2．控制输入/输出设备和CPU(或内存)之间交换数据；3．为用户提供一个友好的透明接口，把用户和设备硬件特性分开，使得用户不心考虑设备的硬件差异；4.提高设备和设备之间、CPU和设备之间的并行性。4.2.5文件管理

文件是在逻辑上具有完整意义的并赋有名称的信息集合体。文件系统，就是操作系统中负责操纵和管理文件的一整套设施，它实现文件的建立、读写、修改、共享和保护等操作，还负责完成对文件的按名存取和进行存取控制。4.2.6操作系统的主要特性

1.并发性

并发性（Concurrence）是指两个或两个以上的运行程序在同一时间间隔段内同时执行。2.共享性共享指操作系统中的资源（包括硬件资源和信息资源）可被多个并发执行的进程所使用。3.异步性

在多道程序环境中，允许多个进程并发执行，由于资源有限而进程众多，多数情况，进程的执行不是一贯到底，而是“走走停停”4.2.7操作系统的分类

1.单用户操作系统2.批处理操作系统3.实时操作系统4.分时操作系统5.网络操作系统6.分布式操作系统7.微机操作系统 4.3应用软件1.科学和工程计算软件2.字表处理软件3.图形图像处理软件4.网络应用软件5.应用数据库软件4.4

程序设计语言与语言处理程序4.4.1程序设计语言程序设计语言是软件系统的重要组成部分，程序语言的进化史可分为机器语言、汇编语言、高级语言三个阶段(图4-21)。1.低级语言：

汇编语言2.高级程序设计语言

FORTRAN语言

BASIC语言

COBOL语言

Pascal语言

C语言4.4.2语言处理程序汇编程序2.编译程序3.解释程序4.4.3可视化编程语言1.VisualBasic2.VisualC++3.Delphi4.C++Builder5.PowerBuilder6.Java4.4.4.NET是什么？.NET是指连接信息、人群、系统和设备的软件。.NET是Microsoft新推出的用于快速创建和集成XMLWeb服务和应用程序的综合工具，用于解決新一代网络应用程序的需求。

4.4.5从面向过程(OP)到面向对象(OO)软件开发的过程就是人们使用各种计算机语言将人们关心的现实世界(问题域)映射到计算机世界的过程（图4-23）。面向过程的程序设计(ProcessOrientedProgramming:PO)是指采用面向过程的程序设计语言进行编程，实现软件设计流程图所描述的信息处理过程的功能。面向对象的程序设计方法(Object-OrientedProgramming：OO)基于面向对象模型。采用面向对象的程序设计语言编程实现。4.5软件工程及其标准4.5.1“软件之道”──软件工程之路软件工程是将系统化的、规范的、可度量的方法应用于软件的开发、运行和维护的过程，即将工程化应用于软件中，并对以上所述的方法研究4.5.2软件工程标准我国软件产业在ISO/IECJTC1/SC7框架的基础上，结合国情，面向管理人员、软件开发人员、软件质量保证人员提出了软件工程标准体系框架，如图4-26所示4.5.3CASE技术在软件工程活动中，软件工程师和管理员按照软件工程的方法和原则，借助于计算机及其软件工具的帮助，开发、维护、管理软件产品的过程，称为计算机辅助软件工程（Computer-AidedSoftwareEngineering，简称CASE）。CASE技术有两个突出特点，使开发支持工具与开发方法学统一和结合起来，通过实现分析、设计、程序开发与维护的自动化，提高整个软件开发工程的效率。第5章信息媒体的表示及数字化5.1计算机系统的信息表示与编码5.2媒体与多媒体信息5.3音频媒体的表示与数字化5.4图像媒体的表示与数字化5.5视频媒体的表示及数字化5.1计算机系统的信息表示与编码5.1.1模拟与数字1.模拟信号与数字信号模拟数据(AnalogData)是随时间连续变化的值数字数据(DigitalData)则是模拟数据经量化后得到的离散的值模/数转换就是将连续变化的模拟信号转换为离散的数字信号，实现该功能的电路或器件称为模/数转换电路，通常称为A/D转换器或ADC(AnalogDigitalConverter)。数/模转换是模/数转换的逆过程，就是将离散的数字信号转换为连续变化的模拟信号，实现该功能的电路或器件称为数模转换电路，通常称为D/A转换器或DAC(DigitalAnalogConverter)。2.模拟技术和数字技术的比较让我们以水桶为例比较这两种方法。为表示数字系统，我们假定用一个空桶表示，用一个有水的桶表示1。表示一个数字值时，我们采用浮点记数法，用一个桶表示一个二进制位。相对而言，为表示模拟系统，我们用一个桶来表示一个值，其值由桶里水的高度指示。5.1.2信息在计算机中的表示1.“0和1”的世界──计算机为什么采用二进制

容易表示

运算简单2.数在计算机内的表示方法数在计算机内的表示，要涉及到数的长度和符号如何确定、小数点如何表示等问题。由于二进制数的每一位数（0或1）是用电子器件的两种稳定状态来表示的，因此，二进制位（bit）是最小信息单位，一个数的长度按二进制位数（即bit数）来计算。5.1.3信息的编码ASCII码2.中文信息编码及标准3.信息时代的“书同文、字同码”──Unicode5.1.4数制的基及其表示1.数制的基把任何数表示为某一特定数字(数基)的幂的和我们通常使用的基为十的数系叫做十进制数系，基为二就叫做二进制数系。由于各数制的数码有重叠，为了不产生混淆，各数制的数分别加不同的角标以示区别：二进制：B（Binary），如(11101)B；八进制：O(Octal),如(35)O；十六进制：H(Hexadecimal),如(1D)H；5.1.5计算机的逻辑运算与逻辑门电路逻辑或运算2.逻辑与运算3.逻辑非运算4.异或运算5.2媒体与多媒体信息5.2.1媒体的分类按国际电信联盟(IUT)下属的国际电报电话咨询委员会(CCITT)的定义，媒体可分为以下五种，如图5-8所示。1.感觉媒体(Perception)

感觉媒体就是指能直接作用于人的感官，使人能直接产生感觉的一类媒体。2.表示媒体(Presentation)

它是为了能更有效地加工、处理和传输感觉媒体而人为研究和构造出来的一种媒体。3.显示媒体(Display)

是指感觉媒体和用于通信的电信号之间转换用的一类媒体，可分为输入显示媒体和输出显示媒体两种。4.存储媒体(Storage)

是用于存放数字化的表示媒体的存储介质。5.传输媒体(Transmission)

用来将表示媒体从一处传递到另一处的物理传输介质。

5.2.2媒体与多媒体从广义上来讲，多媒体一词是指多种信息媒体的表现和传播形式。从狭义的角度来看，多媒体是指人们用计算机及其它设备交互处理多媒体信息的方法和手段，或指在计算机中处理多种媒体的一系列技术。多媒体技术是一种基于计算机科学的综合技术，它包括数字化信息处理技术、音频和视频技术、计算机软硬件技术、人工智能和模式识别技术、通信和网络技术等。或者说，所谓多媒体技术是以计算机为中心，把语音、图像处理技术和视频技术等集成在一起的技术。具有这种功能的计算机称为多媒体计算机。5.3音频媒体的表示与数字化5.3.1音频信号记录的历史19世纪爱迪生发明了留声机（图5-9）音频信息在多媒体中的应用是极为广泛的，当计算机配有声卡和音箱后（图5-10），就能够发出各种悦耳的声音5.3.2音频信号的形式在物理上，声音可用一条连续的曲线来表示。这条连续的曲线无论多复杂，都可分解成一系列正弦波的线性叠加。规则音频是一种连续变化的模拟信号,可用一条连续的曲线来表示，称为声波.由于声波是在时间和幅度上都连续变化的量，我们称之为模拟量。5.3.3模拟音频信号的物理特征模拟音频信号有两个重要参数：频率和幅度。声音的频率体现音调的高低，声波幅度的大小体现声音的强弱。一个声源每秒钟可产生成百上千个波，我们把每秒钟波峰所发生的数目称之为信号的频率，单位用赫兹(Hz)或千赫兹(kHz)表示。人们在日常说话时的语音信号频率范围在300Hz～3000Hz之间。频率小于20Hz的信号称为亚音(subsonic)；频率范围为20Hz～20kHz的信号称为音频(Audio)，高于20kHz的信号称为超音频(ultrasonic)。与频率相关的另一个参数是信号的周期（图5-12）。它是指信号在两个峰点或谷底之间的相对时间。周期和频率之间的关系是互为倒数。信号的幅度是从信号的基线到当前波峰的距离。幅度决定了信号音量的强弱程度。幅度越大，声音越强。对音频信号，声音的强度用分贝(dB)表示，分贝的幅度就是音量。5.3.4音频的数字化过程对模拟音频数字化过程涉及到音频的采样、量化和编码，如图5-13所示。1.声音的采样2.音频的量化3.数字音频的编码5.4图像媒体的表示与数字化5.4.1图像的概念图像实际上是一个子集，在该子集中的每幅图像都和它所表示的物体存在对应关系。在图像集合中，有一个非常重要的、包含了所有可见的图像，在该子集中又包含几种不同方法产生的图像的子集，一个子集为图片(picture)。它包括照片(photograph)、图(drawing)和画(painting)，另一个子集为光学图像(opticalimage)，即用透镜、光栅和全息术产生的图像。5.4.2图像的表示1.空间图像与平面图像的形式化表示在一个空间图像信息中，光强度(Intensivety)是其基本要素，它随图像空间坐标(x,y,z)，光线的波长λ和时间t的变化而变化，因此空间图像函数可表示为：其中，I为像素的光强度。

二维平面图像隐式地包含着景深z的信息，它以x和y的某种函数的形式，即,z隐含在（x,y）平面之中。因此平面图像函数g可表示为：

5.4.3图像的数字化过程1.图像的采样图像采样就是将二维空间上模拟的连续亮度（即灰度）或色彩信息，转化为一系列有限的离散数值来表示。2.图像的量化图像量化实际就是将图像采样后的样本值的范围分为有限多个段，把落入某段中的所有样本值用同一值表示，是用有限的离散数值量来代替无限的连续模拟量的一种映射操作。量化字长越大，则越能真实地反映原有图像的颜色。但得到的数字图像的容量也越大5.4.4图像的压缩与编码1.图像信息为什么能压缩信息本身通常存在很大的冗余量人的视觉和听觉对某些信号(如颜色，声音)不那么敏感的生理特性，至使信息被压缩之后还不知不觉，也不至对压缩后的信息产生误解

2.图像压缩与编码分类图像数据压缩可分为有损压缩和无损压缩两类无损压缩算法是为保留原始多媒体对象（包括图像、语音和视频）而设计的。在无损压缩中，数据在压缩或解压缩过程中不会改变或损失，解压缩产生的数据是对原始对象的完整复制。有损压缩技术主要的应用领域是在影像节目、可视电话会议和多媒体网络这样的由音频、彩色图像和视频组成的多媒体应用中，并且得到了广泛的应用。5.5视频媒体的表示及数字化5.5.1视频的定义从物理上来讲，视频信号是从动态的三维景物投影到视频摄像机图像平面上的一个二维图像序列，一个视频帧中任何—点的彩色位记录了在所观察的景物中一个特定的二维点所发出或反射的光；从观察者的角度来讲，视频记录了从一个观测系统(人眼或摄像机)所观测的场景中的物体发射或反射的光的强度，一般地说，该强度在时间和空间上都有变化；从数学角度描述，视频指随时间变化的图像，或称为时变图像。5.5.2视频的分类1.模拟视频模拟视频（AnalogVideo）是一种用于传输图像和声音的并且随时间连续变化的电信号。早期视频的记录、存储和传输都是采用模拟方式。2.数字视频（DigitalVideo）要使计算机能够对视频进行处理，必须把视频源--即来自与电视机、模拟摄像机、录像机、影碟机等设备的模拟视频信号，转换成计算机要求的数字视频形式并存放在磁盘上，这个过程称为视频的数字化过程（包括采样、量化和编码）。5.5.3视频的数字化过程1.视频信号的采样模拟视频一般采用分量数字化方式，先把复合视频信号中的亮度和色度分离，得到YUV或YIQ分量，然后用三个模／数转换器对三个分量分别进行数字化，最后再转换成RGB彩色模型。5.5.4量化从本质上讲，量化是一个用有限个状态表示一组连续值采样的过程。对视频媒体而言，采样是对图像函数f(x,y)的空间坐标(x,y)

进行离散化处理，而量化是对每个离散点像素的灰度或颜色样本进行数字化处理。与图像量化的概念类似，一般都用一个二进制数来表示某一量化级数，经过传输在接收端再按照这个二进制数来恢复原信号的幅值。所谓量化比特数是指要区分所有量化级所需要的二进制数。5.5.5视频压缩与编码技术标准视频编码（视频压缩）是把数字视频流序列用更少的数据位进行存放的方法。视频编码技术正是将视频分成帧内编码和帧间编码，前者用于去掉图像的空间冗余信息，后者用于去除图像的时间冗余信息。20世纪90年代以来，ITU-T(国际电信联盟)和ISO(国际标准化组织)制定了一系列音视频编码技术标准（信源编码技术标准）和建议，主要有两大系列：ISO制定的MPEG系列标准，数字电视采用的是MPEG系列标准；ITU针对多媒体通信制定的H.26x系列视频编码标准。第6章数据的组织结构与算法6.1数据结构的基本概念6.2常用的几种数据结构6.3算法6.4程序设计方法6.1数据结构的基本概念6.1.1数值计算与非数值计算数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。换句话说，数据对客观事物采用计算机能够识别、存贮和处理形式所进行的描述。简言之，数据就是计算机化的信息。数学模型有定量模型和定性模型两类之分，定量模型指的是可以用数值方程表示的一类计算模型，而定性模型则是指非数值性的数据结构,如表、树和图等及其运算。6.1.2数据结构的起源数据结构（DataStructure）问题起源于程序设计的发展。第一个8008芯片只有4K的内存，微软的最初成立就是为这个芯片的机器编写BASIC语言，优化在每一处都非常重要。逐渐地，人们注意了数据表示与操作的结构化，把一些确实能够有效解决问题的数据表示和算法总结出来，如表、栈、队、树、图（稍后会介绍这些术语）等被单独抽出研究，而这些方法便形成一门学问，这就是“数据结构”这门学科的来源。6.1.3对数据结构的理解数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系。物理上的数据结构反映成分数据在计算机内部的存储安排。1.表示对象/实体及其关系在计算机中的表示。只有对象及其相互关系已存储（表示）在计算机中，才能被进一步处理；2.操作：对对象/实体进行处理、访问。数据结构的一般定义：相互之间存在着一定关系的数据元素的集合及定义在其上的操作（运算)称为数据结构。6.1.4对数据结构中数据元素的操作1.插入：在数据结构中的指定位置增添新的数据元素。2.删除：删去数据结构中指定的数据元素。3.查找：在数据结构中寻找某个特定要求的数据元素。4.排序：（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使之按某个关键字值由小到大或由大到小的次序排列。5.遍历：按某一次序访问数据结构中的每一个数据元素。6.1.5数据结构能解决什么问题[例6.1]解一元二次方程ax2+bx+c=0.

利用计算机解此方程，第一个问题就是如何在计算机中表示该方程。分析该方程，可知决定方程的是方程的三个系数值：a、b、c，而它们的次序表示它们分别属于那一项，其他符号是为增加可读性而引入的，因此，可用这三个系数的线性排列在计算机中表示该方程。例如：

3x2-x+1=0表示为（3,-1,1）

x2-3=0表示为(1,0,-3)

在数据结构中，将若干个数线性排列的数（元素）称为线性表，因此，一元二次方程ax2+bx+c=0就在计算机中表示为线性表（a,b,c）。解方程实质上是对线性表(a,b,c)进行操作。[例6-2]电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：

(a1,b1)(a2,b2)…(ai，bi)

其中ai，bi(i=1，2…n)分别表示某人的名字和对应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)，1≤i≤n。[例6-3]家族成员的族谱表示一个家族的族谱就构成了一个层次结构，在数据结构中，称为树。图6-2给出了这种族谱关系。6.1.6数据结构的图示一般用示意图表示数据结构。用小圆圈代表数据元素，用小圆圈之间的连线代表小圆圈对应的数据元素具有的关系，如果强调关系的方向性，可用带箭头的线段表示关系。具体地讲，若d1和d2表示两个数据元素，它们具有关系＜d1,d2＞，则表示为如图6-3所示的结构。

图中表示的只是一个抽象关系，不代表具体意义。对于具体的应用，也可以表示家族关系中的父子关系。例如，＜d1,d2＞可代表d1是d2的父亲。6.2常用的几种数据结构

根据数据元素之间的关系的不同，将数据结构的逻辑结构分为集合结构、线性结构、树状结构和图结构（图6-4）。6.2.1线性结构1.栈(stack)

栈是只能在某一端插入和删除的特殊线性表。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底插入一般称为进栈（Push），删除则称为退栈（Pop）。栈也称为后进先出表（LIFO：LastIn,FirstOut）。2.队列队列是限定在一端进行插入，另一端进行删除和特殊线性表。通常把队列的删除和插入分别称为出队和入队。允许出队的一端称为队头，允许入队的一端称为队尾。所有需要进队的数据项，只能从队尾进入，队列中的数据项只能从队头离去。由于总是先入队的元素先出队（先排队的人先买完东西），这种表也称为先进先表（FIFO：FirstIn,FirstOut）表。3.链表链表是指用一组任意的存储单元来依次存放线性表的数据元素。在存储每个结点值的同时，必须存储指示其后继（或前趋）结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。如果链表的每一个结点只有一个指针域，则这种链表称为单链表结点结构，如图6-9(a)所示；如果链表的每一个结点有两个指针域，则这种链表称为双链表结点结构。一个指针域指向其前趋结点，一个指针域向其后继结点。如图6-9(b)所示。[例6.4]单循环链表的应用单循环链表的一个典型例子是约瑟夫（Joseph）环，其描述如下：设有ｎ个人依次围成一圈（图6-11），从第１个人开始报数，数到第ｍ个人出列，然后从出列的下一个人开始报数，数到第ｍ个人又出列，…，如此反复到所有的人全部出列为止。设ｎ个人的编号分别为1，2，…，n，打印出出列的顺序。当n和m较大时，用人工求解约瑟夫环问题是相当繁琐的。采用单循环链表就容易解决。其基本思路是：ｎ人围成一圈，把一人看成一个结点，ｎ人之间的关系采用链接方式，即每一结点有一个前趋结点和一个后继结点，每一个结点有一个指针指向下一个结点，最后一个结点指针指向第一个结点。这就是单循环链的数据结构。当ｍ人出列时，将ｍ结点的前趋结点指针指向ｍ结点的后继结点指针，即把ｍ结点驱出循环链。6.2.3树结构

1．树的定义树是由一个或多个结点组成的有限集合，如图6-12所示。树结构的特点是：必有一个特定的称为根(ROOT)的结点，根的每个分支称为子树(Subtree)，子树也是一棵树。树中的每一个结点都可以不止一个直接后继，除根结点外的所有结点有且只有一个直接前趋。结点的前趋结点称为该结点的“父结点”（Parent）；结点的后继结点称为该结点的子结点（Children）；同一父结点的子结点称为“兄弟”（Sibling）；结点下不再有分支的称为树叶（leaf）。2．二叉树二叉树的特点是：树中的每个结点最多只有两棵子树，即树中任何结点的度数不得大于２。二叉树的子树有左右之分，称为左子树和右子树。而且子树的左右次序是重要的，即使在只有一棵子树的情况下，也应分清楚。例如图6-13是两棵不同的二叉树。3．二叉树的遍历所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。二叉树的遍历可分为前序遍历、中序遍历和后序遍历。例如前序遍历的顺序是先向着树的左方走，直到无法前进时，才转往右方走。按照此法，图6-12二叉树的前序遍历顺序是：

A

B

D

E

C

F6.2.4图结构一个图由有限的顶点（Vertices）和边（Edge）组成，所以可形式化地用G＝（V，E）代表一个图。图中的结点称为顶点，顶点之间的连线代表边。6.2.5集合如果数据结构中，数据元素之间不考虑关系问题（无前趋/后继之分），则称这种结构为集合。

在集合中，各元素是"平等"的，它们的共同关系是：都属于同一个集合。6.3算法6.3.1算法的特性算法是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。1.有穷性2.确定性3.可行性4.有输入5.有输出6.3.2什么是“好”的算法在设计算法时，通常应考虑以下原则：首先设计的算法必须是“正确的”其次应有很好的“可读性”，还必须具有“健壮性”最后还应考虑所设计算法的复杂性，即有“高效率与低存储量”。所谓算法的正确性，也称可靠性或有效性，是指算法应满足具体问题的要求。除了应该满足算法说明中写明的“功能”之外，应对各组典型的带有苛刻条件的输入数据得出正确的结果。在算法是正确的前提下，算法的可读性是摆在第一位的，算法的效率指的是算法的执行时间，算法的存储量指的是算法执行过程中所需最大存储空间。算法的健壮性指的是，算法应对非法输入的数据做出恰当反映或进行相应处理。它强调的是，如果输入非法数据时，算法应能加以识别并做出处理，而不是产生误动作或陷入瘫痪。6.3.3算法复杂性算法的复杂性有时间复杂性和空间复杂性之分。算法的复杂性是算法运行所需要的计算机资源的量，需要的时间资源的量称作时间复杂性，需要的空间（即存储器）资源的量称作空间复杂性。算法的时间复杂度是指算法的运行速度。算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。6.3.4算法的表示1．自然语言自然语言是人们日常所用的语言，如汉语、英语、德语等。2．流程图流程图是描述算法的常用工具。它采用美国国家标准化协会ANSI（AmericanNationalStandardInstitute）规定的一组图形符号来表示算法3．伪代码伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。它不用图形符号，因此书写方便格式紧凑，易于理解，便于向计算机程序设计语言过渡。4．计算机程序设计语言一般而言，计算机程序设计语言描述的算法是清晰的、简明的，最终也能由计算机处理的，然而也不是完善无缺。它需要设计者用特定程序设计语言编写的算法，限制了与他人的交流；容易陷入描述计算步骤的细节而忽视算法的本质。6.4程序设计方法6.4.1计算机程序的性质计算机程序包含两方面的内容：对象及对象之间关系(数据结构)；描述对这些对象进行处理的加工规则(算法)。计算机程序具有以下性质：

目的性—程序有明确的目的，程序运行时能完成赋予它的功能。

分步性—程序为完成其复杂的功能，由一系列计算机可执行的步骤组成。

有序性—程序的执行步骤是有序的，不可随意改变程序步骤的执行顺序。

有限性—程序是有限的指令序列，程序所包含的步骤是有限的。

操作性—有意义的程序总是对某些对象进行操作，使其改变状态，完成其功能。6.4.2程序设计与数据结构、算法之间的关系数据结构是数据构造的逻辑表示形式，算法是处理问题的方法和步骤，最后问题的解由计算机程序给出。这是程序员在程序设计时应考虑的主要问题6.4.3结构化程序设计1.程序的控制结构一个可以用顺序、选择、循环和跳转(如goto语句)四种程序结构解决的问题，也一定能用顺序、选择、循环三种程序结构解决。但确实存在这样的问题，它可以用顺序、选择、循环三种程序结构解决，但不能用其中任何两种解决。换句话说，顺序、选择、循环三种程序结构构成了一个最小完备集。我们将这三种程序结构叫基本程序结构。2.结构化程序设计方法结构化程序设计方法主要包括程序结构的自顶向下和模块化设计方法。6.4.4程序设计的步骤程序设计的一般步骤如下：1.分析问题对要解决的问题，首先必须分析清楚，明确题目的要求，列出所有已知量，找出题目的求解范围、解的精度等。2.建立数学模型对实际问题进行分析之后，找出它的内在规律，就可以建立数学模型。只有建立了模型的问题，才能可能利用计算机来解决。3.确定算法建立数学模型后，还不能着手编程序，必须根据数据结构，确定解决问题的算法。一般确定算法要注意：

算法的逻辑结构尽可能简单；

算法所要求的存贮量应尽可能少；

在满足题目条件要求下，使所需的计算量最小。4.编写程序把整个程序看作一个整体，先全局后局部，自顶向下，一层一层分解处理，如果某些子问题的算法相同而仅参数不同，可以用子程序来表示。5.调试运行；6.分析结果；7.写出程序的文档主要是对程序中的变量、函数或过程作必要的说明，解释编程思路，需要时给出程序流程图，并讨论运行结果。第7章数据库技术7.1数据库与数据库管理系统7.2关系模型与关系数据库7.3新一代数据库技术的发展7.1数据库与数据库管理系统7.1.1我们身边的数据库应用1.在超级市场购物2.用信用卡消费3.使用图书馆系统4.学籍及绩管理5.基于网络的数据库7.1.2数据库系统的组成数据库系统（DBS:DataBaseSystem）是一个整体的概念，从根本上说，它只不过是一个以计算机为基础的记录保持系统，其目的是要记录和保持信息。从数据库系统组成的一般概念而言，它主要包括数据库（DataBase）、数据库管理系统（DBMS:DatabaseManagementSystem）、数据库应用系统和数据库用户。如图7-1所示。图7-1数据库系统的组成1.数据库数据库是以一定结构存储在一起且相互关联的、结构化数据集合。更进一步地说，数据库不仅存放了数据，而且还存放了数据与数据之间的关系。一个数据库系统中通常有多个数据库，每个库由若干张表（Table）组成。2.数据库管理系统数据库管理系统的功能可以概括为下列三个方面：描述数据库：描述数据库的逻辑结构、存储结构、语义信息和保密要求等。管理数据库：控制整个数据库系统的运行，控制用户的并发性访问，检验数据的安全、保密与完整性，执行数据检索、插入、删除、修改等操作。维护数据库：控制数据库初始数据的装入，记录工作日志，监视数据库性能，修改更新数据库，重新组织数据库，恢复出现故障的数据库。3.数据库应用系统数据库应用系统是程序员根据用户需要在DBMS支持下运行的一类计算机应用系统。4.数据库用户数据库系统中有多种用户，他们分别扮演不同的角色，承担不同的任务，如图7-2所示。图7-2数据库用户终端用户：具体操作应用系统，通过应用系统的用户界面使用数据库来完成其业务活动。数据库的模式结构对最终用户是透明的。应用程序员：

以用户需求为基础编制具体的应用程序，操作数据库，数据库的映象功能保证了他们不必考虑具体的存储细节。系统分析员：因为要负责应用系统的需求分析与规范说明，需要从总体上了解、设计整个系统，因此他们必须与用户及数据库管理员相结合，确定系统的软硬件配置并参与数据库各级模式的概要设计。数据库管理员（DBA）：负责全面管理和控制数据库系统，数据库管理员的素质在一定程度上决定了数据库应用的水平，所以他们数据库系统中最重要的人员。7.1.3数据库系统的特点1.可实现数据共享2.可减少数据冗余3.在一定程度上可避免不相容4.可实施标准化5.可保证数据安全6.可保证完整性7.1.4数据库系统三级模式结构从数据库管理系统的角度来看，数据库系统通常采用三级模式结构。数据库的三级模式结构是指数据库系统是由外模式，概念模式和内模式三级模式构成。如图7-3所示。

图7-3数据库系统的3级模式结构

1.外模式亦称用户模式，是数据库用户看到的视图模式。它是数据库用户（包括应用各方和最终用户）看见使用的局部数据的逻辑结构和特征的描述，是与