计算机科学导论（第四版）¶

Foundations Of Computer Science (4^th Edition)

出版社	作者	年份
机械工业出版社	Behrouz A. Forouzan	2022

本书的阅读笔记将全部采用英文。仅在本概述部分列出中文目录

章节目录¶

第 1 章绪论 Introduction

第一部分：数据的表示与运算

第 2 章数字系统 Number Systems
第 3 章数据存储
第 4 章数据运算

第二部分：计算机硬件

第 5 章计算机组成
第 6 章计算机网络和因特网

第三部分：计算机软件

第 7 章操作系统
第 8 章算法
第 9 章程序设计语言 Programming Language
第 10 章软件工程

第四部分：数据组织与抽象

第 11 章数据结构
第 12 章抽象数据类型
第 13 章文件结构
第 14 章数据库

第五部分：高级话题

第 15 章数据压缩
第 16 章安全
第 17 章计算理论
第 18 章人工智能

第六部分：社交媒体和社会话题

第 19 章社交媒体导论
第 20 章社会和道德问题

附录

附录 A Unicode
附录 B UML
附录 C 伪代码
附录 D 结构图
附录 E 布尔代数和逻辑电路
附录 F C、C++ 和 Java 程序示例
附录 G 数学知识
附录 H 错误检测和纠正
附录 I 符号加绝对值整数的加减法
附录 J 实数的加减法

Ch1. 绪论¶

什么是图灵模型和冯·诺依曼模型

计算机是一种通用的机器，可以完成各种不同的工作。
图灵在1936年的论文《论可计算数及其在判定上的应用》中给出了图灵机的定义。
- 《论可计算数及其在判定上的应用》简单理解
- 原始论文：On Computable Numbers，with an Application to the Entscheidungsproblem
本书举了图灵机的一个例子——可编程数据处理器：由输入数据、输出数据、程序组成。
冯·诺依曼模型较图灵模型最大的改变，是将程序存储在存储器中。
- 冯·诺依曼模型由 4 个子系统组成：存储器、算术逻辑单元、控制单元、输入输出单元。
- 指令顺序执行。
现代计算机基于冯·诺依曼模型。

计算机的历史

机械计算器：1930 年以前
电子计算机：1930~1950 年
基于冯·诺依曼模型的计算机：1950 年至今
- 第一代计算机：真空管
- 第二代计算机 1959~1965：晶体管
- 第三代计算机 1965~1975：集成电路
- 第四代计算机 1975~1985：微型计算机、计算机网络
- 第五代计算机 1985~：掌上计算机、台式计算机、第二代存储媒体、多媒体、虚拟现实...

附录 B：UML 图¶

UML 是统一建模语言 Unified Modeling Language。它包括：用户视图、结构视图、行为视图和实现视图。

行为视图：
- 状态图：主要使用五种符号

Ch.2 数字系统¶

本章概要

本章主要目的是熟悉二进制、八进制、十进制和十六进制的计算。本书主要以算法形式给出，CSAPP 中有更多数学层面的讨论。

CSAPP：建议你反复阅读数学原理描述和示例与讨论，直到你对该属性的说明内容及其重要性有了牢固的直觉。对于更加复杂的属性，你应该尝试推导。

位置化数字系统、非位置化数字系统（罗马数字等）
其他进制到十进制的转换：直接计算
十进制到其他进制的转换（用 UML 图表示）
- 整数部分：连除
- 小数部分：连乘
将一个 $n$ 位十进制数转换为其他进制，怎么计算需要的位数？

Ch.3 数据储存¶

本章概要

简单介绍了数字、文本、音频、图像、视频是如何存储在计算机中的。这些描述都是概念性的，技术细节需要查阅相应数据格式的规范文档。

描述以下存储整数的方法：它们能存储哪些数字？存储、还原的步骤是怎样的？主要应用在哪里？溢出情况如何？
- 无符号表示法
- 符号加绝对值表示法（原码）
- 二进制补码表示法
- 反码表示法（本书未介绍）

CSAPP：理解补码表示的方法：把最高位看作权重为$-2^{w-1}$的位

尝试给出反码运算的数学表达式，并理解反码的表达式是如何构建的？

注意反码操作和整数的反码表示。反码表示的整数中，只有负数才进行反码操作。

实数的储存：浮点表示法（具有很大整数部分或很小小数部分的数）：符号、位移量和定点数

