2023-07-01 /2023/07/01/A2CS笔记/ 99+ 7 小时 61.3 k0次访问

A2CS笔记

CS课堂笔记 (A2)

写在前面

学了一段时间的计算机，觉得继续写这些笔记还是蛮有用的，于是乎就打算继续下去。
这次是A2阶段的计算机笔记。
和AS部分一样，写下本文的目的是帮助自己更好地学习CS这门科目，因此，希望路过的大佬轻喷。

本笔记内容基于《Computer Science for Cambridge International AS & A Level》，剑桥大学出版社出版，教材为第二版，A-Level课程编号为9618。

PART THREE: 进阶理论

第十六章：数据的表示

崭新的故事从第十六章继续开始了。

数据类型

早在第13章我们介绍过变量的数据类型的概念。具体是：当一个程序在使用变量之前，必须要显示别该变量的数据类型。

当时介绍了一些最常用的数据类型，但是在本章我们将会接触一些更深入的数据类型。

内置数据类型

内置数据类型 (Built-in data types)，顾名思义，就是已经默认集成在编译器中的数据类型，是被编程语言预先定义的数据类型。一般来说，这些数据类型被认为成执行数据操作最快的类型。

比如说在Python里面，内置数据类型就有这些：str, int, float等。

这些数据类型具体的操作，值分配的操作全部由编程语言定义。

用户定义的数据类型

和内置数据类型相对立的，就是可以由用户定义的数据类型。

一般来说，“用户”通常是使用操作系统提供“用户界面”的人：“用户”是向正在运行的程序提供输入并从其接收输出的人。然而在编写程序时，程序员就成为了编程语言所指的“用户”。名词 用户定义的数据类型(User-defined data types) 中的“用户”就是指程序员们。

这种数据类型是由用户在程序中根据需要所定义的，以便根据幼存储相同或者不同类型的数据类型。

尽管用户定义的数据类型不是内置数据类型，但是只有在编程语言提供对该类型构造的支持情况下，才可以使用某种特定的用户定义数据类型。

User-defined data type: where the programmer includes the definition in the program.

非复合数据类型

非复合数据类型 (Non-composite data types) 是不引用其他数据类型的数据类型。也就是说，这些数据类型的定义没有用到其他的数据类型。

某些用户定义的数据类型也有可能是非符合的数据类型。

Non-composite data type: a data type defined without reference to another data type.

枚举数据类型

枚举数据类型 (Enumerated data type)是用户定义的数据类型，它是根据有序值列表定义的。

同时，它是一种非复合数据类型。

简单举一个例子就很好理解了：这里使用Python来定义一个数据类型Color:


from enum import Enum

class Color(Enum):
    RED = 1
    GREEN = 2
    BLUE = 3

print(Color.RED)

运行了print(Color.RED)之后，会输出1。因为RED定义的值正好为1。

我们通过上面的代码定义了一个名叫Color的枚举数据类型，其中包含三个值：RED,GREEN和BLUE。

需要注意的是，枚举数据类型中定义的值是有序的，这意味着枚举数据类型具有隐含的值顺序。

Enumerated data type: a non-composite user-defined data type for which the definition identifies all possible values.

复合用户定义数据类型

开始变复杂了。

复合用户定义数据类型 (Composite user-defined data types)具有引用至少一种其他类型的定义。

复合用户定义数据类型有两个非常重要的实例：

在第十三章介绍过的记录数据类型 (Record data type)是描述值和变量的数据类型。这是程序员定义的数据类型，允许程序员定义新的记录类型。这允许程序员们使用精确匹配特定程序的数据要求的组件来创建并记录数据类型。Python不支持这样的数据类型。
类 (Class)是面向对象编程中用于对象的数据类型。换句话说，类是创建对象(或者特定数据结构)，提供窗台初始值，以及行为实现的蓝图。

下面的代码就是在Python中的一个类：


class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def say_hello(self):
        print(f"Hello, my name is {self.name} and I am {self.age} years old.")

person = Person("John", 25)
person.say_hello()

在这里我们定义了一个名叫Person的类，其中包含两个子变量：name和age，和一个子函数say_hello()。

指针数据类型

在计算机编程中，指针 (Pointer)是一个存储另一个变量的内存地址的变量。指针数据类型 (Pointer data type)是用于声明指针变量的数据类型。

在AS部分学的链表(Linked list)不是一个指针数据类型。因为链表是一种包含指向其他节点的指针的数据结构。不是指针数据类型的原因是它存储的不是内存地址的变量。

学学伪代码：

当需要使用指针的时候，就可以使用这个符号声明：

1 2	TYPE TIntegerPointer ← ^Integer

定义了TIntegerPointer的数据类型是整形的指针。

我们也可以这么写：

1	DECLARE MyIntegerPointer : TIntegerPointer

这是一个不需要使用插入符 (^) 的方法。

接下来我们来定义一些数据：

DECLARE Number1, Number2 : INTEGER
Number1 ← 100

MyIntegerPointer ← @Number1

最后一行代码向指针变量赋了值。变量MyIntegerPointer现在存储着Number1的地址。

然后我们可以使用下面的这种方法为Number2赋予一个200的值：

1	Number2 ← MyIntegerPointer^ * 2

Pointer variable: one for which the value is the address in memory of a different variable.

集合数据类型

计算机科学中也存在集合的定义：集合是一种抽象数据类型，可以存储某些值，没有任何特定的顺序，并且没有重复的值。

集合数据类型 (Set data type)与大多数其他集合类型不同，通常不是从集合中检索特定元素，而是测试集合中的成员资格值，可以说是将一整个整体来进行处理(?)

Set: a collection of data items that lacks any structure;contains no duplicates and has a number of defined operations that can be performed on it.

常用的操作有这些：

检查集合中是否存在某个值
添加新的数据值
删除现有的数据值
将一个集合添加到另一个集合当中

Python的其中一个亮点就和集合数据类型有关。在Python中，处理集合数据类型十分方便。

下面是在Python中操作集合数据类型的一些实例：


# 创建一个集合
my_set = {1, 2, 3}

# 向集合中添加一个值
my_set.add(4)

# 从集合中剔除一个值
my_set.remove(3)

# 检查值是否在集合内
if 2 in my_set:
    print("2 is in the set")

# ---- 华丽的分割线 ------

# 创建两个集合
set1 = {1, 2, 3}
set2 = {3, 4, 5}

# 两个集合的并集
union_set = set1.union(set2)
print(union_set) # 输出为: {1, 2, 3, 4, 5}

# 两个集合的交集
intersection_set = set1.intersection(set2)
print(intersection_set) # 输出为: {3}

# 两个集合的差
difference_set = set1.difference(set2)
print(difference_set) # 输出为: {1, 2}

文件管理

在日常计算机使用中，会遇到各种各样的文件类型，例如图形文件、文字处理文件、电子表格文件等。
无论文件类型如何，内容都使用特定的二进制代码存储，从而保证文件的正常使用。

这里就出现了新东西：二进制文件 (Binary file)和记录 (Record)

二进制文件是包含二进制格式信息的文件，二进制格式是 0 和 1 的序列。二进制文件用于以计算机可以读取但人类不易理解的格式存储数据。二进制文件的示例包括可执行文件、图像文件和音频文件。

记录是一种包含一个或多个字段的数据结构，每个字段包含一条数据。记录用于以易于访问和操作的方式存储和组织数据。在计算机科学中，记录通常用于表示数据库和其他数据存储系统中的数据。

Binary file: a file designed for storing data to be used by a computer program.
Record: a collection of fields containing data values.

串行文件

串行文件 (Serial file)是一种包含信息的文件类型，信息按其发生的顺序记录在文件中。

它还可以用来记录文件信息。在这种情况下，文件信息将按照它们在串行文件中保存的顺序列出。所以说：信息或文件基本上是按时间顺序记录的。

顺序文件

顺序文件 (Sequential files)是根据某些键值排序的文件。顺序文件主要用于文件命中率较高的应用场景中。 #文件命中率衡量计算机系统或程序性能的重要参数,它可以反应计算机在访问存储器时的效率。

顺序文件的一个示例是包含有关公司员工信息的文件。
该文件可以根据员工的姓氏进行排序，以便将具有相同姓氏的所有员工分组在一起。这将使根据姓氏搜索员工变得更加容易。

直接访问文件

直接访问文件 (Direct-access file) 有时候也被称之为随机访问文件 (Random-access files)。和内存一样，随机性表明我们可以访问文件中的任何记录，或者在任何位置写入内容，而无需按照顺序依行读取文件。在使用这种文件时，我们可以直接访问文件的某个区块。

另一种方法是在将记录输入直接访问文件时使用散列算法。

如果每条记录中有一个数字关键字段，则可以使用一种简单的哈希算法。
该算法选择一个合适的数字并将该数字除以关键字段中的值。然后，该除法的余数标识文件中用于存储该记录的地址。
如果合适的数字是与文件的预期大小相似的质数，则效果最佳。

我们举一个简单的计算例子：我们使用关键字段中的 4 位值来说明文件中的地址，其中 1000 用于除数。以下代表三种计算，其中余数代表地址：

0045 / 1000 余数为45
2005 / 1000 余数为5
3000 / 1000 余数为5

从这些计算中可以看出两个事实。
第一个事实是，计算出的地址没有任何顺序，具体取决于关键字段中的值。
第二个事实是，不同的关键字段值可以产生相同的余数，因此在文件中产生相同的地址。

正因为相同的地址可能产生，所以当同一个地址被使用的时候，可能会发生冲突。
哈希算法的职责是尽可能平均地分配地址，从而最大限度地减少冲突的可能性。

但是哈希算法也不是万能的，无论再怎么平均分配，冲突必定出现。所以说如果冲突出现，我们有以下这些解决方案：

使用顺序搜索来查找计算出的地址后是否有空闲地址。
在文件末尾保留一些溢出地址。
创建一个可以从每个地址访问的链接列表。

文件访问

一旦我们选择了文件组织，并将文件中注入了数据，我们就需要考虑下如何使用这些文件，如何访问这些数据。

对于串行文件来说，正常的方法是逐条读取文件。但是说如果需要再其中的一个字段中搜索特定的一个值，唯一的办法就是从头开始读取记录，直到我们找到了我们的目标。

如果我们需要在顺序文件寻找特定值的话，可能也需要像串行文件一样进行搜索。但是，如果我们已知包含所需数据的关键字段，那么直接读取关键字段就可以了。

直接访问文件的话，首先需要将关键字段的值提供给哈希算法进行计算。

文件类型的选择

串行文件特别适合批处理或者备份磁带上的数据，因为串行文件中的数据是与时间相关的。

如果我们需要快速访问一个大文件中的单个记录，就需要使用直接访问文件。比如说需要登录一个具有许多用户的系统，在这种情况下，用户登录时用于检查密码的文件就应该是直接访问的。

顺序文件特别适用与从文件的一次搜索中获得多个记录的应用程序。一个例子是家谱：我们可以对所有特定家族名称的所有记录进行搜索。

实数

在计算机中，实数是带有小数部分的数。

当我们在一个二进制系统中写下一个实数的值，并需要存储下来的话，我们有多个选择：我们可以选择简单的表示法，也可以使用指数表示法(科学计数法)。

比如说，数字’25.3’可以写成：

.253 * 10^2 或 2.53 * 10^1 或 25.3 * 10^0 或 253 * 10^-1

就对于’25.3’来说，直接表达是最好的存储方案。
但如果数字非常大或非常小，就需要尽可能地使用科学计数法。

浮点&定点表示法

在计算机系统中，我们只能是有二进制码来存储实数。其中的一种方法就是使用定点表示法 (Fixed-point representation)。

在定点表示法中，首先需要确定总位数。其中总位数中的一部分位来表示整数部分，其余的位表示小数部分。

另一种方法就是使用浮点表示法 (Floating-point representation)。所有使用浮数都可以改写成下面这种形式：

±M × R^E

其中，有效的位数由±M表示，我们叫做尾数 (Mantissa)。E表示指数。浮点数中的 “指数 “并不代表原数的整数部分。相反，它表示在确定浮点表示数的值时，基数（在计算机系统中通常为 2）所升高的整数幂。

一般来说基数R不会存储进这个浮点数内，因为R有一个隐含值“2”。具体原因是我们在使用二进制表示数字时逢2进一。

Floating-point representation: a representation of real numbers that stores a value for the mantissa and a value for the exponent.

p.s. mantissa是尾数的意思。

我们来举例子了解一下两种表示法之间的区别：

对于定点表示法来说，在一个字节内，我们可以使用最高的有效位作为符号位，然后再使用接下来的五位表示整数部分。这就会为小数部分的表示留下两个位。

下表给出了一些比较重要的非零值：

描述	二进制码	(对应的)十进制数
最大的正值	`011111 11`	31.75
最小的正值	`000000 01`	0.25
绝对值最小的负值	`100000 01`	-0.25
绝对值最大的负值	`111111 11`	-31.75

浮点表示法的话，我们可以使用4个位来表示尾数，然后再使用另外的4位表示指数。每一个位都使用2的补码来表示。
其中，指数存储为有符号的整数，尾数存储为定点实数。

那么我们应该如何确定哪一位是二进制点。

下面的表格给出了使用4位来表示尾数的两个选项：
在每种情况下，我们都选择了等价的二进制点，

First bit pattern	Real value in denary
`011 1`	`3.5`
`011 0`	`3.0`
`010 1`	`2.5`
`101 0`	`-3.0`
`100 1`	`-3.5`
`100 0`	`-4.0`

First bit pattern	Real value in denary
`0 111`	`0.875`
`0 110`	`0.75`
`0 101`	`0.625`
`1 010`	`-0.75`
`1 001`	`-0.875`
`1 000`	`-1.0`

First bit pattern	Real value in denary
`0111`	`7`
`0110`	`6`
`0101`	`5`
`1010`	`-6`
`1001`	`-7`
`1000`	`-8`

浮点表示法的特殊值如下表所示：

描述	二进制码	(对应的)十进制数
最大的正值	`0 111 0111`	0.875 × 2^7 = 112
最小的正值	`0 001 1000`	0.125 × 2^(-8) = 1/2048
绝对值最小的负值	`1 111 1000`	-0.125 × 2^(-8) = -1/2048
绝对值最大的负值	`1 000 0111`	-1 × 2^7 = -128

p.s. 上课时候有人提出了一个问题：Exponent部分的第一位为什么不是1从而达到最大值？老师的解释是“因为Exponent部分也同样存在符号位，所以最大的正值只能将后三位填充为一。”

精度与标准化

当使用浮点表示法表示数据时，需要从两个方面着重考虑。

首先需要决定使用的总位数，然后还要决定分割线的位置 (表示尾数的位数和表示指数的位数之间的分割线)

然而在我们使用的时候只需要选择使用的总位数就可以了。具体的位数分割就会交给浮点处理器来决定。

当然这也不代表你没法决定尾数和指数位数的数量了：一般来说，增加尾数位数可以提供更高的精度，但是同样会减少指数位数。如此一来就会减少可以表示的值的范围。

所以说为了获取最大精度，我们就必须要标准化浮点数。因为越多的尾数位数代表着更高的精准度，所以在考虑提升精度时，要尽可能对表示尾数的位数使用多的位数。

将浮点表示法中的数字标准化意味着选择一个指数，以防止在尾数中出现前导零。。举个例子：0 1000.11并没有标准化：小数点前面一共有5位。如果想要标准化这一串数据，就要将其变成0.100011。小数点向左移动了四位，因此在此情景中指数为4。

我们可以使用八位浮点表示一个数值。因为要表示正数，十进制表示以2进位。
比如说：

十进制表示	浮点二进制表示法
`0.125 × 2^4`	`0 001 0100`
`0.25 × 2^3`	`0 010 0011`
`0.5 × 2^2`	`0 100 0010`

表示负数也没有问题。这里用-4作为十进制表示的底数：

十进制表示	浮点二进制表示法
`-0.25 × 2^4`	`1 110 0100`
`-0.5 × 2^3`	`1 100 0011`
`-1.0 × 2^2`	`1 000 0010`

表示法的转换

在AS部分的第一章，我们讨论了多种将数字转换为不同形式的方法。

先来看定点二进制表示法。举个例子：4.75转换为定点二进制表示法

打眼一看挺简单的：4可以转换为100，.75转化为二进制的.11，所以4.75的定点二进制表示法大概是100.11。但是别忘了正数的首位需要以0开头。这样的话就只添加一个符号位就可以解决问题了。这样，4.75就可以以定点二进制表示法写成0100.11。

那么负数怎么办呢？比如说-4.75，就可以先从4.75的表示开始，然后再将它转换成对应的二进制补码：

0100.11 转换为： 1011.00（一次补码）
1011.01就是-4.75的二次补码。

有关于二次补码的内容，可以去AS部分的第一张扒翻一下。

转换成浮点就有一些复杂了。在转换之前，我们应该注意：大多数小数部分无法精确地转换为浮点数值。因为二进制小数部分的因数有1/2， 1/4， 1/8， 1/16等等。所以说除非被转换的值正好是这些因数的和，否则无法进行精确的转换。
比如说，从0.1到0.9之间的的值中，只有0.5可以被精确的转换。

转换正值的方法如下：

使用我们在AS第一章中描述的方法转换整数部分。
添加在开头添加符号位
使用下面的方法转换小数位
将整数和小数部分组合起来，并将它们输入到分配用于表示尾数的最高有效位中。
用零填充尾数的剩余位和指数的位。
通过改变指数值来调整二进制小数点的位置，以实现归一化的表示。

第三步提到的方法如下：

我们试着转化一下8.75：

整数位8转换成1000，然后添加符号位。这样就变成了0 1000
小数部分“.75”可以在二进制中表示为.11

将小数转换为二进制时，可以将小数部分乘以2，然后观察得到的整数部分和小数部分。然后再乘以2直到得到的小数部分等于0。稍后需要将每次乘法结果的整数部分写成等价的二进制数。0.75十进制到二进制的答案是0.11。

小数部分“0.75”的转换步骤大概是：

1. 0.75 * 2 = 1.5，1.5的整数位包含1，因此位数部分的第一位需要写1。
2. 去掉刚才的乘积的整数部分，0.5 * 2 = 1.0。1.0的整数部分包含1，因此尾数部分的第一位需要写1。正因为整数位的1减去后，小数位不包含任何信息，所以转换到此结束。

所以0.75转化过后就是.11。

该组合给出 0 1000.11，其指数值为零。
移动二进制小数点后，我们得到 0.100011，小数点相比原来向左移动了四位，因此在此情景中指数为4其指数值为十进制的4。
下一阶段取决于为尾数和指数定义的位数；如果为尾数分配10位，为指数分配4位，则最终表示为尾数为 0100011000，指数为 0100。

使用浮点数的问题

如上所述，将十进制实数值转换为二进制表示形式几乎可以保证一定程度的近似。用于存储尾数的位数也有限制。

浮点数用于涉及重复计算的扩展数学过程。例如，在使用大气数学模型的天气预报中，或在经济预测中。在这样的编程中，在记录每次计算的结果时存在轻微的近似。
如果计算重复足够多次，这些所谓的舍入误差可能会变得很大。防止错误成为严重问题的唯一方法是通过使用更多的尾数位来提高浮点表示的精度。
因此，编程语言提供了以“双精度”或“四精度”工作的选项。

另外，浮点数还可能引发溢出错误条件，因为浮点数能够存储的数字范围有限。

第十七章：通讯及互联网技术

传输方式

对于通过互联网进行的通信，有两种可能的方法：电路交换 (Circuit switching)或分组交换 (Packet switching)。

电路交换

电路交换在传统电话系统中运用的比较广泛。

电路交换是实现电信网络的一种方法。在这种方法中，两个网络节点通过网络建立专用的通信信道（通过电路），然后才能进行通信。
电路的特征决定了信道的带宽，并且这个专用通讯链路会在使用期间一直保持连接。
电路交换法师一种面向连接的网络，通过在发送方和接收方之间建立专用路径，提供了有保证的数据传输速率。

通过电路交换传输数据的大致流程如下：

发送方提供预期的接收方的身份信息
由系统来检查接收方是否准备好接收数据
如果接收方可以接收数据，那么就会在网络上建立一些连接
数据随后被传输
移除所有的建立的连接

在这种情况下，我们暂时没有必要对电路交换网络中的每个节点进行定义。
节点之间的链路师共享传输介质中的专用信道，可以保证传输的畅通无阻、
当连接结束后，随着链路的断开，连接也就明确结束了。
不过，对于租用线路数据连接而言，可能会建立永久性的连线。

分组交换

分组交换 (Packet-switching)允许我们再不建立电路的情况下进行数据传输。

数据不能以连续的流的形式发送，相反，数据被打包成一个一个数据包内然后被发送出去。

数据包由包含传送指令的标头和数据主题构成。这个方法有点像邮政服务发送信件一样，但是要更加复杂。比如说在电路交换那一章的图片仍然可以描述数据包交换，只不过所使用的链路在发送方传输数据包的时候还没有被定义。

此外，与电路交换传输所需的功能相比，节点将具有更多扩展的功能。我们将会在下面的一个章节中探讨路由器如何充当节点并且支持数据包的发送与接受。

当我们使用分组交换法的时候，网络可以通过两种方式提供服务：无连接服务 (Connectionless service) 或者是 面向连接的服务 (Connection-oriented service)。

对于无连接服务来说，我们在发送数据包的时候不知道接收者是否准备好接受数据包，而且我们无法确认数据包是否会传输成功。

在面向连接的服务中，我们发送第一个数据包的目的是为了确认对方是否能够正常的接受数据包。如果收到了确认的话，那么发送方就会发送更多的数据包。如果没有收到确认，那么发送方就会再次尝试发送第一个数据包来确认状态。

传输协议

网络协议的基本定义很简单：它是一组规则。但问题是这些规则与什么东西有关呢？

在回答这个问题之前，我们应该明白：我们通常所说的“协议”是指的包含许多单独协议的协议栈，因为网络的复杂性需要我们去制定许多单独的协议。
另一个复杂因素是：一个协议可能有许多不同的版本。
而且通常有一类协议可以用来补充另一类协议的作用。

Protocol: a set of rules for data transmission which are agreed by sender and receiver.

