Progress

Learning Progress: Completed.😸

Learning Source

贝赫鲁兹·佛罗赞. 计算机科学导论（原书第4版）[M]. 吕云翔, 杨洪洋, 曾洪立译. 机械工业出版社, 2020.

1 绪论

1.1 图灵模型

Alan Turing（阿兰·图灵）在 1936 年最先提出了一个通用计算设备的设想。他认为，所有的计算都可以在一种特殊的机器上执行，这就是现在所说的图灵机。
通用图灵机是对现代计算机的首次描述，只要提供了合适的程序，该机器就能做任何运算。可以证明，一台很强大的计算机和通用图灵机一样能进行同样的运算。

1.2 冯·诺依曼模型

1944 ~ 1945 年，冯·诺依曼指出，鉴于程序和数据在逻辑上是相同的，因此程序也能存储在计算机的存储器中。

1.3 计算机组成部分

冯·诺依曼模型要求程序必须是有序的指令集。

1.4 计算机科学作为一门学科

如同其他任何学科一样，计算机科学现在被划分成几个领域。我们可以把这些领域归纳为两大类：系统领域和应用领域。系统领域涵盖那些与硬件和软件构成直接有关的领域，例如计算机体系结构、计算机网络、安全问题、操作系统、算法、程序设计语言以及软件工程。应用领域涵盖了与计算机使用有关的领域，例如数据库和人工智能。

2 数字系统

2.1 位置化数字系统

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

\[ \pm(S_{K-1} \cdots S_2 S_1 S_0. S_{-1} S{_-2} \cdots S_{-L})_b \]

它的值是：

\[ n = \pm \left( S_{K-1} \times b^{K-1} + \cdots + S_1 \times b^1 + S_0 \times b^0 + S_{-1} \times b^{-1} + S_{-2} \times b^{-2} + \cdots + S_{-L} \times b^{-L} \right) \]

其中，$S$ 是一套符号集，$b$ 是底（或基数），它等于 $S$ 符号集中的符号总数，其中 $S_K$ 和 $S_L$ 分别是代表整数和小数部分的符号。

我们使用 $\pm$ 符号表示一个数可正可负，但这些符号并不存储在计算机中——计算机用以处理该符号的方式不同。
十进制不像二进制那样直接显示存储在计算机中的是什么。在二进制位数和十进制数码的数量之间没有显然的关系，它们之间的转换也不快捷。为了克服这个问题，发明了两种位置化系统：十六进制和八进制。
可以用数码 $K$ 表示的最大值：
- 十进制整数的最大值为：$N_{\text{max}} = 10^K - 1$
- 二进制整数的最大值为：$N_{\text{max}} = 2^K - 1$
- 十六进制整数的最大值为：$N_{\text{max}} = 16^K - 1$
- 八进制整数的最大值为：$N_{\text{max}} = 8^K - 1$

2.2 非位置化数字系统

非位置化数字系统仍然使用有限的数字符号，每个符号都有一个值。但是符号所占用的位置通常与其值无关——每个符号的值都是固定的。为求出该数字的值，我们把所有符号表示的值相加。比如罗马数字系统。

3 数据存储

3.1 数据类型

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

3.2 存储数字

3.2.1 存储整数

整数通常使用顶点表示法存储在内存中。
只要用不到负整数，都可以用无符号整数表示法。具体情况如下：
- 计数
- 计算机寻址
- 存储其他数据类型（文本、图形、音频和视频）
在符号加绝对值表示法中，最左位用于定义整数符号。0 表示正整数，1 表示负整数。在 n 位单元可存储的数字范围是 $-\left( 2^{n-1} - 1\right)$ 至 $+\left( 2^{n-1} - 1 \right)$。
反码运算：反转各个位，即把 0 位变为 1 位，把 1 位变为 0 位。可应用于任何整数，无论正负。
补码运算：从右边复制位，直到有 1 被复制；接着反转其余的位。另一种方法是先对它进行 1 次反码运算再加上 1 得到结果。2 次补码运算可以得到原先的整数。
以二进制补码格式存储整数：
1. 将整数变成 n 位的二进制数；
2. 如果整数是正数或零，以其原样存储；如果是负数，取其补码存储。
从二进制补码格式还原整数
1. 如果最左位是 1，取其补码；如果最左位是 0，不进行操作；
2. 将该整数转换为十进制。
二进制补码表示法仅有一个 0，而符号加绝对值表示法则有两个 0（+0 和 -0）。

3.2.2 实数

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

4 数据运算

4.1 逻辑运算

AND 运算的一个应用就是把一个位模式的指定位复位（置 0）。这种情况下的第二个输入称为掩码。掩码中的 0 位对第一个输入中相应的位进行复位。掩码中的 1 位使得第一个输入中相应的位保持不变。
OR 运算的一个应用是把一个位模式的指定位置位（置 1）。掩码中的 1 位对第一个输入中相应的位进行置位，而掩码中的 0 位使第一个输入中相应的位保持不变。
XOR 运算的一个应用是使指定的位反转。掩码中的 1 位对第一个输入中相应的位进行反转，而掩码中的 0 位使第一个输入中相应的位保持不变。

4.2 移位运算

移位运算分为两大类：逻辑移位运算和算术移位运算。
算术移位运算假定位模式使用二进制补码格式表示的带符号位的证书。算术右移被用来对整数除以 2；而算术左移被用来对整数乘以 2。这些运算不应该改变符号位（最左）。算术右移保留符号位，但同时也把它复制，放入相邻的右边的位中，因此符号被保存。算术左移丢弃符号位，接受它的左边的位作为符号位。如果新的符号位与原先的相同，那么运算成功，否则发生上溢或下溢，结果是非法的。

5 计算机组成

计算机的组成部件可以分为三大类（或子系统）：中央处理单元（CPU）、主存储器和输入/输出子系统。

5.1 中央处理单元

