第一章 绪论

1.图灵模型

• 数据处理器：一个接受输入数据、处理数据并产生输出数据的黑盒。这种对计算机的定义太宽泛。
• 可编程数据处理器：计算机的输出数据除依赖于输入数据外，还依赖于程序，输出数据=f(输入数据,程序)。
• 通用图灵机：一种只要提供了合适的程序就能做任何运算的机器，这是对现代计算机的首次描述。

2.冯.诺依曼模型

• 程序和数据在逻辑上是相同的，因此程序也应该存储在计算机的存储器中。
• 该模型包括四个子系统
  • 存储器，存储数据与程序
  • 算术逻辑单元，进行算术逻辑运算
  • 控制单元，控制其他几个子系统
  • 输入/输出
    • 输入接受输入数据和程序
    • 输出将结果送到计算机外部
• 存储的程序（指令）是按照顺序执行的（虽然可能会有跳转）

3.计算机的组成部分

• 计算机硬件，依据冯.诺依曼模型且包含四部分
• 数据
  • 存储数据，以01位模式存储在计算机内部
  • 组织数据，数据存储在计算机中前，可以有效组织成不同的实体和格式
• 计算机软件，冯.诺依曼模型的主要特征是程序的概念
  • 程序必须是存储的
  • 程序必须是有序的指令集，指令集使得重用成为可能
  • 算法，通过合适组织指令来给出解决问题的一系列步骤
  • 语言，（高级）计算机语言使得能以方便人理解与编写的方式来生产程序，避免直接使用机器语言编程的低效
  • 软件工程，结构化程序的设计和编写中应遵循的原理和规则
  • 操作系统，最初是为程序访问计算机部件提供方便的一种管理程序，如今功能更加强大

4.历史

• 机械计算机器（1930年以前）
• 电子计算机的诞生（1930年-1950年）
  • 早期的电子计算机（ENIAC等）
  • 基于冯.诺依曼模型的计算机（EDVAC等）
• 计算机的诞生（1950年至今）

5.社会问题和道德问题（略）

6.计算机作为一门科学

• 系统领域：计算机体系结构、计算机网络、安全问题、操作系统、算法、程序设计语言、软件工程等
• 应用领域：数据库、人工智能等

第二章 数字系统

数字系统定义了如何用独特的符号来表示一个数字。可分为位置化数字系统和非位置化数字系统。

位置化数字系统

• 通用表示方法：+/-(Sk-1 ... S2 S1 S0 . S-1 S-2 S-l)b
• 常见位置化数字系统
  • 十进制(decimal)
  • 二进制(binary)
  • 八进制(octol)
  • 十六进制(hexadecimal)

其他进制转换为十进制

直接用各数位上的十进制值乘以相应的位置量值，然后相加。例如：-(A1.C)16 = -(10*16^1 + 1*16^0 + 12*16^-1) = -161.75。

十进制转换为其他进制

根据书中的算法，将其以javascript实现如下：

let assert = require('assert');
/**
 * 将十进制实数字符串转换为其他进制(2-16)的字符串表示
 * @param {String} numStr 十进制实数字符串
 * @param {number} radix 目标进制（2-16）
 * @param {number} precision 小数最长保留位数，默认值12
 */
function radixConvert(numStr, radix, precision){
    numStr = numStr.toUpperCase();
    assert(/^[\+\-]?((\d+)|([\dA-F]+\.[\dA-F]+))$/.test(numStr), '非法十进制实数');
    assert(radix>=2 && radix<=16, '不满足进制取值的合法区间[2,16]');
    precision = precision || 12;

    let getCharOf = num=>num<10?''+num:String.fromCharCode(55+num);
    
    // 符号
    let symbol = '';
    if(/^[\+\-]/.test(numStr)){
        symbol = numStr[0];
        numStr = numStr.slice(1);
    }
    
    // 分解整数和小数部分
    let parts = numStr.split('.');

    // 转换整数部分
    let int = parseInt(parts[0]);
    let intTarget = [];
    while(int > 0){
        intTarget.unshift(int%radix);
        int = (int-intTarget[0])/radix;
    }
    intTarget = intTarget.map(item=>getCharOf(item));

    // 转换小数部分
    let floatTarget = [];
    if(parts.length > 1){
        let float = parseFloat('0.'+parts[1]);
        while(float > 0 && floatTarget.length < precision){
            float *= radix;
            floatTarget.push(Math.floor(float));
            float -= floatTarget[floatTarget.length-1];
        }
        floatTarget = floatTarget.map(item=>getCharOf(item));
    }

    return symbol + 
        (intTarget.length>0? intTarget.join('') : '0')+ 
        (floatTarget.length>0 ? '.'+floatTarget.join('') : '');
}