任何通过网络传输的通信，都必须在发送方和接收方之间商定一套构成协议的传输规则。
在最简单的层面上，协议可以规定成正电压代表比特值为1。协议也可以规定发送方不得超过的传输速度。
许多规则与信息的格式或信息的组成部分有关。比如说，定义数据包中前40哥字节的格式。

协议栈

对于协议套件而言，协议可以被是认作为协议栈中的层。这一概念设计了多个方面：

每一层只能接受上一层或者下一层的输入。
相邻的层之间有一个明确的界限，这是层与层之间唯一允许的互动。
一个层由下层的行动提供服务。
除了最底层之外，各层的功能都是由安装的软件创建的。
层可以包括子层。
任何用户交互都将使用与堆栈中最高层相关的协议。
对于硬件的任何直接访问都仅限于堆栈的最底层。

TCP/IP 协议套件

TCP/IP是为支持互联网使用二创建的协议套件。
TCP/IP可以根据下图所示的模型来进行解释：

不难看出，TCP/IP协议只占用了这个模型的前三层。

图中显示了两个终端系统（最左边和最右边的两列），并且也显示了这两个系统中相应层之间的逻辑连接。
一个应用程序可以在一个终端系统上运行，并与另一个终端系统上运行的应用程序建立直接连接。
发送端系统上的应用层协议向同一系统上的传输层协议发送信息，然后传输层协议启动一个进程，将相同的信息传送到接收端系统。
在接收端系统上，最后阶段是传输层协议将信息传送给应用层协议。

TCP/IP协议套件由许多子协议组成，包括以下协议：

应用层协议： HTTP SMTP DNS FTP POP3 IMAP
传输层： TCP UDP SCTP IP
网络层： IP IGMP ICMP ARP

选择这些协议是为了说明TCP/IP协议套件包含了应用范围非常广泛的协议，而且这些协议仍然在不断地发展。

TCP (传输控制协议)

传输控制协议 (Transmission Control Protocol, TCP)是指TCP协议套件中定义的一个协议。它起源于最初的网络实施，是互联网协议（IP）的补充。因此，整个协议套件通常被称为 TCP/IP。

TCP 是面向连接的。客户端和服务器之间必须先建立连接，然后才能发送数据。
在建立连接之前，服务器必须监听（被动开放）客户端的连接请求。
三方握手（主动打开）、重传和错误检测增加了可靠性，但延长了延迟。

（所以如果不需要可靠数据流服务的应用程序可以使用用户数据报协议 (User Datagram Protocol, UDP)。它提供的无连接数据报服务优先考虑的是最低延迟，而不是可靠性。）

TCP 可避免网络拥塞，不过，TCP 也存在漏洞，包括拒绝服务、连接劫持、TCP 否决和重置攻击。

如果在终端系统上运行的应用程序要向不同终端的系统上面发送信息，那么这个应用程序会被收到上面说过的应用层协议所控制。
该协议会将用户的数据传送给传输层，然后由传输层运行的TCP协议负责讲信息安全的发送给接收方。

TCP协议会创建足够的数据包来容纳所有的数据，而且每一个数据包都会由报头和用户数据组成。

除了确保数据的安全传输外，TCP协议还需要确保任何相应都会被引导回应用层级，因此，报文头中的一项内容就是端口号 (Port number)。端口号用于标识应用层的协议，比如说，HTTP的端口号就是80。

数据包还必须包括接收端系统应用层协议的端口号，虽然说TCP不关心接收端的系统地址。

在一个序列里的数据包会包含一个序列号，目的是为了在数据传输的重点能够正确的按照顺序重新组装数据。

TCP 协议是面向连接的。一旦网络层向传输层返回确认，表明连接已经建立，TCP 就会发送其他数据包并接收包含确认的响应数据包。而且还可以识别并重新发送丢失的数据包。

IP (互联网协议)

互联网协议 (Internet Protocol)是一种协议或者一组规则，用于数据包的路由和寻址，使其能够穿越网络到达它要去的目的地。
穿越互联网的数据被分为一个个较小的块，我们之前提到过，叫做数据包。每个数据包的报头都附有IP信息，这些信息有助于

在网络层中，IP的是能够确保终端连接互联网的一个重要因素。
IP协议从传输层接受数据包，然后添加一个报头。报头包含发送方和接收方的IP地址。要找到接收方的IP地址，很可能需要使用DNS服务来找到与用户数据中提供的URL相对应的地址。

IP数据包通常被叫做“数据报 (Datagram)”。它被发送到数据链路层，然后被发送到不同的协议套件中。

数据链路层会把数据报组装成一个“帧”，然后再进行发送。有关这个“帧”的内容下一章我们会进一步解释。

IP具有无连接服务的功能，一旦发送了数据包，IP无法知道他是不是真正的到达了目的地。如果IP收到了一个包含对先前发送的数据包的确认数据包，那么它只会把该数据包传递给TCP，自己不会了解其中的内容。

路由器

上面的图片显示，数据链路层发送的“帧”在传送之前会到达一个路由器（或者是多个路由器）。在这一阶段，帧的数据报内容会被反馈给IP。现在路由器软件的功能是在传输过程中选择下一个目标主机。

用白话来说，当数据从一台设备发送到另一台设备时，会被分解成叫做“帧”的微小单元，然后通过网络发送。这些帧首先会被路由器接受，因为路由器是引导网络数据流的设备。
路由器检查包含数据报内的帧内容，并使用路由表来确认数据的下一个目的地。
路由表是每个路由器特有的，包含数据通过网络的最佳路径等其他信息。一旦路由器确认了下一个目的地，它就会更新数据报中的地址，然后将其传回数据链路层，由数据链路层继续发送。这一过程在每一个路由器上都会重复运行。

作为网络中的一个节点，交换机和路由器的主要区别是在于：当一个帧到达交换机的时候，交换机不做任何的路由操作，而是直接发送数据。交换机在数据链路层运行，但是无法进入网络层。

以太网(Ethernet)协议栈

在AS部分的第二章，我们就已经了解过以太网了。以太网是一套专门为局域网设计的协议，因此它可以在不予互联网或者任何网络连接的本地局域网中运行。
但是现在的局域网几乎不可避免地需要与互联网产生链接，所以说局域网的协议套件现在已经添加了对于互联网协议套件的支持。

如果我们仔细查看一个终端系统的协议栈(还是上面的那个图)，你就会发现TCP/IP协议套件占据了五层协议栈的最上面的三层，因此我们可以说，TCP/IP协议套件得到了下面两层的支持。
TCP/IP与这两个较低层的功能无关，它的设计目的是能够得到任何可用协议的支持。

值得注意的是，有些数据来源只对终端系统使用了4层栈。这种情况下，可能是数据决定只调用完全由软件处理的层，也可能是将TCP/IP的所有支持合并到了同一层中。

以太网是最有可能用来提供两个较低层所需功能的协议。从逻辑上来说，以太网套件包括了数据链路层和物理层两个子层，如下图所示：

下面的这几点说明了以太网在支持TCP/IP的时候的功能：

逻辑链路控制(Logic Link Control, LcC)协议负责与网络层的交互。它管理数据传输并确保数据传输的完整性。不过由于以太网是一种无连接协议，所以它不负责检查传输是否成功发送。
介质访问控制(Medium Access Control, mac)协议负责组装被称之为“帧”的以太网数据包。其中的两个组成部分是发送器地址和接收器地址。此外，MAC协议还负责启动帧传输，并处理因碰撞(可能因为使用了CSMA/CD)导致的传输失败之后的恢复工作。
物理编码子层（Physical Coding Sublayer, PCS）,协议负责对准备传输的数据进行编码，或对于收到的数据进行解码。
物理介质附件(Physical Medium Attachment, PMA)协议负责信号的收发。

MAC地址

在以太网中，一个以太网帧使用的地址是物理地址或者MAC地址。
MAC地址值分配给网络接口控制器（NIC）的唯一标识符，用作网段内通信的网络地址。这部分的内容同样在AS部分的第二章提到过。简单来说，MAC地址标识一个唯一的网卡。
在大多数IEEE 802网络技术（包括以太网，Wi-Fi和蓝牙）中，这种用法都十分常见。

迄今为止，定义MAC地址使用的48位可以保证每一个设备都分配到他们自己的MAC地址。不过，除了使用48位方案，现在还有一种64位的替代方案。这种方案已经偶尔使用，但是在将来48位地址不够用的时候就真正派上用场了。

48位地址通常使用十六进制标识，比如说：

4A:30:12:24:1A:10

与TCP/IP有关的应用层协议

HTTP (HyperText Transfer Protocol)

超文本传输协议(HyperText Transfer Protocol, HTTP)，是最重要的应用层协议，因为这是万维网的基础。
每次用户使用网络浏览器访问网站的时候都会用到HTTP，但它的功能对用户是隐藏的。换句话说，当你访问一个网站的时候，你的浏览器会向网站的服务器发送一个HTTP请求，而服务器则使用HTTP回应用户网站的内容。这个过程发生在幕后，用户是看不到的。

HTTP协议定义了报文的格式。请求信息的第一行是“请求行 (Request Line)”，请求行之后还可以加上标题行 (Header Line)。所有这些信息都是用ASCII编码。请求行的格式如下：

<Method> <URL> <Version>CRLF

其中后面的CR和LF是ASCII的回车和换行符。

请求行通常使用GET作为获取方法。不过除了GET方法，还存在其他的获取内容方法。这使得HTTP成为一种适用范围更广的协议，而不仅仅用于网页访问。
在使用HTTP的时候，我们必须指定HTTP的版本，因为HTTP发展到现在已经存在了好多版本。

电子邮件协议

发送和接受电子邮件的传统方法如下图所示：

这其中设计三个单独的客户端到服务器的交互。客户端的电子邮件发件人必须和邮件服务器建立连接，然后该服务器必须变成“客户端”向真正客户端的电子邮件接收者所使用的邮件服务器进行传输。

目前存在以下三种主流的电子邮件协议：

简单邮件传输协议(Simple Mail Transfer Protocol, SMTP)，是一种“Push”协议，即用于从一个服务器向另一个服务器发送电子邮件。而邮局协议版本3 (POP3)是一种“Pull”协议，即用于从服务器检索电子邮件并下载到客户端计算机。

还有一种协议叫做互联网消息访问协议 (Internet Message Access Protocol, IMAP)，这是POP3的最新替代方案。POP3是将电子邮件下载到客户端计算机上，但是IMAP允许将电子邮件保存在服务器上，同时客户端也可以访问存储的电子邮件。
这意味着如果使用IMAP协议，你可以在任何设备上访问你的邮件。而使用POP3，我们只能从下载邮件的客户端系统访问你的邮件。

一般来说，POP3在抵御网络攻击方面可能会更加安全，因为电子邮件都存在客户端计算机的本地。不过使用IMAP存储电子邮件的服务器可能会定期备份，但是本地客户端大概率不会。

FTP (文件传输协议)

文件传输协议 (File Transfer Protocol, FTP)是一种标准通信协议，用于在计算机网络中将计算机文件从服务器传输到客户端。

FTP 基于客户机-服务器模型架构，在客户机和服务器之间使用独立的控制和数据连接。FTP 用户可以通过明文登录协议（通常以用户名和密码的形式）进行身份验证，但如果服务器配置允许，也可以匿名连接。

为了保护用户名和密码并对内容进行加密的安全传输，FTP 通常使用 SSL/TLS (FTPS) 或用 SSH 文件传输协议 (SFTP) 代替。

P2P文件共享

点对点文件共享 (Peer-to-peer file sharing, P2P file sharing)产生的网络流是互联网使用的主要特征之一。

P2P 是一种没有结构和控制机制的架构。点对点既是客户端也是服务器，每个点对点只是一个终端系统。当对等体充当服务器时，它被称为 “种子”。

在P2P中，BitTorrent协议是最常用的协议，因为它可以快速的共享文件。 BitTorrent 是一种用于点对点文件共享（P2P）的通信协议，它使用户能够以分散的方式在互联网上分发数据和电子文件。要发送或接收文件，用户需要在联网电脑上使用 BitTorrent 客户端。

BitTorrent 客户端是实现 BitTorrent 协议的计算机程序。BitTorrent 客户端适用于各种计算平台和操作系统，包括 Rainberry 公司发布的官方客户端。流行的客户端包括 μTorrent、迅雷、Transmission、qBittorrent、Vuze、Deluge、BitComet 和 Tixati等等。

BitTorrent 跟踪器提供可用于传输的文件列表，并允许客户端查找可传输文件的对等用户（称为 “种子”）。程序员布拉姆-科恩于 2001 年 4 月设计了该协议，并于 2001 年 7 月 2 日发布了第一个可用版本。BitTorrent 协议可用于减少分发大文件对服务器和网络的影响。BitTorrent 协议允许用户加入一个主机 “群”，同时相互上传和下载文件，而不是从单个源服务器下载文件。

如果我们决定在终端系统使用BitTorrent，我们需要解决下面这三个基本问题：

如何确保计算机能够在网络上找到拥有目标资源的计算机？

首先每个内容的供应者都提供一个内容描述，叫做torrent。这是一个包含跟踪器（引导计算机找到内容的服务器）名称和内容块列表的文件。torrent文件比内容至少要小上三个过更多的数量级，因此这样的种子文件更易于我们传播。
跟踪器是一个服务器，它的任务是维护正在下载和上传内容的所有其他的终端的列表。

在这样的对等网络上，如何为所有人提供高速的下载？

对等网络在下载和上传的过程是同时发生的，但是对等网络必须同时交换数据块列表，来确保优先下载稀有的数据块。只要下载一次稀有的片段，那么这个数据块的稀有程度就会降低。

每个终端如何鼓励其他的终端提供内容，而不是仅仅使用协议下载文件造福自己？

在经济中有一个名词叫做”Free-rider”。在这里我们需要对付的就是这类的终端。解决的方法如下：
首先一个终端先随机尝试连接其他的终端，然后仅仅向那些提供常规下载的节点传输数据。如果发现有一个节点不下载或者下载速度贼慢，那么这个节点最后就会被“隔离”或者“阻塞”。

第十八章：硬件与虚拟机

控制单元

控制单元 (Control unit, CU)是计算机中CPU的一个组件，用于指导处理器的运行。它通常使用二进制解码器将编码指令转换为定时和控制信号，从而直到内存，算术逻辑单元(ALU)和IO设备等其他单元的运行。

控制单元管理大部分计算机的资源，并直到中央处理器与其他设备之间的数据流。在现在计算机设计中，控制单元通常是中央处理器的内部组成部分，其整体作用和运行方式自推出以来一直没有发生改变。

在执行程序时，中央处理器会接收一连串机器码指令。中央处理器内的控制单元有责任确保正确处理每一条机器指令。有两种方法可以设计控制单元，使其发挥功能：

将控制单元构建为逻辑电路：这也称为硬连线控制单元 (Hardwired control unit)。硬连线控制单元通过逻辑电路将从中央处理器内存接收到的指令转化为控制信号。来自计算机主机内存的指令被发送到指令寄存器，指令寄存器负责识别其“操作码”。随后操作码被传递给指令解码器，指令解码器使用操作码来解释要生成的控制信号。然后，逻辑电路根据任何外部输入和条件代码创建了信号。</br> </br>整个过程由系统时钟同步，系统时钟产生有规律的脉冲，在低电平和高电平之间持续切换，形成了0和1。这种控制单元之所以是“硬连线”，是因为他们的逻辑电路是由硬件以逻辑门电路的物理排列。</br> </br>硬接线控制单元的一些缺点是成本相对较高，难以用于复杂的操作，而且无法在不进行物理改动的情况下对它进行修改。此外，每个电路只能处理一种形式的指令。不过，硬接线控制单元速度更快，因为每一种指令都由自己指定的电路来完成计算。
使用微编程构建微程序控制单元：这样的方法叫做微程序控制单元 (Microprogrammed control unit)。微编程控制单元采用编程的方法实现。在微程序控制中，微操作是通过执行由微指令组成的程序来实现的。

控制存储器地址寄存器用来指定微指令的地址。控制存储器被用为ROM，其永久存储了左右的控制信息我们一般称为固件 (Firmware)。控制寄存器保存从存储器获取的微指令。微指令包含一个控制字，为数据处理器指定一个或者多个微操作。

CISC和RISC处理器

处理器的架构是指其物理结构。不过，处理器也有所谓的 “指令集架构”。

指令集架构涉及到：

指令集
指令格式
寻址模式
指令可以访问的寄存器

其中，指令集的选择是区分指令集架构的主要因素。

在计算机发展的早期，选择计算机指令集架构的一个重要因素是，该架构是否能够使高级语言编译器的编写变得更加容易。我们现在将这一种架构叫做复杂指令集计算机 (Complex Instruction Set Computer, CISC)。

直到20世纪70年代末期，人们开始对这一理念产生质疑。有人认为，使用精简指令集计算机 (Reduces Instruction Set Computer, RISC)会是一种更好的方法。

下面介绍一下这两位：

CISC和RISC是两种不同类型的计算机体系结构。二者的主要区别在于中央处理器可执行的指令数和执行这些指令所需要的周期数。

CISC试图尽量减少每个程序的指令数，但是代价是这会增加每个指令的周期数。这就意味着CISC处理器一般拥有大量的复杂指令，但是可以在一条指令中执行多种操作。这些指令通常更长，功能更强大，可以用更少的单条指令来完成复杂的任务。

现在转过头来看看另一边的RISC。RISC是一种以每个程序的指令数量为代价来减少每条指令周期的方法。这就意味着RISC处理器的简单指令数量较少，只能执行单一的操作。这样，RISC处理器的指令集就设计的比CISC更简单，更小了。这些指令通常更短更简单，需要更多的单独指令才能完成复杂的任务。

这两种方法各有利弊。CISC处理器通常更容易编程，因为它们有更强大的指令。但由于每条指令的周期数多，所以运行速度可能会慢一些。RISC处理器由于减少了每条指令的周期数，因此运行的速度普遍较快，但是因为需要更多的单独指令来执行复杂的任务，因此这可能会使得编程的难度直线上升。

Complex Instruction Set Computer (CISC): a single instruction can be more complex and involve more loading of data from memory.
Reduced Instruction Set Computer (RISC): s single instruction is simpler, requiring minimal loading of data from memory.

下表列出了RISC区别于CISC的一些特征：

RISC	CISC
更少的指令数	更多的指令数
更简单的指令	更复杂的指令
指令格式相对简单	指令格式复杂
尽可能使用单周期指令	多周期指令
定长指令	可变长度指令
只对内存地址执行加载和存储指令	向内存地址存储多种指令
更少的寻址模式	更多的寻址模式
多个寄存器组	更少的寄存器
多为硬连线控制单元	多为微程序控制单元
更利于流水线作业	不太利于流水线作业

需要注意的是，RISC处理器大多使用硬连线控制单元，而CISC处理器大多使用微编程控制单元。

指令数量的减少并不是使用RISC的主要驱动力，降低指令的复杂性才是RISC的主要特征。

典型的CISC架构包含很多的专用指令，专用指令的设计符合高级编程语言的要求。专用指令需要多次访问内存。与直接访问寄存器相比，访问内存的速度可谓是相当慢。

RISC处理器的指令非常简单，因此数据可以存储在寄存器中，并在寄存器中进行操作。除了初始化和资源存储请求之外，无需对存储器进行任何的访问。

RISC指令的简单性使得硬连线控制单元的使用更加容易。而许多CISC指令的复杂性使得硬连线控制单元的构建更加复杂，因此我们使用微程序控制单元。

流水线作业 (Pipelining)

创建 RISC 处理器的主要驱动力之一，就是为高效流水线提供机会。

流水线 (Pipelining)是一种专门应用于指令执行的并行方式。其他并行形式将在下一节中讨论。

好像翻译成“流水线”不是很恰当，但是懂我意思就行

Pipelining: instruction-level parallelism.

流水线作业的基本原理是第五章中介绍的F-E Cycle可以分为若干阶段。其中的一个形式是“五阶段模型”。要实现流水线操作，处理器的结构必须含有5个独立的单元，这样每个单元就可以单独处理五个阶段中的其中一个阶段。这同样解释了为什么RISC处理器需要许多的寄存器组，因为存在多个处理单元，而每个单元必须需要寄存器来访问将要使用的数据。

五阶段模型如下表所述：

时钟周期 →	1	2	3	4	5	6	7
Instruction Fetch (指令读取，IF)	1.1	2.1	3.1	4.1	5.1	(6.1)	(7.1)
Instruction Decode (指令解码，ID)		1.2	2.2	3.2	4.2	5.2	(6.2)
Operand Fetch (操作数抓取，OF)			1.3	2.3	3.3	4.3	5.3
Instruction Execute (指令执行，IE)				1.4	2.4	3.4	4.4
Result Write Back (结果回写，WB)					1.5	2.5	3.5

在上面的表格中，每一行代表流水线中的一个阶段：指令读取 (IF)、指令解码 (ID)、操作数读取 (OF)、指令执行 (IE) 和结果回写 (WB)，同时每列代表一个时钟周期。单元中的数字代表指令编号和该指令的阶段。例如，”1.1 “表示指令 1 处于第一步 “IF” 阶段，”2.5 “表示指令 2 处于第五步 “WB” 阶段。

解读一下表格：最初只有第一条指令的第一阶段进入了流水线。在第六个时钟周期，当第一个指令已经离开流水线时 （因为不存在第六个流水线阶段），指令2的最后一步仍在处理，而且指令6才刚刚进入流水线作业 （因为没有第六个流水线阶段，所以第六个指令的流程并没有画在表上。但如果第六个指令需要处理的话，会在第六个时钟周期进入流水线）。

流水线一旦开始运行，就要处理五个阶段的五条单独指令。特别是在每个时钟周期，都需要完成一条指令的处理工作。如果没有流水线并行作业，那么处理时间将延长五倍。

在流水线系统中，多条指令在流水线的不同阶段同时处理。当中断发生时，流水线中就会有几条指令尚未执行完毕。
有两种解决中断问题的解决方案：

第一种：清除最近进入的四条指令的流水线内容，只留下最早进入的指令。然后，正常的中断处理程序就可以应用于剩余的指令。
第二种：在处理器中构建具有独立程序计数器寄存器的独立单元。这样就可以在处理中断时为流水线中的所有指令存储当前数据。

