《计算机科学知识体-计算机科学与技术方法论附录》由会员分享，可在线阅读，更多相关《计算机科学知识体-计算机科学与技术方法论附录（57页珍藏版）》请在金锄头文库上搜索。
1、1CS（计算机科学）知识体（计算机科学）知识体计算教程 2001 报告的这篇附录定义了计算机科学本科教学计划中可能讲授的知识领域。该 分类方案的依据及其历史、结构和应用的其它细节包含在完整的任务组报告中。由于我们 希望附录比完整的报告有更多的读者，所以任务组认为在每一篇附录中概述理解该推荐所 必须的基本概念是重要的。在下面几节中我们列出了最重要的几个概念。知识体的结构知识体的结构 计算机科学知识体分层组织成三个层次。最高一层是领域（area） ，代表一个特定的学科子 领域。每个领域由一个两个字母的缩写词表示，比如 OS 代表操作系统，PL 代表程序设计 语言，领域之下又被分割成更小的单元（un
2、its） ，代表领域中单独的主题模块。每个单元都 用一个领域名加一个数字后缀表示，比如 OS3 是关于并发的单元。各个单元由被细分成主 题（topics） ，这是 CS 知识体层次结构的最底层。离散结构（离散结构（DS） DS1. 函数函数, ,关系关系, ,集合集合 核心核心 DS2. 基本逻辑基本逻辑 核心核心 DS3. 证明技术证明技术 核心核心 DS4. 计算基础计算基础 核心核心 DS5. 图和树图和树 核心核心 DS6. 离散概率离散概率 核心核心 DS1.DS1.函数、关系、集合论函数、关系、集合论 核心核心 主题： 函数 （满射、入射、逆、复合） 关系 （自反、对称、传递、等价
3、关系） 集合 （文氏图、补集、笛卡尔积、幂集） 鸽洞原理 基数和可数性学习目标： 1 举例说明基本术语：函数、关系和集合。 2 执行与函数、关系和集合相关的运算。 3 把实例与适当的集合、函数或关系模型相联系，并在上下文中解释相关的操作和术语。4 解释基本的计算原理，包括对角化和鸽洞原理的应用。DS2.DS2. 基本逻辑基本逻辑 （核心）（核心） 主题： 命题逻辑 逻辑联结词 真值表 范式（合取与析取范式）2永真性 谓词逻辑 全称量词和存在量词 假言推理和否定后件推理（modus tallens） 谓词逻辑的局限性学习目标： 1 应用符号命题逻辑和谓词逻辑的形式化方法。 2 描述如何使用符号逻
4、辑的形式化工具为算法和真实情形建模。 3 使用形式逻辑证明和逻辑推理来解决诸如迷宫等问题。 4 描述谓词逻辑的重要性和局限性。DS3.DS3. 证明技术证明技术 （核心）（核心） 主题： 蕴含、逆、补、逆否、否定、矛盾 形式证明的结构 直接证法 反例证法 通过逆否命题证明 归谬证法 数学归纳 完全归纳 递归数学定义 良序学习目标： 1 概述本单元中给出的每一种证明技术的基本结构并给出相应的实例。 2 讨论对于指定的问题哪种类型的证明是最优的。 3 把数学归纳思想与递归和递归定义的结构联系起来。 4 说明数学归纳和完全归纳的差别并举例说明如何合理地使用它们。DS4.DS4.计算基础计算基础 （核
5、心）（核心） 主题： 计数理论（counting arguments） 和积规则（sum and production rules） 包含排斥原理 算术和几何级数 斐波纳契（Fibonacci）数列 鸽洞原理 排列和组合 基本定义 Pascal 恒等式 二项式定理 求解递推关系式3常见实例 Master定理学习目标： 1 计算一个集合的排列和组合，并解释在特定应用环境中的意义。 2 阐述Master定理的定义。 3 计算各种不同的递推式。 4 分析问题，产生相应的递推式或识别重要的计算问题DS5.DS5. 图和树图和树 （核心）（核心） 主题： 树 无向图 有向图 生成树 遍历策略学习目标：
6、1 通过例子说明图论的基本术语，各自的性质和特殊情况。 2 说明树和图的不同遍历方法。 3 使用图和树为计算机科学中的问题建模。 4 把图和树与数据结构、算法和计算相联系。DS6.DS6.离散概率离散概率 核心核心 主题： 有限概率空间、概率的度量、事件 条件概率、独立性、贝叶斯定律 整型随机变量、期望学习目标： 1 对基本问题，如机会游戏（games of chance）计算事件概率和随机变量的期望。 2 区别独立事件和非独立事件。 3 对非独立事件应用二项式定理，对独立事件应用Bayes定理。 4 应用概率工具如Monte Carlo方法、算法的平均情况分析和散列法来解决问题。程序设计基础
7、（程序设计基础（PFPF） PF1.PF1.基本程序设计结构基本程序设计结构 核心核心 PF2.PF2.算法和问题求解算法和问题求解 核心核心 PF3.PF3. 基本的数据结构基本的数据结构 核心核心 PF4.PF4. 递归递归 核心核心 PF5.PF5. 事件驱动的程序设计事件驱动的程序设计 核心核心 PF1.PF1.基本程序设计结构基本程序设计结构 核心核心 主题：4高级语言的基本语法和语义 变量、类型、表达式和赋值 简单I/O 条件和循环控制结构 函数和参数传递 结构化分解学习目标： 1. 分析并解释具有本单元所涉及基本程序结构的简单程序的行为。 2.修改和扩展使用了标准条件和循环控制结
8、构和函数的小程序。 3. 设计、实现、测试和调试一个使用下面每一种基本程序设计结构的程序： 基本计算、 简单的输入/输出、标准的条件和循环结构以及函数定义。 4.对于指定的程序设计任务，选择适当的条件和循环结构。 5.运用结构化（功能）分解技术把一个程序分解成一些小的程序块。 6.描述参数传递的机制。PF2.PF2.算法和问题求解算法和问题求解 核心核心 主题： 问题求解策略 算法在问题求解过程中的作用 算法的实现策略 调试策略 算法的概念和性质学习目标： 1. 讨论算法在问题求解过程中的重要性。 2. 指出好的算法所必备的性质。 3. 开发求解简单问题的算法。 4. 使用伪代码或程序设计语言
9、实现、测试和调试求解简单问题的算法。 5. 描述调试中的实用策略。PF3.PF3.基本的数据结构基本的数据结构 核心核心 主题： 原语类型 数组 记录 字符串和字符串处理 数据在内存中的表示 静态、栈和堆分配 运行时间存储管理 指针和引用 链接结构 栈、队列和哈希表的实现策略 图和树的实现策略5选择正确数据结构的策略学习目标： 1. 讨论简单（primitive）数据类型和内置数据结构的表示和使用。 2. 描述主题列表中的数据结构在内存中是如何分配和使用的。 3. 描述主题列表中各数据结构常见的应用。 4. 用高级语言实现用户自定义的数据结构。 5. 比较数据结构的不同实现的性能。 6. 编写
10、使用以下各种数据结构的程序：数组、记录、字符串、链表、栈、队列和哈希表。 7. 比较并说明动态和静态数据结构实现的代价和收益的不同。 8. 为指定问题的建模选择适当的数据结构。PF4.PF4.递归递归 核心核心 主题： 递归的概念 递归数学函数 简单的递归过程 分而治之策略 递归回溯 递归的实现学习目标： 1. 描述递归的概念并举例说明其应用。 2. 鉴别递归定义问题的基本情况和一般情况。 3. 比较基本问题如阶乘的迭代和递归求解方案。 4. 描述分而治之方法的方法。 5. 实现、测试和调试简单的递归函数和过程。 6. 描述怎么能够使用栈实现递归。 7. 讨论适合用回溯方法求解的问题。 8.
11、对于一个问题确定什么时候用递归方法求解是合适的。PF5.PF5.事件驱动程序设计事件驱动程序设计 核心核心 主题： 事件处理方法 事件传播 异常处理学习目标： 1. 解释事件驱动程序设计和命令行程序设计的不同。 2. 设计、编码、测试和调试简单的响应用户事件的事件驱动程序。 3. 编写响应执行期间异常情况的代码。算法和复杂性算法和复杂性（ALAL） AL1.AL1.基本算法分析基本算法分析 核心核心 6AL2.AL2.算法策略算法策略 核心核心 AL3.AL3.基本的计算算法基本的计算算法 核心核心 AL4.AL4.分布式算法分布式算法 核心核心 AL5.AL5.基本基本可计算行可计算行 核心
12、核心 AL6.AL6. P P和和NPNP复杂类复杂类 选修选修 AL7.AL7.自动机理论自动机理论 选修选修 AL8.AL8.高级算法的分析高级算法的分析 选修选修 AL9.AL9.密码算法密码算法 选修选修 AL10.AL10.几何算法几何算法 选修选修 AL11.AL11.并行算法并行算法 选修选修 AL1.AL1.基本算法的分析基本算法的分析 核心核心 主题： 复杂度的上界和平均值近似分析 区分最好、平均和最坏情况下行为的不同 大 “O”、小 “o”、和表示法 标准复杂类 性能的实验测量 算法的时间和空间折衷 使用循环关系分析递归算法学习目标： 1. 解释如何使用大“O”、和描述算法
13、的工作量。 2.使用大“O”、和表示法给出算法时间和空间复杂度的近似上界、下界和精确界 限。 3.确定简单算法的时间复杂度。 4.推导描述递归定义算法时间复杂度的递归关系式。 5.解决简单的递归关系式。AL2.AL2.算法策略算法策略 核心核心 主题： 蛮力算法 贪婪算法 分而治之 回溯 分支界限 启发式 模式匹配和字符串/文本算法 数值逼近算法学习目标： 1 明蛮力算法的缺点。 2 对下面的每一种算法（蛮力、贪婪、分而治之、回溯、分支有界和启发） ，举出一个人 们的日常行为实例解释该基本概念。73 实现一个贪婪算法，求解适当的问题。 4 实现一个分而治之算法，求解适当的问题。 5 使用回溯解
14、决问题，比如迷宫。 6 描述各种不同的启发式问题求解方法。 7 使用模式匹配分析子串。 8 使用数值逼近解决数学问题，如寻找多项式的根。AL3.AL3.基本的计算算法基本的计算算法 核心核心 主题： 简单的数值处理算法 顺序和二分查找算法 二次排序算法 （选择, 插入） O（N log N） 排序算法 （快速排序, 堆分类排序, 归并排序） 哈希表, 包括避免冲突的策略 二分查找树 图的表示 （邻接表，邻接矩阵） 深度和广度优先遍历 最短路径算法 （Dijkstra算法和Floyd算法） 传递闭包 （Floyd算法） 最小生成树 （Prim算法和Kruskal算法） 拓扑排序学习目标： 1.
15、实现一个最常见的二次排序算法和O（N log N） 排序算法。 2. 为应用设计并实现一个适当的哈希函数。 3. 设计并实现一个哈希表的冲突消解算法。 4. 讨论主要的排序、搜索和哈希算法的计算效率。 5. 讨论除计算效率之外影响算法选择的因素，如程序设计时间、可维护性以及在输入数 据中使用某应用特定的模式。 6. 使用基本的图算法解决问题，这些算法包括：深度和广度优先搜索算法、单源 （single-source）和每一对顶点间的（all-pairs）最短路径算法、传递闭包算法、拓扑 排序算法和至少一种最小生成树算法。 7. 具有以下能力：评价算法、从可能的选项中选择可能的算法、给出做出选择的原因并 在某程序设计环境中实现该算法。AL4.AL4.分布式算法分布式算法 核心核心 主题： 一致性与选择 终结检测 容错 稳定性学习目标： 1.解释分布式模式（paradigm）。82.解释一个简单的分布式算法。 3.确定何时使用一致性与选择算法。 2.区别逻辑和物理时钟。 3.描述事件的相对次序。AL5.AL5.基本可计算性理论基本可计算性理论 核心核心 主题： 有限状态机 上下文无关语法 易处理和不易处理的问题 不可计算函数 停机问题 不可计算性的意义学习目标： 1.讨论有限状态机的概念。 2
