计算机科学知识体计算机科学与技术方法论附录.docVIP

CS（计算机科学）知识体 计算教程2001报告的这篇附录定义了计算机科学本科教学计划中可能讲授的知识领域。该分类方案的依据及其历史、结构和应用的其它细节包含在完整的任务组报告中。由于我们希望附录比完整的报告有更多的读者，所以任务组认为在每一篇附录中概述理解该推荐所必须的基本概念是重要的。在下面几节中我们列出了最重要的几个概念。 知识体的结构 计算机科学知识体分层组织成三个层次。最高一层是领域（area），代表一个特定的学科子领域。每个领域由一个两个字母的缩写词表示，比如OS代表操作系统，PL代表程序设计语言，领域之下又被分割成更小的单元（units），代表领域中单独的主题模块。每个单元都用一个领域名加一个数字后缀表示，比如OS3是关于并发的单元。各个单元由被细分成主题（topics），这是CS知识体层次结构的最底层。 离散结构（DS） DS1. 函数,关系,集合[核心] DS2. 基本逻辑[核心] DS3. 证明技术[核心] DS4. 计算基础[核心] DS5. 图和树[核心] DS6. 离散概率[核心] DS1.函数、关系、集合论[核心] 主题： 函数 （） （） （） 基数和可数性 学习目标： 举例说明基本术语：函数、关系和集合。 执行与函数、关系和集合相关的运算。 把实例与适当的集合、函数或关系模型相联系，并在上下文中解释相关的操作和术语。 解释基本的计算原理，包括对角化和鸽洞原理的应用。 DS2. 基本逻辑 （） 逻辑联结词 真值表 范式（合取与析取范式） 永真性 谓词逻辑 全称量词和存在量词 假言推理和否定后件推理（modus tallens） 谓词逻辑的局限性 学习目标： 应用符号命题逻辑和谓词逻辑的形式化方法。 描述如何使用符号逻辑的形式化工具为算法和真实情形建模。 使用形式逻辑证明和逻辑推理来解决诸如迷宫等问题。 描述谓词逻辑的重要性和局限性。 DS3. 证明技术 （） 形式证明的结构 直接证法 反例证法 通过逆否命题证明 归谬证法 数学归纳 完全归纳 递归数学定义 良序 学习目标： 概述本单元中给出的每一种证明技术的基本结构并给出相应的实例。 讨论对于指定的问题哪种类型的证明是最优的。 把数学归纳思想与递归和递归定义的结构联系起来。 说明数学归纳和完全归纳的差别并举例说明如何合理地使用它们。 DS4.计算基础 （） Fibonacci）数列 鸽洞原理 排列和组合 ——基本定义 ——Pascal 恒等式 ——二项式定理 求解递推关系式 ——常见实例 ——Master定理 学习目标： 计算一个集合的排列和组合，并解释在特定应用环境中的意义。 阐述Master定理的定义。 计算各种不同的递推式。 分析问题，产生相应的递推式或识别重要的计算问题 DS5. 图和树 （） 无向图 有向图 生成树 遍历策略 学习目标： 通过例子说明图论的基本术语，各自的性质和特殊情况。 说明树和图的不同遍历方法。 使用图和树为计算机科学中的问题建模。 把图和树与数据结构、算法和计算相联系。 DS6.离散概率[核心] 主题： 有限概率空间、概率的度量、事件 条件概率、独立性、贝叶斯定律 整型随机变量、期望 学习目标： 对基本问题，如机会游戏（games of chance）计算事件概率和随机变量的期望。 区别独立事件和非独立事件。 对非独立事件应用二项式定理，对独立事件应用Bayes定理。 应用概率工具如Monte Carlo方法、算法的平均情况分析和散列法来解决问题。 程序设计基础（PF） PF1.基本程序设计结构[核心] PF2.算法和问题求解[核心] PF3. 基本的数据结构[核心] PF4. 递归[核心] PF5. 事件驱动的程序设计[核心] PF1.基本程序设计结构[核心] 主题： 高级语言的基本语法和语义 变量、类型、表达式和赋值 简单I/O 条件和循环控制结构 函数和参数传递 结构化分解 学习目标： 分析并解释具有本单元所涉及基本程序结构的简单程序的行为。 修改和扩展使用了标准条件和循环控制结构和函数的小程序。 设计、实现、测试和调试一个使用下面每一种基本程序设计结构的程序： 基本计算、简单的输入/输出、标准的条件和循环结构以及函数定义。 对于指定的程序设计任务，选择适当的条件和循环结构。 运用结构化（功能）分解技术把一个程序分解成一些小的程序块。 描述参数传递的机制。 PF2.算法和问题求解[核心] 主题： 问题求解策略 算法在问题求解过程中的作用 算法的实现策略 调试策略 算法的概念和性质 学习目标： 讨论算法在问题求解过程中的重要性。 指出好的算法所必备的性质。 开发求解简单问题的算法。 使用伪代码或程序设计语言