let num = -101.625;
// 测试
console.log(radixConvert(num.toString(), 16));// -65.A
console.log(radixConvert(num.toString(), 8));// -145.5
console.log(radixConvert(num.toString(), 2));// -1100101.101

// js的原生转换方法
console.log(num.toString(16));// -65.a
console.log(num.toString(8));// -145.5
console.log(num.toString(2));// -1100101.101

其主要思路是：

• 对于整数部分，不断除以进制，将各次的余数从右到左排列起来
• 对于小数部分，不断乘以进制，将各次的结果的整数部分从左到右排列起来
• 十进制有限小数可能在其他进制中不能以有限位小数准确表示，为此通常需要指定精度

其他进制间的转换

• 二进制和八进制：每三个二进制位对应一个八进制位
• 二进制和十六进制：每四个二进制位对应一个八进制位
• 八进制和十六进制：以二进制为中介

非位置化数字系统

• 这种系统仍旧使用有限的数字符号，但是他们的值和位置没有关系
• 为求其值，将各数字符号的代表值相加即可；一个
• 罗马数字系统是个例子（虽然各符号的值和位置无关，但是有一定的书写规范）

第三章 数据存储

数据类型

• 数据能以数字、文本、音频、图像、视频等形式存在，包含这些数据的信息在计算机行业中成为多媒体
• 计算机内部的数据采用位模式的通用格式来存储
  • 位（bit，binary digit），计算机中的最小存储单元，只能表示两种状态0或1
  • 位模式，位的序列，也被成为位流；长度为8的为模式成为1字节
• 数据存储在计算机中还会涉及到压缩、错误检测和纠正等

存储数字

存储数字时，对于小数点有两种处理方式

• 定点，把数字作为整数存储，无小数部分
• 浮点，把数字作为实数存储，带小数部分

存储整数

整数通常使用定点的方式存储在内存中。

无符号表示法

• 只能表示非负整数，分配n为能表示的整数范围：0~2^n-1
• 应用：计数、寻址、存储其他数据类型（如文本、图像、音视频）

符号加绝对值表示法

• 直接用最左边1位表示符号（0表示正数，1表示负数），后续位表示绝对值
• 这种表示法会出现两个零：+0和-0
• 应用：采集模拟信号（如音频）

二进制补码表示法

• 反码：所有位全部反转后得到反码，两次反码操作复原
• 补码：反码+1（或：从右复制位，直到有1被复制，然后翻转其余各位），两次补码操作复原
• 补码表示法
  • 最左位表示符号，0正1负
  • 计算机中整数的标准表示法

存储实数

• 很大的整数部分或很小的小数部分不应该使用定点方式存储，浮点表示法（如科学计数法）是个很好的选择
• 使用浮点表示法规范化实数：符号 指数 尾数，例如(1001.011)2规划化后为+ 1.001011 * 2^3
  • 符号用1个二进制位表示（0正1负）
  • 指数表示小数点移动位数（可正可负），它采用余码的方式表示
  • 尾数省略小数点前的1（对于二进制总会是1）
