读《计算机科学概论》（下）

读《计算机科学概论》（上）

image

目录

• 第一部分 基础篇
  • 第 1 章 全景图
• 第二部分 信息层
  • 第 2 章 二进制值和记数系统
  • 第 3 章 数据表示法
• 第三部分 硬件层
  • 第 4 章 门和电路
  • 第 5 章 计算部件
• 第四部分 程序设计层
  • 第 6 章 问题求解和算法设计
  • 第 7 章 低级程序设计语言
  • 第 8 章 高级程序设计语言
  • 第 9 章 抽象数据类型和算法
• 第五部分 操作系统层
  • 第 10 章 操作系统
  • 第 11 章 文件系统和目录
• 第六部分 应用程序层
  • 第 12 章 信息系统
  • 第 13 章 人工智能
  • 第 14 章 模拟、图形学和其他应用程序
• 第七部分 通信层
  • 第 15 章 网络
  • 第 16 章 万维网
• 第八部分 总结
  • 第 17 章 计算的限制

第五部分 操作系统层

第 10 章 操作系统

1. 操作系统的角色

• 操作系统：管理计算机资源并为系统交互提供界面的系统软件。
• 操作系统的角色
  • 计算机的操作系统把硬件和软件紧密地结合在一起,它是其他软件依附的基础,井且允许我们编写与机器进行交互的程序。就像交警要使通过十字路口的车流井井有条一样,操作系统要使通过计算机系统的程序流井然有序。
  • 现代软件一般分为两类
    • 应用软件：是为了满足特定需要一解决真实世界中的问题而编写的。文字处理程序、游戏、库存控制系统、汽车诊断程序和导弹控制程序都是应用软件。
    • 系统软件：负责在基础层上管理计算机系统的软件。它为创建和运行应用软件提供了工具和环境。系统软件通常直接与硬件交互，提供的功能比硬件自身提供的更多。计算机的操作系统是系统软件的核心。操作系统负责管理计算机的资源(如内存和输入/输出设备)，并提供人机交互的界面。其他系统软件则支持特定的目的，如在屏幕上绘制图像的图形软件的库。
  • 操作系统的各种角色通常都围绕着一个中心思想“良好的共享”。操作系统负责管理计算机的资源，而这些资源通常是由使用它们的程序共享的。多个并发执行的程序将共享主存，依次使用CPU，竞争使用输入/输出设备的机会。操作系统将担任现场监视器，确保每个程序都能够得到执行的机会。
• 内存、进程和 CPU 管理
  • 多道程序设计（multiprogramming）：是一种在主存中同时驻留多个程序的技术，这些程序为了能够执行，将竞争 CPU 资源，所有现代操作系统都采用置程序设计技术。
  • 内存管理：因为在主存中可能同时驻留多个程序，所以操作系统必须执行内存管理，以明确内存中有哪些程序，以及它们驻留在内存的什么位置。
  • 进程：可以将它定义为正在执行的程序。程序只是一套静态指令，进程则是动态的实体，表示正在执行的程序。
  • 进程管理：因为在多道程序设计系统中，可能同时其有多个活动进程。操作系统必须仔细管理这些进程。无论何时，下一条要执行的都是一条明确的指令，中间值将被计算出来。在执行过程中，进程可能会被打断，因此操作系统还要执行进程管理，以跟踪进程的进展以及所有中间状态。
  • CPU 调度：内存管理和进程管理都需要 CPU 调度，CPU 调度就是确定某个时刻 CPU 要执行内存中的哪个进程。
  • 记住，操作系统自身也是必须执行的程序。
• 批处理
  • 在早期的系统中，批处理是指操作员把来自多个用户的作业组织成分批，一个分批包含一组需要相同或相似资源的作业，操作员从而不必反复地载入和准备相同的资源。
  • 现代操作系统中的批处理概念，是允许用户把一系列 OS 命令定义为一个批文件，以控制一个大型程序或一组交互程序的处理。例如，Windows 中具有 .bat 后缀的文件就源自于批控制文件的想法，它们存放的是系统命令。类似于 Unix 中的Shell脚本。
  • 延伸阅读：批处理 - 维基百科
• 分时操作
  • 分时系统(timesharing): 如何更大程度地利用机器的能力和速度的问题引出了分时的概念。分时系统允许多个用户同时与计算机进行交互。多道程序设计法允许同时有多个活动进程，从而给了程序员直接与计算机系统交互，且仍然共享资源的能力。分时系统创建了每个用户都专有这台计算机的假象。操作系统负责在幕后管理资源 (包括CPU) 共享。
  • 分时的原理：每个用户由主机上运行的一一个登录进程表示。当用户运行程序时，将创建另一个进程(由用户的登录进程生成)。CPU 时间由所有用户创建的所有进程共享。每个进程将顺次得到一小段 CPU 时间。前提是CPU足够快，能够处理多个用户的请求并不使任何用户发现自己在等待。事实上，分时系统的用户有时会发现系统响应减慢了，这是由活动用户的数量和 CPU 的能力决定的。也就是说，当系统负荷过重时，每个用户的机器看来都变慢了。
