计算机科学导论（原书第3版）
2022-03-05 本文已影响0人
Die时而动
计算机科学导论
[toc]
绪论
- 计算机模型
- 图灵模型
- 冯诺依曼模型
- 存储程序+顺序执行
- 四个子系统
- ALU
- 控制单元
- 存储器
- IO
- 计算机组成部分
- 硬件
- 数据
- 软件
- 计算机科学
- 系统领域
- 计算机体系结构
- 计算机网络
- 计算机安全
- 操作系统
- 算法
- 程序设计语言
- 软件工程
- 应用领域
- 数据库
- 人工智能
- web
- 计算机图形学
- 系统领域
数字系统
- 数字系统：使用符号表示数字
- 位置化
- 非位置化：罗马数字
- 进制与进制转化
数据存储
- 数据相关概念
- 数据类型
- 位，位模式
- 数据压缩
- 错误检测和纠正
- 数字存储
- 整数
- 原码
- 反码
- 补码
- 实数
- 浮点表示法
- 规范化
- 符号，指数和尾数
- 指数余码表示法
- 整数
- 文本存储
- 音频存储
- 采样
- 量化
- 编码
- 图像存储
- 光栅图
- 矢量图
- 视频存储
数据运算
- 逻辑运算
- 与或非，异或
- 移位运算
- 逻辑移位（无符号）
- 算术移位（补码）
- 算术运算
- 加
- 减（补码）
计算机组成
- 三个子系统
- CPU
- ALU
- 逻辑，移位，算数运算
- 寄存器
- 数据，指令，程序计数器
- 控制单元
- ALU
- 主存
- RAM，ROM
- IO
- 存储设备
- 非存储设备
- CPU
- 主线
- CPU与主存
- 数据，指令，控制总线
- IO与主线
- 控制器（接口）
- IO寻址
- 独立寻址
- 存储器映射寻址
- CPU与主存
- 程序执行
- 机器周期
- 取指令
- 译码
- 执行
- IO操作
- 程序控制
- 中断控制
- DMA方式
- 体系结构
- CISC复杂指令集
- RISC精简指令集
- 流水线（并行）
- 机器周期
- 简单计算机（例子）
计算机网络和因特网
- 网络
- 局域网
- 广域网
- 互联网
- 因特网
- 协议分层
- 原则
- 每一层对立镜像
- 逻辑连接
- 原则
- TCP/IP协议族
- 应用层
- 传送消息
- 模式
- C/S模式
- 万维网
- URL
- HTTP
- FTP
- 电子邮件
- TELNET远程登录
- SSH安全套
- DNS
- 域名
- p2p模式
- BT下载
- 集中，分散网络
- C/S模式
- 传输层
- 传送数据包/分段
- 进程通信
- TCP
- UDP
- 网络层
- 传送数据报
- IPV4,IPV6
- 路由
- 数据链路层
- 传送帧
- LAN,WAN
- 物理层
- 位bit
- 信号转换
- 传输介质
- 应用层
操作系统
- 功能
- 有效使用硬件
- 调用资源
- 自举进入RAM
- 演化
- 批处理系统
- 分时系统
- 并行系统
- 分布式系统
- 实时系统
- 组成部分
- 用户界面
- 内存管理
- 单道程序
- 多道程序
- 分区调度
- 分页调度
- 请求分页调度
- 请求分段调度
- 请求段页式调度
- 虚拟内存
- 进程管理
- 程序，作业，进程
- 调度器
- 作业调度器
- 进程调度器
- 队列
- 作业，进程控制块
- 调度算法
- 进程同步
- 死锁
- 饿死
- 设备管理
- 文件管理
- 主流操作系统
- UNIX
- Linux
- windows
算法
- 定义
- 一组明确步骤的有序集合，有限的时间内终止并产生结果
- 三种结构
- 顺序
- 选择
- 循环
- 表示法
- UML
- 伪代码
- 结构图
- 子算法
- 基本算法
- 求和
- 乘积
- 最值
- 查找
- 顺序
- 折半
- 排序
- 选择
- 冒泡
- 插入
- 递归与迭代
程序设计语言
- 演化
- 机器语言
- 汇编语言
- 高级语言
- 翻译
- 编译
- 解释
- 过程
- 词法分析
- 语法分析
- 语义分析
- 代码生成
- 编程模式
- 过程式
- 面向对象
- 函数式
- 声明式（逻辑推理）
- 共同概念
- 数据类型
- 标识符
- 变量
- 字面值
- 常量
- 输入输出
- 表达式
- 语句
- 控制语句
- 子程序
软件工程
- 软件生命周期
- 开发
- 使用
- 修改
- 开发过程模型
- 瀑布模型
- 增量模型
- 开发阶段
- 分析阶段
- 面向过程分析
- 数据流图
- 实体关系图
- 面向对象分析
- 用例图（功能交互）
- 类图
- 状态图
- 面向过程分析
- 设计阶段
- 面向过程设计
- 结构图
- 模块化
- 高聚合低耦合
- 面向对象设计
- 详细设计类的细节
- 过程设计
- 面向过程设计
- 开发实现阶段
- 语言选择
- 软件质量
- 可操作性
- 可维护性
- 可移植性
- 测试阶段
- 白盒测试
- 基本路径测试
- 控制结构测试
- 黑盒测试
- 穷尽测试
- 随机测试
- 边界测试
- 白盒测试
- 分析阶段
- 文档
- 用户文档
- 系统文档
- 技术文档
数据结构
- 数组
- 数组名元素名
- 多维数组
- 行主序存储
- 列主序存储
- 数组操作
- 增删查改
- 记录（数据元素）
- 域（数据项）
- 链表
- 数据和链
- 链表名和节点名
- 链表操作
抽象数据类型
- 定义
- 封装数据与操作的数据类型
- 栈
- 先进后出
- 操作
- 应用
- 倒转数据
- 配对
- 数据延迟使用
- 回溯
- 实现
- 数组
- 链表
- 队列
- 先进先出
- 应用
- 排队
- 广义线性表
- 随机存取
- 有序
- 二叉树
- 树
- 遍历操作
- 深度优先
- 先序
- 中序
- 后序
- 广度优先
- 层次
- 深度优先
- 应用
- 赫夫曼编码
- 表达式树
- 二叉搜索树
- 图
文件结构
- 存取方式
- 顺序存取
- 随机存取
- 顺序文件
- 更新
- 新主文件
- 旧主文件
- 事务文件
- 错误报告文件
- 更新
- 索引文件
- 散列文件
- 散列方法
- 直接散列
- 求模法
- 数字析取法
- 其他方法
- 冲突
- 开放寻址
- 链表法
- 桶散列法
- 散列方法
- 目录
- 和索引相比，增加了权限等信息
- 特殊目录
- 根目录
- 主目录
- 工作目录
- 父目录
- 路径
- 文本文件和二进制文件
数据库
- 引言
- 平面文件系统与数据库系统对比
- 数据库管理系统
- 硬件
- 软件
- 数据
- 用户
- 最终用户
- 数据库管理员
- 普通用户
- 应用程序
- 最终用户
- 规程
- 数据库体系结构
- 内层
- 概念层
- 逻辑视图
- 外层
- 外部视图
- 数据库模型
- 层次模型
- 网状模型
- 关系模型
- 关系数据库模型
- 分布式数据库模型
- 面向对象数据库模型
- XML
- 关系数据库模型
- 关系（二维表）
- 名称
- 属性
- 元组
- 关系操作
- 插入
- 删除
- 更新
- 选择
- 投影
- 连接
- 并
- 交
- 差
- 关系（二维表）
- 数据库设计
- 需求分析
- 实体关系模型ERM
- ER图
- 实体集关系
- 关系集关系
- 规范化
- 第一范式：属性不可分割
- 2NF：主键完全依赖
- 3NF范式
- BCNF
数据压缩
- 无损压缩
- 游程长度编码
- 赫夫曼编码
- LZ编码
- 有损压缩
- 图像压缩JPEG
- 分块
- 离散余弦变换
- 量化
- 无损压缩
- 视频压缩MPEG
- 空间压缩
- JPEG
- 时间压缩
- I帧
- P帧
- B帧
- 空间压缩
- 音频压缩
- 预测编码
- 感知编码mp3
- 频率掩盖
- 时间掩盖
- 图像压缩JPEG
安全
- 引言
- 安全目标
- 机密性
- 完整性
- 可用性
- 攻击
- 针对机密性
- 嗅探
- 流量分析
- 针对完整性
- 篡改
- 假冒
- 重放
- 抵赖
- 针对可用性
- 拒绝服务（Dos攻击）
- 针对机密性
- 服务和技术
- 密码术
- 对称
- 非对称
- 散列
- 隐写术
- 密码术
- 安全目标
- 机密性
- 对称密匙密码术
- 流密码
- 分组密码
- 传统对称密匙（面向字符）
- 替换密码
- 单字母密码
- 加法密码
- 多字母密码
- 自动密匙密码
- 单字母密码
- 移位密码
- 替换密码
- 现代对称密匙（面向位）
- 现代分组密码
- 现代流密码
- 一次一密乱码
- 非对称密匙密码术
- RSA密码系统
- 对称密匙密码术
- 完整性
- 消息验证
- 消息摘要（防篡改）
- 散列函数MD5
- 身份验证（防假冒）
- 消息验证码MAC
- 密匙保证机密性
- 数字签名
- 公私匙
- 使用发送方的公私匙验证
- 消息验证码MAC
- 签署摘要
- 消息摘要（防篡改）
- 实体验证（实时性）
- 验证分类
- 所知道的
- 密码
- 所拥有的
- 身份证
- 所固有的
- 指纹
- 所知道的
- 挑战-回应
- 对称密匙
- 非对称密匙
- 数字签名
- 验证分类
- 消息验证
- 不可抵赖性
- 可信第三方中心
- 密匙管理
- 对称密匙分发
- 密匙分发中心：KDC
- 多个密匙分发中心
- 会话密匙
- 公匙分发（非对称）
- 公开声明（不安全）
- 认证机构：CA
- X.509(结构化证书)
- 对称密匙分发
- 防火墙
- 包过滤防火墙（路由器）
- 针对ip
- 针对端口
- 代理防火墙
- 代理计算机（应用网关）
- 应用层过滤
- 代理计算机（应用网关）
- 包过滤防火墙（路由器）
计算理论
- 简单语言
- 递增语句
- 递减语句
- 循环语句
- 简单语言的宏（模拟任何复杂语句）
- 图灵机
- 组成
- 磁带
- 读写头
- 控制器
- 有限状态自动机
- 模拟简单语言
- 邱奇图灵论题
- 图灵机可完成符号操作的算法
- 组成
- 停机问题
- 哥德尔数
- 程序编号
- 停机问题不可解
- 哥德尔数
- 问题复杂度
- 可解问题
- 多项式问题
- 非多项式问题
- 不可解问题
- 可解问题
人工智能
- 智能体
- 软件智能体
- 物理智能体
- 编程语言
- LISP
- PROLOG
- 知识表示
- 语义网
- 框架
- 谓词逻辑
- 命题逻辑
- 超谓词逻辑
- 基于规则的系统
- 知识库
- 事实库
- 推理机
- 专家系统
- 用户与用户界面
- 知识库与知识库编辑器
- 事实库与解释系统
- 推理机
- 感知
- 图像处理
- 边缘探测
- 分段
- 查找深度
- 查找方向
- 对象识别
- 应用
- 语言理解
- 语音识别
- 语法分析
- 文法
- 词法分析器
- 语义分析
- 语用分析
- 意图
- 消除歧义
- 图像处理
- 搜索
- 蛮力搜索
- 深度
- 广度
- 启发式搜索
- 启发值
- 蛮力搜索
- 神经网络
- 感知器模型
- 多层网络
附录B UML统一建模语言
-
用户视图
- 用户系统交互：用户与功能
- 用例图
- 系统，
- 用例（行为），
- 行动者，
- 关系
-
结构视图
- 系统静态结构：类的设计
- 类图
- 属性与方法
- 关联（类之间的关系（几对几））
- 泛化（继承关系）
-
行为视图
对象在系统中的行为-
协作图
- 对象之间的关系
- 属性和值
- 方法操作
- 链接（几对几关系）
- 消息
-
状态图
- 单个对象状态变化
- 符号
- 状态
- 转换
- 决策点
- 事件（外来自发消息）
- 动作（由事件引发）
-
顺序图
- 对象之间一段时间的交互
- 行动者
- 对象
- 生命线
- 激活
- 消息
-
活动图
- 复杂操作的详细分解流程图
- 符号
- 和状态图差不多
- 决策（分支或融合）
- 分支或连接（表示并发）
-
泳道
- 多个对象的活动
-
-
实现视图
- 显示最终产品的实现（概括）
- 组件图
- 软件组件之间的依赖关系
- 配置图
- 通信链接
附录E：布尔代数和逻辑电路
- 布尔代数
- 常量，变量，运算符
- 表达式
- 逻辑门
- 缓冲器
- AND，OR,NAND,NOR...
- 实现
- 晶体管（电子开关）
- 公理，定理，公式
- 布尔函数（表达式）
- 真值表
- 表式转换
- 积之和
- 和之积
- 函数简化
- 代数方法
- 卡诺图方法
- 逻辑电路
- 组合电路
- 半加法器
- 多路复用器
- 时序电路
- 异步
- SR双稳态多谐振荡器
- D
- JK
- T
- 同步（时钟脉冲）
- 寄存器
- 数字计数器
- 异步
- 组合电路
附录H 误差检测和校正
- 冗余
- 检测和校正
- 向前误差校正与重传
- 编码
- 块编码
- 回旋编码
- 块编码
- 数据字
- 码子
- 线性块编码
- 简单奇偶校验码
- 汉明码
- 循环码
- 循环冗余校验
- 校验和
