计算机科学导论

1. 绪论
   1. 图灵模型：关于计算的抽象概念模型
      1. 可编程的数据处理器，通过添加“程序”这个元素，实现图灵模型；
      2. “程序”是一系列告诉计算机如何对数据进行处理的集合；（凡是图灵完备的语言，理论上都是强大够用的，但好不好用，简不简单，就不一定了，这取决于每个语言的抽象程度）
   2. 冯诺依曼模型：关于计算的物理实现模型
      1. 由4个子系统构成，包括：存储器，算术逻辑单元，控制单元，输入/输出单元；
      2. 在这个模型中，程序是由数量有限的指令组成；控制单元从内存读取一条指令，解释指令，然后执行指令；
   3. 计算机组成
      1. 计算机硬件
      2. 计算机软件
         1. 程序必须是存储的
         2. 程序必须是有序的指令集（目的：通过使用指令集，提高复用性，让编程变得简单）
         3. 算法：对不同的问题，寻找合适的指令来解决；
         4. 语言：利用语言符号来代表位模式（什么是位模式？位流，由一系列的位组成，例如8位，16位，32位）（我们当然可以通过操作位来实现计算，但这样的编程效率太低了，由于很多位操作是通用的，通过引入语言符号在进行抽象封装，使得我们可以在更高的层次进行思考并实现我们的计算目的）
         5. 软件工程：将程序的设计和编写进行结构化，即遵循一定的原理和规则（目的：控制复杂度）
         6. 操作系统：为程序访问计算机硬件提供方便，因为很多指令是通用的；
      3. 数据：存储数据，组织数据；数据目前只能以位模式进行存储；但数据的组织的方式却可以有很多种，这是一个大课题；
2. 数字系统
   1. 位置化数字系统：同一个符号，其所在的不同位置，决定了其表示的不同值；包括2进制，8进制，10进制，16进制等；
   2. 非位置化数字系统：例如罗马数字系统；不管符号出现在哪个位置，它都表示相同的值；
3. 数据存储
   1. 数据类型
      1. 数字，文本，声音，图像，视频；
      2. 位：用 0 或 1 表示；
      3. 位模式：也叫位流，由一系列的位组成，例如8位，16位，32位等；长度为8的位模式，称为1字节；
      4. 数据压缩：为了减少内存空间的占用，数据在存储到计算机之前一般会经过压缩；（有哪些压缩的方法？采样法，短替长法）
      5. 错误检测和纠正：在传输和存储过程中，有时会出现错误，这个时候，可以通过检测技术来纠正；
   2. 存储数字
      1. 整数：一般使用定点表示法；
         1. 无符号表示法：常用于计数，寻址，其他数据类型的存储等场景；
         2. 符号加绝对值表示法：最左边定义符号，0表示正整数，1表示负整数；
         3. 二进制补码表示法（用来表示负数）：
      2. 实数：
         1. 浮点表示法：由于符号，位移量，定点数三部分构成；
         2. 规范化：在小数点的左边使用唯一的非零数码；
         3. 符号、指数和尾数：
            1. 符号：用 0 和 1 来表示正负；
            2. 指数：小数点移动的位数（2 的幂）
            3. 尾数：小数点右边的2进制数；
         4. 余码系统：它是一种表示法，在这种系统中，正负整数都可以作为无符号数来存储，它的实现方式，是通过将一个正整数（称为偏移量）加到每一个数字中，将它们统一移动到非负的一边；这个偏移量的值是 2^(m-1) - 1（正数貌似不用处理，负数则通过加上这个偏移量之后的数来表示）（注：此处的 m 是内存单元存储指数的大小）
   3. 存储文本
      1. 通过一套代码来表示符号，常用的代码系统有
         1. ASCII（美国信息交换标准码），缺点是只能搞定英文，其他语言例如中文的符号搞不定，因为它只有8位，只可以定义 128 个符号；
         2. Unicode：使用32位，因此可以表示42亿个符号，所以可以搞定全世界；至于能不能全宇宙，这个就不知道了，估计应该是不行的吧；
         3. 其他编码：还有很多，比如 UTF-8，UTF-16，GB2312，GBK 等等；
   4. 存储音频
      1. 声音在时间维度上是一种连续的数据，理论上它是无限的，但我们的存储是有限的，所以只能通过采样来解决；（由于是采样，应该会涉及采样的密度，即相同时间单位内，采集的样本数量）
      2. 流程：
         1. 采样：在模拟信号中，选择数量有限的点，并把它们记录下来；
         2. 量化：将样本的值，截取为最接近的整数的值；
         3. 编码：将样本值，转化成位模式；
   5. 存储图像
      1. 光栅图（也叫位图）
         1. 将整张图像分解成很小的像素，每个像素有单独的密度值
         2. 解析度：每单位面积大小，例如每英寸，使用多少个像素来表示，这个扫描率称为解析度，如果解析度足够高，人眼就看不出来图像的不连续性；（理论上图像也是一种连续的数据，因此其实现也同声音一样是通过采样）
         3. 色彩深度：用于表现每个像素的位的数量，一般是24位，由红、黄、蓝组成，每个原色用8位来表示；（对颜色的感觉，其本质是我们的眼睛如何对光线进行响应；我们的眼睛有不同的感光细胞，一些响应三原色，一些响应光的密度，然后产生不同强度的神经信号，之后大脑对信号进行翻译）
            1. 真彩色：使用24位来编码一个像素，理论上可以表示1600万种左右的颜色
            2. 索引色：将真彩色缩编成256个颜色来代表；
      2. 矢量图
         1. 不存储像素的位模式，而是将图像分解为线条，形状，颜色等要素，然后由定义如何绘制这些形状和颜色-的一系列命令组成；
   6. 存储视频：视频可以看做是图像在时间轴上的叠加处理；
4. 数据运算
   1. 三大类：逻辑运算，算术运算，移位运算；
   2. 4种逻辑运算：与，或，非，异或；即AND, OR, NOT, XOR
      1. NOT 的应用：对整个模式求反；
      2. AND 的应用：对整个模式归零；
      3. OR 的应用：对整个模式置壹；
      4. XOR 的应用：对指定位进行反转（求反）；
   3. 算术运算：加减乘除
      1. 二进制补码格式的好处：加法和减法没有不同；如果使用符号加绝对值的格式，加法和减法的表示就会变得比较复杂，涉及8种不同的情况；
      2. 浮点数运算：将小数点对齐，对小数和整数部分使用符号加绝对值的方式进行计算；
