参考：

• 计算机科学导论

绪论

本章的目标：

• 图灵模型
• 冯诺依曼模型
• 计算机的三大部分—：硬件、数据和软件

图灵模型

图灵在 1963 年最先提出了一个通用计算设备的设想——所有的计算都可以在一种特殊的机器上执行，这就是现在所说的图灵机。

数据处理器

把计算机定义成一个数据处理器，它接受输入数据、处理数据并产生输出数据的黑盒。

1
2

graph LR
输入数据 --> 计算机 --> 输出数据

这种模型可以表示为一种设计用来完成特定任务的专用计算机。尽管如此，计算机作为一个当今使用的术语，是一种通用的机器，它可以完成各种不同的工作。这表明我们需要将该模型改编为图灵模型来反映当今计算机的现实。

可编程数据处理器

图灵模型是一个适用于计算机的更好的模型。程序是用来告诉计算机如何对数据进行处理的指令集。

1
2
3

              程序
                |
输入数据 --> 计算机 --> 输出数据

通用图灵机

通用图灵机是对现状的首次描述，只要提供了合适的程序，该机器就能做任何运算。

冯诺依曼模型

基于通用图灵机建造的计算机都是在存储器中存储数据。冯诺依曼指出，鉴于程序和数据在逻辑上是相同的，因此程序也能存储在计算机的存储器中。

四个子系统

冯诺依曼模型建造的计算机分为四个子系统：

• 存储器：存储数据和程序。
• 算术逻辑单元：进行计算和逻辑运算。
• 控制单元：对存储器、算术逻辑单元、输入/输出子系统进行控制操作。
• 输入输出：接受数据和程序，输出处理结果。

存储程序概念

冯诺依曼模型要求程序必须存储在存储器中。这和早期只有数据才能存储在存储器中的计算机结构完全不同。完成某一任务的程序是通过操作一系列的开关或改变其配线来实现的。

现代计算机的存储器用来存储程序及其相应数据。这意味着数据和程序应该具有相同的格式，存储在存储器中。实际上它们都是以位模式（二进制 0 和 1）存储在存储器中。

指令的顺序执行

冯诺依曼模型中的一段程序由一组数量有限的指令组成。按照这个模型，控制单元从存储器中提取一条指令，解释指令，接着执行指令。

指令是一条条顺序执行。当然，一条指令可能会请求控制单元以便跳转到前面或后面的指令去执行，但这并不意味着指令没有按照顺序来执行。

指令的执行顺序是基于冯诺依曼模型的计算机的初始条件。当今的计算机以最高效的顺序来执行程序。

计算机组成部分

可以认为计算机由三大部分组成：计算机硬件、数据和计算机软件。

计算机硬件

当今的计算机硬件基于冯诺依曼模型，且包含四部分，尽管可以由不同类型的存储器，不同类型的输入/输出子系统。

计算机数据

冯诺依曼模型清楚地将计算机定义为数据处理机。

计算机软件

图灵或冯诺依曼模型的主要特征是程序的概念。编程在早期的计算机中体现为一系列开关的打开或闭合以及配线的改变。

1. 程序必须是存储的
2. 指令的序列：这个模型要求程序必须是有序的指令集，每一条指令操作一个或多个数据项。因此，一条指令可以改变它前面指令的作用。
3. 算法
4. 语言
5. 软件工程
6. 操作系统

为什么程序必须由不同的指令集组成？答案是重用性。图灵模型和冯诺依曼模型通过仔细地定义计算机可以使用的不同指令集，使编程变得相对简单。程序员通过组合这些不同的指令来创建任意数量的程序。每个程序可以是不同指令的不同组合。

在计算机时代的早期，只有一种称为 机器语言 的计算机语言。程序员依靠写指令的方式（使用位模式）来解决问题。但随着程序越来越大，采用这种模式来编写很长的程序变得很单调乏味。计算机科学家研究出利用符号来代表位模式，就像人们在日常生活中用符号（单词）来代替一些常用的指令一样。这样，计算机语言的概念诞生了。

软件工程是指结构化程序的设计和编写。

计算机操作系统最初是为程序访问计算机部件提供方便的一种管理程序。今天，操作系统所完成的工作远不止于此。

计算机历史

计算机历史的三个阶段：

• 机械计算机器（1930 年以前）
• 电子计算机的诞生（1930-1950 年）
  • 早期的电子计算机
  • 基于冯诺依曼模型的计算机
• 计算机的诞生（1950 年至今）
  • 第一代计算机（1950-1959）：使用正空管
  • 第二代计算机（1959-1965）：使用晶体管
  • 第三代计算机（1965-1975）：使用集成电路（晶体管、导线和其他部件做在一块单芯片上）
  • 第四代计算机（1975-1985）：微计算机
  • 第五代计算机（1985-）：掌上计算机和台式计算机、存储媒体、多媒体的应用和虚拟现实。

计算机科学作为一门学科

计算机科学现在被划分为几个领域，可以归纳为两大类：

• 系统领域：如计算机体系结构、计算机网络、安全问题、操作系统、算法、程序设计语言以及软件工程。
• 应用领域：如数据库和人工智能等。

本书对这些领域采用广度优先的方式介绍。

课程纲要

本书分为六大部分：

• 数据的表示与运算
  • 数字系统
  • 不同的数据如何存储在计算机中
  • 基本的位运算
• 计算机硬件
  • 计算机硬件的通用概念，不同的计算机的组成
  • 不同的单个计算机是如何连接成计算机网络以及互联网的
• 计算机软件
  • 操作系统
  • 问题求解如何归纳成为该问题编写算法
  • 程序设计语言
  • 软件开发的工程方法
• 数据组织与抽象
  • 数据结构
  • 抽象数据类型
  • 不同文件结构如何用于不同的目的
  • 数据库
• 高级话题
  • 数据压缩
  • 安全问题
  • 计算理论
  • 人工智能
• 社交媒体和社会话题

数字系统

数字系统（数码系统）定义了如何用独特的符号来表示一个数字。如 2A（16进制）和 52（8进制）都是指 42（10进制），但它们的表示截然不同。

一些数字系统已经在过去广为使用，并可与分为两类：位置化系统和非位置化系统。

位置化数字系统

在位置化数字系统中，数字中符号所占据的位置决定了其表示的值。

$$n=±S_(K-1)*b^(K-1)+S_1*b^1+…+S_(-L)*b^(-L)$$

其中，S 是一套符号集，b 是基数。

十进制系统

在该系统中，底 b = 10 并且我们用 10 个符号来表示一个数。符号集是 S = {0,1,2,3,4,5,6,7,8,9}。我们使用 ± 正负符号表示数字的正负，但这些符号并不存储在计算机中——计算机存储正负号的方式不同。

整数部分和实数部分（带有小数的部分）。

二进制系统

十六进制系统

八进制系统

位置化系统的转换

各种位置化系统之间的转换。

非位置化数字系统

非位置化系统并不用在计算机中，这里给出简单的介绍，以便和位置化数字系统进行比较。非位置化数字系统仍然使用有限的数字符号，每个符号有一个值。但是符号所占用的位置通常与其值无关——每个符号的值是固定的。

数据存储

讨论不同的数据类型以及它们是如何存储在计算机中的。

数据类型

数据的不同形式：

• 数字
• 文本
• 音频
• 图像
• 视频

计算机行业使用术语“多媒体”来定义包含数字、文本、图像、音频和视频的信息。

计算机内部的数据

所有计算机外部的数据类型的数据都采用统一的数据表示法转换后存储计算机中，当数据从计算机输出时再还原回来。这种通用格式称为 位模式。

位 （bit, binary digit）是存储在计算机中的最小单位，它是 0 或 1。

位模式 为了表示数据的不同类型，应该使用位模式，它是一个序列，有时也被称为位流。通常长度为 8 的位模式称为 1 字节。

数据压缩

为了占用较少的内存空间，数据在存储到计算机之前通常会被压缩。

错误检测和纠正

传输与存储数据时的错误检测和纠正。

存储数字

在存储到计算机内存中之前，数字会被转换到二进制系统。但这里有两个问题需要解决：

• 如何存储数字的符号
• 如何显示十进制小数点：计算机使用定点和浮点。

存储整数

整数可以被当作小数点位置固定的数字：小数点固定在最右边。

整数通常使用定点表示法存储在内存中。

无符号表示法

无符号表示法，无符号整数的范围介于 0 到无穷大。但计算机不可能表示这个范围的所有整数，通常计算机都定义了一个常量，称为最大无符号整数（$2^n-1$）。

存储无符号整数：

1. 将整数变成二进制
2. 如果二进制位数不足 n 位，则在二进制数的左边补 0，使它总位数为 n 位。

例如 十进制 7 的二进制是 111，1 字节 8 位数是 00000111。十进制 258 的二进制是 100000010，补充成完整的位数是 0000000100000010。

无符号整数的应用：

• 计数
• 寻址：计算机地址都是从 0 开始到整个存储器的总字节数的正整数。
• 存储其他数据模型

符号加绝对值表示法

符号加绝对值表示法，该格式用于在计算机中存储部分实数。

在符号加绝对值表示法中，最左边用于定义整数的符号。0 表示正整数，1 表示负整数。

如 +28 表示为 00011100，-28 表示为 10011100。

在符号加绝对值表示放中，有两个0：+0 和 -0。

二进制补码表示法

二进制补码表示法 来存储位于 n 位存储单元中的有符号整数。

在二进制补码表示法中，最左位决定符号。如果它是 0，改整数为正；如果是 1，该整数为负。

二进制补码表示法仅有一个 0。

介绍两种运算：

• 反码：简单反转各个位，即把 0 变为 1，把 1 变为 0。
• 补码：首先，从右往左复制位，直到有 1 被复制；接着，反转其余的位。

进行两次反码/补码运算，就可以得到原先的整数。

二进制补码表示法存储的整数也会溢出。

实数

实数是带有整数和小数的数字。

带有很大的整数部分或很小的小数部分的实数不应该用定点表示法存储。

浮点表示法

用于维持正确度或精度的解决方法是使用浮点表示法。该表示法允许小数点浮动：可以在小数点的左右有不同数量的数码。这种方法极大地增加了可存储的实数范围：带有很大的整数部分或很小的小数部分的实数可以存储在内存中。

一个数字的浮点表示法由三部分组成：符号、位移量和定点数。

$实际数字 -> + 7 425 000000000 000 000 000.00$

$科学计数法 -> + 7.425 x 10^21$

规范化

为了使表示法的固定部分统一，科学计数法（用于十进制）和浮点表示法（用于二进制）都在小数点左边使用了唯一的非零数码。

1
2

十进制 -> ± d.xxxxxx 注意：d是1-9，x是0-9
二进制 -> ± 1.yyyyyy 注意：y是0或1

符号、指数和尾数

在二进制数规范化之后，我们只存储了一个数的三部分信息：符号、指数和尾数。

1
2
3
4

+1000111.0101
符号  指数      尾数
+     2的6次方  1.0001110101
1     6         0001110101

余码系统

尾数可以作为无符号整数存储。指数是有符号的数。在余码系统中，正和负的整数都可以作为无符号数存储。

IEEE 标准

电气和电子工程师协会（IEEE）定义了集中存储浮点数的标准。讨论两种最常用的：

• 单精度：采用公共 32 位来存储一个浮点表示法的实数。符号占用1位（0为正，1为负），指数占用8位（使用偏移量127），尾数使用23位（无符号数）。该标准有时称为余127码。
• 双精度：采用总共 64 位来存储一个浮点表示法的实数。符号占用1位（0为正，1为负），指数占用11位（使用偏移量1023），尾数使用52位。该标准有时称为余1023码（Excess_1023）。

IEEE 标准浮点数的存储，一个实数可以存储为 IEEE 标准浮点数格式：

• 存储符号
• 将数字转换为二进制
• 规范化
• 找到位移量和定点数的值
• 连接符号、位移量和定点数

将 IEEE 标准浮点数的数字还原。

上溢和下溢

对于浮点数，有上溢和下溢两种情况。试图存储绝对值很小的数会导致下溢，而试图存储绝对值很大的数会导致上溢。

存储零

实数设置为零的时候是 0.0，无法用以上讨论的步骤存储。为了处理这个特例，约定在这种情况下符号、指数和尾数都设为零。

截断错误

原始数字与还原后数字的差异称为截断错误。在使用很小或很大数字的地方，如宇航业的计算中，这种类型的错误是很严重的。在这种情况下，需要更大的内存和其他的表示法。为此，IEEE 定义了更大尾数的其他表示法。

存储文本

在任何语言中，文本的片段是用来表示该语言中某个意思的一系列的符号。

我们可以使用位模式来标时任何一个符号。

在一种语言中，位模式到底需要多少位来表示一个符号。如使用英文大写字母 ，则只需要26个符号。相应地，这种语言的位模式也至少需要表示 26个符号。

不同的位模式集合被设计用于表示文本符号。其中每一个集合称之为代码。表示符号的过程被称为编码。

ASCII编码

美国国家标准协会（ANSI） 开发了一个称为美国信息交换标准码（ASCII）的代码。它使用 7位表示每个符号（128种不同的符号）。如今，ASCII 是 Unicode 的一部分。

Unicode

硬件和软件制造商联合起来共同设计了一种名为 Unicode 的代码，它使用 32 位。代码的不同部分被分配用于表示来自世界上不同语言的符号。其中还有些部分用于表示图形和特殊符号。

存储音频

音频表示声音或音乐。文本由可数的实体组成，文本时数字数据的一个例子。音频是不可数的。音频是随时间变化的实体，我们只能在每一时刻度量声音的密度。当我们讨论用计算机内存存储声音时，我们的意思是存储一个音频信号的密度，例如每隔一段时间来自麦克风的信号。

音频是模拟数据的例子。即使我们能够在一段时间度量所有的值，也不能把它们全部存储在计算机内存中，因为可能需要无限数量的内存。

音频采样

采样意味着我们在模拟信号上选择数量有限的点来度量它们的值并记录下来。

如果信号平滑，则需要很少的样本。如果信号变化剧烈，则需要更多的样本。每秒 40000 个样本的采样率对重现音频信号来说足够好了。

音频量化

从每个样本测量来的值是真实的数字。这意味着我们可能要为每一秒的样本存储 40000 个真实的值。但是，为每个样本使用一个无符号的数（位模式）会更简便。量化是指将样本的值截取为最接近的整数值的一种过程。如 17.2 截取为 17。

音频编码

量化的样本值需要被编码成位模式。一些系统使用无符号整数来表示样本，另一些使用有符号的整数来做。

• 每样本位：对于每个样本系统需要决定分配多少位。如8、16、24 甚至 32 位。每样本位的数量有时称为位深度。
• 位率：如果我们称位深度的数量为 B，每秒样本数为 S，我们需要为每秒的音频存储 SxB 位，该乘积称为位率 R。

声音编码标准

当今音频编码的主流标准是 MP3（MPEG Layer 3）。它采用每秒 44100 个样本以及每样本 16 位。再去掉那些人耳无法识别的信息的压缩方法进行压缩。这是一种有损压缩法。

存储图像

存储在计算机中的图像使用两种不同的技术：光栅图和矢量图。

光栅图

存储模拟图像（如照片）时，就会用到光栅图（位图）。一张图片由模拟数据组成，类似于音频信息。不同的数据密度（色彩）随空间变化。这意味着数据需要采样（扫描）。样本称为像素。

解析度 ，在图像处理中的扫描率称为解析度。如果解析度足够高，人眼不会看出再重现图像中的不连续。

色彩深度，用于表现像素的位的数量，由不同的编码技术来处理。

真彩色，用于像素编码的技术，使用 24 位来编码一个像素。每个三原色（RGB）都表示位 8 位。8 位模式可以表示 0-255 之间的一个数，所以每种色彩都由 0-255 之间的三位数字表示。注意，真彩色模式可以编码 2^24 种颜色。

索引色，许多应用程序并不需要真彩色如此大的颜色范围。索引色模式仅使用其中的一部分。在该模式中，每个应用程序从大的色彩集中选择一些颜色并对其建立索引。

例如，真彩色需要 24 位来存储一个像素，索引色模式通常使用 256 个索引，也就是 8 位来存储同样的像素。

图像编码标准，JPEG（联合图像专家组）使用真彩色模式，但压缩图像来减少位的数量。GIF（图形交换格式）使用索引色模式。

矢量图