基本计算机架构

描述不同计算机体系结构的一种有效的方法是：考虑指令流的数量和数据流的数量。因此这区分出了四种类型的架构：

单指令流单数据流 (SISD)

单指令流单数据流 (Single Instruction Stream Single Data Stream, SISD)是早期计算机中的典型架构，同样也是早期的微处理器所采用的排列方式。具体来说，SISD代表了包含一个控制单元，一个处理器单元和一个存储器单元的单台计算机的组织结构。所有的指令按照顺序执行，系统内部可能有并行能力，也可能没有。

虽说是这样，但是课本上写的是SISD纯粹是顺序性的产物，没有一点点并行性。我们就按照这条来记吧。

下图展示了如何使用SISD来操作数组中的单个元素：

图中给出了一个原始的数组。如果机器需要将这个数组内的元素乘以2，那么SISD就会按照顺序一个一个地处理数组内部的数据，从右到左。换言之，SISD对于数组内每一个元素都执行了相同的“乘以2”的操作。

SISD: Stands for Single Instruction Stream Single Data stream; a single processor accessing one memory.

单指令流多数据流 (SIMD)

单指令流多数据流 (Single Instruction Stream Multiple Data Stream, SIMD)所描述的计算机具有多个处理元件，可以同时对多个数据点执行相同的操作。这类计算机利用数据级的并行性，但是不利用它们的并发性。

SIMD是一种并行处理方式，也就是多个处理元件同时对多个数据点执行相同操作。这意味着计算机就可以使用相同的指令同时处理多个数据点，而不是一步只能处理一个数据点。这可以大大提升某些类型计算的速度。也就是说，虽然说存在并行计算，但是每个单元在任何给定的时刻都执行完全相同的指令。

下图是一个SIMD的图示：

由图可见，所有在数组中的元素都在同一个指令周期完成了处理，而不像SISD一样每一个元素都需要单独处理。

SIMD 的结构通常用图表表示，就像下图一样：

在本图中，结构图显示数据流进入了四个单独的组件，这些组件都提供了相同的指令。这些组件被称之为处理单元(Processing Unit, PU)，有时这些组件也被称为处理原件(Processing Element, PE)。无论使用什么名称，这些组件都全部是ALU，也就是算术逻辑单元。有多个名称的原因是因为实现SIMD有多种方法：

第一种实现方法是使用阵列或者向量处理器(Matrix & Vector processors)。他们有一组并行的寄存器，每一个数据流都会被安排一个寄存器。我们可以使用一4位或者128位的大型寄存器，来同时存储多个数值。在这种实现方式中，并行性仅仅内置在一个处理器中，允许这个处理器同时处理多个数据流。

另一种方法是使用多核处理器。现在大多数的电脑都搭载了多核处理器。比如说使用4核处理器，就代表四个处理器并行工作。在这种情况下，每一个处理器都可能有自己专用的告诉缓存来提供可靠的数据流。

SIMD: Stands for Single Instruction Stream Multiple Data Stream; processing of parallel data input requiring one control unit instructing multiple processing units.

多指令流单数据流 (MISD)

多指令流单数据流 (Multiple Instruction Stream Single Data Stream, MISD)是一种并行计算架构，其中许多功能单元对同样的数据执行不同的操作。

与SIMD相比，MISD的应用就少得多，因为MISD通常更适合常用的数据并行技术。具体来说，他们可以更好的扩展和使用计算资源。话虽这么讲，MISD也是有应用的，比如说用于航天飞机的飞行控制计算机。大家也知道航天方面的数据计算是不容有失的，-在这种情况下，使用 MISD 架构可将多条指令应用于同一数据流，从而提供冗余并提高系统的可靠性。

MISD: Stands for Multiple Instruction Stream Single Data Stream; does not exist in a single architecture.

多指令流多数据流 (MIMD)

多指令流多数据流 (Multiple Instruction Stream Multiple Data Stream, MIMD)是一种并行计算架构。在这种架构中，有许多个处理器异步独立运行。在任何时候，不同的处理器都可能对不同的数据执行不同的指令。

MIMD架构被应用于多个领域，如计算机辅助设计，仿真，建模或者是通信交换机。MIMD机器可以分为共享内存和分布式内存两类，他们的类别是基于MIMD处理器访问内存的方式决定的。共享机器模型可以是总线型、扩展型或者分层型。

MIMD: Stands for Multiple Instruction Stream Multiple Data Stream; multiple processors asynchronously processing parallel data input.

大规模并行计算机系统

大规模并行计算机系统 (Massively parallel computer systems)是指使用大量计算机处理器（或者是独立的计算机）同时并行执行一组协调计算的计算架构。这可以通过各种各样的方法实现，比如说网格计算 (Grid computing)，就是透过使用大量的异构计算机的未使用资源，将其作为嵌入在分布式电信基础设施中的一个虚拟的计算机集群，为解决大规模的计算问题提供模型的方案。大名鼎鼎的SETI@home项目就是使用了这项技术，通过筹集大量计算机用户的剩余资源来分布式计算问题。这些小的计算机结合起来的算力同样强大，丝毫不亚于超级计算机。

大规模并行计算机系统与超级计算机的区别在于，负责驱动多个处理器的不是总线结构，而是支持多个计算机单元的网络基础设施。不同计算机上面运行的程序可以通过网络传递信息进行通信。

虚拟机

虚拟机听起来像是个硬件，但其实不是。最常见的虚拟机类型是系统虚拟机 (System virtual machine)，它的作用是模拟真实计算机系统硬件的软件。

System virtual machine: the emulation of computer system hardware using software.

一般来说，应用程序需要在操作系统支持的情况下才能在硬件上直接运行。虚拟机的原理是进程直接与操作系统提供的软件界面进行交互，如下图所示：

从上图我们需要注意这几点：

应用程序是在客户操作系统的协助下安装的。客座操作系统将通过与虚拟机交互来支持运行中的应用程序，就好像客座操作系统通常运行的硬件一样。
虚拟机实施软件可被视为一种实用程序，运行时受特定主机操作系统的支持，而主机操作系统又是主机硬件所特有的。
在主机操作系统的控制下，主机硬件上可以同时直接运行应用程序。

虚拟机方法的主要优点是可以在一个计算机系统上提供多个不同的操作系统。如果一个组织拥有遗留系统，希望继续使用旧软件，但又不想保留旧硬件，这一点就特别有价值。

另外，拥有大型主机并提供服务器整合设施的公司也可以多次提供相同的操作系统。不同的公司可以获得自己的虚拟机，作为服务器运行。

使用虚拟机的一个缺点是需要花费大量时间和精力来实施。另一个缺点是虚拟机的性能无法达到普通系统的性能水平。

之前在第八章讨论的 Java 虚拟机是进程虚拟机的一个例子，它基于不同的基本概念。进程虚拟机提供了一个与平台无关的编程环境，允许程序在任何平台上以相同的方式执行。这是一种仅支持运行 Java 程序的特定软件。

第十九章：逻辑门与布尔代数

逻辑电路

早在第四章，我们就已经接触过了逻辑电路中使用的逻辑门符号，并讨论了逻辑电路，真值表和逻辑表达式之间的关系。本章会介绍一些额外的内容，比如一些用于构建计算机硬件功能组建的特定电路。

半加法器 (The half adder)

在计算机中，二进制加法运算随处可见。两个比特的结果相加结果要么为1，要么为0。在一些特殊情况下，如1和1相加，会导致当前位结果为0，同时它的下一位会被加一，也就是进位。

执行二进制加法最简单的电路是半加法器 (Half adder)。如下图所示，半加法器会接受两个值的输入，然后输出“和位(S)”和一个“进位(C)”。

这个电路的真值表看起来就是这样的：

Input	Input	Output	Output
A	B	S	C
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

通过检查这个真值表，我们大概可以推测出半加法器的成分如何。
可以看到，只有在两个输入位都为1的时候，进位C才会出现1的结果。因此，C输出的真值表就可能是基于AND逻辑门实现的。
和位S输出的真值表与之前聊过的XOR运算符的真值表一致，所以我们也可以推测半加法器里面还存在一个XOR逻辑门。
因此，产生半加法器功能的电路可以包含一个AND门和一个XOR门，其中这两个逻辑门都会接受A和B两个输入。

当然，上面列出的只是完成这个功能的其中一种情况，还有更多逻辑门的搭配方式可以实现这样的功能。冷知识：NAND逻辑门和NOR门是两个通用门，这意味着任何的逻辑电路都可以使用这两种逻辑门进行构建。再加上NAND和NOR门易于制造的特点，导致电路制造商们很喜欢使用它们俩。下面这个图片就是仅仅使用NAND门和NOR门构建出来的一个半加法器：

Half adder circuit: a circuit which performs binary addition of two individual bits.

全加法器 (The full adder)

一般来说，如果我们需要计算两个二进制数字相加，则我们必须要从两个数字的最小位开始计算，一直计算到最大位。在计算的每一个阶段，前一个加法的结果的进位数字都必须并入到当前的计算中。
如果每次使用半加法器，就必须需要使用单独的电路来处理进位问题，因为半加法器仅仅接受两个输入。

全加法器 (Full adder)是一种执行加法运算的一种电路。这种加法器接受三个输入：两个需要相加的数字和上一位产生的进位，并产生三个输出，分别是三个输入的和以及下一位的进位。

当我们需要对不止一位进行二进制加法运算时，我们最好使用全加法器，因为全加法器考虑了前一位假发的金文，所以它能够处理所有的进位问题。例如我们设计对多位二进制数（如4位，8位，16位二进制数等）进行算术运算的电路，我们就需要使用全加法器。

全加法器的真值表如下：

Input	Input	Input	Output	Output
A	B	Cin	S	Cout
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

全加法器的一种可能的构造如下图所示：

我们之前说过，所有的电路理论上都可以使用NAND和NOR逻辑门来构建。所以全加法器的另一种构造如下图所示：

Full adder circuit: a circuit which performs binary addition of two individual bits and an input carry bit.

时序电路

到目前为止，本书中介绍过的所有电路全部都是组合电路 (Combinational circuit)。对于这样的电路来说，输出的值只由输入的值决定。
接下来我们会介绍时序电路，它的输出取决于输入和前一个输出项。

时序电路 (Sequential logic circuit)是一种数字电路，它存储上一个输出信息并使用它来计算下一个输出。我们刚说过，时序电路于组合电路不同之处就在于，时序电路既依赖当前输入值，同样也依赖存储在某一个存储元件中的上一个输出状态。

Combinational circuit: a circuit in which the output is dependent only on the input values.
Sequential circuit: a circuit in which the output depends n the input values and the previous output.

SR 触发器 (SR Flip-flop)

下面我们要介绍的SR触发器，是时序电路的一个简单例子。

SR触发器 (SR Flip-flop)，又称之为SR锁存器，是数字电子产品中经常会用到的一种基本触发器。SR触发器是一种双稳定器件，这意味着SR触发器有两个稳定状态，而这两种稳定状态可以被无限期保存。正因为这种独特的记忆特性，卫门叫它“锁存器”。它可以由两个NAND门和一个NOR门组成，如下图所示：

SR触发器有两个输入端，分别是 “置位” (S)和 “复位” (R)。以及两个输出端，分别是Q和Q’。
SR触发器的工作原理如下：

设置 (set) 状态：当设置(S)为1，(R)为0时，这时输出(Q)就会变为1。这表示锁存器进入了设置状态。
复位 (reset) 状态：当设置(R)为1，(S)为0时，这时输出(Q)就会变为0。这表示锁存器进入了复位状态。
保持 (hold) 状态：当输入端的(S)和(R)均为0时，无论上一个状态是设置状态还是复位状态，触发器会保持原来的状态。也就是说，输出还是会与上次相同。
比如说，如果SR触发器的上一个状态处于“set”状态，也就是Q的输出为1，并且输入S和R都是0，那么触发器会继续输出Q为1。

SR触发器的真值表如下所示：

Input Signals	Input Signals	Initial State	Initial State	Final State	Final State
S	R	Q	Q’	Q	Q’
0	0	1	0	1	0
1	0	1	0	1	0
0	1	1	0	0	1
0	0	0	1	0	1
1	0	0	1	1	0
0	1	0	1	0	1

从真值表中我们可以发现，表中不包含当R = 1或者S = 1的行，因为如果当S与R同时等于1，会导致输出“非法”。因为当遵循布尔代数原则时，Q和Q’不会同时输出0。Q与Q’本身应该就是彼此互补的，即当一个值为1时，另一个值应该为0。所以，输出是违反这个逻辑，是“非法”的。

在实际运用中，我们要避免使S和R都同时为1，因为它会导致数字电路中不可预测的行为。因此为了保证电路的可靠运行，我们需要尽可能避开这种用法。

JK 触发器 (JK Flip-flop)

我们在数字电路中最讨厌的就是像刚才SR触发器中，任何可能导致电路发生“不可预测”的无效输出或者错误处理。
实际上，除了在电路中存在S与R都为1导致的无效输出之外，如果信号无法同时到达触发器，也会导致输出的不可预测性。为了解决这个问题，电路可以包含一个时钟脉冲输入，以提供同步输入的更好机会。JK触发器 (JK Flip-flip)，也叫JK锁存器，就是这样的一个例子。

JK触发器是一种连续双状态单比特存储设备，是以它的发明者杰克·基尔命名的。
这个不重要，重要的是JK触发器有一个时钟输入引脚(Clock, CLK)，两个数据输入引脚(J和K)和两个输出引脚(Q和Q’)。如下图所示：

JK触发器可以画成左边的简略形式，它的展开形式如右图所示。

在时钟周期的情况下，JK触发器可以在时钟的前缘触发，或者是后缘触发。将时钟周期想象成一个方波。前缘就是电平从0变成1的电平上升时刻，而后缘就是电平从1变成0的电平下降时刻。

要理解电路是如何运作的，我们需要先理解一个大前提。除非所有的输入都为1，否则与非门的输出为1。如果电路处于未设置状态，那么Q = 0， Q’ = 1。这种状态是稳定并且自洽的，就正如下面的参数所示：

时钟和J都输入为0
因此左上角的NAND门输出为1
右上角的NAND门会接受两个为1的值的输入。
Q = 0

如果J的输入变成了1，时钟的输入也变成了1，那么就会发生下面这些事情：

左上角的NAND门就会接受两个为1的值的输入
所以它的输出为0
这就会导致右上角的NAND门以1的值输出Q
这样一来，右下角的NAND门就会接受两个为1的值的输入。
所以Q’的输出为0

JK触发器的真值表如下：

J	K	Clock	Q
0	0	↑	Q unchanged
1	0	↑	1
0	1	↑	0
1	1	↑	Q toggles

由此可见，当J和K的输入均为1的时候，Q与Q’的值会发生变换。

J可以被称作为“集合输入”。当J被设置为1，并K被设置为0的时候，它会导致输出Q也被设置为1。
K可以被叫做“清除输入”。当K被设置为1，J被设置为0的时候，会导致Q被清除（设置为0）。

JK与SR触发器不一样的是，每两个输入任意发生组合都会产生一个有效的输出，输入J和K的每一个组合都对Q和Q’产生明确定义的影响，而不像SR触发器一样，包含一个无效输出。这个特性导致JK触发器更加可靠，更有预测性，因为没有导致任何不确定因素或者未定义输出的情况出现。

布尔代数基础

本书的第四章讲过了如何使用逻辑命题来使用布尔运算符来组合成逻辑表达式。而布尔代数为编写简洁的逻辑表达式提供了方法，并提供了一种简化表达式的“公式”。

当使用一种代数形式的时候，理解它的含义是十分重要的。举个简单的例子，1+1可以被解释成很多不同的情况：

1 + 1 = 2
1 + 1 = 10
1 + 1 = 0
1 + 1 = 1

一式表示的是十进制算术，二式表示二进制算术，三式表示位算术，而四式可以表示布尔代数。这是因为在布尔代数中，1表示为TRUE，0表示为FALSE，而+可以表示或。因此，第四个计算式可以以下面这种形式表示出来：

TRUE OR TRUE is TRUE

布尔代数的表示有它的专有符号。比如说AND可以表示为∧，OR可以表示为∨。或者，A AND B可以写成A.B或者AB。在本章中，我们会使用这种类似“点乘”的AND表示方法。NOT的具体方式是在字母上面加一个横线。比如说NOT A可以表示为Ā。

在建立了基本的表示法之后，我们就需要考虑我们的计算规则了。
下表中的内容可以被叫做“法则”或者“定义式”：

Identity / Law	AND form	OR form
Identity	`1.A = A`	`0 + A = A`
Null	`0.A = 0`	`1 + A = 1`
Idempotent	`A.A = A`	`A + A = A`
Inverse	`A.Ā = 0`	`A + Ā = 1`
Commutative	`A.B = B.A`	`A + B = B + A`
Associative	`(A.B).C = A.(B.C)`	`(A + B) + C = A + (B + C)`
Distributive	`A + B.C = (A + B).(A + C)`	`A.(B + C) = A.B + A.C`
Absorption	`A.(A + B) = A`	`A + A.B = A`
De Morgan’s
Double Complement	`̿A = A`	`̿A = A`

打表格太费劲了，下次直接截图算了

下文中出现的Ā或者A'都代表NOT A

上面的表格展示了在布尔代数中的一系列恒等式。就拿德摩根定律举例子：德摩根定律允许我们交换FALSE和TRUE，或者交换AND和OR来将形式变换掉。

比如说这里有一个表达式：0.A = 0，读作”FALSE AND A is FALSE”。根据德摩根定律，我们可以将AND换成OR,并将所有元素取反。这样就能得到另一个相等的形式：1 + A = 1。总结一下，德摩根定律的变化法则是：

变换时交换TRUE和FALSE（0和1）
变换时交换AND和OR（.和+）

Example

来做个例题。

考虑一下这个表达式：A + Ā.B。我们如何化简它？

有意思的是，要化简这个式子，我们首先需要将式子先变得更复杂。
表中提到了有这样一个公式：A + A.B = A。可以通过这一点把原式中的A换掉，就变成了这样：

A + A.B + Ā.B

下一步我们暂时忽略A，然后对A.B + Ā.B使用交换律。步骤如下：

A.B + Ā.B = B.A + B.Ā = B.(A + Ā)

B.(A + Ā) = B.1

这一步应用了公式A + Ā = 1。

将结果带回原式，即可得到化简最终答案：A + B.1。

布尔代数运用

从真值表中创建布尔表达式

为特定问题创建布尔表达式，有时可以以真值表作为切入点。

直接上例子把：

Example

我们来举一个两个输出的AND门的例子。真值表如下所示：

A	B	Output
0	0	0
0	1	0
1	0	0
1	1	1

我们即将使用的”Sum of product”的方法是为真值表中的每一行创建一个最小项，输出为1。然后再对这些最小和求和，得到最终的布尔表达式。

最小项 (Minterm)是输出为1的特定组合。
在这个真值表里，只有一个最小项，那就是当A = 1或者B = 1时。我们将这个最小项记为A.B。
因为这个真值表只有一个最小项，所以说这个真值表的最终布尔表达式就是A.B。

但是如果不只有一个最小项怎么办？或者，表中不只有一个输出项怎么办？

下面是一个半加法器的真值表：

Input	Input	Output	Output
A	B	Sum	Carry
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

首先，我们对”Sum”这一列输出创建最小项：

第二行 (A = 0, B = 1)，最小项是Ā.B (NOT A AND B)
第三行 (A = 1, B = 0)，最小项是A.B' (A AND NOT B)

我们使用OR将所有的最小项连接在一起，这样的话就形成了Sum的布尔表达式：

Sum = A'.B + A.B'

同理可得，Carry = A.B

化简只能够将两列输出分别对应一个布尔表达式，所以最终的答案是：

Sum = A'.B + A.B'
Carry = A.B

逻辑电路的布尔代数式

Example

有时候我们需要通过一个逻辑电路来写出布尔代数式。那这个半加法器电路举例子：

我们跟着A和B两个输入项，来到了第一个NAND门。根据NAND的真值表：

A	B	Output
0	0	1
0	1	1
1	0	1
1	1	0

NAND真值表的前三行都为1，所以我们需要为此构建三个最小项。结合起来如下：

W = A'.B' + A'.B + A.B'

下一步，W的输出会去到三个NAND门里进行运算。我们这里以X门举例子。如果要画出X的真值表不是很容易，因此我们会考虑NAND门的本质计算方法，那就是先进行一个AND运算，然后将结果取反，也就是跟一个NOT运算。而AND的结果正式两个值的乘积。

我们先来进行AND运算：

A.(A'.B' + A'.B + A.B')

接着应用布尔分配式，也就是A.(B + C) = A.B + A.C：

A.A'.B' + A.A'.B + A.A.B'

A.A'的结果是0。在AND运算中，只要输入有0，那么输出必然为0。所以我们可以简化成：

A.A.B'

因为A.A = A，所以最后化简出来的式子就是：

A.B'

然而事情到这里还没有结束。因为我们只完成了NAND运算里的AND部分，接下来我们会执行NOT运算，也就是将上面的表达式求逆。根据德摩根定律 (元素取反，AND和OR交换)，我们可以得到原式的逆式：

A' + B

到这一步就可以出X的结果了。同样的流程也可以适用于Y的结果：

X = A' + B , Y = A + B'

这两位合起来，就是S的输出。同样，我们需要先执行AND运算，再通过德摩根定律执行NOT运算：

(A + B').(A' + B) (AND执行后)

S = A'.B + A.B' (NOT执行后)

C的结论，也可以通过这样的流程算出来了。

卡诺图 (Karnaugh map)

卡诺图 (Karnaugh map, K-map)是一种从真值表创建布尔代数表达式的方法。
K-map可以使这个过程比使用乘积之和来创建最小项要简单得多。如果应用正确，那么卡诺图就可以生成布尔代数表达式的最简单形式。

下表是一个OR逻辑门的真值表：

A	B	X
0	0	0
0	1	1
1	0	1
1	1	1

我们如果使用Sum of products方式来写出的布尔逻辑式如下:

X = A'.B + A.B' + A.B