• IEEE的单双精度浮点数标准
  • 单精度：符号（S）1位，指数（E）8位，尾数（M）23位，共计4字节
    • 最大绝对值：(1-2^-24)*2^128，此时指数为0xFE，尾数为0x7FFFFF
    • 最小绝对值：2^-126，此时指数为0x01，尾数为0x000000
    • 非正规化最小绝对值2^-149，此时指数为0x00(此时表示的是-126而不是-127)，尾数为0x0000001
    • 另外还有特定的模式表示0（全部为0）和正负无穷
  • 双精度：符号（S）1位，指数（E）11位，尾数（M）52位，共计8字节
  • （更多参考）
    • 维基百科：https://en.wikipedia.org/wiki/IEEE_754-1985#Single_precision
    • CSDN博客文章：IEEE 754浮点数表示标准

存储文本

• 文本由一系列的符号构成，表示一个字符集的所需要的位模式的长度和字符集字符数量之间是对数关系
• 不同的位模式集合被设计来表示文本符号，这些集合称为代码；表示符号的过程称为编码
• 常用编码：
  • ASCII（American Standard Code for Information Interchange，美国信息交换标准码），7位，可表示128个字符
  • Unicode，32位，兼容ASCII
  • 其他编码，相对没有Unicode流行

音频

音频本身是模拟数据，需要离散采样才能存储，大致分为如下几步：

• 采样
  • 合适的采样率和音频的变化剧烈程度相关，通常40000采样率的音频足够好
• 量化
  • 可能会将样本值进行截取取整
• 编码
  • 位率R = 每样本位的数量（位深度）B * 每秒样本数S
  • 流行的MP3音频编码使用每秒样本数44100，位深度16，结果信号位率705600b/s，采用有损压缩法

存储图像

光栅图

在存储模拟图像时使用，类似音频需要对图像进行采样（扫描），其样本称为像素（图像元素）

• 解析度
  • 单位尺寸的像素数量
• 色彩深度
  • 存储像素色彩的位的数量
  • 真彩色：使用24位，可以表示1600多万种颜色值
  • 索引色（调色板色）：部分颜色（通常256种）的索引
• 图像编码标准
  • JPEG使用真彩色，但压缩图像以减少位的数量
  • GIF使用索引色

矢量图

• 使用数学公式来表达图像，而非逐个像素表达，从而缩放不失真
• 应用：flash、字体、工程制图等

视频

• 视频是图像（帧）在时间上的表示，帧的序列构成了视频
• 视频通常是被压缩存储的，MPEG是一种常见的视频压缩技术

第四章 数据运算

逻辑运算

位层次上的逻辑运算

• 非（NOT）
• 与（AND）
• 或（OR）
• 异或（XOR）

真值表如下：

模式层次上的逻辑运算

只需要将位层次上的各逻辑运算应用到一个模式的各个位，或两个模式的各对应位对。

应用

• 求反，利用NOT，让模式的各位取反
• 使指定的位复位，利用AND，其中第二个输入称为掩码，掩码中的值为0的位对应位置被复位（设为0）
• 使指定的位置位，利用OR，掩码中的值为1的位对应位置被置位（设为1）
• 使指定的位反转，利用XOR，掩码中的值为1的位对应位置被反转

移位运算

逻辑移位

• 用于无符号整数的移位，分为左移和右移，空位以0填充
• 另一种逻辑移位：循环移位，空位被移出位填充

算术移位

• 用于使用二进制补码方式的带符号整数
• 算术右移：保留符号位，并将符号位复制到空位上，用于除以2（向下）取整操作
• 算术左移：和逻辑左移相同的方式，但是结果以有符号数解读，用于乘以2操作，可能发生溢出（符号位改变）

举例：

算术运算

由于乘法、除法复杂度太高，只讲加减法。

• 整数的算术运算
  • 二进制补码中的加减法
    • 减法中将被减数转变为其补码，然后做加法
    • 注意结果是否有溢出
  • 符号加绝对值整数的加减法
• 实数的算术运算
  • 实数的加减法：将两个实数取规范化，移位以统一指数，然后做符号加绝对值（尾数）格式整数的加减法

第五章 计算机组成