光栅图有两个缺点：文件体积太大和重新调整图像有麻烦。放大光栅图像意味着扩大像素，所以放大后的图像看上去很粗糙。

矢量图图像编码方法并不存储每个像素的位模式。一个图像被分解成几何图形的组合，每个几何形状由数学公式表达。矢量图是由定义如何绘制这些形状的一系列命令构成的。

当要显示或打印图像时，将图像的尺寸作为输入传入系统。系统重新设计图像的大小并用相同的公式画出图像。这次情况下，每绘制一次图像，公式将重新估算一次。因此，矢量图也称为几何模型或面向对象图形。

矢量图不适合存储照片图像的细微精妙。光栅图提供了更好更生动的图片。矢量图适合应用程序采用主要的几何元素来创建图像。

存储视频

视频是图像（称为帧）在时间上的表示。一部视频就是一系列的帧一张接一张地播放而形成运动的图像。视频通常是被压缩存储的。

数据运算

数据上的运算可以分为三大类：算术运算、移位运算和逻辑运算。

逻辑运算

逻辑运算是指那些应用于模式中的一个二进制位，或在亮哥模式中相应的两个二进制位的相同基本运算。

位层次上的逻辑运算

可以应用布尔代数中定义的运算去操纵二进制位。介绍四种二进制位的位层次上的运算：

• 非（NOT）
• 与（AND）
• 或（OR）
• 异或（XOR，发音为 exclusive-or），如果输入都是 1，则输出为 0。

移位运算

移位运算移动模式中的位，改变位的位置。分为两大类：逻辑移位运算和算术移位运算。

逻辑移位运算

逻辑移位运算应用于不带符号位的数的模式。原因是这些移位运算可能会改变数的符号，此符号是由模式中最左边定义的。两类：

• 逻辑移位
  • 逻辑左移位：把每一位想向左移动一个位置，最左位丢失，最右位填0。
  • 逻辑右移位：把每一位向右移动一个位置，最右位丢失，最左位填0。
• 循环移位：回环，最左位回环称为最右位，反之。
• 算术移位运算：用二进制补码格式表示的带符号位的整数。

算术运算

算术运算包括加减乘除，适用于整数和浮点数。

整数的算术运算

虽然整数的乘除能使用重复的加减来实现，但程序是低效的，有更高效的程序（如 Booth 程序）。这里只讨论加减法。

二进制补码中的加减法，整数通常是以二进制补码形式存储的。二进制补码表示法的一个优点和缺点是加法和减法间没有区别。当遇到减法时，计算机只简单地把它转变为加法，但要为第二个数求二进制的补。

当我们进行计算机中数字上的算数运算时，要记住每个数字和结果应该在分配的二进制位的定义范围之内。

符号加绝对值整数的加减法，这种方式看起来非常复杂。

实数的算术运算

实数的乘法除法涉及用符号加绝对值表示的整数的乘法除法。

计算机组成

计算机的组成部件可以分为三大子系统：

• 中央处理器（CPU）
• 存储器
• 输入/输出子系统

中央处理器

中央处理器（CPU）用于数据的运算，在大多数体系结构中，他有三个组成部分：

• 算数逻辑单元（ALU）
• 控制单元
• 寄存器组

算数逻辑单元

算术逻辑单元（ALU）对数据进行逻辑、移位和算数运算（前面介绍了这几种运算）。

寄存器

寄存器是用来存放临时数据的高速独立的存储单元。CPU 的运算离不开大量寄存器的使用。

数据寄存器 由于越来越多的复杂运算改由硬件设备实现，所以计算机在 CPU 中使用了几十个寄存器来提高运算速度，并需要一些寄存器来保存这些运算的中间结果。

指令寄存器 计算机存储的不仅是数据，还有存储在内存中相应的程序。CPU 的主要职责是：从内存中逐条地取出指令，并将取出的指令存储在指令寄存器中，解释并执行指令。

程序计数器 程序计数器中保存着当前正常执行的指令。当前的指令执行完后，计数器将自动加 1，指向下一条指令的内存地址。

控制单元

控制单元控制各个子系统的操作。控制是通过从控制单元但其他子系统的信号来进行。

主存储器

主存储器是存储单元的集合，每一个存储单元都有唯一的标识，称为地址。数据以称为字（可以是 8/16/32/64 位）的位组的形式在内存中传入和传出。8 位称为 1 字节。

地址空间

在存储器中存取每个字都需要有相应的标识符。尽管程序员使用命名的方式来区分字，但在硬件层面上，每个字都是通过地址来标识的。所有在存储器中标识的独立的地址单元的总数称为地址空间。

例如，一个 64 KB，字长为 1 字节的内存的地址空间的范围是： 0-65535。

作为位模式的地址 由于计算机都是以位模式进行运算，因此地址本身也用位模式表示。如果一个内存是 64K（2^16），字长为 1 字节。那么就需要 16 位的位模式来确定地址。

通常，如果一个计算机有 N 个字的存储空间，那就需要有 $log_2^N$ 位的无符号整数来确定一个存储单元。

内存地址使用无符号二进制整数定义。

存储器的类型

主要有两种类型的存储器：

• 随机存取存储器（RAM）：在随机存取设备中，可以使用存储单元地址来随机存取一个数据项，而不需要存取位于它前面的所有数据项。用户可以读写 RAM，但当系统断电后数据将丢失。
  • SRAM（静态）：用传统的触发器门电路来保存数据。这些门保持状态（0或1），也就是说当通电的时候数据始终存在。它速度快，但价格昂贵。
  • DRAM（动态）：使用电容器器。如果电容器充电，则这是状态为 1；如果放电则状态为 0。因为电容器会随着时间而漏掉一部分电，所以内存单元需要周期性地刷新。比较慢，但价格便宜。
• 只读存储器（ROM）：用户只能读不能写，它的优点是非易失性。如用来存储运行的 BIOS 程序。
  • PROM（可编程只读存储器）：计算机使用者可以用它存储一些特定的程序。
  • EPROM（可擦除可编程只读存储器）：用户可以对它进行编程，但是得用一种可以发出紫外光的特殊仪器对其擦写。
  • EEPROM（电可擦除可编程只读存储器）：对它的编程和擦除使用电子脉冲。

存储器的层次结构

速度快的存储器都不便宜。解决办法是采用存储器的层次结构。

• 对速度要求很严苛时可以使用少量高速存储器。如 CPU 中的寄存器。
• 用适量的中速存储器来存储经常需要访问的数据。如高速缓冲存储器。
• 用大量的低速存储器存储那些不经常访问的数据。如主存。

高速缓冲存储器

高速缓冲存储器通常容量较小，且常置于 CPU 和主存之间。

高速缓冲存储器在任何时候都含有主存中一部分内容的副本。当 CPU 要存取主存中的一个字的时候，将按以下步骤进行：

1. CPU 将首先检查高速缓冲存储器。
2. 如果要存取的字存在，CPU 则将它复制；如果不存在，CPU 将从主存中复制一份需要读取的字开始的数据块。该数据块将覆盖高速缓冲存储器中的内容。
3. CPU 存取高速缓冲存储器并复制该字。

这种方式将提高运算的速度。

为什么高速缓冲存储器尽管存储容量小效率却很高。这是由于 80-20 规则。据观察，通常计算机花费 80% 的时间来读取 20% 的数据。换句话说，相同的数据往往被存取多次。告诉缓冲存储器，凭借其告诉，可以存储这 20% 的数据而使存取至少快 80%。

输入输出子系统

输入输出子系统可以使计算机与外界通信，并在断电的情况下存储程序和数据。输入输出设备可以分为两大类：非存储设备和存储设备。

非存储设备

非存储设备使得 CPU/内存 可以与外界通信，但它们不能存储信息。

如键盘、显示器和打印机等。

存储设备

存储设备可以存储大量的信息以备后用，它们比主存编译很多，存储的信息也不容易丢失。有时称它们为辅助存储设备，通常分为磁介质和光介质两种。

磁介质存储设备

磁介质存储设备使用磁性来存储位数据。如果一点有磁性则表示 1，没有磁性则表示 0。

磁盘 磁盘由一张张的磁片叠加而成，这些磁片由薄磁膜封装起来。信息是通过盘上每一个磁盘的读/写磁头读写磁介质来进行读取和存储的。

• 表面结构：为了将数据存储在磁盘的表面，每个盘面都被划分成磁道，每个磁道又分成若干个扇区。
• 数据存取：磁盘是一个随机存取设备。但是，某一时间可以读取的最小的存储区域只能是一个扇区。数据块可以存储在一个或多个扇区上。
• 性能：最重要的三个因素
  • 角速度：定义了磁盘的选择速度
  • 寻道时间：定义了读/写磁头寻找数据所在的磁道的时间
  • 传送时间：定义了将数据从磁盘移到 CPU/内存 所需要的时间

磁带 磁带大小不一。最普通的一种是用厚磁膜封装的半英寸塑料磁带。

• 表面结构：磁带的宽度可以分为九个磁道；磁道上的每个点可以存储 1 位的信息。垂直切面的 9 个点可以存储 8 位信息和 1 位错误检测。
• 数据存取：磁带是顺序存取设备。要想读取指定的快就需要按照顺序通过前面所有的块（如快进或快退）。
• 性能：比磁盘满，但它非常便宜。

光存储设备

光存储设备是一种新技术，它使用激光技术来存储和读取数据。使用这种技术的设备有只读光盘（CD-ROM）、可刻录光盘（CD-R）、可重写光盘（CD-RW）、数字多功能关盘（DVD）。

子系统的互联

内部连接扮演着很重要的角色，因为信息需要在这三个子系统中交换。

CPU和存储器的连接

CPU 和总线之间通常由称为总线（bus）的三组线路连接在一起。分别是：

• 数据总线：由多根线组成，每一根线上每次传送 1 位的数据。线的数量取决于计算机的字的大小。例如，计算机的字是 32 位（4 字节），那么需要有 32 根线的数据总线，以便同一时刻能够同时传送 32 位的字。
• 地址总线：允许访问存储器中的某个字，线的数量取决于存储空间的大小。如果存储器的容量为 $2^n$ 个字，那么地址总线一次传送 n 位的地址数据，因此它需要 n 根线。
• 控制总线：负责在 CPU 和内存之间传送消息。例如，必须有一个代码从 CPU 发往内存，用于指定进行的是读操作还是写操作。线数取决于所需要的控制命令的总数。如果计算机有 $2^m$ 条控制命令，那么控制总线就需要 m 根。

输入输出设备的连接

输入输出设备不能够直接与连接 CPU 和内存的总线相连。因为输入输出设备的本质与 CPU 和内存的本质不同，输入输出设备都是些机电、磁性或光学设备，而 CPU 和内存是电子设备。与 CPU 和 内存相比，输入输出设备的操作速度要慢得多。因此必须要有中介来处理这种差异。

输入输出设备是通过一种被称为输入输出控制器或接口的器件连接到总线上。每个输入输出设备都有一个特定的控制器。

控制器 或者说接口，清除了输入输出设备与 CPU 及内存在本质上的障碍。控制器可以是串行或并行的设备。串行控制器只有一根数据线连接到设备上，而并行控制器则有数根数据线连接到设备上，使得一次能同时传送多个位。最常用的如 SCCI（小型计算机系统接口）、火线、USB（通用串行总线） 和 HDMI（高清晰度多媒体接口）。

输入输出设备的寻址

通常 CPU 使用相同的总线在主存和输入输出设备之间读写数据。唯一的不同是指令。

如果指令涉及主存中的字，那么数据会在主存和 CPU 之间传送。如果指令涉及输入输出设备，那么数据会在输入输出设备和 CPU 之间传送。有两种方法对输入输出设备进行寻址，即 IO 独立寻址和 IO 存储器映射寻址。

IO独立寻址

在 IO 独立寻址中，用来读写内存的指令与用来读写输出输出设备的指令是完全不同的。有专门的指令完成对输入输出设备的测试、控制以及读写操作。每个输入输出设备有自己的地址。

例如，CPU 可以使用读命令 Read 101 从内存中读取字 101。也可以使用输入命令 Input 101 从地址端口为 101 的输入输出设备中读取数据。这里不会发生混淆，因为 Read 指令是规定从内存中读取数据，而 Input 指令则是规定从输入输出设备中读取数据。

IO存储器映射寻址

在 IO 存储器寻址中，CPU 将输入输出控制器中的每一个寄存器都看作内存中的某个存储字。换言之，CPU 没有单独的指令来表示是从内存或是输入输出设备传送数据。

例如，在指令集中只有一条 Read 指令，如果地址指定的是内存中的某个单元，则从内存中读取数据。如果地址指定的是输入输出设备中的某个寄存器，那么就从寄存器中读取数据。

存储器映射的输入输出的配置优点在于有一个较小的指令集，所有对内存的操作指令都同样适用于输入输出设备。其缺点是输入输出控制器占用了一部分内存地址。例如，如果有 5 个输入输出控制器，每个控制器有 4 个寄存器，则占用 20 个地址。相应的内存的大小就减少了 20 个字。

程序执行

当今，通用计算机使用称为程序的一系列指令来处理数据。计算机通过执行程序，将输入数据转换成输出数据。程序和数据都放在内存中。

机器周期

CPU 利用重复的机器周期来执行程序中的指令，一步一条，从开始到结束。一个简化的周期包括三步：

• 取指令：控制单元命令系统将下一条将要执行的执行复制到 CPU 指令寄存器。被复制的指令地址保存在程序计数器中。复制完成后，程序计数器自动加 1 指向内存中的下一条指令。
• 译码：指令译码的结果是产生一系列系统可以执行的二进制代码。
• 执行：控制单元发送任务命令到 CPU 的某个部件，执行相应的动作。如从内存中读数据，或者是将两个输入寄存器的内容相加并将结果保存在输出寄存器。

输入输出操作

计算机需要通过命令把数据从 IO 设备传输到 CPU 和内存。因为输入输出设备的速度比 CPU 慢得多，因此 CPU 的操作在某种程度上必须和输入输出设备同步。有三种方法被设计用于同步：

• 程序控制输入输出
• 中断控制输入输出
• 直接存储器存取

在程序控制输入输出中，采用最简单的一种同步：CPU 等待 IO 设备。

CPU 和 IO 设备之间的数据传输是通过程序中的指令实现的。当 CPU 遇到一条 IO 指令时，它就会停止工作知道数据传输完毕。CPU 不时地查询 IO 设备的状态：如果设备做好了传输准备，那么数据将被传送到 CPU；如果设备没有做好准备，那么 CPU 将继续查询 IO 设备的状态直到 IO 设备准备好为止。

这种方法最大的问题就是，当每一个单元数据被传输时，CPU 都要浪费时间去查询 IO 的状态。要注意的是，数据在输入操作后被传送到内存，在输出操作前则是从内存中取出。

在中断控制输入输出中，首先 CPU 告知 IO 设备即将开始传输，但是 CPU 并不需要不停地查询 IO 设备的状态。当 IO 设备准备好时，它通知（中断）CPU。在这个过程中，CPU 还可以做其他工作，没有阻塞。

在这种方法中，CPU 时间没有被浪费。这种方法也在 IO 设备和 CPU 之间传输数据。数据在输入操作后被传送到内存，在输出操作前则是从内存中取出。

直接存储器存取（DMA），用于在高速 IO 设备间传输大量的数据，例如磁盘、内存（不需要通过 CPU 的数据传输）。这种方法需要一个 DMA 控制器来承担 CPU 的一些功能。DMA 控制器中有寄存器，可以在内存传输前后保存数据块。

不同的体系结构

讨论一些常见的体系结构和组织。

复杂指令集计算机

复杂指令集计算机（CISC, complex instruction set computer），CISC 体系结构的设计策略是使用大量的指令，包括复杂指令。和其他设计相比，在 CISC 中进行程序设计要比在其他设计中容易很多，因为每一项简单或复杂的任务都有一条对应的指令。程序员不需要写一大堆指令去完成一项复杂的任务。

指令集的复杂性使得 CPU 和控制单元的电路非常复杂。CISC 的设计者提出了减少这种复杂性的解决方案：程序在两个层面上运行。CPU 不直接执行机器语言指令。CPU 只执行被称为微操作的简单操作。复杂指令被转化为一系列简单操作然后由 CPU 执行。这种执行机制需要一个被称为微内存的特殊内存，它负责保存指令集中的每个复杂指令的一系列操作。使用微操作的程序设计被称为微程序设计。