但是我们如果使用卡诺图，就会比较简单了。下面的卡诺图表示了OR逻辑门：

在解读卡诺图时，我们需要遵循这些规则：

只考虑内容为1的单元格
在可能的情况下，尽可能将包含1的单元格以最大矩形囊括起来。而且矩形的面积必须是2，4，8等等。
每一个矩形可以重叠，但也只是在必要的情况下重叠。尽量做到不重叠矩形。
如果有单个1无法加入到任何矩形中，那么我们就把它自己视为一个组。

这些规则决定了图中的蓝色框框。
竖着看：B保持不变，但是A发生了变化，所以B被保留。
横着看：A保持不变，所以A被保留。
最终的布尔表达式就是这些保留值的和。，如下所示：

X = A + B

第二十章：系统软件

操作系统的目的

我们在第八章就提到了操作系统 (Operating System, OS)。本章会详细讨论一些有关于操作系统的更多细节。

我们可以先从系统使用方面的细节开始：

计算机系统需要一个程序，这个程序会在计算机启动时开始运行。我们将其称之为基本输入/输出系统(Basic input/output system, BIOS)。BIOS存储在ROM中。它作为一个引导程序，目标是在计算机开始运行时，将操作系统从硬盘引导至内存中，从而使其运行。
多程序设计 (Multi-programming)是一个操作系统提供的功能，允许多个程序同时加载到内存中。问题在于在一个特定时间内，只有一个程序能够使用CPU，所以其他程序需要保持准备状态，并在合适的实际轮流使用CPU。这样做是为了最大化利用CPU，因为若当前的程序的输入或输出任务完成后，CPU就可以立即切换到下一个程序。
分时 (Time-sharing)是另一个计算机系统中的概念，此概念赋予了多用户同时使用同一个计算机系统的机会。“分时”的概念是指每个用户可以获得使用CPU的一小段时间。具体来说，分时操作系统使用CPU调度和多程序设计，一次为一个用户提供共享计算机的一小部分。每个用户在内存中至少有一个独立的程序。当程序被加载到内存中并执行后，会在短时间内完成IO的处理或者其他处理。用户获得CPU关注的这一小部分时间叫做“时间片 (Time slice)”，“时间段 (Time slot)”或者“量子 (Quantum)”。一般来说它的时间长度约为10-100毫秒。
操作系统的目的可以由两个视角来进行解释，分别是内部视角 (Internal viewpoint)和外部视角 (External viewpoint)。内部视角主要关注操作系统如何组织其活动以最大化利用资源。这包括管理硬件资源，如CPU、内存和各种存储设备，以及软件资源，如运行进程、系统性能和安全性。操作系统需要保证这些资源被有效的利用，才能提供给用户最棒的性能。
外部视角主要关注操作系统为用户提供的设施和服务。这些服务包括UI，对运行应用程序的支持，文件管理，网络连接，用户身份验证等等的特性。从这个角度来看，操作系统的目标是为用户提供方便有效的功能和体验。

操作系统结构

操作系统的结构为资源管理和用户提供设施和功能提供了平台。它管理硬件资源，如CPU、内存和存储设备，以及软件资源，如运行进程、系统性能和安全性。它还为用户提供服务，如用户友好的界面、对运行应用程序的支持、文件管理、网络连接和安全特性。

操作系统的逻辑结构提供了两种运行模式 (Mode of operation)，分别是用户模式 (User mode)和内核模式 (Kernel mode)。具体解释如下：

用户模式：应用程序和部分操作系统的其中一种运行模式。在用户模式下，程序不能直接访问硬件或内存，必须使用系统调用来访问这些资源。
内核模式：也称为主管模式、系统模式或特权模式。在这种模式下，操作系统可以不受限制地访问所有硬件资源和内存。在内核模式下运行的代码可以直接与系统硬件交互，并且可以执行任何CPU指令。

提供这两种运行模式的操作系统部分是分开的。实际上，操作系统的内核是一直运行的，但操作系统的其余部分会以用户模式持续运行。
一种可能的实现方式是使用分层结构，如下图所示：

在这种结构中，用户通过用户界面(UI)来操作应用程序，而应用程序通过Utilities来对内核进行调用。为了维护系统的正常运作，每一个较高的层都需要较低的层来提供完整的服务。

虽然但是，上面的这一种结构在实际实践的过程中可能会碰到一些问题。所以说一般的方法是使用一个更加灵活的模块化结构。
该结构会在内核需要的时候调用不同的模块来处理工作。这种结构与微内核结构 (Micro-kernel structure)联系在一起。
简单的解释一下微内核结构：这种结构旨在使内核尽可能小而轻，因为它只提供必要的服务，比如进程调度和进程通信。而大多数非必要的服务，比如说设备驱动程序，会交给用户空间处理。这种设计可以使得操作系统比传统的单片内核更加模块化和灵活。

具体的结构如下图所示：

输入/输出系统 (I/O)

实际上，I/O系统不只是涉及到计算机与用户之间发生的输入和输出，同时也负责了程序运行时对存储设备的输入和输出。
下图展示出了I/O系统的结构：

上图中的总线结构说明，I/O设备和内存之间可以有一个数据传输选项，那就是设备驱动。如果对于大量数据来说，操作系统也可以确保在内存和I/O设备之间直接传输数据。

为了理解I/O的管理问题，我们需要考虑一下时间表。
不难理解，一秒钟对于计算机系统来说是一个很长的时间，因为CPU大多运行在GHz频率，所以说一秒钟内会存在超过一万亿个时钟周期。
下表给出了I/O的典型速度：

Device	Data rate	Time for transfer of 1 byte
Keyboard	10 Bps	0.1s
Screen	50 MBps	2 * 10^(-8) s
Disk	5 MBps	2 * 10^(-7) s

不难看出，这些设备的运行速度和CPU的运行速度简直不是一个数量级。所以说CPU就需要特意注意，在I/O设备交流数据时候，CPU不能进入空闲状态。
具体的管理方法会在下一节讨论：

进程调度

在系统运行过程中，为了提供最佳性能，我们需要考虑进程调度的问题。

CPU调度 (CPU Scheduling)是操作系统中的一个进程，它允许一个进程在另一个进程因为I/O资源不可用或者暂停（处于等待状态）的时候使用CPU，从而发挥出CPU的最佳性能。
CPU调度的目标是让系统更加高效和快速。每当CPU空闲时，操作系统必须在就绪的进程队列中选择一个进程来执行。

对于可以在操作系统上运行的程序来说，他们一开始是存储在磁盘上的。然而，用户可以将这些程序作为“作业 (job)”来提交给系统。
在操作系统的上下文中，“作业”是系统需要执行的工作单元。这可以是一个程序或一组相关的程序，以及关于它们如何运行的附加信息。
一份“作业”中可能包含：

实际需要执行的程序（代码）
程序的输入
有关程序所需的资源信息（如内存或者硬盘空间和地址）
有关如何处理输出的说明（比如说输出应该保存到哪里）

一旦作业被提交给系统，操作系统就有责任管理作业的执行。这包括将程序加载到内存中，调度程序的CPU时间，管理程序对其他系统资源的使用，以及处理程序的输出。

在实际的情况中，如果对于多CPU系统来说，调度就会有些更加麻烦了。不过这不是我们目前需要考虑的问题。

操作系统中，长期调度器或者高级调度程序可控制选择将存储在磁盘上的程序移入主内存。
如果内存过于拥挤，中期调度程序需要负责将某些程序从内存中取回磁盘。
当程序已经被记录至在内存中时，一个短期或低级调度程序会控制程序何时可以访问 CPU

长期调度器 (Long-term Scheduler)又称为准入调度器，负责控制新进程是否可以进入系统。它来决定哪些程序可以从作业池（包括所有进程的磁盘存储）中放入就绪队列，并加载到内存中。它可以确保选择某些合适的进程，以优化CPU的工作效率。

中期调度器 (Medium-term Scheduler)可以将进程暂时从主内存中移除，并在主内存空间比较紧张的时候将进程重新放回至磁盘中，使此进程变为“挂起”状态。我们将这个操作叫做换出 (Swapping out)或者滚出 (Rolling out)。中期调度器也可以评估当前主内存的情况，然后决定时候将挂起的进程重新加入至主内存中继续处理。

短期调度器 (Short-term Scheduler)也被称之为CPU调度器，它决定哪些已经就绪，并且存在在内存中的进程可以被CPU执行。短期调度器所做出的决定的频率要比其他两个调度器的频率要高得多，因为为了发挥最大性能，进程之间不允许出现任何中断。

以上三种调度器在操作系统中一起工作，可以有效地管理进程，从而确保每个进程都获得成功执行所需的必要资源和CPU时间。

High-level scheduler: makes decisions about which program stored on disk should be moved into memory
Low-level scheduler: makes decisions about which process stored in memory should have access to the CPU

所以说在运行程序时，涉及到的硬件之间的交流大概是这样子的：

进程状态

在第八章中，我们提到过：进程可以定义成“正在运行中的程序”。这个定义可以进一步加入程序第一次进入内存时的状态，来改进进程的定义。具体来说，当一个进程第一次进入到内存后，它的状态就可以叫做“新”。在这一阶段，我们可以在内存中创建一个叫做进程控制块 (Process control block, PCB)的东西，以便我们在进程执行的同时读取有关它的数据。
PCB是一个数据结构，操作系统可以用它来管理进程的信息。这些信息包括如下细节：

进程的状态：进程的当前状态（比如说是新，就绪，运行，挂起还是停止）
进程ID (PID)：这是进程的唯一标识码
程序计数器 (Program counter)：老朋友了。表示该进程要执行的下一条指令的地址。
CPU寄存器：该进程目前正在使用的CPU寄存器
CPU调度信息：调度进程所需的信息。可能包含优先级信息以及调度队列的指针
I/O信息：分配给进程的I/O设备，或者打开文件的列表等等

除了列出的条目，PCB中还存在更多的细节。这里就不展开说了。

一旦进程进入内存，并且设置好了PCB，进程的状态就可以随着它开始执行和与系统交互而改变。例如，当进程使用CPU的时候，进程的状态就可能从“就绪”变成“运行”。如果进程在等待用户的输入，那么它的状态就可能从“运行”变成“等待”。等等。

哦对了，一个进程可以拆分成不同的部分来执行，这些独立的部分叫做“线程 (Threads)”。

Process: a program in memory that has an associated control block
Process control block (PCB): a complex data structure containing all data relevant to the running of a process
Thread: part of a program which is handled as an individual process when being executed

进程处理的流程如下图所示：

中断

有些时候，中断是因为过早终止正在运行的进程而引起的。除此之外，中断的发生也有其他两种可能性：

进程由交替使用CPU和I/O的处理时段共同组成。然而I/O需要的时间太长，而且CPU不可能一直闲置等待 I/O 完成。因此当处于运行状态的进程发出需要进行 I/O 操作的系统调用，并不得不转入等待状态时，就会使用中断机制。
调度程序决定停止进程的原因有多种，稍后将在 “调度算法”标题下讨论。

不管发生中断的原因是什么，操作系统的内核都必须需要调用一个中断处理例程来尝试处理问题。首先，我们必须要将程序运行过程中，存储在寄存器中的当前值记录在进程控制块，也就是刚才说过的PCB中。这允许系统可以重新拾起这个进程，然后重新开始处理终端的进程。

调度算法

尽管长期调度器在选择将哪个程序加载到内存时需要做出决定，但这里我们只关注短期调度器或低级调度器的选项。

首先，调度算法可以是抢占式 (Preemptive)的或非抢占式 (Non-preemptive)的。抢占式算法可以停止进程，否则进程将继续不受干扰地运行。如果一个算法是抢占式的，那么它可能需要涉及进程优先级的考虑工作。所谓 “抢占式”，是指当进程的分配时间（或时间片）过期时，调度器可以强行将其从 CPU 中移除。这与非抢占式调度相反，在非抢占式调度中，进程一直运行到结束或被 I/O 阻塞为止。

这时候我们可以使用轮询算法 (Round-robin algorithm)来处理问题。这是一种抢占式算法，是操作系统中最简单的进程调度算法之一。在轮转调度中，每个进程都被分配了一个固定的时间片。如果这个进程所分配的时间片用完了，那么这个进程会被直接停止掉。

当然，进程如果以某些奇怪的方式停止掉以后，在某些情况下我们还会希望他们继续回来执行。因此，轮询算法还可以用来实现FIFO队列 (FIFO queue)，也就是“先进先出队列”来实现。进程被添加到队列的末尾，并按照到达的顺序分配 CPU。一旦某个进程轮到使用 CPU（即其时间片已过期），它就会被移到队列的后面。

基于优先级的调度算法则更为复杂。其中一个原因是，每次有新进程进入就绪队列或运行中的进程停止时，都需要重新评估进程的优先级。另一个原因是，无论使用什么方案来判断优先级，都需要进行一定的计算。可能的标准有：

进程执行的所需估计时间
进程执行剩余的时间
在就绪队列中已经花费的时间长度
进程是I/O绑定还是CPU绑定

显然，在上面列出的条目里，估计执行时间并非易事。
有些程序需要大量的输入输出，例如为员工打印工资条。此类进程的CPU使用很少，因此为其分配高优先级是有意义的，这样就可以进行少量的CPU使用。然后，在打印发生时，就可以将本流程切换到等待状态了。

内存管理

“内存管理”一词包含如下方面：

内存管理为操作系统内核提供受保护的内存空间
将程序加载到内存中需要做准备工作，而内存管理可以为程序本身、相关的过程和程序所需的数据定义内存地址
当运行在多程序设计的计算机上时，内存管理就相对来说比较复杂了。与存储在硬盘上的文件一样，进程在主内存中的存储也会产生碎片。这时，中期调度器可能需要将进程移出主内存，以缓解问题。
内存管理必须决定应该将多大一部分内存分配给共享内存的各个进程。

分区与段

当不同的进程同时加载到内存中时，早期的内存管理方法是对内存进行分区 (Partition)，它的目的是尽可能将整个进程加载到一个分区中。但是如果进程的大小小于分区大小，就会浪费内存。
后续出现的其中一个改进方法是“动态分区 (Dynamic partitioning)”，其中允许调整分区大小以匹配进程大小。然而每个分区一个进程的规则仍然存在。

具体来说，分区是一种将计算机内存划分为多个分区的方法，每个分区可容纳一个进程。其目的是将一个进程的全部内容加载到一个分区中。不过，如果进程的大小小于分区的大小，这种方法可能会造成浪费，导致分区内的内存闲置。

动态分区是对最初方法的改进。在动态分区中，我们允许调整分区的大小以匹配进程的大小。这有助于确保每个进程只使用其所需的内存，从而减少内存浪费。不过，每个分区只能容纳一个进程的规则仍然存在，这意味着每个分区一次只能容纳一个进程。

上述思想拓展出了另一个解决方案，那就是分段 (Segmentation)。分段是操作系统中的一种内存管理技术，它将计算机的主内存划分为大小可变的部分，称为段 (Segments)。其中的每个段可分配给一个进程。每个段的详细信息都存储在一个称为段表 (Segment table)的表格中。

分段被描述为动态分区思想的延伸，因为如果一个进程太大，那么它就无法容纳在一个分区中。所以将其划分为更小的段会是一个潜在的解决方案。然后，每个分段都可以加载到内存中的动态分区中。这种方法可以更高效地处理大型进程，因为每个分段都可以根据需要独立加载或卸载。这也有助于减少外部碎片，因为分段可以更整齐地嵌入可用内存空间。

分页与虚拟内存

在现代计算机系统中，我们一般使用分页 (Paging)的方法来管理内存。
分页是一种不需要连续分配物理内存的方案，它允许计算机的物理内存以不连续的方式记录。在分页中，进程会被划分为长度相等的部分，我们将这些部分称之为“页 (Page)”。

在操作系统内存管理中，内存可以被划分为固定长度的块，我们将其称为“帧 (Frames)”。
二级存储器(如硬盘)也可以划分为固定大小的块，通常称为“扇区 (Sectors)”或“集群 (Clusters)”，但在这里也可以称为“帧”。这些块可以保存从主内存换出的页。

操作系统会跟踪哪些帧是空闲的，哪些帧是正在使用的。当程序需要将一页加载到内存中时，操作系统会找到一个空闲帧，并将该页加载到其中。如果没有空闲帧，操作系统可能需要换出当前内存中的一页，为新页腾出空间。这种技术允许操作系统有效地利用内存和辅助存储，并支持虚拟内存等特性，其中程序可以比物理内存的总量更大。

将所有的页同时加载到内存中实际上是可行的（如果你的计算机内存够大）。
但即使这是可能的，通常情况下我们也不需要使用程序的所有部分。因此将某些页放回二级存储是必要的。

Segmentation: where a large process is divided into segments for loading into memory but the segments are not constrained to be the same size
Paging: where a large process is divided into pages which have to be the same size

这就引出了一个新的概念。

分页使用的一种特殊情况是，如果程序非常大，其所需的地址空间可能会大于内存大小。
这时候，我们就会需要用到分页技术支持的虚拟内存管理 (Virtual memory management)来解决这种情况了。

分页在执行过程中会要求CPU将地址传输到内存管理单元 (Memory management unit, MMU)，内存管理单元负责为每一个“页”分配地址。这个地址必须由两个部分组成，分别是“页码”加上该页起始处的“偏移量”。

内存管理单元负责将CPU中的逻辑地址转换为内存中的物理地址。它使用一种称为页表 (Page table)的数据结构来实现这一点，页表跟踪每个页在物理内存中的位置。地址的页码部分用作页表的索引。该索引处的页表项包含物理内存中该页的基址。然后将偏移量添加到该基址，以获得所需的确切物理内存位置。

有些抽象，所以我们来简单展示一个非常简化的页表：

图片的左侧展示了一个有48条指令的程序，不难看出，这些指令占用了3个页。反过来说，这3页占用了48条内存地址。

该系统的逻辑地址采用8个位存储。因为一个字节(8位)可以表示256个不同的值(从0到255)，而我们只使用16页，所以我们只需要前4位来表示页码(因为2^4 = 16)。剩下的4位用来表示页面内的偏移量。所以说在本系统中，逻辑地址被分为了两个部分，而他们的表示方式为：

四个最高位存储页码。
四个最低有效位将偏移量存储在页面中。

这使得系统可以通过其页码和偏移量快速有效地定位内存中的任何指令。

而图表的右半部分展示了各个页的物理内存地址。在继续之前，我们需要先强调，页帧 (Page frame)和帧之间没啥区别。

好的，我们继续。

需要注意的是，所使用的页帧不必在物理内存中相邻。这意味着程序的不同部分可以加载到不同的内存区域，而不必彼此相邻。这是分页和虚拟内存的优点之一，因为它允许更有效地使用内存。从图中我们可以得到，程序的前两个页已经被加载到内存中的页帧中。

图表中间的部分说明了此流程中页表的内容。在分页系统中，内存中的每个进程都有一个单独的页表。页表中每个页都有条目，而页码会作为索引。
表中的每个条目都包含一个表示该页当前是否在内存中的存在标志，我们叫它”Presence flag“，如图中第二列所示。
在这里显示的版本中，第三个条目显示了页帧号。或者，这可以记录页面框架中第一个项目的物理地址。它可以记录页面框架中第一个项目的物理地址。

在使用分页的时候，在最开始的开始，包含一个进程的一组页会存储在磁盘上。在进程切换到“就绪”状态时，其中的一个页或者多个页就会被加载到内存中。当进程被指派为“运行”状态时，进程就可以开始执行了。

然而，有些时候，进程可能会请求访问地址不在内存中的页，我们管这种情况叫做“缺页异常条件 (Page fault)”，或者更简单的说法——页面错误。
当出现页面错误时，操作系统需要将所需的页面从辅助存储(如硬盘)带到内存中。但是，如果没有可用的空闲内存，操作系统将需要选择一个当前加载的页面来替换。这就是页面替换算法 (Page replacement algorithm)发挥作用的地方。

有好几种页面替换算法，比如说：

先进先出 (First-in First-out, FIFO):这个简单的算法替换内存中最老的页面(即，首先加载的页面)。虽然易于实现，但如果仍然频繁访问旧页面，则此方法可能导致更高的页面错误率。
LRU (Least Recently Used):这个方法会替换最长时间未被访问的页面。它基于这样一种观察，即最近被大量使用的页面很可能在将来再次被大量使用。虽然这种方法通常执行得很好，但它需要跟踪每个页面最后访问的时间，所以这种方法带来的计算量就会变得更大一些。

虚拟内存可能会带来一些问题。可能出现的最严重的问题之一是磁盘抖动 (Disk thrashing)。当进程不断地需要在内存内和内存外交换页面时，就会发生这种情况。简单来说，虚拟存储管理中的抖动现象是指系统频繁地进行磁盘交换，导致系统的性能下降的现象。

比如说当系统内存不足时，操作系统会将一部分数据交换到磁盘中以释放内存。但是，当系统再次需要这些数据时，又需要将其从磁盘中加载回来，这就会产生磁盘交换。当系统的内存利用率接近饱和状态时，这种抖动现象会变得更加明显。因为系统需要频繁的交换数据，导致磁盘的负载变高，同时也降低了系统的响应速度和性能。为了避免这种情况的发生，我们可以增加系统内存，或者优化虚拟内存的存储策略来缓解问题。

Disk thrashing: when paging is being used and a repetitive state has been reached where loading one page causes a need for another page to be loaded almost immediately but the loading of this new page causes the same immediate need

提供给用户的操作系统设施

操作系统需要让用户来使用，所以它需要提供用户界面 (User interface, UI)。用户界面可以以命令行、图形显示或语音识别系统等方式来体现，但是请记住，用户界面的功能始终是允许用户与正在运行的程序进行交互。

当程序涉及到设备的使用时，操作系统提供设备驱动程序 (Device driver program)。

操作系统还必须提供一个文件系统 (File system)来存储数据和程序。在实际使用的时候，用户必须选择用户名并组织文件在文件夹中的结构，但是用户用不着管理磁盘上的物理数据是怎样存储的——因为这些是文件系统的活儿。

如果用户是程序员，则操作系统支持提供编程环境 (Programming environment)。这样，程序员就可以在操作系统的帮助下，即便在不熟悉处理器功能的情况下也能创建和运行程序。