计算机由三部分组成：中央处理单元（CPU）、主存储器、输入/输出子系统

中央处理单元

• 算术逻辑单元（ALU）
• 寄存器
  • 数据寄存器，保存运算中间结果
  • 指令寄存器，保存着从内存中读取的指令用于解释执行
  • 程序计数器，保存着当前指令的地址
• 控制单元，控制各子系统的操作

主存储器

它是许多带有唯一地址的存储单元的集合。内存中的数据位组单位称为字，通常字长可能是8，16，32，64等。

地址空间

• 所有在内存中标识的独立的内存单元的总数称为地址空间
• 地址本身也是位模式（无符号二进制整数）表示的，因此位模式的长度限制了寻址能力（比如32位的系统，能寻址的最大内存是4GB）

存储器的类型

• RAM(Random Access Memory)，可读可写，易失性
  • SRAM，使用触发门电路，速度快，昂贵
  • DRAM，使用电容器，速度慢，偏移
• ROM(Read Only Memory)，只读
• PROM
• EPROM
• EEPROM

存储器的层次结构

从寄存器到高速缓存储器，再到主存，速度变慢，价格变低；综合使用以折中速度和价格。

高速缓冲存储器

用它主存中部分主存的内容副本，利用80-20规律提高效率。

输入/输出子系统

非存储设备

用于通信，本身不存储信息，如键盘、显示器、打印机

存储设备

可以存储信息，比主存便宜，不易丢失。

• 磁介质存储设备，利用磁性的有无来表示1和0，如磁盘、磁带
• 光存储设备，利用激光技术来存储和读取数据，在塑料/树脂涂层上制造出凹坑和纹间表面，将它们的明显离散的光反射特性映射到0与1，如只读光盘（CD-ROM）、可刻录光盘（CD-R）、可重写光盘（CD-RW）、数字多功能光盘（DVD）

子系统的互连

CPU和存储器的连接

利用总线进行连接，总线中的每一根线每次只传输一位数据

• 数据总线：取决于计算机字的大小
• 地址总线：取决于存储器的容量
• 控制总线：负责在中央处理器和内存之间传递信息，取决于控制指令的总数

IO设备的连接

由于IO设备和CPU与主存在速度上有明显差异，需要借助输入/输出可控制器（接口）来连接到主线上，最常用的包括SCSI、火线、USB和HDMI。

IO设备的寻址

• IO独立寻址，与主存使用不同的操作指令，从而地址可以重复
• IO存储器映射寻址，使用同一套操作指令，从而减少指令集，但会占用部分地址

程序执行

机器周期

CPU利用重复的机器周期来执行程序中的指令，包括三个阶段：

• 取指令
• 译码
• 执行

输入/输出操作

CPU在某种程度上需要和输入输出设备同步，有三种设计：

• 程序控制输入/输出
• 中断控制输入/输出
• 直接存储器存取（DMA）

不同的体系结构

• CISC，复杂指令集计算机，使用大量的指令，包括复杂指令
• RISC，精简指令集计算机，少量的指令，复杂指令由简单指令子集模拟
• 流水线，使得不同指令的不同阶段可以被同时执行
• 并行处理，硬件上可以实现多个控制单元、多个算术逻辑单元、多个内存单元，按并行处理发生在指令流和数据流上可以分为四类：
  • SISD，单指令流、单数据流
  • SIMD，单指令流、多数据流
  • MISD，多指令流、单数据流
  • MIMD，多指令流、多数据流

第六章 计算机网络和因特网

概述

网络是一系列可用于通信的设备（如大型计算机、台式机、手机、安全系统等）相互连接（通过有线或无线的传输媒介）构成的。

局域网、广域网、互联网络

• 局域网和广域网通常不单独存在；当两个或多个网络互相连接时，它们构成了互联网络（网际网）
• 因特网就是一个互联网络
• 因特网的构成：几个骨干网、供应商网络、客户网络

协议分层