中央处理单元（CPU）用于数据的运算。在大多数体系结构中，它有三个组成部分：
1. 算术逻辑单元（ALU）：对数据进行逻辑、移位和算术运算。
2. 控制单元：控制各个子系统的操作。
3. 寄存器：存放临时数据的高速独立的存储单元，CPU 的运算离不开大量寄存器的使用。可细分为数据寄存器、指令寄存器和程序计数器。
CPU 的主要职责是：从内存中逐条取出指令，并将取出的指令存储在指令寄存器中，解释并执行指令。

5.2 主存储器

主存储器是存储单元的集合，每一个存储单元都有唯一的标识，称为地址。数据以称为「字」的位组的形式在内存中传入和传出。字可以是 8 位、16 位、32 位，甚至有时是 64 位（还在增长），如果字是 8 位，一般称为 1 字节。
内存地址用无符号二进制整数定义。
随机存取存储器（RAM）与只读存储器（ROM）的区别在于，用户可读写 RAM，即用户可以在 RAM 中写信息，之后可以方便地通过覆盖来擦除原有信息。RAM 的另一个特点是易失性，当系统断电后，信息（程序或数据）将丢失。ROM 的内容是由制造商写进去的。用户只能读但不能写，它的有点是非易失性，当系统断电后，数据也不会丢失。通常用 ROM 存储关机后也不能丢失的程序或数据，例如开机时运行的程序。

5.3 输入/输出子系统

输入/输出设备可以分为两大类：非存储设备和存储设备。
在 I/O 独立寻址中，用来读/写内存的指令与用来读/写输入/输出设备的指令是完全不同的。有专门的指令完成对输入/输出设备的测试、控制以及读写操作。每个输入/输出设备有自己的地址。因为指令的不同，所以输出/输出地址可以和内存地址重叠而不会产生混淆。
在 I/O 存储器映射寻址中，CPU 将输入/输出控制器中的每一个寄存器都看作内存中的某个存储字。换言之，CPU 没有单独的指令用来表示从内存或是从输入/输出设备传送数据。

6 计算机网络和因特网

骨干网和供应商网络被称为因特网服务供应商（ISP）。骨干网通常被称为国际因特网服务供应商，供应商网络则被称为国内或地域性因特网服务供应商。
一个协议层（模块）可以定义为一个具有输入和输出而不需要考虑输入是如何变成输出的黑匣子。当向两台机器提供相同输入得到相同输出时，它们就可以相互替换。
用户数据协议（UDP）是不可靠的无连接传输协议。它除了提供进程间通信而不是主机间通信以外，没有向网络层服务添加任何东西。
传输控制协议（TCP）是一个面向连接的可靠协议。它明确定义了连接设施、数据传输和连接拆卸段以提供面向连接的数据。在传输层，TCP 将一些字节组合成叫作段的数据包。TCP 在每一段之前加上一个头（目的是方便控制），并且将这些段发送至网络层进行传输。

7 操作系统

一个作业是一个要运行的程序，一个进程则是在内存中等待分配资源的程序。
现代操作系统至少具有以下 4 种功能：内存管理、进程管理、设备管理、文件管理。就像很多组织有一个部分不归任何经理管理一样，操作系统也有这样一个部分，称为用户界面或命令解释程序，它负责操作系统与外界的通信。

8 算法

定义：
- 非正式：算法是一种逐步解决问题或完成任务的方法。
- 正式：算法是一组明确步骤的有序结合，它产生结果并在有限的时间内终止。
- 可解问题的解法形式为一个可终止的算法。

递归解决问题有两条途径。首先将问题从高至低进行分解，然后从低到高解决它。

9 程序设计语言

9.1 演化

计算机唯一识别的语言是机器语言。
高级语言同汇编语言有一个共性：它们必须被转化为机器语言，这个转化过程被称为解释或编译。

9.2 翻译

高级语言程序被称为源程序。被翻译成的机器语言程序称为目标程序。有两种方法用于翻译：编译和解释。编译和解释的不同在于，编译在执行前翻译整个源代码，而解释一次只翻译和执行源代码中的一行。
编译程序通常把整个源程序翻译成目标程序。
解释是把源程序中的每一行翻译成目标程序中的行，并执行它的过程。
随着 Java 的到来，一种新的解释过程就被引入了。Java 语言能向任何计算机移植。为了取得可移植性，源程序到目标程序的翻译分成两步进行：编译和即使。Java 源程序首先被编译，创建 Java 的字节代码，字节代码看起来像机器语言中的代码，但不是任何特定计算机的目标代码，它是一种虚拟机的目标代码，该虚拟机被称为 Java 虚拟机或 JVM。字节代码然后能被任何运行 JVM 模拟器的计算机编译或解释，也就是运行字节代码的计算机只需要 JVM 模拟器，而不是 Java 编译器。

9.3 编程模式

当今计算机语言按照它们使用的解决问题的方法来分类。因此，模式是计算机语言看待要解决问题的一种方式。计算机语言可分成 4 中模式：过程式（强制性）、面向对象、函数式和声明式。

9.3.1 过程式模式

在过程式模式中，对象（文件）和过程（如 print）是完全分开的实体。对象（文件）是一个能接收 print 动作或其他一些动作（如删除、复制等）的独立实体。为了对文件应用这些动作中的任何一个，我们需要一个作用于文件的过程。过程 print （或复制、删除）是编写的一个独立实体，程序只是触发它。
我们需要把过程与程序触发区分开。程序不定义过程，它只触发或调用过程。过程必须已经存在。
过程式模式的程序由三部分构成：对象创建部分、一组过程调用和每个过程的一组代码。

9.3.2 面向对象模式

面向对象模式处理活动对象，而不是被动对象。
在面向对象模式中的文件能把所有的被文件执行的过程（在面向对象模式中称为方法）打包在一起，这些过程有打印、复制、删除等。在这种模式中的程序仅仅向对象发送相应请求（打印、复制、删除等），文件就会被打印、复制、删除。
比较过程式模式和面向对象模式，可以看出过程式模式中的过程是独立的实体，但面向对象模式中的方法是属于对象领地的。
总体上，方法的格式与有些过程式语言中的函数非常相似。每个方法有它的头、局部变量和语句。这就意味着我们对过程式语言所讨论的大多数特性都可以应用在为面向对象程序所写的方法上。换言之，我们可以认为面向对象语言实际上是带有新的理念和新的特性的过程式语言的拓展。
多态性意思“许多形状”。在面向对象模式中的多态性是指我们可以定义一些具有相同名字的操作，而这些操作在相关类中做不同的事情。
在 Java 中，程序的执行也是独具特色的。构建一个类并把它传给编译器，由编译器来调用类的方法。Java 的另一大有趣的特点是多线程。线程是指按顺序执行的动作序列。C++ 只允许单线程执行（整个程序作为单线程），但是 Java 允许多线程执行（几行代码同时执行）。

