A-Level 计算机科学

你必须使用的三种数制(number systems):

• 十进制(denary,decimal,基数 10)——用数字 0–9。位值是十的幂。
• 二进制(binary,基数 2)——用 0 和 1。位值是二的幂。每个字节(byte)是 8 个位(bits)。
• 十六进制(hexadecimal,基数 16)——用 0–9 然后 A–F 表示 10–15。每个十六进制数位(digit)恰好代表 4 个位。

转换

十进制 → 二进制:不断除以 2 并记录余数,从下往上读。或者减去装得下的最大位值(place value,2 的幂)。

例子:$558_{10}$:$558 = 512 + 32 + 8 + 4 + 2 = 2^{9} + 2^{5} + 2^{3} + 2^{2} + 2^{1}$。用 12 位:0010 0010 1110。

二进制 → 十六进制:从右边起把位分成半字节(nibbles,4 位)并转换每一个。0010 0010 1110 → 2 2 E → 22E。

十六进制 → 二进制:把每个十六进制数位换成它的 4 位模式。十六进制 → 十进制:把每个数位乘以它的位值。22E $= 2 \times 256 + 2 \times 16 + 14 = 558$。

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

$200 = 128 + 64 + 8$,所以二进制是 11001000。分成半字节,1100 1000 $= 12$ 和 $8$,即 $\text{C}$ 和 $8$,所以十六进制是 C8。

二进制与十进制词头

两个词头族看起来相似但不同——十进制(10 的幂)和二进制(2 的幂):

所以一个 tebibyte(TiB)略多于一个 terabyte(TB)。一个"1 TB"的驱动器容纳 $10^{12}$ 字节,但一个以 TiB 报告的操作系统显示一个较小的数字。

二进制加法

从右边起逐列相加,像十进制那样进位:

当结果需要的位比寄存器(register)能容纳的更多时,发生溢出(overflow)——最左列的进位输出就是溢出位。

二进制减法