• 其他
  • 网络
  • 设备驱动程序
  • 实时系统

image

2. 内存管理

• 主存：所有程序在执行时都存储在主存中。 这些程序引用的数据也都存储在主存中，以便程序能够访问它们。可以把主存看作一个大块的连续空间，这个空间被分成个被分成了 8 位、16 位或 32 位的小组。主存中的每个字节或字有一个对应的地址，这个地址只是一个整数，唯一标识了内存中的一个特定部分。（如下图所示）
• 程序是怎样被加载到内存中的？
• 操作系统如何管理程序内存
  • 跟踪一个程序驻留在内存中的什么位置以及如何驻留的
  • 把逻辑程序地址转换成实际的内存地址
    • 程序中到处都是对变量的引用和对程序其他部分的引用。在编译程序时，对标识符（如变量名）的引用将被转化为逻辑地址。当程序最终被载入内存时，每个逻辑地址将被转换成对应的物理地址。
      • 逻辑地址（又称虚拟地址或相对地址）：是对一个存储值的引用，是相对于引用它的程序的地址。
      • 物理地址：主存储设备中的真实地址。
      • 地址联编：指逻辑地址和物理地址间的映射。
• 几种不同的内存管理方式
  • 单块内存管理
    • 原理：首先把主存分成两部分，操作系统占用一部分，另一部分分配给应用程序。当加载应用程序时，我们把整个应用程序载入一大块连续的内存区域，除了操作系统外，一次只能处理一个程序。进行地址联编所要做的只是把操作系统的地址考虑在内。
    • 优缺点：实现和管理起来非常简单，但却大大浪费了内存空间和 CPU 时间。应用程序一般不可能需要操作系统剩余的所有空间，而且在程序等待某些资源的时候，还会浪费 CPU 时间。
  • 分区内存管理
    • 原理：为了能同时在内存中驻留多个应用程序，内存不再被分成两个部分，有两种划分内存的方法——固定分区法和动态分区法。无论是固定分区还是动态分区，任何时候内存都是
      被划分为一组分区，有些是空的，有些分配给了程序。
      • 固定分区法：主存被划分成特定数目的分区，这些分区的大小不一定相同，但在操作系统初始引导时它们的大小就固定了。
      • 动态分区法：根据程序的需要创建分区。初始时，主存将被看作一一个大的空白分区。当载入程序时，将从主存划分出一块刚好能容纳程序的空间，留下一块新的、小一些的空白分区，以便之后供其他程序使用。操作系统将维护一个分区信息表，不过在动态分区中，地址信息会随着程序的载入和清除而改变。
    • 优缺点：可以同时把多个程序载入内存，从而更高效地利用主存。但是一个分区的大小必须要能够容纳整个程序，所以如果程序太大而主存可用空间较小，那就无法加载大程序了。
  • 页式内存管理
    • 原理：主存被分成小的大小固定的存储块，叫做帧。进程将被划分为页，为了便于讨论，我们假设页的大小等于帧的大小。在程序执行时，进程的页将被载入分散在内存中的各个未使用的帧中，因此，一个进程的页可能是四处散落的、无序的，与其他进程的页混合在一起。 为了掌握进程页的分布，操作系统需要为内存中的每个进程维护一个独立的页映射表(PMT)， 把每个页映射到载入它的帧（如下图所示）。注意，页和帧都从0开始编号的，这样可以简化地址的计算。
      • 请求分页：页式内存管理法的扩展，只有当页面被引用（请求）时才会被载入内存。任何时刻 CPU 都只访问进程中的一个页面，此时，进程中的其他页面是否在内存中无关紧要。
      • 页面交换：在请求分页法中，页面经过要求才会被载入内存。也就是说，当引用一个页面时，首先要看它是否已经在内存中了，如果该页面在内存中，就可以直接访问，否则，要从二级存储设备把这个页面载入可用的帧，然后再完成访问。从二级存储设备载入页面通常会引发把其他页面写回二级存储设备，这种行为叫做页面交换。
      • 虚拟内存：由于整个程序不必同时处于内存而造成的程序大小没有限制的假象。
    • 优缺点：
      • 优点：相比前面的所有内存管理法中，整个进程都必须作为整体载入内存。因此，进程大小始终有一个上限，而页式内存管理中的请求分页法消除了这一限制。
      • 缺点：不过，虚拟内存在程序执行时需要很多开销。以前，一旦程序载入了内存，就完全处于内存中，准备好执行了。采用虚拟内存法，则经常需要在主存和二级存储设备间进行页面交换。当一个进程等待页面交换时，另一个进程接管 CPU 的控制，那么这种开销是可以接受的。但页面交换过多就会造成系统颠簸，会严重降低系统的性能。
        • 系统颠簸(thrashing): 频繁的页面交换造成的低效处理。