9.3.3 函数式模式

在函数式模式中程序被看成是一个数学函数。关于这一点，函数是把一组输入映射到一组输出的黑盒子。
函数式语言相对过程式语言具有两方面优势：它支持模块化变成并且允许程序员使用已经存在的函数来开发新的函数。这两个因素使得程序员能够编写出庞大而且不易出错的程序。

9.3.4 声明式模式

声明式模式依据逻辑推理的原则响应查询。
声明性语言也有自身的缺憾，那就是有关特殊领域的程序由于要收集大量的事实信息而变得非常庞大。这也是说明性程序迄今为止只局限于人工智能等领域的原因。

9.4 共同概念

字面值是程序中使用的预定义的值。在大多数程序车技语言中，可以有整数、实数、字符和布尔字面值，还可以有字符串字面值。为了把字符和字符串字面值从变量名和其他对象中区分开，大多数语言要求字符字面值被括在单引号中，而字符串字面值被括在双引号中。
传值有个优点：子程序接收的仅仅是个值。它不能改变（有意或无意）主程序中变量的值。但是，当程序实际上要求子程序这样做时，子程序不能改变主程序中变量的值就变成了缺点。
传引用被设计来允许子程序改变主程序中变量的值。在传引用中，变量（实际上它是内存的地址）被主程序和子程序共享。相同的变量可能在主程序和子程序中有不同的名字，但两个名字是指向同一个变量。我们可以形象地把传引用看成是有两个门的盒子，一个开在主程序；另一个开在子程序。主程序可以把值留在盒子里给子程序，子程序可以改变这个原始的值，并留个新值给主程序。

10 软件工程

10.1 设计阶段

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

10.2 测试阶段

10.2.1 白盒测试

使用软件结构的白盒测试需要保证至少满足下面 4 条标准：
1. 每个模块中所有独立的路径至少被测试过一次。
2. 所有的判断结构（两路的或多路的）每个分支都被测试。
3. 每个循环被测试。
4. 所有数据结构都被测试。
基本路径测试是一种软件中每条语句至少被执行一次的方法。基本路径测试使用图论和图复杂性找到必须被走过的独立路径，从而保证每条语句至少被执行一次。

10.2.2 黑盒测试

几种黑盒测试方法：
1. 穷尽测试
2. 随机测试
3. 边界值测试

10.3 文档

通常软件有三种独立的文档：用户文档、系统文档和技术文档。注意，文档是一个持续的过程。如果软件在发布之后有问题，也必须写文档。如果软件被修改，那么所有的修改与原软件包间的关系都要被写进文档。只有当软件包过时后，编写文档才停止。
一个好的用户手册能够成为一个功能强大的营销工具。用户文档在营销中的重要性再强调也不过分。手册应该面向新手和专业用户。配有好的用户文档必定有利于软件的销量。

11 数据结构

当需要进行的插入和删除操作数目较少，而需要大量的查找和检索操作时，数组是合适的结构。
把字符串放在双引号之间，而单个字符放在单引号之间，这个是大多数编程语言通常使用的。
如果需要大量的插入和删除，那么链表是合适的结构，但查找一个链表比查找一个数组要慢。

12 抽象数据类型

对于一个抽象数据类型（ADT），用户不用关心任务是如何完成的，而是关心能做什么。换言之，ADT 包含了一组允许程序员使用的操作的定义，而这些操作的实现是隐藏的。这种不需详细说明实现过程的泛化被称为抽象。我们抽取了过程的本质，而隐藏了实现的细节。

12.1 栈

栈是一种限制线性表，该类列表的添加和删除操作只能在一端实现，称为“栈顶”。如果将一系列数据插入栈中，然后移走它们，那么数据的顺序将被倒转。数据插入时的顺序为 5, 10, 15, 20，移走后顺序就变成 20, 15, 10, 5。这种倒转的属性也正是栈被称为后进后出（LIFO）数据结构的原因。
栈的基本操作有四种：建栈、入栈、出栈和空。
栈的应用可以分为 4 大类：倒转数据、配对数据、数据延迟使用和回溯操作。

12.2 队列

队列是一种线性表，该表中的数据只能在称为尾部的一端插入，并且只能在称为头部的一端删除。这些限制确保了数据在队列中只能按照它们存入的顺序被处理。换言之，队列就是先进先出（FIFO）结构。
队列的基本操作有四种：建队列、入队、出队和空。
队列的一个常用应用是调节和建立数据的快速生成和缓慢消费间的平衡。

12.3 广义线性表

广义线性表是像插入和删除等操作可以在其中任何地方进行的表，可以在表头、表中间或表尾。
广义线性表的常用操作：建表、插入、删除、检索、遍历和空。
广义线性表可应用于元素被随机存取或顺序存取的情况。

12.4 树

二叉树是没有一个节点所含有的子树超过两个的树。
二叉树的递归定义：二叉树是一颗空树或由一个根节点和两个子树构成，且每棵子树也是二叉树。
二叉树的常用操作：建树、插入、删除、检索、遍历和空。
二叉树的遍历
- 深度优先遍历
  - 前序遍历：根 -> 左子树 -> 右子树
  - 中序遍历：左子树 -> 根 -> 右子树
  - 后序遍历：根在左右子树处理后才处理