网络的沟通需要硬件和软件的配合，这通过协议分层来实现。其目的在于将复杂的通信任务利用模块化的思想，分配到不同的层中。其优点：

• 服务与其实施分开来，每层使用更底层的服务，并向高一层提供服务，并且不需要考虑该层的实施细节
• 因特网中并不全是端系统（主机），还有中间系统，它们只需要部分协议层，协议分层避免系统变得更复杂

协议分层的原则：

• 可逆性，每一个层都可以进行对立的且相反方向的工作（发和收）
• 两个站点的同一层的对象必须一致

基于上述原则，可以认为每个层之间具有逻辑连接（事实上的连接只有物理层）

TCP/IP协议族

这是因特网所使用的协议集，包括五层：应用层、传输层、网络层、数据链路层、物理层，各层的地址和数据包名称如下：

应用层

应用层只需要使用传输层的服务，而不需要向更高的协议层提供服务，这使得它非常灵活；常见的应用层协议如：http、ftp、smtp等。

应用层模式主要包括：

• 客户机-服务器模式，这种模式服务器成本高、需要持续维护，例如万维网和超文本传输协议(HTTP)、文件传输协议（FTP）、安全外壳协议（SSH）、邮件服务
• 端到端模式（P2P），灵活低成本，其问题在于安全性和适应性，例如网络电话、网络用户文件共享

标准化客户端-服务器程序

万维网

万维网（WWW，或Web）是分布在世界各地、相互间具有链接的的文档构成的信息存储库。

万维网是一个分布式的客户机-服务器服务。提供服务的服务器称为站点，每个站点有一到多个文档，这些文档称为网页，一个网页中可能有到本站点或其他站点的其他文档的链接。每个网页都是一个具有名称和地址的文件。

URL

客户端通过URL（Uniform Resource Locator，统一资源定位符）来找到网页所在的服务器和文件本身。一个URL包含四个部分：

• 协议，它是要使用的客户端-服务器程序类型（服务类型）的缩写，如http、ftp
• 主机，服务器的IP地址或特定名称
• 端口，服务器预定义的16为整数，用来指定服务器上的具体服务，比如http默认端口是80
• 路径，标识请求的网页文件的名字和位置

URL格式：protocol://host:port/path，由于常用服务都有默认端口号，通常可以省略端口号写作protocol://host/path。

浏览器

浏览器通常包括以下三部分：

• 客户端协议，用于存取文档，如http、ftp
• 控制器，接受键盘、鼠标等输入
• 解释器，用于将文档具体显示在屏幕上，解释器可以是HTML、javascript、java等

http协议

它定义了如何编写客户端-服务器程序以便从网络中检索网页；客户端发送请求，服务器响应请求，默认端口80。

ftp协议

• 客户端三部分：客户端控制进程、客户端数据传输进程、用户接口
• 服务器两部分：服务器控制进程、服务器数据传输进程
• 控制连接建立在控制进程间，用于命令传输，整个FTP交互会话中都打开
• 数据连接建立在数据传输进程间，用于数据传输，为每个文件分别打开和关闭

电子邮件

电子邮件（electronic mail或e-mail），允许客户交换信息。但是事实上，邮件的发送与回复是两个不相关的单向事务。客户A与B都可以在对方不开机的情况下向对方发送邮件，这就需要中间服务器，而客户A与B与这中间服务器间都是客户机/服务器模式。一个邮件发送与接收过程如下：

客户1 使用 UA1 准备信息，并使用 MTA客户端1 发送邮件到 MTA服务器1 通过队列传送给 MTA客户端1 发送邮件到 MTA服务器2存入邮箱 MAA服务器2 被 MAA客户端2 拉取邮件，并被 UA2 处理显示给 客户2

• UA, User Agent, 用户代理
• MTA, Mail Transfer Agent, 邮件传输代理
• MAA, Mail Access Agent, 邮件访问代理
• MTA客户端可以主动发送邮件，MTA服务器可以被动获取(接受)邮件
• MAA服务器可以被动发送邮件，MAA客户端可以主动获取邮件