主存中的内存地址：

image

单块内存管理：

image

分区内存管理：

image

页式内存管理：

image

3. 进程管理

• 进程的几种状态
  • 创建
  • 准备就绪
  • 运行
  • 等待
  • 终止
• 进程控制块（PCB）
  • 操作系统必须为每个活动进程管理大量的数据,这些通常存储在称为进程控制块的数据结构中。
  • 通常，每个状态由一个PCB列表表示,处于该状态的每个进程对应一个PCB。当进程从一个状态转移到另一个状态时,它对应的PCB也会从一个状态的列表中转移到另一个状态的列表。新的PCB是在最初创建进程(新状态)的时候创建的,将一直保持到进程终止。
  • PCB存储了有关进程的各种信息,包括程序计数器的当前值(说明了进程中下一条要执行的指令)。PCB还存储了进程在其他所有CPU寄存器中的值。
  • 上下文切换：每当一个进程进入了运行状态,当前正在运行的进程的寄存器值将被存入它的PCB,新运行的进程的寄存器值将被载入CPU。这种信息交换叫做上下文切换。

image

4. CPU 调度

• CPU 调度：所谓CPU调度，就是确定把哪个处于准备就绪状态的进程移入运行状态。也就是说CPU调度算法将决定把 CPU 给予哪个进程，以便它能够运行。
  • 抢先调度：当当前执行的进程自愿放弃了CPU时发生的CPU调度
  • 非抢先调度：当操作系统决定照顾另一个进程,抢占当前执行进程的CPU资源时发生的CPU调度
• 调度方法
  • 先到先服务（非抢先的）：给予最早到达的作业优先权。
  • 最短作业优先（非抢先的）：给予运行时间最短的作业优先权。
  • 循环调度法（一种抢先调度）：让每个活动进程轮流使用 CPU，每个进程得到一个小时间片。

第 11 章 文件系统和目录

1. 文件系统

• 最常见的二级存储设备是磁盘驱动器。
• 基本概念
  • 文件：磁盘上的数据都在储在文件中,这是在电子媒介上组织数据的一种机制。所谓文件,就是相关数据的有名集合。从用户的角度来看,文件是可以写入二级存储设备的最小信息量。用文件组织所有信息,呈现出一个统一的信息存储视图。
  • 文件系统：文件系统是操作系统提供的一个逻辑视图，使用户能够按照文件集合的方式管理数据。文件系统通常用目录组织文件。
  • 目录：文件的有名分组。
• 文件中存的是什么？
  • 文件 = 数据 + 数据的组织方式
• 根据文件数据的组织方式，所有文件都可以被归为两类：文本文件和二进制文件
  • 文本文件：其中的数据字节是 ASCII 或 Unicode 字符集中的字符。比如 .py 文本文件。
  • 二进制文件：包含特定格式的数据的文件，要求给位串一个特定的解释。比如 png 格式的图片文件。
• 文件类型
  • 文件类型：文件中包含的信息的种类叫做文件类型。
  • 文件扩展名：文件名通常由两部分组成，即主文件名和文件扩展名。文件扩展名说明了文件的类型。
  • 注意：文件扩展名只说明了文件中存放的是什么，改变扩展名不会改变文件中的数据或它的内部格式。