- 广度优先遍历
虽然我们在编程语言中使用中缀表示，但编译程序经常在计算表达式之前需要把它们转为后缀表达。进行转换的一种方法就是建议表达式树。在表达式树中，根和内部节点是操作符，而叶子是操作数。中序遍历产生中缀表达式，后续遍历产生后缀表达式，前序遍历产生前缀表达式。只有中缀表达式需要括号。
二叉搜索树（BST）中每个节点的关键字值大于左子树中所有节点的关键字值，而小于右子树中所有节点的关键字值。
二叉搜索树的中序遍历创建了一个升序列表。

12.5 图

图可分为有向或无向。

13 文件结构

在设计一个文件时，关键问题是如何从文件中检索信息（一个特定的记录）。存取方法决定了怎样检索记录：顺序的或随机的。
索引文件和散列文件都允许随机存取。

13.1 索引文件

索引文件由数据文件组成，它是带索引的顺序文件。索引本身非常小，只占两个字段：顺序文件的键和在磁盘上相应记录的地址。
索引文件的好处之一就是可以有多个索引，每个索引有不同的键。例如，职员的文件可以按社会保险号或姓名来检索。这种索引文件被称为倒排文件。

13.2 散列文件

在索引文件中，索引将键映射到地址。散列文件用一个数学函数来完成映射。用户给出键，函数将键映射成地址，再传送给操作系统，这样就可以检索记录了。散列文件无需额外的文件（索引）。
散列方法有直接散列法、求模法、数字析取散列法等。
同义词指的是列表中一些映射为同一地址的键。
如果插入列表的实际数据中有两个或多个同义词，将产生冲突。冲突的产生是在散列算法为插入键产生地址时，发现该地址已被占用。由散列算法产生的地址称为内部地址。包含所有内部地址的区域称为主区。当两个键在内部地址上冲突时，必须将其中一个键和数据存放到主区外的另一个地址单元来解决冲突。
冲突解决方法有：开放寻址、链表解决法、桶散列法（可能有很多浪费的存储单元）。

14 数据库

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

15 数据压缩

15.1 无损压缩方法

游程长度编码可以用来压缩由任何符号组成的数据。它不需要知道字符出现频率的有关知识（赫夫曼编码需要）。
赫夫曼编码对于出现更为频繁的字符分配较短的编码，而对于出现较少的字符分配较长的编码。

15.2 有损压缩方法

包括图像压缩（JPEG）、视频压缩（MPEG）和音频压缩。

16 安全

三个安全目标：机密性、完整性和可用性。
完整性的意思是变化只应该由授权的实体通过授权的机制来完成。完整性冲突不一定是由于恶意行为造成的，也可能是系统终端造成的对信息的一些不希望的改动。
对机密性的威胁：嗅探、流量分析。
对完整性的威胁：篡改、假冒、重放、抵赖。
对可用性的威胁：拒绝服务。

16.1 机密性

对称密钥密码术基于共享保密，对字符进行排列或替换；非对称密钥密码术基于个人保密，对数字进行操作。
非对称密钥密码术意味着 Bob 只需要一个私钥就能从团体中任何人那里接收信息。但 Alice 需要 n 个公钥与团队中的 n 个人进行通信。一人一个公钥。
非对称密钥密码术通常用来加密或解密小段信息（如对称密钥密码术中的密码密钥）。

16.2 其他安全服务

为了保证消息完整性，消息要通过一个成为密码散列函数的算法。函数建立消息的压缩影响（称为摘要），这个影像就像指纹一样使用。
密码系统使用接收者的私钥和公钥；数字签名使用发送者的私钥和公钥。

17 计算理论

17.1 简单语言

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

17.2 图灵机

图灵机由三部分组成：磁带、控制器和读/写头。
邱奇-图灵论题：如果存在一个能完成一个符号操纵任务的算法，那么也存在一台完成这个任务的图灵机。
在计算机科学理论中，一个无符号数能被分配给任何用特定语言编写的程序，通常被称为哥德尔数。
停机问题不可解。

17.3 问题复杂度

如果程序的复杂度为 $O(\log n)$、$O(n)$、$O(n^2)$ 或 $O(n^k)$，则被称为多项式问题。
如果一个程序的复杂度远比多项式问题复杂，例如 $O(10^n)$ 或 $O(n!)$，当输入数很小（小于 100）时，这种问题可以解决。如果输入数很大，则需要做坐在计算机面前等上几个月的时间才能看到非多项式问题的解决结果。

18 人工智能

人工智能是对程序系统的研究，该程序系统在一定程度上能模仿人类的活动，如感知、思考、学习和反应。
虽然有些通用语言（如 C、C++ 和 Java）能用来编写智能软件，但有两种语言是特别为人工智能设计的，它们是 LISP 和 PROLOG。

18.1 知识表示

如果打算用人工智能体来解决现实世界中的一些问题，那么它必须能表示知识。事实被表示成数据结构后就能被存储在计算机中的程序操纵。常见的 4 种知识表示方法：语义网、框架、谓词逻辑和基于规则的系统。
语义网能很好定义的最重要的关系是「继承」。继承关系定义明了这样一个事实：一个类的所有属性将出现在继承的类中。这可以用来从用图表示的知识中推导出新的知识。

18.2 专家系统

一个专家系统是建立在预先定义的关于领域专家经验的知识的基础上的。（知识抽取）
为了能推导新的事实或采取动作，除了需要用知识表示语言表示的知识库外，还需要事实库。（事实抽取）