5. 计算机组成
   1. 三大类
      1. 中央处理单元
         1. 算术逻辑单元：逻辑运算，移运运算，算术运算；
         2. 寄存器
            1. 数据寄存器
            2. 指令寄存器
            3. 程序计数器
         3. 控制单元
      2. 主存储器：磁盘不是一种存储器，而是一个存储设备，属于输入输出系统；
         1. 它是存储单元的集合，每个存储单元都有一个自己的地址标识；所有标识了地址的单元的总数，称为地址空间；
         2. 类型：
            1. RAM：随机存取存储器；分为静态 SRAM 和动态 DRAM 两种，前者快但贵，后者慢但便宜；动态与静态的差别在于，动态使用电容存储的电荷数量来表示0或1，但由于电容中的电荷会衰减，所以需要定时动态充电，静态则不用；
            2. ROM：只读存取器；
         3. 层次结构：根据 80/20 法则，存储器内部通过三个层次结构（寄存器 + 高速缓存 + 主存），来取得速度和成本之间的平衡；
      3. 输入/输出子系统
         1. 非存储设备：例如屏幕，鼠标，键盘，打印机等，用于通信
         2. 存储设备：磁盘，光盘等；
   2. 子系统的互连
      1. CPU 和存储器（主要指内存）主要通过总线来连接，包括：数据总线，控制总线，地址总线；
      2. I/O 设备的连接：不能和CPU直连，因为大家的速度不一样，需要通过输入输出控制器（或者适配器）中转，常见的控制器有：USB，HDMI，火线，SCSI
      3. 输入输出设备的寻址
         1. I/O 独立寻址：CPU 使用单独的指令来寻址
         2. I/O 存储器映射寻址：CPU 使用与主存储器相同的指令来寻找（方案：CPU 将输入输出设备的寄存器当做内存中的某个单元），优点是共用指令，缺点是占用内存地址；（此时可使用虚拟内存方案来解决）
   3. 程序执行
      1. 机器周期：取指令，译码，执行；
      2. 输入输出操作的三种同步方式（因为CPU 和输入输出的速度不同，所以需要有一种方案，可以用来同步大家的速度）
         1. 程序控制输入/输出：CPU 等待 I/O 设备，每隔一段时间，CPU 就去扫描一下设备状态，看有没有指令等待处理；（或许可以理解为轮询）
         2. 中断控制输入/输出：CPU 通知 I/O 可以传输，之后不管了；等 I/O 设备准备好，通知 CPU 开始；在 I/O 设备准备好前，CPU 可以先去干别的；（有点像web socket）
         3. 直接存储器存取（DMA）：给 CPU 增加了一个助理，CPU 收到指令后，通知 DMA 准备，之后CPU 干别的；等DMA 准备好了，DMA通知CPU 需要使用总线资源，然后 CPU 停止使用总线并转交给 DMA 使用；在 DMA 和内存之间完成数据传输后，CPU 恢复正常工作；在这种情况下，CPU 在 DMA 和 内存之间传输数据时，可以偷懒空闲一会（事实上，这一会经常是整个过程最占用时间的部分）；DMA 的缺点是有可能会出现数据不同步导致冲突的情况；
   4. 体系结构
      1. 复杂指令集计算机：优点：编程比较简单；缺点：控制单元的电路变得非常复杂，解决方案是将 CPU 分层，增加一层微内存，它用于保存指令集中每个复杂指令的一系列操作，英特尔的奔腾CPU即是使用这种设计方式；
      2. 精简指令集计算机：复杂指令使用简单指令进行模拟；缺点：编程比较复杂
      3. 流水线：可以尽量减少空闲；（对相同类型指令的批量处理，实现指令级并发）
      4. 并行处理：通过多个控制单元，多个算术单元，多个内存单元来实现；（线程级并发）(多核心的CPU是否即是一种并行处理的实现？是的，不过应该是属于进程级并发了）
6. 计算机网络和因特网
   1. 引言
      1. 网络：一组可相互通信的设备相互连接构成，设备包括主机、服务器、路由器、交换机、调制解调器等；
         1. 局域网：局部区域数量有限的设备相互连接的私有网络；
         2. 广域网：比局域网规模更大的网络，例如跨地区，跨国家等；
         3. 互联网：两个或多个网络互相连接的时候，称为互联网，或者网际网，因特网即是一个最著名的大型的网际网；
      2. 网络的运行，需要硬件，也需要软件；它们之间通过协议分层来相互配合；发送器，接收器，以及所有中间设备都需要遵守相同的协议，以保证有效的通信；（或许可以考虑通过快递的转运和分发中心来比喻？）
      3. 协议分层：模块化，服务与实施分离，降低复杂度，降低维护成本；
      4. TCP/IP 协议族：一个分层协议
         1. 地址和数据包名称
            1. 应用层：通常使用名称来定义提供服务的站点，例如域名，邮箱地址等；应用层的职责是创建消息（这些消息也有一定的格式规范，取决于所使用的协议）；
            2. 传输层：提供进程间的通信服务；传输层的职责是创建/分段用户数据报
               1. 在传输层地址被称为端口号，它的作用是在源和目标之间，定义应用层程序（提供一层应用程序的抽象）；
               2. 它可以通过各程序的本地地址，来辨别多个同时运行的本地程序（即使用端口号）；
            3. 网络层：IP地址，独一无二的定义了该设备与因特网的连接，它是一个逻辑地址；网络层的职责是创建包含更多一层头部信息的数据报；
            4. 链接层：链接层的职责是创建桢，提供节点与节点之间的链接；（例如两台机器间通过WIFI、蓝牙或网线的链接）
               1. MAC地址，是在本地定义的地址，它定义了一个特定的主机或路由器，它是一个物理地址；
            5. 物理层：各种信号转换和传输的方式；
         2. 或许可以根据访问的 url 从左到右进行记忆：
            1. HTTP 表示应用层，即对待传输的数据使用 HTTP 协议来打包；
            2. 端口号 表示传输层，即表明源机器和目标机器之间哪两个程序要建立连接和传输数据；
            3. IP 地址表示网络层，即表示哪两台机器之间要建立连接；
            4. WIFI 或蓝牙表示链接层，即表示使用哪种网络连接设备建立连接；
            5. 数字信号或模拟信号表示物理层，即表示使用哪种电子信号进行传输；
   2. 应用层
      1. 提供服务：该层不需要向其他协议提供服务，只需要向用户提供服务，因此它比较灵活，可以根据需要添加协议，只要它能够接收传输层的服务即可；这种也导致目前不计其数的应用层协议，大家根据需要创建并使用；
      2. 应用层模式
         1. 客户机-服务器模式 Client Server
            1. 服务提供者是一个应用程序，叫做服务器进程；这个进程持续运行，等待客户端进程的应用程序通过网络连接要求服务；
         2. 端到端模式 P2P
            1. 端到端只在两个计算机之间建立连接；
            2. 最适用的场景是网络电话；
            3. 优点：易于拓展，低维护成本，无需昂贵的服务器；
            4. 缺点：安全性低；在分散的服务之间建立安全的通信较为困难；
         3. 标准化客户端-服务器应用
            1. 万维网和超文本协议：连接文档的存储库；文档称为网页，提供服务的地方称为站点；
            2. 客户端：即浏览器，由控制器，解释器，和客户端协议三部分构成；控制器负责接受键盘或鼠标等设备的输入；解释器负责解释HTML/CSS/JS；协议包括HTTP、FTP等；
            3. 服务器：存储网页，每当收到请求时，将文档发送给客户端；
            4. 统一资源定位器：URL，由4部分构成，包括协议、地址、端口、文档路径；
            5. 客户端-服务器应用程序包括：超文本传输协议 HTTP，文档传输协议 FTP，电子邮件 EMAIL，远程登录 TELNET，安全外壳 SSH，域名系统 DNS
            6. SSH 安全外壳最初是为了解决 TELNET 的不安全而设计的，但现在用途更广泛了；它有 SHA-1 和 SHA-2 两个版本，互相之间不兼容，前者有安全漏洞；
            7. 域名系统 DNS 是一个独立的应用程序，它通过站点名称和 IP 地址的映射，解决了人们通过名称而非数字记住站点的问题；
   3. 传输层
      1. 提供的服务：进程间通信地址（即端口号）；（此处的进程间，可能既可以表示客户端进程与服务器进程，同时也可以表示服务器本身的多个进程之间，比如本地A程序访问本地B程序提供的服务）
      2. 传输层协议
         1. UDP：用户数据协议，user data protocol，缺点：无连接，不可靠；优点：资源开销少；
         2. TCP：传输控制协议，transfer control protocol，可靠的连接；它会将数据分段传输；
   4. 网络层
      1. 提供的服务：
         1. 打包：从传输层接收数据报，然后添加源地址、目标地址、以及其他网络协议需要用到的头部信息；（此处的源地址和目标地址，除了常用的IP地址外，估计还包括机器在局域网内部的地址？答：是的，还包括 MAC 地址）
         2. 数据包传递：使用不可靠、无连接的传递；
         3. 路由：从所有路线中，找到最优的路线；
         4. 解包：等待所有的包到齐，解开，发给传输层；
      2. 网络层协议：IPv4，IPv6；
   5. 数据链路层（或许可以理解为机器间的连接方式，比如蓝牙、WIFI、LAN等）
      1. 提供的服务：
         1. 提供节点对节点之间的链接（节点指 LAN 或 WAN）；
         2. 封装：将数据包封装到桢中；（然后另一段通过接收和解析桢来获得所要的数据）
      2. 协议：TCP/IP 协议族没有规定这一种的协议；这一层的协议种类比较多，包括：
         1. LAN：以太网、Wifi、蓝牙
         2. WAN
            1. 有线：拨号上网 PPPoE，数字用户回路 DSL，有线电视网络
            2. 无线：WiMax，手机网络，卫星通讯；
   6. 物理层
      1. 提供的服务
         1. 信号转换：数模转换、数数转换、模数转换、模模转换等；
         2. 信号传输：数字化传输、模拟传输；
   7. 传输介质
      1. 导向介质：双绞线、同轴电缆、光纤；
      2. 非导向介质：无线电波、微波、红外波；
7. 操作系统
   1. 引言
      1. 计算机由硬件和软件两部分组成，其中软件又分为操作系统和应用程序两种；
      2. 定义：操作系统是硬件和用户（包括程序和人）的一个接口，它使得其他程序更加方便有效的运行，并更加方便的对计算机硬件和软件资源进行访问；
      3. 在计算机通电后，通过内存中的ROM小程序，实现自举的过程，将操作系统从磁盘载入内存；
   2. 演化
      1. 批处理系统，分时系统，个人系统，并行系统，分布式系统，实时系统（在特定时间限制内完成任务，例如自动驾驶的实时监控）；
   3. 组成部分
      1. 内存管理器
         1. 单道程序：一次只能一个程序载入内存，执行完毕后，再载入下一个程序；已淘汰
         2. 多道程序：一次允许多个程序载入内存；
            1. 非交换：分区调度，分页调度；
            2. 交换（运行过程中，程序可以在内存和硬盘之间多次交换数据）：请求分页调度，请求分段调度，请求分页和分段调度；
         3. 虚拟内存：在请求分页调度和请求分段调度中使用；
      2. 进程管理器
         1. 程序（在磁盘），作业（被选中），进程（进内存）
         2. 状态图：保持状态，就绪状态，运行状态；
         3. 调度器：作业调度器，进程调度器，
         4. 队列：通过多个队伍和多种策略，解决计算机资源的分配；
         5. 进程同步：避免死锁和饿死；
      3. 设备管理器
         1. 不停监视所有输入/输出设备
         2. 为每个设备维护一个队列；
         3. 设置访问设备的不同策略；
      4. 文件管理器
         1. 访问，创建，删除，修改，命名，存储，归档，备份；
      5. 用户界面（或命名解释程序）：负责操作系统与外界用户之间的通信；有 GUI 窗口和 CUI shell 两种形式；
   4. 主流操作系统
      1. UNIX：内核，命令解释器，标准工具，应用程序
      2. LINUX：内核，系统库，系统工具
      3. WINDOWS：面向对象，多层的操作系统；
         1. HAL：硬件抽象层
         2. 内核
         3. 执行者：对象管理器，安全引用监控器，进程管理器，虚拟内存管理器，本地过程调用工具，I/O管理
         4. 环境子系统
8. 算法
   1. 定义：步骤明确，有序集合，有限时间内，产生结果
   2. 程序结构由三部分组成：顺序，判断，循环
   3. 算法的表示：UML图，伪代码；
   4. 基本算法：求和，求积，求最大最小值，排序，查找；
   5. 排序
      1. 选择排序：找出最小值，放到最左边；在剩下的元素中，循环这个过程；
      2. 冒泡排序：从最右边开始，逐个检查元素，如果遇到比自己大的元素，交换位置，直到最左边；再从最右边开始循环；
      3. 插入排序：将最左边的值，插入已排序的列表；
   6. 查找：顺序查找，折半查找；
   7. 子算法：在算法中抽象一个利用的子过程，在需要的时候，重复调用，使程序更加简单易懂；也易于维护；
   8. 递归：算法的定义涉及调用自身；
   9. 迭代：算法的定义不涉及调用自身；
9. 程序设计语言
   1. 计算机语言：一组预定义的单词，根据语法写出的语句集合（语法是一些事先定义的规则）
   2. 机器语言：计算机唯一能看懂的语言，因此，所有任何语言，最终都需要翻译成机器语言，以便计算机可以看懂并执行；
   3. 汇编语言：引入了符号和助记符，相当于多了一层抽象；
   4. 高级语言：继续增加抽象，让程序员可以摆脱硬件和操作系统的约束，直接只关注程序本身；
   5. 编译和解释的区别
      1. 编译：直接将源程序翻译成目标程序；
      2. 解释：
         1. 第一种：逐行翻译，立即执行，出错马上反馈，程序中止；
         2. 第二种：先翻译成字节码；然后字节码可以拷贝到有虚拟机的机器上，进一步编译成目标程序；相当于增加了一层抽象，目的是增加可移植性；由字节码翻译器面对不同的操作系统，而源程序则就不用考虑这个问题；
      3. 翻译过程
         1. 词法分析：搞定单词
         2. 语法分析：搞定语法
         3. 语义分析：搞定意思
         4. 代码生成：生成目标程序（据说是助记符表？）；
   6. 编程模式
      1. 过程式
      2. 对象式
      3. 函数式
      4. 声明式：使用逻辑推理来回答答题，常用于人工智能领域，例如 Prolog；
   7. 过程式和对象式中的常见概念：标识符（即对象的名称，内存地址的抽象化，方便引用），数据类型（简单，复合），变量，常量，字面值，输入输出，表达式（由运算符-算术/逻辑/关系 + 操作数组成），语句（赋值、复合、控制）；
   8. 两类控制语句：顺序，选择（if-else 双路，switch-case 多路），重复
10. 软件工程
    1. 软件有生命周期，当软件过时，意味着生命周期即将结束；
    2. 生命周期包括分析、设计、开发、测试四个阶段；
    3. 分析阶段产生规格说明文档，此文档说明了软件要做什么，但不说怎么实现；
       1. 过程式：
          1. 数据流图
          2. 实体关系图：设计数据库需要；
          3. 状态图：显示系统中的实体，在事件触发下，状态会如何改变；
       2. 对象式：
          1. 用例图：显示了用户如何与系统进行交互；
          2. 类图
          3. 状态图；
    4. 设计阶段定义了如何完成说明文档所定义的内容；
       1. 过程式：将软件分解为模块和过程；
          1. 模块化：将大程序分解成小程序；耦合最小化，内聚最大化；
       2. 对象式：罗列类中的细节；
    5. 开发阶段
       1. 过程式：编写模块的代码
       2. 对象式：编写类的代码；
11. 数据结构
    1. 数组
       1. 数组是元素的顺序集合，这种结构也决定了对数组的元素进行插入和删除，会比较麻烦，因为它涉及动态调整插入或删除位置的后续元素的一系列调整；
       2. 数组可以是一维数组，也可以是二维，也可以是多维；
       3. 数组一般使用行主序存储；也可以使用列主序存储，但前者比较常见；
       4. 未排序的数组，元素的查找只能按顺序查找；已排序的数组，则可以使用折半查找；
       5. 由于数组是元素的顺序集合，因此对数组中的元素进行提取是比较容易的，只需要知道它的下标即可；
       6. 数组适用于插入和删除操作少，而检索和查找操作多的场景；
    2. 记录
       1. 记录中的元素可以相同类型，也可以是不同类型，关键在于这些元素有某种关联关系；(记录，即是大多数语言中的简单对象）
       2. 数组一般是元素的集合，而记录是可以用来确认元素的部分或标识；
    3. 链表
       1. 链表是一个数据的集合，每个元素包含下一个元素的地址；即每个元素包含两部分：数据和链（即指针）；
       2. 链表的元素习惯上称为节点，节点包含两个域，一个用来存数据，一个用来存地址；
       3. 数组在内存中是连续存储，而链表可以随机存储；
       4. 数组通过索引连接起来，而链表通过指针连接起来；
       5. 链表的好处是插入和删除元素都很容易，只要改变指针的指向即可，缺点是它比较占据内存空间，因为它需要多一倍的空间用来存储地址；
       6. 链表的另外一个缺点是只能顺序查找；
       7. 链表适用于需要大量进行插入和删除操作的场景，但链表的查找速度较慢；
12. 抽象数据类型
    1. 抽象数据类型（ADT）基于基本数据类型来实现，使用 ADT 的目的是为了能够在更高的抽象层次上进行思考和解决问题，减少对底层实现细节的关注；
    2. 抽象数据类型通过封装公有操作、私有操作、数据结构来实现（感觉跟类的实现很像）；
    3. 常见的抽象数据类型：
       1. 栈
          1. 应用场景：倒数数据，步骤回溯、配对数据（例如括号的检查）、数据延迟使用等；
       2. 队列
          1. 应用场景：处理速度差距大的两个环节的协作；
       3. 广义线性表
          1. 应用场景：元素的存储是随机的，但读取是顺序的；
       4. 树
          1. 应用场景：文件索引、赫夫曼编码（文件压缩）、表达式树、文件夹目录
       5. 图
          1. 应用场景：寻找网络中是的最优路径，例如路由、导航等场景；
    4. 其实还有其他很多，所有面向对象编程中的类，大部分都可以看做是抽象数据类型；
13. 文件结构
    1. 引言
       1. 文件是记录的集合，存储在二级存储设备上面；
       2. 记录是由一些由属性组成的对象；
       3. 设计一个文件时，核心是如何从文件中检索出信息，即检索出所需要的记录，有两种读取方式：顺序存取（顺序文件）、随机存取（索引文件、散列文件）；
    2. 顺序文件
       1. 特点：需要查找某个记录时，需要从头开始挨个顺序核对，直至找到为止；
       2. 更新过程：涉及四个文件，包括事务文件，旧文件，新文件，错误文件；
       3. 通过更新程序，逐个比对事务文件和旧文件中的键，事务的键小，新增记录；键相等，修改或删除记录；旧文件键小，记录不变；
       4. 错误文件记录两种情况：增加相同标识，删除不存在的标识；
    3. 索引文件
       1. 为顺序文件提供快速查找的功能；只存储两个字段，键和地址，其中键是按顺序排列的；索引体积很小，使用的时候加载到内存中，通过折半算法进行查找到键，然后获得对应记录的地址；
    4. 散列文件
       1. 设计一个散列函数，可以将键直接翻译成地址，然后到该地址中取得记录；
       2. 散列函数
          1. 直接散列法：优点是不会出现重复，缺点是很浪费空间；比如身份证号，系统中的用户可能才100个，即需要占用18位编号对应的存储空间；
          2. 求模法：文件大小，除以键值，得到的余数加1，作为地址，address = key mod list_size + 1；当文件大小为素数时，得到的结果出现重复的概率非常小；因此，当设计存储空间时，以最接受空间容易的素数，作为空间的值，例如假设需要300左右的空间，那么最接近的素数是307，因此选择以307做为实际空间大小；会存在一点浪费，但不大；
          3. 数字析取法：例如从6位的键值中，按固定位置挑出3位，例如：138655，固定挑 1、3、4 位，因此得到 186 作为地址（感觉存在冲突的可能性也不小，例如和 138653 即冲突了）
          4. 其他方法：平方中值法、折叠法、旋转法、伪随机法等；
       3. 冲突解法办法
          1. 开放寻址：冲突的时候，新键的地址，为老键地址+1；优点：看似简单粗暴；缺点：增加了未来出现更多冲突的可能性；例如多个键映射到同一地址；或者新地址已经被其他键占用；
          2. 链表法：在冲突键的记录末尾，添加新键的指针；这样相当于将所有的存在冲突的键，组成了一从链表，共享一个地址，然后按顺序查找；
          3. 桶列法：相当于批量创建链表，不管是否存在冲突（提前设计）；缺点：存在很大的空间浪费；
          4. 组合法：使用多种方法组合来解决冲突；
    5. 目录
       1. 用来组织文件，其实它本身也是一种文件，比较特殊的文件；这个文件保存了其项下所有文件的位置（相当于索引），另外它还可以用来设置访问权限、文件被增删改的时间等；
       2. 目录一般被处理成像树那样的抽象数据类型；
       3. UNIX系统中的目录
          1. 特殊目录
             1. 根目录：以 / 表示
             2. 主目录：每个用户有一个主目录，首次登录系统时，会默认先进入这个以用户名区分的主目录（也可视为个人目录，可能相当于 windows 下的我的文件）
             3. 工作目录：即当前目录；
             4. 父目录：即当前目录的上一级目录；
          2. 路径和文件名
             1. 每个目录和每个文件都有名字，不同目录中的文件甚至会有相同的名字，我们可以通过路径+文件名的形式来标识它们；
                1. 绝对路径：以根目录 / 开始进行标识；/cat/john/test.file
                2. 相对路径：以当前目录开始进行标识，例如 john/test.file
    6. 文本文件与二进制文件
       1. 文件最终在存储设备上，都是以二进制位的序列进行存储的，但是，它的翻码有两种类型，一种是文本文件，一种是二进制文件；
       2. 文本文件：它会将文件中的所有东西，都当做字符来存储，包括数字如100也当成1、0、0三个字符来存储；它不能直接存储整数、浮点数或其他数据类型；
       3. 二进制文件：它会将文件中的所有东西，都按照它们在内存中的二进制值来存储，即原封不动；但是，由于数据类型有很多种，为了能够让存储的数据在提取时被正确解读，它需要为每个二进制值增加一个类型的标识，这样提取的时候才能够正确翻译；因此，用二进制来存储，会占用更多的空间；但好处是可以保存所有的数据类型；
14. 数据库
    1. 引言
       1. 定义：传统上，数据是保存在文件中的，优点是很灵活，缺点是数据在不同的文件与文件之间的无法建立关联，使得数据无法做为一个整体进行关联使用；数据库则通过将这些相关的数据做成一个逻辑有序的集合，让数据的使用具备以下优点：减少冗余、保持完整、避免不一致、提高效率、安全管理；（注：数据库只是一种数据的逻辑集合，跟数据的物理存储是无关的，例如物理存储可能是分开的）
       2. 数据库管理系统：定义、创建、维护数据库的一种工具；由硬件、软件、数据、用户、规则等组成；
    2. 数据库体系结构：内层（与硬件交互，负责传输数据到设备，定义存储的方法），概念层（定义数据模式，是中介层，使得用户不必与内层直接打交道）、外层（将数据展示成用户可以理解的图式或格式）；
    3. 数据库模型：定义数据的逻辑设计，描述不同数据之间的联系；有三种模型：层次模型（已过时）、网状模型（已过时）、关系模型（正当时，还有另外两种常见的模型：分布式模型、面向对象模型）
    4. 关系数据库模型
       1. 关系（也即二维的表）：表有一个唯一的名称；
       2. 属性：表中的列称为属性，列的数量即为关系（表）的度，例如总共有3列，则关系的度为3；
       3. 元组：表中的列称为记录（或叫元组）；
    5. 关系的操作
       1. 操作类型
          1. 基本操作：增（插入）、删（删除）、改（更新）、查（选择）
          2. 其他操作：投影、连接、并、交、差；
       2. 结构化查询语言
          1. 投影：从表中选择部分列出来；
          2. 连接：基于共有的属性，把两个表连接起来，记录的数量不变，可以只选择部分列，例如 select 列1，列2，列3， 列4 from 表1，表2 where 列1 = 列4
          3. 并：将两个表中的记录合并到一个新表中，即记录的合并（去除重复项）；
          4. 交：两两个表中相同的记录提取出来到一个新表中，即提取共同项；
          5. 差：将A表中的，不在B表中的记录提取出来，即相当于 A表 减去 B表余下的记录；
    6. 数据库设计
       1. 步骤：
          1. 访谈调研，收集数据和文件，了解数据的使用需求；
          2. 建立实体关系模型
       2. 实体关系模型：通过E-R图来表示，矩形表示实体，椭圆表示实体的属性，菱形表示实体之间的关系（动作，1对多等）
       3. E-R图到表：给实体（矩形）建表，给实体间的关系（菱形）建表
       4. 规范化（即范式NF）：让表之间的关系更加坚固，1NF,2NF,3NF,4NF,5NF
    7. 其他数据库模型：
       1. 不完全的分布式数据库：分公司存储自己的雇员信息，总公司可以读取所有的雇员信息；
       2. 复制式的分布式数据库：一个节点是对另外一个节点的完全拷贝（增加健壮性）；
       3. 面向对象数据库：记录由对象和其属性、方法组成；
       4. XML：可以用嵌套结构表示数据；
15. 数据压缩
    1. 引言
       1. 有损压缩：MP3, JPG, MPEG
       2. 无损压缩：赫夫曼编码、游程长度、Lempel Ziv等；
    2. 无损压缩
       1. 游程长度编码：将重复出现的字符，用出现次数+字符值来表示，例如：AAAAAAAAAA，表示为 A10，即10个A；适用场景：用符号组成的数据；
       2. 赫夫曼编码：
          1. 先统计各种字符出现的频率；按频率从小到大，按对组合一个新节点，最终得到一颗树；
          2. 从树的根节点开始，根据权值大小，分配0和1；
          3. 每个字符，从根节点出发，一路路过的0或1，即组成每个字符的编码；得到一张每个字符的编码表
          4. 将源文件按照编码表进行转译；
          5. 解压缩时，将压缩文件按照编码表进行还原；
          6. 总结：越频率出现的字符，其编码越短，因此从总体上节省了空间；
       3. Lempel Ziv 编码
          1. 思路：自适应编码思想，发送方制作一张字典，每个字符串有相应的索引，将文件中的字符串替代成索引，然后发送；对于接收方，由于字典是按约定的共同规则建立的，因此，可以根据发放的压缩文件，还原出字典，并逐步得到解压缩后的源文件；LZ 编码有多种不同的版本（即不同的编码规则）；
             1. 步骤：
                1. 建立字典索引：从未压缩的文件中，选择未在字典中出现的最小子字符串，放入字典，分配一个索引值；
                2. 压缩：除了该子字符串的最后一个字符外，前面的部分如果已经在字典中出现，替换成字典中的索引，写入压缩文件；
                3. 发送文件给接收方
                4. 建立字典索引：从压缩文件中，选择未在字典中出现的子字符串，放入字典，分配一个索引值
                5. 解压缩：除了该子字符串的最后一个字符外，前面的部分如果已经在字典中出现，替换成字典的字符串，写入解压缩文件；
                6. 重复步骤5，最后得到一张完整的字典和源文件；
    3. 有损压缩
       1. 对于文本文件和程序文件，有损压缩不可接受，但对于图像、音频和视频，有损可以接受；因为我们的生理限制，只能识别一定范围内的差别；JPEG（联合图像专家组）用来压缩图片，MPEG（运动图像专家组）用来压缩视频，MP3（即MPEG-3，第3代音频压缩格式）用来压缩声音；
       2. 图像压缩
          1. 思路：将图像转化成数，揭示出数的冗余，再使用无损压缩的方法来去除这些冗余，最终实现压缩；
          2. 步骤
             1. 分块：黑白图使用8位表示每个像素，彩色图使用24位（一个3个8组成的数组，例如[8,8,8])来表示每个像素；每张图片是由很多个像素组成的，分块指先将图片划分成多个 8*8 的像素块，后续压缩以像素块为单位进行处理；
             2. 离散余弦变换：这种变换方法有“能量集中”的特性，而自然界的声音和图像信息，刚好也有能量集中的特性，因此这种变换方法，可以最大程序的提示冗余，实现更好的压缩效率；将像素块的表P变换成新表T
             3. 量化：定义一张通用的8*8量化表，将 T 表中的每个值除以量化表上面的值，舍弃小数部分，得到一个新值R（大多数情况下，由于变换的能量特性，这一步会得到很多0，形成冗余，为压缩创建了条件）
             4. 压缩：使用Z字形按对角线读取R表，最大程序的聚集所有0值（以便压缩时得到最好的效果）；然后使用游程长度的压缩方法，将量化结果进行压缩；
       3. 视频压缩
          1. 思路：视频是图像桢的组合，因此视频压缩分为空间压缩（单桢压缩，即图像压缩）和时间压缩（丢弃多余的桢）两部分；
          2. 步骤
             1. 将桢分成三种，分别是 I 桢（可以理解为关键桢），P 桢（可以理解为基于前 I 桢和后 I 桢计算的变化桢），B 桢（可以理解为基于前面 I 桢和后面的 P 桢生成的中间桢）
             2. 发送顺序：I P B B P B B I
          3. 以上是 MPEG-1 版本的工作原理，MPEG 不断更新，最近的版本已经到了 MPEG-7（多媒体内容描述接口，使用XML 描述元数据和视频内容，方便用户对感兴趣的内容进行搜索，注意，它不是一项视频压缩编码标准，只是内容描述标准）；最近的一个压缩编码标准是 MPEG-4，相对于MPEG-2，MPEG-4 不再使用宏区块作为视频分析，而是以视频上的个体为变化记录进行分析（优点：当视频变化很快，码率不足时，也不会出现方块画面）
       4. 音频压缩
          1. 两种类型的音频，语音（64 KHz的数字信号）和音乐（1.411 MHz的数字信息，比语音的频率覆盖范围大很多，约22倍）
          2. 两种压缩技术
             1. 预测编码：对样本间的差别进行编码，通常用在语音；
             2. 感知编码：
                1. 基于心理声学，即利用人耳的生理缺陷进行掩盖，包括两种：
                   1. 频率掩盖：高频掩盖低频
                   2. 时间掩盖：高频会在一定时间内降低耳朵的听觉灵敏度；
                2. 操作：分析音谱，把音谱分成几个组，0 位分配给频率范围被完全掩盖的，小数位分配给部分掩盖的，整数位分配给不能掩盖的；
          3. MP3 码率：每秒音频所需要的编码位数，常见的有：96 kbps，128 kbps，160 kbps，320 kbps；CD 上未被压缩的码率一般是 1411.2 kbps）；声音的质量跟码率和编码器都有关，因为编码器的工作在应用合适的心理声学模型，滤除人耳无法识别声音。因此，如果模型优秀，甚至可以做到在低码率的基础上，实现比高码率差编码器更好的效果；另外，不同的人，对声音的敏感度是不一样的，因此以上理论只对同一个人进行测试有效，如果是不同的人，则失去了比较的意义；
          4. 如果由于某种原因，比如需要对音频进行混合、编码等处理，不允许出现质量损失，则应该使用无损压缩；
16. 安全
    1. 引言
       1. 安全的目标：机密性（避免未授权的使用），完整性（避免未授权的修改），可用性（实时可用）；
       2. 以上目标不仅在信息存储时需要实现，在信息传输时也需要实现；
       3. 攻击类型：针对以上三个安全目标，分别有3大类的攻击
          1. 机密性：嗅探、流量分析
          2. 完整性：修改、假冒、重放、抵赖；
          3. 可用性：拒绝服务（例如 Dos）
       4. 安全技术：密码术、隐写术
    2. 机密性
       1. 类型：对称密钥、非对称密钥；
       2. 对称密钥密码术
          1. 传统式：面向字符
             1. 替换密码：用一个符号替代另外一个符号；
             2. 单字母密码：例如加法密码（移位密码或凯撒密码）-明文、密文和密钥都是模26中的整数；注：这种加密方式可以统计字符频率来破解；
             3. 多字母密码：字母的每一次出现都使用不同的替换密码，因此一个字符将会对应多个字符，这多个字符组成了一个集合，称为子密钥流；
                1. 例如：自动密钥密码，约定第一个子密钥流的替换字符，然后第2个替换字符基于明文的第1个字符，第3个基于明文的第2个字符，以此类推；
             4. 移位密码：通过改变符号的位置来实现加密，而不是通过替换；相当于给字符重新排序了；
             5. 流密码：加密和解密一次只对应一个符号（一个字符或者一个位）进行，因此有明文流、密文流和一个密钥流组成；
             6. 分组密码：以组为单位，整个分组单独使用一个密钥；密文分组则取决于明文分组
             7. 组合密码：局部分组+整体流；
          2. 现代式：面向位（原因：数据的种类变多了，包括图片、声音、视频等；另外，由于一人字符会替换8位或16位，由于混淆的数据变成8倍大，即使用旧的方法，也变得更安全）
             1. 分组密码：以 n 个位为分组的单位（多拆少补）进行分组加密；常用的 n 包括：64，128，256， 512 等；
             2. 流密码：跟传统的流密码原理相同，只是字符改成了位；
       3. 非对称密钥
          1. 与对称密钥的区别
             1. 场景：对称密钥面向多个共享秘密，非对称面向个人保守自己的秘密；非对称还可以用于数字签名和身份验证；
             2. 操作：对称基于字符的排列或替换；非对称基于数字的函数运算；
          2. 非对称通常用来加密或解密小段信息（原因：对于长消息，对称密钥术速度要快，非对称则比较慢，因此它使用指数和模计算，当数字比较大时，计算非常费时）
    3. 其他安全服务
       1. 消息完整性：信息是公开的，但不能被篡改（例如遗嘱）
          1. 消息和消息摘要
             1. 可以类比于文档和作者的指纹；如果有人伪造文档，但文档上面的指纹不符，则可以查出来；
             2. 通过散列函数，从消息中，生成消息的压缩版本，即摘要；如果消息有变更，则压缩出来的摘要会不同；（摘要需要通过不可篡改的渠道进行传输，避免传输过程中摘要被改了）
          2. 散列函数
             1. MD：消息摘要，message digest；MD5 可以将512位的消息生成128位的摘要（目前发现128位太短，不够安全，因此发明安全散列算法 SHA 算法来改进它）
             2. SHA：安全散列算法，secure hash algorithm；
       2. 消息验证
          1. MAC：消息验证码，message authentication code，通信双方拥有一个只有他们自己知道的 K 密钥，消息使用 K 密钥生成 MAC，然后将 M 和 MAC 一起传输给接收方（可以使用不安全通道）；接收方收到消息后，使用 K 密钥将 M 生成 MAC ，再与收到以 MAC 进行比对，如果正确，说明消息没有被改；如果错误，说明已经被改过；
          2. HMAC 是新一代的消息验证码标准；
       3. 数字签名
          1. 数字签名使用一组公私钥，发送者使用私钥为发放的消息生成签名，签名随同消息一起发送；接收者使用公钥对签名进行计算，判断签名是否来自真实的发送者；（注：这一过程和非对称数字加密正好相反）（再读一遍的时候，感觉没有相反啊，顺序正好相同）
          2. 每条消息生成的签名不同，它是根据消息内容计算出来的；
          3. 考虑到非对称密钥的性能不高，对于长消息的场景，可以考用统一的散列函数生成摘要，之后再对摘要使用签名，这样就可以避免速度慢的问题；
       4. 不可抵赖性
          1. 通过引入公正可信的第三方，来解决不可抵赖性的问题
          2. 过程：消息发送者将消息发给第三方，第三方验证消息无误后，保存副本，然后使用自己的私钥重新加密消息，并发给接收者；由于第三方做了验证的工作，如果将来发送者要抵赖，第三方可以根据保存的消息副本进行举证；
       5. 实体验证
          1. 使用三种证据：所知道的（例如密码），所拥有的（例如身份证），所固有的（如指纹）
          2. 验证分类：
             1. 密码：不安全，因为密码很容易被破解，例如在传输过程中；
             2. 挑战-回应：通过回应挑战，证明自己拥有密码；
       6. 密钥管理
          1. 对称密钥分发
             1. 密钥分发中心（Key Distributed Center）：
                1. 使用可信的第三方，解决由于人数增加带来的密钥分发问题，不然密钥数量会上升到 n * (n - 1)；
                2. 过程：A 通知 KDC 请求要与 B 通信，KDC 通知 B，如果 B 同意，则 KDC 生成一个密钥，发给双方，双方使用这个临时的密钥建立通信；（如何确保KDC 传输密钥给 A/B 的过程是安全的，避免密钥被中途截获？貌似这涉及 KDC 与 A/B 的通信加密，需要使用加密通道）
             2. 多个密钥分发中心：由于全球用户数量多太，按地区划分成多个区域，每个区域设立一个 KDC ，当有用户需要跨区通信时，中间就由两个或多个 KDC 建立起连接；
             3. 会话密钥：KDC 给每个成员签发一个密钥，用来建立成员和 KDC 之间的安全通信；如果 A 想和 B 通信，就向 KDC 发起请求；KDC 返回一个临时会话密钥，A 可以用自己的密钥打开，B 也可以用自己的密钥打开，这样 A B 就都获得了这个临时的会话密钥；如果双方有任何一方的身份不真实，他们都无法打开取得会话密钥；
          2. 公钥分发
             1. 引入认证机构 CA ( Certificate Authority），
                1. 首先每个用户在 CA 的数据库里面有一个公钥；
                2. CA 有一个众所周知的公钥，如果 A 想和 B 通信，可以利用这个公钥给 CA 发送请求， CA 使用自己私钥解密查阅请求，然后从数据库中找出 B 的公钥，加密后发给 A，A 收到后，使用该 B 的公钥给 B 发消息即可；这样就可以解决公钥骗局的问题，确保 A 收到的 B 的公钥是真实的；(貌似这个就是常用的 SSL 证书的方式，用户 A 向证书颁发机构申请一份证书，里面有私钥也有公钥，私钥自己保存，公钥 CA 保存；任何想与A 通信的人，使用 CA 的公钥发送请求，这个请求只有 CA 能够查看，CA 收到请求后，将 A 的公钥发给申请人，然后申请人用这个 A 的公钥与 A 进行加密通信，确保消息只有 A 能够查看；当然，此处还有一个问题，对于 A 发给 B 的消息，虽然是加密的，但由于 A 的公钥是公开的，所以所有人都可以查看，仍然不够安全，除非 B 也有申请一个自己的公钥，让 A 对消息进行加密）（对于移动客户端，由于开发者可以控制移动端的代码，可以自行引入公私钥加密方法，即每个客户端有自己的私钥，然后服务端使用对应的公钥对消息进行加密，只有真正的客户端收到后才能解密，对于伪造的客户端，无法解密）
                3. 如果每个用户在 CA 的数据库中的公钥的格式都不同，则会带来很大的麻烦，因此通过 X.509 引入证书的标准格式，解决格式不同的问题；避免 A 收到 B 的公钥后，读取不出数据；
    4. 防火墙：允许一些数据包和阻止另外一些数据包的动作；
       1. 包过滤防火墙：基于网络层的信息和传输层的头部信息，来定义过滤规则；
          1. 过滤选项包括：源 IP，源端口，目标IP，目标端口等；
       2. 代理防火墙：也叫应用网关，gateway
          1. 原理：基于消息自身携带的信息进行过滤（即是基于应用层，需要打开数据包，查看数据是否合法，如果合发，再转给真正的服务器进行处理）
17. 计算理论
    1. 引言：本章介绍三个东西，分别是：简单语言、图灵机、任何程序无法知道其他程序是否终止的证明；
    2. 简单语言
       1. 只有三个语句，分别是递增语句、递减语句、循环语句，通过这三个语句，基本上可以模拟出相对复杂的语言（例如 C）（但执行效率会差很多）
       2. 宏：等价于一条语句或多条语句的特定集合；类似于函数，可以重复使用，但与函数的不同在于，没有局部作用域；
    3. 图灵机
       1. 图灵机由三个部分组成，分别是磁带（此处假设空间无限）、读写头、控制器；
       2. 控制器：一个存储有限状态的自动机，即如果：处于当前状态->如果读到什么->就写入什么->然后转移到哪里->最后调置一个新的状态（这样就可以实现无限的循环了）
       3. 当有了控制器并设置相应的有限状态后，我们就可以对前面的简单语言进行模拟，包括递增、递减和循环；
       4. 邱奇-图灵问题：如果存在一个算法，可以使用符号来完成任务操纵，那么也存在一个可以完成这个任务的图灵机；
    4. 歌德尔数
       1. 语言是由符号组成的，而符号可以数字来约定替代，因此，程序可以使用数字来表示；
    5. 停机问题
       1. 停机问题是无法解决的，即我们无法编写出一个程序，去检测另外一个程序是否会停止下来；
    6. 问题的复杂度
       1. 不可解问题
          1. 不可解的问题有很多，可以考虑使用反证法进行证明，即如果它是可解的，是否也会导致停机问题也可解；
       2. 可解问题
          1. 问题的复杂度，可以用相对输入的计算次数量级来表示，即大 O 表示法
             1. 对于 O(log n)，O(n), O(n2), O(n3), O(n4)：当输入在100万以内时，多项式问题可以解决；
             2. 对于 O(10n)，O(n!)：当输入小于100时，可以解决；如果输入很大，可能要算上很长时间，例如几个月，才能有结果；
18. 人工智能
    1. 引言
       1. 定义：人工智能是对某种程序系统的研究，这种程序系统能够在某种程度上模仿人类的一些行为，例如思考、学习、感知和反应等；
       2. 图灵测试：给一组问题，由AI 和真人各给出答案，如果无法辨别答案是由谁给出的，表示通过测试；
       3. 智能体：
          1. 软件智能体：一组用来完成特殊任务的程序；
          2. 硬件智能体：一个用来完成各项任务的可编程系统；
       4. 编程语言：专用的有 LISP 和 PROLOG 两种
    2. 知识表示
       1. 将知识表示成某种数据结构，然后程序可以对其实现操纵；
       2. 4种常见的知识表示方法
          1. 语义网：使用有向图表示知识，有向图由顶点和边组成；顶点表示概念，边表示概念之间的关系；
          2. 框架：相对于语义网使用图来表示知识，框架则使用数据结构来表示相同的知识，计算机更容易处理数据结构；框架由对象和槽组成；对象表示某种事物或概念，相当于语义网中的节点，槽定义了关系的类型和值；
          3. 谓词逻辑
             1. 命题逻辑
                1. 运算符：与，或，非，如果…那么，当且仅当；
                2. 句子
                3. 推理：从已知的事实中，推导新的事实；当找不到反例时，推断就是合法的；
             2. 谓词逻辑：谓词逻辑可以定义命题之间的关系；在谓词逻辑中，句子被分成谓词和参数（谓词很像编程中的函数，是个动词）；
                1. 句子： John’s father loves Ann’s sister，表示为 love [father (John), sister(Ann)]，eat [I, apples]（感觉很像可以转换成树，动词做为 root 节点）
                2. 量词：
                   1. 全称量词“所有的”：变量所表示的全部对象的某些事为真；
                   2. 存在量词“存在”：变量所表示的一个或多个对象的某些事为真；
             3. 超谓词逻辑
                1. 高阶逻辑：扩展了量词的范围，使其能够表达更复杂的关系
                2. 默认逻辑：假设诊断的默认结论都可以被接受，直到出现反例；
                3. 模态逻辑：用来表达 could, may, should 的情形；
                4. 时态逻辑：用来表达 from now on, at some point of time 的情形；
          4. 基于规则的系统：使用规则来表示知识，根据规则，可以从已知的事实中，推导出新的事实；
             1. 组成
                1. 知识库：即规则库
                2. 事实库
                3. 解释器：即推理机，可以根据知识库和事实库的输入，推导出新的事实；
             2. 正向推理：解释器使用一组规则和一组事实，来执行一个行动；
             3. 反向推理：先定目标，然后查事实库，如果目标在事实库存在，推理结束得出结论；如果不存在，查规则库与目标对应的规则，然后验证该规则涉及的事实（进入循环迭代）
    3. 专家系统
       1. 抽取知识：从专家身上抽取知识；这个过程并不容易，一般由专门的知识工程师来执行；
       2. 抽取事实：收集事例和数据，以便后续可以被推理机使用；
       3. 体系结构：由用户界面、推理机、解释器、知识库编辑器、知识库、事实库组成；其中前4个是可以通用的（意味着可以做成框架库），后2个是需要根据实际场景进行搭建的；
    4. 感知
       1. 人类有五官，即5种感知器官，包括视觉、听觉、触觉、嗅觉、味觉；其中前2个计算机已经可以实现，后面3个还有待研究；
       2. 图像处理
          1. 边缘探测：由于边缘部分存在较大的反差，因此可以通过高通滤波器来查找边缘；
          2. 分段：将图像分为不同的区域，每个区域内部是同构的；
          3. 查找深度
             1. 立体视觉：通过使用两只摄像头来实现，原理就像人类的眼睛一样；
             2. 运动：当图像中的物体发生移动时，根据单位移动的幅度，也可以判断出物体的远近；
          4. 查找方向
             1. 光照：假设物体表面的物理特性相同，则根据其反射为光线的数量，可以判断物体的方面；
             2. 纹理：假设物体表面存在规则或重复的纹理，则也可以用来判断方向；
          5. 对象识别
             1. 为所要识别的物体，在数据库建立对象模型；
             2. 将物体视为由多个简单的几何形状组成；在识别对象时，将对象进行分解，如果分解后的结果与存储的组合匹配，则对象被识别；
          6. 应用：可以使用在制造业的流水线上，此时需要检测的目标数量有限，环境相对简单可控，可以取得比较理想的效果；
    5. 语言理解
       1. 语音识别：根据语音信息的输入，抽取单词序列做出输出；
       2. 语法分析
          1. 良好定义的文法；
          2. 词法分析器：基于文法规则建立一棵词法分析树，来判断一个句子的合法性；
       3. 语义分析：在语法分析的基础上，得到句子的意思；意思可以用前面的知识表示规则进行表示，例如使用谓词逻辑等；
       4. 语用分析：进一步明确句子的用途和消除歧义；
          1. 意图：例如告知、请求、询问、承诺等；
          2. 消除歧义：排解一些毫无道理的句子，例如 John eat the ocean;
    6. 搜索
       1. 用状态集合求解问题；有一个初始状态，然后通过多个中间状态，最后到达一个目标状态；例如8数字拼图游戏（9个格式，8个数字，1格为空；目标状态为1~8顺时针有序排列，中间为空）
       2. 搜索方法
          1. 蛮力搜索
             1. 广度优先
             2. 深度优先：在走迷宫的时候，深度优先的方法，一般比广度优先的方法效率高一些；
          2. 启发式搜索
             1. 给每个节点赋一个启发值，该值用来表示节点当前的状态，与目标状态的距离；
             2. 开始搜索时，我们遍历下一层所有的状态，以及它们的启发值，然后从最小的启发值的下一个状态开始搜索；
    7. 神经网络：使用神经元网络去模拟人脑的学习过程；
       1. 生物神经元：由神经细胞体、树突（接收输入）、轴突（发送输出）、神经键（与其他神经元的连接点）组成
       2. 感知器：类似一个神经元细胞，它接收一组输入（带权重），对输入进行求和，如果结果大于阈值，则触发输出；如果小于，则抑制（没有动作）；
       3. 多层网络：将多个层次的感知器组合起来，可以形成多层网络，每一层的输出，成为下一层的输入；第一层为输入层（它们不是神经元，是分配器）、中间层为隐藏层（给上一层的输出加上权重）、最后一层为输出层；
       4. 应用：如果有足够数量、预先定义的输入和输出时，就可以定义神经网络，目前在两个领域得到很好的应用，一个是信用赋值（为每个人建立信用等级）、一个是 OCR 字符识别；