• 文件操作
  • 创建和删除文件
    • 准备工作：操作系统用两种方式跟踪二级存储设备。它维护了一个表以说明哪些内存块是空的(也就是说可用的)，还为每个目录维护了一个表，以记录该目录下的文件的信息。
    • 创建文件：要创建一个文件，操作系统需要先在文件系统中为文件内容找一块可用空间，然后把该文件的条目加人正确的目录表中，记录文件的名字和位置。
    • 删除文件：要删除一个文件，操作系统要声明该文件使用的空间现在是空的了，并要删除目录表中的相应条目。
  • 读写文件
    • 打开和关闭文件：大多数操作系统要求，在对文件执行读写操作前要先打开该文件。操作系统维护了一个记录当前打开的文件的小表，以避免每次执行项操作都在大的文件系统中检索文件。当文件不再使用时，要关闭它，操作系统会删除打开的文件表中的相应条目。无论何时，一个打开的文件都有一个当前文件指针(一个地址)，说明下一次读写操作要发生在什么位置。”有些系统还为文件分别设置了读指针和写指针。
    • 读文件：所谓读文件，是操作系统提交文件中从当前文件指针开始的信息的副本。发生读操作后，文件指针将被更新。
    • 写文件：写信息是把指定的信息记录到由当前文件指针所指的文件空间中，然后更新文件指针。
    • 通常，操作系统允许用户打开文件以便进行写操作或读操作，但不允许同时进行这两项操作。
  • 重定位文件中的当前文件指针：打开的文件的当前指针可以被重定位到文件中的其他位置，以备下一次读或写操作。
  • 把数据附加到文件结尾：在文件结尾附加信息要求把文件指针重定位到文件的结尾，然后再写入相应的数据。
  • 删减文件：有时，删除文件中的信息是很有用的。所谓删减文件，是删除文件的内容，但不删除文件表中的管理条目。提供这项操作是为了避免删除一个文件，然后又重新创建它。有时，删减操作非常复杂，可以删除从当前文件指针到文件结尾的文件内容。
  • 重命名文件：更改文件名的操作
  • 复制文件：创建一个文件内容的完整副本并给该副本一个新名字
• 文件访问
  • 顺序访问法：以线性方式访问文件中的数据的方法。
  • 直接访问法：通过指定记录编号直接访问文件中的数据的方法。
  • 说明：任何类型的介质都可以存储这两种类型的文件。文件访问方法定义了重定位当前文件指针的方法。它们与存储文件的设备的物理限制无关。
• 文件保护
  • 文件保护机制决定了谁可以使用文件，以及为什么目的而使用文件。
  • 比如，Unix 系统下，文件保护设置有三类，即 Owner、Group 和 World，在每种类别下，你可以决定一个文件是可读的、可写的还是可执行的。
  • 控制文件的访问，以防止蓄意获取不正当访问的企图，以及最小化那些由于用户不经意引起的问题。

image

2. 目录

• 什么是目录
  • 目录的本质是文件：大多数操作系统都用文件表示目录。目录文件存放的是关于目录中的其他文件的数据。
• 创建和操作目录
  • 建立文件目录
  • 列出目录下的所有文件
  • 在目录中创建、删除和重命名文件
  • 在目录中查找文件
• 目录树
  • 目录树：展示文件系统的嵌套目录组织的结构。
  • 根目录：包含其他所有目录的最高层目录。
  • 工作目录：当前活动的子目录。
• 路径名
  • 路径：要用文本指定一个特定的文件,必须说明该文件的路径,即找到这个文件必须历经的系列目录。路径可以是绝对的,也可以是相对的。
  • 绝对路径：从根目录开始,包括所有后继子目录的路径。
  • 相对路径：从当前工作目录开始的路径。

3. 磁盘调度

• 背景：CPU和主存的速度都比二级存储设备的数据传输速度快很多。这就是为什么一个进程要执行磁盘IO操作,在等待信息传输的同时把使用CPU的机会让给另一个进程
  的原因。由于二级IO是一般计算机系统中最慢的部分,所以访问磁盘驱动器上的信息的方法对于文件系统至关重要。
• 磁盘调度：在计算机同时处理多个进程时,将建立一个访问磁盘的请求列表。操作系统用于决定先满足哪个请求的方法叫做磁盘调度。
• 磁盘驱动器读取数据的原理
  • 磁盘驱动器被组织得像一叠盘片,每个盘片被分为几个磁道,每个磁道又被分为几个扇区。所有盘片上对应的磁道构成了柱面。（如下图所示）
  • 对我们的讨论来说,最重要的一点是在任意时刻都有一组读写头在所有盘片的特定柱面上盘旋。记住,寻道时间是读写头到达指定柱面所花费的时间。等待时间是盘片旋转到正确的位置以便能读写信息所花费的时间。在这两个时间中,寻道时间的要求更高,因此它是磁盘调度算法处理的重点。
• 几种磁盘调度算法
  • 先到先服务磁盘调度法
  • 最短寻道时间优先磁盘调度法
  • SCAN 磁盘调度法

image

第六部分 应用程序层

第 12 章 信息系统

1. 信息管理

• 数据和信息的关系
• 信息系统：帮助用户组织和管理数据的应用软件。
  • 电子制表软件
  • 数据库管理系统

2. 电子制表软件

• 电子制表软件是用单元格来组织数据和计算新值的公式的应用软件。比如微软的 Excel。

3. 数据库管理系统

