计算机科学常识整理

计算机科学(Computer Science)

计算机科学(CS; Computer Science)是系统性研究信息与计算理论基础以及它们在计算机系统中如何实现与应用的学科，包含众多研究领域，与数学、工程学、认知科学等联系密切。

英国作家理查德·布雷斯韦特(Richard Braithwait)最早使用「计算机」一词以指示一种职业，即负责计算的人，之后才逐渐开始代表机器。

计算机(Computer)指接受输入，处理和存储数据，并根据一系列指令产生输出的多用途设备。狭义的计算机指个人计算机(PC; Personal Computer)，即广泛应用于商业、家庭和办公服务的计算机，通用性强、体积小且价格相对较低。

算盘(Abacus)是公认最早的计算设备，发明于美索不达米亚。社会的规模超出个人心算的能力，是制造算盘的原因。算盘大致可分为沙盘、算板和穿珠算盘三类。算盘的进步体现于其拥有一套完整算术法则，且具有存储功能。

算盘属于手动式计算器，需要使用者自行记录算法，而机械式计算器可以大幅减少使用者的思考。帕斯卡计算器(Pascaline; Pascal's Calculator)是由法国科学家布莱兹·帕斯卡发明的机械式计算器，可以直接对两个数字进行加减运算，并能通过重复加减运算以达到乘除运算的目的。

莱布尼兹计算器(Leibniz's Calculator)又称步进计算器(Stepped Reckoner)，则是最早能完成四则运算的机械式计算器。德国数学家戈特弗里德·莱布尼兹因发明步进计算器和二进制计数系统，被认为是第一个计算机科学家。步进计算器的设计非常成功，以至于沿用了三个世纪。

查尔斯·巴贝奇(Charles Babbage)

英国数学家兼发明家，计算机先驱，计算之父。

查尔斯·巴贝奇发明的差分机(Difference Engine)是一台由蒸汽驱动的更复杂的机器，能够近似多项式。差分机项目最终因不能制造出满足精度需求的齿轮而放弃，但后人根据其草稿制作完成，并能正常运行。

查尔斯·巴贝奇的分析机(Analytical Engine)是通用目的计算机，不只是进行一种特定运算。分析机在当时过于超前，也没有建造成功，但其思想包含了许多现代计算机的概念，激励了第一代计算机科学家。

阿达·洛芙莱斯(Ada Lovelace)

英国数学家兼作家。

阿达·洛芙莱斯为分析机编写了假想的程序，详细说明了使用分析机计算伯努利数的方法，被认为是史上第一位程序员。她主张计算机不只可以用来算数，也因此被认为是史上第一位认识计算机完全潜能的人。

阿达·洛芙莱斯建议分析机用二进制存储。

国际商用机械(IBM; International Bussiness Machines)

生产并销售计算机硬件及软件，其前身为制表机器公司。

哈佛马克1号(Harvard Mark 1)又称自动序列控制计算器(ASCC; Automatic Sequence Controlled Calculator)，是最大的机电计算机之一，使用十进制的表示方式，由IBM为二战同盟国制造。哈佛马克1号最早的用途是为「曼哈顿计划」模拟。其指令集非常原始，甚至没有跳转指令，如果需要执行循环，需要将纸带的两端连接起来。

电子数值积分计算机(ENIAC; Electronic Numerical Integrator and Calculator)于宾夕法尼亚大学诞生，是第一个真正的通用可编程电子计算机。

计算理论(Theory of Computation)

即研究「计算机基础能力和限制到何种程度」的数学领域。

可判定性问题(Decision Problem)

阿隆佐·邱奇(Alonzo Church)

美国数学家，对计算理论的系统发展做出巨大贡献。

可判定性问题即研究「是否存在一种算法，使输入逻辑语句后，输出准确的是否判断」。阿隆佐·邱奇提出能表示任何计算的算子，并证明了这样的算法不存在。

阿兰·马蒂森·图灵(Alan Mathison Turing)

计算机科学之父。

阿兰·马蒂森·图灵的图灵机(Turing Machine)是一种理论计算设备，将人的计算行为抽象化。图灵证明了图灵机可以实现任何计算，即计算能力等同于算子。就可计算和不可计算而言，没有计算机比图灵机更强大。

人们用纸笔进行数学运算的过程可以看作如下两种简单动作：在纸上写下或擦除某个符号；将注意力从纸的一个位置移动到另一位置，这又依赖于此人当前关注的纸上的某个位置的符号与此人当前思维的状态。以此为基础，图灵机由以下几个部分组成：无限长的纸带；读写头；控制规则；状态寄存器。

如果一系列操作数据的规则，可以用来模拟任何图灵机，称为图灵完备(Turing Complete)的。

停机问题(Halting Problem)即是否存在程序，对任意输入的程序能判定其会在有限时间结束(即停机)或死循环。停机问题是一种可判定性问题。图灵证明了不存在解决停机问题的通用算法，精要如下：假设有能够判断停机问题的程序；若输入的程序能停机则进入死循环，若输入的程序不能停机则该程序进入停机状态；将此程序作为此程序的输入，则导致悖论。

停机问题证明了不是所有问题都能用计算解决。邱奇和图灵指出，计算机的能力有限，无论有多少时间或内存，有些问题是计算机无法解决的，进而起步了可计算性理论，即邱奇-图灵论题(Church-Turing Thesis)。

自动机(Automaton)

见编译原理知识点整理。

硬件(Hardware)

早期计算机使用机械继电器(Mechanical Relay)，即用电控制的机械开关，通过线圈产生的电磁场吸引金属臂而闭合电路，其限制如下：继电器内的机械臂有质量，因此无法快速开关；机械会随时间磨损，随继电器数量增加，故障概率也会增加。

分立元件(Discrete Components)

分立元件即只有一个电路元件的组件，可以是被动的(电阻、电容、电感等)或主动的(真空管、晶体管等)。提升性能需要追加大量部件而导致复杂设计的现象，称为数字暴政(Tyranny of Numbers)。

真空管(Vacuum Tube)是一种在电路中控制电子流动的电子元件，每个真空管都能被设置为0和1两种状态之一。真空管因比机械继电器反应快而计算速度更快，但消耗大量的电能。

第一支真空管是热电子管(Thermionic Valve)。最简单的真空管即二极管(Diode)，仅允许电流由单一方向流过，即电子从阴极到达阳极。三极真空管(Triode Vacuum Tube)取代机械继电器成为电子设备的基础。

晶体管(Transistor)取代易碎的真空管，通过门电路控制半导体材料的导电性。半导体(Semiconductor)如硅和锗，是处于导体和绝缘体之间的物质。虽然晶体管更快更小、更便宜且耗电更低、更可靠，但其出现并没有解决数字暴政的问题。

集成电路(IC; Integrated Circuits)

集成电路是指将电路集中制造在半导体晶圆表面的小型化方式。许多早期集成电路将很小的分立元件封装成一个独立单元，其载体具有保护作用，一些封装形式如下。

• 直插式封装(DIP; Dual Inline Package)：通常具有两排针脚；
• 针脚网格阵列(PGA; Pin Grid Array)：针脚分布于同心正方形上，通常用于微处理器的封装。

杰克·基尔比(Jack Killby)

德州仪器工程师，集成电路的发明者。

杰克·基尔比提出用锗制作集成电路，但锗稀少且不稳定。

罗伯特·诺伊斯(Robert Noyce)

仙童半导体和英特尔的共同创始人之一，发展近代实用集成电路。

仙童半导体使用蕴藏量丰富的硅制作集成电路，也更稳定可靠。

印刷电路板(PCB; Printed Circuit Board)通过刻蚀金属线的方式将零件连接，可大规模生产。集成电路焊接于印刷电路板上，而印刷电路板是集成电路的载体。

光刻(Photolithography)技术用光将复杂图案印到如半导体的材料上。光刻的工艺步骤如下。

• 晶圆(Wafer)，即半导体晶体圆形薄切片，是集成电路的载体基片；
• 在硅层顶部加一层薄的氧化层(Oxide Layer)作为保护层；
• 然后加一层特殊化学品光刻胶(Photoresist)，光刻胶被光照射后可溶；
• 光掩模(Photomask)与光刻胶配合使用，包含转移到晶圆上的图案；
• 强光照射，光照处光刻胶发生化学变化，冲洗后暴露出氧化层；
• 冲洗氧化层露出的部分，使刻蚀至硅层；
• 冲洗光刻胶。

为使暴露的硅层导电性更好，需要掺杂(Doping)，通常使用高温气体，例如磷。生产复杂集成电路的工艺过程可能需要进行多次光刻流程。

将光掩模聚焦到极小的区域，制作出非常精细的细节。晶体管越小，要移动的电荷量越少，能更快切换状态，耗电更少，电路更紧凑，还意味着信号延迟更低，时钟速度更快。

戈登·摩尔(Gordon Moore)

英特尔的共同创始人之一，提出摩尔定律。

摩尔定律(Moore's Law)指出，集成电路上可容纳的晶体管数目，约每隔两年便会增加一倍。

然而摩尔定律存在极限，晶体管进一步小型化将面临如下问题：由于光的波长，光刻技术精度已达极限，需要研制波长更短的光源以投射更小的图案；晶体管非常小时，电极之间可能只距离几个原子，电子会跳过间隙，导致晶体管漏电，称量子隧穿效应(Quantum Tunneling)。

软件(Software)

软件(Software)指计算机系统中的程序及其文档，是一种逻辑实体，不是有形的系统原件，没有类似硬件的机械磨损和老化问题。软件可分为如下几类。

• 系统软件(System Software)：最靠近硬件的一层，如操作系统、编译器等；
• 支撑软件(Supporting Software)：支撑软件开发、维护和运行的软件，如中间件、数据库等；
• 应用程序(Application)：特定领域专用的软件，如浏览器等。

编程语言(Programming Language)产生于计算机发明之前，能够准确地定义指令以便执行。

早期的计算机编程形式

约瑟夫·玛丽·雅卡尔(Joseph Marie Jacquard)发明可编程纺织机，即雅卡尔纺织机(Jacquard Machine)，是计算机历史的重要一步。雅卡尔纺织机每一行的图案由可打孔的纸卡决定，根据打孔的有无控制线的关系，以达到编制不同花式的目的。

自动演奏钢琴使用钢琴纸卷(Piano Roll)记谱，其打孔位置与钢琴谱相符，根据打孔的有无以控制钢琴的演奏。

穿孔纸卡(Punch Card)用于记录数据和程序信息，便宜且可靠，过去曾用于美国人口普查。

装载穿孔纸卡读取器的计算机将卡片内容写进内存，程序和内容写入完毕即开始执行，程序的输出也可以是穿孔纸卡。即使简单程序也有数百条指令，需要一叠纸卡存储，为避免混乱，会在一叠纸卡的侧面画对角线。贤者系统(SAGE; Semi-Automatic Ground Environment)是供北美防空司令部使用的半自动地面防空系统，是使用穿孔纸卡的最大型程序。

穿孔纸带(Punch Tape)，是穿孔纸卡的改良。

可插拔插线板(Plugboard)供程序员插拔电线，让机器的不同部分互相传输数据和信号，编程复杂。

面板编程(Panel Programming)即使用开关、按钮和指示灯达到编程的效果。面板编程流行于早期家用计算机，因为外围设备(如穿孔纸卡读取器)是昂贵的。

漏洞(Bug)得名于从哈佛马克2号(Harvard Mark 2)故障继电器中拔出的死虫，现在泛指软件出现的各种错误(Error)，具体而言有如下的概念。

根据语境的不同，错误可指不正确的系统状态，也可指程序员在编码过程中犯的错误，即程序设计错误。心智模式(Mental Model)指人们深植心中，对于周遭世界如何运作的看法和行为。而程序设计错误实际上反映的是「程序」与「程序员对该程序的心智模式」两者的相异之处。

• 缺陷(Defect)：多指存在于软件中的偏差，静态地存在于软件内部，可被某种条件激活，是错误的成因，通常被程序员或缺陷定位技术观察；
• 故障(Fault)：软件运行时出现的意料外的状态；
• 失效(Failure)：软件执行过程中的异常表现，表现为与用户需求不一致，因此是可被用户观察的。

缺陷被激活可能导致故障，而故障可能导致失效。通常，缺陷难以根据失效定位。

葛丽丝·霍普(Grace Hopper)

美国海军军官，哈佛马克1号的首批程序员之一。

葛丽丝·霍普设计了高级语言A-0(Arithmetic Language version 0)，创造了第一个编译器。然而霍普的想法遭受质疑，没有任何A-0的代码遗留下来，A-0和之后的版本没有广泛使用。

约翰·巴科斯(John Backus)

FORTRAN发明小组的组长，巴科斯范式的提出者之一。

FORTRAN(Formula Translation)编程语言由IBM发布，主宰早期计算机编程。最初，FORTRAN代码只能在IBM计算机上执行。

COBOL(Common Business-Oriented Language)是CODASYL打造的通用编程语言，而CODASYL(Committee on Data Systems Languages)由葛丽丝·霍普担任顾问，致力于开发能在不同机器上使用的通用编程语言。

汇编语言(Assembly Language)

All discussed below are based on x86-64.

x86-64整数寄存器

Usage	64-bit Register	Lower 32 Bits	Lower 16 Bits	Lower 8 Bits
Return Value	%rax	%eax	%ax	%al
Arguments	%rdi %rsi %rdx %rcx %r8 %r9	%edi %esi %edx %ecx %r8d %r9d	%di %si %dx %cx %r8w %r9w	%dil %sil %dl %cl %r8b %r9b
Caller-Saved Temporaries	%r10 %r11	%r10d %r11d	%r10w %r11w	%r10b %r11b
Callee-Saved Temporaries	%rbx %r12 %r13 %r14	%ebx %r12d %r13d %r14d	%bx %r12w %r13w %r14w	%bl %r12b %r13b %r14b
-	%r15	%r15d	%r15w	%r15b
-	%rbp	%ebp	%bp	%bpl
Stack Pointer	%rsp	%esp	%sp	%spl

Operand types are as follows.

• Immediate: Constant integer data prefixed with $ such as $0x400, $-533;
• Register: One of 16 integer registers such as %rax, %r13;
• Memory: such as (%rax).

移动(Move)

The x86-64 mov instructions cover wide range of data movement forms.

x86-64移动指令的常见形式

Note that cannot do memory-memory transfer with a single instruction.

Src.	Dest.	Assembly	C Analog
Immediate	Register	movq $0x4, %rax	temp = 0x4;
Immediate	Memory	movq $-147, (%rax)	*p = -147;
Register	Register	movq %rax, %rdx	temp2 = temp1;
Register	Memory	movq $rax, (%rdx)	*p = temp;
Memory	Register	movq (%rax), %rdx	temp = *p;

x86-64寻址模式

Wherein, is called scale factor and can be 1, 2, 4 or 8. Also form like (, %rcx, 4) is allowed.

Modes	Example	Description
Immediate	movq $-500, %rax
Register	movq %rdx, %rax
Direct Addressing	movq 2000, %rax
Indirect Addressing	movq (%rdx), %rax
Base Displacement	movq 40(%rdx), %rax
Scaled Index	movq (%rdx, %rcx, 4), %rax
Scaled Index Displacement	movq 80(%rdx, %rcx, 2), %rax

Some C expression can be optimized by arithmetic operations. An example is as follows.

Wherein, the statement is y = x * 48;.

leaq    (%rdi, %rdi, 2), %rax
salq    $4, %rax

控制(Control)

Single bit registers are as follows.

Not set by lea instructions.

• CF(Carry Flag): Set if carry out from most significant bit (unsigned overflow);
• OF(Overflow Flag): Set if two’s complement overflow (signed overflow);
• ZF(Zero Flag): Set if result equals to zero;
• SF(Signed Flag): Set if result less than zero.

Condition codes are usually related to the following instructions.

• cmpq b, a: Like computing without setting destination;
• testq b, a: Like computing without setting destination.

set instructions set low-order byte of destination to 0 or 1 based on combinations of condition codes. For example, setl means "less" and its condition is "SF xor OF". Also there exists synonym(同义指令), like setg and setnle.

set instructions do not alter remaining bytes, so typically use movzbl to finish job in condition codes. An example is as follows.

Wherein, the statement is return x > y;, x uses regiser %rdi and y uses regiser %rsi.

cmpq      %rsi, %rdi    # Compare x:y
setq      %al           # Set when >
movzbl    %al, %eax     # Zero rest of %eax (and rest of %rax)
ret

jmp instructions can jump to different part of codes. They help to build conditional branches. Assume that there exists conditional branches as follows.

long fun(long x, long y) {
    long res;
    if(x > y) res = x - y; else res = y - x;
    return res;
}

The corresponding assembly code is as follows.

Wherein, x uses regiser %rdi and y uses regiser %rsi.

• 旧式条件分支
• 使用条件移动

Require gcc settings –fno-if-conversion.

fun:    cmpq    %rsi, %rdi    # Compare x:y
        jle     .L4           # Jump when <=
        movq    %rdi, %rax
        subq    %rsi, %rax    # x - y
        ret
.L4:    movq    %rsi, %rax
        subq    %rdi, %rax    # y - x
        ret

fun:    movq      %rdi, %rax
        subq      %rsi, %rax    # res = x - y
        movq      %rsi, %rdx
        subq      %rdi, %rdx    # tmp = y - x
        cmpq      %rsi, %rdi    # Compare x:y
        cmovle    %rdx, %rax    # res = tmp, when <=
        ret

Therefore, bad cases for conditional move are as follows.

• Expensive Computations: value = c ? Hard1() : Hard2();;
• Risky Computations: value = p ? *p : 0;;
• Side Effects: value = x > 0 ? x *= 7 : x += 3;.

Assume that there exists switch statements as follows.

long sw_ex(long x, long y, long z) {
    long w = 1;
    switch(x) {
        case 1:     // L3
            w = y * z; break;
        case 2:     // L5 to L6
            w = y / z;
        /* Fall Through */
        case 3:     // L9 to L6
            w += z; break;
        /* No case 4 */
        case 5:     // L7
        case 6:
        /* Multiple Labels */
            w -= z; break;
        default:    // L8
            w = 2;
    }
    return w;
}

The corresponding jump table is as follows.

.section    .rodata
    .align 8
.L4
    .quad    .L8    # x = 0
    .quad    .L3    # x = 1
    .quad    .L5    # x = 2
    .quad    .L9    # x = 3
    .quad    .L8    # x = 4
    .quad    .L7    # x = 5
    .quad    .L7    # x = 6

The corresponding assembly code is as follows.

Wherein, x uses regiser %rdi, y uses regiser %rsi and z uses register %rdx.

sw_ex:     movq     %rdx, %rcx         # Note that w not initialized here
           cmpq     $6, %rdi           # Compare x:6
           ja       .L8                # Jump when x > 6 and x < 0 (unsigned)
           jmp      *.L4(, %rdi, 8)    # Jump table
.L3:       movq     %rsi, %rax         # case 1: w = y;
           imulq    %rdx, %rax         # w *= z;
           ret
.L5:       movq     %rsi, %rax         # case 2: w = y;
           cqto
           idivq    %rcx               # w /= z;
           jmp      .L6                # goto merge;
.L9:       movl     $1, %eax           # case 3: w = 1;
.L6:       addq     %rcx, %rax         # merge: w += z;
           ret
.L7:       movl     $1, %eax           # case 5: case 6: w = 1;
           subq     %rdx, %rax         # w -= z;
           ret
.L8:       movl     $2, %eax           # default: w = 2;
           ret

Sparse(稀疏的) switch statements may use decision trees.

Usually put some bias to make sure that the first case is at value 0.

过程(Procedure)

The x86-64 stack is usually related to the following instructions.

• pushq src: Decrement %rsp by 8, and write src at %rsp address;
• popq dest: Increment %rsp by 8, and store value given by %rsp at dest(Must be a register).

push and pop are used to support procedure call and return.

The instruction pointer register %rip points to the next instruction to execute. Use call instruction to do procedure call. Caller invokes callee.

A stack frame is a memory management technique used in some programming languages for generating and eliminating temporary variables, and it consists of two parts as follows (From top to bottom).

• Callee Stack Frame(Current Stack Frame): Stack pointer %rsp points here, an unused address block;
  • Argument Build Area(Optional): Parameters for function about to call;
  • Local Variables(If cannot keep in registers);
  • Saved Register Context;
  • Old Frame Pointer(Optional): Frame pointer %rbp points here.
• Caller Stack Frame;
  • Return Address(Pushed by call instruction);
  • Arguments for this call.

Caller saves temporary values in its frame before the call. Callee saves temporary values in its frame before using and restores them before returning to caller.

Assume that there exists a function as follows.

long caller(long x) {
    long v1 = 100;
    long v2 = callee(&v1, 200);
    return x + v2;
}

The corresponding assembly code is as follows.

Wherein, x uses regiser %rdi and the first parameter of callee reuses %rdi.

caller:    pushq    %rbx             # Callee-Saved
           subq     %16, %rsp
           movq     %rdi, %rbx       # Puts x in %rbx
           movq     $100, 8(%rsp)
           movl     $200, %esi
           leaq     8(%rsp), %rdi
           call     callee
           addq     %rbx, %rax
           addq     $16, %rsp
           popq     %rbx             # Restore
           ret

Assume that there exists a recursive function as follows.

long pcount(unsigned long x) {
    if(x == 0) return 0;
    else return (x & 1) + pcount(x >> 1);
}

The corresponding assembly code is as follows.

Wherein, x uses regiser %rdi.

pcount:    movl     $0, %eax
           testq    %rdi, %rdi
           je       .L6
           pushq    %rbx
           movq     %rdi, %rbx
           andl     $1, %ebx
           shrq     %rdi
           call     pcount
           addq     $rbx, %rax
           popq     %rbx
.L6:       rep; ret

函数式编程(Functional Programming)

函数式编程将计算过程视为函数，并避免使用程序状态或可变对象。函数可大致分为如下两类。

• 纯函数(Pure Function)：函数与外界交换数据只能通过参数和返回值；
• 非纯函数(Impure Function)：具有副作用(Side Effect)，函数通过参数和返回值以外的渠道和外界进行数据交换，例如捕获外部变量、修改参数或修改全局变量等。

函数式编程重视使用纯函数。

算子(Lambda Calculus)是形式化的数学逻辑系统，也是函数式编程的基础。只使用如下规则来建构算子。

• 变量(Variable)：形如，用字符或字符串来表示参数或者数学上的值或者表示逻辑上的值；
• 抽象(Abstraction)：形如，即函数定义，其中为形式参数，为函数体；
• 应用(Application)：形如，即以为参数调用函数。

算子的规约(Reduction)操作如下。

• -变换(-Conversion)：，即重命名操作；
• -规约(-Reduction)：，即调用操作。

操作系统(OS; Operating System)

见操作系统知识点整理。

软件工程(Software Engineering)

见软件工程知识点整理。

开源软件(Open Source Software)

开源软件向想要修改或改进软件的程序员公开软件的源代码，且受版权保护。自由软件(Free Software)与开源软件存在很多共性，开源软件与自由软件都是可以不受限制地自由使用、复制、研究、修改和分发的软件。

常见的软件许可协议

常见的软件许可协议如下。

• 麻省理工学院(MIT; Massachusetts Institute of Technology)：他人修改后可闭源，不必须声明版权，衍生软件的广告可以用作者的名字促销；
• Apache：他人修改后可闭源，每一个修改后的文件必须放置版权说明；
• 伯克利软件分发(BSD; Berkeley Software Distribution)：他人修改后可闭源，不可以用作者名和原产品名做市场推广；
• 通用公共许可证(GPL; General Public License)：他人修改后不可闭源，新增代码即软件的派生物要求采用同样许可证；
• Mozilla：他人修改后不可闭源，需要对源代码修改之处提供说明文档。

冯·诺依曼结构(Von Neumann Architecture)

约翰·冯·诺伊曼(John Von Neumann)

匈牙利裔数学家和物理学家，曾参与曼哈顿计划和早期电子计算机项目。

冯·诺依曼结构又称普林斯顿结构(Princeton Architecture)，是一种将程序指令存储器和数据存储器合并在一起的计算机设计概念结构。依此结构设计出的计算机又称「存储程序式计算机」，一般具有如下基本特点。

• 计算机由运算器、控制器、存储器、输入设备和输出设备等部分组成；
• 采用存储程序方式，程序和数据放在同一个存储器中，并以二进制形式表示；
• 指令由操作码和地址码组成，在存储器中按执行顺序存放，由程序计数器指明要执行的指令所在的存储单元地址。

电子延迟存储自动计算器(EDSAC; Electronic Delay Storage Automatic Calculator)又称Manchester Baby，是第一台实际运行的冯·诺依曼体系的电子计算机。

中央处理器(CPU; Central Processing Unit)

解释计算机指令以及处理计算机软件中的数据。

指令集架构(ISA; Instruction Set Architecture)是处理器系列独有的，是一组指令的集合，包含特定处理器执行的基本命令。计算机依指令集复杂程度可分为如下两类。

• 复杂指令集计算机(CISC; Complex Instruction Set Computer)：如Intel和AMD的x86架构CPU等；
• 精简指令集计算机(RISC; Reduced Instruction Set Computer)：如ARM、IBM Power等。

单一指令的执行过程称指令周期(Instruction Cycle)，这个循环包括取指令、翻译指令、执行指令和寻找下一指令等步骤。微处理器时钟(Microprocessor Clock)意味着处理器执行指令的速度，通常以千兆赫(GHz)为单位。

CPU的高速缓存(Cache)允许处理器更快访问数据，分为几个级别。一级缓存(L1; Level 1 Cache)是最快的，而二级缓存(L2; Level 2 Cache)和三级缓存(L3; Level 3 Cache)则稍慢些，但仍快于访问内存或磁盘存储。

英特尔(Intel)

得名于集成电子(Integrated Electronics)，世界上最大的芯片制造商。

英特尔推出的Intel 4004是世界上第一个微处理器。x86泛指一系列基于Intel 8086且向后兼容的中央处理器指令集架构，如IA-32(Intel Architecture, 32-bit)和x86-64。英特尔的其他重要产品如下。

• 8086：First 16-bit Intel processor, 1MB address space;
• 386：First 32-bit Intel processor, referred to IA32;
• Pentium 4E：First 64-bit Intel processor, referred to x86-64;
• Core 2：First multi-core Intel processor;
• Core i7：Four cores.

基于x86技术的处理器常见于台式计算机和笔记本电脑的内部；基于ARM技术的处理器则主导平板电脑和智能手机。

运算器(PU; Process Unit)

运算器负责算术运算和逻辑运算，又称处理单元/逻辑通路，包含算术逻辑单元(ALU; Arithmetic/Logic Unit)和寄存器(Register)，ALU使用寄存器保存正在处理的数据。经典的的冯诺依曼计算机以运算器为中心。

字长(Word Size)指微处理器能同时处理的位数，取决于寄存器的大小以及与寄存器相连的线路的容量。

控制器(CU; Control Unit)

控制器包含指令寄存器(IR; Instruction Register)和程序计数器(PC; Program Counter)，用于读取指令，控制程序流程，譬如条件、跳转等。数据被加载到寄存器中，控制器给ALU发送信号并开始处理。控制器部件逐渐由操作系统取代。

在x86中，代码段(CS; Code Segment)和指令指针(IP; Instruction Pointer)是PC的实现设施。

存储器(Memory)

存储器的设计目标是高速度、大容量和低成本。现代冯诺依曼计算机以存储器为中心。

端序(Endianness)得名于「格列佛游记」中小人国为水煮蛋从何处剥开而争执的故事，内容如下。

• 大端(Big Endian)：低位放在较大的地址处，代表如Sun、PPC Mac等；
• 小端(Little Endian)：低位放在较小的地址处，代表如x86、ARM等。

端序的具体示例

假设有变量int a = 15213;且位于0x100 ~ 0x103的地址范围。

端序	0x100	0x101	0x102	0x103
大端	00	00	3B	6D
小端	6D	3B	00	00

利用电能方式存储信息的存储设备可大致分为随机存取存储器和只读存储器两类。

随机存取存储器(RAM; Random Access Memory)

又称内存，数据、应用程序指令和操作系统的暂存区。

RAM is traditionally packaged as a chip. Its basic storage unit is normally a cell(one bit per cell). Multiple RAM chips form a memory.

RAM comes to two varieties, SRAM(Static RAM) and DRAM(Dynamic RAM).

SRAM和DRAM的对比

RAM	Trans. per Bit	Access Time	Needs Refresh?	Cost	Applications
SRAM	4 or 6		No		Cache Memories
DRAM	1		Yes		Main Memories & Frame Buffers

SRAM and DRAM are volatile memories(Lose data when the power goes off). Nonvolatile memories like ROMs retain value even if powered off.

只读存储器(ROM; Read Only Memory)

永久而稳定的存储电路，主要任务是引导设备。

存储在ROM的程序称为固件(Firmware)或引导加载程序(Boot Loader)，当一个计算机系统通电后，它会运行存储在ROM中的固件如称为基本输入/输出系统(BIOS; Basic Input/Output System)的小型指令集，执行自测试以查明硬件是否能正常运行，并验证基本程序是否损坏，然后将操作系统加载到RAM中。

通常ROM可分为如下几类，虽然有的ROM类型可读也可写，但由于历史原因整体上都称为ROM。

• PROM(Programmable ROM)：只能被编程一次；
• EPROM(Eraseable PROM)：利用紫外线将位清除为零；
• EEPROM(Electronically EPROM)：可直接在印制电路卡上编程；

闪存(Flash Memory)由一系列EEPROM组成，又称固态存储器。采用固态存储技术的存储器如下。

• 固态硬盘(SSD; Solid State Drive)：由一系列闪存芯片构成，具有很快的传输速率；
• U盘(USB Flash Drive)：是一种便携式存储设备，可直接插拔使用；
• 内存卡(Memory Card)：多为卡片或方块状，其类型有快闪内存(CF; Compact Flash)卡、多媒体卡(MMC; Multi Media Card)、安全数字(SD; Secure Digit)卡等。

磁存储(Magnetic Storage)

通过磁化磁盘表面上的微观粒子来存储数据，粒子保持其磁化方向直到方向改变，为数据提供永久但可修改的存储。

磁盘(Disk)又称机械硬盘，是以坚硬旋转盘片为基础的非易失性存储器。

磁盘包括数个盘片(Platter)，每个盘片有两面，每一面包括数个称为磁道(Track)的同心圆，磁道由外至内的标号依次为0 ~ 。对齐的磁道形成圆柱，圆柱的中心轴称为主轴(Spindle)，每一磁道包括数个被间隙(Gap)分隔的扇区(Sector)，而间隔不含数据。

磁盘总容量的计算式如下。 磁盘容量的评价方式如下。

• 记录密度(Recording Density)：磁道一英寸的段能存储的位数；
• 磁道密度(Track Density)：从盘片中心出发半径上一英寸的段内的磁道数；
• 面密度(Areal Density)：记录密度磁道密度。

磁盘用读写头(Read-Write Head)来读写存储在磁性表面上的位，读写头连接至一个转动臂(Actuator Arm)的一端，在紧贴表面的一层薄薄的气垫上滑动。读写头垂直排列，一致行动。读写头冲撞(Crash)指碰到灰尘而停下，与盘面接触，这很可能损坏盘面并破坏其存储的数据。

磁盘时间性能的评价方式如下。

其中，旋转速率(PRM; Revolution per Minute)指盘片固定的转速，需要留意单位。通常，旋转速率为5400 ~ 15000PRM。

• 寻道时间(Seek Time)：移动转动臂所需要的时间，通常是3 ~ 9ms；

• 旋转时间(Rotation Time)：目标扇区的第一个位转动到头下的时间，旋转延迟和寻道时间大致相等，估算时可利用这一特性；

• 传送时间(Transfer Time)：读取目标扇区的位的时间。

访问扇区中的第一个字节耗时长，但相比之下访问剩下的数据几乎不耗时。

廉价/独立磁盘冗余阵列(RAID; Redundant Arrays of Inexpensive/Independent Disks)即磁盘阵列，将多个硬盘组合成一个逻辑硬盘，目的为提升性能或资料冗余，即提高并行性和可靠性，成本较低。

光存储(Optical Storage)

使用光盘表面的亮点和暗点表示数据。如下是使用光存储技术的介质。

• 激光唱片(CD; Compact Disc)：容量0.7 ~ 0.9GB；
• 数字多功能光盘(DVD; Digital Versatile Disc)：容量4.7 ~ 17GB；
• 蓝光光盘(BD; Blu-ray Disc)：容量超过25GB。

光学技术根据内容可变性可分为如下三类。

• 只读(ROM)：批量生产，内容不能改变；
• 可录制(R; Recordable)：数据可由用户设备写入可刻录光盘，但一旦写入数据就不能改变；
• 可重写(RW; Rewritable)：数据可以在写入光盘后进行更改，但光盘寿命更短。

输入/输出设备(I/O Device)

输入(Input)是指提交或传输到计算机系统的一切数据；输出(Output)则是计算机产生的结果。输入/输出设备是计算机与用户或其他设备通信的桥梁。

显示器(Display)

即显示文本和图像的计算机显示设备。

液晶显示器(LCD; Liquid Crystal Display)通过过滤经过一层液体晶状单元的光线产生图像。标准的LCD的光源通常是不环保的冷阴极荧光灯管(CCFL; Cold Cathode Fluorescent Lamp)，现在通常使用低功耗的发光二极管(LED; Light-Emitting Diode)替代。

触摸屏(Touchscreen)

各类触摸屏的工作原理如下。

• 电阻式(Resistive)：屏幕由基础面板和小空间分隔的柔性顶层组成，轻按顶层使其与底层接触，接触点收集并传递位置信息，不易受灰尘或水的影响，但可能会被尖锐的物体磨损；
• 电容式(Capacitive)：屏幕内含涂有导电材料薄层的透明面板，由于人体是导电体，触摸屏幕会产生电流变化。

打印机(Printer)

各类打印机的工作原理如下。

• 喷墨式(Ink Jet)：打印头由一系列喷嘴组成，每个喷嘴有对应的墨盒；
• 激光式(laser)：在光敏滚筒上涂上光点，静电荷油墨被应用到滚筒上，然后转移到纸上。

图形处理器(GPU; Graphics Processing Unit)

图形处理器的类型如下。

• 集成式(Integrated)：内置于主板上；
• 独立式(Discrete)：或称专用显卡，拥有更强劲的性能。

图形处理器有专用的内存，通常称为显存(Video Memory)。

总线(Bus)

总线是计算机组件规范化交换地址、数据和控制信号的方式，总线通常为多个设备所共享。前端总线(FSB; Front Side Bus)是指与微处理器交换数据的电路。

计数系统(Numeral System)

即使用一组数字符号来表示数的体系，理想计数系统具有如下功能：有效地描述一组数(如整数、实数)；所有的数对应唯一的表示；反应数的代数和算数结构。

数字(Numerals)

数字是计数系统的基础。

计算机领域中，有时数字一词的含义与数码(Digital)相近，其词根是数(Digit)，源于拉丁语的手、脚趾(digitus)一词，通常用于形容数字技术的事物。

巴比伦楔形数字(Babylonian Cuneiform Numerals)

巴比伦数字为目前已知的最早的的位值制数字系统，没有表示0的符号，因为这一概念未被发明。

巴比伦楔形数字符号

常见的巴比伦楔形数字符号如下。

符号	数字	符号	数字	符号	数字	符号	数字	符号	数字
-	0	𒐕	1	𒐖	2	𒐗	3	𒐘	4
𒐙	5	𒐚	6	𒐛	7	𒐜	8	𒐝	9
𒌋	10	𒌋𒌋	20	𒌍	30	𒐏	40	𒐐	50

罗马数字(Roman Numerals)

同古巴比伦数字一样，罗马数字中也没有表示0的。罗马数字的规则如下。

• 用I表示1，V表示5，X表示10，L表示50，C表示100，D表示500，M表示1000；
• 相同的字符连写时，表示相加所得之数，如III即1+1+1=3；
• 小的字符写在大的字符右边时，表示相加所得之数，如VIII即5+1+1+1=8；
• 小的字符写在大的字符左边时，大数减小数所得之数，如IV即5-1=4，此处「小的字符」仅限I、V和C，且左侧最多仅一个，同时限制I右边最大字符为X、X右边最大字符为C、C右边最大字符为M，如99表示为XCIX即100-10+10-1，而不是指示100-1的IC；
• 字符上若有横线表示增值1000倍；
• 满足上述规则的情况下，用最少的字符表示，相同的字符不超过三个，然而古罗马中4较为特殊，其表示有IIII和IV两种。

在中国，数字编码解码的规则是乘法；而在罗马，解码的规则是加减法。从编码的有效性上看，中国人的做法比罗马人高明。

阿拉伯数字(Arabic Numerals)

阿拉伯数字真正的发明者是印度人，其发明标志着数字和文字的分离。

干支纪年法(Sexagenary Cycle)

干支是天干地支的合称，两者经一定的组合方式搭配成60对，为一个周期。

• 十天干(Ten Heavenly Stems)：甲乙丙丁戊己庚辛壬癸；
• 十二地支(Twelve Earthly Branches)：子丑寅卯辰巳午未申酉戌亥。

下例代码通过给定的年份输出天干地支纪年。

const wstring s1 = L" 庚辛壬癸甲乙丙丁戊己 ";
const wstring s2 = L" 申酉戌亥子丑寅卯辰巳午未 ";
int year;
cin >> year;
(void)wcout.imbue(locale("chs")); // 中文输出设置
wcout << s1[year % 10] << s2[year % 12] << endl;

二进制(Binary)

以2为底数的计数系统，最早由德国数学家戈特弗里德·莱布尼兹提出。位(Bit)是二进制数字(Binary Digit)的缩写，通常以小写字母「b」表示；字节(Byte)是位的组合，一个字节由8个位组成，通常以大写字母「B」表示。

计算机硬件不区分无符号数据和有符号数据，而由程序，即指令来区分。

无符号编码(Unsigned)

无符号数只表示非负数，位二进制数用无符号编码表示的值如下式。

原码(Sign-Magnitude)

分配一个符号位以表示有符号数，位二进制数用原码表示的值如下式。 由上式可知，原码的符号位决定其他位的权的正负。

反码(Ones' Complement)

又称一的补码，修正原码使。正数的反码等于其原码，而负数的反码则可以通过保留其符号位，将原码的数值位取反得到。位二进制数用反码表示的值如下式。 原码和反码都使数字有和两种形式，因而加减法运算存在问题。

补码(Two's Complement)

位二进制数用补码表示的值如下式。 由上式可知，补码的符号位含义即负权重。

负数的补(原)码即其原(补)码除符号位外取反后加一；取相反数的操作是取反后加一，注意补码所能表示的最小值取反后加一仍是，即表达式-INT_MIN == INT_MIN永真。

由一个正数得到其对应负数的补码的方法如下。

1. 从右边起找到第一个出现的1；
2. 对由这个1开始(除这个1外)到最左边所有的位取反。

移码(Offset Binary)

移码即将二进制原码无符号整数所代表的值，减去一个预设值。

移码没有标准。预设值通常取，这种移码使一个数的移码和补码的最高位相反，其余各位均相同。

二进制浮点数算术标准(IEEE754)

定点数(Fixed Point Number)即固定小数点在二进制位中的位置，形式过于僵硬，不利于同时表示特别大和特别小的数；浮点数(Float Point Number)使用类似科学计数法的表示，形式灵活。

IEEE754标准规定单精度浮点数(float)和双精度浮点数(double)，内容如下。

• 单精度：符号位占位，指数位占位，小数位占位；
• 双精度：符号位占位，指数位占位，小数位占位。

IEEE754标准的浮点数具有如下数学形式。 上式右端各符号的说明如下。

• 符号(Sign)：用表示；
• 尾数(Mantissa)：用表示，规格化时的范围为，非规格化时的范围为；
• 阶码(Exponent)：用表示，使用的特殊移码，对浮点数加以的权重。

IEEE754标准规定的浮点数类型如下。

其中，令表示位于小数点后的小数区域，即定点小数。

• 正零和负零：和全为0；
• 非规格化数：全为0，不全为0，此时有且；
• 规格化数：不全为0也不全为1，此时有且；
• 无穷大：全为1，全为0；
• NaN：全为1，不全为0。

由上述可知，浮点数的可能取值在附近密集。在非规格化数与规格化数的不同定义，使得浮点数在最大非规格化数与最小规格化数间平滑过渡。

非负浮点数的示例

描述			备注
			或
最小非规格化数
最大非规格化数
最小规格化数
最大规格化数
无穷大

浮点数运算不具备结合性，见下例。

double x = (3.14 + 1e10) - 1e10; // 0.0
double y = 3.14 + (1e10 - 1e10); // 3.14

词头(Prefix)

国际单位制词头(Metric Prefix)使用10的幂次表示度量衡单位的倍数和分数；二进制乘数词头(Binary Prefix)则使用2的幂次表示大的数字，引入带的缩写符号以与国际单位制词头区分。然而，二进制乘数词头未被广泛采用，非正式的场合可在二进制领域使用国际单位制词头，因此上述二者容易混淆。

国际单位制词头与二进制乘数词头

Prefix	Character	Symbol		Symbol
Yotta	尧
Zetta	泽
Exa	艾
Peta	拍
Tera	太
Giga	吉
Mega	兆
Kilo	千
Deci	分			-	-
Centi	厘			-	-
Milli	毫			-	-
Micro	微			-	-
Nano	纳			-	-
Pico	皮			-	-
Femto	飞			-	-
Atto	阿			-	-
Zepto	仄			-	-
Yocto	夭			-	-

对于DRAM和SRAM容量相关的计量单位，通常使用；对于像磁盘、网络一类的I/O设备的容量，通常使用。

字符编码(Character Encoding)

早期编码系统(Early Encoding System)

• EBCDIC(Extended Binary Coded Decimal Interchange Code)：扩增二进式十进交换码，由IBM推出，英文字母不连续排列，中间出现多次断续；
• ASCII(American Standard Code for Information Interchange)：美国信息交换标准码，是最常用的编码系统，正确读音是/ˈæski/，使用7位表示一个字符；
• 扩展ASCII(Extend ASCII)：ASCII的超集，使用8位表示一个字符，ISO8859-1是常用的扩展ASCII字符集标准。

中文编码系统(Chinese Encoding System)

支持中文的编码系统如下。

• GB2312：1980年发布，基于ASCII，英文字符1字节，汉字2字节；
• GBK：(K：扩展)1995年发布，向下兼容GB2312；
• GB18030：2005年发布，基本兼容GBK，完全兼容GB2312；
• UTF-8：灵活性强，用1 ~ 4字节表示一个字符，英文字符1字节，汉字3字节，衍生的UTF-8 BOM(Byte Order Mark)主要是微软的习惯，无BOM才是标准格式；
• UTF-16：与UTF-8彻底不同，一个字符2字节或4字节；
• UTF-32：一个字符一律4字节。

乱码(Mojibake; 文字化け)指编码系统不相互兼容而引发的问题。

常见的由软件解码错误导致的中文乱码情况

其中，例句为「我能吞下玻璃而不伤身体」。

案例	特点	原因
鎴戣兘鍚炰笅鐜荤拑鑰屼笉浼よ韩浣3	生僻汉字居多且夹杂日文	使用国标码读取UTF-8的文本
�������²�������������	问号方块居多	使用UTF-8读取国标码的文本
我能吞下玻璃而不伤身体	注音小写符号居多	使用ISO8859-1读取UTF-8的文本
ÎÒÄÜÍÌϲ£Á§¶ø²»ÉËÉíÌå	注音大写符号居多	使用ISO8859-1读取国标码的文本
我能吞下玻璃而不伤身�?	字符串长度为偶数时正常 而长度为奇数时结尾异常	使用国标码读取UTF-8的文本后 用UTF-8再次读取
锟斤拷锟斤拷锟斤拷锟铰诧拷锟斤拷 锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷	以「锟斤拷」居多	使用UTF-8读取国标码的文本后 用国标码再次读取

编译器的中文乱码情况

如Visual Studio中，未初始化的栈空间用0xCC填充，而未初始化的堆空间用0xCD填充。而0xCCCC和0xCDCD在GB2312中分别对应「烫」和「屯」两个汉字。因此「烫烫烫」的情况可能意味着栈溢出，而「屯屯屯」的情况可能意味着堆溢出。

校验码(Check Digit)

校验码通常是一组数字的最后一位，由前面的数字通过某种运算得出，用以检验该组数字的正确性。

古犹太人抄写「圣经」，将每一个希伯来字母对应一个数字，每行文字加起来就得到一个特殊的数字，这个数字便是这一行的校验码。犹太学者每抄写一页，就会检查校验码是否与原文相同。

奇偶校验位(Parity Bit)是最简单的校验码。偶校验补充一个位，使得总的1的个数为偶数(奇校验则为奇数)。偶校验实际上是循环冗余校验中生成多项式为的特例。

汉明校验码(Hamming Code)

理查德·汉明(Richard Hamming)

美国数学家，发明汉明校验码，在计算机科学和电讯领域有重要贡献。

汉明校验码的实现原理是在个数据位中加入个校验位，并将每一个数据位分配在若干奇偶校验组中，使不仅能发现出错，还能指出出错的位置。

个校验位能表示个状态，其中一个状态表示「没有错误」而其余的个状态指出错误发生在哪一位。错误也可能发生于校验位，因此有个状态用于纠正数据的一位错，即下式。 若能检测并自动纠正一位错，并发现两位错，则需满足下式。 校验位通常被安排在的位置，其覆盖范围为数据位置和该校验位位置的二进制与的值不为0的数据。

海明码的数据位位置和校验位位置案例

其中，假设数据位位数，由式得有最小值。

海明码位号	数据位/校验位	海明码位号与校验位位号之和的关系

要检查某一位的错误，则需检查某一位所包含的所有奇偶校验位。

循环冗余校验(CRC; Cyclic Redundancy Check)

在个比特的数据后追加位冗余码，计算的方法如下。

1. 在二进制数据的后面追加个0，得到位二进制数据；
2. 除以事先规定的位的除数，得到余数；
3. 将余数拼接在原数据后。

常用的CRC版本如下。

其中：表示二进制除数的第位；称为生成多项式。

• CRC-8：；
• CRC-12：；
• CRC-16：；
• CRC-CCITT：：。

通信(Communication)

通信即发送者通过某种媒体以某种格式来传递信息到接收者以达成某个目的。

数据通信(Data Communication)

即通信技术与计算机技术结合而产生的通信方式。

消息(Message)在数据通信中，指由计算机本身发送而属于其人类用户之间，或不同程序/同一程序的不同组件互相发送的内容。

信号(Signal)是数据的电气或电磁的表现，可分为如下两类。

• 模拟信号(Analog Signal)：消息的参数取值是连续的；
• 数字信号(Digital Signal)：消息的参数取值是离散的。

数据通信的目的是将消息以信号的形式传递给接收者，使接收者获得最多的信息。一个数据通信系统可划分为如下三部分。

• 源系统：又称发送端或发送方；
  • 信源(Source)：产生传输的数据，来自信源的信号称基本频带信号(Baseband Signal)或基带信号；
  • 发送器：如调制器，调制(Modulation)即使基带信号能够在信道中传输的操作。
• 传输系统：又称传输网络或信道(Channel)，即向某一方向传送消息的媒体；
• 目的系统：又称接收端或接收方。
  • 接收器：如解调器，解调(Demodulation)即调制的逆过程；
  • 信宿(Destination)：接收数字比特流。

调制可分为如下两类。

• 基带调制：又称编码(Encoding)，将数字信号转为另一种数字信号，变换后的信号仍是基带信号；

  常见编码方式

  其中，自同步能力即能从信号波形本身提取信号时钟频率。

  编码方式	0的描述	1的描述	说明
  不归零制	负电平	正电平	没有自同步能力
  曼彻斯特(Manchester)编码	位中心向上跳变	位中心向下跳变	有自同步能力，中心必跳变
  差分曼彻斯特编码	位开始边界有跳变	位开始边界无跳变	有自同步能力，中心必跳变

• 带通调制：将基带信号的频率搬移到更高频段，并转为模拟信号，变换后的信号称为带通信号，一般情况的讨论下，调制就是指带通调制。

  常见带通调制方式

  带通调制方式	示例
  调幅(AM; Amplitude Modulation)	0或1分别对应无载波或有载波输出
  调频(FM; Frequency Modulation)	0或1分别对应频率或
  调相(PM; Phase Modulation)	0或1分别对应相位0°或180°

根据通信双方交互的方式，通信可以有如下三种基本方式。

• 单工(Simplex)：只有一个方向的通信而没有反方向的交互，如无线电广播等；
• 半双工(Half Duplex)：双方都能发送消息，但不能同时，如电话、短信等；
• 全双工(Full Duplex)：双方可以同时发送和接收消息。

数据(Data)是未经处理、没有意义的、对现实世界客观事物的符号表示。数据是载荷信息的媒体，是运送消息的实体。码元(Symbol)是数字信号中的概念，代表不同离散数值的基本波形，即矩形脉冲。在使用二进制编码时，只有两种不同的码元，一种表示0状态，另一种表示1状态。

波特率(Baud)又称调制速率或码元传输速率，指每秒传送的码元状态数。码元周期即传送一个码元状态所需的时间。

失真(Distortion)指信号在传输过程中发生扭曲和变化。接收端波形失真的因素可能如下：码元传输速率快；信号传输距离远；传输媒体质量差；噪声干扰。

奈奎斯特-香农采样定理(Nyquist-Shannon Sampling Theorem)又称奈氏准则，该准则指出，在任何信道中，码元传输的速率是有上限的，传输速率超过此上限，就会出现严重的码间串扰(接收端收到的信号波形失去了码元间的清晰界限)的问题，使接收端对码元的识别成为不可能。

奈奎斯特指出，信道的极限传输速率(单位为bps)如下。

其中：为信道的带宽(单位为Hz)；为码元的不同状态数。

香农指出，信道的极限传输速率如下。

其中：为信道的带宽；为信道内所传信号的平均功率；为信道内部的高斯噪声功率。

上式中又称信噪比(SNR; Signal-to-Noise Ratio)，以分贝形式表示时为。

信道的带宽或信道中的信噪比越大，信息的极限传输速率就越高。

奈氏准则的意义在于，只要信息传输速率低于信道的极限传输速率，就一定可以找到某种方法实现可靠传输。

信息论(Information Theory)

克劳德·香农(Claude Shannon)

美国数学家，信息论创始人。

信息论是应用数学的分支，主要研究的是对「信号包含信息的多少」进行量化。信息论的基本想法如下。

• 「不太可能的事情居然发生」要比「非常可能的事情发生」能提供更多的信息，如「今天早上会有日食」比「今天早上太阳升起」的信息更为丰富；
• 独立事件应具有增量的信息，如「投掷的硬币两次正面朝上」传递的信息量，应该是「投掷的硬币一次正面朝上」的信息量的两倍。

信息(Information)是数据的内涵，对数据语义的解释，泛指人类社会传播的一切内容。当数据以人类能够理解和使用的形式表现时，就成为了信息。

香农认为，信息是用来消除随机不定性的东西。为满足信息论的基本想法，对随机变量的事件的自信息(Self-Information)，即随机变量的某个事件发生所带来的信息量，作出如下定义。 知识(Knowledge)是起预示作用的、经过验证的、有组织的信息。

信息熵(Information Entropy)

又称香农熵(Shannon Entropy)，即自信息关于概率分布的期望，用以表示信息的「价值」的含量。信息的不确定性越大，信息熵也就越大。对于任意一个随机变量，它的信息熵定义如下。

已知的信息越多，随机事件的不确定性就越小。假设还存在随机变量，定义条件熵(Conditional Entropy)如下。 可证明，当已知信息和所研究信息没有任何关系时等号成立。

推广至多维随机变量的分布，定义联合熵(Joint Entropy)如下。 联合熵相当于条件熵与已知信息单独的信息熵之和，即有下式。

KL散度(Kullback-Leibler Divergence)

又称相对熵，衡量两个取值为正数的函数的相似性，定义如下。

其中，和是同一随机变量的两个单独的概率分布。

KL散度具有如下性质。

• 对于两个完全相同的函数而言，它们的KL散度等于零；
• KL散度越大，两个函数差异越大；
• 概率分布、概率密度函数取值均大于零时，KL散度可以度量两个随机分布的差异性。

交叉熵(Cross Entropy)

交叉熵与KL散度类似，其定义如下。

其中，和是同一随机变量的两个单独的概率分布。

计算机网络(Computer Network)

见计算机网络。

移动互联网(Mobile Internet)

移动设备(Mobile Device)又称移动终端，即小型的、手持的智能设备。移动互联网是以移动网络作为接入网络的互联网及服务，包括移动设备、移动接入网络和移动应用服务等，有时又称蜂窝网络(Cellular Network)。重要的移动网络技术如下。

• 1G：使用模拟技术，支持语音通信；
• 2G：利用数字技术替代了模拟技术，并增加了对文本消息形式基本数据传输的支持，主流的标准有全球移动通讯系统(GSM; Global System for Mobile Communications)等；
• 3G：同时支持语音和数据信号的数字传输，主流的标准有宽频码分多址(W-CDMA; Wideband CDMA)等；
• 4G：更高的数据吞吐量，主流的标准有长期演进技术(LTE; Long Term Evolution)等。

无线应用协议(WAP; Wireless Application Protocol)将互联网丰富信息及先进业务引入到移动电话等无线移动终端。无线接入点(WAP; Wireless Access Point)也称WAP，使设备通过无线网络连接至有线网络。

移动接入网络(Mobile Access Network)包括如下三类技术：移动网络接入技术；移动组网技术，分布式组网动态、灵活；移动网络管理技术，不同网络的无缝切换，实现异构融合。

无线热点(Wi-Fi)基于IEEE802.11标准的无线局域网技术，为公众提供互联网接入。Wi-Fi一词没有任何意义，也没有全写。无线接入点每100ms都会将服务集标识(SSID; Service Set Identifier)广播一次，用户可以借此决定是否要和这一SSID的无线接入点连接。

自组织无线网络(Ad-Hoc)是无中心的自组织动态拓扑网络。Ad-Hoc一词源自拉丁语，引申为特地的某种目的。Ad-Hoc没有集中的接入点，一些可移动的设备发现其附近有其他的可移动设备，并且要求和其他的可移动设备进行通信，从而形成Ad-Hoc网络。Ad-Hoc路由协议分为如下几种。

• 先验式(Proactive)：每个结点维护其至网络中其他结点的路由信息表，当网络拓扑结构发生变化时，结点通过交互信息来实时地维护到网络中其他结点的路由，路由延迟小，但路由开销大；
• 按需式(On-Demand)：源结点根据需要通过路由发现过程来确定路由，路由开销小，但路由延迟大；
• 混合式(Hybrid)。

物联网(IoT; Internet of Things)

传感器(Sensor)感受被测量的信息，并变换为所需形式的信息输出的检测装置，是物联网得以实现的关键。传感器一般由敏感元件、转换元件、变换电路和辅助电源四部分组成。

惯性测量单元(IMU; Inertial Measurement Unit)属于传感器的一种，用于需要进行运动控制的设备，或用姿态进行精密位移推算的场合，其封装的三种常见传感器如下。

• 加速度计(Accelerometer)：感知任意方向上的加速度，测量设备的受力情况；
• 陀螺仪(Gyroscope)：感知角速度、旋转角度的变化，测量设备的旋转运动；
• 磁力计(Magnetometer)：测量磁场以定位设备的方位。

物联网又称传感网，是随机分布的集成传感器、数据处理单元和通信单元的微小结点，通过一定的组织和通信方式构成的网络，用以实现智能化识别、定位、跟踪、监控和管理。

物联网被称为继计算机、互联网后世界信息产业发展的第三次浪潮。物联网基本架构可分为如下三层：识别物体、采集信息的感知层；信息传输的网络层；信息处理的应用层。

适用于物联网的无线技术

Wi-Fi相当耗电，不适合作为物联网无线技术，而适用于物联网的无线技术如下。

• 射频识别(RFID; Radio Frequency Identification)：非接触的自动识别技术，是条码识别的代替品，可分为主动、半被动和被动三种类型，其系统的基本工作方式可分为全双工、半双工系统和时序系统；
• 近场通讯(NFC; Near-Field Communication)：RFID的演变；
• 蓝牙低功耗(Bluetooth Low Energy)：用于物联网的蓝牙技术，相较经典蓝牙保持同等通信范围且同时显著降低功耗和成本；
• ZigBee：一种各业界共同通用的低速短距无线通信技术。

无线传感器网络(WSN; Wireless Sensor Network)

WSN是分布式传感网络，其末梢是可以感知和检查外部世界的传感器。WSN由部署在区域内大量廉价微型传感器结点组成，协作地感知、采集和处理网络覆盖区域中被感知对象的信息，并发送给观察者。WSN、通信技术和计算机技术共同构成信息技术的三大支柱。

传感器、感知对象和观察者是WSN的三个要素。

微机电系统(MEMS; Micro-electro-mechanic System)

微机电系统即尺寸很小的高科技电子机械器件。微机电系统由微传感器、微执行器和微电子器件三部分组成。

全球卫星导航系统(Global Navigation Satellite System)

现有的全球卫星导航系统如下。

• 美国全球定位系统(GPS; Global Position System)；
• 俄罗斯全球卫星定位系统(GLONASS)；
• 中国北斗卫星导航系统(BDS)；
• 欧洲伽利略卫星导航系统(GALILEO)。

云计算(Cloud Computing)

云计算是以资源租用、应用托管、服务外包为核心的全新互联网应用模式。根据云计算所提供服务的不同，云计算可分为如下几种服务模式。

• 软件即服务(SaaS; Software as a Service)；
• 平台即服务(PaaS; Platform as a Service)；
• 基础设施即服务(IaaS; Infrastructure as a Service)。

云计算的演化有如下四个阶段：电厂模式阶段；效用计算阶段，资源打包计费，按照计算和存储分别计量费用；网格计算阶段，由松散耦合的计算机集群执行大型任务；云计算阶段。

Google文件系统(GFS; Google File System)是由Google提出的专用分布式文件系统。GFS旨在以廉价且不可靠的硬件上构建可靠的分布式文件系统，应对大型文件处理并支持大量用户同时访问。

GFS集群由一个主服务器(Master)和多个块服务器(Chunk Server)组成，每个文件拆分为若干个64兆字节的文件块(Chunk)，每个文件块都由主服务器根据其创建时间指定的块句柄，存储于块服务器的本地磁盘中，并多处热备份块文件。客户端可与主服务器和块服务器通信，向主服务器索取块句柄，并根据块句柄于块服务器查找数据。

每个文件块又被划分为64千字节的若干小块(Block)，每小块对应一个32字节的校验码。

面向服务架构(SOA; Service Oriented Architecture)

SOA指软件的部分组件即调用者，可以通过网络通用协议调用另一个软件组件，以获得服务。企业服务总线(ESB; Enterprise Service Bus)是实现企业级SOA的核心支撑手段。云计算技术体系可分为如下四层：物理资源层；资源池层；管理中间件；SOA构建层。

数据仓库(DW; Data Warehouse)

强调利用某些特殊资料存储方式，有利于分析处理，以产生有价值的信息并依此作决策。

数据仓库具有主题导向(Subject-Oriented)、集成化(Integrated)、相对稳定(Nonvolatile)等的特性；而数据库面向事务，符合范式要求；数据仓库面向主题，允许冗余。

大数据(Big Data)

数据的容量、获取速度或数据的表示限制了使用传统关系方法对数据的分析处理能力，需要使用水平扩展机制来提高处理效率。

大数据的四个显著特点即4V，内容如下：数据容量(Volume)巨大；数据多样(Variety)；处理速度(Velocity)快；价值(Value)密度低。

大数据处理方式可分为如下两种。

• 流(Stream)式处理：数据以流的方式连续到达，由于流携带大量数据，小部分数据流被保存在有限的内存中，通常工作在毫秒级别，用于在线应用；
• 批(Batch)处理：数据先被存储，然后再分析，广泛应用于各个领域。

MapReduce是Google提出的批处理模型。其核心思想是将数据块并行处理并以分布方式产生中间结果，最后这些中间结果被合并产生最终结果。程序员只需执行简单计算，不必关心已封装的并行化、容错、数据分布、负载均衡等细节。

人工智能(AI; Artificial Intelligence)

人工智能是研究人类智能活动的规律，构造具有一定智能的人工系统，研究如何让计算机去完成以往需要人类智慧才能胜任的工作。人工智能的发展路径如下。

• 弱(Weak)AI：只能做特定任务，即模仿人类智力活动的某些方面；
• 强(Strong)AI：真正通用的，像人类一般思考的智能系统；
• 超级AI：其能力超越人类，且能不断自我学习和进化。

人工智能的四个能力特征如下：感知外部世界的能力，对外部刺激信息进行获取和加工；记忆与思维能力；学习与自适应能力，从样例或从与环境的交互进行学习；行为能力，即对外界的智能化反应。

图灵测试(Turing Test)由阿兰·图灵提出，测试机器能否仅通过文本表现出与人等价或无法区分的智能。尤金·古斯特曼(Eugene Goostman)是首个勉强通过图灵测试的计算机。

马文·明斯基(Marvin Minsky)

美国计算机科学家，专长于人工智能与认知科学领域。

约翰·麦卡锡(John McCarthy)

美国计算机科学家，LISP语言的发明者。

约翰·麦卡锡首次定义「人工智能」的概念，即「使机器的行为像人类的行为一样」。

达特茅斯会议(Dartmouth Workshop)由马文·明斯基、约翰·麦卡锡和克劳德·香农发起，主要讨论机器是否能像人类一样思考，催生了人工智能革命。

深蓝(Deep Blue)是由IBM开发的超级计算机，作为人工智能的代表之一，曾击败国际象棋世界冠军。

机器学习(ML; Machine Learning)

见机器学习相关整理。

计算机视觉(CV; Computer Vision)

计算机视觉利用摄像头和计算机代替人眼对目标进行识别、跟踪和测量，并进一步做图像处理。OpenCV是经典的计算机视觉开源工具库，使用OpenCV完成计算机视觉任务见python库相关整理的OpenCV部分。

计算机安全(Cybersecurity)

指信息系统(硬件、软件、数据、人、物理环境及其基础设施)受到保护, 不受偶然的或恶意的原因而遭到破坏、更改、泄露，系统连续可靠正常地运行，信息服务不中断，最终实现业务连续性。

计算机安全即保护系统和数据的如下特性。

• 保密性(Secrecy)：只有授权用户才能读取计算机系统和数据；
• 完整性(Integrity)：只有授权用户才能修改计算机系统和数据；
• 可用性(Availability)：授权用户应随时能够访问系统和数据。

安全专家为实现保护，从上述三个抽象层面分假想敌，称为威胁模型(Threat Model)，假想敌的攻击手段称为攻击矢量(Attack Vector)。而黑客(Hacker)正是凭借技术知识闯入计算机系统的人或团体，可分为如下几类。

• 白帽(White Hat)黑客：寻找并修复系统漏洞，经常被公司和政府雇佣以做安全评估；
• 网络罪犯(Cybercriminal)：窃取、利用和销售计算机漏洞和数据；
• 黑客行动主义者(Hacktivist)：影响社会或达到政治目的。

能够在计算机间相互传播的恶意程序称蠕虫(Worm)。这些由黑客可控的计算机组成僵尸网络(Botnet)，其作用如下：发送大量垃圾邮件(Spam)；盗用算力；发起分布式拒绝服务攻击(DDoS; Distributed Denial of Service)，用于堵塞网络。

漏洞利用(Exploit)即利用系统漏洞以获得某些能力如访问权限。漏洞利用的常见方式如下。

• 缓冲区溢出(Buffer Overflow)：超额的输入数据覆盖内存其他区域造成系统崩溃，可进行边界检查以防御，也可设置特定值用于验证数据是否因溢出损坏，这一特定值称金丝雀(Canary)，因为曾经矿工会带金丝雀下矿，金丝雀会警告危险；
• 代码注入(Code Injection)：输入的部分包含可执行代码，如SQL注入等。

防范漏洞利用，应该总是假设外部数据是危险的。

零日漏洞(Zero-Day Vulnerability)指针对未发布补丁的安全漏洞，对计算机系统的安全有巨大威胁。

暴力攻击(Brute Force Attack)即尝试解的所有可能组合。计算机系统可通过设置等待时间和锁定以防御。新的攻破方法如内存镜像，物理接触设备以复制整个内存，通过重置内存以避免等待和锁定。

身份认证(Authentication)使计算机得知使用者身份。身份认证的三种类型如下。

• 你知道什么(What You Know)：基于只有用户和计算机所知道的，如密码等，但易被暴力攻击破解；
• 你有什么(What You Have)：基于用户持有的特定物体，如电子卡、令牌等，但攻击者与用户物理距离较近时危险；
• 你是什么(What You Are)：基于生物特征认证，如指纹、虹膜等，但是概率性的(Probabilistic)，系统可能辨识不出用户。

上述三类方式都有优缺点，因此有时采用双因素认证(2FA; Two-Factor Authentication)。

访问控制(Access Control)用于控制用户访问的规范。访问控制通常通过访问控制表(ACL; Access Control List)实现，访问控制表描述用户对每个文件、文件夹和程序等的访问权限。通常权限可分为如下几类：读取(Read)；写入(Write)；执行(Execute)。

安全内核(Security Kernel)是尽可能少的、安全性接近可验证的系统软件，又称可信计算基础(Trusted Computing Base)。

社会工程学(Social Engineering)

社会工程学是最常见的入侵方式，通过欺骗使其泄密信息。社会工程学攻击的常见方式如下。

• 钓鱼(Phishing)：通过以假乱真的网页欺骗用户输入真实信息；
• 假托(Pretexting)：如电信欺诈；
• 特洛伊木马(Trojan Horse)：伪装成无害物的恶意软件(Malware)或勒索软件(Ransomware)。

密码学(Cryptography)

本意为「秘密写作」，加密(Encryption)即通过加密算法(Cipher)将明文转为密文(Ciphertext)，解密(Decryption)即将密文恢复为明文。简单的加密策略有如下两种。

• 替换加密(Substitution Cipher)指将明文的每个字母替换成其他字母，替换加密后明文与密文对应字母出现的频率是一样的，易被熟练的破译员发现规律进而破译；
• 位移加密(Permutation Cipher)指将明文填入矩阵，更换读出的顺序产生密文。

凯撒加密(Caesar Cipher)将明文的字母向前移动三个位置实现加密，据称罗马共和国末期军事统帅尤利乌斯·凯撒(Julius Caesar)曾用此方法与其将军们进行联系。

英格玛(Enigma)是纳粹在战争时期使用的加密机。英格玛并不是简单的替换加密，它拥有三个或更多的替换转子作为一次替换的映射，一个转子的输出作为下一个转子的输入，后置反射器将信号发回给转子，前置插板可将输入的字母预先进行替换。纳粹为英格玛制作了密码本，包含每日的配置。

巨人1号(Colossus MK 1)是巨人计算机系列，由英国密码分析师设计，用于破解纳粹通信。巨人1号是第一个大规模使用真空管的计算机，也被认为是第一个可编程电子计算机。

炸弹机(Bombe)是在巨人1号诞生前由阿兰·图灵制作的机电装置，同样用于破解纳粹通信。Bombe严格来说不属于计算机。巨人1号和Bombe都诞生于英国布莱切利园。

随计算机的发展，密码学逐渐由硬件转向软件。数据加密标准(DES; Data Encryption Standard)是应用最广泛的早期加密算法，随后出现了高级加密标准(AES; Advanced Encryption Standard)，现在难以破解，且在性能与安全性间取得平衡。

密钥交换(Key Exchange)

密钥交换不发送密钥，但依然让两台计算机在密钥上达成共识。通过单向函数(One-Way Function)实现，即难以逆向推算出输入的函数。一种常见的形式是迪菲-赫尔曼密钥交换(Diffie–Hellman Key Exchange)，其流程大致如下。

1. 通信的双方甲和乙协定使用素数以及基数；
2. 甲选择一个秘密整数，计算并发送给乙；
3. 乙选择一个秘密整数，计算并发送给甲；
4. 最终甲计算，乙计算，得到一样的值，用作对称密钥，结合如AES之类的加密技术来加密通信。

非对称加密(Asymmetric Encryption)

非对称加密使用两个不同的密钥，即公钥(Public Key)和私钥(Private Key)，使用公钥加密信息，而私钥的持有者才能解密。目前最流行的非对称加密技术是RSA，得名于其发明者Rivest、Shamir和Adleman。知道公钥只能加密但不能解密，因而称「非对称」。

视觉设计(Visual Design)

色彩模型(Color Space)

CMYK

即印刷四分色，是彩色印刷时采用的一种套色模式。印刷品的色彩由青(Cyan)、洋红(Magenta)、黄(Yellow)和黑(Black)四种颜色的散点组成，控制这些散点的大小、密度和角度就能混出颜色。

理论上CMYK可形成种颜色，加上印刷油墨并非理想纯色的原因，其实际形成的色彩空间必小于RGB，故而不能以屏幕上所看到的色彩要求印刷品的色差。

RGB

即三原色，将红绿蓝三色的色光以不同比例相加而产生各种颜色，广泛用于在电子系统中表示图像。

理论上RGB可形成种颜色。

HSB

将RGB色彩模型的点在圆柱坐标系中的表示法，又称HSV颜色空间。

• 色相(Hue)：颜色种类；
• 饱和度(Saturation)：鲜艳程度；
• 明暗(Brightness/Value)：暗亮程度。

基于HSB色彩模型描述的色彩搭配如下。

• 单色(Monochrome)搭配：保持色相不变，饱和度、明暗发生变化；
• 类比(Analogous)搭配：选用颜色的色相值保持在色相环相邻的60°内；
• 互补/对色(Complimentary)搭配：撞色/强烈色搭配，即色相值间隔180°；
• 三角(Triad)搭配：三色搭配，两两颜色色相间隔120°。

排版(Typography)

乱数假文(Lipsum)

Lorem ipsum dolor sit amet.

西方传统印刷业时就开始使用的没有实际意义的拉丁文组合，用于排版测试的占位文字，据传是某个工匠随意选取的，经考证出自「善恶之尽」。

敏捷的棕毛狐狸(The Quick Brown Fox)

The quick brown fox jumps over the lazy dog.

在Microsoft Office Word中使用=rand()命令(新版本则是=rand.old())会生成此句，此句也是著名的全字母句，通常用于英文测试字体显示效果和键盘故障。