规范化：定点数小数点左侧只有一个非零数码。二进制数规范化后，左侧的 1 隐含了。
十进制称为科学计数法，二进制称为浮点表示法
尾数：小数点右边的二进制数定义了该数的精度，作为无符号整数存储
指数：有符号，使用余码系统：偏移量$(2^{m-1}-1)$被加到每个数字中（m 为内存单元大小），统一移到非负的一遍。如 4 位存储单元使用余 7 码系统。这样做的优势是对这些整数进行比较或运算时不需要考虑符号。
IEEE 标准：单进度为 1，8，23；双精度为 1，11，52
储存：确定符号，转二进制，规范化，储存指数和尾数，连接三个部分
还原：拆分为三个部分，确定符号，解码位移量，去规范化尾数，还原数字，转十进制，加上符号
浮点数的上溢和下溢：举例单精度浮点数最大负值为$-(1-2^{-24})\times 2^{+128}$，其中，尾数 23 位无符号数，最大绝对值为$2^{24}-1$，指数 8 位余码数，最大为$2^{8-1}=128$。最小负值为$-(1-2^{-1})\times 2^{-127}$
零的约定：三个部分都设置为 0
什么是截断错误？

存储文本¶

补充知识：ASCII 和 Unicode

编码类型位数

ASCII 7

扩展 ASCII 8

Unicode 32

UNICODE 的编码结构¶

每个 Unicode 编码以十六进制表示为 U-XXXXXXXX

前 16 位定义平面

后 16 位定义字符

ASCII 占据 Unicode 中前 128 个编码，即 U-00000000 ~ U-0000007F

ASCII 表的记忆

关键字符十进制十六进制

空字符 0 00

空格 32 20

0 48 30

9 57 39

A 65 41

Z 90 5A

a 97 61

z 122 7A

删除 127 7F

存储音频¶

文本是数字数据的例子，音频是模拟数据的例子。

采样
采样率
量化：截取为最近整数值
编码
- 位深度：每样本位的位数
- 位率：每秒音频位数（位率）=深度 x 每秒样本数 $ R = B \times S$
声音编码标准：MP3（MPEG Layer3），S=44100，B=16，R=705600b/s，再去掉人耳无法识别的信息进行压缩

存储图像¶

光栅图或矢量图

光栅图¶

采样称为扫描，样本称为像素
解析度：扫描率，每英寸的方块记录多少像素。
色彩深度：
- 真彩色：24 位，每个三原色 RGB 表示为 8 位，每种色彩都由 0~255 之间表示
- 索引色：许多应用程序并不需要如此大的色彩范围，索引色仅使用其中的一部分，对其建立索引
图像编码标准：
- JPEG 使用真色彩，但压缩图像减少位的数量
- GIF 使用索引色模式

矢量图¶

由定义如何绘制形状的一系列命令构成。要显示图像时，系统依据图像的尺寸大小用相同的公式绘制图形。

TrueType，PostScript 和 CAD（计算机辅助设计）主要使用矢量图

存储视频¶

视频是随空间（单个图像）和时间（一系列图像）变化的信息表现

Ch4. 数据运算¶

关键词：算术运算、移位运算、逻辑运算

逻辑运算¶

位层次和模式层次上的逻辑运算

非、与、或和异或
思考：如何用其他运算符模拟异或？异或的特性
位模式的四种应用：求反、使指定的位复位（置 0）、对指定的位置位（置 1）、使指定的位反转
掩码

移位（Shift）运算¶

逻辑移位运算
- 不带符号位的数：这些移位运算可能改变数的符号
- 填 0 或循环移位（旋转运算）
算数移位运算
- 假定位模式是使用二进制补码存储的带符号整数。
- 算数右移对整数除二，算数左移对整数乘二，这些运算本不应该改变符号位
- 算数右移：保留符号位，并复制入右侧位中，因此保存符号
- 算数左移：丢弃符号位，接受左边为符号位。如果新符号位与原先相同，运算成功，否则发生溢出

算术运算¶

二进制补码中的加减法¶

遇到减法时，转变为加法，只需为第二个数求二进制的补
加法正常

深入理解原码，反码，补码的原理 ¶

花了很长时间理解补码的构造意图。自己理了一遍逻辑如下：

计算机只能进行加法，不能进行减法

由于位数的限制，加法相当于在模运算下进行

模运算下的加法可以看作一个闭环

由上面三条说明，我们的目标是：在模运算的闭环中用加法模拟减法

数学定义：

对于长度为 $\omega$ 的位向量，它的模为 $2^{\omega}$ ，这一位向量在长度 $0\sim 2^{\omega}-1$ 的环内

要用加法模拟减法 $a - b = c$ ，目的是找到 $d$ 使得 $ (a + d)mod 2^\omega = c$

画出这样一个环，很容易看出加到 $c$ 和减到 $c$ 合起来绕了一个圈，因此： $d = 2^\omega - b$

通过这一等式可以建立从负数 $-b$ 到 $x_d$ 的映射，这个映射把负整数 $b$ 映射为 $d = 2^\omega - b$ 的位模式， $d$ 的位模式就是 $-b$ 的补码表示

这样的映射就是补码操作：先取反码再+1

接下来再分析以上过程，以 0110 - 0010 = 0100 即 6-2=4 为例

$x$ 是一个负数