当一个程序被运行时，我们可以将其认为是一个用户类型 (Type of user)，程序就像人类用户可能通过单击或键入来告诉计算机要做什么一样，程序使用一种称为系统调用 (System call)的东西向操作系统发出请求，这些类似于程序的点击或输入方式。例如，如果程序需要从文件中读取数据，它不会去查找文件本身。相反，它使用系统调用来要求操作系统执行此操作。然后操作系统接管，找到文件，并将数据提供给程序。
这样就引申出来了一个新的概念，叫做程序编程接口 (Application programming interface, API)。API就像操作系统为程序提供的选项菜单。菜单上的每个选项(每个API调用)都做一件特定的事情，比如在屏幕上创建一个图标。为了完成它的工作，API调用可能会使用一个或多个系统调用。

转译软件

同样是在第八章，我们概述了编译器和解释器的使用与特性。现在我们来深入介绍一下解释器的工作原理，并同时介绍解释器的工作原理。
编译器和解释器的编写工作是一项专业性极强的工作，通常情况下都由专家完成，而每个人的编写方式都各不相同。因此，本小节会探讨一些比较常见的思路。

编译器可以被分解成一个“前端”和“后端”。前端程序对代码进行分析，它检查代码的语法和语义，确保它遵循编程语言的规则并具有逻辑意义。如果没有错误，它会生成中间代码 (Intermediate code)。中间代码是一种完全捕获源代码含义(语义)的表示形式。

而编译器的“后端”将这些中间代码作为输入。然后，它从这个中间表示合成或创建目标代码。目标代码是计算机能够执行的最终机器码。

这样的一个分析-综合模型如下图所示：

先说好，我们假设上面的结构处理的源代码没有任何错误。接下来我们解释一下每一个步骤：

首先，源代码是逐行读取的，而且是重复逐行读取的。对于每一行来说，编译器都会生成它们对应的中间代码。上图还展示了解释器程序如何在前端进行分析过程。在这种情况下，一旦发现某一行源代码没有错误，并将其转换为中间代码，就会执行该行源代码。

前端分析阶段

如下图所示，我们可以将前端的处理阶段分成这样的四个部分：

词法分析
语法分析
语义分析
生成中间代码

编译器或解释器的输入数据是程序的源代码，我们叫它字符序列 (Sequence of characters)，而词素 (Lexeme)是这个序列中一个有意义的单个字符或字符集合。例如，词素可以是程序员定义的标识符（如变量名），也可以是编程语言预定义的关键字、运算符或符号。

第一步：词法分析：就是将源代码分解为这些单个词法的过程。
一种方法是首先删除源代码中的所有空白（空格、制表符、换行符）和注释。然后，检查源代码的每一行并识别每个词素。简单来说，词法分析就像是将一个句子分解成一个个单词，并了解每个单词在句子中的作用。

以伪代码的形式表述：Var Count : integer;，会被解释成一个存在五个词素的指令，分别是Var Count : integer ;。
同样，PercentMark[Count] := Score * 10会被解释成一个存在八个词素的指令，分别是PercentMark [ Count ] := Score * 10。

词法分析器现在必须对每个词素进行分类，以便将代码行标记化。例如，在第一个例子中，var和integer必须被识别为关键字，;被识别为标识符，:以及;必须被视为不同的词素。

对于每个识别到的标识符，我们都必须在符号表 (Symbol table)中创建一个条目。符号表中包含了每个标识符的属性，比如说数据类型，在何处被声明以及在何处被赋值。
符号表是编译器的一个重要的数据结构，虽然上面的的图显示了它只会在语法分析程序中使用，但是到了后期的编译阶段，我们同样也会继续使用它。
值得强调的是，因为大多数的编译器是多遍的，所以说符号表里面的内容是可以频繁的更新的。

Symbol table: a data structure in which each record contains the name and attributes of an identifier

也不是所有的内容都可以转换为标识符，所以我们需要另一个表来记录非标识符词法的内容。
总之，无论采用何种方案，词法分析的输出都是源代码的分词版本。文献中提到了用于表示标记的各种格式。

第二部：语法解析：也称之为解析，涉及对程序结构的分析。分析的结果会被记录为语法或者是解析树。
下面的图片展示了这个语句”y := 2 * x + 4“的解析树：

如果树被成功的解析了，那么程序会在+4之前先去将x乘以2。

第三步：语义分析：语义分析是为了确定代码的全部含义。为记录这些信息，我们构建了一棵带注释的抽象语法树。对于语法树中的标识符，会建立一套相关的属性，包括数据类型等。这些属性也记录在符号表中。

前端分析的最后阶段经常创建的中间代码的格式是三地址码。例如，下面的赋值语句有5个标识符，对应5个地址:

y := a + (b * c - d) / e

这一个赋值语句可以转换为以下4个语句，每个语句最多需要3个地址:

temp := b * c
temp := temp - d
temp := temp / e
y := a + temp

语言的语法表示

每种编程语言都有自己定义的语法。为了使语言可以正常使用，这个语法必须被程序员和编译器作者理解。

表示语法的一种方法是使用语法图 (Syntax diagram)，上图就是一个实例语法图。
比如，上面的语法图规定了这样一条语法规则：标识符必须以字母开头，而后面可以是无字符或者多个字母或数字的集合。

另一种方法是使用巴科斯范式 (Backus-Naur Form)来表示。下面是一些使用巴科斯范式的例子：

<Identifier>::=<Letter>|<Identifier><Letter>|<Identifier><Digit>
<Digit>::=0|1|2|3|4|5|6|7|8|9
<Letter>::=<UpperCaseLetter>|<LowerCaseLetter>
<UpperCaseLetter>::=A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
<LowerCaseLetter>::=a|b|c|d|e|f|g|h|i|j|K|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z

在巴科斯范式中，|为了分离单独的每一个选项，::=可以被描述成“被定义为”。
在上面的例子中，<Identifier>是使用递归的方式定义的。但如果我们要定义的内容无法抽象到这个级别，那么我们也可以使用列举的方式定义内容。

后端合成阶段

如果前端分析已经确定源代码存在语法错误，那么后端过程的唯一目标就是通过列表的形式来呈现这些错误。
每个发生的错误，都会有两个属性：错误的解释和在程序源代码中的位置。这些信息可以帮助到程序员，让他们更方便的调试软件。

但是如果在没有错误的情况下，主要的后端阶段是从中间代码生成机器代码，同时可能涉及代码优化。
优化的目的是创建一个高效的程序。有一种优化方式专注于优化原始源代码中固有的、已经传播到中间代码中的特性。
举个简单的例子，以下连续的赋值语句:

x := (a + b) * (a - b)
y := (a + 2 * b) * (a - b)

它的优化方式就可以是这样：

temp := (a - b)
x := (a + b) * temp
y := x + temp * b

表达式的求值

赋值语句通常是一个为标识符定义新值的代数表达式。
计算表达式时，首先要将代码中的中缀表示法转换为反向波兰表示法(Reverse Polish Notation, RPN)。
在 RPN 中，运算符（如 +、-、*、/）写在操作数的后面。例如，表达式 5 + 3 在 RPN 中会写成 5 3 +。这可以简化表达式的求值过程，因为一旦将表达式转换成 RPN，就可以从左到右地求值，而无需跟踪优先级规则或括号。

举一些例子:

Absolutely! Here are some examples of Reverse Polish Notation (RPN):

中缀表示法: 2 + 3
RPN: 2 3 +
中缀表示法: 4 * 5
RPN: 4 5 *
中缀表示法: (1 + 2) * 3
RPN: 1 2 + 3 *
中缀表示法: 2 + 3 * 4
RPN: 2 3 4 * +
中缀表示法: (7 - 2) / (5 + 3)
RPN: 7 2 - 5 3 + /

计算RPN表达式

我们可以使用栈来计算RPN表达式。
让我们下面这个RPN表达式的执行，其中x的值为3,y的值为4:

x 2 * y 3 * + 6 /

这里遵循的规则是依次将值添加到栈中。
如果RPN表达式中的下一项是操作符，则进程中断。这将导致前两个元素从栈中弹出。
随后需要使用运算符从这两个值创建一个新值，并将新值添加到栈中，然后该过程继续进行。
下图给出了栈的连续内容，指出了何时使用了操作符。当弹出两个值时，栈的中间状态不会显示。

如果使用的是第6章讨论的具有有限指令集的简单处理器，那么RPN的使用就没有什么价值。
因为现代处理器的指令集中会有处理堆栈操作的指令，因此编译器可以将表达式转换为RPN，因为它知道将表达式转换为机器码可以利用这些内容并允许在程序执行中进行堆栈处理。

第二十一章：数据安全

加密原理

在计算机系统中，加密可以用来作为存储数据的常规方法。不过，本章讨论的加密的重点是在数据通过网络的传输时而使用。

本章会主要探讨下面这三个问题：

加密算法是不是足够稳健，以至于加密数据不会对未经授权的第三方应用（或者任何个体）解密？
如何确认加密数据时用的密钥，是保密的呢？
通信的接收者如何知道是谁发送了加密通信？

加密的流程如下图所示：

首先，数据以明文 (Plaintext)的形式进入加密环节。首先，明文会使用密钥 (Key)进行加密 (Encryption)步骤。
明文经过加密后，就会变成密文 (Ciphertext)，随后密文就会被发送到它传输的目的地。
当另一台计算机收到了密文的时候，它也可以使用密钥来对密文进行解密 (Decryption)来还原原本的明文。

Plaintext: data before encryption
Ciphertext: the result of applying an encryption algorithm to data

安全问题

在进行加密传输的时候，下面这些安全问题确实是值得一提的：

保密性 (Confidentiality)：确保只有接收方能解密密文，而其他未经授权的终端无法解密密文
真实性 (Authenticity)：接收方能够确定到底是谁发送了密文
完整性 (Integrity)：密文在传输过程中无法发生修改
不可否认性 (Non-repudiation)：发送方和接收方都不能否认参与了数据的传输
可用性 (Availability)：不应该发生任何事情来阻止接收方接收传输

而在本章的讨论中，我们只考虑前三点：保密性，真实性和完整性。
由于讯息在传送过程中可能会被截取，而内容可能会被未获授权的人士阅读，因此我们需要考虑保密性问题。
同时对完整性的关注反映了这样一个事实:传输可能被故意干扰，但也可能在传输过程中意外损坏数据。

加密方法

对于加密算法来说，首先它不能被保密，这意味着加密算法必须在公共领域公开。而且，加密密钥必须是保密的。
加密一般来说有两种常用的策略，一种是对称密钥加密 (Symmetric key encryption)，另一种是非对称密钥加密 (Asymmetric key encryption)，也称为公钥加密 (Public key encryption)。

Symmetric key encryption: one private key is held by both sender and receiver and is used for both encryption and decryption
Asymmetric key encryption: there is a public key and a private key one of which is used for encryption and the other for decryption

在对称密钥加密中，我们自始至终只会用到一个密钥，而这个密钥只有消息的发送端和接收端知道。“只会用到一个密钥”的意思是：发送方会使用这个密钥加密信息，而接收端同时也会使用这个密钥来解密信息。

而对称密钥加密就不是这种方式了，因为加密和解密的密钥不同，所以密钥的传递就会变成一个大问题。
发送方需要密钥来加密，但如何将密钥安全地传递给接收方以允许解密呢？
在非对称密钥加密中，使用两个不同的密钥，一个用于加密，另一个用于解密。两个密钥中只有一个是保密的。所以说如果我们要使用非对称密钥加密，那么发送端手中会有两个密钥，其中一个是公钥，而且这个公钥可以被发送给任何想要参与通信的人，而另一个密钥是永远不会发送给任何人的秘密私钥。如果某人(发送方)想要向密钥持有者(接收方)发送安全消息，他们使用接收方的公钥对消息进行加密。此过程将原始消息(明文)转换为不可读的格式(密文)。一旦接收方获得密文，他们可以使用他们的私钥将其解密回原始消息。因为只有接收方可以访问他们的私钥，所以他们是唯一可以解密和读取消息的人。公钥可以被多人共享。这意味着任何数量的人都可以向接收者发送安全消息，并且只有接收者能够解密和读取这些消息。

需要注意以下两点：

如果两个人需要双向通信，那么通信的双方都需要一个私钥，并且必须将匹配的公钥发送给另一个人。
要确保传输被截获和消息被提取时的机密性，必须满足两个要求：加密算法必须复杂，而且用于定义密钥的位数必须很大（防止暴力穷举）。

数字签名与电子证书

上面提到的非对称加密，是一种使用两个不同密钥的加密类型，包括用于加密的公钥和用于解密的私钥，反之亦然。每一个个体都可以用他们的私钥加密消息。然后可以将此加密消息发送给拥有相应公钥的收件人。同时，接收方可以使用公钥将接收到的密文解密回原始消息。但因为公钥的公开性，这就导致了非对称加密不保证数据的完全保密，因为任何人都可能获得公开密钥，从而可以解密信息。

不过，这种方法可用来验证发件人是谁。由于只有发件人才拥有私人密钥，而公钥只对特定的私人密钥起作用，如果收件人发现解密成功，就意味着该信息一定是用相应的私人密钥加密的。因此，它验证了信息确实是由私钥持有者发送的。这就是所谓的数字签名。

数字签名(Digital Signature)是一种特定类型的电子签名，它要求签名者使用基于证书的数字ID来验证其身份。数字证书通常由独立的证书颁发机构(CA)颁发，CA在颁发证书之前验证签名者的身份。

现在来看，电子签名是使用非对称加密算法的公钥和私钥实现的：发送方使用他们的私钥加密消息。这就像用只有寄件人才有的私人印章来封一封信一样。而接收方拥有相应的公钥，可以对消息进行解密。这就像用合适的工具打开密封的信。如果解密成功，它验证消息确实是由私钥的持有者发送的，因为只有特定的私钥可以被用来加密消息，并且可以被相应的公钥解密。这就像一个数字签名，提供发送者身份的证明。

但是使用这种数字签名的缺点在于：它与整个消息的加密相关联。这可能导致计算数字签名会需要强大的算力支持，因为牵扯到所有数据来计算数字签名需要密集计算。

所以另一种选择是使用加密哈希函数。这是一个特殊的函数，它接受一个输入(或’消息’)并返回一个固定大小的字节字符串。对于每个唯一的输入，输出都是唯一的——即使输入中的一个小变化也会产生如此巨大的哈希值输出变化，以至于新的哈希值看起来与旧的哈希值不相关。
随后，发送方将哈希函数应用于他们的消息，从而创建一个“摘要 (Digest)”。此摘要是表示消息内容的唯一数字。发送方然后使用他们的私钥加密该摘要。加密后的摘要作为数字签名。上图展示了通过摘要生成电子签名的流程。

在信息发送阶段，原始消息(明文)和加密摘要(数字签名)然后一起发送，通常将摘要作为单独的文件附加到消息中。由于摘要比整个消息小得多，因此加密和传输它比加密整个消息要快得多。在一些网站下载内容时，它们可能会同时提供文件的SHA-256摘要。通过比对自己下载的文件的SHA-256与官网的进行比较，可以知道用户下载的文件是否在下载过程中发生了损坏。

上图描述了信息在接收端发生的处理过程。

刚才谈到SHA-256的时候说过，接收方使用与发送方使用相同的公共单向哈希函数从接收到的消息中创建摘要。这将产生一个唯一的数字，表示接收到的消息的内容。随后，接收方使用发送方的公钥解密随消息一起发送的原始摘要的加密版本。接收方将从收到的消息中计算出的摘要与解密后的原始摘要进行比较。如果它们匹配，则验证消息在传输过程中没有被篡改，并确认发送方的真实性(因为只有发送方的私钥才能以一种可以由相应的公钥解密的方式加密原始摘要)。

然而，真实性只向接收者确认消息是由向他们发送公钥的人发送的，但是它没有考虑这样一个事实，即某人可能会创建公钥并假装是其他人。为了克服这一限制，需要一种更严格的方式来确保身份验证。这就是证书颁发机构 (Certification Authority, CA)的用武之地。
CA是一个受信任的第三方，它验证实体(如人、计算机或组织)的身份，并通过数字证书将它们绑定到公钥。

而CA是一个更大的系统的一部分，被称为公钥基础设施 (Public Key Infrastructure, PKI)，它管理密钥和证书，并在不受信任的网络(如互联网)上实现安全通信。PKI确保每个公钥对于其持有者是唯一的，并提供查找、撤销和更新证书的方法。

根据上图，我们可以来探讨一下从CA获取安全证书的过程：

联系CA：想要接收安全消息的个体会联系本地CA来获取一对公私钥
身份确认：CA需要确认个体的身份，这可能涉及多种身份验证方法
提供公钥：当身份确认通过后，个体需要将他们的公钥提供给CA
创建数字证书：提交后，CA会创建一个数字证书，并将该个体的公钥写入该文档。此证书作为一种形式的身份证的公钥
添加数字签名：随后CA会使用自己的私钥加密数字证书，并对其添加数字签名
接收数字证书：然后CA将数字证书发送给该个体
发布数字证书：该个体就可以将数字证书发布在网站或其他可访问的位置。现在，任何想要发送加密消息给该个体的人都可以在数字证书中找到他们的认证公钥

这个过程可以确保当有人使用该个体的公钥向他们发送加密消息时，他们可以确信该密钥确实属于该个体，并且没有被篡改。

对称密钥加密

多年来，数据加密标准(DES)一直是对称密钥加密的正常选择。当DES的弱点成为一个问题时，Triple DES取代了它。
2001年，高级加密标准(AES)作为一种优越的方法被引入。出于教育目的，我们在本章之探讨相对较简单的简化数据加密标准 (Simplified DES, S-DES)，以便更好地理解在加密中执行的各种操作。

S-DES实际上是一种分组密码，这意味着它以比特为单位对数据进行加密。在S-DES中，它操作以8位构成的“块”。
这个过程从一个10位的密钥开始。S-DES的第一步是从原来的10位密钥创建两个8位密钥。这是通过一系列的置换(位的重新排序)和移位来实现的。
简单简述一下步骤：

置换 (Permutation)：10位的密钥首先根据预定义的置换规则进行置换(重排)
拆分 (Splitting)：置换后的内容被拆分为两部分
移位 (Shifts)：每一半都要经历一系列的左移
二次置换 (Second permutation)：移位后，将两部分合并，再进行一次置换来生成第一个8位的密钥
更多的移位：如题，更多的移位
最终置换 (Final permutation)：在经过这些移位步骤后，将这两部分再次组合，并进行另一次置换以生成第二个8位密钥

举一个置换过程例子吧：

我们有一个10为的密钥：0101010101，而且定义好的置换规则为35274101986
将这种排列规则应用于密钥意味着按照规则指定的位置重新排列键中的位：
在这种置换规则的情况下，表示：置换后的密钥的第一个位置是原始密钥的第3位，第二个位置是原始密钥的第5位，以此类推。
之后的置换过程就是这样继续循环下去了。

公钥加密方法

RSA (Rivest-Shamir-Adleman)是一种常用的公钥加密方法，这个名字是以三位发明者的名字命名的。
RSA中的密钥生成过程包括一系列利用素数和模运算的数学特性的步骤。下面是这种加密算法的详细说明：

选择质数：首先选择两个非常大的指数，我们把它们记作p和q。这两个数字是保密的，其他设备都不会知道这两个质数。
计算n：计算p * q，记作n。该值将会用作公钥和私钥的一部分。
计算φ(n)：计算(p - 1) * (q - 1)，我们一般将这个值记作φ(n)。
选择e：再选择一个质数e，使其小于φ(n)并这个数不是φ(n)的因数。我们一般选择65537这个数字，因为它在计算的时候比较好算。
求d：现在我们需要求解另一个数字d，满足(d * e) % φ(n) = 1，也就是它们俩相除余数为1。
得出公钥：然后，公钥就得出来了：(n,e)。公钥是对所有人公开可用的。
得出私钥：同时我们也可以得出私钥：(n,d)。私钥是保密的，不对外公开的。

RSA的安全性基于这样一个数学原理：虽然两个大质数相乘得到n相对容易，但反过来得出两个质数是几乎不可能的。

因为RSA的加密是基于数字的，所以在进行加密之前，我们需要将信息转换为数字的形式。这通常使用ASCII或Unicode等标准编码方案完成。
一旦文本被转换成数字x，就会使用公钥(n,e)对其进行加密，以生成加密的数字y。
加密使用公式y = (x^e) mod n完成。
公式的意思是：x被取e的幂，然后当结果除以n时的余数得到y。

类似的过程耶同样用于用于解密，但它解密过程设计私钥(n,d)，而不是公钥。
使用公式x = (y^d) mod n，可以从加密的数字y中恢复原始数字x。

像RSA这样的公钥加密比对称密钥加密更安全，因为它不需要安全交换密钥。
但是，公钥加密中使用的算法不如对称密钥加密中使用的算法快。因此，通常使用公钥加密来安全地传递密钥，然后将密钥用于更快的对称密钥加密。

SSL 和 TLS

当访问一个网站时，用户通常有两个主要的关注点。
首先，用户他们希望确保网站是官方的网站，而不是看起来很像官方的钓鱼或者诈骗网站。
其次，用户在有需求的时候（比如网购时），希望能够安全地传输敏感的个人数据。而SSL协议的创建是为了解决这些问题。

安全套接字层 (Secure Socket Layer, SSL)是为网络通信提供安全及数据完整性的一种安全协议。如今被广泛使用，如网页，电子邮件，互联网传真，即时消息和语音在IP电话（VoIP）。其中网站是通过使用TLS来保护WEB浏览器与服务器之间的通信安全。
它为基于客户端-服务器的应用程序提供了一个安全层，确保在用户浏览器(客户端)和网站服务器之间传输的数据是加密和安全的。

在网络中，“套接字 (Socket)”是IP地址和端口号的组合。传输控制协议(TCP)使用端口号为特定的应用程序提供服务。如果没有SSL这样的安全协议，TCP将使用此端口号直接与应用程序交互。
但是当有SSL时，它会作为传输层中的TCP和网络协议栈的应用层之间的附加层。这意味着从应用程序传递到TCP的数据要经过SSL，反之亦然。当数据被发送时，会在SSL中进行加密；在接收时会进行解密。
所以启用SSL后，应用协议HTTP(超文本传输协议)会变成变成HTTPS (HTTP Secure)。这表明客户端和服务器之间的通信是加密和安全的。

