IGCSE 计算机科学

一台计算机只能用两个状态工作:开和关。你把这些写成 1 和 0。一个只用两个数字(digits)的系统叫二进制(binary,基数 2)。

每种数据(data)——数字、文本、声音和图像——在计算机能使用它之前都必须被变成二进制。计算机用逻辑门(logic gates)处理这个二进制,并把它存储在寄存器(registers,处理器(processor)内部的小的、快速的存储)中。

一个数制(number system)是用一组固定的数字书写数字的方式。你需要其中三个。

• 十进制(denary)是正常的计数系统(也叫 decimal)。
• 二进制(binary)只用 0 和 1。
• 十六进制(hexadecimal,hex)用十六个数字:0–9,然后 A、B、C、D、E、F 代表 10、11、12、13、14、15。

基数(base)告诉你一个系统用多少个不同的数字。

Place value

一个数中的每一列有一个位值(place value)。在二进制中位值从右到左翻倍。对一个 8 位数它们是:

128  64  32  16  8  4  2  1

一个位(bit)是一个单一的 0 或 1。八个位构成一个字节(byte)。四个位(半个字节)是一个半字节(nibble)。

Converting between number systems

十进制 → 二进制。 写出位值。在你需要的每个值下面放一个 1,使它们加起来为你的数;在其余的下面放 0。

例子:把十进制 150 变成二进制。$150 = 128 + 16 + 4 + 2$。

128 64 32 16 8 4 2 1
  1  0  0  1 0 1 1 0

所以 $150$ = 10010110。

二进制 → 十进制。 加上有 1 的位值。10010110 $= 128 + 16 + 4 + 2 = 150$。

十六进制 → 二进制。 把每个十六进制数字变成它自己的 4 位组(一个半字节)。

例子:十六进制 F08。$F = 1111$,$0 = 0000$,$8 = 1000$,所以 F08 = 1111 0000 1000。

二进制 → 十六进制。 把位分成 4 个的半字节,从右边开始。把每个半字节变成一个十六进制数字。

十进制 → 十六进制。 简单的方式是先变成二进制,然后二进制变成十六进制。

这个表格帮助记十六进制字母:

Cambridge 的题目用长达 16 位的二进制数。

例题。 把十进制 100 转换成 8 位二进制,然后转换成十六进制。

$100 = 64 + 32 + 4$,所以二进制是 01100100。分成半字节,0110 0100 $= 6$ 和 $4$,所以十六进制是 64。

Why hexadecimal is used

十六进制比二进制更短,对人们更容易读和写。一个十六进制数字替换 4 个二进制数字,所以你犯更少的错误。值不改变——十六进制只是显示同样的二进制的一个更短的方式。

计算机科学家把十六进制用于:

• MAC 地址和 IPv6 地址
• HTML 中的颜色代码(例如 #FF0000 是红色)
• 内存地址(memory addresses)和错误代码
• 显示内存的内容(一个"内存转储")

你可以把两个 8 位二进制数相加,从右边逐列,就像十进制。一列的规则是:

当一个进位也进来时,$1 + 1 + 1 = 1$ 带一个 1 的进位。

例子:把 01110110(118)和 00110000(48)相加。

  0 1 1 1 0 1 1 0    (118)
+ 0 0 1 1 0 0 0 0    (48)
-------------------
  1 0 1 0 0 1 1 0    (166)

Overflow

一个 8 位寄存器只能容纳 0 到 255 的十进制值。若一个加法给出一个 255 以上的结果,答案需要一个第 9 位。寄存器不能容纳这个额外的位,所以它丢失了。这叫溢出(overflow,一个溢出错误)。它在一个值超出寄存器能存储的极限时发生。

例子:11001000(200)$+$ 01001000(72)$= 272$。用二进制那是 1 00010000,它需要 9 位。前导的 1 在 8 位中放不下,所以存储的答案错误。

一个逻辑二进制移位(logical binary shift)把所有的位左移或右移若干位。

• 移出寄存器末端的位丢失。
• 零被加在空的末端。

一个左移每移一位把数乘以 2。一个右移每移一位把它除以 2;最右边的位(最低有效位(least significant bit(s)))丢失。

例子:把 00110101(53)左移 2 位。

start:         0 0 1 1 0 1 0 1
left shift 2:  1 1 0 1 0 1 0 0

结果是 11010100(212),它是 $53 \times 4$。最左边的两位丢失,而两个零从右边进来。若一个 1 被推出末端,那个信息就永远消失了。

到目前为止这些数是正的。补码(two's complement)让一个 8 位寄存器也容纳负数。

在补码中,最左边的位(最高有效位(most significant bit),或 MSB)有一个负的位值:

-128  64  32  16  8  4  2  1

• 若 MSB 是 0,数是正的。
• 若 MSB 是 1,数是负的。

要使一个正数变负: 写出正的二进制,翻转每个位(0↔1),然后加 1。

例子:制造 $-40$。

• $+40$ = 00101000
• 翻转位 = 11010111
• 加 1 = 11011000

所以 $-40$ = 11011000。通过加上位值检查:$-128 + 64 + 16 + 8 = -40$。

要读一个负的补码数,只需加上位值(MSB 算作 $-128$)。一个 8 位补码数的范围是 $-128$ 到 $+127$。

计算机通过给每个字符一个数字、然后把那个数字存储为二进制来存储文本。一台计算机能使用的字符集,连同它们的数字,是一个字符集(character set)。

• ASCII 每个字符用 7 位,所以它有 128 个不同的字符。这对英文字母、数字和常见符号足够了。
• Unicode 每个字符用更多的位。它能表示多得多的字符——许多语言,加上符号和表情符号(emoji)。

因为 Unicode 有更多的字符,它每个字符需要比 ASCII 更多的位,所以同样的文本占用更多的存储(storage)。

一个声波(sound wave)平滑而一直在变。要存储它,计算机在规律的时刻测量波的高度。这叫采样(sampling),而每次测量是一个样本。

• 采样率(sample rate)是每秒取的样本的数目(以 Hz 测量)。
• 采样分辨率(sample resolution)是每个样本使用的位的数目。波在一个采样点的高度是它的振幅(amplitude)。

一个更高的采样率和一个更高的采样分辨率给一个更准确的录音,但一个更大的文件。

一个计算机图像由叫像素(pixels)的小点的一个网格构成。

• 分辨率(resolution)是图像中像素的数目(例如 $1920 \times 1080$)。
• 颜色深度(colour depth)是用来存储每个像素颜色的位的数目。

一个更高的分辨率和一个更高的颜色深度给一个更好质量的图像,但一个更大的文件。

数据存储用下面的单位测量。一个半字节是 4 位,一个字节是 8 位;从千字节(KiB)往上,每个单位是它之前的那个的 1024 倍(因为 $1024 = 2^{10}$,它适合二进制)。

图像文件大小(以位计)$=$ 分辨率 $\times$ 颜色深度 $=$ 宽 $\times$ 高 $\times$ 颜色深度。

例子:一个图像是 $1024 \times 1024$ 像素,颜色深度为 2 字节($= 16$ 位)。

• 位 $= 1024 \times 1024 \times 16 = 16\,777\,216$ 位
• 字节 $= \div 8 = 2\,097\,152$ 字节
• KiB $= \div 1024 = 2048$ KiB
• MiB $= \div 1024 = 2$ MiB

声音文件大小(以位计)$=$ 采样率 $\times$ 采样分辨率 $\times$ 以秒计的长度。

总是除以 1024(不是 1000)以变成 KiB、MiB 等等。以题目要求的单位给出你的答案。

例题。 一个声音以 8,000 Hz 的采样率、16 位的采样分辨率被录制 30 秒。求以千字节(KiB)计的文件大小。

• 位 $= 8\,000 \times 16 \times 30 = 3\,840\,000$ 位
• 字节 $= 3\,840\,000 \div 8 = 480\,000$ 字节
• KiB $= 480\,000 \div 1024 \approx 469$ KiB

压缩(compression)使一个文件更小。一个更小的文件:

• 使用更少的存储空间,
• 需要更少的带宽(bandwidth,一个连接能携带的数据量),
• 花更短的时间发送(一个更短的传输(transmission)时间)。

有两种类型。

Lossless compression

无损(lossless)压缩使文件更小而没有永久损失数据。原始文件能被精确地重建。

一种方法是行程编码(run-length encoding,RLE)。它用值的一个副本和它重复多少次的一个计数替换一个重复值的行程。例如 WWWWWWWW(8 个白)被存储为"8 W"。这在数据有许多重复时工作得好。

Lossy compression

有损(lossy)压缩通过永久移除一些数据使文件小得多。移除的数据不能取回。例如:

• 减少一个图像的分辨率或颜色深度,
• 减少一个声音的采样率或采样分辨率。

当你必须保留每个细节时(文本和程序文件)用无损。对照片、音乐和视频用有损,那里一个小的质量损失换来一个小得多的文件是值得的。

• 通过减去位值(128、64、32 …)把十进制 → 二进制转换;通过加上有 1 的位值把二进制 → 十进制转换。
• 要转换成十六进制,从右边把二进制分成 4 位的半字节;每个半字节恰好是一个十六进制数字。
• 溢出在一个结果需要比寄存器有的更多的位时发生(一个 8 位寄存器只容纳 0–255),所以额外的位丢失。
• 以位计的文件大小:对一个图像,宽 × 高 × 颜色深度;对声音,采样率 × 分辨率 × 秒。除以 8 得字节,然后每个更大的单位除以 1024。
• 无损压缩保留每一位(文本;行程编码);有损永久移除数据(照片、音乐)以获得一个小得多的文件。

数据传输(data transmission)意味着把数据从一个地方移到另一个——例如从你的计算机到一个网站,或从一部手机到一台打印机。

数据常常沿一根电缆行进。下面显示两种常见的。

在它被发送之前,数据被分解成叫数据包(packets)的小的、相等大小的片。每个数据包分别行进,而它们在另一端被重新组合。

用数据包有好处:

• 若一个数据包丢失或损坏,只有那个数据包被再次发送,而不是整个文件;
• 数据包能走不同的路由,所以一个繁忙或损坏的路由能被避免;
• 许多用户能同时共享同一个连接。

每个数据包有三部分。

包头容纳:

• 发送方的 IP 地址(address,数据包来自哪里),
• 接收方的 IP 地址(它去哪里),
• 数据包号(所以数据包能被以正确的顺序重新组合)。

数据包交换(packet switching)是数据包在一个网络上被发送的方式。

• 叫路由器(routers)的特殊设备读每个数据包的包头并为它选择最好的路由。
• 每个数据包可能走它自己的路径,所以数据包能以不同的方式行进。
• 数据包可能乱序到达。
• 当最后一个数据包到达时,数据包用它们的数据包号被重新排序。

Serial and parallel

串行沿一根单一的导线一个接一个地发送位。并行沿几根导线同时发送几位,所以它在短距离上更快。

Simplex, half-duplex and full-duplex

这些描述数据能行进的方向。

Choosing a method

选择取决于距离、需要的速度、成本,以及数据是否必须同时两个方向行进。

通用串行总线(universal serial bus,USB)是一个把设备连接到一台计算机的常见接口(interface,一个连接点)。

好处:

• 同样的连接器被许多设备使用(一个标准);
• 设备被自动检测,而正确的驱动被加载;
• 它携带电,所以它能充电或运行一个设备;
• 连接器只以一种方式插入,所以难以插错。

缺点:

• 电缆只能是一个有限的长度(几米);
• 较旧的 USB 版本比较新的慢;
• 传输速度能低于一些其他连接类型。

当数据行进时,干扰(interference)能改变它。三件事能出错:

• 数据丢失——一些位没有到达;
• 数据增加——额外的位被加上;
• 数据改变——一些位被翻转。

所以接收方检查数据是否正确地到达。

Parity check

一个奇偶校验(parity check)给每个字节加一个额外的位,奇偶校验位(parity bit)。有两种类型:

• 偶校验——字节中 1 的总数(包括奇偶校验位)必须是偶;
• 奇校验——1 的总数必须是奇。

例子(偶校验):数据 1011001 有四个 1,它已经是偶,所以奇偶校验位是 0:

parity bit + data
    0        1011001

要找到一个错误:接收方数 1。若约定了偶校验但一个字节到达时带奇数目的 1,一个错误在传输期间发生了。

一个奇偶校验不能找到每个错误。若两位翻转,计数可能仍看起来正确。

例题。 一个单一的奇偶校验位告诉你一个错误发生了,但不告诉在哪里。一个奇偶校验块(parity block)能找到确切的位。几个字节一起被发送,每个带一个行奇偶校验位,而底部一个额外的奇偶校验字节(parity byte)为每一列容纳一个奇偶校验位。下面用了偶校验,而一位在传输期间被翻转。找到它。

          b1 b2 b3 b4 b5 | parity
 byte 1    1  0  1  1  0 |   1
 byte 2    0  1  1  0  1 |   1
 byte 3    1  1  1  1  0 |   1    <- row: odd number of 1s
 byte 4    0  0  1  1  0 |   0
 ------------------------------
 parity    0  0  1  1  1 |   1
                 ^ column b3: odd number of 1s

行 byte 3 打破偶校验,而列 b3 打破偶校验。翻转的位是它们交叉的地方:byte 3, bit b3。把它从 1 改回 0 修复数据。一个单一的奇偶校验位只说一个错误发生了;一个奇偶校验块确切地说在哪里,所以接收方甚至能修复它。

Checksum

一个校验和(checksum)是发送前从所有数据算出的一个值。接收方从它收到的数据再次算出校验和。若两个值不匹配,一个错误发生了,而数据被重新发送。

Echo check

在一个回送校验(echo check)中,接收方把数据发送回发送方。发送方把它与原始比较。若它们不同,一个错误发生了。(这需要数据被发送两次,所以它慢。)

Automatic Repeat reQuest (ARQ)

自动重传请求(Automatic Repeat reQuest,ARQ)用叫确认(acknowledgements)的消息。

• 若一个数据包正确地到达,接收方发送一个肯定确认;若它没有,发送一个否定确认。
• 发送方启动一个超时(timeout)计时器。若没有肯定确认及时回来,发送方再次发送数据包。

Check digit

一个校验码(check digit)是放在一个数末端的一个额外数字,从其他数字算出。它被用来在一个数被键入时找到错误。

当数被输入时,校验码被再次计算并比较。它能捕捉:

• 输入了一个不正确的数字,
• 一个换位错误(transposition error,两个数字被交换,例如 21 被键成 12),
• 一个数字被遗漏或加了一个额外的数字,
• 一个语音错误(一个听起来相似的数字,例如 13 和 30)。

校验码被用于条形码(barcodes)和 ISBN(书号)。

Why we need encryption

加密(encryption)打乱数据,使它在被错误的人拦截(intercepted,捕获)时不能被理解。可读的数据叫明文(plaintext);加密后它变成密文(ciphertext)。

加密不阻止数据被拦截。它只阻止数据被理解。

Symmetric encryption

对称加密(symmetric encryption)用一个单一的密钥(key)来加密和解密数据两者。发送方和接收方必须共享这个同样的秘密密钥。风险是密钥本身可能在被共享时被偷。

Asymmetric encryption

非对称加密(asymmetric encryption)用两个不同的密钥:

• 一个任何人都能有的公钥(public key),用来加密;
• 一个保密的私钥(private key),用来解密。

用公钥加密的数据只能用匹配的私钥解密,所以密钥从不必被共享。这比共享一个秘密密钥更安全。

• 数据以数据包发送(一个带地址和数据包号的包头、一个有效载荷,和一个尾部)。数据包能走不同的路由并乱序到达,然后由它们的数据包号重新排序。
• 匹配传输类型:串行(一次一位,长距离上好)对并行(一次几位,短距离);单工 / 半双工 / 全双工描述方向。
• 一个单一的奇偶校验位只显示一个错误发生了;一个奇偶校验块定位确切的错误位——都失败的那一行和那一列。
• 学习错误检测方法以及每个做什么:奇偶校验、校验和、回送校验、ARQ,和校验码(用于键入的数)。
• 对称加密用一个共享密钥;非对称用一个公钥加密、一个私钥解密,所以没有秘密密钥被共享。

中央处理器(central processing unit,CPU)是计算机处理数据并执行指令(instructions)的部分。它通过重复一个周期、每秒数百万次来运行程序。

Parts of the CPU

各部分由总线(buses,携带信息的成组导线)连接:

• 地址总线(address bus)携带内存地址(一个方向);
• 数据总线(data bus)携带数据和指令(两个方向);
• 控制总线(control bus)携带控制信号。

Special registers

这些寄存器在取指-执行周期期间被使用。

The fetch–execute cycle

取指执行周期(fetch–execute cycle)有三个阶段,一遍又一遍地重复:

1. 取指——指令从内存(memory)被复制进 CPU(用 PC、MAR 和 MDR)。PC 随即增加 1。
2. 译码——控制单元算出指令的意思。
3. 执行——指令被执行(ALU 可能做一个计算,结果去累加器)。

Cache memory

高速缓存(cache)是 CPU 内部或靠近它的少量非常快的内存。它存储 CPU 常用的数据和指令。CPU 从高速缓存读取比从主存快得多,所以计算机运行得更快。

What affects CPU performance

例题。 两台电脑除以下不同外完全相同:A 是 3.0 GHz 单核 CPU,带 2 MB 缓存;B 是 2.4 GHz 四核 CPU,带 8 MB 缓存。哪一台更适合视频剪辑?为什么?视频剪辑可以拆成许多能同时进行的任务,所以 B 的四个核心可以并行处理多路数据,而 A 一次只能处理一路。B 更大的缓存也把更多常用数据留在离 CPU 很近的地方,所以它需要从 RAM 取数的次数更少。尽管 A 的主频更高,B 仍是更好的选择。不要只凭主频作答:要把核心数、缓存和主频放在一起权衡,并把每一项都联系到具体要做的工作。

Embedded systems

一个嵌入式系统(embedded system)是建在一个更大的设备内部做一件固定工作的一台小计算机。它专门用于那个任务,通常小而低成本,而且没有通用操作系统。例子:一台洗衣机、一个微波炉、一个机顶盒。

一个输入设备把数据发送进计算机。

一个触摸屏能以三种方式工作:

• 电阻式(resistive)——两层在你触碰的地方被压在一起;
• 电容式(capacitive)——它感知你手指的微小电荷;
• 红外线(infrared)——你的手指打破一个光束的网格。

一个输出设备把数据从计算机发送出到用户。

主存储器(primary storage)是 CPU 能直接使用的内存。有两种。

两者都需要:ROM 告诉计算机如何启动,然后 RAM 容纳你运行的程序。

辅助存储器(secondary storage)永久地保留数据,即使电关了。它是非易失性的,被用于长期存储。有三种类型。

当 RAM 变满时,计算机能把辅助存储的一部分用作额外的、假装的 RAM。这叫虚拟内存(virtual memory)。

现在不需要的数据被从 RAM 移出到磁盘上,这为其他程序在 RAM 中腾出空间。这让你运行比单独的 RAM 能容纳的更多的程序。它更慢,因为辅助存储比 RAM 慢得多。

云存储(cloud storage)把你的数据保存在通过互联网访问的远程物理服务器上,而不是在你自己的设备上。

• 优点:从任何地方任何设备访问它;没有本地存储硬件要购买或维护;容易分享文件和自动备份。
• 缺点:需要一个可用的互联网连接;持续的订阅成本;安全和隐私取决于提供商;你依赖那个提供商保持可用和在营。

Network interface card (NIC)

一个网络接口卡(network interface card,NIC)是让一个设备加入一个网络并发送和接收数据的硬件。每个 NIC 有一个内建的 MAC 地址。

MAC address and IP address

• 一个 MAC 地址(media access control 介质访问控制 地址)是一个识别一个物理设备的数。制造商设定它,而它通常不改变。它用十六进制书写。
• 一个 IP 地址(internet protocol 网际协议 地址)是一个识别一个网络上的一个设备的数。它由网络给出并能改变。

所以一个 MAC 地址随设备,而一个 IP 地址取决于设备正在使用的网络。

IP 地址有两个版本。IPv4 是 32 位的,写成四个 0–255 的十进制数(例如 192.168.0.1);较新的 IPv6 是 128 位的,写成用冒号分隔的八组十六进制数,提供多得多的地址。一个地址还要么是静态(static)的(固定、手动设置、从不改变),要么是动态(dynamic)的(每次设备连接时由路由器/网络分发,所以能改变)。

Router

一个路由器(router)把不同的网络连接在一起——例如,你的家庭网络连到互联网。它读每个数据包中的 IP 地址并把它转发向正确的网络。

• 学习取指-译码-执行周期和特殊寄存器:程序计数器容纳下一条指令的地址,MAR/MDR 携带地址/数据,而累加器容纳 ALU 的结果。
• CPU 性能随更多的核心、一个更大的高速缓存和一个更高的时钟速度改善。
• RAM 是易失性的(它在没有电时失去它的数据)并容纳使用中的程序;ROM 是非易失性的且只读(启动指令)。
• 匹配辅助存储类型:磁(HDD、磁带)、光(CD/DVD,被一个激光读取)、固态(SSD、USB、闪存——没有移动部件)。
• 一个 MAC 地址识别物理设备且通常不改变;一个 IP 地址由网络给出并能改变。

一个计算机系统由一起工作的两部分构成。

• 硬件(hardware)是计算机的物理的(physical)部件——你能触摸的部件。例子:CPU、内存、键盘、屏幕和硬盘。
• 软件(software)是控制计算机并告诉硬件做什么的程序(programs)。

硬件自己不能做任何有用的事。软件需要硬件来运行。两者都需要。

软件分成两种类型。

System software

系统软件(system software)控制计算机本身并给其他程序一个运行的基础。例子:

• 操作系统(operating system,见下面);
• 编译器(compiler)和链接器(linker,把程序变成计算机能运行的一个形式的工具);
• 设备驱动程序(device driver)——让操作系统控制一件硬件的软件;
• 实用程序(utility software)——照料计算机的小工具(例如防病毒、备份、磁盘清理)。

操作系统之下是固件(firmware)——永久存储在 ROM 或闪存上、计算机一开机就运行的软件。BIOS 和引导程序(bootloader)就是固件:它们测试硬件然后加载操作系统。所以各层堆叠成硬件 → 固件 → 操作系统 → 应用软件,每一层都在它下面的层上运行。

Application software

应用软件(application software)让用户做一个有用的任务。例子:

• 文字处理(word processing)软件(写文档);
• 电子表格(spreadsheet)软件(在一个网格中处理数字);
• 数据库管理系统(database management system,存储和搜索数据);
• 网页浏览器(web browser,查看网页)。

一个操作系统(OS)是主要的系统软件。它控制整个计算机并让硬件、应用软件和用户一起工作。没有一个 OS,计算机很难使用。

OS 有许多作用:

• 管理文件——保存、打开、命名、移动和删除文件;
• 处理中断(见下面);
• 提供一个用户界面(user interface),所以用户能控制计算机;
• 管理内存——决定 RAM 中保留什么、在哪里;
• 管理外围设备(peripherals)及它们的驱动——控制像打印机的设备;
• 管理多任务处理(multitasking)——让几个程序一次运行;
• 提供一个平台(platform)用于运行应用软件;
• 管理安全——用户账户、密码和访问权限。

一个中断(interrupt)是发送给处理器(processor)的一个信号,告诉它某样东西现在需要注意。

一个中断能来自三个来源:

• 硬件——例如一个键被按下,或一台打印机用完纸;
• 软件——例如一个程序试图除以零;
• 用户——例如用户按一个"取消"键。

当一个中断到达时,处理器停止它正在做的事、保存它的位置,并服务(处理)中断。当那完成时,它回到它之前正在做的事。这让计算机对重要的事件快速反应。

所有计算机用中央处理器(central processing unit,CPU)处理数据。要使 CPU 做工作,人们用一门编程语言(programming language)写程序。有两种。

High-level languages

一门高级语言(high-level language)用看起来有点像英语的词书写(例如 Python)。它是:

• 对人们容易读、写和修复;
• 独立于计算机——同一个程序能在不同类型的计算机上运行。

Low-level languages

一门低级语言(low-level language)接近硬件实际使用的。它包括:

• 机器码(machine code)——用二进制(0 和 1)书写的指令,CPU 直接运行它;
• 汇编语言(assembly language)——用短的词代码(助记符)而不是二进制书写的机器码。

一门低级语言与特定的(specific)类型的 CPU 相关,所以为一个 CPU 写的程序可能不在另一个上运行。它在程序员需要对硬件的完全控制或非常快、小的代码时使用。

CPU 只能运行机器码。一个高级程序必须先被变成机器码。做这个的软件是一个翻译程序(translator)。有三种类型:编译器和解释器(用于高级代码),以及汇编器(用于低级代码)。

Compiler

一个编译器在程序被运行之前把整个程序翻译成机器码。翻译之后,机器码能被运行许多次而不再翻译。

• 翻译一次性发生,完整地;
• 它在翻译结束时一起报告所有的错误;
• 完成的程序运行快,而且不需要编译器来运行。

Interpreter

一个解释器(interpreter)一次一行地翻译并运行程序。

• 它在它找到的第一个错误停止,这在测试时有帮助;
• 程序运行更慢,因为它每次运行都被翻译;
• 每次程序运行时解释器都必须在场。

当你想分享一个快速的、完成的程序时用一个编译器。当你在写和测试一个程序、想容易地找到错误时用一个解释器。

Assembler

一个汇编器(assembler)把一个低级汇编语言程序(用像 LDA、ADD 这样的助记符写成)翻译成机器码。每个助记符变成一条机器指令——一个直接的一对一翻译,不像处理高级代码的编译器或解释器。

例题。 一个团队正在编写程序。开发期间他们希望快速找到并修复错误;发布时他们希望客户运行得快,并且看不到源代码。每个阶段各适合哪种翻译器?开发时用解释器:它一次翻译并运行一行,遇到第一个错误就停下,所以错误很容易定位。发布时用编译器:它把整个程序一次性翻译成机器码,之后无需翻译器就能快速运行,而且客户拿到的只是可执行文件,不是源代码。两者不是对手 - 要说出阶段并给出理由,因为只写"编译器更快"是得不到分的。

一个集成开发环境(integrated development environment,IDE)是帮助你写程序的软件。它把许多有用的工具放在一个地方:

• 一个代码编辑器(code editor)——用于键入你的程序;
• 一个运行时环境(run time environment)——用于运行程序以测试它;
• 一个翻译程序(translator)——一个编译器或解释器把你的代码变成机器码;
• 错误诊断(error diagnostics)——帮助你找到并理解错误的消息;
• 自动补全(auto-completion)和自动纠错(auto-correction)——IDE 在你键入时完成或修复代码;
• 美化打印(prettyprinting)——用颜色和缩进整齐地布置代码,使它容易阅读。

• 硬件是物理部件;软件是程序。系统软件运行计算机(OS、驱动、实用程序);应用软件为用户做一个任务。
• 一个编译器把整个程序一次翻译(完成的程序运行快,而所有错误在结束时报告);一个解释器逐行翻译(它在第一个错误停止、运行更慢,而且每次都需要)。
• 高级语言接近英语并在任何计算机上运行;低级语言(汇编、机器码)绑定到一种类型的 CPU。
• 一个中断是使 CPU 停止、保存它的位置、服务事件,然后在它离开的地方继续的一个信号。
• 学习操作系统的作用:管理文件、内存、外围设备、多任务处理、安全和用户界面。

人们常常混淆这两个术语,但它们不相同。

• 互联网(internet)是基础设施(infrastructure)——巨大的全球计算机网络以及连接它们的电缆、路由器和连接。
• 万维网(world wide web,WWW)是你用互联网查看的网站(websites)和网页的一个集合。

所以互联网是网络;网是你在那个网络上使用的东西之一。

一个统一资源定位符(uniform resource locator,URL)是一个网页的一个基于文本的地址。你把它键入一个网页浏览器(web browser)以访问一个页面,例如 https://www.example.com/index.html。

一个网页浏览器是你用来查看网页的程序。它的作用包括:

• 渲染(rendering)超文本标记语言(hypertext markup language,HTML)——把页面的代码变成你看到的;
• 在屏幕上显示网页;
• 管理一个网页如何呈现——它的布局、文本和图像。

当你键入一个 URL 并按回车时,几个步骤发生:

1. 浏览器需要网站的 IP 地址(网际协议地址),但一个 URL 用一个名称,而不是一个数。
2. 浏览器询问一个域名服务(domain name service,DNS)——一个存储每个网址 IP 地址的系统。
3. DNS 找到匹配的 IP 地址并把它发送回浏览器。
4. 浏览器用 IP 地址联系存储页面的网页服务器(web server)。
5. 网络服务器把页面的 HTML 发送回浏览器。
6. 浏览器把 HTML 变成页面并显示它。

若 DNS 没有这个地址,它询问另一个 DNS 服务器,直到地址被找到。

例题。 分解网址 https://www.example.com/books/index.html。https 是协议,即传输该网页所用的一套规则(其中的 s 表示传输是加密的)。www.example.com 是域名,它标识这台网页服务器,并由 DNS 服务器把它转换成 IP 地址。/books/index.html 是该服务器上所存资源的文件路径和文件名。要把每一部分连同它的作用一起说出来:只答"第一段"和"最后一段"是在描述网址,而不是在解释它。

一个 cookie 是一个网站存储在你设备上的一个小文本文件。它让网站记住关于你的东西。有两种类型。

Cookie 被用来:

• 保存个人详细信息,所以你不再键入它们(如登录或地址);
• 跟踪用户偏好(user preferences),如你的语言或你喜欢的东西,所以网站能建议内容。

一个数字货币(digital currency)是只以电子形式(electronic form)存在的钱。没有硬币或纸币。它用计算机在人们之间存储和移动,并能被用来在线为东西付款。

数字钱的一个问题是信任:你如何阻止某人把同样的钱花两次,或改变记录?区块链解决这个。

一个区块链(blockchain)是一个数字账本(digital ledger)——每个交易(transaction)的一个共享记录。这个记录被复制到许多计算机上,所以没有单个人控制它,而且它很难改变。

交易被保存在连接成一条链的块中。每个块容纳:

• 交易的数据(谁付谁,以及多少);
• 一个时间戳(timestamp,日期和时间);
• 一个哈希值(hash value)——从块的内容算出的一个特殊代码。

每个块也存储它之前的块的哈希。若某人改变一个旧块,它的哈希改变,所以它不再匹配下一个块。这打破链,而改变立即被发现。这就是区块链如何安全地跟踪交易。

网络安全(cyber security)意味着保持计算机、网络和数据免于攻击。你必须知道这些威胁。

Types of malware

恶意软件是任何制造来伤害一台计算机的软件。主要的类型是:

Impact of the threats

这些攻击能窃取个人数据、删除或改变文件、阻止一个服务工作、花钱,并使用户失去对一个公司的信任。例如,一个 DDoS 攻击能使一个在线商店不可用,所以它失去销售。

你可以用这些方法保护数据。

• 访问权限(access levels)——每个用户只能看或改变他们需要的数据,不多。
• 反恶意软件(anti-malware)软件,包括杀毒软件(anti-virus)和反间谍软件(anti-spyware)——扫描并移除有害的软件。
• 身份验证(authentication)——在你获得访问之前证明你是谁。方法包括:
  • 生物识别(biometrics,指纹或面部),
  • 一个密码(password),
  • 两步验证(two-step verification,一个发到你手机的代码加上一个密码)。
• 自动化软件更新——更新自动地修复软件中的弱点(漏洞)。
• 检查消息的拼写和语气——糟糕的拼写或一个奇怪、紧急的语气能显示一个消息是假的(网络钓鱼)。
• 检查附着到一个链接的 URL——一个错误或奇怪的网址警告你链接不安全。
• 防火墙(firewall)——检查进出一个网络的数据并阻挡任何不被允许的东西。
• 隐私设置(privacy settings)——控制谁能在线看到你的信息。

• 代理服务器(proxy server)——坐在用户和互联网之间,隐藏用户的 IP 地址并过滤掉不安全的内容。

• 互联网是全球网络(基础设施);万维网是你在它上面查看的页面——不要混淆这两个。
• 学习一个页面如何加载:浏览器向一个 DNS 询问网站的 IP 地址,然后从网络服务器请求页面,它返回 HTML。
• 匹配恶意软件类型:病毒(附着到一个文件)、蠕虫(自己跨一个网络传播)、特洛伊木马(假装有用)、间谍软件、勒索软件。
• 把每个威胁匹配到一个防御:网络钓鱼/域名欺骗 → 检查 URL;暴力破解 → 强密码 + 两步验证;拦截 → 加密;黑客攻击/DDoS → 一个防火墙。
• 一个会话 cookie 在你关闭浏览器时被删除;一个持久 cookie 被保存以在访问之间记住你。

一个自动化系统(automated system)是软件和硬件的一个混合,它感知并响应它环境(environment)中的数据,不需要人工干预(human intervention)。换句话说,它自己工作。

自动化系统的例子:

• 一个中央供暖(central heating)系统;
• 一个工厂里的化学过程(chemical process);
• 一个温室(greenhouse,用于种植植物);
• 一个停车场道闸(car park barrier)。

Sensors, microprocessors and actuators

三个部分在一个自动化系统中一起工作。

循环像这样工作:

1. 传感器把数据发送给微处理器。
2. 微处理器把这个数据与存储值(stored values)比较并做一个决定。
3. 微处理器把信号发送给执行器以采取行动。

例如,在一个温室里:一个温度传感器读取热;微处理器把它与想要的值比较;若太热,微处理器给一个执行器发信号以打开一扇窗。

考纲点名许多传感器类型(sensor types),每个读一个物理量——例如一个加速度计(accelerometer)(运动或倾斜)、一个湿度(humidity)传感器(空气中的水),和一个接近(proximity)传感器(附近的物体):

给一个场景挑传感器,选读正确物理量的那个:一个鱼缸需要 pH 和温度传感器;一扇自动门需要一个红外/接近传感器。

Advantages and disadvantages

自动化系统被用于许多情况,如工业、运输、农业(agriculture,种田)、天气(收集数据)、游戏和照明。

例题。 描述一个自动温室如何把温度保持在 25 °C。温度传感器持续测量温度,读数经模数转换器转成数字后送给微处理器。微处理器把读数与存储的 25 °C 这个值进行比较。如果温度高于它,微处理器就给执行器发信号,打开窗户或启动风扇;如果低于它,就打开加热器。然后整个回路不断重复。有两分几乎总是落在"与存储的(预设的)值比较"和"该过程重复进行"这两句话上 - 只写到"传感器告诉计算机"就停下的描述会丢掉它们。

机器人技术(robotics)是处理机器人(robots)的设计、建造和操作的技术分支。

一个机器人有这些特征:

• 一个物理结构(physical structure,一个机械的(mechanical)身体,如手臂);
• 电子元件(electrical components,马达、传感器和线路);
• 可编程指令(programmable instructions)——它遵循一个能被改变的程序。

What robots do

机器人能执行许多作用,例如:

• 工厂设备(factory equipment)——建造汽车、焊接、移动重的部件;
• 家用电器(domestic appliances)——如一个机器人吸尘器(vacuum cleaner)。

一个机器人的一个关键限制是它不能自己思考。当某样意外的事发生时它不能做它自己的选择。

人工智能(artificial intelligence,AI)是计算机系统对人类智能的模拟(simulation)。这意味着一台计算机做通常需要人类思考的任务。

Characteristics of AI

AI 系统通常有这些特征:

• 它们收集数据以及使用那个数据的规则(rules);
• 它们有推理(reason,用规则算出东西)的能力;
• 它们有得出结论(draw conclusions)的能力,结论可能是近似的(approximate,一个最佳猜测)或确定的(definite,确定);
• 它们有从数据学习(learn)的能力;
• 它们有适应(adapt)的能力——随着它们得到新数据改变它们的行为。

Examples of AI

• 专家系统(expert systems)——像一个人类专家一样给出建议的软件(例如,帮助一个医生做一个诊断);
• 自然语言处理(natural language processing)——理解人类的语音或文本;
• 自动驾驶汽车(self-driving cars)。

Inside an expert system

一个专家系统存储人类专长并从中推理。它有四个部分:

• 一个知识库(knowledge base)——关于该主题的存储事实;
• 一个规则库(rule base)——一个人类专家会应用的"如果……那么……"规则;
• 一个推理引擎(inference engine)——把规则应用到事实上以得出一个结论;
• 一个用户界面(user interface)——向用户提问并显示结果。

界面从用户收集事实;推理引擎把规则库对知识库运行;而系统输出一个诊断或一个概率——就像用来帮助一名医生诊断疾病或找出一个汽车故障。

Machine learning

机器学习(machine learning)是一个从经验改进自己表现、无需被显式重新编程的程序。它在数据里找模式并适应:一个搜索引擎在排名结果上变得更好、一个语音助手更准确地识别口语命令,而一个扫地机器人逐渐学会一个房间的布局。

Narrow, general and strong AI

• 学习控制循环:一个传感器测量一个量 → 微处理器把它与一个存储值比较 → 一个执行器采取行动;然后循环重复。
• 不要混淆各部分:一个传感器把数据发送进;一个执行器引起出的运动。
• 一个机器人遵循可编程指令,而当某样意外的事发生时它不能做它自己的决定。
• AI 模拟人类思考:它收集数据和规则、推理、得出结论,并能学习和适应。
• 知道 AI 级别:弱(一个任务;今天所有的 AI)、通用(任何人类任务)、强(有自我意识;还不存在)。

程序开发生命周期(program development life cycle)是用来制作一个程序的一套阶段。有四个阶段。

Analysis

在分析中你理解问题。两个关键技能有帮助:

• 抽象(abstraction)——只保留重要的细节并忽略其余的;
• 分解(decomposition)——把一个大问题分成更小、更容易的部分。

Design

在设计中你规划解决方案,常常用分解。你可以把各部分显示为一个结构图(structure diagram,一个把一个系统分成更小的框的图)中的子系统(sub-systems)。

Coding and testing

在编码中你编写程序代码。你用迭代测试(iterative testing)——在你构建小部分时一遍又一遍地测试它们。在测试中你用测试数据(test data)运行整个程序以检查它工作。

你可以用三种主要方式规划一个解决方案。

• 一个结构图(structure diagram)——显示一个系统的各部分以及它们如何组合在一起;
• 一个流程图(flowchart)——一个用框和箭头按顺序显示步骤的图;
• 伪代码(pseudocode)——用简单的、类似代码的英语书写的步骤(不是一门真实的语言)。

一个算法(algorithm)是解决一个问题的一套步骤,以正确的顺序。每个算法能被分成三部分:

• 输入(input)——进去的数据;
• 处理(processing)——对数据做的工作;
• 输出(output)——出来的结果。

这叫分解成输入、处理和输出。例如,对于"求三个分数的平均值":输入是三个分数;处理是把它们相加并除以 3;输出是平均值。

当数据被输入时,你检查它以减少错误。

验证(validation)检查数据是合理的并遵循规则。它不能检查数据是真的,只能检查它是被允许的。

核实(verification)检查数据被正确地复制或输入(键入它时没有错误)。两种方法:

• 目视检查(visual check)——一个人把键入的数据与原始比较;
• 双重输入(double entry)——数据被输入两次,而两个副本被比较。

一个追踪表(trace table)一步步地记录一个算法运行时每个变量的值。它帮助你:

• 检查一个算法正确地工作;
• 通过用给定的数据跟随它来算出一个算法做什么。

例子:用输入 5 追踪这个算法。

INPUT n
total ← 0
FOR i ← 1 TO n
    total ← total + i
NEXT i
OUTPUT total

追踪显示算法把 1 到 n 相加。用输入 5,输出是 15。

例题。 追踪这个算法并给出输出。

x ← 20
count ← 0
WHILE x > 1
    x ← x DIV 2
    count ← count + 1
ENDWHILE
OUTPUT count

DIV 只取除法的整数部分。每循环一次写一行:x 变成 10(count 为 1),然后 5(count 为 2),然后 2(count 为 3),然后 1(count 为 4)。此时 x > 1 为假,所以循环结束,输出是 4。有两个习惯能保住这些分:在每次循环之前而不是之后检验条件;以及每一次循环都新写一行 - 想把这些值记在脑子里,正是追踪出错的原因。

测试数据(test data)是你用来测试一个程序的数据。有四种你必须知道的类型。

你必须知道这些常见的算法。

Linear search

一个线性查找(linear search)逐个检查一个列表中的每个项,直到它找到它想要的值或到达末端。

found ← FALSE
FOR i ← 0 TO 9
    IF list[i] = searchValue THEN
        found ← TRUE
    ENDIF
NEXT i
OUTPUT found

Bubble sort

一个冒泡排序(bubble sort)把一个列表排序。它比较每对并排的项,若它们顺序错误就交换它们。它重复这个直到不再需要交换。

FOR i ← 0 TO 8
    IF list[i] > list[i + 1] THEN
        temp ← list[i]
        list[i] ← list[i + 1]
        list[i + 1] ← temp
    ENDIF
NEXT i

Totalling and counting

• 求和(totalling)——不断把值加到一个运行中的总数(total ← total + value)。
• 计数(counting)——每次某样东西发生时给一个计数器加 1(count ← count + 1)。

Maximum, minimum and average

• 要求最大值(maximum):保留到目前为止见过的最大值。
• 要求最小值(minimum):保留到目前为止见过的最小值。
• 要求平均值(average):把总数除以有多少个值。

total ← 0
FOR i ← 0 TO 9
    total ← total + list[i]
NEXT i
average ← total / 10
OUTPUT average

• 学习四个生命周期阶段:分析 → 设计 → 编码 → 测试。抽象只保留重要的细节;分解把一个问题分成更小的部分。
• 验证检查数据是合理的(范围、长度、类型、存在性、格式检查);核实检查它被正确地复制(一个目视检查或双重输入)。
• 学习四种测试数据类型:正常(被接受)、异常(被拒绝)、极端(仍被允许的最大/最小)、边界(一个限制两侧的值)。
• 要算出一个算法做什么,填一个追踪表——写下每个变量在每一步的值。
• 知道标准算法:线性查找(依次检查每个项)和冒泡排序(交换并排的对直到不需要交换)。

一个变量(variable)是一个有名字的存储,容纳一个在程序运行时能改变的值。一个常量(constant)是一个有名字的存储,它的值是固定的、不改变。

你应当在使用前声明(declare)它们(说它们的名称和类型):

DECLARE score : INTEGER
DECLARE name : STRING
CONSTANT Pi = 3.142

对一个从不改变的值(如 Pi)用一个常量,所以它在一处被设定,而且容易阅读。

一个数据类型(data type)说明一个变量容纳什么种类的值。你必须知道五种基本类型。

输入(input)从用户读一个值。输出(output)在屏幕上显示一个值。

OUTPUT "What is your name?"
INPUT name
OUTPUT "Hello ", name

每个程序从三个控制结构构建。

Sequence

顺序(sequence)意味着步骤一个接一个地运行,按顺序,从上到下。

INPUT length
INPUT width
area ← length * width
OUTPUT area

Selection

选择(selection)基于一个条件选择哪些步骤运行。用一个 IF 语句,或当有许多选择时用一个 CASE 语句。

IF score >= 50 THEN
    OUTPUT "Pass"
ELSE
    OUTPUT "Fail"
ENDIF

CASE OF grade
    'A' : OUTPUT "Excellent"
    'B' : OUTPUT "Good"
    OTHERWISE : OUTPUT "Keep trying"
ENDCASE

Iteration

迭代(iteration,一个循环(loop))重复步骤。有三种。

一个计数循环(count-controlled loop)重复一个固定的次数:

FOR i ← 1 TO 5
    OUTPUT "Hello"
NEXT i

一个前测循环(pre-condition loop)在每次重复之前检查条件,所以它可能运行零次:

WHILE answer <> "stop" DO
    INPUT answer
ENDWHILE

一个后测循环(post-condition loop)在每次重复之后检查条件,所以它总是运行至少一次:

REPEAT
    INPUT password
UNTIL password = "secret"

• 求和(totalling)——不断把值加到一个运行中的总数:total ← total + value。
• 计数(counting)——每次给一个计数器加 1:count ← count + 1。

total ← 0
FOR i ← 1 TO 10
    INPUT mark
    total ← total + mark
NEXT i
OUTPUT total

例题。 一个程序要读入 5 个分数,然后输出总分和平均分。

total ← 0
FOR i ← 1 TO 5
    INPUT mark
    total ← total + mark
NEXT i
average ← total / 5
OUTPUT total, average

有两行是得分点。total ← 0 必须放在循环之前:放进循环里,总和每次都会被清零,程序最后只会输出最后一个分数。而 average ← total / 5 必须放在循环之后,因为在所有分数都加完之前,总和还不完整。先初始化,后计算 - 这个先后顺序才是题目真正考的东西。

Arithmetic operators

例如,17 MOD 5 是 2,而 17 DIV 5 是 3。

Relational operators

这些比较两个值并给出一个布尔结果:=、<、<=、>、>=,以及 <>(不等于)。

Logical operators

这些连接条件:AND(两者都必须为真)、OR(至少一个必须为真)、NOT(反转真/假)。

IF age >= 13 AND age <= 19 THEN
    OUTPUT "Teenager"
ENDIF

一个字符串由字符构成。有用的操作:

• 长度(length)——字符串中字符的数目;
• 子串(substring)——从字符串取出的一个更小的部分;
• 大写(upper case)——把字母改成大写;
• 小写(lower case)——把字母改成小写。

name ← "Computer"
OUTPUT LENGTH(name)          // 8
OUTPUT SUBSTRING(name, 1, 4) // "Comp"
OUTPUT UCASE(name)           // "COMPUTER"
OUTPUT LCASE(name)           // "computer"

(第一个字符可能被数为位置 0 或位置 1,取决于语言。)

一个嵌套语句(nested statement)是放在另一个里面的一个控制结构。你可以嵌套选择和迭代。

FOR i ← 1 TO 3
    IF i MOD 2 = 0 THEN
        OUTPUT i, " is even"
    ELSE
        OUTPUT i, " is odd"
    ENDIF
NEXT i

你不会必须写多于三层的嵌套。

为了避免重复代码,你可以把一个程序分成有名字的块。

• 一个过程(procedure)是做一个任务的一个有名字的代码块。你用 CALL 运行它。
• 一个函数(function)像一个过程,但它把一个值返回到它被调用的地方。

一个参数(parameter)是一个传入一个过程或函数的值(最多三个参数)。

PROCEDURE Greet(personName : STRING)
    OUTPUT "Hello ", personName
ENDPROCEDURE

CALL Greet("Sam")

FUNCTION Square(n : INTEGER) RETURNS INTEGER
    RETURN n * n
ENDFUNCTION

answer ← Square(5)   // answer is 25

Local and global variables

• 一个局部变量(local variable)在一个过程或函数里面声明。它只能在那里被使用。
• 一个全局变量(global variable)在主程序中声明。它能在任何地方被使用。

局部变量更安全,因为它们不能被程序另一部分错误地改变。

一个库程序(library routine)是你能使用的一段现成的代码。你必须知道这些:

一个可维护的(maintainable)程序对其他人来说以后容易阅读和改变。要制作一个:

• 用有意义的标识符(meaningful identifiers)——变量、常量、数组、过程和函数的清晰名称(totalScore,不是 x);
• 加注释(comments)以解释代码的各部分做什么;
• 用过程和函数把工作分成小块。

一个数组(array)是一个单一变量,容纳同一类型的许多值,由一个索引(index,一个位置号)找到。

One-dimensional arrays

一个一维(1D)数组(one-dimensional array)像一个单一的列表。

DECLARE scores : ARRAY[1:5] OF INTEGER
scores[1] ← 90
scores[2] ← 75
OUTPUT scores[1]

你可以用一个循环填充或读取一个数组:

FOR i ← 1 TO 5
    INPUT scores[i]
NEXT i

Two-dimensional arrays

一个二维(2D)数组(two-dimensional array)像一个带行和列的表。它用两个索引。

DECLARE grid : ARRAY[1:3, 1:3] OF INTEGER
grid[1, 1] ← 5
grid[2, 3] ← 8