计算机科学与技术学科知识体系
下面是14个知识领域（area）及其中的知识单元（IInits）和知识点（topiCS ）的描述: 1 离散结构（DS）
1.1 函数、关系和集合（核心）DS1
1.1.1 函数DS11
1.1.1.1 满射
1.1.1.2 到内的映射
1.1.1.3 逆函数
1.1.1.4 复合函数
1.1.2 关系
1.1.
2.1 自反
1.1.
2.2 对称
1.1.
2.3 传递
1.1.
2.4 等价关系
1.1.3 集合
1.1.3.1 文氏图
1.1.3.2 补集
1.1.3.3 笛卡儿集
1.1.3.4 幂集
1.1.4 鸽笼原理
1.1.5 基数性和可数性
1.2 基本逻辑（核心）
1.2.1 命题逻辑
1.2.2 逻辑连接词
1.2.3 真值表
1.2.4 范式
1.2.4.1 合取式
1.2.4.2 析取式
1.2.5 永真性
1.2.6 谓词逻辑
1.2.7 全称量词和存在量词
1.2.8 假言推理、否定式推理
1.2.9 谓词逻辑的局限性
1.3 证明技巧（核心）
1.3.1 蕴涵、逆、逆反、置换、非、永假等概念
1.3.2 形式证明结构
1.3.3 直接证明
1.3.4 反例证法
1.3.5 逆反式证明法
1.3.6 反证法
1.3.7 数学归纳法
1.3.8 强归纳法
1.3.9 递归数学定义
1.3.10 良序
1.4 计数基础（核心）
1.4.1 计数变元
1.4.2 求和与相乘的规则
1.4.3 包含排斥
1.4.4 算术和几何级数
1.4.5 斐波那契（Fibonacci ）数列1.4.6 排列组合
1.4.7 基本定义
1.4.8 恒等式
1.4.9 二项式定理
1.4.10 递归关系
1.4.11 实例
1.4.12 Master 原理
1.5 图与树（核心）
1.5.1 树
1.5.2 无向图
1.5.3 有向图
1.5.4 生成树
1.5.5 遍历策略
1.6 离散概率
1.6.1 有限概率空间、概率度量、事件1.6.2 条件概率、独立性、贝叶斯规则1.6.3 整型随机变量、期望
2 程序设计基础（PF ）
2.1 程序设计基本结构（核心）
2.1.1 变量、类型、表达式和语句
2.1.2 高级语言的基本语法和语义
2.1.3 输人和输出基础
2.1.4 顺序、条件和循环控制结构
2.1.5 函数定义、函数调用和参数传递2.1.6 程序结构分解基础
2.2 算法与问题求解（核心）
2.2.1 问题求解策略
2.2.2 问题求解算法
2.2.3 算法实现策略
2.2.4 调试策略
2.2.5 算法的概念和特性
2.3 基本数据结构（核心）
2.3.1 基本类型
2.3.2 数组
2.3.3 记录
2.3.4 字符串和字符串处理
2.3.5 数据在存储器中的表示
2.3.6 静态分配、栈式分配和堆式分配2.3.7 运行时的存储器管理
2.3.8 指针和引用
2.3.9 链式结构
2.3.10 栈、队列和哈希表的实现策略2.3.11 树和图的实现策略
2.3.12 数据结构的应用和选择策略2.4 递归（核心）
2.4.1 递归的概念
2.4.2 递归数学函数
2.4.3 递归过程
2.4.5 回溯法
2.4.6 递归的实现
2.5 事件驱动程序设计（核心）
2.5.1 事件处理方法
2.5.2 事件传播
2.5.3 异常处理
3 算法与复杂性（AL ）
3.1 算法分析基础（核心）
3.1.1 复杂性上界和平均复杂性的渐近分析
3.1.2 最佳、最差和平均情况下的复杂性差异
3.1.3大0,小o, Q和B符号
3.1.4 标准复杂性类
3.1.5 性能的经验度量
3.1.6 算法时间、空间复杂性的权衡
3.1.7 用递归关系分析递归算法
3.2 算法策略（核心）
3.2.1 穷举算法
3.2.2 贪心算法
3.2.3 分治算法
3.2.4 回溯法
3.2.5 分支界限法
3.2.6 试探法
3.2.7 模式匹配和字符串／文本匹配算法
3.2.8 数值逼近算法
3.3 基本算法（核心）
3.3.1 简单数值算法
3.3.2 顺序查找算法和折半查找算法
3.3.3 二次排序算法
3.3.3.1 选择排序
3.3.3.2 插人排序
3.3.4 复杂度为0（N log N ）排序算法
3.3.
4.1 快速排序
3.3.
4.2 堆排序
3.3.
4.3 归并排序
3.3.5哈希（Hash）表，包括冲突消解策略
3.3.6 二叉查找树
3.3.7 图的表示
3.3.7.1 邻接表
3.3.7.2 邻接矩阵
3.3.8 深度优先遍历
3.3.9 广度优先遍历
3.3.10 最短路径算法（Dijkstra 和Floyd 算法〕3.3.11 传递闭包（FIoyd 算法）
3.3.12 最小生成树（Prim 算法和Kruskal 算法）3.3.13 拓扑排序
3.4 分布式算法（核心）
3.4.1 一致性和选择
3.4.2 终止探测
3.4.3 容错
3.5 可计算性理论基础（核心）
3.5.1 有限状态自动机
3.5.2 上下文无关文法
3.5.3 易解问题和难解问题
3.5.4 不可计算函数
3.5.5 停机问题
3.5.6 不可计算性的含义
3.6 复杂性类：P 类和NP 类（选修）3.6.1 P 类和NP 类的定义
3.6.2 NP 完全性
3.6.3 基本的NP 完全问题
3.6.4 归约技术
3.7 自动机理论（选修）
3.7.1 确定的有限自动机（DFA）
3.7.2 非确定的有限自动机（NFA）
3.7.3 DFA 和NFA 的等价性
3.7.4 正则表达式
3.7.5 正则表达式的泵引理
3.7.6 下推自动机（PDA ）
3.7.7 PDA 和上下文无关文法的关系
3.7.8 上下文无关文法的特性
3.7.9 图灵机
3.7.10 非确定的图灵机
3.7.11 集合和语言
3.7.12 Chomsky 文法分类
3.7.13 Church －Turing 论题
3.8 高级算法分析（选修）
3.8.1 退火算法分析
3.8.2 联机算法和脱机算法
3.8.3 随机算法
3.8.4 动态程序设计
3.8.5 组合优化
3.9 加密算法（选修）
3.9.1 密码学史回顾
3.9.2 私钥密码和密钥交换问题
3.9.3 公钥密码
3.9.4 数字签名
3.9.5 安全协议
3.9.6 应用（零知识证明，认证系统等等）3.10 几何算法（选修）
3.10.1 线段的性质和线段相交性
3.10.2 求凸包算法
3.11 并行算法（选修）
3.11.1 PRAM 模型
3.11.2 互斥读写与并发读写
3.11.3 指针跳转
3.11.4 Brent 定理和工作效率
4 计算机组织与体系结构（AR）
4.1 数字逻辑与数字系统（核心）
4.1.1 计算机发展历史回顾
4.1.2 基本的组成元件（逻辑门，触发器，计数器，寄存器，PLA ）
4.1.3 逻辑表达式，最小化，寄存器传输的表示，物理特性（门延迟，扇入，扇出）4.1.4 计算机的基本组成，硬件结构，软件的概念，计算机语言及其编译
4.1.5 计算机系统结构的概念，性能评价
4.2 数据的机器级表示（核心）
4.2.1 数值表示和数制
4.2.2 定点数和浮点数系统
4.2.3 有符号数的表示方法和基本运算方法
4.2.4 非数值数据的表示（如字符代码和图象数据）
4.2.5 系统可靠性与纠错码
4.2.6 数据运算器的结构
4.3 汇编级机器组织（核心）
4.3.1 指令格式
4.3.2 数据的存储方式与寻址方式
4.3.3 指令集及其分类（数据操作，控制，输入输出）
4.3.4 子程序调用和返回机制
4.3.5 汇编语言和机器语言编程基础
4.4 存储系统组织和结构（核心）
4.4.1 存储器件类型及其工作原理
4.4.2 主存储器的组织和操作
4.4.3 存储器的延迟，工作周期，带宽提高和交叉存储技术
4.4.4 层次化存储系统
4.4.5 高速缓冲存储器（地址映射，块大小，替换和更新机制）
4.4.6 虚拟存储器（页表，TLB 快表）
4.5 接口和通信（核心）
4.5.1 输人输出基本原理，信号交换，缓冲存储
4.5.2程序控制I/ 0,中断驱动I /O , DMA
4.5.3 中断结构，向量化和优先级化，中断识别
4.5.4 外部存储器的物理组织及驱动
4.5.5 总线和总线协议,仲裁机构和直接存储器存取（DMA）
4.5.6 多媒体支持
4.5.7 RAID 系统结构
4.6 功能组织（核心）
4.6.1 简单的数据通路实现
4.6.2 控制单元,硬连线实现和微程序实现
4.6.3 指令读取、解码和执行
4.6.4 异常与中断
4.6.5 指令流水技术，指令级并行（ILP ）技术与循环级并行技术
4.7 多处理和其他系统结构（核心）
4.7.1 SIMD ，MIMD ，VLIW 和EPIC
4.7.2 网络互联（超立方体，混洗交换，网格结构，交叉开关结构）
4.7.3 共享存储系统
4.7.4 cache 一致性
4.7.5 存储模型和存储一致性
4.8 性能提高技术（选修）
4.8.1 超标量体系结构
4.8.2 分支预测
4.8.3 指令预取
4.8.4 推测执行
4.8.5 多线程
4.9 网络与分布式系统结构（选修）
4.9.1 LAN 与WAN
4.9.2 网络的分层协议
4.9.3 分布式算法对系统结构的影响
4.9.4 网络计算
4.9.5 分布式多媒体
5 操作系统（OS）
5.1 操作系统概述（核心）
5.1.1 操作系统的作用和目的
5.1.2 操作系统的发展历史
5.1.3 操作系统的特征和功能
5.1.4 支持客户——服务器模型和手提设备的机制
5.1.5 有关有效性、健壮性、灵活性、可移植性、安全性、兼容性的设计问题5.1.6 安全性、网络化、多媒体、视窗所带来的影响
5.2 操作系统原理（核心）
5.2.1 结构化方法（整体的、分层的、模块化的、微内核模型）
5.2.2 抽象、进程、资源
5.2.3 应用程序接口（API ）的基本概念
5.2.4 应用的需求以及软、硬件技术的发展
5.2.5 设备的组织
5.2.6 中断的方法和实现
5.2.7 用户系统状态及其保护，以及用户／系统状态转换到核心态的原理
5.3 并发性（核心）
5.3.1 状态和状态图
5.3.2 就绪队列、进程控制块等的结构
5.3.3 调度和状态转换
5.3.4 中断的作用
5.3.5 并发执行的优点和缺点
5.3.6 互斥问题和一些解决的方法
5.3.7 死锁的产生、条件及其预防措施
5.3.8 信号量、监控、条件变量、聚集的模型和机制
5.3.9 生产者——消费者问题和同步
5.3.10 多处理器自旋锁定和重入的问题
5.4 调度与分派（核心）
5.4.1 抢占和非抢占调度
5.4.2 调度和策略
5.4.3 进程和线程
5.4.4 里程碑和实时问题
5.5 内存管理（核心）
5.5.1 物理内存和内存管理硬件的回顾
5.5.2 覆盖、交换、分区
5.5.3 内存分页和分段
5.5.4 分配和淘汰策略
5.5.5 工作集和系统颠簸
5.5.6 高速缓存
5.6 设备管理（核心）
5.6.1 串行和并行设备的特点
5.6.2 设备的分类
5.6.3 缓冲策略
5.6.4 直接存储器访问（DMA ）
5.6.5 故障恢复
5.7 安全与保护（核心）
5.7.1 系统安全概论
5.7.2 策略／机制分离
5.7.3 安全方法和设备
5.7.4 保护、访问、身份验证
5.7.5 保护模型
5.7.6 内存保护
5.7.7 加密技术
5.7.8 恢复管理
5.8 文件系统（核心）
5.8.1 文件中的数据和元数据，文件的操作、组织及缓冲，顺序文件和非顺序文件5.8.2 目录的内容和结构
5.8.3 文件系统（磁盘分区、文件的安装／卸载、虚拟文件系统）
5.8.4 标准的实现技术
5.8.5 内存映像文件
5.8.6 特定用途的文件系统
5.8.7 文件的命名、搜索、访问、备份
5.9 实时和嵌入式系统（选修）
5.9.1 进程和任务调度
5.9.2 实时环境中内存／硬盘管理所需要的条件
5.9.3 故障、风险、恢复
5.9.4 实时系统中需考虑的特殊问题
5.10 容错（选修）
5.10.1 基本概念（可靠性和可用性系统）
5.10.2 空间和时间冗余
5.10.3 实现容错的方法
5.10.4 可靠系统的实例
5.11 系统性能评价（选修）
5.11.1 系统性能评价的意义
5.11.3 高速缓存、内存分页、调度安排、内存管理、安全等策略
5.11.4 确定型的、分析型的、仿真型的、具体实现型的评估模型
5.11.5 收集评估数据的方法（剖析和追踪机制）
5.12 脚本（选修）
5.12.1 脚本和脚本语言的作用