需要注意下面这些有关于SSL的内容：

SSL通常被称为一个协议，但它实际上是一组协议套件
SSL协议处理数据传输的格式，确保数据被正确打包以进行传输
SSL协议负责建立安全连接。SSL为了达成目的会涉及以下几个步骤，包括对服务器的身份验证和对加密算法和密钥的协商
SSL的操作不需要用户操作即可发生。它集成到网络协议栈中，并在需要安全连接时自动操作
SSL实现的起点是通过TCP (Transport Control Protocol，传输控制协议)在客户端和服务器之间建立的连接
客户端浏览器需要调用SSL套件中的握手协议来确保安全连接。这涉及几个步骤：
- 首先握手协议要求服务器提供SSL证书，即验证服务器身份的数字证书
- 随后，服务器将此SSL证书连同其公钥一起发送
- 最后，浏览器使用此公钥加密密钥，该密钥将在数据传输会话期间作为对称密钥加密的一次性会话密钥

SSL最初是一个专有协议，但后来被互联网工程任务组(Internet Engineering Task Force, IETF)接管，形成了一个标准化版本。
当IETF意识到需要一个改进的版本时，他们决定使用一个新的名称。因此，传输层安全 (Transport Layer Security, TLS)作为SSL的升级版、更安全的版本被引入。
尽管SSL存在一些安全问题，但它现在仍然被广泛使用。现在，当你听说“SSL证书”时，它通常意味着SSL/TLS证书。
SSL现在多与TLS协议一起用于安全通信，所以在今天的实践中，即使人们提到“SSL”，TLS也很有可能被使用。

量子密码

不开玩笑，这下真的需要讨论一下量子力学了：

量子力学提供了支配最小尺度粒子行为的基本物理定律。光子 (Photons)是传输光的粒子。它们表现出波状的行为，这意味着每个光子似乎在垂直于其传播方向的特定方向上振动。
每个光子振动的方向称为偏振度 (Polarization)。在图表中，偏振度通常用双端箭头表示。
而我们在计算机中，可以使用特定的偏振来创建光子来表示比特的值，而比特是计算中信息的基本单位。如果我们允许四种极化状态的可能性，我们可以用两种不同的方式表示一个二进制值(0或1)。这可能被用于增加每个光子中可编码的信息量，或在量子通信或计算系统中提供冗余或错误纠正。

具体的编码方式如下图所示：

因此，该方案可用于使发送方和接收方创建由若干比特组成的“秘密代码”。下表详细描述了量子密钥的分发过程：

被发送的比特值：发送方（我们一般称之为Alice），选择一个随机的比特序列进行发送。上图第一行表示了一段被选中的比特值，它是1 0 1 1 0 0 0 1 0 1。
发送方的极化基：随后，Alice会为每一个比特位选择一个随机的极化基。在这个表格中，+表示垂直和水平偏振，×表示对角偏振。
接收方的极化基：接收方（我们一般称之为Bob），会在Alice不知情的情况下为每一个位选择一个随机的极化基。
传输并揭示极化基：随后数据会被传输。最后，Alice会告诉Bob她使用的每一个位的极化基。
确认位值：Bob会将从Alice那里拿到的极化基信息与自己选择的极化基相匹配。通过判定他们之间的匹配情况，就可以反映出哪些位是这两位之间的秘密代码。

在上图的例子中，最后的秘密代码1001就是通过这样的方式得到的。
加密的过程利用了量子力学的原理来确保安全性。如果窃听者试图截获并测量传输过程中的量子态，由于海森堡测不准原理，会干扰量子态并引入可检测误差。

第二十二章：人工智能 (AI)

综述

定义“人工智能”是什么并不容易。
一个关键问题是智能的定义。例如，你可能会说一个人做心算需要智力，比如43 × 13。不过，你可以使用计算器来得到答案，但不会将计算器描述为具有人工智能。这意味着像这样的定义:

“人工智能涉及智能行为的自动化。”

并不完全令人信服。

人们一致认为人工智能是计算机科学的一部分。很明显，这个主题有许多不同的子节，本章将讨论其中一些。结论是一个模糊的定义是最好的。例如:

Artificial Intelligence is concerned with “how to make computers do things at which, at the moment, people are better.”
(E. Rich. Artificial Intelligence. McGraw-Hill, 1983)

我个人认为人工智能行业在近年来发展十分迅速，迭代速度十分离谱。所以说本章可能会出现一些过时的理论，但是也没办法，毕竟我们需要考试嘛。

人工智能与图表

我们在AI这一块使用的图标大多是像下面这种类型的：

这样的图片由节点和连接线组成。每一条线连接两个节点，连接线上面存在一个相关联的标签，这个标签是一个数值。

这样的图可以用来表示各种场景。一种常见的表示方法是，节点表示位置，边缘标签表示这些位置之间的距离。只有当节点对之间存在可直接移动的路径时，图中才包含连接线。例如，这种图可以找到两个不相邻的节点之间的最短路径。

我们可以通过考虑所有可能的路线并计算每条路线的总距离，利用我们的模型来找到节点A和节点D之间的最短路线:

A → B → C → D 40 + 10 + 40 = 90

A → B → F → E → D 40 + 15 + 20 + 5 = 80

A → F → E → D 60 + 20 + 5 = 85

A → B → B → C → D 60 + 15 + 10 + 40 = 125

不难看出，第二种方案是路径最短的方案。
如果我们需要在一个包含100个节点的图像里面寻找最短距离方案，会把我们数累死。好在现在已经有了好用的人工智能算法来解决这个问题。

狄克斯特拉算法

狄克斯特拉算法是一种寻找加权图中节点之间最短路径的方法。该算法可用于寻找从图中单个节点到所有其他节点的最短路径，从而生成最短路径树。它还可以用于查找从单个节点到单个目标节点的最短路径，在确定到目标节点的最短路径后停止算法。

狄克斯特拉算法的准备步骤如下：

标记路径开始的原点：首先标记一个我们开始的位置。
创建ShortestPath变量：这个变量将会存储从源节点到目标节点的最短路径。随着我们对于整个树的深入探索，变量内部的值也会发生改变。一开始，这个变量中的值为零，因为我么还没有探索任何可能的路径。
创建RemainingNodes变量：我们将所有的节点放入这个变量中，包括源节点，我们将源节点记作S。这个集合包含了我们目前为止还没有探索过的节点。最初，这个变量仅包含图像中的所有节点，包括源节点。
创建record：接下来我们需要创建一个record，其中包含以下数据类型：
- 节点名称 (Node name)
- 从源节点到此节点的距离 (Calculated distance to the node from the source node)
- 到达此节点路由中的顺序 (Sequence of node in the route to the node)
这些record用来跟踪源节点到每个节点的最佳已知距离，以及到达这个节点的路径。
源节点距离值为0：将源节点的距离值设为0（因为源节点到自身的距离总是为0）。
其他点距离设为无穷大：我们需要将其他的点的距离设为无穷大，因为我们在算法的开始不知道源节点到其他节点的距离。为了保证正常的计算，只能使得距离值大于可能计算出来的值。

接下来算法会步入一个循环，这就是狄克斯特拉算法能够寻找最短路径的核心：

从RemainingNodes中选择距离最小的节点：RemainingNodes变量中存储的是所有的未探索的节点。这一步要求程序再RemainingNodes变量中选择一个距离当前点距离最小的节点。
节点移动至ShortestPath变量中：这一步过后，我们就已经探索了该点的距离了。这时候就应该将这个节点移动到ShortestPath变量中。
最短距离的判定与计算：我们通过被链接的两个节点的最短路径上的标签的值来计算距离。所有的标签值相加既是最新的最短距离，然后将此值更新，替换当前存储的最短距离值。

这时，我们就已经找出了通往每个节点的最短路径。

上图展示了狄克斯特拉算法的更多细节信息。
当节点仍在RemainingNodes中时，会以红色显示。在每个阶段，节点 N 都以黑色表示。当节点已被移动到最短路径集而无法再更改时，距离和路径数据将以灰色显示。

**A* 算法**

狄克斯特拉的算法的目的是找到某一个节点通向每一个节点的最短路径。而在实际应用中，我们经常需要的是寻找两点之间的最短路径，而不是寻找某个节点到所有点的最短路径。

这种情况下，我们可以对狄克斯特拉算法进行一些简单的修改，使得算法只求解两个特定节点之间的最短路径。可能达成这一目标的一种方法是使用基于启发式的算法，如A*(发音为“a -star”)。不过，在查找单个最短路径时，A*可能比Dijkstra更有效，但如果需要查找从一个节点到许多其他节点的最短路径，Dijkstra可能仍然更有效，因为它不依赖于特定于目标的启发式算法。

A*算法的有效性在很大程度上取决于所使用的启发式算法的质量。一个质量低下的的启发式算法可能导致寻找的路径十分低效，甚至导致算法无法找到一条路径。

将狄克斯特拉算法经过下方的简单修改，就可以实现A*算法的内容和功能：

将连接两个节点的边的标签值与已存储的 N 的距离值相加，计算出新的距离值：这一步与狄克斯特拉算法相似，都是用根据节点N的路径的不断探索来更新已知的最佳距离。
计算 N 与目的地节点距离的估计值，并将其与新的距离值相加：这一步与狄克斯特拉算法就不一样了。A*算法使用启发性函数来估算节点到目的地的剩余距离，然后根据剩余距离的大小分别对待不同的节点。而不是对所有的未探索节点一视同仁。这个估计距离会与已知距离相加，然后总值较低的节点会被优先探索。

我们需要在选择A*算法的启发式函数时格外注意。启发式算法应该是对于实际剩余距离的预估，当选择这个函数时，它必须保证任何估计值都将小于实际值。如果这个预估值过高，就会导致A*算法探索更多的节点，从而导致A*算法找不到正确的路径。一般来说，如果在二维平面上寻找最短距离，那么这个启发式算法的一般选择是曼哈顿距离，或距离目的地的欧氏距离。

为了简单理解A*算法，这里举一个在二维平面上寻路的简单例子：

图中展示了7个城镇，每个城镇的名字都使用A-G进行编号。之所以使用这样平面的形式来呈现城镇的位置，那是因为它是通过定义每个城镇位置的一对x,y坐标绘制的，而这正是启发函数能得以应用的基础。

下面是这7个城镇的坐标：

A	B	C	D	E	F	G
(40, 20)	(30, 30)	(80, 35)	(130, 30)	(120, 20)	(45, 5)	(100, 30)

毕达哥拉斯定理，也就是勾股定理可以用来计算两个位置之间的直接距离，可以写作Δx方加Δy方，然后开个根。

而使用这种方法计算的距离，一定会小于等于我们要实际走的路程。这个实际问题画成图像就像下图：

首先事先说明，A*算法实际上有很多的实现方案。我们在这里使用的A*算法是CIE的某种神奇的独创方法。。。用文字表示出来是这样的：

创建三个列表：初始列表、开放列表和封闭列表：这些列表用来记录我们尚未探索的节点（initial）、正在探索的节点（open）和已经探索完毕的节点（closed）。
为图中的每个节点在初始列表中插入一条空记录：这样我们就建立了包含图中所有节点的initial列表。
在initial列表的每条记录中存储节点的 x 和 y 坐标：这将用于计算节点之间的距离。
在initial列表的每条记录中，将旅行距离值初始化为 0。因为在算法的开始，我们还没有走过任何距离。
创建一个查询表，为每对有直接连接道路的节点建立一个条目。该表会用于快速查找直接相连的节点之间的距离。
为表中的每对节点存储沿该道路的行驶距离。这会用于计算节点之间的距离。
确定旅行的目标节点，也就是我们的目的地。
确定旅行的起始节点，并将该节点的记录复制到开放列表中。
从initial列表中删除初始节点的记录：我们将起始节点从initial移到open，是因为我们即将开始探索它。
现在递归地应用下面的算法，直到所有的可能性都被检查过：
- 对于与当前节点（父节点）相邻的每个节点，我们都要计算一个新的距离值，相应地更新我们的记录，并根据需要在列表之间移动节点。
- 我们将继续这个过程，直到探索完所有可能的路径或找到目标。
如果目标节点在打开的列表中，则仅对该节点执行以下操作：计算实际距离，然后更新我们的记录。
- 我们计算实际距离，更新相应记录，并根据需要在列表之间移动节点。
- 如果没有更多节点需要探索（open列表为空），我们会倒回去检查closed列表中没有包含在之前路径序列中的节点。
- 如果一条未探索的路径可能比我们当前的最佳路径短，我们就把它的起始节点移回open，然后继续探索。

以上的过程会一直持续到我们找到通往目标的最短路径或确定不存在这样的路径为止。

机器学习

机器学习的特性可以概括为:

基于计算机的系统有一个或多个需要执行的任务
知识是通过执行任务的经验获得的
通过这些经验和获得的知识，可以改善未来任务的表现。

从经验中学习的能力是智能的体现。因此，机器学习是人工智能范畴内众多方法中的一种。有许多方法可以描述如何进行学习。这里将讨论其中三种：

无监督学习 (Unsupervised learning)

在无监督学习 (Unsupervised learning)中，系统必须根据自己执行任务的经验得出结论。为此，需要有能够对所获知识进行组织或分类的算法。
例如，可以根据层次框架确定 “概念集群 (Conceptual clusters)“。在这种方法中，知识最初都被置于树形结构的根部。然后，根据知识的属性，将选定的群组移入树形结构的分支中。

如今，无监督学习已成为一种主流活动。访问海量数据库的强大计算机系统可以被用来通过学习以往的数据与记录，从而学习对未来做出决策。
我们在互联网上的活动都会被记录和存储。这些存储的数据很可能会被用来做出决策，而这些决策可以决定在未来使用互联网时服务商向我们推荐哪些产品或服务。

监督学习 (Supervised learning)

在监督学习中，系统被输入相关的分类知识。例如，我们可能正在开发一个人工智能程序，用于批改试卷。在监督学习中，试题答案可以连同每道题的分数或分类评语一起提供。这种对模型数据的分类提供就是监督学习的典型标志。

专家系统是一种计算机系统，可模拟人类专家在特定领域的决策能力。它旨在通过知识体系的推理来解决复杂的问题。
在这种情况下，监督学习指的是人类专家分析数据样本并提供结论的过程。然后将这些数据样本和结论输入专家系统的知识库。
专家系统的有效性可以通过人类专家提供样本数据并检查系统结论的准确性来检验。如果效果不佳，则向系统输入更多数据和结论，以提高其性能。
虽然专家系统是人工智能的一个例子，但它并不是机器学习的一个例子。这是因为人们并不期望系统在无人帮助的情况下提高性能。相比之下，机器学习系统的设计目的是自动学习和改进经验，而无需明确编程。

强化学习 (Reinforcement learning)

强化学习具有一些类似于无监督学习的特征，而另一些特征则类似于有监督学习。这种方法有自己特定的词汇。下面的语句就是用这些词汇来描述强化学习算法如何工作的。

Agent：Agent是学习如何行为的实体（如机器人或软件应用程序）。它通过采取行动、接收反馈并从中学习来与环境互动。
Environment：这是Agent运行的环境或空间。它可以是物理环境（如机器人的迷宫），也可以是虚拟环境（如下棋程序的棋盘）。
States：这是Agent在环境中可能遇到的不同条件或情况。
Action：这是Agent在与环境交互时每一步所做的事情。例如，在一盘棋中，行动可以是移动一个棋子。
Policy：这是Agent根据其当前状态决定其行动的策略。换句话说，这是Agent的行为函数。
Reward：这是Agent在采取行动后得到的反馈。它是衡量该行动在实现总体目标方面的好坏程度。
Exploitation vs Exploration：这是Agent在决定下一步行动时可以使用的两种策略。开发 (Exploitation)是指利用已知信息，根据过去的经验采取预期会产生回报的行动。探索 (Exploration)是指尝试新的行动，以发现潜在的更好策略。

在强化学习中，代理通过与环境互动并接受奖励或惩罚来学习。其目标是学习一种能在一段时间内使总奖励最大化的策略。总而言之，目标是通过提高策略的质量来最大化奖励值。这是一种寻找最佳性能的反复试验。它需要对同一个问题进行多次反复的尝试。

上述内容是有关于强化学习的抽象描述。如果考虑该方法应用的一些实例，那么概念就会更清晰一些。
比如，强化学习的一个领域是玩诸如双陆棋这样的逻辑游戏。或者是机器人技术，机器人必须学习如何有效地完成任务。比如说，机器必须学会如何在迷宫中导航。在这种情况下，当agent选择一个最终将通向目的地的左转时，奖励将被给出一个正值。如果它选择右转，则奖励为负值。

Machine learning: where a system improves its performance through analysis of previous performance
Unsupervised learning: where the machine learning takes place entirely through the system analysing and categorising the available data
Supervised learning: where a sample data is supplied to the system with associated data relating to the outcome of its use
Reinforcement learning: where an agent learns by receiving graded rewards for actions taken

回归分析方法

在某些应用中，人工智能的目的是根据输入到人工智能算法中的不同数量的数据值，预测并提供某些确定数量的输出数值。
如果要使用回归分析 (Regression analysis)，第一步需要为系统提供一些输入数据的实际值，以及人工智能系统运行时将成为输出数据的实际值。
机器可以利用这些数据来研究这两组数值之间是否存在任何相关性。如果相关性可以用数学公式来表示，那么在输入新数据时，就可以用这个公式来输出预测值。

Regression analysis: finding a mathematical function that provides the best fit to the actual outcomes when outcomes are calculated from previous inputs

回归分析最简单的应用是只输入一个量的值，并预期这些值与要预测的值之间存在线性关系。
例如，人工智能系统可以用来预测 A-Level 计算机科学考试考生的分数。
人们可能期望考生在 A-Level 计算机科学考试中的分数与他们在 IGCSE 数学考试中的分数之间存在相关性。下图显示了输入和分析一些历史数据后可能发现的情况：

我们可以发现，两个量之间有着很强的相关性。而这些数据拟合起来，图像中的直线就是最好的拟合直线。因此，这条线的公式可以根据IGCSE数学试卷的分数来预测A-Level计算机科学试卷的未来分数。

回归分析还可以更复杂。
例如，如果使用三种不同考试的分数作为输入，可以进行类似的数学公式拟合。在其他情况下，非线性关系可能是合适的，因为当需要预测新产品的未来销售时，预计销售将呈指数级增长。

人工神经网络

没想到这年头学计算机都需要了解生物知识。

下图我们人脑中的神经元的结构：

在神经细胞的一端有许多可以接收信号的树突。在细胞的另一端有许多轴突终末按钮可以传递信号。突触是位于轴突终末按钮和含有神经递质的树突之间的区域。当一个神经细胞接收到输入信号时，轴突内的电压就会增加。在该电压的某个阈值时，神经递质被激活，信号被发送到邻近细胞的树突。

而人工神经网络可以通过软件或硬件创建。
网络的组成部分可以用下图所示的图表来表示：三角形是网络中的节点 (Node)，代表人工神经元。一般来说节点会使用圆圈表示。
通常，节点可以接收一个或多个输入，并向其他节点提供一个或多个输出。节点动作的建模涉及到对每个输入施加一个权重因子。对加权输入值求和，然后使用激活函数计算节点的输出值。如果输入不是数值，则必须将其转换为1，以便对加权值进行求和。

图中显示了一个由三层组成的非常简单的网络结构。
左侧的3个节点的列接收输入。右边的列提供输出。中间的两个节点形成了所谓的隐藏层 (Hidden layer)。一些人工神经网络都会包含好几个隐藏层。

使用人工神经网络的人工智能系统的一个例子是根据支付的初始价格和使用寿命来估计电池的成本效益：每个输入节点代表一个特定的电池，它们的输入可包括电池的序列号，电池价格等数据。

接下来的隐藏层是输入层和输出层之间的层级。在这种情况下，隐藏层中的一个节点可能与电池使用的设备类型有关，另一个节点可能与设备的用户类型有关。这些节点处理输入，并将其传递给输出层。

在输出层，每个节点都会根据隐藏层处理后的输入，计算出特定电池单位时间成本的估计值。

在这个神经网络中，目标是学习一个从输入（电池数据和价格）映射到输出（估计成本效益）的函数。该网络将在已知成本效益的电池数据集上进行训练，并调整其内部参数（权重和偏置），使其预测值与实际值之间的差异最小。训练完成后，该网络可用于估算新电池的成本效益。

在这个系统中，每个节点都有可调节的因素。这些因素包括每个输入的权重和激活函数。
在初始学习时，需要对这些可调因子进行调整，以达到系统的最佳预测能力。为此，可以采用误差反向传播 (Back propagation of errors)的方法来实时调整权重和激活函数的参数。

要做到这一点，我们需要从电池的实际使用中获取一些电池寿命数据，然后为所有可调因素创建一个测试数据集。

在模型使用真实数据进行训练时，他会为每次输出确定一个误差，而误差是电池寿命的输出值与实际使用值之间的差值。然后，根据误差值反向传播，按需修改在某些节点上的权重和激活函数的参数，随后继续训练。这种操作可以提升模型的准确性。

Back propagation of errors: An algorithm for machine learning that optimizes the values for parameters which are adjustable. It is applied first to the nodes in the output layer and then works backward through the nodes in hidden layers until finally the input nodes are considered

学习过程从输出层开始，然后到隐藏层，最后到输入层。这种逐层学习的方法允许网络逐步完善其预测。随着反向传播的不断进行，我们最后会开始处理输入层节点的可调因素。
初始学习过程完成后，系统可应用于新的输入数据，以预测不同电池的成本效益。随着更多实际使用数据的出现，可以再次应用反向传播学习过程，以进一步提高系统性能。

深度学习

简单介绍下：大脑中有一层神经元结构，其中的低层具有易于理解的功能，而高层涉及更抽象的信息处理。
随着现在可用的计算能力的增加，人工神经网络被引入了大量的隐藏层，试图实现类似人脑的思考方式。这些方法被称为深度学习 (Deep Learning)系统。