• 数据库：结构化的数据集合。
• 数据库管理系统：由物理数据库、数据库引擎和数据库模式构成的软件和数据的组合。
• 数据库管理系统一般由下列几部分构成
  • 物理数据库：存放数据的文件的集合。
  • 数据库引擎：支持对数据库内容的访问和修改的软件。
  • 数据库模式：存储在数据库中的数据的逻辑结构的规约。
• 关系模型
  • 关系模型是目前最常见的一种数据库模型
  • 在关系DBMS中,用表组织数据项和它们之间的关系。表是记录的集合。记录是字段的集合。每个表会被指派一个(或一组)键,键的值唯一标识了表中的每个记录。
  • 一些概念
    • 表（table）：数据库记录的集合。
    • 记录（record）：构成一个数据库实体的相关的字段的集合。
    • 字段（field）：数据库记录中的一个值。
    • 键（key）：在表的所有记录中唯一标识一个数据库记录的一个或多个域。
• 关系
  • 数据库元素之间的关系可以用新的表表示,这个表也可以有自己的属性。关系表并不是重复其他表的数据,而是存储数据库记录的关键值,以便需要的时候能够查找详细的数据。
• 结构化查询语言（SQL）
  • 结构化查询语言(SQL)是一种用于管理关系数据库的综合性数据库语言。它包括指定数据库模式的语句和添加、修改及删除数据库内容的语句。顾名思义,它还具有查询数据库以获取特定数据的功能。
• 数据库设计
  • 实体建模法
  • ER 图
  • 基数约束
    • 一对一
    • 一对多
    • 多对一

4. 信息安全

• 信息安全的三个方面
  • 机密性
  • 完整性
  • 可用性
• 密码学
  • 加密(encryption)：把明文转换成密文的过程。
  • 解密(decryption):把密文转换成明文的过程。
  • 密码（cipher）：用于加密和解密文本的算法。
  • 对称加密:密码学的一种方法,同一个密钥可以同时用作信息的加密和解密
  • 非对称加密:密码学的一种方法,每个用户具有两个相关的密钥,一个是公开的,另一个是私有的。
  • 密钥(key):指导密码的一组参数。
    • 公钥
    • 私钥
  • 数字签名:附加在消息上的数据,由消息自身和发送者的私有密钥生成,以确保消息的真实性。
  • 数字认证:发送者经过鉴定的公共密钥的一种形式,用于最少化恶意伪造事件。

第 13 章 人工智能

1. 思维机

• 什么是人工智能
  • 人工智能就是研究对人类思想建模和应用人类智能的计算机系统的学科。
• 图灵测试
  • 确定一台机器是否能像人一样思考的衡量方法，采用的方式是模拟人类对话。
• AI 领域的分支
  • 知识表示：用于表示知识,以便计算机能够用来解决智能问题的技术。
  • 专家系统：嵌入人类专家知识的计算机系统。
  • 神经网络：模拟人脑处理的计算机系统。
  • 自然语言处理：处理人类用来交流的语言的难题。
  • 机器人学：关于机器人的研究。

2. 知识表示

• 什么是知识表示
  • 表示一个对象或事件所需的知识会根据情况而有所不同，对于要解决的问题，我们需要特定的信息。而且我们需要的不仅仅是特定的信息，还需要一种形式，使我们能有效地检索和处理信息。
• 语义网
  • 语义网是知识的图形化表示法,它捕捉了对象在真实世界中的关系。根据网络图的分析可以回答问题。我们一般用有向图来表示语义网。
• 检索树
  • 检索树是表示游戏中所有可能移动（包括你和你的对手的移动）的结构。
  • 两种检索方法
    • 深度优先方法
    • 广度优先方法

语义网：

image

检索树：

image

3. 专家系统

• 什么是专家系统
  • 专家系统嵌入了人类专家的知识。它采用一套规则来定义条件,在这种条件下,可以得出某些结论。专家系统适用于多种类型的决策过程,如医疗诊断等。
• 知识库
  • 专家系统的规则集合
• 推理机
  • 处理规则以得出结论的软件

4. 神经网络

• 生物神经网络
• 人工神经网络
  • 人工神经网络模拟了人脑神经网络的处理。人工神经元将根据多个输入信号生成一个输出信号,输人信号的重要性由它们的权来决定。这点模拟了人类的神经元,即由神经键调节从一个神经元到下一个神经元的信号强度
  • 有效权：人工神经元中输入值和相应的权的乘积之和
  • 训练：调整神经网络中的权和阈值的过程叫做训练。训练神经网络，可以使它生成任何需要的结果。对神经网络训练的越多，它生成精确结果的机会就越大。
  • 人工神经网络的实际应用：找出一副图片中的猫；光学字符识别（OCR）