这种体系结构的支持者认为这使得在机器层上的程序更简洁。CISC 体系结构的一个栗子便是因特尔公司所开发的奔腾系列处理器。

精简指令集计算机

精简指令集计算机（RISC, reduce instruction set computer），RISC 体系结构的设计策略是使用少量的指令完成最少的简单操作。在 RISC 中进行程序设计比在其他设计中更难、更费时，因为复杂指令都用简单指令来模拟。

流水线技术

在早期的计算机中，每个指令的三个阶段（取指令、译码和执行）需要串行完成。换言之，指令 n 需要在指令 n+1 开始它的阶段之前完成它的所有阶段。现代计算机使用称为流水线的技术来改善吞吐量（在单位时间内完成的指令总数）。这个理念是如果控制单元能同时执行两个或三个阶段，那么下一条指令就可以在前一条指令完成前开始。换言之，当计算机在执行第一条指令的编译码阶段时，它还能执行第二条指令的取指令阶段。

当然，流水线并不像这么简单。当遇到转移指令时，就会出现一些问题。在这种情况下，在管道中的指令应该被丢弃。但是，最新的 CPU 设计已经克服了大部分缺点，有些新的 CPU 设计甚至能同时进行多个取指令周期。

并行处理

随着技术的进步，可以拥有多个控制单元、多个算术单元和多个内存单元的计算机。这个思想称为并行处理。像流水线一样，并行处理能改善吞吐量。

并行处理涉及多种技术。并行处理的总体试图由 Flynn 提出的分类法给出。此分类法把计算机的组织分成四类：

• 单指令流单数据流（SISD）
• 单指令流多数据流（SIMD）
• 多指令流单数据流（MISD）
• 多指令流多数据流（MIMD）

单指令流单数据流组织

单指令流单数据流组织表示计算机有一个控制单元、一个算术逻辑单元和一个内存单元。指令被顺序执行，每条指令可以存取数据流中的一个或多个数据项。

单指令流多数据流组织

单指令流多数据流组织表示计算机有一个控制单元、多个处理单元和一个内存单元。所有处理器单元从控制单元接收相同的指令，但在不同的数据项上操作。

多指令流单数据流组织

多指令流单数据流体系结构是属于多个指令流的多个指令作用于相同的数据项的体系结构。但它从来就未被实现。

多指令流多数据流组织

多指令流多数据流体系结构是属于多个指令流的多个指令作用于多个数据流（每条指令作用于一个数据项）。在这种体系结构中，可以同时执行多个任务。这个体系结构可以使用单个的共享内存或多个共享内存区。

5-29-MIMD

简单计算机

为了解释计算机的体系结构，还有他们的指令处理，我们引入一台简单（非真实）计算机。简单计算机有三个组成部分：CPU、存储器和输入输出子系统。

CPU

CPU 本身被分成三部分：数据寄存器、算数逻辑单元和控制单元。

上图有 16 个 16 位的数据寄存器。

控制单元具有电路，控制 ALU 的操作、对内存的存取和对 IO 子系统的存取。它有两个专用的寄存器：

• 程序计数器（PC）：保存下一条将被执行的指令的踪迹。内容指向含有下一条程序执行的主存的存储单元的地址。在每个计算机周期后，程序计数器将加 1，指向下一条程序指令。
• 指令寄存器（IR）：含有 16 位值，它是当前周期译码的指令。

主存

主存有 256(2^8) 个 16 位的存储单元。主存中既有数据，又有程序指令。前 64 个存储单元被专用于程序指令。其余存储单元被用来存储数据。

输入/输出子系统

输入输出子系统是内存地址方式的一部分。这些设备有内存映射地址。

指令集

简单计算机具有 16 条指令集合的能力。每条指令由两部分组成：

• 操作码（opcode）：指明了操作数上执行的操作的类型。
• 操作数（operand）

处理指令

简单计算机使用周期：取指令、译码和执行。

在取指令阶段，其地址由程序计数器决定的指令从内存中得到，被装入指令寄存器中。然后程序计数器加 1，指向下一条指令。

在译码阶段，指令寄存器中的指令被破译，所需的操作数从寄存器或内存中取到。

在执行阶段，指令被执行，结果被放入合适的内存单元或寄存器中。一旦第三个阶段结束，控制单元又开始新的周期。

一个简单的相加的栗子如下。

为了用简单计算机解决这个问题，有必要把前面两个整存放在寄存器中。操作的结果存放在第三个寄存器中。

ALU 只能操作那些存储在 CPU 数据寄存器中的数据。

但是，大多数计算机在 CPU 中只有有限的寄存器。如果数据项的数量很大，并且它们在程序执行过程中应该保留在计算机中，比较好的方法是把它们存储在内存中，临时地把它们调入寄存器中。

1
2
3
4
5
6
7

C=A+B

1, 把内存 M40 的内容装入寄存器 R0 (R0 <- M40)
2, 把内存 M41 的内容装入寄存器 R1 (R1 <- M41)
3, 相加 R0 和 R1 的内容，结果放入 R2 (R2 <- R0 + R1)
4, 把 R2 的内容存入 M42 中 (M42 <- R2)
5, 停机

存储程序和数据

为了遵循冯诺依曼模型，需要把程序和数据存储在内存中。

指令周期

计算机每条指令使用一个指令周期。如果有5条指令的小程序，那么需要5个指令周期。每个周期通常由三个步骤组成：取指令、译码、执行。

计算机网络和因特网

本章节的一些内容：

• 局域网（LAN）和广域网（WAN）
• 因特网和互联网
• 作为因特网网络模型的 TCP/IP 协议簇
• 定义 TCP/IP 协议簇中的各层以及它们的关系
• 应用层的应用
• 传输层协议提供的服务
• 网络层协议提供的服务
• 数据链路层使用的不同协议
• 物理层的责任
• 计算机网络中使用的不同传输媒介

计算机网络引言

定义一个网络，然后通过网络来建造小型的互联网络，最终展示因特网的结构。

网络

网络是一系列可用于通信的设备（端系统）相互连接构成的。当我们在家里通过路由器连接两台计算机时，虽然规模很小，但已经建造了一个网络。

局域网（LAN）通常是与单个办公室、建筑等主机相连的私有网络。在一个局域网中的每一台主机都有作为这台主机在局域网中唯一定义的一个标识符和一个地址。一台主机向另一台主机发送的数据包中包括源主机和目标主机的地址。

广域网（WAN）的地理跨度更大。局域网将主机相连，广域网则将交换机、路由器之类的连接设备相连。通常，局域网为机构私有，广域网则由通信公司创建并运营。

当两个或多个网络互相连接时，它们构成一个互联网络（internet）。

因特网

最值得注意的互联网时因特网（Internet），它由成千上万个互连的网络组成。

骨干网和供应商网络也被称为因特网服务供应商（ISP），骨干网通常被称为国际因特网服务供应商，供应商网络则被称为国内或地域性因特网服务供应商。

硬件和软件

如果仅仅将这些设备连接到一起，什么都不会发生。为了产生通信，既需要硬件也需要软件。

协议分层

协议定义了发送器、接收器以及所有中间设备必须遵守以保证有效地通信的规则。当通信变得复杂时，可能需要将任务分配到不同的协议层中，在这种情况下，每一个协议层都需要一个协议。

在协议分层中需要遵守的原则：

• 如果想要达到双向通信，就需要保证每一个协议层都可以进行两个对立且方向相反的工作。
• 在两个站点中每一层的两个对象必须完全相同。

TCP/IP协议簇

传输控制协议/网际协议（TCP/IP）是如今因特网中使用的协议集，TCP/IP 协议簇是一个分层协议，它由提供特定功能的交互式模块组成。分层这个术语说明了每一个高层协议都是基于一个或多个低层协议提供的服务。

源主机需要在应用层中创建消息并将其通过协议层向下发送，这样这条消息才能物理地发送至目标主机。目标主机需要在物理层接收通信并通过其他协议将其发送至应用层。

路由器只涉及三个层，由于路由器仅用来路由，所以在路由器中没有传输层和应用层。

链接层交换机只涉及两个协议层，数据链路层和物理层。

地址和数据包名称。在应用层，我们通过使用名称（如 xxx.com）来定义提供服务的站点。在传输层，地址被称为端口号，端口号的作用是在源地址和目标地址之间定义应用程序。网络层地址是独一无二的。链路层地址有时称为 MAC 地址。

应用层

应用层向用户提供服务。通信由逻辑连接提供，也就是说，假设两个应用层通过它们之间假想的直接连接发送和接收消息。

提供服务

应用层是协议簇中最高层。这一层的协议不像其他协议提供服务，它们只接收传输层的协议提供的服务。这意味着该层的协议可以轻易取出。只要新的协议可以使用传输层中任意一个协议提供的服务，这个协议就可以添加到应用层上。

由于应用层是唯一向因特网用户提供服务的层，应用层的灵活性使得新的协议可以很容易地添加到网络上。

应用层模式

在网络的生命周期中，应用程序发展出了两种模式：

• 客户机-服务器模式（C-S）：服务端提供服务，客户端请求服务。如万维网（WWW）和它的超文本传输协议（HTTP）、文件传输协议（FTP）、安全外壳协议（SSH）、邮件服务等等。
• 端到端模式（P2P）：端与端之间共享。如网络电话。它的主要挑战是安全性，在分散的服务之间创造安全的通信更为困难。

标准客户机-服务器应用

万维网（WWW 或 Web）和超文本传输协议（HTTP）

Web 是信息的存储库，这个存储库中叫做网页的文档分布在全世界并且相关的文档都链接在一起。Web 的普及和发展与以上提到的俩个术语相关：分布式和链接。网页之间的连接是通过一个叫做超文本的概念实现的。

今天的 WWW 是一个分布式客户机-服务器服务。提供的服务分布在许多地方，称为站点。每个站点存储的一个或多个文档称为网页。网页之间包含其他网页的链接。

Web 客户端（浏览器）。浏览器通常由三部分构成：控制器（接收输入）、客户端协议和解释器（如 HTML 和 JavaScript）。

Web 服务器。服务器存储网页，响应客户端请求。

统一资源定位符（URL）。作为文件，网页需要唯一的标识符来将它和其他网页区分开来。定义一个网页需要四个标识符：协议、主机、端口和路径。

超文本传输协议是一个用来定义如何编写客户机-服务器程序以便从网络中检索网页的协议。

文件传输协议

文件传输协议（FTP）是 TCP/IP 提供的标准协议，用于从一台计算机复制文件到另一台计算机。

客户端由三部分组成：用户接口、客户端控制进程和客户端数据传输进程。服务器由两部分组成：服务器控制进程和服务器传输进程。控制连接建立在控制进程间，数据连接建立在数据传输进程间。

命令和数据分开使得 FTP 效率更高。

电子邮件

电子邮件被认为是一个单向事务。

TELNET

TELNET（终端网络 TErminal NETwork），是早期的远程登录协议。它有安全问题，它以明文形式发送数据。

SSH

安全外壳（SSH）是加密数据来代替 TELNET 而设计。

域名系统

域名系统（DNS）将主机名映射到 IP 地址上的六个步骤：

1. 用户将主机名传递给文件传输客户端
2. 文件传输客户端将主机名传递给域名系统客户端
3. 每台计算机在启动之后得知一台域名系统服务器的地址。域名系统发送消息和查询给域名系统服务器，查询利用已知的域名系统服务器的 IP 地址命名文件传输服务器。
4. 域名系统服务器给出需要的文件传输服务器的 IP 地址
5. 域名系统客户端将 IP 地址传输给文件传输服务器
6. 文件传输客户端现在使用得到的 IP 地址 访问文件传输服务器

端到端模式

端到端网络如 BT下载（BitTorrent）。

准备好共享资源的网络用户称为同位体（peer）并逐渐构成网络。随着更多同位体加入和下载文件，这个文件的更多副本就会提供到组中。

由于同位体列表可能增长也可能收缩，因此问题是该模式应当如何跟踪忠实的同位体和文件位置。为了回答这个问题，需要把端到端模式分成两类：

• 集中的：也被称为混合 P2P 网络。它存在一个主服务器。
• 分散的：不依赖于集中网络，同位体形成一个物理网络之上的逻辑网络，称为重叠网络。

传输层

传输层位于应用层和网络层之间，它从网络层接收服务并且为应用层提供服务。传输层作为一个客户程序和服务器程序之间的联络，是一个进程间连接。它是一个在网络中从一点向另一点进行数据传输的端与端之间的逻辑媒介。

传输层服务

传输层可以提供的服务：

• 进程间通信
• 地址和端口号：在 TCP/IP 协议中，端口号是 0-65535（16 位）之间的整数。

传输层协议

讨论两种：UDP（用户数据报协议）和TCP（传输控制协议）。

用户数据报协议

UDP 是不可靠的无连接传输协议。它除了提供进程间通信外（而不是主机间通信），没有向网络层服务添加任何东西。它是一个极简单同时开销最少的协议，但并不可靠。

UDP 数据包叫做用户数据报，有一个固定大小为 8 字节的头部。然而，由于用户数据报是存储在总长度为 65 535 字节的 IP 数据报中，所以其整体长度会比较短。

传输控制协议

TCP 是一个面向连接的可靠协议。它明确定义了连接设施、数据传输和连接拆卸段以提供面向连接的服务。这里面向连接的服务指的是在（来自应用层）同一消息中的所有数据包之间有连接。TCP 使用序列号来定义段的顺序。序列号与每一段的字节数有关。如果一段丢失了，接收者会持有另外的段知道发送者重置丢失的那段。

TCP 将一些组合成一个叫做段的数据包。它在每一段之前加上一个头（目的是方便控制），并且将这些段发送至网络层进行传输。这些段都封装在 IP 数据报里。

网络层

TCP/IP 协议簇中的网络层负责源到目的地（主机到主机）的消息发送。

网络层提供的服务

1，打包

网络层的第一个责任就是定义打包：在源主机的网络层数据包封装有效负荷，并且从来自目的主机网络层的数据包解除有效负荷的封装。

1.1 源网络层协议从传输层协议接收数据包，添加包含源地址和目的地址以及其他网络层协议所需信息的头。

1.2 网络层协议在逻辑上将该数据包传递至目的地处的网络层协议。

1.3 目标主机接收网络层数据包，解除有效负荷的封装并将其传输至上一层协议。

如果在源主机或路径中的路由器处时数据包为碎片状，网络层有责任等待直到所有碎片达到，对它们重新组合并发送至上一层协议。

传输层的有效负荷可以封装在几个网络层数据包中。

2，数据包传递

网络层的数据包传递时无连接且不可靠的。

在网络层传递的数据是不可靠的，这意味着这些数据包可能损毁、丢失或者重复。换句话说，网络层提供的是尽力而为的传输，它不能保证数据包如我们所期望的那样到达目的地。

在网络层做数据检查成本很高，因此我们通过传输层协议中的 TCP 来保证消息没有损坏。如果在传输层的一个有效负荷损毁了，TCP 会丢弃这个数据包并要求重新发送。

网络层的无连接，不是说发送者和接收者之间没有物理连接，而是说网络层对每个数据包的处理是单独的。例如一个传输层数据包分成了 4个网络层数据包，按顺序发出（1, 2, 3, 4），但收到它们的顺序是乱的（2, 4, 3, 1）。目的地的传输成负责等待和接收所有数据包，再将它们组合在一起并传送至应用层。

3，路由

网络层负责将数据包从它的源传送到目的地。物理网络是网络（LAN 和 WAN）和连接这些网络的路由器的集合，这意味着有很多线路。网络层的职责就是找到一条最优线路，它需要一些特定的策略来定义最优路线。

网络层协议

虽然在网络层有很多协议，但主要的协议叫做网际协议（IP）。其他协议都是辅助协议，帮助 IP 完成它的职责。有两类网络协议：IPv4 和 IPv6。

第四版网际协议。

在 TCP/IP 协议簇中 IPv4 层中用来标记每个设备和互联网之间的连接的标识符叫做网络地址或 IP 地址。IPv4 地址是一种 32 位的地址。

IP 使用的数据包叫做数据报。数据报是一种长度不一的数据包，这种数据包包括两部分：头部和有效负荷。头部长度是 20-60 字节，它包含路由和传递时必要的信息。

第六版网际协议。

IPv4 的一些地址耗尽之类的缺点促进了 IPv6 的出现，是一个在扩大 IPv4 的地址空间的同时重新设计 IP 数据包的格式并修改一些辅助性协议的计划。有趣的是，IPv5 是一个从未实现过的计划。