通常的方法是补码(two's complement)加法:要做 $A - B$,构成 $B$ 的补码(每一位取反并加 1),然后相加,并丢弃任何最终的进位输出。

从 $01100100$ 中减去 $00011110$(无符号 8 位):

• $00011110$ 的补码:取反 → $11100001$,加 1 → $11100010$。
• 加到 $01100100$:结果 $1\,01000110$(9 位)——丢弃前导的 1 → $01000110 = 70_{10}$。检验:$100 - 30 = 70$。✓

补码有符号整数

在一个 $n$ 位补码数中:

• 最高有效位(most significant bit,MSB)是符号位(sign bit):0 = 正,1 = 负。
• 要读一个负数:每一位取反,加 1,然后取负。

所以 $11100010$ 是负的;取反 → $00011101$,加 1 → $00011110 = 30$,所以它是 $-30$。这是一个有符号整数(signed integer,不同于无符号(unsigned)的)。$n$ 位的范围是 $-2^{n-1}$ 到 $+2^{n-1} - 1$;对 8 位,$-128$($10000000$)到 $+127$($01111111$)。

例题。 8 位补码数 $10110100$ 表示什么十进制值?

MSB 是 1,所以它是负的。取反 → $01001011$,加 1 → $01001100 = 76$,所以值是 $-76$。用位值检验:$-128 + 32 + 16 + 4 = -76$。

有符号运算中的溢出发生在真实结果落在这个范围之外时——当符号位错误地翻转时可以发现(两个正数给出一个负数,或两个负数给出一个正数)。

反码

在补码之前,一个较老的方案叫反码(one's complement),它表示一个负数只是把正数的每一位取反——没有"加 1"步骤。

• $+30 = 00011110$,所以在反码中 $-30 = 11100001$(就是取反)。
• 缺点:它有两个零——$00000000$($+0$)和 $11111111$($-0$)——这浪费了一个位模式,并使运算别扭。

补码(取反并加 1)去除了负零:它有单一的零,并让加法和减法使用同一个电路。这就是为什么现代计算机以补码而非反码存储有符号整数。

在 BCD(二进码十进数)中,每个十进制数位被写成它自己的 4 位模式。数字 $93$ 在 BCD 中是 1001 0011——不是二进制 93($01011101$)。每个半字节只用 0–9;模式 $1010$–$1111$ 是无效的。

BCD 读法:0010 0111 0101 → 2, 7, 5 → 275。

用途:计算器、数字钟,以及显示十进制数位的设备——每个数位驱动一个七段显示器(7-segment display)。货币代码常用 BCD 以避免把像 0.1 这样的分数转换成二进制时的舍入误差。

十六进制是写二进制的一种紧凑方式(1 个十六进制数位 = 4 位):

• 底层编程中的内存地址(memory addresses)——0x7FFE。
• HTML/CSS 中的颜色值——#FF8800。
• MAC 地址——AC:DE:48:00:11:22。

十六进制不改变存储的数据——它只是使二进制对人类更容易。

计算机把文本存储为数字;每个字符有一个由字符集(character set)设定的数字码点(code point)。

ASCII

• ASCII 用 7 位——128 个码点。基本拉丁字母、数字、标点和控制码。
• 扩展 ASCII 用 8 位——256 个码点;低 128 个与 ASCII 相符,高 128 个因地区而异。

Unicode

• Unicode 是一个通用字符集,涵盖几乎每一种文字,加上符号和表情符号。
• 常见的编码(encodings):UTF-8(1–4 字节,兼容 ASCII)、UTF-16(2 或 4 字节)、UTF-32(固定 4 字节)。

为什么 Unicode 胜过 ASCII

• 它表示多得多的字符(每一种文字、表情符号);ASCII 只涵盖基本英语。
• 文件可移植、没有代码页混乱,并允许一个文档中的多语言文本。
• 权衡:对于纯英语文本,Unicode 文件通常更大。

一个位图(bitmap)图像(也叫位映射图像)在一个网格中存储每个像素(pixel)的颜色。在文件的开头,一个文件头(file header)记录图像的元数据——它的宽度、高度和颜色深度——这样软件就知道如何读取随后的像素数据。

• 图像分辨率(image resolution):位图自身的大小,以像素计的宽 × 高(例如 1920 × 1080)。
• 屏幕分辨率(screen resolution):显示器能显示的宽 × 高。如果一个图像的分辨率比屏幕大,它被缩小以适应;一个低分辨率图像被拉伸到一个较高分辨率的屏幕上时看起来有块状感。
• 颜色深度(colour depth,位深度(bit depth)):每像素的位数。1 位 → 黑/白;8 位 → 256 种颜色;24 位 → 1670 万("真彩色")。

文件大小

除以 8 得字节,除以 1024 得 KiB,等等。例子:一个 $3000 \times 2000$、24 bpp 的图像是 $3000 \times 2000 \times 24 = 1.44 \times 10^{8}$ 位 $\approx 17.2\ \text{MiB}$。

改变设置

• 较低分辨率 → 较小的文件,较少的细节(放大时看起来有块状感)。
• 较低颜色深度 → 较小的文件,但平滑的色调显示出条带。
• 两者中较高的 → 较大的文件,更好的质量。

一个矢量图形(vector graphic)把画图像的指令存储为一个绘图列表(drawing list)——一个有序的绘图对象(drawing objects,几何图元(primitives):线、曲线、多边形、圆)列表。每个绘图对象有属性(properties),如颜色、填充、线宽和位置(坐标)。要显示它,程序以所需的任何分辨率渲染(renders)这个绘图列表。

位图与矢量

矢量的优点:它缩放而不损失质量——一个矢量徽标在任何大小都保持清晰,而一个位图放大时会模糊。矢量的缺点:它不能描述任意的像素细节(照片)。

一个连续的模拟数据(analogue data,声音)波通过采样(sampling)被转换成数字数据(digital data):

• 采样率(sampling rate)——每秒的采样数(Hz)。CD 质量是 $44.1\ \text{kHz}$。
• 采样分辨率(sampling resolution,位深度)——每个采样的振幅(amplitude)的位数。CD 质量是 16 位。

文件大小

一段 10 秒的立体声 CD 片段:$44100 \times 16 \times 10 \times 2 = 14\,112\,000$ 位 $\approx 1.68\ \text{MiB}$。

改变设置

• 较高采样率 → 捕捉较高的音调,较大的文件。
• 较高采样分辨率 → 更精细的振幅步长,较少的量化(quantisation)噪声,较大的文件。
• 两者中较低的 → 较小的文件,明显的质量损失。

(采样率必须至少是你想保留的最高频率的两倍。)

压缩(compression)减小文件大小,节省存储和传输的带宽(bandwidth)。两种:

• 无损(lossless)——原始数据被精确恢复(文本、程序、ZIP/PNG)。
• 有损(lossy)——为了小得多的文件丢弃一些细节(JPEG、MP3、视频)。

何时用哪种

• 无损用于文档、源代码、医学图像——任何需要精确数据的东西。
• 有损用于流媒体。实时视频流用有损压缩,因为它必须在有限的带宽上实时发送大量数据;无损不能把它缩得足够小。原始高清视频是每分钟几个吉字节,所以没有压缩画面会不断卡住。

无损方法

• 行程编码(run-length encoding,RLE):存储"接下来的 $n$ 个值是 $x$",而不是重复 $x$。对平坦区域很好;对噪声数据没用。
• 字典编码(dictionary methods,ZIP、PNG):用一个短引用替换重复的字节序列。对文本和代码很好。
• 霍夫曼编码(Huffman coding):给常见符号短码、给罕见符号长码,使平均码长接近数据的熵(entropy)。

有损方法

• 图像(JPEG):丢弃眼睛几乎看不见的精细细节和颜色差异。
• 声音(MP3、AAC):丢弃我们听得不太清楚的音调,以及被较响声音掩盖的安静声音。
• 视频结合空间(spatial)压缩(在每一帧内,像 JPEG)与时间(temporal)压缩(大多数帧只存储与前一帧的差异)。

• 显示进制转换的过程:十进制 → 二进制用位值,二进制 → 十六进制分半字节(4 位一组)。
• 对于补码,MSB 是负的;要取负,取反并加 1;当符号位错误地翻转时留意溢出。
• 区分位图(像素;文件大小 $=$ 宽 $\times$ 高 $\times$ 颜色深度)和矢量(绘图命令;缩放而不损失)。
• 声音文件大小取决于采样率 $\times$ 位深度 $\times$ 时间——每样越多意味着越好的质量但越大的文件。
• 比较无损与有损压缩并给出各自的一个用途。

一个网络(network)是一组连接起来以便能通信和共享资源的计算设备。好处:

• 共享资源(打印机、文件服务器、互联网)——比给每台计算机都配备更便宜。
• 共享数据——许多用户访问相同的文件。
• 集中管理——在一台服务器上一次性安装软件、管理用户和备份。
• 通信——电子邮件、视频通话、消息。
• 远程访问——从任何地方工作。

一个局域网(local area network,LAN)覆盖一个小区域——一个家庭、办公室或学校,通常由组织拥有,数据速率高、延迟(latency)低。

一个广域网(wide area network,WAN)覆盖一个大区域——一个城市、国家或全世界(互联网是最大的 WAN)。它使用电信公司的基础设施——常常是公共交换电话网(Public Switched Telephone Network,PSTN)、租用线路或光纤——数据速率较低、延迟较高。一个 WAN 把各个 LAN 连接在一起。

客户端-服务器

• 强大的机器充当服务器(servers),提供服务(文件、网页、电子邮件)。
• 其他机器是请求服务的客户端(clients)。
• 集中且易于管理,但除非备份,服务器是单点故障。

对等网络(P2P)

• 所有机器都是平等的对等方(peers);每个既可以是客户端又可以是服务器(对等网络(peer-to-peer))。
• 资源分散在各对等方上——没有中央服务器。对单个故障稳健,但更难保持安全和一致。

一个瘦客户端(thin client)在本地做很少的处理,依赖一台强大的服务器(网页终端、远程桌面)。一个胖客户端(thick client)有强的本地处理和存储,自己运行完整的应用程序(一台普通的台式 PC)。

拓扑(topology)是节点和链路如何排列。

• 总线(bus)——所有设备在一条共享电缆上。便宜;如果总线故障,整个 LAN 就故障;随着更多设备共享带宽(bandwidth),性能下降。
• 星形(star)——每个设备连到一个中央交换机。一个设备故障不影响其他;交换机故障使全部瘫痪。今天最常见。
• 网状(mesh)——每个设备直接连到其他设备,有许多路径。非常容错(fault-tolerant,流量重新路由),但需要大量布线。
• 混合(hybrid)——一种混合(每个办公室内一个星形,办公室之间网状链路)。

云计算(cloud computing)通过互联网交付计算服务(服务器、存储、软件),由第三方托管。好处:可扩展性(scalability,按需付费)、较低的成本、从任何地方访问,以及可靠的冗余数据中心。缺点:需要互联网、你的数据由第三方持有,以及可能的供应商锁定。

• 有线(以太网(Ethernet)通过双绞线(twisted-pair)或光纤(fibre-optic)):速度更高、延迟更低、错误更少、更安全。
• 无线(Wi-Fi、蓝牙、蜂窝):没有电缆、设备可以移动,但更慢、易受干扰和窃听。

对于同一代,有线在速度和可靠性上胜出;无线在便利性上胜出。

• 网络接口卡(network interface card,NIC)——让一个设备能在网络上发送和接收;有一个唯一的 MAC 地址(MAC address,一个 48 位的硬件地址)。一个无线设备用一个无线网络接口卡(wireless network interface card,WNIC)。
• 交换机(switch)——只把以太网帧转发到目标 MAC 地址所对应的端口。
• 集线器(hub)——一个更简单的设备,把流量复制到所有端口(现已过时)。
• 无线接入点(wireless access point,WAP)——让无线客户端加入一个有线 LAN。
• 布线——短距离用双绞线;较长、较快的用光纤。

一个路由器(router)连接不同的网络并在它们之间转发数据——通常在一个 LAN 与互联网的边界处。它做:

• 转发——读取每个数据包(packet)的目标 IP 地址(IP address),并用一个路由表(routing table)从正确的端口把它发出去。
• 网络地址转换(network address translation,NAT)——让许多私有 LAN 地址共享一个公共 IP。
• DHCP(动态主机配置协议)——向 LAN 设备分发私有 IP 地址。
• 防火墙(firewall)——阻止不需要的入站流量。

以太网是主要的有线 LAN 技术。在共享介质上,当两个设备同时发送时可能发生一次冲突(collision)。协议是 CSMA/CD(载波侦听多路访问,Carrier Sense Multiple Access with Collision Detection):

1. 载波侦听——发送前先听;如果电缆繁忙就等待。
2. 多路访问——许多设备共享介质。
3. 冲突检测——发送时持续听;一次碰撞就是一次冲突。
4. 发生冲突时,两者都停止,发送一个短暂的"干扰"信号,然后等待一个随机退避时间再重试。

现代交换式以太网使用全双工(full-duplex)点对点链路,所以冲突不再发生。

流式传输(bit streaming)把多媒体作为一个连续的流发送,接收方在它到达时播放,而不是先下载整个文件。

• 实时(直播):在事件发生时被捕捉并流出(现场体育、视频通话)。你不能倒退;低延迟至关重要。
• 点播:在一台服务器上预先录制(YouTube、Netflix)。你可以暂停和倒退;服务器可以提前缓冲(buffer)。

实时流作为一个短流水线工作:

1. 捕捉并采样源(一个摄像机或麦克风)。
2. 编码它,用压缩(compression)缩小数据。
3. 作为数据包在网络上发送它。
4. 接收方缓冲一点,然后实时播放它——丢弃任何迟到的数据包,因为一个直播流不能等它。

这里用有损(lossy)压缩:活动画面掩盖小的损失,而流必须小到足以适应带宽。

互联网(internet)是一个使用共同协议(protocol)族(TCP/IP)的全球网络的网络。万维网(World Wide Web,WWW)是在它上面运行的一项服务:由 URL 标识的超链接文档,通过 HTTP/HTTPS 在浏览器中查看。电子邮件和文件传输是其他不属于 WWW 的互联网服务。

一个 IP 地址唯一地标识一个设备。

• IPv4——32 位,四个 0–255 的十进制数字(192.168.1.10);约 $4.3 \times 10^{9}$ 个地址(现已耗尽)。
• IPv6——128 位,八组四个十六进制数位;约 $3.4 \times 10^{38}$ 个地址。

子网划分

一个网络可以被分成子网(subnets)。IP 地址分成一个网络部分和一个主机部分,由一个子网掩码(subnet mask,例如 255.255.255.0 = 前 24 位是网络)给出。子网划分改善管理、减少广播流量,并改善安全。

公共地址与私有地址

• 私有地址在一个 LAN 内使用,在互联网上不可路由(例如 192.168.0.0/16)。
• 一个公共 IP 地址(public IP address)全球唯一且可路由,由一个 ISP(互联网服务提供商)分配。

在 NAT 后面带私有地址的设备不能从互联网直接到达,提供了一些保护。

静态与动态

• 一个静态 IP 地址(static IP address)是固定的;用于必须在一个已知地址被找到的服务器。
• 一个动态 IP 地址(dynamic IP address)由 DHCP 分配,可能改变;对客户端设备更容易,并高效地使用一个有限的地址池。

例题。 某主机的 IP 地址是 192.168.10.130,子网掩码是 255.255.255.192。它在哪个网络上?192.168.10.200 和它在同一个网络上吗?掩码的最后一段 192 的二进制是 11000000,所以前 26 位是网络部分,后 6 位用于主机寻址。这使得各子网以 $256 - 192 = 64$ 为步长划分:.0、.64、.128、.192。地址 130 落在从 .128 开始的那一块,所以该主机在网络 192.168.10.128/26 上,其可用主机地址从 .129 到 .190(.191 是广播地址)。200 落在下一块(.192)里,所以它在不同的子网上,两者之间的通信必须经过路由器。要先从掩码算出块大小($256$ 减去掩码那一段的值) - 只看前三段来猜,正是这类题出错的原因。

一个 URL(统一资源定位符,Uniform Resource Locator)定位 WWW 上的一个资源:

https://www.example.com/about/contact.html
protocol     domain name        path

• protocol:http、https 等。
• domain name 域名:一个可读的服务器地址。
• path:那台服务器上的资源。

域名系统(Domain Name System,DNS,也叫域名服务)是一组分布式服务器,它把域名变成 IP 地址。当你输入一个 URL 时,浏览器向一个 DNS 解析器询问 IP,解析器查询 DNS 服务器(根 → 顶级 → 权威)直到找到它;然后浏览器连到那个 IP 并请求路径。DNS 使人类免于记忆 IP 地址,并让一个站点在不改变它名称的情况下更换服务器。

• 通过谁存储和控制资源来区分 LAN 与 WAN 以及客户端-服务器与对等网络。
• 把每种拓扑(总线、星形、网状)与它的优点和缺点(成本、可靠性、冲突)匹配。
• 知道每个设备的工作:一个交换机按 MAC 地址在一个 LAN 内定向,一个路由器按 IP 在网络之间路由。
• 解释流式传输以及为什么需要缓冲(数据到达的速率与播放不同)。
• 区分 IPv4 与 IPv6 以及公共与私有地址;DNS 把一个 URL 变成一个 IP 地址。

一台通用计算机有四个构件:

• 输入设备(input devices)——把数据输入(键盘、鼠标、麦克风、扫描仪、传感器)。
• 输出设备(output devices)——把结果输出(显示器、扬声器、打印机、执行器)。
• 主存储器(primary memory)——处理器(processor,CPU)直接访问的快速存储器(RAM 和 ROM)。容纳运行中的程序及其数据。
• 辅助存储器(secondary storage)——较慢、较大,在不用时保存程序和数据(硬盘、SSD、光盘、U 盘)。

一个嵌入式系统(embedded system)是一台内置于另一个设备中、做一个固定工作的计算机(洗衣机、微波炉、汽车发动机单元、恒温器)。

• 好处:为一个任务优化(低功耗、小、便宜);可靠;启动快;批量便宜。
• 缺点:限于它的一个任务;难以更新(它的固件(firmware)可能需要特殊工具);常常不可维修;有时安全性弱。

激光打印机

一台激光打印机(laser printer)把页面图像扫描到一个带电的感光感光鼓(drum)上。墨粉(toner)黏附到带电区域,转移到纸上,并被一个定影器熔上去。快速、清晰、大批量。

3D 打印机

一台 3D 打印机(3D printer)逐层构建一个物体:FDM 通过一个喷嘴熔化塑料丝;立体光刻用一个 UV 激光固化液态树脂。用于原型和定制医疗部件。

麦克风和扬声器

一个麦克风(microphone)把声音变成一个电信号(一个膜片振动,改变电容器(capacitor)的电荷或线圈位置);信号被一个模数转换器(analogue-to-digital converter,ADC)数字化。一个扬声器做相反的——一个变化的信号驱动一个磁场中的线圈,移动一个纸盆来发声。

磁性硬盘(HDD)

一个硬盘(hard disk)把数据存储在涂有磁性材料的旋转盘片上。每个盘片有分成扇区(sectors)的磁道(tracks)。一个读写头(read/write head)浮在其上方,磁化微小区域(写)或感应它们(读)。每吉字节便宜,但比 SSD 慢,并有运动部件。

固态(闪存)存储器

一个固态硬盘(solid-state drive)把数据作为电荷存储在晶体管(transistors)中,没有运动部件。随机访问比 HDD 快、更耐用、功耗更低,但每吉字节更贵;每个单元在许多次写入后会磨损。

光盘

一个激光检测来自一个光盘(optical disc,CD、DVD、蓝光)上微小凹坑的反射。驱动器是一个光盘读写器:写入用一个更强的激光来改变表面的反射率。

触摸屏

一个触摸屏(touchscreen)感应接触。电阻式(resistive):两个导电层被压在一起;能与任何东西一起工作但不太准确。电容式(capacitive):一根手指扰乱一个电荷场;准确、多点触控,用于手机。

虚拟现实头显

一个虚拟现实(virtual reality,VR)头显有两个小显示屏(每只眼一个)和跟踪头部运动的运动传感器(加速度计(accelerometer)、陀螺仪(gyroscope)),这样当你环顾四周时场景就移动。

一个缓冲(buffer)是在数据于不同速度的设备之间移动时暂时容纳数据的存储器。例子:CPU 快速地把一个文档写入一个打印机缓冲区,然后就能自由地做其他工作,而打印机以它自己的速度从缓冲区打印。缓冲区阻止快设备等待慢设备(也用于流式传输、键盘和磁盘访问)。

• RAM(随机存取存储器,Random Access Memory)——易失性(volatile,断电丢失数据)。容纳操作系统、运行中的程序及其数据;不断地读和写。
• ROM(只读存储器,Read-Only Memory)——非易失性(non-volatile,断电保持数据)。通常写一次;容纳启动时所需的固件(BIOS / 引导加载程序)。

ROM 启动系统;然后 RAM 容纳活动的工作。

• SRAM(静态 RAM,Static RAM)把每一位存储在一个由几个晶体管构成的触发器(flip-flop)中。快,但昂贵且不密集。用于 CPU 高速缓存(cache)。
• DRAM(动态 RAM,Dynamic RAM)把每一位作为电荷存储在一个微小的电容器上。更便宜、更密集但更慢,并且必须每秒刷新(refreshed,重写)数千次。用于主存储器。

小的快速存储器(高速缓存)用 SRAM;大的主存储器用 DRAM。

制造后你能编程的 ROM 变体:

• PROM(可编程 ROM)——写一次(由一个编程器烧断熔丝);不能改变。
• EPROM(可擦可编程 ROM)——通过一个窗口用强 UV 光擦除,然后重写(一次整个芯片)。
• EEPROM(电可擦可编程 ROM)——电气地擦除和重写,一次一个字节,在电路中。闪存是一个为块擦除优化的衍生物。

两者都读传感器;区别在于它们接下来做什么。

• 监控(monitoring)——收集并报告数据但不采取行动(一个记录读数的气象站)。
• 控制系统(control system)——用传感器数据通过执行器来决定并行动,通常在一个反馈回路中(一个开关锅炉的恒温器)。

传感器和执行器

一个传感器(sensor)把一个物理量变成一个信号:温度(一个热敏电阻(thermistor)或热电偶)、压力(应变片)、红外、声音。模拟信号需要先经过一个 ADC。一个执行器(actuator)做相反的——把一个信号变成一个动作(一个电机、阀门、加热器、蜂鸣器)。

反馈

在一个控制系统中,执行器改变环境,传感器随即重新测量它——一个反馈(feedback)回路。没有反馈,系统不能自我纠正或知道何时停止(一个没有温度反馈的恒温器会永远加热)。

一个逻辑门(logic gate)是一个做一个布尔(Boolean)运算的小电路。输入和输出是 0(假、低)或 1(真、高)。要知道每个门的符号、功能和真值表(truth table)。

NOT(反相器)

AND —— 仅当所有输入都为 1 时输出 1

OR —— 若至少一个输入为 1 则输出 1

NAND(NOT AND)—— 仅当所有输入都为 1 时输出 0

NOR(NOT OR)—— 仅当所有输入都为 0 时输出 1

XOR(异或,也叫 EOR)—— 若输入不同则输出 1

一个逻辑电路(logic circuit)是一个执行一个布尔表达式的门网络。你应当能够在一个问题陈述、一个逻辑表达式、一个真值表和一个电路图之间转换。

从表达式到电路

每个运算符画一个门并把它们连起来。对于 $X = (A \text{ AND } B) \text{ OR } (\text{NOT } C)$:$C$ 上一个 NOT 门、$A$ 和 $B$ 上一个 AND 门,然后两个结果上一个 OR 门。

从电路到表达式

从输入向前推进,标注每个门的输出,直到你到达最终输出。

从电路到真值表

对于 $n$ 个输入有 $2^{n}$ 行。列出每个输入组合;对每一个,算出内部的门再算出输出。

从真值表到表达式(积之和)

对每个输出为 1 的行,写一个输入的 AND(对那一行中为 0 的任何输入取 NOT);把这些 OR 在一起。例子:一个只在 $(A=0,B=1)$ 和 $(A=1,B=0)$ 输出 1 的表给出 $\overline{A}B + A\overline{B}$,即 $A \text{ XOR } B$。

从一个问题陈述

先把英语变成一个布尔表达式:"A and B" → A AND B;"A or B or both" → A OR B;"exactly one of A and B" → A XOR B;"neither A nor B" → A NOR B;"not both" → A NAND B。

例题。 某机器的警报 $X$ 在防护罩打开($A=1$)并且电机运转($B=1$)或温度过高($C=1$)时鸣响。写出布尔表达式,并给出 $X=1$ 的各行。把英文一句一句地转成逻辑:"B 或 C"是 $B + C$,"A 并且这个"是 $X = A\cdot(B + C)$。至于各行,$X=1$ 需要 $A=1$ 并且 $B$、$C$ 中至少有一个为 1 - 所以是 $(A,B,C) = (1,0,1)$、$(1,1,0)$ 和 $(1,1,1)$,八行中的三行。注意 $A=0$ 时无论 $B$ 和 $C$ 怎样都不会报警。在与 A 相与之前要给 OR 加括号:$X = A\cdot B + C$ 完全是另一个电路,它会在防护罩关着时也因高温而报警。

• 区分 **RAM(易失性、读/写)**和 ROM(非易失性、容纳引导程序);SRAM(高速缓存、更快)和 DRAM(主存储器、需要刷新)。
• 对于一个逻辑电路,逐门构建布尔表达式,然后一个覆盖每个输入组合的真值表。
• 学每个门(AND、OR、NOT、NAND、NOR、XOR)的符号、表达式和真值表。
• 解释一个缓冲(一个桥接两个不同速度的临时存储)以及一个中断的作用。

冯·诺依曼体系结构(Von Neumann architecture)是几乎每一台通用计算机的基础:

• 一个单一存储器——立即存取存储器(Immediate Access Store,IAS)——同时容纳程序指令和数据(存储程序(stored program)概念)。
• 一个处理器(processor,CPU)从存储器取指令并一次运行一条。
• 除非一个分支改变流程,指令按顺序运行。

存储程序的想法就是使一台计算机灵活的东西:改变程序,你就改变它所做的事,不用重新布线。

所有这些部件都位于一个小芯片内。本节后面的图显示它们如何连接;下面的照片显示实物。

算术逻辑单元(ALU)

ALU(算术逻辑单元)做算术(加、减……)和逻辑(AND、OR、比较)。它从寄存器(registers)取操作数,并把结果放回一个寄存器。

控制单元(CU)

控制单元(control unit)译码每条指令,并发送控制信号来执行它——打开数据通路、告诉 ALU 做什么,以及控制存储器读和写。

系统时钟

时钟发送一串稳定的脉冲,使 CPU 保持同步。每条指令占固定数目的周期,时钟频率(clock speed,例如 3.8 GHz)是性能的一个因素。

寄存器

寄存器是 CPU 内微小、非常快的存储。专用寄存器(special purpose registers)各在周期中有一个固定的工作:

• 程序计数器(Program Counter,PC)——下一条指令的地址。
• 内存地址寄存器(Memory Address Register,MAR)——正在读或写的地址。
• 内存数据寄存器(Memory Data Register,MDR)——正在往存储器去或从存储器来的数据。
• 当前指令寄存器(Current Instruction Register,CIR)——正在译码的指令。
• 累加器(Accumulator,ACC)——ALU 正在处理的值。
• 状态寄存器(Status Register)——容纳分支所用的标志(flags,进位、零、负、溢出)。
• 变址寄存器(Index Register)——变址寻址中所用的一个偏移量。

通用寄存器(general-purpose registers)由程序员用于计算过程中的临时值。寄存器与存储器之间的数据移动用寄存器传送(register transfer)记法写——例如 MAR ← [PC]("把 PC 的内容复制到 MAR")。

三条内部总线(buses,一组组并行导线)连接各部件:

• 地址总线(address bus)——传送存储器地址。单向(CPU → 存储器)。
• 数据总线(data bus)——传送数据。双向。
• 控制总线(control bus)——传送控制信号(读、写、中断)。双向。

一条 $n$ 位地址总线能到达 $2^{n}$ 个存储单元。数据总线宽度决定每次访问移动多少位(常常是字长)。

• 时钟频率——每秒更多的周期。
• 核心数(cores)——一个多核 CPU 一次运行几个线程。
• 字长(word size)——一个 64 位 CPU 每周期处理 64 位块,并能寻址比一个 32 位的多得多的存储器。
• RAM 数量(随机存取存储器)——更多的 RAM 容纳更多的工作集;太少迫使操作系统页(page)到磁盘。
• 高速缓存(cache memory)大小——更多的高速缓存减少平均存储器访问时间。
• 辅助存储器(secondary storage)类型——一个 SSD 加载程序比一个 HDD 快得多。
• 总线宽度和速度——更宽/更快的总线更快地移动数据。

使规格与工作负载匹配:一个四核在并行工作上胜过一个双核,但更高的每核速度在单线程工作上胜出。

一个端口(port)是一个用于连接外围设备(peripheral)的物理插座:

• USB(通用串行总线)——通用(键盘、驱动器、手机)。
• HDMI(高清多媒体接口)——向一个屏幕的数字视频和音频。
• VGA(视频图形阵列)——向一个显示器的较老的模拟视频输出。
• Ethernet(RJ-45)——有线 LAN。音频插孔——耳机/麦克风。

不同的端口用不同的信号,所以一根 HDMI 电缆不会装进一个 USB 插座。USB-C 不寻常,它携带视频、数据和电力。

CPU 重复取指-执行周期(fetch-execute cycle),每条机器指令运行一次。

取指

1. PC 的地址被复制到 MAR。
2. PC 被递增以指向下一条指令。
3. 一个读信号经控制总线传送。
4. 存储器把指令放到数据总线上。
5. 它被复制到 MDR,然后到 CIR。

译码

CU 译码 CIR 中的指令——什么运算,以及哪些操作数或地址。

执行

CU 执行它:算术/逻辑去 ALU(结果到 ACC);一个加载/存储在存储器和一个寄存器之间移动数据;一个分支改变 PC。然后周期重复。

一个中断(interrupt)是一个暂停正常周期的信号,以便 CPU 能处理一个紧急事件(一次按键、一个数据包到达、一个硬件故障、除以零、操作系统计时器)。

处理一个:

1. 完成当前指令。
2. 保存状态(PC 和寄存器)。
3. 把中断服务程序(interrupt service routine,ISR)的地址加载到 PC 并运行它。
4. ISR 处理事件。
5. 恢复保存的状态并继续。

中断让系统及时响应,而 CPU 不用不断检查设备,并且这是操作系统多任务的方式。

CPU 实际运行机器码(machine code)——位模式,专属于一个体系结构。汇编语言(assembly language)是一种可读的形式,每条机器指令一条指令,用像 LDD、ADD、JMP 这样的助记符(mnemonics)书写。一个汇编器(assembler)把它翻译成机器码。

两遍汇编器

一个两遍汇编器读源两次:

• 第一遍构建一个符号表(symbol table):每当一个标签(label,如 LOOP:)出现时,记录它的地址;还不生成代码。
• 第二遍生成代码:翻译每条指令,当一条引用一个标签(如 JMP LOOP)时,在符号表中查找它的地址。

两遍处理前向引用(forward references,一个跳到后面定义的标签的跳转)。

示例指令集

剑桥用一个小的通用集:数据移动(LDD、LDM、LDI、LDX、STO、MOV)、算术(ADD、SUB、INC、DEC)、逻辑/位(AND、OR、XOR、LSL、LSR)、比较和分支(CMP、JMP、JPE、JPN)、I/O(IN、OUT),以及 END。确切的助记符在试卷的参考表中给出。

寻址方式(addressing mode)说明 CPU 如何找到操作数:

• 立即寻址(immediate addressing)——操作数是指令中的值。LDM #10 加载 10。
• 直接寻址(direct addressing)——指令容纳一个地址;操作数是那里的值。LDD 200。
• 间接寻址(indirect addressing)——指令容纳一个地址,它容纳另一个地址,那才是数据。LDI 200。
• 变址寻址(indexed addressing)——有效地址是 address + index register;用于数组。LDX 100 且 IR = 5 读地址 105。

(相对寻址(relative addressing)把地址作为从 PC 起的一个偏移量给出——用于跳转。)

例题。 内存中:地址 200 存放 250,地址 250 存放 99,地址 105 存放 7。变址寄存器中是 5。分别执行 LDM #200、LDD 200、LDI 200 和 LDX 100 之后,累加器中各是什么?跟着每种寻址方式要找多远来看。LDM #200 是立即寻址 - 操作数就是指令中写的那个数,所以累加器中是 200。LDD 200 是直接寻址 - 去地址 200 取出其中的内容:250。LDI 200 是间接寻址 - 地址 200 中存的是 250,那是另一个地址,所以继续去地址 250:99。LDX 100 是变址寻址 - 把变址寄存器加到地址上,$100 + 5 = 105$,再读地址 105:7。用"跳几次"来区分它们:立即 0 次,直接 1 次,间接 2 次,变址 1 次(在加上变址值之后)。

要跟踪它:做一个表,列有 PC、ACC、变址寄存器、每个变量和任何标志。逐条走过指令,每条之后更新表;当分支改变 PC 时跟随它们;在 END 停止。一个常见模式是用变址寻址在一个数组上循环。

一个逻辑移位(logical shift)把所有位向左或向右移若干位,用 0 填充新位置。

• 左移 1(LSL #1)——位向左移,一个 0 从右边进入;对一个无符号数这是 × 2。
• 右移 1(LSR #1)——位向右移,一个 0 从左边进入;对一个无符号数这是整数 ÷ 2。

移 $n$ 位乘以或除以 $2^{n}$。例子:00001011(11)LSL #1 → 00010110(22)。

一个算术右移保留符号位,使一个负的有符号数保持为负。一个循环移位(cyclic shift,旋转)把从一端掉出的位从另一端送回,所以没有位丢失。

用于监控/控制的位操作

嵌入式设备常常每个信号用一个寄存器位(bit)(例如位 $n$ = LED $n$)。用一个掩码(mask)——位掩码——你可以:

• 置位 $n$:R = R OR 一个位 $n$ 置位的掩码。
• 清位 $n$:R = R AND 一个位 $n$ 清零而其余置位的掩码。
• 翻转位 $n$:R = R XOR 一个位 $n$ 置位的掩码。
• 测试位 $n$:R AND 掩码,然后检查结果是否非零。

位操作快、用很少的存储器,并让一个字节容纳至多 8 个开/关状态。

• 用寄存器传送术语(PC、MAR、MDR、CIR、ACC)学取指-执行周期,以及什么递增 PC。
• 说出每个寄存器的工作;地址总线是单向的,数据总线是双向的。
• 区分寻址方式(立即、直接、间接、变址)——一个常见的题目。
• 解释时钟频率、核心数、高速缓存大小和字长如何影响性能。
• 对于一个二进制移位,说明它是逻辑的还是算术的;左移乘以 2,右移除以 2。

为什么一台计算机需要一个操作系统

硬件本身只能取指令并运行它们——它对文件、程序、网络或用户一无所知。操作系统(operating system,OS)是这样一个软件层,它:

• 为运行中的程序管理硬件(处理器(processor)、内存、I/O、存储)。
• 通过一个清晰的接口提供服务(文件系统、网络、用户账户),所以程序不必直接与硬件对话。
• 提供一个用户界面(命令行、GUI、触控)。
• 让几个程序安全地共享硬件——每个获得公平的 CPU 时间并被挡在其他程序的内存之外。

没有操作系统,每个程序都需要它自己的驱动,而且一次只能安全地运行一个程序。

关键的管理任务

• 进程管理(process management)——加载程序、在 CPU 上调度它们、在它们之间切换,并杀死行为不当的。(一个运行中的程序是一个进程(process)。)
• 内存管理(memory management)——把内存给进程、使它们分开,并使用虚拟内存(virtual memory)/ 分页(paging)使工作集能超过物理 RAM(随机存取存储器)。
• 文件管理——在辅助存储器(secondary storage)上组织文件和文件夹、控制权限、防止写入损坏。
• 设备管理(硬件管理)——通过设备驱动(device drivers)处理 I/O 和外围设备、缓冲数据、管理中断,并给出一个统一的接口。
• 安全管理——账户、权限、防火墙、加密。
• 用户界面和联网。

实用软件

大多数操作系统包含实用程序(utility programs)来维护系统:

• 磁盘格式化程序——一个文件 / 磁盘管理工具,它准备一个磁盘(建立它的文件系统);相关工具复制、移动和删除文件。
• 碎片整理软件(磁盘碎片整理(disk defragmenter))——在一个硬盘上把碎片文件的各部分移到一起以减少寻道时间(对 SSD 无用)。
• 磁盘内容分析 / 磁盘修复软件——检查磁盘完整性并修复文件系统错误和坏扇区。
• 备份软件(备份(backup))——把用户数据复制到别处,以便能恢复。
• 病毒检查器(杀毒软件(antivirus))——扫描恶意软件并隔离威胁。
• 防火墙(firewall)——按规则过滤网络流量。
• 文件压缩(压缩(compression))/ 归档;系统监视器;更新。

把这些与操作系统捆绑,省去用户安装每一个。

一个程序库(program library)是预先写好的代码(子程序(subroutines)、类、模块),程序重用它而不是自己写——例如一个数学库、一个网络库、一个图形库。

好处:节省时间(现成的代码)、可靠(经过充分测试、广泛使用),以及标准化(一致的行为)。

• 一个静态库(static library)在编译时被复制到可执行文件中(独立,但更大且需要重建来更新)。
• 一个动态库(dynamic library,DLL,动态链接库;.so)在运行时被加载(可执行文件更小、被许多程序共享、一次更新惠及所有)。

你写源代码;计算机运行机器码(machine code)。一个翻译器(translator)在它们之间转换。

汇编器

一个汇编器(assembler)把汇编语言(assembly language)翻译成机器码,每条指令一条指令。用于底层代码(嵌入式系统、驱动)。

编译器

一个编译器(compiler)在运行之前一次性把一个高级程序翻译成机器码。

• 它在编译时报告所有错误;一旦干净,它产生一个独立的可执行文件(executable),它在没有安装编译器的情况下运行,并能运行许多次。
• 通常运行时更快(运行时没有翻译),但绑定到一个 CPU/OS——为每个平台重新编译。

解释器

一个解释器(interpreter)一次一行地翻译并运行一个高级程序,不产生可执行文件。

• 它在到达那一行时报告一个错误,然后停止;你可以修正它并继续——对开发很好。
• 必须安装解释器才能运行程序;通常更慢(每次运行都重新翻译),但容易跨平台移植(port)。

在它们之间选择

混合:Java

Java 被编译成字节码(bytecode,一种平台无关的中间形式),一个虚拟机(virtual machine,JVM)随即解释它——或使用即时编译(just-in-time compilation)把热点部分变成本地代码。所以错误被及早捕获、字节码在任何有 JVM 的地方运行("一次编写,到处运行"),并且长时间运行的程序达到接近本地的速度。C# 和 Python 用类似的设计。

例题。 Java 源代码被编译成字节码,再由 JVM 解释执行。为什么两者都用,而不直接编译成机器码?编译器生成的是针对某一种处理器和操作系统的机器码,所以在一台机器上编译的程序无法在另一台上运行。而 Java 的编译器面向的是一台虚拟机器,所以它产生的字节码在哪里都完全相同;各个平台再各自提供自己的 JVM,把这些字节码解释成本平台的原生指令。因此一个编译好的文件可以在任何有 JVM 的地方运行 - "一次编写,到处运行"。代价是速度:解释字节码比运行原生代码慢,这正是真实的 JVM 还会用 JIT 编译在运行时把频繁执行的字节码转成原生代码的原因。要把两面都说出来 - 得分点是用速度换来的可移植性。

一个集成开发环境(integrated development environment,IDE)把写、测试和调试代码的工具带进一个应用程序:

• 带语法高亮(syntax highlighting,关键字、字符串、注释用不同的颜色)、自动缩进和括号匹配的源代码编辑器。
• 自动补全(auto-complete)——在你输入时建议名称并显示函数参数。
• 翻译器集成——用一次击键编译/运行;错误内联显示。
• 调试器(debugger)——设置断点(breakpoints)来暂停、逐行单步执行(step through),并检查变量。
• 版本控制(version control)集成(git)、项目管理、一个帮助系统、重构(refactoring)工具(安全重命名),以及单元测试(unit test)集成。

一个 IDE 通过把写 → 运行 → 调试 → 修正放在一个接口后面来加速开发。常见的 IDE:Visual Studio、PyCharm、Eclipse、VS Code。

• 列出操作系统的工作(内存、进程、文件、设备和安全管理)——单说"管理资源"太含糊。
• 比较编译器对解释器对汇编器:每个翻译什么,以及何时报告错误。
• 解释一个 IDE 提供什么(编辑器、调试器、错误诊断、自动补全)。

这些听起来相似,但意思不同:

• 安全(security)——保护数据免于未授权(unauthorised)的访问、更改或破坏。
• 隐私(privacy)——个人控制谁看到他们个人数据的权利,带有同意和一个明确的目的。
• 完整性(integrity)——数据是准确且完整的——没有被损坏或意外更改。

一个文件可以是安全的(只有正确的人能打开它)但缺乏完整性(一个拼写错误把它损坏了);或者准确但不私密(任何人都能读它)。三者都需要。

要保护两样东西:数据本身(保持它机密、完整和可用)和计算机系统(一个被攻破的系统可以攻击其他人、窃取凭据,或被勒索赎金)。

威胁分成三组。

1. 恶意软件(malware,malicious software)——有害的程序:

• 病毒(virus)——附着到其他程序、在它们运行时传播的自我复制代码。
• 蠕虫(worm)——在网络(networks)上无需用户操作就传播的自我复制代码。
• 木马(Trojan horse)——看起来有用但隐藏恶意代码。
• 间谍软件(spyware)——秘密收集信息(击键、密码)。
• 勒索软件(ransomware)——加密你的文件并要求付款。
• 广告软件(adware)——推送不需要的广告。

2. 欺骗人(社会攻击):

• 网络钓鱼(phishing)——欺骗用户交出凭据的假邮件/网站。
• 域名欺骗(pharming)——即使用户输入正确的地址,也把他们重定向到一个假网站。
• 社会工程(social engineering)——欺骗人交出信息。

3. 对网络的攻击:

• 黑客(hackers)的黑客入侵(hacking)——未授权访问,常通过弱密码或软件缺陷。
• 拒绝服务(denial of service,DoS/DDoS)——淹没一台服务器,使真实用户不能到达它。
• 窃听(eavesdropping)——捕获传输中的数据(在开放 Wi-Fi 上的一个风险)。
• 中间人攻击(man-in-the-middle)——一个攻击者秘密地在双方之间转发或更改消息。

措施既保护数据的安全(免于丢失、被盗或损坏)又保护计算机系统的安全(它的硬件、软件和网络)。

一台独立 PC

• 一个强密码;保持最新的杀毒软件;及时的软件更新;向单独介质的备份(backup);全盘加密(encryption);一个锁定的屏幕。

一台联网 PC

以上全部,加上一个防火墙(firewall)、每用户的权限(admin 权限只给 admin)、用户账户(user accounts)的集中管理,以及审计日志(audit logs,谁登录、他们碰了什么)。

跨越互联网

• VPN(虚拟专用网)——加密用户和企业网关之间的流量。
• HTTPS / TLS——加密网络流量。
• 数字签名(digital signatures)——证明谁发送了一个消息,以及它在传输中没有被更改。
• 入侵检测——观察流量以寻找已知的攻击模式。

• 传输中被拦截 → 加密数据(HTTPS、VPN)。被拦截的密文没有密钥就没用。
• 未授权访问 → 强身份验证(authentication,长密码;带手机码或密钥的双因素认证(two-factor authentication));用户授权(authorisation);登录失败后锁定。
• 恶意软件 → 带实时扫描的杀毒软件和反间谍软件(anti-spyware);打补丁;避免不受信任的下载。
• 网络钓鱼 → 用户培训;邮件过滤;在输入凭据前检查 URL。
• 内部威胁 → 最小权限(least-privilege)原则(只给每个用户他们需要的);审计。
• DDoS → 速率限制和流量过滤。

• 加密——用一个密钥把明文(plaintext)变成密文(ciphertext)。对称加密(symmetric encryption,AES)用一个共享密钥;非对称加密(asymmetric encryption,RSA)用一个公钥(public key)和一个私钥(private key)。保护静止和传输中的数据。
• 访问控制(access control)——文件权限(读/写/执行)和访问权限(access rights),由操作系统强制执行。
• 身份验证——身份验证技术核实用户:你知道的东西(密码)、你有的东西(令牌、手机),或你是的东西(生物识别(biometrics)——指纹、面部、虹膜);组合起来最强。
• 备份——保留副本(一些异地),使丢失或损坏可恢复。
• 物理安全——上锁的服务器机房、电缆锁。

数据在它准确且完整时有完整性。两种技术:数据验证(在存储前抓住坏数据)和数据核对(确认数据被正确地输入或传输)。

验证——数据说得通吗?

验证(validation)自动地对照合理的规则检查数据:

• 范围检查——在限度内(一个月是 1–12)。
• 界限检查——在一个单一界限的正确一侧(例如年龄 ≥ 18)。
• 存在检查——被引用的项存在(例如一个产品代码在表中)。
• 长度检查——正确数目的字符。
• 类型 / 字符检查——正确种类的数据(一个电话字段只允许数字)。
• 格式检查——匹配一个模式(一个电子邮件必须含有 @)。
• 存在性检查——必填字段不为空。
• 校验位(check digit)——从其他位算出的一个额外数位(ISBN、卡号),它发现誊写错误。
• 查找检查和一致性检查(例如交货日期 ≥ 订购日期)。

验证抓住格式错误的数据,但抓不住格式正确却事实上错误的数据("Bob" 写成 "Bib")。

核对——数据被正确地输入或传输了吗?

核对(verification)检查数据在从一个地方移到另一个地方时没有被改变。

在输入时:双重输入(输入两次并比较,如同一个新密码)或目视检查。

在传输时(位可能翻转):

• 奇偶校验(parity check)——一个额外的位使 1 的数目为偶(偶校验)或奇。接收方重新计数。抓住单位错误。
• 校验和(checksum)——发送方发送数据的一个摘要值;接收方重新计算它并比较。
• 循环冗余校验(cyclic redundancy check,CRC)——一个用多项式除法的更强的校验和,抓住多得多的错误类型。

一个奇偶块校验(parity block check)更进一步,还能定位错误。把字节排成一个网格:给每个字节一个行奇偶位,然后计算一个额外的奇偶字节,它的各位是上方字节的列奇偶。一个翻转的单一位现在会使一行和一列都不通过——它们的交叉点精确指出哪一位改变了,所以它甚至能被纠正。

核对只证明到达的与发送的相符——不证明数据是正确的,也不能抵御蓄意篡改。验证问"这说得通吗?";核对问"这被正确地复制了吗?"——两者都用。

例题。 一位用户把出生日期输成 31/02/2009,并把电子邮箱地址输入了两遍。哪种检查能抓到哪个错误?两者的区别是什么?验证(合法性检查)问的是"这个数据合理吗?" - 计算机按某条规则去检验它,格式检查或范围检查会拒绝 31/02/2009,因为二月从来没有 31 号。核验问的是"这个数据输入正确吗?" - 把邮箱输两遍就是双重输入,比较两份副本就能抓到打字失误。正是它们的局限使这成为常考题:验证永远无法告诉你数据是正确的,只能说明它是可能的 - 即使用户其实生于另一天,01/02/2009 也能通过所有验证规则。要说清每种检查能抓什么、不能抓什么。

• 把这三个概念分开:安全(保持数据安全)、隐私(谁可以看它)、完整性(保持它正确)。
• 把每种威胁(恶意软件、黑客入侵、网络钓鱼、拦截)与一种措施(防火墙、加密、身份验证、访问权限)匹配。
• 加密保护机密性,而不是完整性——用一个校验和、奇偶校验或校验位来保护完整性。
• 区分一个病毒、蠕虫和木马以及每个如何传播。

一个计算专业人员是这样的人:他的工作——软件、系统、网络、数据——影响其他人。因为工作是技术性的,其他人往往无法判断它是否做得好或做得诚实。所以这个职业遵循共享的伦理(ethics,良好行为的原则)。

为什么伦理重要

• 信任——用户和雇主信任专业人员会为他们的利益行事。没有那种信任,软件就失去可信度。
• 影响——软件运行医疗设备、银行、车辆。粗心或不诚实的工作会伤害人。

专业团体(BCS、ACM、IEEE)为其成员发布伦理准则。

典型的原则

• 公众利益优先——保护受影响者的安全和福利。
• 诚实和胜任——对你的技能诚实;不要声称你缺乏的专长。
• 保密性(confidentiality)——保护客户和雇主的私密信息。
• 避免利益冲突(conflicts of interest)——不要接受你的利益与客户的相冲突的工作。
• 保持你的技能与时俱进;尊重知识产权(intellectual property)和隐私(privacy);公平地对待同事。

合乎伦理地行事对不合伦理地行事

合乎伦理地行事保护用户、加强声誉、减少法律风险,并建立信任。不合伦理地行事(跳过测试、隐藏漏洞、滥用数据)会伤害真实用户、导致解雇或法律诉讼、损害声誉,并总体上侵蚀对技术的信任。

当你面对一个模棱两可的决定时:辨认谁的利益受影响、查阅伦理准则和法律、权衡后果、请教一位受信任的前辈,并选择把用户置于短期便利之上的选项。

例题。 你团队的新 AI 招聘工具把简历分类快十倍,但你注意到它拒绝了更多较年长的申请人。发布它会取悦你的经理,但它不公平地对待一个群体。合乎伦理的选择是把它扣住直到偏见被修正——公众利益和公平先于短期便利。

版权(copyright)是一个原创作品的创作者控制它如何被复制、分发、修改和表演的法律权利。它自动适用(无需注册)于源代码、软件、文档、图像、音频和视频。

没有版权,任何人都可以自由复制软件,开发者就得不到报酬,而剽窃就是合法的。有了版权,开发者能从他们的工作中挣钱(鼓励更多的软件),用户知道谁制作了它,而再利用通过许可以开发者的条件发生。版权持续很长时间(常常是创作者死后 70 年)。一般的想法和算法不受版权覆盖,但可能受一个专利(patent)覆盖。

一个软件许可证(software licence)是一个以所有者的条件授予使用软件许可的合同;选择并应用一个叫作软件许可。

商业(专有)

• 商业软件被出售:你购买一个许可证;软件只在它的条件内使用。
• 不给出源代码(一个专有(proprietary)产品);你不能修改或再分发它。
• 例子:Microsoft Office、Adobe Photoshop、大多数游戏。

在开发者想要每个用户的收入并保持对代码的控制时使用。

开源

• 源代码是公开的;用户可以读、修改和再分发它(开源(open-source))。
• 宽松(permissive)许可证(MIT、BSD)允许几乎任何使用;著佐权(copyleft)许可证(GPL)要求修改后的版本以相同的许可证发布("相同方式共享")。
• 自由软件基金会(FSF)和开源促进会(OSI)推动并批准开源许可证。
• 例子:Linux、Python、Apache。

在开发者想要软件被广泛使用并由社区改进时使用。

免费软件和共享软件

• 免费软件(freeware)——免费,没有源代码,可以再分发但不能修改(Acrobat Reader、WhatsApp)。
• 共享软件(shareware)——试用期免费,然后你付费才能继续使用;没有源代码。

要论证一个许可证选择,把它与开发者的目标(收入、覆盖面、社区)、用户的需求(成本、定制)和用例联系起来。

人工智能(artificial intelligence)构建做过去认为需要人类智能的任务的系统——识别语音和图像、翻译、玩游戏、驾驶。

大多数现代 AI 用机器学习(machine learning)——通过从大量数据中学习模式而在一个任务上进步的算法,而不是被一步一步地编程。用有许多层的神经网络(neural networks)的深度学习(deep learning)是今天领先的方法。

日常例子

AI 任务分成两种——理解输入,和产生输出或决策。

理解输入:

• 语音识别(speech recognition)——口语词到文本(语音助手)。
• 图像识别(image recognition)——在图像中找出物体、面部或文本。

产生输出或决策:

• 机器翻译(machine translation)——语言之间的自动翻译。
• 推荐系统(recommendation systems)——建议产品、视频或音乐。
• 自动驾驶汽车(autonomous vehicles)和机器人。

一个常见的考试场景:一个程序用一个摄像头读一个标签、翻译它,并大声读它——用光学字符识别(optical character recognition)找出词、用机器翻译转换它们,用文本转语音(text-to-speech)转成音频。

好处

• 无障碍——语音/图像 AI 帮助有障碍的用户;翻译帮助非母语者。
• 生产力——自动化重复任务使人腾出手来做创造性工作。
• 决策支持——AI 在巨大的数据集中发现模式(医学诊断、欺诈检测)。
• 始终可用,并为每个用户个性化。

顾虑

• 偏见(bias)——训练数据中不公平的模式变成不公平的 AI 决策(招聘、放贷)。
• 岗位替代——AI 可能取代一些角色。
• 隐私——训练常常使用大量个人数据。
• 透明度——大模型是"黑盒",难以解释。
• 问责——当 AI 出错时,谁负责:开发者、用户,还是运营者?
• 滥用——深度伪造、错误信息、监视。

专业人员必须理解他们所构建的 AI 的局限、告知用户,并减少伤害。

• 对照一个职业行为准则(公众利益、胜任、诚实)而非个人观点来回答伦理问题。
• 区分版权(保护表达)和一个专利(保护一个发明)。
• 比较软件许可证:专有、开源、免费软件、共享软件和 FOSS。

在数据库之前,程序把数据存储在平面文件(flat files)中——通常每个程序一个文件。这对小数据没问题,但在规模上会崩溃。

局限

• 数据冗余(data redundancy)——相同的数据(一个客户的地址)保存在几个文件中。
• 数据不一致(data inconsistency)——分别更新的冗余副本变得不同步。
• 数据依赖(data dependence)——程序绑定到文件格式;改变格式,每个程序都必须重写。
• 难以强制完整性(integrity)、难以安全共享、查询能力弱,以及每字段的安全性弱。

一个关系数据库(relational database)通过把数据存储在由一个所有程序都使用的软件(DBMS)管理的表中来修复这些。

• 表(table,关系)——行和列的一个网格;每种实体(entity)一个表(例如 CUSTOMER)。
• 记录(record,行,也叫元组(tuple))——一行;实体的一个实例。
• 字段(field,列,也叫属性(attribute))——一列;关于每条记录的一条信息。
• 主键(primary key)——唯一标识每条记录的一个字段(或多个字段);从不为空或重复。
• 外键(foreign key)——一个值匹配另一个表主键的字段,把两者链接起来。
• 复合键(composite key)——由两个或更多字段一起构成的一个主键。
• 候选键(candidate key)——任何可以是主键的字段。
• 次键(secondary key)——一个为快速搜索而建立索引的非主字段。
• 索引(indexing)——在一个字段上建立一个索引,使查找和连接运行得更快。
• 参照完整性(referential integrity)——每个外键值必须匹配一个现有的主键(没有孤立记录)。

一个表用简写书写,主键加下划线、外键标注:

CUSTOMER(CustomerID, Name, Phone)
ORDER(OrderID, CustomerID, OrderDate)   -- CustomerID is FK → CUSTOMER

一个实体关系图(entity-relationship diagram)显示结构:每个实体是一个矩形,每个关系是一条线,在每端标注基数(cardinality):

• 一对一(1:1)。
• 一对多(one-to-many,1:M)——每个客户有许多订单;每个订单有一个客户。
• 多对多(many-to-many,M:N)——学生选许多课程,而课程有许多学生。

一个多对多关系不能直接存储。把它拆成两个一对多关系,通过一个容纳两个外键的连接表(link table):

ENROLMENT(StudentID, CourseID, EnrolmentDate)

规范化(normalisation)组织表以减少冗余和不一致,按顺序经过各范式(normal forms)。

• 第一范式(1NF)——每个字段容纳一个单一(原子(atomic))值,没有重复组,并有一个主键。
• 第二范式(2NF)——处于 1NF,并且每个非键字段依赖于整个主键(只对一个复合键有意义)。
• 第三范式(3NF)——处于 2NF,并且每个非键字段只依赖于主键,而不依赖于另一个非键字段(没有传递依赖(transitive dependency))。

一个 3NF 设计把每个事实存储一次,所以插入/更新/删除异常消失。权衡是更多的表和更多的连接。以 3NF 为目标。

要产生一个 3NF 设计:找出实体及其属性;为每个选择一个主键;拆分重复/非原子字段(1NF);拆分依赖于一个复合键一部分的字段(2NF);拆分传递地依赖于键的字段(3NF);为关系添加外键。

例题。 表 ORDER(OrderID, CustomerID, CustomerName, ProductID, Quantity) 的复合主键是 (OrderID, ProductID)。把它规范化到 3NF。逐个用主键去检验每个非键字段。Quantity 同时依赖 OrderID 和 ProductID,这没问题。但 CustomerID 只依赖 OrderID - 也就是复合主键的一部分。这是部分依赖,所以该表不满足 2NF。把它拆成 ORDER_LINE(OrderID, ProductID, Quantity) 和 ORDER(OrderID, CustomerID, CustomerName)。再检验 3NF:在新的 ORDER 表中,CustomerName 依赖于 CustomerID,而后者不是主键 - 这是传递依赖。再拆一次:ORDER(OrderID, CustomerID) 和 CUSTOMER(CustomerID, CustomerName)。要点出破坏每种范式的那种依赖(部分依赖破坏 2NF,传递依赖破坏 3NF);写"它有重复数据"只是在描述症状,得不到分。

一个 DBMS(数据库管理系统)集中管理数据库。修复基于文件的局限的特性:

• 数据字典(data dictionary)——对每个表、字段、类型和键的描述;程序查询它而不是硬编码结构。
• 冗余/一致性控制——每个事实存储一次。
• 并发访问(concurrent access)控制——锁和事务让许多用户一次工作。
• 备份(backup)和恢复;安全和每用户权限。
• 完整性规则——键、唯一和范围约束,集中强制执行。
• 事务(transactions)——一组全部成功或全部失败的操作。
• 视图(views)——向每个用户显示"他们的"那一片数据的虚拟表。
• 数据管理(data management)和数据建模(data modelling)——控制数据如何存储,并把它的结构定义为一个逻辑模式(logical schema,逻辑设计,独立于物理存储)。
• 数据完整性(data integrity)和数据安全(data security)——集中强制正确性并控制访问。
• 一个查询处理器(query processor)运行查询;一个开发者接口(developer interface)给出构建应用程序的工具和 API。

它的工具包括一个数据字典编辑器、一个查询构建器、一个表单构建器、一个报表生成器、用户管理,以及一个 SQL 编辑器。