计算机科学与技术学科知识体系.pdf

计算机科学与技术学科知识体系 下面是 14 个知识领域（ area）及其中的知识单元（ llnits ）和知识点（ topiCS ）的描述： 1 离散结构（ DS） 1.1 函数、关系和集合（核心） DS1 1.1.1 函数 DS11 满射 到内的映射 逆函数 复合函数 1.1.2 关系 自反 对称 传递 等价关系 1.1.3 集合 文氏图 补集 笛卡儿集 幂集 1.1.4 鸽笼原理 1.1.5 基数性和可数性 1.2 基本逻辑（核心） 1.2.1 命题逻辑 1.2.2 逻辑连接词 1.2.3 真值表 1.2.4 范式 合取式 析取式 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 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 2.3.12 数据结构的应用和选择策略 2.4 递归（核心） 2.4.1 递归的概念 2.4.2 递归数学函数 2.4.3 递归过程 2.4.4 分治法 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 大 O ，小 o， Ω和 θ符号 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 模式匹配和字符串／文本