为了防止地址耗尽，IPv6 使用 128 位来定义地址，显示为二进制或十六进制冒号的格式。IPv6 中的地址事实上定义了三个等级：站点、子网和主机的连接。IPv6 头部的长度是 40 字节，然而在这个版本中，一些扩展有时也被认为是有效负荷的一部分。

数据链路层

TCP/IP 协议簇中没有定义数据链路层的任何协议。这一层是网络中连接起来可以构成因特网的区域。

在源和目的处只包括一个数据链路层，但在每个路由器处都有两个数据链路层。

节点和链接

虽然应用层、传输层和网络层的通信都是端到端的，但数据链路层的通信是节点对节点的。传统上会将两个端主机和路由器看作节点，

局域网

局域网可以是有线或无线网络。

有线局域网

只有一种有线 LAN 幸存了下来——以太网。它的发展经历了四代：标准以太网（10 mbps）、快速以太网（100 mbps）、千兆以太网（1 Gpbs）和万兆以太网（10 Gpbs）。数据速率，也就是每秒传输的位数。

在以太网中，这些位不是一个接着一个发送的，魅族数据都被打包起来，并称为帧（frame）。帧中不仅包括从发送者到目标的数据，还带有一些诸如源 MAC 地址（48位）、目的 MAC 地址（48位）、数据类型、实际数据的信息和其他一些作为守卫来帮助检查传输中数据完整性的控制位。

无线局域网

无线通信是发展最快的技术之一。在无线 LAN 中，传输媒介是空气，信号通常在空气中传播。在这个领域现在有两种技术：无线以太网和蓝牙。

无线以太网（WiFi, wireless fidelity）

电气和电子工程师协会（IEEE）为无线 LAN 定义规格。无线 LAN 有时又称为无线以太网。然而，WiFi 其实是一个由 WiFi 联盟认证的无线 LAN。这个标准定义了两种服务：基本服务集（BSS）和扩展服务集（ESS）。扩展服务集使用了额外设备（接入点 AP）作为连接其他 LAN 或 WAN 的交换机。

蓝牙是一种无线 LAN 技术，用于连接不同的功能的设备。蓝牙是一个临时网络，也就意味着这个网络是自发的。

广域网

广域网也可以分为有线和无线。

有线 WAN:

• 点对点：拨号上网、调制解调器、数字用户线路、有线电视网络
• 交换式：骨干网

无线 WAN:

• 全球互联接入（WiMax），通过基站。
• 手机网络，移动电话或蜂窝电话。
• 卫星网络

物理层

物理层的角色是将从数据链路层接收的比特（位）转换成用于传输的电磁信号。当比特被转换为信号后，信号将被传送至传输媒介。

数据和信号

在物理层的通信是节点对节点的，但是节点交换的是电磁信号。比特不能直接发送到传输媒介，需要在传输之前先转换成信号。

模拟数据和数字数据。模拟数据指连续的信息。数字数据呈现的是离散的值。

数字化传输

计算机网络是为了将信息从一点发送到零一点而设计。这个信息需要转换成数字信号或模拟信号来进行传输。

如果数据是数据化的，需要用数数转换技术，即一种将数字数据转换成数字信号的方法。如果数据是模拟的，需要使用转换技术，即一种将模拟数据转换成数字信号的方法。

模拟传输

虽然数字化传输是令人满意的，但它需要一个专用通道。模拟传输是没有专用通道的唯一选择。

数模转换是基于数字数据的信息改变模拟信号的某个特征的过程。模模转换是基于模拟数据的信息改变模拟信号的某个特征的过程。

传输介质

在物理层产生的电子信号需要传输介质从一段传输到另一端。传输介质通常在物理层之下，并且受到物理层的直接控制。我们可以说传输介质属于第 0 层。

传输介质可以大致定义为任何将信息从源传输到目标的介质。

在电信中，传输介质可以分为：导向介质和无导向介质。

导向介质

导向介质就是那些用来提供从一个设备到另一个设备的通道的，包括：

• 双绞线（DSL 线路）
• 同轴电缆（有线电视线路）
• 光纤电缆（光纤网络）

非导向介质

非导向介质不通过物理上的导体来传播电磁波。这种通信通常归为无线通信。信号通常在自由空间中传播，这样任何有能够接收信号的设备的人都可以使用它。

电磁波范围：

• 无线电波：频率在 3 kHz - 1 GHz 之间，它们通常用于无线电通信。
• 微波：频率在 1 - 300 GHz。微波没有方向性。
• 红外波：频率在 300 GHz - 400 THz 之间。它可以用于短程通信。红外波的频率较高，无法穿透墙壁，这个特点是防止不同系统之间的干扰。如红外遥控器。红外信号对于长距离通信是无用的。另外，我们不能在室外使用红外波，因为太阳光中的红外波会对通信产生干扰。

操作系统

计算机系统由两个主要部分组成：硬件和软件。

• 硬件：计算机的物理设备
• 软件：使得硬件能够正常工作的程序的集合
  • 操作系统：控制计算机系统用户对硬件的访问
  • 应用程序：使用计算机硬件来解决用户的问题

操作系统引言

列举一些常见的操作系统的定义：

• 操作系统是介于计算机硬件和用户之间的接口
• 操作系统是一种用来使其他程序更加方便有效运行的程序
• 操作系统为通用管理程序管理者计算机系统中每个部件的活动，并确保计算机系统中的硬件和软件资源能够更加有效地使用。当出现资源使用冲突时，操作系统应能够及时处理，排除冲突。

操作系统的两个主要设计目标：

• 有效地使用硬件
• 容易地使用资源

操作系统演化

操作系统经过了很长的发展历程。

批处理系统

批处理程序设计于 20 世纪 50 年代，目的是控制大型计算机。这个时代的操作系统非常简单，只保证计算机所有资源从一个作业转移到另一个作业。

分时系统

为了有效使用计算机资源，多道程序的概念被引入。它可以将多个作业同时装入内存，并且仅当该资源可用时分配给需要它的作业。

多道程序带来了分时的概念：资源可以被不同的作业分享。每个作业可以分到一段时间来使用资源。因为计算机运行速度很快，所以分时系统对于用户使隐藏的，每个用户都感觉系统在为自己服务。

个人系统

当个人计算机产生后，需要有一类适合这类计算机的操作系统。于是，单用户操作系统就产生了（如 DOS）。

并行系统

人们对更快和更有效的需求导致了并行系统的设计：在同一个计算机中安装了多个 CPU，每个 CPU 可以处理一个程序或者一个程序的一部分。

分布式系统

资源使分布式的，只要它们通过网络连接即可。

实时系统

实时系统是指在特定时间限制内完成任务。

组成部分

现代操作系统至少具有以下四种功能：

• 内存管理
• 进程管理
• 设备管理
• 文件管理
• 用户界面或命令解释程序（其他）：它负责操作系统与外界的通信。

用户界面

用户界面用来接收用户（进程）的输入并向操作系统解释这些请求的程序。如 Unix 的用户界面被称为命令解释程序（shell）。

内存管理器

现代操作系统的一个重要职责是内存管理。内存分配必须进行管理以避免内存溢出的错误。操作系统按照内存管理可以分为两类：单道程序和多道程序。

单道程序

单道程序中，大多数内存用来装载单一的程序，仅仅一小部分用来装载操作系统。在这种配置下，整个程序装入内存运行，运行结束后，程序区域由其他程序取代。

这里的内存管理器简单明了，即将程序载入内存、运行它、再装入新程序。但仍有一些问题：

• 程序必须能够载入内存。如果内存容量比程序小，程序将无法运行。
• 当一个程序运行时，其他程序不能运行。程序需要与 IO 设备交互，其他程序不能运行，导致 CPU 和内存的使用效率很低。

多道程序

多道程序中，同一时刻可以装入多个程序并且能够同时被执行。CPU 轮流为其服务。

• 非交换范畴：程序在运行期间始终驻留在内存中
• 交换范畴：在运行过程中，程序可以在内存和硬盘之间多次交换数据。

分区调度技术。在这种模式中，内存被分为不定长的几个分区。每个部分或分区保存一个程序。CPU 在各个程序之间交替服务。

在这种技术下，每个程序完全载入内存、并占用连续的地址。分区调度改进了 CPU 的使用效率，但仍有一些问题：

• 分区的大小必须由内存管理器预先决定。如果分区小了，有些程序就不能载入内存。如果分区大了，就会出现空闲区。
• 即使分区在刚开始时比较合适，但随着新程序的交换载入内存后有可能出现空闲区。
• 当空闲分区过多时，内存管理器能够紧缩分区并删除空闲区和创建新区，但这将增加系统额外开销。

分页调度提高了分区调度的效率。在分页调度下，内存被分成大小相等的若干部分，称为帧。程序则被分为大小相等的部分，称为页。页被载入内存中的帧。在这种技术下，程序在内存中不必是连续的。

分页调度在一定程度上提高了效率，但整个程序仍需要在运行前全部载入内存。

在请求分页调度中，程序被分为页，但是页可以一次载入内存、运行，然后被另一个页替代。换句话说，内存可以同时载入多个程序的页。

在请求分段调度中，程序将按程序员的角度划分成段，它们载入内存中、执行，然后被来自同一程序或其他程序的模块所替代。

请求分页和分段调度结合了两者的有点以提高系统效率。一个段也许太大而不能载入内存中的空闲区。内存可以分成很多帧，一个模块可以分成很多页，一次装入内存运行。

虚拟内存

请求分页调度和请求分段调度意味着当程序运行时，一部分程序驻留在内存中，一部分则放在硬盘上。

例如，10 MB 内存可以运行 10 个程序。每个程序 3 MB，一共 30 MB。任一时候 10 个程序中 10 MB 在内存中，还有 20 MB 在磁盘上。这里实际上只有 10 MB 内存但却有 30 MB的虚拟内存。

虚拟内存意味着请求分页调度、请求分段调度，或两者都有。如今几乎所有的操作系统都使用了该技术。

进程管理器

现代操作系统关于指令集有三个术语：程序、作业和进程。

程序是由程序员编写的一组稳定的指令。

从一个程序被选中执行，到其运行结束并再次成为一个程序的这段过程中，该程序称为作业。

进程是一个运行中的程序。换句话说，进程是驻留在内存中运行的作业，一个进程可以处于运行状态或等待 CPU 调用。

状态图显示了每个实体的不同状态。

将一个作业或进程从一个状态改变为另一个状态，进程管理器使用了两个调度器：作业调度器和进程调度器。

作业调度器将一个作业从保持状态转入就绪状态，或是从运行状态转入终止状态。换句话说，作业调度器负责从作业中创建一个进程和终止一个进程。

进程调度器将一个进程从一个状态转入另一个状态。

事实上，会有很多的作业和进程相互竞争计算机资源。为了处理多个进程和作业，进程管理器使用队列（等待列表）。与每一作业或进程相关的是存有这些作业和进程信息的作业控制块或进程控制块。进程管理在队列中存储的不是作业或进程，而是作业或进程控制块。作业或进程仍保存在内存或硬盘中，它们因为太大而无法被复制到队列中。这些作业控制块或进程控制块就是等待中的作业和进程的代表。

一个操作系统有很多队列。进程管理器可以使用多种策略从队列中选择下一个作业或进程，可以是先进先出、最短长度有线、最高优先级等。

• 作业队列：用来保存那些等待内存的作业。
• 就绪队列：用来保存那些已经在内存中准备好运行但在等待 CPU 的进程。
• I/O队列：用来保存那些正在等待 I/O 设备的进程。

所有进程管理的思想都是使得拥有不同资源的不同进程同步。只要资源可以被多个用户（进程）同时使用，那么它就可能有两种有问题的状态：死锁和饥饿。

在大多数操作系统中，文件都是不可共享的。当文件被一个进程使用时，将不能再被别的进程使用。在这种情况下，如果没有强制一个进程释放文件的防备措施，就会发生死锁。

死锁发生在操作系统允许一个进程运行，而不用首先检查它所必需的资源是否准备好，是否允许这个进程占有资源直到它不需要为止。操作系统中需要一些措施来防止死锁。一种解决方法是当所需资源不空闲时，不允许程序运行。但后面会发现这样做将导致另一种问题。另一种解决方法时限制进程占有资源的时间。

当操作系统没有对进程的资源进行限制时将会发生死锁。

死锁不是经常发生，发生死锁需要 4 个必要条件：

• 互斥：一个资源只能被一个进程占有；
• 资源占有：一个进程占有一个资源，即使在获取其他资源之前无法使用它；
• 抢先：操作系统不能临时对资源重新分配；
• 循环等待：所有的进程和资源包含在一个循环里。

所有四个条件都是死锁发生所必须的。但是它们只是必要条件（不是充分条件），也就是说对于死锁来说它们必须同时出现，但它们并不一定能引起死锁。换句话说，如果它们其中之一没有出现，死锁不会发生。

只要不让它们中的某一个条件发生，就能避免死锁。

饥饿是一种与死锁相反的情况。它发生在当操作系统对进程分配资源有太多限制的时候。

例如，假使一个操作系统中规定一个进程只有在所需的所有资源都为其占有时才能执行。

设备管理器（或输入输出管理器）负责访问输入输出设备。在计算机系统中，输入输出设备存在着数量和速度上的限制。

由于速度相比 CPU 和内存很慢，所以当一个进程访问输入输出设备时，在这段时间内这些设备对其他进程而言是不可用的。设备管理器负责让输入输出设备使用起来更有效。

简要的设备管理器的功能：

• 设备管理器不停地监视所有的输入输出设备，以保证它们能够正常运行。管理器也需要知道何时设备已经完成一个进程的服务，而且能够为队列中下一个进程服务。
• 设备管理器为每一个输入输出设备维护一个或多个队列。
• 设备管理器控制用于访问输入输出设备的不同策略。

文件管理器

现今的操作系统使用文件管理器来控制对文件的访问。

简单的文件管理器的功能：

• 文件管理器控制文件的访问。只有那些获得允许的应用程序才能够访问，访问方式也可以不同。
• 文件管理器管理文件的创建、修改和删除。
• 文件管理器可以给文件命名。
• 文件管理器管理文件的存储：怎样存储，存在哪里等。
• 文件管理器负责归档和备份。

主流操作系统

三种用户熟悉的操作系统，使用 C/C++ 等独立于某种计算机系统的机器语言。

• UNIX：多用户、多道程序、可移植的操作系统，它被设计来方便编程、文本处理、通信。
• Linux：1997 年发布的 Linus 2.0 内核成为商业操作系统，它具有传统 UNIX 的所有特性。
• Windows：微软开发的视窗界面操作系统。

算法

本章的目标：

• 定义算法，并于问题求解关联；
• 定义三种结构（顺序、选择和循环），并描述它们再算法中的作用；
• 描述 UML（统一建模语言） 图和当表示算法时它们是如何使用的；
• 描述伪代码和当表示算法时它们是如何使用的；
• 列出基本算法和它们的应用；
• 描述排序的概念，理解三种原始排序算法背后的机制；
• 描述搜索的概念，理解两种常见搜索算法背后的机制；
• 定义子算法和它们与算法的关系；
• 区分迭代和递归算法。

算法的概念

算法是一种逐步解决或完成任务的方法。

按照这种定义，算法完全独立于计算机系统。更特别的是，算法接收一组输入数据，同时产生一组输出数据。

算法的三种结构

计算机专家为结构化程序或算法定义了三种结构。这种想法认为程序必定是由顺序、判断（选择）和循环这三种结构组成的。

算法的表示

这里介绍统一建模语言和伪代码这两种工具。

统一建模语言

统一建模语言（UML）是算法的图形表示法。它使用大图的形式因该了算法的所有细节，只显示算法从开始到结束的整个流程。

伪代码

伪代码是算法的一种类似英语的表示法。

示例，用伪代码写出求两个整数之和的算法。

1
2
3
4
5
6
7
8
9

算法: SumOfTwo(first, second)
目的：求两个整数之和
前提：给定两个整数（first, second）
后续：无
返回：和的值
{
  sum <- first + second
  return sum
}

更正式的定义

算法是一组明确步骤的有序集合，它产生结果并在有限的时间内终止。

算法更正式的定义：

• 定义良好：算法必须是一组定义良好且有序的指令集合。
• 明确步骤：算法的每一步都必须有清晰、明白的定义。
• 产生结果：算法必须产生结果，否则该算法就没有意义。
• 在有限的时间内终止：算法必须能够终止。如果不能（如无限循环），说明不是算法。