机器学习是人工智能的一个子集，它允许计算机系统在没有明确编程的情况下自动做出预测或决策。它所需的计算能力较低，可以在较小的数据集上进行训练。但是，它需要更多的人工干预来纠正和学习，而且它只做简单的线性相关。

而深度学习是机器学习的一个子集，它使用人工神经网络来解决机器学习算法可能无法解决的更复杂的问题。深度学习使用以人脑为模型的复杂算法结构，能够处理文档、图像和文本等非结构化数据。它通常需要较少的持续人工干预，但需要大量数据和大量的算力（专门的 GPU来训练）。深度学习能够建立非线性的复杂关联。

人话讲：虽然机器学习和深度学习都涉及计算机从数据中学习，但深度学习更为复杂，可以处理更大、更多的非结构化数据集，但需要更多的计算资源。

Deep learning: where a system uses an artificial neural network with an exceptionally large number of hidden layers

至此，A2计算机 Paper3部分全部完成。

PART FOUR: 进阶编程技能与问题解决

第二十三章：算法

鉴于本人只会Python，本章的所有实例代码全部换成了Python。VB.NET还有Java那是真的一点不会。

线性搜索

线性搜索 (Linear search)，也叫做顺序搜索，是一种在列表中查找元素的方法。
算法的实现方法是：顺序地检查列表中的每个元素，直到找到匹配的元素或搜索了整个列表才可以结束。
线性搜索的最差运行时间为线性时间，最多进行 n 次比较，其中 n 是列表的长度。因为最坏的情况，就是算法爬遍了整个列表才找到结果。

代码如下：

def linear_search(list, target):
    for i in range(len(list)):
        if list[i] == target:
            return i  # 如果元素被找到，那么就返回index值
    return None  # 如果未找到元素，那么就返回None值

# 函数测试
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(linear_search(numbers, 5))  # 输出： 4
print(linear_search(numbers, 10))  # 输出： None

冒泡排序

冒泡排序 (Bubble sort)，又称为下沉排序，是一种简单的排序算法。
它对输入列表中的元素进行逐个重复排序，比较当前元素和其后的元素，并在必要时交换它们的值。
这种算法会重复检查列表，直到在某一次通过中发现没有元素需要交换位置，这意味着列表已完全排序。
该算法因较大的元素 “冒泡 “上升到列表顶端而得名。

冒泡排序的工作原理如下：

从列表的开始遍历列表
将列表中的第n个值与第n+1值进行比较。
如果第一个值较大，则交换两个值的位置。
移动到列表中的第二个值。再次比较该值和下一个值，如果该值较大，则交换位置。
继续进行，直到没有需要比较的项目为止。
回到列表的起点。
- 从列表遍历的开始到结束，每一次都称为一次通过 (Pass)。
冒泡排序一直持续到没有数值交换为止。此时，列表排序完毕。

下面是代码实例：

def bubble_sort(list):
    for i in range(len(list)):
        for j in range(len(list) - 1):
            if list[j] > list[j+1]:
                # 交换元素位置
                list[j], list[j+1] = list[j+1], list[j]
    return list

# 测试函数
numbers = [9, 8, 7, 6, 5, 4, 3, 2, 1]
print(bubble_sort(numbers))  # 输出: [1, 2, 3, 4, 5, 6, 7, 8, 9]

在本例中，bubble_sort 函数将一个列表作为输入。它将列表中的每个元素与其相邻元素进行比较。
如果某个元素大于其相邻元素，它就会交换它们。这个过程一直持续到不再需要交换为止，表明列表已经排序。

插入排序

插入排序 (Insertion sort)是一种简单的排序算法，它一次一个元素地建立最终的排序数组或排序列表。

在大型列表中，它的效率远低于更先进的算法，如快速排序，堆排序或合并排序，不过，插入排序有几个优点：

对小数据集排序比较高效
在应用中，插入排序比大多数其他简单的四元算法（如选择排序）更有效。
对已基本排序完毕的数据集更有效率
稳定，即不会改变相同键元素的相对顺序
就地排序，即只需要一定量的 O(1) 额外内存空间

插入排序的工作原理如下：

从列表开头开始遍历
将列表中的当前值(n)与之前的值(n-1)进行比较。
如果当前值小于前一个值，则对调它们。
移动到列表中的下一个值，重复步骤 2 和 3。
一直重复，直到没有可比较的项目为止。

插入排序的代码示例如下：

def insertion_sort(list):
    for i in range(1, len(list)):
        key = list[i]
        j = i - 1
        while j >= 0 and key < list[j]:
            list[j + 1] = list[j]
            j -= 1
        list[j + 1] = key
    return list

# 测试函数
numbers = [9, 8, 7, 6, 5, 4, 3, 2, 1]
print(insertion_sort(numbers))  # 输出: [1, 2, 3, 4, 5, 6, 7, 8, 9]

不难发现，在插入排序和冒泡排序这两种简单的排序算法中，每个元素的位置都是基于比较来决定的，这就决定了它们俩是最稳定的排序算法。因此它们不会在排序过程中交换具有相同值的键，从而保留这些元素的初始顺序。

然而他们之间有些区别：

在每次迭代中，插入排序算法将当前元素与之前的元素进行比较。相反，冒泡排序算法在每次迭代中，会比较并交换相邻的元素。
冒泡排序比插入排序执行更多的交换操作。对于每次迭代，插入排序在已经排序的元素中为当前元素找到合适的位置。相反，冒泡排序在每次迭代中比较和交换相邻的元素。大量的交换导致冒泡排序算法的运行时间变长。
虽然两种算法的时间复杂度都是O(n²)，即完成排序操作所需的时间是二次，但平均而言，由于交换次数较多，冒泡排序的性能不如插入排序。

下图是一个插入排序的直观解释：

首先，6先与它前面的数据47进行比较。6比47小，因此它们对调位置，6跑到了列表的最前面。
继续，54与47进行比较，54比47大，因此不执行任何操作。
17与54比较，因为17比54小，所以17会与54对调，并一直向前寻找元素比较大小，直到17换不动了为止。

排序就这么一直执行下去，直到序列中的最后一个元素也排列完成。

二分查找

二分查找 (Binary search)，又称半区间查找，对数查找或者二进制切分，是一种好用的查找算法，用来查找目标值在排序数组中的位置。
它的工作原理是反复将列表中可能包含该项的部分一分为二，直到将可能的位置缩小到一个为止。

Binary search: repeated checking of the middle item in an ordered search list and discarding the half of the list which does not contain the search item

二分查找的工作原理如下所示：

从数组的中间元素开始处理元素。
如果目标值等于数组的中间元素，则返回该元素的索引。
如果目标值小于中间元素，则重复数组左半部分的过程：寻找左半部分的中间点，然后看看目标值是小于这个数还是大于这个数。一直循环下去，直到找到匹配值。
如果目标值大于中间元素，则对数组的右半部分重复上述过程：寻找右半部分的中间点，然后看看目标值是小于这个数还是大于这个数。一直循环下去，直到找到匹配值。
如果在检查所有元素后仍未找到匹配值，则返回None。

Python代码实例：

def binary_search(list, target):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
    return None

# 测试函数
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search(numbers, 5))  # 输出: 4
print(binary_search(numbers, 10))  # 输出: None

抽象数据结构 (ADT)

13章我们说过，ADT是数据类型的数学模型。它从数据用户的角度来定义其行为的，特别是可能的值、对该类型数据的可能操作以及这些操作的行为。
例如，整数是一种 ADT，定义为…、-2、-1、0、1、2、…值，并可进行加、减、乘、除运算。用户可以使用抽象而非具体的表示方法。

链表

链表也是老朋友了。在这里我们会讲解有关于链表的各种操作：