找到 $d=10000-0010=1110$。我们发现：$d$ 可以通过取反码再+1 的找到。

原理：$\({|x|}_反+|x| = 2^\omega-1$\)

$0110 + 1110 = 10100$ 取模后即为 $0100$

原理：负数的补码和它的绝对值相加等于模（本质是闭环内绕一圈的两种方法）

\[2^\omega = x_补 + |x| \]

由以上两式，我们得到了反码和补码的关系：$x_补={|x|}_反+1$

要把 $1110$ 映射为 $-2$ ，就需要把最左侧的权重设置为 $-8$

为什么把最左侧位的权重解释为 $-8$ 可以做到呢？其实就是进行了 $-16$ 的操作，反向转了一圈。$14-16=-2$

遇到一个有趣的题目：对于一个补码表示的系统，表达式~x的值是多少？

写出三个函数（数字到二进制补码，反码操作，二进制到数字），对分段函数分类讨论，容易得到，~x = $-1-x$

符号加绝对值（原码）表示的加减法¶

一共有四种不同的符号组合，需要考虑 8 种不同的情况

第一步，检查运算，统一为加法
第二步，用异或检查两数的符号一致性
第三步：若符号相同，绝对值相加；若符号不同，绝对值相减（减法原理同上，转换为补码加法），符号是绝对值较大的符号
- 此处需要考虑上溢：如果 $A\geq B$ 则有上溢（模运算后舍弃）
- 如果 $A < B$ 则无上溢，结果是一个负数，应当取其二进制补码（可以这样理解：绝对值部分使用了补码式的减法运算，结果仍然是补码表示。现在取补码就是转换为无符号整数模式，结合先前确定的符号位，就变回符号加绝对值表示）

值得注意的是，在该加减法中，符号位和绝对值分开计算。绝对值之间的减法运算仍然与补码相同。比如：17-22，

$ 0010001-0010110 = 0010001 + 1101010 = 1111011$，所得结果是补码表示，需要再进行一次补码以还原为无符号整数表示。

实数的加减法¶

将实数的加减法简化为小数点对齐后以符号加绝对值格式存储的两整数的加法和减法

统一为加法
去规范化
使指数相等
相加，处理上溢
规范化
四舍五入，停止

Ch.5 计算机组成¶

关键词：中央处理单元，主存，输入输出子系统

CPU¶

CPU 由哪三部分组成？他们各自的作用是什么？
你能说出哪些种类的寄存器？他们的作用是什么？
- PC，IR 是什么？

主存¶

字是什么？地址是什么？
地址空间是什么？64kb，1b 字长的主存有多少地址空间？

Note

单位	确切的字节数	近似
KB	$2^{10}$ 1024	$10^3$
megabyte	$2^{20}$ 1048576	$10^6$
gigabyte	$2^{30}$ 1073741824	$10^{9}$

一个有 N 字的主存需要多长的位模式来存储地址？
简述 RAM（SRAM，DRAM）和 ROM
- 电脑的内存是哪一种存储器？寄存器呢？
- ROM、PROM、EPROM、EEPROM、Flash Memory 分别是什么？

补充：逻辑电路标识

简述非门、与非门、或非门的电路实现：需要用几个电控开关？

再次思考：异或如何使用与门或门模拟？

我的解决方案：$x XOR y = (x OR y) AND (NOT(xANDy))$这是观察与门或门真值表后，思考如何对这两个结果进行运算得出的

$xORy=((NOTx)ANDy)OR(xAND(NOTy))$这是思考异或的特性：反转其中任意一个，两者就一样，可以利用与门判断

补充：布尔代数部分-《离散数学及其应用》

布尔代数与命题逻辑的转换：补-否定、布尔和-析取、布尔积-合取

布尔函数，布尔变元，函数的运算

思考：有多少个不同的 n 元布尔函数？

吸收律：¶

《计算机科学导论》表述： $ x \cdot(x^\prime+y) = x \cdot y$ 证明：分配律得 $(x \cdot x^\prime)+(x\cdot y)$ 左侧是 0，消去

《离散数学及其应用》表述： $x+xy=x;x(x+y)=x$ 通过真值表可以理解：布尔和强调了 x 的作用，布尔积削弱了 y 的作用

真值表与到表达式的互化、函数化简¶

和之积法与积之和法，互补项合并原理，运算完备性证明

子系统协作¶

三条总线：数据、地址、命令
IO 设备的接入：控制器

关键字符	十进制	十六进制
空字符	0	00
空格	32	20
0	48	30
9	57	39
A	65	41
Z	90	5A
a	97	61
z	122	7A
删除	127	7F

单位	确切的字节数	近似
KB	\(2^{10}\) 1024	\(10^3\)
megabyte	\(2^{20}\) 1048576	\(10^6\)
gigabyte	\(2^{30}\) 1073741824	\(10^{9}\)