5. 自然语言处理

• 自然语言处理要解决的问题
  • 实现人与计算机之间进行交谈
• 人机语音交互过程中的三种基本处理类型
  • 语音识别：用计算机来识别人类所讲的话
    • 难点
      • 每个人的发音不同
      • 人是以连贯流畅的方式讲话的，所以会出现“连读”的情况
      • 有些词语发音相同
  • 自然语音理解：用计算机对人类传达的信息作出合理的解释
    • 难点：二义性
  • 语音合成：用计算机制造出人类的语音
    • 两种解决办法
      • 动态语音生成
      • 录制语音

6. 机器人学

• 机器人学是研究机器人科学,可以把机器人分为两大类
  • 固定机器人：你在装配线上看到的就是固定机器人,这些机器被固定在装配线上,产品从它们下面经过。由于固定机器人的世界非常有限,所以它的任务就内置在硬件上。因此,固定机器人几乎都应用于工业工程的领域。
  • 可移动机器人：可移动机器人可以到处移动,而且必须与周围的环境进行交互。为可移动机器人的世界建模需要使用人工智能的技术。
• 感知-规划-执行范型
• 包孕体系结构
• 物理部件

第 14 章 模拟、图形学和其他应用程序

1. 什么是模拟

• 什么是模拟

  • 设计复杂系统的模型并为观察结果而对该模型进行实验

• 复杂系统

• 模型

  • 模型是真实系统的抽象，系统中的对象和管理对象相互作用的规则的表示法

• 构造模型

  • 连续模拟
    • 连续模拟把时间看做连续的，用一组反映特征集合中的关系的微分方程表示时间的变化。
    • 例子：气象模型
  • 离散事件模拟
    • 离散事件模拟中，行为被表示为实体、属性和事件，其中实体即对象，属性即实体的特征，事件即实体之间的相互作用
    • 例子：排队系统

• 其他模型

• 必要的计算能力

2. 计算机图形学

• 什么是计算机图形学
  • 算机图形学是结合了计算机、科学和绘画艺术的领域,令人着迷。它依赖数学方程来模拟图像中要呈现的自然现象。
  • 我们可以把计算机图形学描述为计算机屏幕上的像素值的设置。计算机图形学决定了如何设置像素的颜色来显示图标以及在屏幕上拖曳图标时如何改变像素值。
  • 计算机图形学把光的交互、对象的属性(如透明度和表面材质)、对象的形状和物理属性组合在一起,生成了接近真实照片的图像。
    • 光的工作原理
    • 物体形状
    • 光模拟
    • 复杂对象的建模
    • 让物体动起来
• 计算机图形的应用
  • 现代操作系统中的图形用户界面（GUI）
  • 文字处理软件和桌面出版软件
  • 计算机辅助设计系统（CAD）、三维模型设计软件（Pro/E、CATIA 等）
  • 图像处理软件，比如 Photoshop
  • 科学可视化系统
  • 游戏、动画片和影视特效

3. 嵌入式系统

• 什么是嵌入式系统
  • 嵌入式系统是大型系统中专用于执行有限功能的计算机。嵌入式系统通常嵌在单个微处理器芯片上。程序存储在 ROM
• 为嵌入式系统编写程序
  • 由于一般人只是在厨房、客厅或汽车中遇到嵌入式系统,所以我们视嵌入式系统等同于
    硬件。但是,为嵌入式系统编写程序是必不可少的,而且要把程序烧录到系统附带的ROM
    (只读内存)中,以便它能实现自己的使命。由于不能在嵌入式处理器上开发和测试程序,那
    么如何实现它们呢?程序是先在PC上编写,然后为目标系统进行编译,生成嵌入式系统的处
    理器能够执行的代码。
• 嵌入式系统程序的语言
  • 在早期的嵌入式系统中,代码的长度和执行速度都非常重要。由于汇编语言能够最有效
    地简化代码,加速它们的执行,所以汇编语言一直是嵌入式系统的专用语言。甚至当C语言盛
    行,出现了跨平台的C编译器后,许多程序员仍然继续使用汇编语言。C程序比汇编程序大约
    长和慢25%,但是比较容易编写。即使是今天,ROM的大小仍然要求代码越短越好,所以汇
    编语言程序仍在使用中。

4. 电子商务

• 电子商务：通过互联网进行商品交易的过程。
• 例子：ebay、alibaba、淘宝、京东

5. 计算机安全