基本算法

有一些算法在计算机科学中应用非常普遍，我们称之为基本算法。

求和算法

怎样才能实现一系列整数相加呢？答案很简单：在循环中使用加法操作。

求和算法可分为三个逻辑部分：

• 将和初始化。
• 循环，在每次迭代中将一个新数加到和上。
• 退出循环后返回结果。

乘积算法

乘积算法的实现：在循环中使用乘法操作。

乘法算法有三个逻辑部分：

• 将乘积初始化
• 循环，在每次迭代中将一个新数与乘积相乘。
• 退出循环后返回结果。

最大值和最小值的算法

求一组数中的最大/小值，思路是通过一个判断结构求出两个数中的最大/小值，再把这个结构放到循环中，就可以一组数中的最大/小值。

排序算法

计算机科学中一个最普遍的应用是排序，即根据数据的值对它们进行排序。人们的周围充满了数据，如果这些数据都是无序的，可能会花很多时间去查找一条简单信息。

本节介绍三种排序算法：选择排序、冒泡排序和插入排序。这三种排序算法是当今计算机科学中使用的快速排序的基础。

选择排序

在选择排序中，数字列表可分为两个子列表（已排序和未排序的），它们通过假想的一堵墙分开。求未排序子列表中最小的元素并把它和未排序子列表中的第一个元素进行交换，经过每次选择和交换，两个子列表中假想的这堵墙向前移动一个元素，这样每次排序列表中将增加一个元素而未排序列表中将减少一个元素，每次把一个元素从未排序列表移动到已排序列表就完成了一轮排序。

一个含有 n 个元素的数字列表需要 n-1 轮排序来完成数据的重新排列。

选择排序算法使用两重循环，外层循环每次扫描时迭代一次，内存循环在未排序列表中求最小的元素。

冒泡排序

在冒泡排序方法中，数字列表被分为两个子列表：已排序的和未排序的。在未排序子列表中，最小的元素通过冒泡的方法选出来并移到已排序子列表中。当把最小的元素移动到已排序列表后，墙向前移动一个元素，使得已排序元素的个数增加 1，而未排序元素的个数减少 1。每次元素从未排序子列表中移到已排序子列表中，便完成一轮。

一个含有 n 个元素的列表，冒泡排序需要 n-1 轮来完成数据排序。

冒泡排序在最初被编写为将列表中的最大元素向下冒泡。从效率的观点来看，无论是大数冒泡还是小数冒泡并没有什么区别。

冒泡排序也是用两重循环，外层循环每轮迭代一次；内存循环的每次迭代将某一元素冒泡至顶部。

插入排序

插入排序是最常用的排序技术之一，经常在扑克牌游戏中使用。玩家将拿到的每张牌插入手中合适的为止，以便手中的牌以一定的顺序排列。

在插入排序中，排序列表被分为两部分：已排序和未排序的。在每轮，把未排序子列表中的第一个元素转移到已排序子列表中，并且插入合适的为止。

一个含有 n 个元素的列表至少需要 n-1 轮排序。

插入排序算法的涉及类似于选择排序算法和冒泡排序算法的模式。外层循环每轮都迭代，内存循环则寻找插入的位置。

其他排序算法

这里讨论的三种排序算法是效率最低的排序算法，如果要排序的列表中有多于几百个元素，那么不应该使用这些算法。讨论这些算法仅出于学习的目的，但它们不实用。

在一本导论书中讨论这些排序算法有几个原因：

• 它们是最简单的算法，容易理解和分析
• 它们是更高效算法的基础，如快速排序、堆排序、Shell 排序、桶排序、合并排序和基排序等。

大多数这些高级排序算法在数据结构的图书中有讨论。

为了决定哪种算法更适合特定的程序，需要一种叫做算法复杂度的度量。

查找算法

计算机科学中还有一个常用的算法叫做查找，是一种在列表中确定目标所在位置的算法。

在列表中，查找意味着给定一个值，并在包含该值的列表中找到第一个元素的位置。对于列表则有两种基本的查找方法：顺序查找和折半查找。顺序查找可以在任何列表中查找，折半查找则要求列表是有序的。

顺序查找

顺序查找用于在无需列表中查找。顺序查找算法很慢。一般来说，可用这种方法来查找较小的列表或不常用的列表。其他情况下，最好的方法是首先将列表排序，然后使用折半查找。

顺序查找从列表起始处开始查找，当找到元素或确信查找目标不在列表中时，查找过程结束。

折半查找

如果列表是无序的，则顺序查找是唯一的方法。如果这个列表是有序的，那么就可以使用一个更有效率的方法，称为折半查找。

折半查找是从一个列表的中间元素来测试的。这将能够判别出目标在列表的前半部分还是后半部分。换句话说，可以通过判断减少一般的列表。

重复这个过程，直到找到目标或确定目标不在这个列表里。

子算法

结构化编程的原则要求将算法分成几个三元，称为子算法。每个子算法又分成更小的子算法。

使用子算法的优点：

• 程序更容易理解。
• 子算法可在主算法中的不通地方调用，而无需重写。

结构图

结构图是一种高级设计工具，它显示了算法和子算法之间的关系。它一般在设计阶段使用，而不是在编程阶段。

递归

通常，有两种途径可用于编写解决问题的算法。一种使用迭代，另一种使用递归。递归是算法自我调用的过程。

迭代的定义

一个简单的栗子，考虑一个阶乘的计算。阶乘的因此供 1 到该数的证书。如果算法的定义不涉及算法本身，则算法是迭代的。

递归的定义

如果每一个算法出现在它本身的定义中，该算法就是递归定义的。

由这个示例看，似乎递归计算花费时间更长且更困难。那么为什么我们要用递归呢？虽然递归在使用纸和笔来解决问题时看起来很困难，但如果使用计算机则变得更简单和优美。而且，对于编程人员和程序阅读者在概念上很容易理解。

程序设计语言

本章的目标：

• 描述从机器语言到高级语言的编程语言演化；
• 理解如何使用编译器将高级语言中的程序编译成机器语言；
• 区分四种计算机语言模式；
• 理解面向过程模式和在模式中程序单元与数据项间的交互；
• 理解面向对象模式和在这种模式中程序单元与对象间的交互；
• 定义函数式模式，理解它的应用；
• 定义声明式模式，理解它的应用；
• 定义面向过程和面向对象语言中的常见概念。

程序设计语言的演化

对于计算机而言，编写程序就必须使用计算机语言。计算机语言是指编写程序时，根据事先定义的规则（语法）而写出的预定语句集合。计算机语言净多过年的发展已经从机器语言演化到高级语言。

机器语言

在计算机发展的早期，唯一的程序设计语言是机器语言。每台计算机都有自己的机器语言，这种机器语言由 0 和 1 的序列组成。

机器语言是计算机硬件唯一能理解的语言，它由具有两种状态的电子开关构成：关（0）和开（1）。

虽然用机器语言编写的程序真实地表示了数据是如何被计算机操纵的。但它至少有两个缺点：

• 首先，它依赖于计算机。如果使用不同的硬件，那么两者的机器语言就不相同。
• 其次，用机器语言编写程序时非常单调乏味的，而且很难发现错误。

下表是两个整数相加的机器语言代码。

现在我们将机器语言时代称为编程语言的第一代。

汇编语言

汇编语言中接下来的演化是伴随着用带符号或助记符的指令和地址代替二进制码而发生的。因为它们使用符号，所有又被称为符号语言。这些助记符语言后来被称为汇编语言。

下表是两个整数相加的汇编语言代码。

称为汇编语言的特殊程序将用于将汇编语言代码翻译成机器语言。

高级语言

尽管汇编语言大大提高了编程效率，但仍然需要程序员在所使用的硬件上花费大部分精力。用符号语言编程也很枯燥，因为每条机器指令都必须单独编码。为了提高程序员效率以及从关注计算机转到关注要解决的问题，促进了高级语言的发展。

高级语言旨在使程序员摆脱汇编语言繁琐的细节。高级语言同汇编语言有一个共性：它们必须被转化为机器语言，这个转化过程称为解释或编译。

数年来，人们开发了各种各样的语言，如 BASIC、Pascal、C、C++ 和 Java 等。

翻译

当今程序通常是使用一种高级语言来编写。为了在计算机上运行程序，程序需要被翻译成它要运行在其他的计算机的机器语言。

高级语言程序被称为源程序，被翻译成的机器语言程序称为目标程序。有两种方法用于翻译：编译和解释。

编译

编译程序通常把整个源程序翻译成目标程序。

解释

有些计算机语言使用解释器把源程序翻译成目标程序。解释是指把源程序中的每一行翻译成目标程序中相应的行，并执行它的过程。

解释中有两种趋势：

• 解释的第一种方法，在 Java 语言之前
• 解释的第二种方法，Java 使用。

在 Java 语言之前的有些解释式语言（如 BASIC）使用的解释，源程序的每一行被翻译成被其使用的计算机上的机器语言，改行机器语言被立即执行。如果在翻译和执行中有任何错误，过程就显示消息，其余的过程就被中止。程序需要被改正，再次从头解释和执行。第一种方法被看成一种慢的过程，这就是大多数语言使用编译而不是解释的原因。

随着 java 的到来，一种新的解释过程就被引入了。Java 语言能向任何计算机移植。为了取得可移植性，源程序到目标程序的翻译分成两步进行：编译和解释。Java 源程序首先被编译，创建 Java 的字节代码，字节代码看起来像机器语言中的代码，但不是任何特定计算机的目标代码，它是一种虚拟机的目标代码，该虚拟机称为 Java 虚拟机或 JVM。字节代码然后能被任何运行 JVM 模拟器的计算机编译或解释，也就是运行字节代码的计算机只需要 JVM 模拟器，而不是 Java 模拟器。

翻译过程

编译和解释的不同在于，编译在执行前翻译整个源代码，而解释一次只翻译和执行源代码中的一行。但两种方法都遵循西面相同的翻译过程。

编程模式

当今计算机语言按照它们使用的解决问题的方法来分类。因此，模式是计算机语言看待要解决问题的一种方式。计算机语言可分为 4 中模式：

• 过程式（强制式）
• 面向对象
• 函数式
• 声明式

过程式模式

在过程式模式（强制性模式）中，我们把程序看成是操纵被动对象的主动主体。我们在日常生活中遇到许多被动对象：石头、书、灯等。一个被动对象本身不能发出一个动作，但它能从主动主体接收动作。

过程式模式下的程序就是主动主体，该主体使用称为数据或数据项的被动对象。作为被动对象的数据项存储在计算机的内存中，程序操纵它们。为了操纵数据，主动主体（程序）发出动作，称之为过程。

我们需要把过程与程序触发区分开。程序不定义过程，它只触发或调用过程。过程必须已经存在。

当使用过程式高级语言时，程序仅由许多过程调用构成，除此之外没有任何东西。

如果我们考虑过程和操作对象，那么过程式模式的概念就变得更为简单，且容易理解。这种模式的程序由三部分构成：对象创建部分、一组过程调用和每个过程的一组代码。有些过程在语言本身中已经被定义。通过组合这些代码，开发者可以建立新的过程。

面向对象模式

面向对象模式处理活动对象，而不是被动对象。我们在日常生活中遇到许多活动对象：汽车、自动门、洗盘机等。在这些对象上执行的动作都包含在这些对象中：对象只需要接收合适的外部刺激来执行其中一个动作。

比较过程式模式和面向对象模式，过程式模式中的过程是独立的实体，但面向对象模式中的方法是属于对象领地的。

相同类型的对象可以共享或继承方法。

面向对象模式的一些特性：

• 类：相同类型的对象需要一组方法，为了创建这些方法，面向对象语言使用了称为类的单元。
• 方法：每个方法有它的头、局部变量和语句。
• 继承性：指一个对象能从另一个对象继承。
• 多态性：指我们可以定义一些具有相同名字的操作，而这些操作在相关类中做不同的事情。

函数式模式

在函数式模式中程序被看成是一个数学函数。函数式语言主要实现以下功能：

• 函数式语言预定义一系列可供任何程序员调用的原始函数。
• 函数式语言允许程序员通过若干原始函数的组合创建新的函数。

函数式语言相对过程式语言具有两方面优势：它支持模块化编程并且允许程序员使用已经存在的函数来开发新的函数。这两个因素使得程序员能够写出庞大而且不易出错的程序。

声明式模式

声明式模式依据推理的原则响应查询。

声明性语言也有自生的缺憾，那就是有关特殊灵枢的程序由于要收集大量的事实信息而变得非常庞大。

共同概念

标识符，即对象的名称。标识符允许给程序中的对象命名。

数据类型定义了一系列值及应用于这些值的一系列操作。每种数据类型值得集合称为数据类型得域。大多数语言都定义了两种数据类型：

• 简单数据类型：有时称为原子类型、基本类型、标量类型或内建类型。是不能分解成更小数据类型得数据类型。
  • 整数类型
  • 实数类型
  • 字符类型
  • 布尔类型
• 复合数据类型：是一组元素，其中每个元素都是简单数据类型或复合数据类型。
  • 数组是一组元素，其中每个元素具有相同的类型。
  • 记录是一组元素，其中得每个元素可以具有不同得类型。

变量是存储单元的名字。虽然计算机内部使用地址，但对程序员而言却十分不便。

字面量是程序中使用的预定义的值。

字面量被看作一种不好的编程实践，除非我们能确信字面值将不会随时间而改变。但是大多数字面值都会随时间而改变它的值。

由于这个原因，大多数语言定义常量。常量的值不能改变。

几乎所有的程序都需要输入和输出。

表达式是由一系列操作数和运算符简化后的一个单一数值。

• 运算符
  • 算数运算符
  • 关系运算符
  • 逻辑运算符
• 操作数

每条语句都使程序执行一个相应动作。

• 赋值语句
• 符合语句
• 控制语句

子程序在过程式语言中极其重要，在面向对象语言中作用要少些。

软件工程

本章的重点：

• 软件生命周期的概念；
• 开发过程模型——瀑布模型和增量模型；
• 分析阶段，分析阶段两种独立的方法——面向过程分析和面向对象分析；
• 设计阶段，设计阶段的两种独立的方法——面向过程设计和现象对象设计；
• 实现阶段，识别该阶段的质量问题；
• 测试阶段，区分白盒测试和黑盒测试；
• 识别软件工程中文档的重要性，区分用户文档、系统文档和技术文档。

软件生命周期

软件生命周期是软件工程中一个基础概念。软件和其他产品一样，周期性地重复着一些阶段。

开发过程模型

开发过程最常见的两种模型：

• 瀑布模型：在这种模型中，开发过程只能一个方向的流动。这意味着前一阶段不结束，后一阶段不能开始。
• 增量模型：在此模型中，软件开发要经历一系列步骤。开发者首先要完成整个系统的一个简化版本，这个版本表示了整个系统，但不包括具体的细节。

分析阶段

整个开发过程始于分析阶段，这个阶段生成规格说明文档，这个文档说明了软件要做什么，而没有说明如何去做。

面向过程分析

面向过程分析（结构化分析或经典分析）使用的工具：

• 数据流图：显示了系统中数据的流动。
• 实体关系图
• 状态图：通常用于当系统中的实体状态在响应时间时将会改变的情况下。

面向对象分析

面向对象分析使用的工具：

• 用例图：它显示了用户与系统间的交互。
• 类图
• 状态图

设计阶段

设计阶段定义系统如何完成在分析阶段所定义的需求。在设计阶段，系统所有的组成部分都被定义。

面向过程设计

在面向过程设计中，我们既要设计过程，也要设计数据。在面向过程设计中，整个系统被分解成一组过程或模块。

• 结构图：说明模块间的关系。
• 模块化：将大项目分解成较小的部分，以便能够容易理解和处理。

当系统被分解成模块时，主要关心两点：耦合和内聚。

耦合是对两个模块互相绑定成都的度量。越紧耦合的模块，它们的独立性越差。既然目标是为了让模块尽可能地独立，你需要让它们松散耦合。至少有三条理由说明松散耦合是希望的：

• 松散耦合的模块更可能被重用
• 松散耦合的模块不容易在相关模块中产生错误
• 当系统需要修改时，松散耦合的模块允许我们只修改需要改变的模块，而不会影响到不需要改变的模块。

软件系统中模块间的耦合必须最小化。

内聚是程序中处理过程相关紧密成都的度量。

软件系统中模块间的内聚必须最大化。

