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

《计算机科学知识体-计算机科学与技术方法论附录》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、CS（计算机科学）知识体计算教程2001报告的这篇附录定义了计算机科学本科教学计划中可能讲授的知识领域。该分类方案的依据及其历史、结构和应用的其它细节包含在完整的任务组报告中。由于我们希望附录比完整的报告有更多的读者，所以任务组认为在每一篇附录中概述理解该推荐所必须的基本概念是重要的。在下面几节中我们列出了最重要的几个概念。知识体的结构计算机科学知识体分层组织成三个层次。最高一层是领域（area），代表一个特定的学科子领域。每个领域由一个两个字母的缩写词表示，比如OS代表操作系统，PL代表程序设计语言，领域之下又被分割成更小的单元（units），代表领域中单独的主题模块。每个单元都

2、用一个领域名加一个数字后缀表示，比如OS3是关于并发的单元。各个单元由被细分成主题（topics），这是CS知识体层次结构的最底层。离散结构（DS）DS1.函数,关系,集合[核心]DS2.基本逻辑[核心]DS3.证明技术[核心]DS4.计算基础[核心]DS5.图和树[核心]DS6.离散概率[核心]DS1.函数、关系、集合论[核心]主题：函数（满射、入射、逆、复合）关系（自反、对称、传递、等价关系）集合（文氏图、补集、笛卡尔积、幂集）鸽洞原理基数和可数性学习目标：1．举例说明基本术语：函数、关系和集合。2．执行与函数、关系和集合相关的运算。3．把实例与适当的集合、函数或关系模型相联系

3、，并在上下文中解释相关的操作和术语。4．解释基本的计算原理，包括对角化和鸽洞原理的应用。DS2.基本逻辑（核心）主题：命题逻辑逻辑联结词真值表范式（合取与析取范式）永真性57谓词逻辑全称量词和存在量词假言推理和否定后件推理（modustallens）谓词逻辑的局限性学习目标：1．应用符号命题逻辑和谓词逻辑的形式化方法。2．描述如何使用符号逻辑的形式化工具为算法和真实情形建模。3．使用形式逻辑证明和逻辑推理来解决诸如迷宫等问题。4．描述谓词逻辑的重要性和局限性。DS3.证明技术（核心）主题：蕴含、逆、补、逆否、否定、矛盾形式证明的结构直接证法反例证法通过逆否命题证明归谬证法数学归纳完

4、全归纳递归数学定义良序学习目标：1．概述本单元中给出的每一种证明技术的基本结构并给出相应的实例。2．讨论对于指定的问题哪种类型的证明是最优的。3．把数学归纳思想与递归和递归定义的结构联系起来。4．说明数学归纳和完全归纳的差别并举例说明如何合理地使用它们。DS4.计算基础（核心）主题：计数理论（countingarguments）——和积规则（sumandproductionrules）——包含排斥原理——算术和几何级数——斐波纳契（Fibonacci）数列鸽洞原理排列和组合——基本定义——Pascal恒等式——二项式定理求解递推关系式——常见实例57——Master定理学习目标：1

5、．计算一个集合的排列和组合，并解释在特定应用环境中的意义。2．阐述Master定理的定义。3．计算各种不同的递推式。4．分析问题，产生相应的递推式或识别重要的计算问题DS5.图和树（核心）主题：树无向图有向图生成树遍历策略学习目标：1．通过例子说明图论的基本术语，各自的性质和特殊情况。2．说明树和图的不同遍历方法。3．使用图和树为计算机科学中的问题建模。4．把图和树与数据结构、算法和计算相联系。DS6.离散概率[核心]主题：有限概率空间、概率的度量、事件条件概率、独立性、贝叶斯定律整型随机变量、期望学习目标：1．对基本问题，如机会游戏（gamesofchance）计算事件概率和随机

6、变量的期望。2．区别独立事件和非独立事件。3．对非独立事件应用二项式定理，对独立事件应用Bayes定理。4．应用概率工具如MonteCarlo方法、算法的平均情况分析和散列法来解决问题。程序设计基础（PF）PF1.基本程序设计结构[核心]PF2.算法和问题求解[核心]PF3.基本的数据结构[核心]PF4.递归[核心]PF5.事件驱动的程序设计[核心]PF1.基本程序设计结构[核心]主题：高级语言的基本语法和语义57变量、类型、表达式和赋值简单I/O条件和循环控制结构函数和参数传递结构化分解学习目标：1.分析并解释具有本单元所涉及基本程序结构的简单程序的行为。2.修改和扩展使用了标准

7、条件和循环控制结构和函数的小程序。3.设计、实现、测试和调试一个使用下面每一种基本程序设计结构的程序：基本计算、简单的输入/输出、标准的条件和循环结构以及函数定义。4.对于指定的程序设计任务，选择适当的条件和循环结构。5.运用结构化（功能）分解技术把一个程序分解成一些小的程序块。6.描述参数传递的机制。PF2.算法和问题求解[核心]主题：问题求解策略算法在问题求解过程中的作用算法的实现策略调试策略算法的概念和性质学习目标：1.讨论算法在问题求解过程中的重要性。2.指出