• 将未许可的用户拒绝在计算机系统之外是维护系统安全的基本原则——访问控制
  • 访问控制采用的三种鉴别凭证
    • 基于用户知道的信息，比如用户名和密码
    • 基于用户所拥有的物品，比如具有芯片的卡片
    • 以生物特征为基础，比如指纹识别、视网膜识别
• 恶意代码
  • 病毒：能够自我复制的恶意程序，通常嵌入在其他代码中
  • 木马：伪装成恶意资源的恶意程序
  • 逻辑炸弹：一种恶意程序，被设置为在某些特定系统事件发生时执行
• 安全攻击
  • 口令猜测( password guessing):通过系统地尝试来判断用户口令,从而获取对计算机系统的
    访问的企图。
  • 网络钓鱼(phishing):利用网页伪装成官方系统的一部分,从而诱使用户暴露安全信息。
  • 欺骗(spoofing):恶意用户伪装在许可用户对计算机系统进行的攻击。
  • 后门(back door):程序的一个要点,知道它的人都可以利用它对计算机系统进行特殊的或未经许可的访问。
  • 缓存溢出(buffer overflow):计算机程序的一个缺陷,会导致系统崩溃,并让用户具有过高的访问权限。
  • 拒绝服务攻击/DoS 攻击(denial of service):对网络资源的一种攻击,可以使许可的用户不能访问系统。
    • 通常 DoS攻击 是通过网络进行的,即让大量通信包涌入站点或其他网络资源,使它保持忙碌状态,从而不能处理其他许可的用户的请求。由于规避请求数量,它甚至会造成系统自身崩溃。
  • 中间人(man-in-the-middle):一种安全攻击,即通过获取公匙数据截取网络通信消息。

第七部分 通信层

第 15 章 网络

1. 连网

• 什么是计算机网络
  • 计算机网络是为了通信和共享资源而连接在一起的一组计算设备。