面向对象设计

在面向对象设计中，设计阶段通过详细描述类的细节来继续。类由一组变量（属性）和一组方法组成。面向对象设计阶段列出这些属性和方法的细节。

实现阶段

在实现阶段，程序员为面向过程设计中的模块编写程序或编写程序单元，实现面向对象设计中的类。

在每种情况中，都有一些我们需要提及的问题。

语言的选择

选择合适的编程语言。

软件质量

软件质量是一个非常重要的问题。具有高质量的软件系统是一个能满足用户需求、符合组织操作标准和能高效运行在其开发的硬件上的一个软件。

软件质量能够划分成三个广义的度量：

• 可操作性：可操作性涉及系统的基本操作。可操作性有多种度量方法：准确性、高效性、可靠性、安全性、及时性和适用性。
• 可维护性：可维护性以保持系统正常运行并及时更新为参照。
• 可迁移性：可迁移性是指把数据和系统从一个平台迁移到另一个平台并重用代码的能力。

测试阶段

测试阶段的目标是发现错误，这就意味着良好的测试策略能发现最多的错误。有两种测试：白盒测试和黑盒测试。

白盒测试

白盒测试（玻璃盒测试）是基于软件内部结构的。测试的目标是检查软件所有的部分是否全部设计出来。白盒测试假定测试者知道有关软件的一切。在这种情况下，程序就像玻璃盒子，其中的每件事都是可见的。

使用白盒测试需要保证至少满足下面四个标准：

• 每个模块中的所有独立的路径至少被测试过一次。
• 所有的判断结构每个分支都被测试。
• 每个循环被测试。
• 所有数据结构都被测试。

讨论两种白盒测试方法：基本路径测试和控制结构测试。

基本路径测试由 Tom McCabe 提出。这种方法创建一组测试用例，这些用例执行软件中的每条语句至少一次。

基本路径测试是一种软件中每条语句至少被执行一次的方法。

基本路径测试使用图论和圈复杂性找到必须走过的独立路径，从而保证每条语句至少被执行一次。

控制结构测试比基本路径测试更容易理解并且包含基本路径测试。此方法使用下面三种不同类的测试。

• 条件测试：应用于模块中的条件表达式，简单条件是关系表达式，而复合条件是简单条件和逻辑运算符的组合。条件测试用来检查是否所有的条件都被正确设置。
• 数据流测试：基于通过模块的数据流。这种测试选择测试用例，这些用例涉及检查被用在赋值语句左边的变量的值。
• 循环测试：使用测试用例检查循环的正确性。所有类型的循环被仔细检查。

黑盒测试

黑盒测试在不知道程序的内部也不知道程序是怎样工作的情况下测试程序。换言之，程序就像看不见内部的黑盒。黑盒测试按照软件应该完成的功能来测试软件，如它的输入和输出。

下面介绍集中黑盒测试方法。

• 穷尽测试：最好的黑盒测试方法就是用输入域中的所有可能的值去测试软件。但是，在复杂的软件中，输入域是如此巨大，这样做常常不现实。
• 随机测试：在随机测试中，选择输入域的子集来测试，子集选择的方式（值在输入域上的分布）是非常重要的。在这种情况下，随机数生成器是非常有用的。
• 边界值测试：当遇到边界值时，错误经常发生。

文档

软件的正确使用和有效维护离不开文档。通常软件有三种独立的文档：用户文档、系统文档和技术文档。

注意，文档是一个持续的过程。如果软件在发布之后有问题，也必须写文档。如果软件被修改，那么所有的修改与原软件包间的关系都要被写进文档。只有当软件包过时后，编写文档才停止。

用户文档

用户手册的文档对用户时必不可少的。它告诉用户如何一步步地使用软件包。

系统文档

系统文档定义软件本身。撰写系统文档的目的是让原始开发人员之外的人能够维护和修改软件包。系统文档在系统开发的所有四个阶段都应该存在。

• 在分析阶段，收集的信息应该仔细地使用文档记录。
• 在设计阶段，最终版本中用到的工具必须记录在文档中。
• 在实现阶段，代码的每个模块都应记录在文档中。另外，代码应该使用注释和描述尽可能详细地形成自文档。
• 最后，开发人员必须仔细地形成测试阶段的文档。

技术文档

技术文档描述了软件系统的安装和服务。

数据结构

数据结构利用了有关变量的集合，而这些集合能够单独作为一个整体被访问。换句话说，一个数据结构代表了有特殊关系的数据的集合。

本章讨论三种数据结构：数组、记录和链表，大多数编程语言都隐式实现了前两种，而第三种则通过指针和记录来模拟。

本章的目标：

• 定义数据结构；
• 把数组定义为数据结构，并说明它是如何用于存储数据项列表的；
• 区分数组的名字和数组中元素的名字；
• 描述为数组定义的操作；
• 把记录定义为数据结构，并说明它是如何用于存储属于单个数据元素的属性；
• 区分记录的名字和它的域的名字；
• 把链表定义为数据结构，并说明它是如何用指针来实现的；
• 描述为链表定义的操作；
• 比较和区分数据、记录和链表；
• 说明数组、记录和链表的应用。

数组

数组是元素的顺序集合，通常这些元素具有相同的数据类型。我们可以使用循环来读写数组中的元素。

当需要进行的插入和删除操作比较少，而需要大量的查找和检索操作时，数组是合适的结构。

数组名与元素名

数组的名字是整个结构的名字，而元素的名字允许我们查阅这个元素。

多维数组

到目前为止，我们所讨论的都是一维数组，因为数据仅是在一个方向上线性组成。许多的应用要求数据存储在多维中。常见的例子如表格，就是包括行和列的数组，这是一个二维数组。

存储配置

一维数组的索引直接定义了元素在实际存储上的相对位置。但是二维数组表示行和列。在内存中如何存储每个元素取决于计算机，大多数计算机使用行主序存储，其中数组的一个整行在内存上存储在下一个行之前。但是计算机也可以使用列主序存储，其中一个整列在内存上存储在下一个列之前。

数组操作

数组作为结构的常用操作有：

• 查找元素
• 插入元素
  • 尾部插入
  • 开始或中间插入
• 删除元素
• 检索元素
• 数组的遍历

字符串

字符串是字符的集合，不同的语言对于字符串的处理并不相同。字符串也可以理解为是字符构成的数组。

记录

记录是一组相关元素的集合，它们可能是不同的类型，但整个记录有一个名称。记录中的每个元素称为域。域是具有含义的最小命名数据。它有类型且存在于内存中，它能被赋值，也能够被选择和操纵。域不同于变量主要在于它是记录的一部分。

记录中的元素可以是相同类型或不同类型，但记录中的所有元素必须是关联的。

记录名与域名

记录的名字是整个结构的名字，而每个域的名字允许我们存取这些域。

1
2
3
4
5

# 记录
student

# 域
student.id, student.name

链表

链表是一个数据的集合，其中每个元素包含下一个元素的地址。即每个元素都包含两部分：数据和链。

数据部分包含可用的信息，并被处理。链则将数据连在一起，它包含一个指明列表中下一个元素的指针（地址）。另外，一个指针变量标识该列表中的第一个元素。列表的名字就是该指针变量的名字。

链表中的元素习惯上称为节点 ，链表中的节点是至少包括两个域的记录：数据和下一个节点地址。

链表名与节点名

链表名是头指针的名字，该头指针指向表中的第一个节点。另一方面，节点在链表中没有明显的名字，有的只是隐含的名字。

例如，如果指向节点的指针称为 p，我们称节点为 *p，节点的数据部分为 (*p).data，节点的链部分为 (*p).link。

链表操作

为数组定义的操作同样可以应用于链表。

• 查找链表：链表的查找算法只能是顺序的。链表中的节点没有特定的名字，那我们使用两个指针：pre（先前的） 和 cur（当前的）。
• 插入节点：在链表中插入节点之前，要先使用查找算法，不允许重复值的数据。
  • 插入空表
  • 开始处插入
  • 末尾处插入
  • 中间插入
• 删除节点：在链表中删除节点前，要先使用查找算法。
  • 删除首节点
  • 删除中间或末尾节点
• 检索节点：检索就是为了检查或复制节点中所含数据的目的而随机访问节点。
• 遍历链表

链表的应用

当需要对存储数据进行许多插入和删除时，链表是一种非常高效的数据结构。链表是一种动态的数据结构，其中表从没有节点开始，然后当需要新节点时，它就逐渐增长。与数组的情况相比，节点很容易被删除，不需要移动其它节点。

链表可以无限增长，也可以缩短为空表。额外的开销是为这个节点含有一个额外的域。但对于经常需要查找的数据来说，链表不是一个好的候选者。

如果需要大量的插入和删除，那么链表是合适的结构，但查找一个链表会比查找一个数组要慢。

抽象数据结构

抽象数据类型使用数据结构来实现，一些抽象数据类型：栈、队列、广义线性表、树、二叉树、二叉搜索树和图。

本章的学习目标：

• 说明抽象数据类型的概念
• 说明栈、栈上的基本操作、它们的应用以及它们是如何实现的；
• 说明队列、队列上的基本操作、它们的应用以及它们是如何实现的；
• 说明广义线性表、广义线性表的基本操作、它们的应用以及他们是如何实现的；
• 说明一般的树及其应用；
• 说明二叉树及其应用；
• 说明二叉搜索树及其应用；
• 说明图及其应用。

背景

使用计算机进行问题求解意味着处理数据。为了处理数据，我们需要定义数据类型和在数据上进行的操作。数据类型的定义和应用于数据的操作的定义是抽象数据类型背后的一部分概念，以隐藏数据上的操作是如何进行的。

简单抽象数据类型

许多编程语言已经定义了一些简单的抽象数据类型作为语言的组成部分。例如，C 语言定义了称为整数的简单抽象数据类型。C 还定义了可以在这种数据类型上应用的集中操作（加减乘除等）。

复杂抽象数据类型

几种简单的抽象数据类型（如整数、实数、字符、指针等）已经被实现，在大多数语言中它们对用户是可用的。但是许多有用的复杂抽象数据类型（如栈、表、队列等）却没有实现。

抽象概念意味着：

• 知道一个数据类型能做什么；
• 如何去做是隐藏的。

定义抽象数据类型

抽象数据类型：

• 数据的定义；
• 操作的定义；
• 封装数据和操作。

抽象数据类型的模型

下图的抽象模型有两个部分：数据和操作（共有的和私有的）。应用程序只能通过结构访问公有操作。私有操作是抽象数据类型内部用户使用的。

抽象数据类型的实现

计算机语言不提供抽象数据类型包。要使用抽象数据类型，首先要实现它们，把它们存储在库中。

栈

栈是一种限制线性表，该类列表的添加和删除只能在一端实现，称为栈顶。栈是一种后进先出（LIFO）的数据结构。

栈的操纵

栈有四种基本操作：建栈、入栈、出栈和空。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# 建栈创建一个空栈
stack(stackName)

# 入栈操作在栈顶部添加新的元素
push(stackName, dataItem)

# 出栈操作将栈顶部元素移走
pop(stackName, dataItem)

# 空操作检查栈的状态
empty(stackName)

栈的抽象数据类型

栈的抽象数据类型：

• 定义：一种只能在一段存取的数据项表，该端称为栈顶。
• 操作: stack, push, pop, empty

栈的应用

栈的应用可以分为四类：

• 倒装数据
• 配对数据
• 数据延迟
• 回溯步骤

栈的实现

栈抽象数据类型可以使用数组也可以使用链表来实现。

在数组中实现，我们有带有两个域的记录。第一个域用来存储关于数组的信息：把它当做计数域，在任何时刻其中显示的是栈中数据项的数目。第二个域是一个含有栈顶元素索引的整数。

链表的实现是相似的，有一个具有栈名字的额外节点。这个节点也有两个域：一个计数器和一个指向栈顶元素的指针。

队列

队列是一种线性表，该表中的数据只能在称为尾部的一端插入，并且只能在称为头部的一端删除。换言之，队列是先进先出结构。

队列在日常生活中是常见的。如排队等待的人群队列。

队列上的基本操作

