《计算机科学与技术学科知识体系.doc》由会员分享，可在线阅读，更多相关《计算机科学与技术学科知识体系.doc（23页珍藏版）》请在金锄头文库上搜索。
1、计算机科学与技术学科知识体系 下面是14个知识领域（ area）及其中的知识单元（llnits）和知识点（topiCS）的描述：1离散结构（DS）1.1函数、关系和集合（核心）DS11.1.1函数DS111.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范
2、式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恒
3、等式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问题求解策略
4、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.4分治法2.4.5回溯法2.4.6递归的实现2.5事件驱动程序设计（核心）2.5.1事件处
5、理方法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模式匹配和字符串文本匹配算法3.2.8数值逼近算法3.3基本算法（核心）3.3.1简单数值算法3.3.2顺序查找算法和折半查找算法3.3.3二次
6、排序算法3.3.3.1选择排序3.3.3.2插人排序3.3.4复杂度为 O（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.4.4稳
7、定性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
8、图灵机3.7.10非确定的图灵机3.7.11集合和语言3.7.12 Chomsky文法分类3.7.13 ChurchTuring论题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
9、.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系统可靠性与纠错码
10、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程序控制 IO，中断
11、驱动 IO，DMA4.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和 EPIC4.7.2网络互联（超立方体，混洗交换，网格结构，交叉开关结构）4.7.3共享存储系统4.7.4
12、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与 WAN4.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安全性、网络化
13、、多媒体、视窗所带来的影响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信号量、监控、条件变量、聚集的
14、模型和机制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文件系统（磁盘分区、文件的安装卸载、虚拟文件系统