• 基本概念
  • 无线连接(wireless)):没有物理电线的网络连接。
  • 节点(或主机)(node(or host):网络中任何可寻址的设备。
  • 数据传输率(也叫带宽)(data transfer rate( also bandwidth)):数据从网络中的一个地点传输到另一个地点的速率。
  • 协议(protocol):定义如何在网络上格式化和处理数据的一组规则。
  • 客户/服务器模型(client/server model):客户发出对服务器的请求,服务器做出响应的分布式方法。
  • 文件服务器(file server):专用于为网络用户存储和管理文件的计算机。
  • Web 服务器(Web server):专用于响应客户端请求的计算机。
• 网络的类型
  • 局域网(loal-area network,LAN):连接较小地理范围内的少量计算机的网络。
    • 拓扑
      • 环形拓扑(ring topology):所有节点连接成了封闭环的LAN配置。
      • 星形拓扑(star topology):由中心节点控制所有消息传输的LAN配置。
      • 总线拓扑(bus topology):所有节点共享一根通信线的LAN配置。
    • 以太网(Ethernet):基于总线拓扑的局域网业界标准。
  • 广域网(wide- area network,WAN):连接两个或多个局域网的网络。
  • 网关(gateway):处理它的LAN和其他网络之间通信的节点。
• Internet 连接
  • Internet 骨干网(Internet backbone):承载 Internet 通信的一组高速网络。
  • Internet 服务提供者(Internet service provider,IsP):提供 Internet访问的公司。
  • 将个人计算机连接到 Internet 上的几种方式
    • 电话调制解调器(phone modem):把计算机信号转换成模拟音频信号,然后再把模拟音频信号转换回计算机信号的设备。
    • 数字用户线路(digital subscriber line,DSL):用常规电话线传输数字信号的 Internet 连接方式。
    • 线缆调制解调器(cable modem):使用家庭的有线电视网络进行计算机网络通信的设备。
  • 宽带（broadband）：宽带是指提供的数据传输率大于 128Kbps 的连网技术。DSL 连线和线缆调制解调器都属于宽带。
• 包交换
  • 包(packet):在网络上传输的数据单位。
  • 包交换(packet switching):为了提高在共享线路上传输信息的有效性,消息被分割为大小固定、有编号的包。每个包将独立在网上传输,直到到达目的地,它们将在此被重新组合为原始的消息。这种方法做包交换。
  • 路由器(router):指导包在网络上向最终目的地传输的网络设备。
  • 中继器(repeater):在较长的通信线路上加强和传播信号的网络设备。

image image image

[图片上传失败...(image-d2b529-1542123115644)]

2. 开放式系统和协议

• OSI 参考模型
  • 为了便于建立通信标准而对网络交互进行的 7 层逻辑划分。每一层处理网络通信的一个特定方面。
• 网络协议
  • 网络协议参照 OSI 参考模型的基本概念也进行了分层。
• TCP/IP
  • TCP/IP
  • TCP
  • UDP
  • IP
  • ping
  • 跟踪路由程序
• 高层协议
  • SMTP
  • FTP
  • telnet
  • HTTP
• MIME 类型
  • 定义电子邮件附件或网站文件的格式的标准。
• 防火墙
  • 一台网关机器，它的软件通过过滤网通信来保护网络。

image

3. 网络地址

• 主机名：由点号分隔的单词组构成的名字,唯一标识了 Internet上的机器;每个主机名对应一个IP地址。
• IP 地址：由点号分隔的四个数值构成的地址,唯一表示了 Internet 上的机器。
• 域名系统
  • 域名：主机名由计算机名加域名构成。域名由两个或多个部分组成，它们说明了计算机所属的组织或组织的一个子集。
  • 域名系统（DNS）：主要用于把域名翻译成数字 IP 地址的分布式系统。
  • 域名服务器：把主机名翻译成数字 IP 地址的计算机。

第 16 章 万维网

1. Web 简介

• 什么是 Web
  • 万维网(或Web)(World Wide Web(or Web)，不同于 Internet，万维网指的是信息和用于访问信息的网络软件的基础设施。
  • 一些概念
    • Web页( Web page):包含或引用各种类型的数据的文档。
    • 链接(link):两个Web页之间的连接。
    • Web网站(website):一组相关的网页,通常由同一个人或公司设计和控制。
    • Web浏览器(Web browser)：获取并显示 web 页的软件工具。
    • Web服务骼(Web server)：用于响应 web 页请求的计算机。
    • 统一资源定位符(Uniform Resource locator,URL):说明 web 地址的标准方式
• 搜索引擎
  • 搜索引擎是通过检索具有上百万个网站的信息的数据库来生成候选站点列表的。
  • 两种搜索引擎技术
    • 关键字搜索
    • 基于概念的搜索
• 即时消息
• 博客
• cookie
  • cookie是web站点存储在你的硬盘上的小文本文件,以便你返回该站点时,该站点能够得到有关你以及你上次访问的信息。它们通常用于跟踪用户的活动,对用户和使用它们的站点
    都很有帮助。 cookie 不是程序,因此不能在你的计算机上执行代码。

2. HTML

• HTML 是一种标记语言，用于创建 web 页的语言。浏览器通过解析 HTML 文本内容来展示网页。

3. 交互式网页（动态网页）

• 两种基于 Web 的交互的技术
  • Java 小程序
  • Java 服务器页（JSP）

4. JavaScript

5. XML 和 JSON

第八部分 总结

第 17 章 计算的限制

1. 硬件

• 硬件带给计算的限制来自于几个因素
  • 算术运算的限制：数字是无限的,而计算机的数字表示却是有限的。
    • 整数的大数问题
    • 实数的精读问题
  • 部件的限制：硬件就是硬件,也就是说,它是由易坏的机械部件和电子部件构成的。
  • 通信的限制：在把数据从一个内部设备传递给另一个内部设备,或者从一台计算机传递到另一台计算机时
    • 如何保证数据在传输过程中不被破坏？
      • 检错码：判断在数据传输过程中是否发生了错误
        • 校验位
        • 校验数位
      • 误差校正码：不仅能检测出数据传输过程中发生的错误，而且还能判断出正确的值
      • 相关应用案例：微信团队开源的 MMKV 库中就使用了 crc 校验来对无效数据进行鉴别。
        会发生问题。

2. 软件

• 软件的复杂度
• 当前提高软件质量的方法

3. 问题

• 算法比较/算法分析
  • 如何比较两个算法的工作量
    • 第一种，对算法编码，然后比较两个程序的执行时间
    • 第二种，计算执行的指令数或语句数
    • 第三种，把算法中的一个特定基本操作分离出来，计算这个操作执行的次数
  • 复杂度分析
  • 大 O 分析
  • 常见的数量级
• 图灵机
• 停机问题
• 算法分类
  • P 类问题：能用单处理器在多项式时间内解决的问题
  • NP 类问题：能用足够多的处理器在多项式时间内解决的问题
  • NP 完全问题：NP类问题的子集,如果发现了其中任何一个问题的单处理器多项式时间的解决方案,那么其他所有问题都存在这样的解决方案。

延伸阅读

• 《计算机是怎样跑起来的》
• 《程序是怎样跑起来的》
• 《编码：隐匿在计算机软硬件背后的语言》
• 《深入理解计算机系统》

---

如果你也喜欢交流技术、喜欢阅读、积极践行，欢迎关注我的公众号：祥龙Shannon写字的地方，一起成长。

qrcode_for_gh_cc686217be41_344.jpg