队列的四个基本操作：建队列、入队、出队和空。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# 建队列建立一个空队列
queue(queueNamel 

# 入队操作在队列的末尾插入一个数据项
enqueue (queueName , dataltem )

# 出队操作删除队列头部的数据项
dequeue(queueName, dataItem)

# 空操作检查队列的状态
empty(queueName) 

队列的抽象数据类型

• 定义：队列是一种线性表，该表中的数据只能在称为头部的一段删除，并且之恩那个在称为尾部的一端插入。
• 操作：queue, enqueue, dequeue, empty

队列的使用

队列是最常用的数据处理结构之一。事实上，在所有的操作系统和网络中都有队列的身影，在其他技术领域更是数不胜数。

队列的实现

队列的抽象数据类型可以使用数组或链表来实现。

在数组实现中，我们有带有三个域的记录。第一个域用来存储关于队列的信息：把它当作计数域，在任何时刻其中显示的是队列中数据项的数目。第二个域是一个含有队首元素索引的整数。第三个域也是一个整数，它含有队尾元素的索引。

链表的实现是相似：我们有一个有队列名字的额外节点。这个节点也有三个域：一个计数器、一个指向队首元素的指针和一个指向队尾元素的指针。

广义线性表

栈和队列都是限制线性表。广义线性表是像插入和删除操作可以在其中任何地方进行的表。

我们把广义线性表定义成具有如下特性的元素集合：

• 元素具有相同的类型。
• 元素顺序排列，这意味着有第一个元素和最后一个元素。
• 除第一个元素外每个元素都有唯一的前驱，除最后一个元素外每个元素都有唯一的后继。
• 每个元素是一个带有关键字域的记录。
• 元素按关键字值排序。

广义线性表的操作

广义线性表的六种常用的操作：建表、插入、删除、检索、遍历和空。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

# 建表操作建立一个空表
list(listName)

# 广义线性表中的数据是已排序的，那么插入就必须在保持元素顺序的方式下进行。
insert(listName, element)

# 从广义表中删除数据也需要查找表，以找到删除数据在表中的位置。当数据的位置被找到后，删除操作就能进行了。
delete(listName, target, element)

# 检索的意思是单个元素的存取。像插入和删除操作一样，广义表首先被查找，数据被发现，才能被检索。
retrieve(listName, target, element)

# 遍历涉及表的顺序存取
traverse(listName, action)

# 空操作检查表的状态
empty(listName)

广义线性表的抽象数据类型

• 定义：一个有序的数据项表，所有的项具有相同类型。
• 操作：list, insert, delete, retrieve, traverse, empty

广义线性表的应用

广义线性表可用于元素被随机存取或顺序存取的情况。例如，用线性表来存储每个学期入学的学生信息。

广义线性表的实现

广义线性表抽象数据类型可以使用数组或链表来实现。

在数组实现中，我们有带有两个域的记录。第一个域用来存储关于数组的信息的信息：把它当作计数域，其中显示的是表中当前数据项的数目。第二个域是一个含有表中首元素索引的整数。

链表的实现是相似的：我们有一个具有表名字的额外节点。这个节点也有两个域：一个计数器和一个指向首元素的指针。

树

树包括一组有限的元素，称为节点（顶点），同时包括一组有限的有向线段，用来连接节点，称为弧。

如果树是非空的，其中有一个节点没有进入的弧，该节点称为根。树中的其他节点都可以沿着从根开始的唯一路径到达，该路径是指一系列相邻连接的节点序列。树的结构通常被画成上下颠倒，根在顶部。

我们可以把树中的顶点分成三类：根、内部顶点和叶子。

从一给定节点可以直接达到的节点称为子节点，从其触发子节点可以直接达到的节点称为双亲。具有相同双亲的节点称为兄弟节点。节点的子孙是指从该节点触发可以到达的所有节点，而从其出发所有的子孙都可以到达的节点称为祖先。树中的每个节点都可能有子树。

二叉树

二叉树是一棵树，且其中没有一个节点所含有的子树的个数超过两个。换句话说，任一节点只能有0、1或2棵子树。这些子树被描述为左子树和右子树。

二叉树是一棵空树或有一个根节点和两颗子树构成，而每棵子树也是二叉树。

二叉树的操作

二叉树中六种最常用的操作：建树、插入、删除、检索、遍历和空。

下面讨论二叉树的遍历，二叉树的遍历要求按照预定的顺序处理每一个节点且仅处理一次。两种常用的遍历次序是深度优先和广度优先。

深度优先遍历：

• 前序遍历：根首先被访问，接着是左子树，最后是右子树。
• 中序遍历：先处理左子树，然后是根，最后是右子树。
• 后序遍历：根在左/右子树都处理完后才处理。

广度优先遍历，先处理节点的子节点，然后进行下一层。

二叉树的应用

二叉树在计算机科学中有许多应用。这里介绍两种：赫夫曼编码和表达式树。

赫夫曼编码是一种压缩技术，它使用二叉树来生成一个符号串的可变长度的二进制编码。

一个算术表达式可以用三种格式来表示：

• 中缀：操作符处于两个操作数中间（如 A+B）
• 后缀：操作符处于两个操作数之后（如 AB+）
• 前缀：操作符处于两个操作数之前（如 +AB）

虽然我们在编程语言中常使用中缀表示，但编译程序经常在计算表达式之前需要把它们转变为后缀表示。进行转换的一种方法就是建立表达式树。

在表达式树中，根和内部节点是操作符，而叶子是操作数。三种标准的遍历表示了三种不同的表达式格式。中序遍历产生了中缀表达式；后序遍历产生了后缀表达式；前序遍历产生了前缀表达式。

二叉树的实现

二叉树可以使用数组或链表来实现。对于删除和插入操作，链表实现的效率要高，所以更为流行。

二叉搜索树

二叉搜索树（BST）是一种具有额外特性的二叉树：每个节点的关键字值大于左子树中所有节点的关键字值，而小于右子树中所有节点的关键字值。

注意，如果所有子树是二叉搜索树，并且整棵树也是二叉搜索树，那这棵树才是二叉搜索树。

二叉搜索树的两个特性：

• 对二叉搜索树应用中序遍历会得到一个升序列表。
• 能对二叉搜索树使用折半查找。

图

图是由一组节点（称为顶点）和一组顶点间的连线（陈伟边或弧）构成的抽象数据类型。树是定义成层次结构的，节点只能有一个双亲。而图中的节点可以有一个或多个双亲。图可能是有向或无向的。

图中的顶点可以代表对象或概念，边可以代表这些对象或概念间的关系。如果图是有向的，那么关系就是单向的；如果图是无向的，那么关系就是双向的。

城市的地图和连接城市的道路可以表示称计算机中的一个无向图。城市是顶点，无向边是连接它们的道路。如果我们要显示城市间的距离，可以使用加权图，其中的每条边都有一个权重，该犬种表示由这条边连接的两个城市间的距离。

图的另一个应用是在计算机网络中。顶点可以代表节点或集线器，边可以代表路由。每条边都有一个权重，表示从一个集线器到相邻集线器的代价。路由器能使用图算法找到它与包的最终目的地间的最短路径。

文件结构

本章的学习目标：

• 定义两类存取方法：顺序存取和随机存取；
• 理解顺序文件的结构和它们是如何更新的；
• 理解索引文件的结构和索引文件与数据文件间的关系；
• 理解散列文件背后的概念，说出一些散列方法；
• 描述地址冲突和它们是如何解决的；
• 定义目录和它们是如何用来组织文件的；
• 区分文本文件和二进制文件。

文件结构引言

文件存储在辅助存储设备或二级存储设备中。两种最常见的二级存储设备是磁盘和磁带。文件在二级存储设备中是可读写的。广义上，键盘也是文件。

文件是数据记录的集合，每一个记录都由一个或多个域组成。

在设计文件时，关键问题是如何从文件中检索信息。有时需要一个接一个地处理记录，有时又需要快速存取一个特定的记录而不用检索前面的记录。存取方法决定了怎样检索记录：顺序的或随机的。

顺序存取

如果需要顺序地存取记录，则使用顺序文件结构。

随机存取

如果想存取某一特定记录而不用检索其之前的所有记录，则使用允许随机存取的文件架构。

有两种结构都允许随机存取：索引文件和散列文件。

顺序文件

顺序文件是指记录只能按照从头到尾一个接一个地进行存取。

顺序文件用于需要从头到尾存取记录的应用。例如公司职员信息存储于一个文件中。

然而，顺序文件对随机存取来说效率并不高。

顺序文件必须定期更新，以反映信息的变化。更新过程将非常棘手，因为所有记录都要被顺序地检查和更新。

文件更新过程：要使文件更新过程有效率，所有文件都必须按同一个键排序。

索引文件

在文件中随机存取记录，需要知道记录的地址。

索引文件由数据文件组成，它是带索引的顺序文件。

索引文件的好处之一就是可以有多个索引，每个索引有不同的键。

散列文件

散列文件用一个数学函数来完成映射。用户给出键，函数将键映射成地址，再传送给操作系统，这样就可检索记录了。

散列文件无需额外的索引。在索引文件中，必须将文件的索引保存在磁盘上。当需要处理文件时，需要把索引导入内存中，搜索索引找到数据记录的地址，再访问数据文件存取记录。在散列文件中，用函数来寻找地址。这里不需要索引和随之而来的所有开销。然而，散列文件自身也存在问题。

散列方法

有多种散列方法：

• 直接散列方法：键是未经算法处理的数据文件地址。
• 求模法（除余散列法）：用文件大小去除键后，将余数加 1 作为地址。
• 数字分析散列法：选择从键中析取的数字作为地址。
• 其它方法：平方中值法、折叠法、旋转法和伪随机法。

散列冲突

通常散列列表中键的数量比在数据文件中的记录数量要多。因为在文件中有很多键对应于一个地址。有可能多于一个的键就被散列为文件中的同一个地址。我们把列表中一些映射为同一地址的键称为同义词。

如何插入列表的实际数据中有两个或多个同义词，将产生冲突。冲突的产生是在散列算法为插入键产生地址时，发现该地址已被占用。由散列算法产生的地址称为内部地址。包含所有内部地址的区域称为主区。当两个键在内部地址上冲突时，必须将其中一个键和数据存放到主区外的另一个地址单元中来解决冲突。

冲突解决法：

• 开放寻址解决法：解决了在主区的冲突。当一个冲突发生时，主区地址将查找开放的或空闲的记录来用于存放新数据。对于不能再内部地址中存放的数据，一种简单的策略就是把该数据存储在内部地址的下一个地址中（内部地址 +1）。
• 链表解决法：开放寻址的一个主要缺点时每个冲突的解决增加了将来冲突的可能性。在链表解决法中，第一条记录存储在内部地址，但它包含了一个指向下一条记录的指针。
• 桶散列法：桶是一个能接纳多个记录的节点。此方法的缺点是可能有很多浪费（未占用的）存储单元。
• 组合方法：复杂的实现方法通常是组合使用多种方法。

目录

目录是大多数操作系统提供的，用来组织文件。在大多数操作系统中，目录被表示为含有其他文件信息的一种特殊文件类型。目录的作用不仅仅像一种索引文件，还包括了关于它所包含的文件的其他信息（如权限、日期这些）。

在大多数操作系统中，目录被组织成像树的抽象数据类型，其中除根目录外每个目录都有双亲。包含在另一个目录中的目录称为子目录。

UNIX操作系统中的目录

在 UNIX 中有 4 中特殊目录类型：

• 根目录
• 主目录
• 工作目录
• 父目录

路径和路径名：文件系统的每个目录和文件都必须有一个名字。因此，使用了路径这个唯一标识。

• 绝对路径
• 相对路径

文本文件与二进制文件

存储在存储设备上的文件是一个位（bit）的序列，可被应用程序翻译成一个文本文件或是二进制文件。

文本文件

文本文件是一个字符文件。在它们的内存储器格式中不能包含整数、浮点或其他数据结构。要存储这些类型的数据，必须把它们转换成对应的字符格式。

二进制文件

二进制文件是计算机的内部格式存储的数据集合，在这种定义中，数据可以是整型（包括其他表示成无符号整数的数据类型，如图像、音频或视频）、浮点型或其他数据结构。

不像文本文件，二进制文件中的数据只有当被程序正确地解释时才有意义。

数据库

本章讨论数据库和数据库管理系统。

本章的学习目标：

• 定义数据库和数据库管理系统
• 描述基于 ANSI/SPARC 定义的数据库管理系统的体系结构
• 定义三种传统的数据库模型：层次、网络和关系
• 描述关系模型和关系
• 理解关系模型和关系的操作，这些操作在 SQL 中有相应的命令
• 描述数据库设计的步骤
• 说明 ERM 和 E-R 图，解释这种模型中的实体和关系。
• 列出除关系模型外其他的数据库类型

数据库引言

数据的存储传统上是使用单独没有关联的文件，有时称为平面文件。在过去，组织中的每个应用程序都是用自己的文件。但现在，所有这些平面文件都被组合成一个实体——一个数据库。

数据库的定义

数据库是一个组织内被应用程序使用的逻辑相一致的相关数据的集合。

数据库的优点

优点：

• 冗余较少
• 避免不一致性
• 效率
• 数据完整性
• 机密性

数据库管理系统

数据库管理系统是定义、创建和维护数据库的一种工具。DBMS 也允许用户来控制数据库中数据的存取。它由 5 部分组成：

• 硬件
• 软件
• 数据
• 用户
  • 最终用户
  • 应用程序
• 规程

数据库体系结构

美国国家标准协会为数据库管理系统建立了三层体系结构：

• 内层：决定了数据在存储设备中的实际位置。它处理低层次的数据存取方法和如何在存储设备间传输字节。内层直接与硬件交互。
• 概念层：定义数据的逻辑视图。在该层中定义了数据模式。它使得用户不必与内存打交道。
• 外层：直接与用户交互。它将来自概念层的数据转化为用户所熟悉的格式和视图。

数据库模型

数据库模型定义了数据的逻辑设计，它也描述了数据的不同部分之间的联系。在数据库的发展中，曾使用过三种数据库模型：层次模型、网状模型和关系模型。

层次模型

层次模型中，数据被组织成一个倒置的树。每一个实体可以有不同的子节点，但只能有一个父节点。层次的最顶端有一个实体，称为根。层次模型已过时。

网状模型

网状模型中，实体通过图来组织，图中的部分实体可通过多条路径来访问。网站模型已过时。

关系模型

关系模型中，数据组织称为关系的二维表，表或关系相互关联。

如今，关系模型是数据库设计中最常用的模型。

关系数据库模型

在关系数据库管理系统（RDBMS）中，数据是通过关系的集合来表示的。

关系

从表面上看，关系就是二维表。在关系数据库管理系统中，数据的外部视图就是关系或表的集合，但这并不代表数据以表的形式存储。数据的物理存储与数据的逻辑组织的方式毫无关系。

关系有以下特征：

• 名称：每种关系都具有唯一的名称。
• 属性：关系中的每一列称为属性。
• 元组：关系中的行叫元组。关系中元组的个数叫关系的基数。当增加或减少元组时，关系的基数就会改变。这就实现了动态数据库。

关系的操作

在关系数据库中，我们可以定义一些操作来通过已知的关系创建新的关系。本节定义了 9 种操作。我们并不抽象地讨论这些操作，而是把它们描述成在数据库查询语言 SQL（结构化查询语言）中的定义。

结构化查询语言是美国国标协会和国际标准化组织用于关系数据库的标准化语言。这是一种描述性的语言，意味着使用者不需要一步步地编写详细的程序而只需声明它。

SQL 语句允许我们组合祖居，从数据库中抽取出更复杂的信息。

• 插入：一元操作。
• 删除：一元操作。
• 更新：一元操作。
• 选择：一元操作，应用于一个关系并产生另外一个新关系。
• 投影：一元操作，应用于一个关系并产生另外一个新关系。
• 连接：二元操作，基于公有的属性把两个关系组合起来。
• 并：二元操作，将两个关系合并成一个新的关系。两者必须有相同的属性。
• 交：二元操作，对两个关系进行操作，创建一个新关系。两者必须具有相同的属性。
• 差：二元操作，应用于具有相同属性的两个关系。

数据库设计

数据库的设计是一个冗长且只能通过一步步过程来完成的任务。第一步通常设计于数据库潜在用户的交谈。第二部是建立一个实体关系模型（ERM），此模型定义了其中一些信息需要维护的实体，这些实体的属性和实体间的关系。

实体关系模型

使用实体关系（E-R）图来表示那些其信息需要保存的实体和实体间的关系。

• 矩形表示实体集。
• 椭圆形表示属性。
• 菱形表示关系集。
• 线连接属性和实体集，实体集和关系集。

E-R 图完成后，关系数据库中的关系就能建立了。

规范化过程

规范化是一个处理过程，通过此过程给定的一组关系转化成一组具有更坚固结构的新关系。规范化允许数据库中表示的任何关系，要允许像 SQL 这样的语言去使用由原子操作组成的恢复操作，要移除插入、删除和更新操作中的不规则，要减少当新的数据类型被加入时对数据库重建的需要。

规范化过程定义了一组层次范式（NF）。多种范式已经被提出，包括 1NF, 2NF, 3NF, BCNF, 4NF, PJNF 和 5NF等。有一点需要知道，这些范式形成了一个层次结构。换言之，如果一个数据库中的关系是 3NF，那它首先应该是 2NF。

第一范式（1NF）。

当我们把实体或关系转换成表格的关系时，可能有些关系的行或列的交集有多个值。一个教授可以教授多门课程，而一个学生也可以修多门课程。这两个关系可以通过重复有问题的行来进行规范化。

一个不是第一范式的关系可能会遇到许多问题。在数据库中，我们总是删除一整条记录，而不是一条记录的一部分。

第二范式（2NF）。

在每个关系中，我们需要有一个关键字（称为主键），所有其他的属性都依赖于它。如果每一个非关键字属性都依赖于整个复合关键字（两个或以上关键字的组合），那么这个关系就是第二范式。

如果有些属性只依赖于复合关键字的一部分，那这个关系就不是第二范式的。

其他范式使用属性间更复杂的依赖关系。这部分知识请查看专门介绍数据库的书籍。

其他数据库模型

关系型数据库并不是当今唯一通用的数据库模型。另外两种通用模型时：分布式数据库和面向对象数据库。

分布式数据库

分布式数据库模型实际上并不是一种新的模型，它是基于关系模型的。只不过，数据库中的数据存储在一些通过因特网通信的计算机上。每台计算机都拥有部分或全部数据库。

• 不完全的分布式数据库：数据是本地化的。本地使用的数据存储在相应的站点上。
• 复制式分布式数据库：每个站点都有一个完全的副本。

面向对象数据库

面向对象数据库在试图保留关系模型优点的同时，允许应用存取结构化数据。在面上对象数据库中，定义了对象和它们的关系。另外，每一个对象可以具有属性并以域的形式表达。

数据压缩

人们希望在更短的时间内下载更多的数据，人们希望能在更小的空间存储更多的数据。

压缩数据通过消除数据中内在的冗余来减少发送或存储的数据量。当我们产生数据的同时，冗余也就产生了。通过数据压缩，提高了数据传输和存储的效率，同时保护了数据的完整性。

本章的学习目标：

• 区分无损压缩和有损压缩；
• 描述游程长度编码和它是如何实现压缩的；
• 描述赫夫曼编码和它是如何实现压缩的；
• 描述 Lempel Ziv 编码以及字典在编码和译码中的作用；
• 描述压缩静止图像的 JEPG 标准背后的主要思想；
• 描述压缩视频的 MPEG 标准背后的主要思想以及它与 JPEG 的关系；
• 描述压缩音频的 MP3 标准背后的主要思想。

数据压缩引言

数据压缩意味着发送或存储更少的位数。压缩方法一般分为两类：

• 无损压缩
  • 游程长度编码
  • 赫夫曼编码
  • LZ 编码
• 有损压缩
  • JPEG
  • MPEG
  • MP3

无损压缩方法

在无损数据压缩中，数据的完整性是收到保护的。原始数据与压缩和解压后的数据完全一样。压缩和解压缩算法是完全互反的两个过程，没有数据丢失。

游程长度编码

游程长度编码的思想是将数据中连续重复出现的符号用一个字符和这个字符重复的次数来代替。例如，AAAAAAAA 用 A08 来代替。

赫夫曼编码

在赫夫曼编码中，对于出现更为频繁的字符分配较短的编码，而对于出现较少的字符分配较长的编码。

在给每个字符分配位模式前，首先根据每个字符的使用频率给他们分配相应的权值。然后根据权值构造一棵树。构造树的过程遵循以下三个基本步骤：

• 将全部字符排成一排。每个字符现在都是树的最底层节点。
• 找出权值最小的两个节点并由他们合成第三个节点，产生一个简单的二层树。
• 重复上述步骤，知道各个层的所有节点结合成一棵树。

Lemple Ziv 编码

Lempel Ziv(LZ) 编码是称为基于字典的编码的那一类算法的一个例子，用其发明者的名字命名的。在通信会话的时候它将产生一个字符串字典（一个表）。如果接收和发送双方都有这样的字典，那么字符串可以由字典中的索引代替，以减少通信的数据传输量。

有损压缩方法

信息的丢失在文本和程序中都是不可接受的。但在图片、音频和视频中是可以接受的。对于这些情况，可以使用有损数据压缩。这使得在传输图像和视频数据时只需要花费更少的时间和空间以及更廉价的代价。

图像压缩: JPEG

在 JPEG 中，一幅图像被划分成许多的像素块。JPEG 的整体思想是将图像变换成一个数的线性（矢量）集合来揭示冗余。这些冗余可以通过使用前面学过的无损压缩的方法来除去。

视频压缩: MPEG

运动图像专家组（MPEG）方法用于压缩视频。帧是像素在空间上的组合，视频是一幅接一幅的帧的时间组合。压缩视频，就是对每帧空间上的压缩和对一系列帧时间上的压缩。

空间压缩：每一帧的空间压缩使用 JPEG（或它的改进版）。

时间压缩：在时间压缩中，多余的帧将被丢弃。

音频压缩

音频压缩可用来处理语音和音乐。有两类技术用来进行音频压缩：

• 预测编码：样本间的差别被编码，而不是对所有的样本进行编码。此压缩方法通常用在语音上。已有的标准：GSM、G.729 和 G.723.3。
• 感知编码：用来创建 CD 质量音频最常用的压缩技术。

感知编码是基于心理声学的，心理声学是一门研究人类是如何感知声音的科学。想法是基于我们听觉系统的瑕疵，有些声音能够掩盖其他声音。掩盖可以发生在频率上和时间上。在频率掩盖中，一个频率范围的高的声音可以部分或完全掩盖另一个频率范围的低的声音（例如，在高音重金属演出中听不见同伴说的话）。在时间掩盖中，即使在高音停止后，它也可以在短时间内降低我们听觉灵敏度。

MP3 使用这两种现象来压缩音频信号。该技术分析音谱并把音谱分成几个组。0 位被赋给了那些频率范围被完全掩盖的，小数值得位被赋给了那些频率范围部分被掩盖的。大数值得位被赋给了那些不被掩盖得。

安全

本章得学习内容：

• 定义安全目标：机密性、完整性、可用性；
• 区分对称加密和非对称加密，以及它们可以达到得机密性程度；
• 描述安全的其他领域：消息完整性、消息验证、数字签名、实体验证和密钥管理；
• 理解防火墙在防止有害消息达到一个系统中的作用。

安全引言

信息是一种有价值的资产，需要保护，免受攻击。为了安全，信息需要避开未授权的使用（机密性），保护信息不受到未授权的篡改（完整性），并且对于得到授权的实体来说是需要时可用的（可用性）。

信息不仅应该在存储时保密，在传输时也应该保持机密性。

安全目标

三个安全目标：

• 机密性
• 完整性
• 可用性

安全攻击

安全攻击的分类：

• 威胁机密性的攻击
  • 嗅探
  • 流量分析
• 威胁完整性的攻击
  • 篡改
  • 假冒
  • 重放
  • 抵赖
• 威胁可用性的攻击
  • 拒绝服务（DoS）

服务和技术

现今流行的两种安全技术：

• 密码术：通过加密把消息中的内容隐藏起来。有加密和解密。
• 隐写术：通过在消息上覆盖其他内容而隐藏消息。

机密性

机密性可以通过密码达到。密码术可分为两大类：对称密钥和非对称密钥。

对称密钥密码术

对称密钥密码术使用了同一个密钥进行加密和解密，这个密钥可用来进行双向通信，这就是为什么它被称为对称。

对称加密又分为两类：

• 传统对称加密：面向字符的密码。
  • 替换密码：用一个符号替换另一个符号。
  • 单字母密码：明文中相同的字符在密文中用相同的字符替换，与该字符在明文中的位置无关。
  • 多字母密码
  • 移位密码：改变符号的位置。
• 流密码和分组密码
  • 流密码：加密和解密都是一次只对一个符号进行。
  • 分组密码：一组大小为 m（m大于1）的明文符号被加密在一起，创造一组同样大小的密文。
  • 组合
• 现代对称加密：面向位的密码。
  • 现代分组密码：对大小为 n 位（常用 64、128、256 和 512 位）的明文分组进行加密或密文解密。
  • 现代流密码：加密和解密都是每次对 r 位进行。流密码比分组密码更快，硬件实现也更简单。

非对称密钥密码术

在非对称密钥密码术中，秘密是个人独享的，每个人创造并保守个人的秘密。如身份认证和数字签名等。

与对称密钥基于符号（字符或位）的替换和排列不同，非对称密钥基于数学函数在数字上的应用。在对称密钥中，明文和密文被看作符号的组合，加密和解密是对这些符号的排列或相互替换。在非对称密钥中，明文和密文都是数字，加密和解密的过程是对数字应用数学函数并创造其他数字的过程。

非对称密钥通常用来加密或解密小段信息。

在非对称密钥中使用两个公开的密钥：

• 公钥：加密。最常用的公钥算法是 RSA 密码系统。
• 私钥：解密

其他安全服务

消息完整性

有些场合需要保证完整性，如遗嘱。

保证文档完整性的一种方法是通过指纹。为了保证消息的完整性，消息要通过一个称为密码散列函数的算法。

散列函数将任意长度的消息加密成固定长度的消息摘要。

罗恩-李维斯设计的几个散列算法被称为 MD2、MD4 和 MD5。这里的 MD 代表消息摘要。MD5 是 MD4 的加强版，它可以将消息分成长度为 512 位的分组并创造大小为 128 位的摘要。然而，事实证明大小为 128 位的消息摘要太小了以至于不能阻挡攻击。

为了回应 MD 散列算法的不安全性，安全散列算法（SHA）诞生了。

消息验证

消息摘要可以验证消息的完整性，保证消息没被篡改。

消息验证码（MAC, Message Authentication Code）通过散列函数和密钥的组合来保证消息的完整性和消息验证。

新一代的 MAC 标准称为 HMAC（散列消息验证码）。

数字签名

保证消息完整性和消息验证的另一种方法是数字签名。数字签名使用一组公私钥。

• 对比
  • 包含
  • 验证手段
  • 关系
  • 复制性
• 过程
• 签署摘要
• 服务
  • 消息验证
  • 消息完整性
  • 不可抵赖性
  • 机密性

实体验证

实体验证用来使得以放证明另一方标识的一种技术。

• 实体验证与消息验证
• 验证分类
  • 所知道的
  • 所拥有的
  • 所固有的
• 密码
• 质询-响应
  • 使用对称密钥
  • 使用非对称密码
  • 使用数字签名

密钥管理

• 对称密钥分发
  • 密钥分发中心（KDC）
  • 多个密钥分发中心
  • 会话密钥：一个双方间的会话对称密钥只被使用一次。
• 公钥分发：公钥对公众可用
  • 公开声明
  • 认证机构（CA）
  • X.509：是一个结构化描述证书的方式，证书格式的通用性。

防火墙

我们需要防火墙控制对系统的访问。防火墙是一个在内部网络和因特网其他部分之间的一个设备。防火墙是为了推进一些数据包而过滤其他数据包所设计的。

包过滤防火墙

防火墙可以用作数据包过滤器。它是基于网络层的信息和传输层的头部：源和目的 IP 地址、源和目的端口以及协议类型来放行或阻拦数据包。

代理防火墙

有时我们也需要基于消息自身携带的信息（应用层）进行过滤。

一个解决措施是安装代理计算机（应用网关）。当客户发送消息时，应用网关检查数据包并判断这个请求是否合法。

计算理论

哪些问题可以通过计算机解决？语言之间是否存在优劣？运行一个程序前，是否可以确定该程序将要停止还是一直运行？用一种特定的语言解决一个问题需要多长时间？为了回答这些问题，我们求助于一门学科：计算理论。

本章的学习目标：

• 描述称为简单语言的编程语言，并定义它的基本语句；
• 在简单语言中，使用简单语言的复合写出宏；
• 描述作为计算机模型的图灵机的构成；
• 使用图灵机，显示简单语言中的简单语句是如何被模拟的；
• 理解邱奇-图灵理论和它的含义；
• 定义哥德尔数和它的应用；
• 理解停机问题的概念和问题不可解是如何被证明的；
• 区分可解和不可解问题；
• 区分多项式和非多项式可解问题。

简单语言

我们可以仅用三条语句来定义一种语言：递增语句、递减语句和循环语句。

归纳来说，可以证明只使用这三种语句的简单程序设计语言和我们现在使用的任何一种复杂语言（如 C）一样强大。

图灵机

图灵机是用来解决可计算问题的，它是现代计算机的基础。

图灵机能模拟简单语言中的三个基本语言。这就意味着图灵机能模拟我们为简单语言定义的所有的宏。那么图灵机是否能解决一台计算机能解决的任何问题？答案可在邱奇-图灵论题中找到。

邱奇-图灵论题：如果存在一个能完成一个符号操纵任务的算法，那么也存在一台完成这个任务的图灵机。

注意，这只是论题，不是定理。定理可以在数学上得到证明，但论题却不饿能。虽然这个论题可能永远得不到证明，但有些强有力的论断在支持它。首先，尚未发现有图灵机不能模拟的算法；其次所有在数学上已经证明的。

哥德尔数

在计算机理论中，一个无符号数能被分配给任何用特定语言编写的程序，通常称为哥德尔数。

停机问题

几乎所有的简单语言编写的程序都包含某种形式的重复（循环或递归）。一个重复结构可能永远都不会结束（停机）。这就是说，一个含有无限循环的程序可以永久运行。

能否编写一个程序来测试可以用哥德尔数标识的程序是否会终止吗？不幸的是，现在已经证明这样的程序不可能存在。

停机问题是不可解的。

问题的复杂度

在计算机科学领域，我们可以这么说，一般来说问题可以分为两类：

• 可解问题
  • 多项式问题
  • 非多项式问题
• 不可解问题

不可解问题

无法用计算机解决的问题无穷无尽，停机问题是其中一个。证明一个问题能否解决等同于证明停机问题能否解决。

可解问题

能够被计算机解决的问题也是无穷无尽。我们关心的是：计算机需要花多长时间去解决一个问题。换言之，这个问题有多复杂？

问题的复杂度可以用不同的方法衡量：如运行时间、内存用量等。

可解问题的复杂度。衡量可解问题复杂度的一个方法是找出计算机运行该程序时要执行的运算数量。这样，复杂度问题不是依赖于运行程序的计算机的速度，而是依赖于输入的数目。

大 O 表示法。相对于当今计算机的速度，我们关心的是程序总体的数量级而不是精确的数字。效率的简化以大 O 表示法最为著名。在该表示法中，运算数量表示为输入量的函数，符号 O(n) 表示有 n 个输入，执行 n 次运算。

如果程序的复杂度为 O(log n)、O(n)、O(n^k)，则被称为多项式问题。以当今计算机的处理速度，对于一个有合理输入数量的多项式问题我们都能解决。

如果程序的复杂度远比多项式问题复杂，如 O(10^n) 或 O(n!)。当输入数很小时，这种问题可以解决。如果输入数很大，则需要几个月的时间才能看到非多项式的解决结果。

人工智能

本章的学习目标：

• 定义和叙述人工智能的简史；
• 描述知识在智能体中是如何表示的；
• 说明当人类专家不可用时，专家系统是如何使用的；
• 说明如何用人工智能体来模仿人类完成任务；
• 说明专家系统和平凡系统是如何使用不同的搜索方法解决问题的；
• 说明人类的学习过程是如何被模仿的，在一定程度上，使用神经网络创建的电子版神经元称为感知器。

人工智能引言

当两千多年前希腊哲学家亚里士多德发明了逻辑推理这个概念时，人工智能就开始了，接着莱布尼茨和牛顿完成了逻辑语言的定稿。乔治布尔在十九世纪逐步提出了布尔代数奠定了计算机电子电路的基础。思维计算机的主要思想来自阿兰图灵，他提出了图灵测试。人工智能这个术语是约翰麦卡思在 1956 年首次提出的。

在 1950 年，阿兰图灵提出了图灵测试，这个测试提出了机器具有智能的一个定义。该测试的方法是，简单比较人类的智能行为和计算机的智能行为。一个询问者对计算机和人类都提出一组问题，然后，询问者得到两组答案。如果询问者不能肯定地说出哪一组答案来自认类，哪一组答案来自计算机，那么，计算机就通过了具有智能行为的图灵测试。

智能体是一个能智能地感知环境、从环境中学习并与环境进行交互的系统。智能体可以分为两大类：

• 软件智能体：如搜索引擎
• 硬件智能体：如机器人

虽然有些通用语言能用来编写智能软件，但有两种语言是特别为人工智能设计的：LISP 和 PROLOG。

知识表示

如果打算用人工智能来解决现实世界中的一些问题，那么它必须能表示知识。事实被表示成数据结构后就能被存储在计算机中的程序操纵。4 种常见的知识表示方法：语义网、框架、谓词逻辑和基于规则的系统。

语义网

语义网使用有向图表示知识。语义网用顶点代表概念，用边表示两个概念间的关系。

框架

在框架中，数据结构（记录）用来表示相同的知识。

语义网中的一个节点变成了一组框架的一个对象，所以一个对象可以定义一个类、一个子类或类的一个实例。

语义网中的边被翻译成槽（数据结构中的域）。槽的名字定义了关系的类型和构成关系的槽的值。

谓词逻辑

最通常的知识表示是谓词逻辑。谓词逻辑可用来表示复杂的事实。

命题逻辑是对世界进行逻辑推理的一组句子组成的一种语言。命题逻辑使用 5 种运算符：

• 非
• 或
• 与
• 如果…那么
• 当且仅当

在人工智能中，我们需要从已知的事实中推导出新的事实。在命题逻辑中，这样的过程称为推演。给定两个假定为真的句子，我们能推演出新的为真的句子，前面两个句子称为前提，推演出的句子称为结论，而整个称为论断。

当找不到反例时，论断就是合法的。

谓词逻辑定义了命题各部分间的关系。在谓词逻辑中，句子被分成谓词和参数。

谓词逻辑允许使用量词。在谓词逻辑中两个常用的量词：

• 全称量词：它表明变量所表示的全部对象某些事为真。
• 存在量词：它表明变量所表示的一个或多个对象某些事为真。

由于逻辑推理的需要，逻辑得到了进一步的发展，包括高阶逻辑、默认逻辑、模态逻辑和时态逻辑。

基于规则的系统

社会和道德问题

本章的学习目标：

• 定义和计算机使用相关的三个道德原则；
• 区分物质财产和知识产权，并列举几种知识产权；
• 定义和计算机使用相关的隐私；
• 给出计算机犯罪的定义，并讨论几种攻击以及攻击的动机，以及如何防范攻击；
• 定义黑客以及他们造成的损害。

道德问题

当使用电脑时，评判我们对世界上其他人的责任的一种方式是将决策建立在道德至上。

• 道德规则：我们应该尽量避免去做那些违反普遍道德的行为。
• 使用：如果一个行为能够带来好的结果，那么它是道德的。
• 社会契约：如果一个行为被社会中的大部分人接受，那么它是道德的。

知识产权

现代社会已经确认的几种类型的知识产权：

• 商标
• 商业机密
• 专利
• 版权

隐私

有一些国家已经引进了和用来收集数据的计算机的使用的相关的道德准则：

• 只收集有必要的数据
• 确保收集到的数据的准确性
• 允许个人知道所收集到的数据有哪些
• 在必要情况下，允许个人修改已收集到的数据。
• 确保收集的数据只被用于原来的目的。
• 使用加密技术来达成四小的交流。

计算机犯罪

计算机犯罪是一种非法行为，它又被称为攻击。攻击类型：

• 入侵攻击
  • 病毒
  • 蠕虫
  • 特洛伊木马
• 拒绝服务攻击

攻击保护的策略：

• 使用物理保护：计算机只能被信任的个人使用。
• 使用受保护的软件
• 安装防病毒软件

黑客

现今，黑客指那些未经授权就访问他人计算机获取机密信息的人。