--- title: "计算机科学导论" subtitle: "原书第4版" date: "2023-08-13" date-modified: "2023-09-01" image: "cover.jpg" categories: - Computer Science --- ```{r} #| include: false 1 + 1 ``` ::: {.callout-note title='Progress'} `r stfun::progress(463, 463)` ::: ::: {.callout-tip title="Learning Source"} - 贝赫鲁兹·佛罗赞. 计算机科学导论（原书第4版）[M]. 吕云翔, 杨洪洋, 曾洪立译. 机械工业出版社, 2020. ::: # 绪论 ## 图灵模型 - Alan Turing（阿兰·图灵）在 1936 年最先提出了一个通用计算设备的设想。他认为，所有的计算都可以在一种特殊的机器上执行，这就是现在所说的**图灵机**。 - **通用图灵机**是对现代计算机的首次描述，只要提供了合适的程序，该机器就能做任何运算。可以证明，一台很强大的计算机和通用图灵机一样能进行同样的运算。 ## 冯·诺依曼模型 - 1944 ~ 1945 年，冯·诺依曼指出，鉴于程序和数据在逻辑上是相同的，因此程序也能存储在计算机的存储器中。 ## 计算机组成部分 - 冯·诺依曼模型要求程序必须是有序的指令集。 ## 计算机科学作为一门学科 - 如同其他任何学科一样，计算机科学现在被划分成几个领域。我们可以把这些领域归纳为两大类：**系统领域**和**应用领域**。系统领域涵盖那些与硬件和软件构成直接有关的领域，例如计算机体系结构、计算机网络、安全问题、操作系统、算法、程序设计语言以及软件工程。应用领域涵盖了与计算机使用有关的领域，例如数据库和人工智能。 # 数字系统 ## 位置化数字系统在位置化数字系统中，数字中符号所占的位置决定了其表示的值。在该系统中，数字这样表示： $$ \pm(S_{K-1} \cdots S_2 S_1 S_0. S_{-1} S{_-2} \cdots S_{-L})_b $$ 它的值是： $$ n = \pm \left( S_{K-1} \times b^{K-1} + \cdots + S_1 \times b^1 + S_0 \times b^0 + S_{-1} \times b^{-1} + S_{-2} \times b^{-2} + \cdots + S_{-L} \times b^{-L} \right) $$ 其中，$S$ 是一套符号集，$b$ 是底（或基数），它等于 $S$ 符号集中的符号总数，其中 $S_K$ 和 $S_L$ 分别是代表整数和小数部分的符号。 - 我们使用 $\pm$ 符号表示一个数可正可负，但这些符号并不存储在计算机中——计算机用以处理该符号的方式不同。 - 十进制不像二进制那样直接显示存储在计算机中的是什么。在二进制位数和十进制数码的数量之间没有显然的关系，它们之间的转换也不快捷。为了克服这个问题，发明了两种位置化系统：十六进制和八进制。 - 可以用数码 $K$ 表示的最大值： - 十进制整数的最大值为：$N_{\text{max}} = 10^K - 1$ - 二进制整数的最大值为：$N_{\text{max}} = 2^K - 1$ - 十六进制整数的最大值为：$N_{\text{max}} = 16^K - 1$ - 八进制整数的最大值为：$N_{\text{max}} = 8^K - 1$ ## 非位置化数字系统 - 非位置化数字系统仍然使用有限的数字符号，每个符号都有一个值。但是符号所占用的位置通常与其值无关——每个符号的值都是固定的。为求出该数字的值，我们把所有符号表示的值相加。比如罗马数字系统。 # 数据存储 ## 数据类型 - 为了表示数据的不同类型，应该使用**位模式**，它是一个序列，有时也被称为**位流**。通常长度为 8 的位模式被称为 1 字节。有时用**字**这个术语指代更长的位模式。 ## 存储数字 ### 存储整数 - 整数通常使用顶点表示法存储在内存中。 - 只要用不到负整数，都可以用无符号整数表示法。具体情况如下： - 计数 - 计算机寻址 - 存储其他数据类型（文本、图形、音频和视频） - 在符号加绝对值表示法中，最左位用于定义整数符号。0 表示正整数，1 表示负整数。在 n 位单元可存储的数字范围是 $-\left( 2^{n-1} - 1\right)$ 至 $+\left( 2^{n-1} - 1 \right)$。 - **反码运算**：反转各个位，即把 0 位变为 1 位，把 1 位变为 0 位。可应用于任何整数，无论正负。 - **补码运算**：从右边复制位，直到有 1 被复制；接着反转其余的位。另一种方法是先对它进行 1 次反码运算再加上 1 得到结果。2 次补码运算可以得到原先的整数。 - 以二进制补码格式存储整数： 1. 将整数变成 n 位的二进制数； 1. 如果整数是正数或零，以其原样存储；如果是负数，取其补码存储。 - 从二进制补码格式还原整数 1. 如果最左位是 1，取其补码；如果最左位是 0，不进行操作； 1. 将该整数转换为十进制。 - 二进制补码表示法仅有一个 0，而符号加绝对值表示法则有两个 0（+0 和 -0）。 ### 实数 - 一个数字的浮点表示法由 3 部分组成：符号、位移量和定点数。 # 数据运算 ## 逻辑运算 - AND 运算的一个应用就是把一个位模式的指定位复位（置 0）。这种情况下的第二个输入称为**掩码**。掩码中的 0 位对第一个输入中相应的位进行复位。掩码中的 1 位使得第一个输入中相应的位保持不变。 - OR 运算的一个应用是把一个位模式的指定位置位（置 1）。掩码中的 1 位对第一个输入中相应的位进行置位，而掩码中的 0 位使第一个输入中相应的位保持不变。 - XOR 运算的一个应用是使指定的位反转。掩码中的 1 位对第一个输入中相应的位进行反转，而掩码中的 0 位使第一个输入中相应的位保持不变。 ## 移位运算 - 移位运算分为两大类：逻辑移位运算和算术移位运算。 - 算术移位运算假定位模式使用二进制补码格式表示的带符号位的证书。算术右移被用来对整数除以 2；而算术左移被用来对整数乘以 2。这些运算不应该改变符号位（最左）。算术右移保留符号位，但同时也把它复制，放入相邻的右边的位中，因此符号被保存。算术左移丢弃符号位，接受它的左边的位作为符号位。如果新的符号位与原先的相同，那么运算成功，否则发生上溢或下溢，结果是非法的。 # 计算机组成 - 计算机的组成部件可以分为三大类（或子系统）：中央处理单元（CPU）、主存储器和输入/输出子系统。 ## 中央处理单元 - **中央处理单元**（CPU）用于数据的运算。在大多数体系结构中，它有三个组成部分： 1. 算术逻辑单元（ALU）：对数据进行逻辑、移位和算术运算。 1. 控制单元：控制各个子系统的操作。 1. 寄存器：存放临时数据的高速独立的存储单元，CPU 的运算离不开大量寄存器的使用。可细分为数据寄存器、指令寄存器和程序计数器。 - CPU 的主要职责是：从内存中逐条取出指令，并将取出的指令存储在指令寄存器中，解释并执行指令。 ## 主存储器 - **主存储器**是存储单元的集合，每一个存储单元都有唯一的标识，称为**地址**。数据以称为「字」的位组的形式在内存中传入和传出。字可以是 8 位、16 位、32 位，甚至有时是 64 位（还在增长），如果字是 8 位，一般称为 1 字节。 - 内存地址用无符号二进制整数定义。 - 随机存取存储器（RAM）与只读存储器（ROM）的区别在于，用户可读写 RAM，即用户可以在 RAM 中写信息，之后可以方便地通过覆盖来擦除原有信息。RAM 的另一个特点是易失性，当系统断电后，信息（程序或数据）将丢失。ROM 的内容是由制造商写进去的。用户只能读但不能写，它的有点是非易失性，当系统断电后，数据也不会丢失。通常用 ROM 存储关机后也不能丢失的程序或数据，例如开机时运行的程序。 ## 输入/输出子系统 - 输入/输出设备可以分为两大类：非存储设备和存储设备。 - 在 **I/O 独立寻址**中，用来读/写内存的指令与用来读/写输入/输出设备的指令是完全不同的。有专门的指令完成对输入/输出设备的测试、控制以及读写操作。每个输入/输出设备有自己的地址。因为指令的不同，所以输出/输出地址可以和内存地址重叠而不会产生混淆。 - 在 **I/O 存储器映射寻址**中，CPU 将输入/输出控制器中的每一个寄存器都看作内存中的某个存储字。换言之，CPU 没有单独的指令用来表示从内存或是从输入/输出设备传送数据。 # 计算机网络和因特网 - 骨干网和供应商网络被称为**因特网服务供应商**（ISP）。骨干网通常被称为国际因特网服务供应商，供应商网络则被称为国内或地域性因特网服务供应商。 - 一个协议层（模块）可以定义为一个具有输入和输出而不需要考虑输入是如何变成输出的黑匣子。当向两台机器提供相同输入得到相同输出时，它们就可以相互替换。 - **用户数据协议**（UDP）是不可靠的无连接传输协议。它除了提供进程间通信而不是主机间通信以外，没有向网络层服务添加任何东西。 - **传输控制协议**（TCP）是一个面向连接的可靠协议。它明确定义了连接设施、数据传输和连接拆卸段以提供面向连接的数据。在传输层，TCP 将一些字节组合成叫作**段**的数据包。TCP 在每一段之前加上一个头（目的是方便控制），并且将这些段发送至网络层进行传输。 # 操作系统 - 一个作业是一个要运行的程序，一个进程则是在内存中等待分配资源的程序。 - 现代操作系统至少具有以下 4 种功能：内存管理、进程管理、设备管理、文件管理。就像很多组织有一个部分不归任何经理管理一样，操作系统也有这样一个部分，称为用户界面或**命令解释程序**，它负责操作系统与外界的通信。 # 算法 - 定义： - 非正式：算法是一种逐步解决问题或完成任务的方法。 - 正式：算法是一组明确步骤的有序结合，它产生结果并在有限的时间内终止。 - 可解问题的解法形式为一个可终止的算法。  - 递归解决问题有两条途径。首先将问题从高至低进行分解，然后从低到高解决它。 # 程序设计语言 ## 演化 - 计算机唯一识别的语言是机器语言。 - 高级语言同汇编语言有一个共性：它们必须被转化为机器语言，这个转化过程被称为**解释**或**编译**。 ## 翻译 - 高级语言程序被称为**源程序**。被翻译成的机器语言程序称为**目标程序**。有两种方法用于翻译：**编译**和**解释**。编译和解释的不同在于，编译在执行前翻译整个源代码，而解释一次只翻译和执行源代码中的一行。 - 编译程序通常把整个源程序翻译成目标程序。 - 解释是把源程序中的每一行翻译成目标程序中的行，并执行它的过程。 - 随着 Java 的到来，一种新的解释过程就被引入了。Java 语言能向任何计算机移植。为了取得可移植性，源程序到目标程序的翻译分成两步进行：编译和即使。Java 源程序首先被编译，创建 Java 的**字节代码**，字节代码看起来像机器语言中的代码，但不是任何特定计算机的目标代码，它是一种虚拟机的目标代码，该虚拟机被称为 Java 虚拟机或 JVM。字节代码然后能被任何运行 JVM 模拟器的计算机编译或解释，也就是运行字节代码的计算机只需要 JVM 模拟器，而不是 Java 编译器。 ## 编程模式 - 当今计算机语言按照它们使用的解决问题的方法来分类。因此，模式是计算机语言看待要解决问题的一种方式。计算机语言可分成 4 中模式：**过程式**（强制性）、**面向对象**、**函数式**和**声明式**。 ### 过程式模式 - 在过程式模式中，对象（文件）和过程（如 `print`）是完全分开的实体。对象（文件）是一个能接收 `print` 动作或其他一些动作（如删除、复制等）的独立实体。为了对文件应用这些动作中的任何一个，我们需要一个作用于文件的过程。过程 `print` （或复制、删除）是编写的一个独立实体，程序只是触发它。 - 我们需要把过程与程序触发区分开。程序不定义过程，它只触发或调用过程。过程必须已经存在。 - 过程式模式的程序由三部分构成：对象创建部分、一组过程调用和每个过程的一组代码。 ### 面向对象模式 - 面向对象模式处理活动对象，而不是被动对象。 - 在面向对象模式中的文件能把所有的被文件执行的过程（在面向对象模式中称为**方法**）打包在一起，这些过程有打印、复制、删除等。在这种模式中的程序仅仅向对象发送相应请求（打印、复制、删除等），文件就会被打印、复制、删除。 - 比较过程式模式和面向对象模式，可以看出过程式模式中的过程是独立的实体，但面向对象模式中的方法是属于对象领地的。 - 总体上，**方法**的格式与有些过程式语言中的函数非常相似。每个方法有它的头、局部变量和语句。这就意味着我们对过程式语言所讨论的大多数特性都可以应用在为面向对象程序所写的方法上。换言之，我们可以认为面向对象语言实际上是带有新的理念和新的特性的过程式语言的拓展。 - **多态性**意思“许多形状”。在面向对象模式中的多态性是指我们可以定义一些具有相同名字的操作，而这些操作在相关类中做不同的事情。 - 在 Java 中，程序的执行也是独具特色的。构建一个类并把它传给编译器，由编译器来调用类的方法。Java 的另一大有趣的特点是**多线程**。线程是指按顺序执行的动作序列。C++ 只允许单线程执行（整个程序作为单线程），但是 Java 允许多线程执行（几行代码同时执行）。 ### 函数式模式 - 在函数式模式中程序被看成是一个数学函数。关于这一点，函数是把一组输入映射到一组输出的黑盒子。 - 函数式语言相对过程式语言具有两方面优势：它支持模块化变成并且允许程序员使用已经存在的函数来开发新的函数。这两个因素使得程序员能够编写出庞大而且不易出错的程序。 ### 声明式模式 - 声明式模式依据逻辑推理的原则响应查询。 - 声明性语言也有自身的缺憾，那就是有关特殊领域的程序由于要收集大量的事实信息而变得非常庞大。这也是说明性程序迄今为止只局限于人工智能等领域的原因。 ## 共同概念 - **字面值**是程序中使用的预定义的值。在大多数程序车技语言中，可以有整数、实数、字符和布尔字面值，还可以有字符串字面值。为了把字符和字符串字面值从变量名和其他对象中区分开，大多数语言要求字符字面值被括在单引号中，而字符串字面值被括在双引号中。 - **传值**有个优点：子程序接收的仅仅是个值。它不能改变（有意或无意）主程序中变量的值。但是，当程序实际上要求子程序这样做时，子程序不能改变主程序中变量的值就变成了缺点。 - **传引用**被设计来允许子程序改变主程序中变量的值。在传引用中，变量（实际上它是内存的地址）被主程序和子程序共享。相同的变量可能在主程序和子程序中有不同的名字，但两个名字是指向同一个变量。我们可以形象地把传引用看成是有两个门的盒子，一个开在主程序；另一个开在子程序。主程序可以把值留在盒子里给子程序，子程序可以改变这个原始的值，并留个新值给主程序。 # 软件工程 ## 设计阶段 - 软件系统中模块间的耦合必须最小化。 - 软件系统中模块间的内聚必须最大化。 ## 测试阶段 ### 白盒测试 - 使用软件结构的白盒测试需要保证至少满足下面 4 条标准： 1. 每个模块中所有独立的路径至少被测试过一次。 1. 所有的判断结构（两路的或多路的）每个分支都被测试。 1. 每个循环被测试。 1. 所有数据结构都被测试。 - 基本路径测试是一种软件中每条语句至少被执行一次的方法。基本路径测试使用图论和图复杂性找到必须被走过的独立路径，从而保证每条语句至少被执行一次。 ### 黑盒测试 - 几种黑盒测试方法： 1. 穷尽测试 1. 随机测试 1. 边界值测试 ## 文档 - 通常软件有三种独立的文档：用户文档、系统文档和技术文档。注意，文档是一个持续的过程。如果软件在发布之后有问题，也必须写文档。如果软件被修改，那么所有的修改与原软件包间的关系都要被写进文档。只有当软件包过时后，编写文档才停止。 - 一个好的用户手册能够成为一个功能强大的营销工具。用户文档在营销中的重要性再强调也不过分。手册应该面向新手和专业用户。配有好的用户文档必定有利于软件的销量。 # 数据结构 - 当需要进行的插入和删除操作数目较少，而需要大量的查找和检索操作时，数组是合适的结构。 - 把字符串放在双引号之间，而单个字符放在单引号之间，这个是大多数编程语言通常使用的。 - 如果需要大量的插入和删除，那么链表是合适的结构，但查找一个链表比查找一个数组要慢。 # 抽象数据类型 - 对于一个**抽象数据类型**（ADT），用户不用关心任务是如何完成的，而是关心能做什么。换言之，ADT 包含了一组允许程序员使用的操作的定义，而这些操作的实现是隐藏的。这种不需详细说明实现过程的泛化被称为**抽象**。我们抽取了过程的本质，而隐藏了实现的细节。 ## 栈 - 栈是一种限制线性表，该类列表的添加和删除操作只能在一端实现，称为“栈顶”。如果将一系列数据插入栈中，然后移走它们，那么数据的顺序将被倒转。数据插入时的顺序为 `5, 10, 15, 20`，移走后顺序就变成 `20, 15, 10, 5`。这种倒转的属性也正是栈被称为**后进后出**（LIFO）数据结构的原因。 - 栈的基本操作有四种：建栈、入栈、出栈和空。 - 栈的应用可以分为 4 大类：倒转数据、配对数据、数据延迟使用和回溯操作。 ## 队列 - 队列是一种线性表，该表中的数据只能在称为**尾部**的一端插入，并且只能在称为**头部**的一端删除。这些限制确保了数据在队列中只能按照它们存入的顺序被处理。换言之，队列就是**先进先出**（FIFO）结构。 - 队列的基本操作有四种：建队列、入队、出队和空。 - 队列的一个常用应用是调节和建立数据的快速生成和缓慢消费间的平衡。 ## 广义线性表 - 广义线性表是像插入和删除等操作可以在其中任何地方进行的表，可以在表头、表中间或表尾。 - 广义线性表的常用操作：建表、插入、删除、检索、遍历和空。 - 广义线性表可应用于元素被随机存取或顺序存取的情况。 ## 树 - 二叉树是没有一个节点所含有的子树超过两个的树。 - 二叉树的递归定义：二叉树是一颗空树或由一个根节点和两个子树构成，且每棵子树也是二叉树。 - 二叉树的常用操作：建树、插入、删除、检索、遍历和空。 - 二叉树的遍历 - 深度优先遍历 - 前序遍历：根 -> 左子树 -> 右子树 - 中序遍历：左子树 -> 根 -> 右子树 - 后序遍历：根在左右子树处理后才处理 - 广度优先遍历 - 虽然我们在编程语言中使用中缀表示，但编译程序经常在计算表达式之前需要把它们转为后缀表达。进行转换的一种方法就是建议**表达式树**。在表达式树中，根和内部节点是操作符，而叶子是操作数。中序遍历产生中缀表达式，后续遍历产生后缀表达式，前序遍历产生前缀表达式。只有中缀表达式需要括号。 - **二叉搜索树**（BST）中每个节点的关键字值大于左子树中所有节点的关键字值，而小于右子树中所有节点的关键字值。 - 二叉搜索树的中序遍历创建了一个升序列表。 ## 图 - 图可分为有向或无向。 # 文件结构 - 在设计一个文件时，关键问题是如何从文件中检索信息（一个特定的记录）。存取方法决定了怎样检索记录：顺序的或随机的。 - 索引文件和散列文件都允许随机存取。 ## 索引文件 - 索引文件由数据文件组成，它是带索引的顺序文件。索引本身非常小，只占两个字段：顺序文件的键和在磁盘上相应记录的地址。 - 索引文件的好处之一就是可以有多个索引，每个索引有不同的键。例如，职员的文件可以按社会保险号或姓名来检索。这种索引文件被称为倒排文件。 ## 散列文件 - 在索引文件中，索引将键映射到地址。散列文件用一个数学函数来完成映射。用户给出键，函数将键映射成地址，再传送给操作系统，这样就可以检索记录了。散列文件无需额外的文件（索引）。 - 散列方法有直接散列法、求模法、数字析取散列法等。 - 同义词指的是列表中一些映射为同一地址的键。 - 如果插入列表的实际数据中有两个或多个同义词，将产生冲突。冲突的产生是在散列算法为插入键产生地址时，发现该地址已被占用。由散列算法产生的地址称为**内部地址**。包含所有内部地址的区域称为**主区**。当两个键在内部地址上冲突时，必须将其中一个键和数据存放到主区外的另一个地址单元来解决冲突。 - 冲突解决方法有：开放寻址、链表解决法、桶散列法（可能有很多浪费的存储单元）。 # 数据库 - 数据库是一个组织内被应用程序使用的逻辑相一致的相关数据的集合。 # 数据压缩 ## 无损压缩方法 - **游程长度编码**可以用来压缩由任何符号组成的数据。它不需要知道字符出现频率的有关知识（赫夫曼编码需要）。 - **赫夫曼编码**对于出现更为频繁的字符分配较短的编码，而对于出现较少的字符分配较长的编码。 ## 有损压缩方法 - 包括图像压缩（JPEG）、视频压缩（MPEG）和音频压缩。 # 安全 - 三个安全目标：机密性、完整性和可用性。 - **完整性**的意思是变化只应该由授权的实体通过授权的机制来完成。完整性冲突不一定是由于恶意行为造成的，也可能是系统终端造成的对信息的一些不希望的改动。 - 对机密性的威胁：嗅探、流量分析。 - 对完整性的威胁：篡改、假冒、重放、抵赖。 - 对可用性的威胁：拒绝服务。 ## 机密性 - 对称密钥密码术基于共享保密，对字符进行排列或替换；非对称密钥密码术基于个人保密，对数字进行操作。 - 非对称密钥密码术意味着 Bob 只需要一个私钥就能从团体中任何人那里接收信息。但 Alice 需要 n 个公钥与团队中的 n 个人进行通信。一人一个公钥。 - 非对称密钥密码术通常用来加密或解密小段信息（如对称密钥密码术中的密码密钥）。 ## 其他安全服务 - 为了保证消息完整性，消息要通过一个成为**密码散列函数**的算法。函数建立消息的压缩影响（称为**摘要**），这个影像就像指纹一样使用。 - 密码系统使用接收者的私钥和公钥；数字签名使用发送者的私钥和公钥。 # 计算理论 ## 简单语言 - 我们可以仅用三条语句来定义一种语言，它们是：递增语句、递减语句和循环语句。 ## 图灵机 - 图灵机由三部分组成：磁带、控制器和读/写头。 - 邱奇-图灵论题：如果存在一个能完成一个符号操纵任务的算法，那么也存在一台完成这个任务的图灵机。 - 在计算机科学理论中，一个无符号数能被分配给任何用特定语言编写的程序，通常被称为**哥德尔数**。 - 停机问题不可解。 ## 问题复杂度 - 如果程序的复杂度为 $O(\log n)$、$O(n)$、$O(n^2)$ 或 $O(n^k)$，则被称为多项式问题。 - 如果一个程序的复杂度远比多项式问题复杂，例如 $O(10^n)$ 或 $O(n!)$，当输入数很小（小于 100）时，这种问题可以解决。如果输入数很大，则需要做坐在计算机面前等上几个月的时间才能看到**非多项式问题**的解决结果。 # 人工智能 - 人工智能是对程序系统的研究，该程序系统在一定程度上能模仿人类的活动，如感知、思考、学习和反应。 - 虽然有些通用语言（如 C、C++ 和 Java）能用来编写智能软件，但有两种语言是特别为人工智能设计的，它们是 LISP 和 PROLOG。 ## 知识表示 - 如果打算用人工智能体来解决现实世界中的一些问题，那么它必须能表示知识。事实被表示成数据结构后就能被存储在计算机中的程序操纵。常见的 4 种知识表示方法：语义网、框架、谓词逻辑和基于规则的系统。 - 语义网能很好定义的最重要的关系是「继承」。继承关系定义明了这样一个事实：一个类的所有属性将出现在继承的类中。这可以用来从用图表示的知识中推导出新的知识。 ## 专家系统 - 一个专家系统是建立在预先定义的关于领域专家经验的知识的基础上的。（知识抽取） - 为了能推导新的事实或采取动作，除了需要用知识表示语言表示的知识库外，还需要事实库。（事实抽取）