创建链表

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert(self, data):
        if not self.head:
            self.head = Node(data)
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = Node(data)

    def print_list(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next

# 测试链表
linked_list = LinkedList()
linked_list.insert(1)
linked_list.insert(2)
linked_list.insert(3)
linked_list.print_list()  # 输出: 1 2 3

链表是一种线性数据结构，其中每个元素都是一个独立的对象，我们将其称为节点。
每个节点包含两个字段：节点包含的“数据”和节点连接的下一个节点的“指针信息”。
“数据”字段存储节点应持有的任何类型的数据，“指针信息”字段存储指向列表中下一个节点的引用。

下面我们来解释一下上面的代码：

创建Node类：该类代表链表中的单个元素。每个节点有两个属性：
- data：这个属性用来存储节点所持有的实际数据
- next：这是存储列表中下一个节点的引用。它初始值为 None，这意味着它不指向任何其他节点。
创建LinkedList类：该类表示整个链表。类中包含一个属性和两个方法：
- head：这是指向列表中第一个节点的引用。它初始设置为 None，这意味着列表是空的。
- insert：该方法会在列表末尾插入一个新节点。如果列表为空（即 self.head 为 None），它将创建一个新节点，并设置 self.head 指向它。否则，它会遍历列表，直到找到最后一个节点（即 node.next 为 None 的节点），然后创建一个新节点，并设置 last_node.next 指向它。
- print_list()：该方法会打印列表中存在的所有元素。它从 self.head 开始处理，沿着 next 引用从一个节点到下一个节点，打印每个节点的数据，直到到达 node.next 为 None 的节点。

实际上也不难。

向有序列表中添加节点

功能会基于创建链表的代码逐步添加新的模块：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_ordered(self, data):
        if self.head is None:
            self.head = Node(data)
        elif data < self.head.data:
            new_node = Node(data)
            new_node.next = self.head
            self.head = new_node
        else:
            current = self.head
            while current.next is not None and current.next.data < data:
                current = current.next
            new_node = Node(data)
            new_node.next = current.next
            current.next = new_node

    def print_list(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next

# 测试函数
linked_list = LinkedList()
linked_list.insert_ordered(3)
linked_list.insert_ordered(1)
linked_list.insert_ordered(2)
linked_list.print_list()  # 输出: 1 2 3

在这个示例中，insert_ordered 函数将一个值作为输入。它创建了一个新节点，然后为这个节点在列表中找到正确的位置。
如果列表为空或新值小于头节点中的值，它就会将新节点插入列表的开头。否则，它会遍历列表，直到找到一个节点的值大于新值或到达列表的末尾，然后将新节点插入该节点之前。

详细解释一下：

创建Node类：Node类跟之前创建链表的代码是完全一样的。
创建LinkedList类：其余也与之前一样，但是方法insert_ordered()主要管的就是节点的正确插入。它的实现方法如下：

空列表：如果列表为空（self.head 为 None），则会创建一个新节点，并设置self.head指向它。这个新节点将成为列表中的第一个节点。
在开头插入：如果新节点的数据小于头部节点的数据（data < self.head.data），则创建一个新节点，设置 new_node.next 指向当前的头部节点，然后更新 self.head 指向这个新节点。这实际上是将新节点插入列表的开头。
在中间或末尾插入：如果新节点的数据大于或等于头部节点的数据，则需要在列表的其余部分为该节点找到正确的位置。
为此，它会从 self.head 开始遍历列表。对于每个节点，它会检查 current.next.data<data。
如果该条件为真，它就会继续检查下一个节点（current = current.next）。如果该条件为假（意味着已找到数据大于或等于 data 的节点），或者已到达列表的末尾（current.next is None），则停止迭代。
然后，它会将新节点插入该节点之前（如果已到达列表末尾，则插入列表末尾）。

从链表中查找数据

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_ordered(self, data):
        if self.head is None:
            self.head = Node(data)
        elif data < self.head.data:
            new_node = Node(data)
            new_node.next = self.head
            self.head = new_node
        else:
            current = self.head
            while current.next is not None and current.next.data < data:
                current = current.next
            new_node = Node(data)
            new_node.next = current.next
            current.next = new_node

    def find_element(self, target):
        current = self.head
        while current:
            if current.data == target:
                return True
            elif current.data > target:
                return False
            current = current.next
        return False

# 测试函数
linked_list = LinkedList()
linked_list.insert_ordered(1)
linked_list.insert_ordered(2)
linked_list.insert_ordered(3)
print(linked_list.find_element(2))  # 输出: True
print(linked_list.find_element(4))  # 输出: False

在这个例子中，find_element 函数将目标值作为输入，并负责元素的寻找。它从列表的首项开始，遍历每个节点。如果找到数据等于目标值的节点，则返回 True。如果找到数据大于目标值的节点（因为列表是有序的），则返回 假，因为它知道目标值不在列表中。
如果没有找到目标值就到达了列表的末尾，也会返回假。

人话讲：该方法遍历一个有序链表，一旦发现数据等于目标节点（返回 True）或数据大于目标节点（返回 False），就立即停止。

我们来详细看一下find_element是怎么完成这一操作的：

初始化：该方法首先将 current 设置为列表的首项。这是我们在循环的每次迭代中都要检查的节点。
循环：只要 current 不是 None，while 循环就会继续。换句话说，当我们找到目标或检查了列表中的所有节点后，循环就会停止。
检查是否相等：在循环的每次迭代中，首先检查 current 节点的数据是否等于目标（current. data == target）。如果相等，则返回 True，表示已在列表中找到目标。
检查顺序：如果 current 节点的数据不等于目标值，则检查它是否大于目标值（current. data > target）。如果是，则返回 False。这是因为在有序链表中，如果我们遇到一个节点的值大于我们的目标值，我们就知道我们的目标值不可能出现在链表中更远的地方。
移动到下一个节点：如果上述两个条件都不满足（即 current.data小于 target），则移动到列表中的下一个节点（current = current.next）并重复上述过程。
未找到目标：如果已检查了列表中的所有节点，但仍未找到目标（即已退出 while 循环），则返回 False。

从链表中删除节点

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_ordered(self, data):
        if self.head is None:
            self.head = Node(data)
        elif data < self.head.data:
            new_node = Node(data)
            new_node.next = self.head
            self.head = new_node
        else:
            current = self.head
            while current.next is not None and current.next.data < data:
                current = current.next
            new_node = Node(data)
            new_node.next = current.next
            current.next = new_node

    def delete_node(self, target):
        if self.head is None:
            return
        if self.head.data == target:
            self.head = self.head.next
            return
        current = self.head
        while current.next is not None and current.next.data != target:
            current = current.next
        if current.next is not None:
            current.next = current.next.next

    def print_list(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next

# 测试函数
linked_list = LinkedList()
linked_list.insert_ordered(1)
linked_list.insert_ordered(2)
linked_list.insert_ordered(3)
linked_list.delete_node(2)
linked_list.print_list()  # 输出: 1 3

在这个示例中，delete_node 函数将目标值作为输入。
它从列表的首项开始，遍历每个节点。如果找到一个数据等于目标值的节点，它就会调整前一个节点的 next 引用，使其指向下一个节点，从而有效地从列表中删除目标节点。如果在检查所有节点后仍未找到这样的节点，则不会执行任何操作。

人话讲：此方法遍历一个有序链表，并删除一个数据等于 target 的节点。如果列表中不存在这样的节点，则不执行任何操作。

详细看一下delete_node的步骤：

空列表：该方法首先检查列表是否为空（self.head is None）。如果是，则退出方法，因为没有要删除的内容。
删除头部节点：然后，它会检查头部节点是否是要删除的节点（self.head.data == target）。如果是，它就会更新 self.head 以指向列表中的下一个节点（self.head = self.head.next），从而有效地从列表中删除原来的头部节点。
循环：如果头节点不是要删除的节点，它就会进入一个循环，其中 current 从列表的头开始，只要 current.next 不是 None （即直到到达列表的末尾）且 current.next.data 不等于 target （即直到找到要删除的节点），就会沿着列表移动。
删除节点：如果它找到了下一个节点的数据等于 target 的节点（current.next.data == target），它就会更新 current.next 以指向下一个节点的下一个节点（current.next = current.next.next）。这实际上是从列表中删除了下一个节点（要删除的节点）。

访问链表中的所有节点

这个就相对简单一些了。思路就是按照指针的顺序，按照顺序访问每个节点，然后输出节点中的内容。

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert(self, data):
        if not self.head:
            self.head = Node(data)
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = Node(data)

    def print_list(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next

# 测试函数
linked_list = LinkedList()
linked_list.insert(1)
linked_list.insert(2)
linked_list.insert(3)
linked_list.print_list()  # 输出: 1 2 3

在本例中，print_list 函数从列表的首部开始，遍历每个节点，打印其数据。它将继续执行，直到到达 next 为 None 的节点，表示已到达列表的末尾。这样，它就访问并打印了列表中的所有节点。

二叉树

在计算机科学中，二叉树 (Binary tree )是一种被称之为k-ary的数据结构，其中每个节点最多有两个延伸出来的子节点。这些节点一般被叫做左子节点 (Left child)和右子节点 (Right child)。

二叉树是递归定义的，这就意味着每一棵非空二叉树都由一个根节点和两个后代二叉树组成。

下面是关于二叉树的一些要点和常识：

二叉树中最顶端的节点叫做根节点 (Root)
二叉树中的每一个元素都叫做节点 (Node)
每个节点最多有两个子节点
子节点一般被叫做左子节点 (Left child)和右子节点 (Right child)，这个我们刚才说过。
二叉树可用于许多计算机科学应用中，包括组织层次关系、管理有序数据以及作为抽象流程的工作流。

要向有序二叉树增加一个节点，我们的步骤如下：

从作为当前节点的根节点开始：进程从树的根节点开始，也就是最顶端的节点。
重复：接下来重复这些条件：
- 如果数据值大于当前节点的数据值，则沿右分支：在二叉树中，任何数据值大于其父节点的节点都会被置于右侧。因此，如果要插入的数据值大于当前节点的数据值，则应移动到当前节点的右侧子节点。
- 如果数据值小于当前节点的数据值，则沿左侧分支：相反，在二叉树中，任何数据值小于其父节点的节点都会被置于左侧。因此，如果要插入的数据值小于当前节点的数据值，就会移动到当前节点的左侧子节点。
直到当前节点没有分支可循：继续在树中移动，直到到达一个在需要移动的方向上没有子节点的节点（即向左移动时没有左子节点，向右移动时没有右子节点）。这就是你要插入新节点的地方。
在此位置添加新节点：根据数据小于或大于当前节点的数据，创建一个包含数据的新节点，并将其作为当前节点的左子节点或右子节点插入。

这个过程确保了左边的所有节点都小于其父节点，而右边的所有节点都大于其父节点，这就是有序或排序二叉树的原理。

创建二叉树

我们可以使用Python来创建一个二分查找树：

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self, root):
        self.root = Node(root)

# 初始化二叉树
tree = BinaryTree(1)
tree.root.left = Node(2)
tree.root.right = Node(3)
tree.root.left.left = Node(4)
tree.root.left.right = Node(5)

解释一下这段代码：

我们首先定义了一个 Node 类，它将创建一个带值的节点，以及两个初始化为 None 的子节点。
然后，我们定义一个 BinaryTree 类，初始化为一个根节点。
最后，我们创建一棵名为 tree 的二叉树，根节点为 1，然后在根节点上添加左侧子节点 2 和右侧子节点 3。然后，我们在根的左子节点上添加两个子节点 4 和 5。

画出图来就像这样：

十分形象。

我们详细来说一下实现步骤：

class Node:
def __init__(self, value):
self. value = value
self. left = None
self. right = None

先讲一下Node类的定义。每个Node对象都有三个属性:

value:节点持有的数据。
left:指向节点的左子节点。
right:指向节点的右子节点。

而__init__方法是Python类中的一个特殊方法，当类的对象实例化时，它是自动调用的构造方法。在这个例子中，它用给定的值初始化一个节点，并将其左子节点和右子节点设置为None。

1
2
3

class BinaryTree:
def __init__(self, root):
self. root = Node(root)

在BinaryTree类的定义中，二叉树对象有一个属性:root，它是对树的根节点的引用。这里的__init__方法用根节点初始化一棵二叉树。

# 初始化二叉树
tree = BinaryTree(1)
tree.root.left = Node(2)
tree.root.right = Node(3)
tree.root.left.left = Node(4)
tree.root.left.right = Node(5)

在这里，我们创建一个二叉树实例。我们用一个包含值 1 的根节点来初始化它。
随后，我们通过创建新节点并将其赋值给 tree.root.left 和 tree.root.right 来为根节点添加左右两个子节点。
我们还将以类似的方式为根节点的左侧子节点添加两个子节点。

向二叉树中添加一个新节点

在二叉树中，新节点可以根据一定的规则或标准插入某个位置。然而，在二分查找树（BST）中，节点会被插入到一个特定的位置，在这个位置上，节点左边的所有节点的值都小于该节点，而右边的所有节点的值都大于该节点。

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self, root):
        self.root = Node(root)

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(value, self.root)

    def _insert(self, value, current_node):
        if value < current_node.value:
            if current_node.left is None:
                current_node.left = Node(value)
            else:
                self._insert(value, current_node.left)
        elif value > current_node.value:
            if current_node.right is None:
                current_node.right = Node(value)
            else:
                self._insert(value, current_node.right)
        else:
            print("Value already in tree!")

# Initialize a tree
tree = BinaryTree(5)
tree.insert(3)
tree.insert(7)
tree.insert(1)
tree.insert(4)

在这段代码中，我们为原来的 BinaryTree 类新添加了一个 insert 方法，该方法将一个值作为输入。
如果树为空（即根节点为 None），它将用给定的值创建一个新的 Node，并将其赋值给根节点。如果树不为空，则调用 _insert 方法。

_insert 方法是一个辅助方法，用于为新节点找到正确的位置。
它是一个递归方法，用于比较要插入的值和当前节点的值。具体步骤如下：

如果待插入的值小于当前节点的值，就会插入左侧子节点。如果左侧子节点为 None，则在此处插入新节点。否则，它会再次调用 _insert，将左侧子节点作为新的当前节点。
如果待插入的值大于当前节点的值，则转到右侧子节点。如果右侧子节点为 None，则在此处插入新节点。否则，它会再次调用 _insert，并将右侧子节点作为新的当前节点。
如果值等于当前节点的值，则会打印一条信息，说明该值已在树中，而不会插入。

这样就能在二分查找树中，当插入新节点时保持它的特性不变了。

在二叉树中寻找指定节点

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self, root):
        self.root = Node(root)

    def find(self, value):
        if self.root is None:
            return "二叉树为空。"
        else:
            return self._find(value, self.root)

    def _find(self, value, current_node):
        if value == current_node.value:
            return "已发现匹配值"
        elif value < current_node.value and current_node.left is not None:
            return self._find(value, current_node.left)
        elif value > current_node.value and current_node.right is not None:
            return self._find(value, current_node.right)
        return "未发现匹配值"

# 初始化二叉树
tree = BinaryTree(5)
tree.root.left = Node(3)
tree.root.right = Node(7)
tree.root.left.left = Node(1)
tree.root.left.right = Node(4)

# 在二叉树中寻找特定值
print(tree.find(7))  # 输出: "已找到匹配值"
print(tree.find(2))  # Output: "未找到匹配值"

为了添加寻找节点功能，在这段代码中，我们为我们的 BinaryTree 类添加了一个 find 方法，该方法将一个值作为输入。
如果树为空（即根为 None），它将返回一条信息，说明树为空。如果树不为空，则调用 _find方法。

_find 方法是一个辅助方法，用于查找具有给定值的节点。它是一个递归方法，用于比较要查找的值和当前节点的值：

如果值等于当前节点的值，则返回一条信息，说明已找到该值。
如果值小于当前节点的值，且左侧子节点不是 None，则再次调用 _find，并将左侧子节点作为新的当前节点。
如果值大于当前节点的值，且右侧子节点不是 None，则再次调用 _find，并将右侧子节点作为新的当前节点。
如果这些条件都不满足，则表示在树中没有找到该值，并返回一条信息说明这一点。

这将在二分查找树中查找给定值。

栈

我们早在AS部分就已经接触过栈了。接下来我们来简单复习一下栈的性质。

栈是一种作为元素集合的抽象数据类型，栈主要有两种操作：

Push 推入：也就是向集合压进元素。
Pop 弹出：弹出最近添加但尚未删除的元素。

元素加入栈或从栈中移除的顺序被描述为后进先出 (Last in first out, LIFO)。这种结构使得从栈顶移除一个项目非常容易，但要访问栈中较深的数据可能需要先移除多个其他项目。

我们会声明一个TopOfStack指针变量，用来跟踪栈顶元素。它的值根据在栈上执行的操作而变化。

当向栈中推入一个新元素时，TopOfStack 会更新为指向这个新元素。
当从栈中弹出一个元素时，TopOfStack 会更新为指向栈中的下面一个元素。
如果栈是空的，TopOfStack 可能会被设置为一个特殊值，如-1，以表示没有顶层元素。

例如，如果要将栈作为数组来实现，一开始可以将 TopOfStack 设为 -1，以表示栈是空的。当向栈中推入一个元素时，TopOfStack 会递增 1；当从栈中弹出一个元素时，TopOfStack 会递减 1。

栈的创建，压入和弹出

Python内置的List数据类型可以很轻松的让我们创建一个栈：

# 初始化栈
stack = []

# 向栈中压入元素
stack.append("Apple")
stack.append("Banana")

# 从栈中弹出元素
print(stack.pop())  # 输出: "Banana"

在这段代码中，我们初始化一个空列表作为栈。
我们使用列表的append方法将元素压入栈中，使用pop方法将元素从栈中弹出。
最后添加的元素是第一个弹出的元素，这与栈的LIFO行为一致。

队列

在计算机中，队列 (Queue)是一种遵循先进先出 (First in first out, FIFO)原则的线性数据结构。这意味着第一个添加到队列的元素将是第一个被删除的元素。你可以把它想象成一排等待服务的人，等待时间最长的人(排队的第一个人)是下一个被服务的人。相比于栈来说，这是比较符合直觉的。

在队列中，我们会定义两个指针类型变量： FountOfQueuePointer和EndOfQueuePointer，分别用来追踪队列中的第一个和最后一个元素：

FrontOfQueuePointer始终指向队列中的第一个元素，它是下一个要从队列中删除的元素。这是因为在队列中，删除操作发生在最前面。
EndOfQueuePointer始终指向队列中的最后一个元素。当一个新元素被添加(或“加入”)到队列中时，它会被添加到队列的末尾，所以EndOfQueuePointer会递增指向这个新元素。

队列还存在所谓“环绕的可能性”。
这指的是循环队列（一种最后一个元素指向第一个元素的队列）中的一种情况，在这种情况下，如果将 EndOfQueuePointer 的增量超出底层数组的终点，就会导致它绕到数组的起点。同样，将 FrontOfQueuePointer 递减到数组开头之后，也会使其绕到数组结尾。这样就可以重复使用数组中之前被从队列中删除的元素占据的位置，从而有效地利用空间。

常规队列和环绕型队列如下所示：

队列的创建，压入和弹出

Python的列表数据形式也同样支持我们去简单的声明并操作一个队列：

# 初始化队列
queue = []

# 向队列内加入元素
queue.append("Apple")
queue.append("Banana")

# 从队列内弹出元素
print(queue.pop(0))  # 输出: "Apple"

在这段代码中，我们初始化一个空列表作为队列。
我们使用列表的append方法将项目加入到队列中，并使用参数为0的pop方法将项目从队列中取出。这里的参数决定了这个列表是一个队列，而不是一个栈。
添加的第一个元素就是第一个删除的元素，这与队列的FIFO行为是一致的。

图表

在计算机科学中，图表 (Graphs)是由顶点(或者节点)和边组成的抽象数据类型，用于实现数学中图理论领域的无向图和有向图概念，或者简单来说：记录事物之间的关系。

图表是一种基本数据结构，它对一组对象（称为节点或顶点）以及它们之间的关系（称为边或弧）进行建模。

图表也可以描述AI，但是在这里我们不讨论。如果需要了解这部分的内容就前往22章简单一看吧。
下面的图表表示伦敦地铁地图的一小部分：

从A到F的所有顶点表示地铁站，而连接线表示连接地铁站的铁路线。
例如，你可以直接从B乘火车到D。要从B乘火车到F，你必须经过C或E。由边连接的两个顶点被称为邻居 (Neighbours)。

同时，你也可以在连接线上加入标签，也就是权重。在我们的这个实例中，我们可以使用权重来表示站点之间的旅行时间：

节点之间的连接线可以是有向的，也可以是无向的：

在计算机内存中，有两种常见的图表示方法：邻接矩阵 (Adjacency matrix)和邻接表 (Adjacency list)。

邻接矩阵是大小为 V x V 的二维数组，其中 V 是图中的顶点数。
每一行和每一列代表一个顶点。如果矩阵中第 i 行和第 j 列的元素值为 1，则表示第 i 个顶点和第 j 个顶点之间有一条边。反之，如果值为0，则表示两个顶点之间没有连接。这种表示方法仅适用于无权重图表。

而对于加权图表，边有相关的权重或成本，这些权重会直接写在对应的表格内。比如说第 i 个顶点和第 j 个顶点之间有链接，并且权重为5，那么矩阵中第 i 行和第 j 列的元素值为 5。
如果顶点之间没有边，我们通常会用一个很大的数字（通常用无穷符号∞表示）来代替 0，以表示这两个节点之间没有直接路径。

下面是分别是无权图表和加权图表的邻接矩阵的实例：

刚才提到过的邻接表是表示图形的另一种方法。

在邻接列表表示法中，我们在图形对象中保留了一个包含所有顶点的主列表，然后图形中的每个顶点对象都保留了一个与其相连的其他顶点的列表。在邻接表中，每个顶点都有一个相邻顶点的列表。这非常适合需要遍历每个顶点的邻接顶点时使用，因为可以高效地访问邻接顶点集。

解释的有些抽象，我们直接看下面这个邻接表的实例吧：

图表中的内容代表：

A与B和D相连
B与A,C,D,E相连
C与B和F相连
D与A,B,E相连
E与B,D,F相连
F与C,E相连

不难看出这个邻接表展示了一个无权重的图表的节点之间的关系。如果需要表示节点之间的权重，就会像下图一样：

道理还是一样，不过加了个权重而已。

第一行代表：“A与B相连，权重为3；A与D相连，权重为5”

哈希表

哈希表 (Hash table)，也叫散列表，是一种实现关联数组抽象数据类型的数据结构，是一种可以将键映射到值的结构。
它使用哈希函数来计算一个进入桶或槽数组的索引，从中可以找到所需的值。
哈希表背后的主要理念是，它提供了对存储在数组中的记录的直接访问。这是通过使用记录的键值计算出一个地址（数组索引），然后将记录存储在这个计算出的地址上。
当你想搜索一条记录时，你可以再次使用键值来计算地址，然后直接到这个地址去查找记录。这种通过密钥计算地址的过程被称为散列 (Hashing)。

哈希表的创建，添加元素，与查找

# 创建一个简单的散列函数
def hash_function(key):
    return key % 5

# 初始化一个空哈希表
hash_table = [None] * 5

# 向哈希表中添加元素
keys = [15, 30, 45]
values = ["Apple", "Banana", "Cherry"]
for i in range(len(keys)):
    address = hash_function(keys[i])
    hash_table[address] = values[i]

# 从哈希表中搜索元素
key_to_search = 30
address = hash_function(key_to_search)
print(hash_table[address])  # Output: "Banana"

我们来简单解释一下这写代码：

在函数hash_function中，我们创建了一个简单的哈希函数。它接收一个值，然后返回该值除以 5 的余数。这会输出在0-4区间内的一个值。这个值会用来计算哈希表中我们要存储或查找值的索引。

hash_table = [None] * 5 将一个空的哈希表初始化为一个包含 None 值的列表。该列表的长度（5）应与散列函数返回的可能值范围相同。

keys = [15, 30, 45]
values = ["Apple", "Banana", "Cherry"]
for i in range(len(keys)):
    address = hash_function(keys[i])
    hash_table[address] = values[i]

在本节中，我们将向哈希表中插入一些内容，我们将这些内容叫做记录 (Record)。
我们有两个列表：keys（包含记录的键）和 values（包含相应的值）。我们遍历这些列表，使用散列函数计算每个键的地址，并将每个值存储在散列表中计算出的地址处。

1
2
3

key_to_search = 30
address = hash_function(key_to_search)
print(hash_table[address])  # Output: "Banana"

最后，我们要搜索带有给定键的记录。
我们使用哈希函数计算出这个键的地址，并输出存储在哈希表中这个地址的值。
在本例中，我们要查找的是键 “30”，它的散列地址是 “0”，在散列表的这个地址上，我们可以找到值Banana。

词典

在计算机科学中，词典 (Dictionary)也称为映射 (Map)，是一种用于存储键值对的数据结构，类似于现实世界中的词典。
键用于查找相关的值，就像在现实世界的词典中查找单词的定义一样。

词典可以使用各种数据结构来实现，哈希表就是其中之一。哈希表使用哈希函数来计算的索引，从中可以找到所需的值。这样就可以使用键值高效地直接访问检索值。

例如，如果您有一本将英语单词翻译成法语的词典，您可以将英语单词作为键，将法语翻译作为值。如果将该词典作为哈希表来实现，则可以通过将英语单词作为键，快速高效地查找任何给定英语单词的法语翻译。

词典的创建与操作

VB.NET和Java都有内置的词典数据类型，但是他们看起来好像都很复杂。

好在Python也存在内置的词典数据类型：

# 创建词典
english_french_dict = {
    "hello": "bonjour",
    "goodbye": "au revoir",
    "please": "s'il vous plaît",
    "thank you": "merci",
    "yes": "oui",
    "no": "non"
}

# 访问词典中的数据
print(english_french_dict["hello"])  # 输出: "bonjour"

# 向词典中加入新的值
english_french_dict["sorry"] = "désolé"

# 从词典中移除值
del english_french_dict["goodbye"]

# 检查一个值是否在词典里
print("please" in english_french_dict)  # 输出: True

# 取出词典中所有元素的索引
print(english_french_dict.keys())  # 输出: dict_keys(['hello', 'please', 'thank you', 'yes', 'no', 'sorry'])

# 取出词典中所有的元素
print(english_french_dict.values())  # 输出: dict_values(['bonjour', "s'il vous plaît", 'merci', 'oui', 'non', 'désolé'])

挺简单的，代码我就不解释了。

时间复杂度与大O符号

大O符号是一种数学符号，用于描述当参数趋向特定值或无穷大时函数的极限行为。
在计算机科学中，它用于根据算法对输入大小变化的反应（时间复杂度）对算法进行分类。

我们来设想一个线性搜索算法。线性搜索算法的时间复杂度为 O(n)。这是因为在最坏的情况下（正在搜索的项目位于列表的末尾），运行算法所需的时间与输入的大小呈线性增长。这意味着，如果将列表的大小增加一倍，最坏情况下的时间也将大致增加一倍。

值得注意的是，大O符号通常描述的是最坏情况，因为它提供了时间要求的上限，通常比最佳或平均情况更重要。不过，在某些情况下，平均情况或最佳情况也可以用大O符号来描述。

我们来考虑计算一下冒泡排序的时间复杂度：

冒泡排序是一种简单的排序算法，它重复通过列表，比较相邻的元素，如果顺序错误，则交换它们。重复通过列表，直到列表排序完毕。

最坏情况下，冒泡排序的时间复杂度为 O(n^2)。原因如下：

在第一次通过列表时，冒泡排序会进行 n-1 次比较，其中 n 是列表中元素的个数。这是因为它会对每一对相邻元素进行比较（n 元素为 n-1 对）。
在第二次排序时，由于最大的元素已经在第一次排序的正确位置上，所以要进行 n-2 次比较。
这种情况一直持续到最后一次，只进行 1 次比较。

因此，在最坏的情况下，泡泡排序所做的比较总数是，这个总和等于，简化为。

当我们讨论时间复杂度和大O符号时，我们感兴趣的是运行时间是如何随着输入大小的增长而增长的。
因此，我们取最高阶项（即 n^2），忽略常数和低阶项。这就是为什么我们说冒泡排序的最坏情况时间复杂度为 O(n^2)。这意味着，如果将列表的大小增加一倍，最坏情况下的时间大约会翻两番。如果将列表的大小增加两倍，最坏情况下的时间将增加约 9 倍。以此类推。

下面这张表格展示了不同的大O符号代表了哪些算法：

Order of growth	Example	Explanation
O(1)	`FUNCTION GetFirstItem(List : ARRAY); RETURN List[1]`	算法的复杂度不会随数据集的大小而改变
O(n)	线性搜索在已排序的列表上执行Bubble soft	这些算法呈线性增长
O(Log2(n))	二分搜索	随着数据集大小的增加，所花费的总时间也会增加，但每次比较都会将数据集减半。所以所用的时间增加的幅度较小，接近常数时间。
O(n^2)	冒泡排序插入排序	以平方速度增长这在涉及数据集上嵌套迭代的算法中很常见
O(n^3)		以次方速度增长常见于嵌套算法
O(2^n)	斐波那契数的递归计算	指数速度增长

第二十四章：递归

在计算机科学中，递归例程 (Recursive routine)或递归 (Recursive)是一种解决问题的方法，其解决方案取决于同一问题较小实例的解决方案。
它涉及函数在某些条件为真时调用自身。
这个过程一直持续到满足某个条件为止，这个条件通常称为基例 (Base case)或停止条件。
一般情况 (General case)，也称为递归情况 ()是指导致函数不断调用自身的情况。

Base case: an explicit solution to a recursive function
General case: a definition of a recursive function in terms of itself

递归在编程中用于解决可分解为更简单、类似子问题的问题。它是计算机科学的核心思想之一。大多数计算机编程语言都支持递归，允许函数在自己的代码中调用自己。

下面是 Python 中一个简单的递归函数示例，用于计算一个数字的阶乘：

def factorial(n):
    if n == 0:  # 基本情况
        return 1
    else:  # 一般情况
        return n * factorial(n-1)

在这段代码中，factorial 是一个调用自身的递归函数。它一直这样做，直到达到基值（当 n 为 0 时），这时它开始将结果返回到调用栈。

编写递归子程序

当编写递归子程序时，我们需要考虑以下几点，或者说按照以下步骤来编写程序：

确定基例：基例是允许递归停止的条件。它是最简单的情况，可以直接求解，无需进一步递归。例如，在计算一个数字的阶乘的函数中，基例是当数字为 0 或 1 时，因为 0 和 1 的阶乘是 1。
定义一般情况：一般情况是指函数以问题的较简单版本调用自身。其定义方式应使每次递归调用都更接近基例。
递归计算：每次递归调用都应使你更接近一般情况。如果做不到这一点，就会出现无限递归，最终导致栈溢出错误。
返回值：确保函数正确返回值。在递归函数中，你通常会返回递归调用的结果，可能还会进行一些额外的计算。

举一个例子吧。

使用递归编程解决实际问题的一个经典例子就是斐波那契数列的计算。
斐波那契数列是一个数列，其中一个数是前两个数的和，通常从 0 和 1 开始。
下面是一个使用递归计算第 n 个斐波那契数的 Python 函数：

def fibonacci(n):
    if n <= 0:
        return "输入值必须为正整数"
    elif n == 1:
        return 0  # 基例1
    elif n == 2:
        return 1  # 基例2
    else:  # 一般情况
        return fibonacci(n-1) + fibonacci(n-2)

在此函数中：

当 n 为 1 或 2 时，对应两个基例。斐波那契数列的前两个数是 0 和 1，因此如果 n 是 1，函数返回 0，如果 n 是 2，函数返回 1。
一般情况是 fibonacci(n-1)+ fibonacci(n-2)。这符合斐波那契数列中每个数字都是前两个数字之和的规则。这使我们更接近基本情况，因为每次递归调用都在递减 n。
在一般情况下，我们将返回 fibonacci(n-1) + fibonacci(n-2)，而在基例下，我们将返回 0 或 1。

第二十五章：编程范式

编程范式是一种基本的编程风格。每种范式都支持不同的思考和解决问题的方式。编程语言的功能支持各种范式。
有些编程语言支持不止一种范式。有许多不同的范式，有些还相互重叠。以下是几种不同的范式。

Programming paradigm: A fundamental style of programming

低级编程语言范式

低级编程语言更接近机器语言，也就是计算机硬件能理解的基本语言。这些语言允许程序员直接操作内存地址和寄存器的内容。这意味着你可以精确控制程序与系统硬件的交互方式。

特定处理器的架构是指其设计和执行指令的方式。不同的处理器有不同的架构，因此需要不同的编程语言。例如，英特尔处理器系列使用 x86 指令集。

用低级模式编程时，解决问题的方式与高级模式不同。高级语言旨在方便人类读写，它们抽象掉了机器（计算机硬件）的许多复杂性。另一方面，低级编程更为复杂，需要更深入地了解计算机硬件的工作原理。

不过，低级编程能让你更有效地控制程序的性能，并能针对特定的硬件配置优化代码。这就是低级编程常用于编写操作系统或开发嵌入式系统等任务的原因。

所以，低级编程语言可以直接访问计算机硬件，但需要对系统架构有更详细的了解。低级编程语言可以更好地控制程序的性能，但与高级语言相比，它们也需要不同的解决问题的方法。

命令式编程范式

命令式编程 (Imperative programming)是另一种编程范式，在这种编程范式中，你编写的程序是一连串明确的步骤或指令，计算机必须按照这些步骤或指令实现预期的结果。
这与声明式编程形成鲜明对比，在声明式编程中，你只需描述所需的结果，计算机就能找出实现的方法。

换句话说，在命令式编程中，你是在告诉计算机如何做某事。例如，如果你要做一个三明治，那么命令式编程就需要一步一步地发出指令，如 “拿两片面包”、”在一片面包上涂黄油”、”在另一片面包上放火腿 “等等。但是，在声明式编程中，你是在告诉计算机你想要做什么。再以三明治为例，声明式编程方法就是简单地说 “我想要一个火腿三明治”，然后由计算机（或三明治制作者）找出实现这一目标所需的步骤。

程序设计是命令式程序设计的一种，程序围绕程序或例程（也称为子程序或函数）构建。主程序调用这些过程来执行任务。每个过程都是一组执行特定任务的指令。

支持命令式编程的语言有很多。例如 Pascal、C 和 Basic。这些语言提供了定义变量和函数的结构，以及控制执行流程的结构（如循环和条件语句），这些都是命令式编程范式的关键要素。

面向对象的编程语言范式

面向对象编程 (Object-oriented programming, OOP)是一种基于 “对象 “概念的编程范式。对象是类的实例，可以包含数据（以字段的形式，也称为属性）和代码（以过程的形式，也称为方法）。在 OOP 中，对象之间通过交互来执行任务。这种方法更易于管理大型程序的复杂性，使代码更易于重复使用和维护。

许多编程语言最初是为命令式编程而设计的，现在已经扩展到支持 OOP。例如，Pascal 以 Delphi 或 Object Pascal 的名称进行了扩展，以支持 OOP。同样，Visual Basic 也被扩展为支持 OOP，.NET 版本是第一个完全面向对象的版本。

还有一些语言从一开始就被设计成面向对象的。Python 和 Java 就是这样的两种语言。这些语言提供了类、对象、继承和多态等功能，这些都是面向对象编程范式的关键要素。

声明式编程语言范式

Pascal、VB 和 Python 等命令式编程语言之所以被称为命令式编程语言 (Imperative programming language)，是因为它们采用循序渐进的方法来解决问题。在这些语言中，程序员编写一系列语句或指令，告诉计算机如何解决问题。

另一方面，声明式编程是一种程序设计风格，程序员编写的规范描述的是问题，而不是如何解决问题。
换句话说，在声明式编程中，你告诉计算机你想实现什么，然后由计算机来决定如何实现。

声明式程序通常用形式逻辑来表达，而计算则是从这些逻辑语句中演绎出来的。这使得声明式编程特别适用于涉及搜索、模式匹配和推理的问题。

SQL（结构化查询语言）和 Prolog 就是声明式编程语言的例子。SQL 用于管理和操作关系数据库，而 Prolog 则用于逻辑编程和人工智能。

总结一下：命令式编程和声明式编程的主要区别在于解决问题的方法：命令式编程告诉计算机如何解决问题，而声明式编程则描述问题是什么。

第二十六章：文件处理和异常处理

A2CS笔记

http://naughtychas.github.io/2023/07/01/A2CS笔记/

作者

ntcs

发布于

2023-07-01

更新于

2024-05-20