南京大学软件工程学科的知识体系

南京大学软件工程学科的知识体系1南京大学软件工程学科教程——附件一软件工程学科的知识体系（南京大学软件学院2006年3月）1引言1.1目标本文论述复合型软件实用人才所应具备的知识体系，以作为南京大学软件学院学科与专业规划、人才培养方案制定、课程设置、教学计划安排、课程教学内容确定的基本依据。1.2本文结构第一章为引言。第二章介绍知识体系分类。第三章起详细介绍各知识体系分类。1.3相关报告南京大学软件学院人才培养方案，课程设置与教学计划，课程教学大纲。1.4本知识体系依据的参考文献来源本文主要依据IEEECC2004的五个学科CCSE、CCCS、CCCE、CCIT和CCIS的文件，以及南京大学软件学院的研究报告。2培养目标、规格和知识体系分类2.1培养目标南京大学软件学院旨在培养具有国际竞争能力的多层次复合型软件实用人才。2.2培养规格人才培养的基本要求是：政治合格，思想品德好，达到基本的数学和语言要求，具备科学的世界观，掌握科学方法，具有扎实的软件基础，受到良好的软件工程训练，熟悉软件应用和工具，拥有较好的沟通技巧和团队工作能力，通晓和遵守相关的法律和职业道德。南京大学软件工程学科的知识体系2人才还应具备以下的一般特征：z对软件系统、计算机系统、信息系统乃至与计算机软件相关的社会系统具有系统级的认识能力；z有扎实的理论基础，能够全面通晓计算机软件和软件工程的基础知识，较深入理解一个以上的计算机软件应用领域；z有较强的动手能力，能够具有一定的系统分析和软件设计的能力，熟练使用两种以上主流的操作系统、数据库管理系统和程序设计语言，做到理论与实践相结合；z能够合理认知软件科学与技术中的重复概念；z有实际项目的工作经验；z具备自学习的能力以适应软件技术的快速变化，能够通过自学的方式在较短时间内掌握系统软件的使用；z具备综合应用各类方法、技术和工具，运用工程方法解决复杂性软件问题的能力；z具备语言、交流、写作等基本的软件从业能力，认同现行的法律、道德和伦理。2.3知识体系分类本节对软件工程专业毕业生的知识体系进行分类：z基本素质BAS：依据中国教育部要求所应具备的政治、数学和外国语知识；z计算机软件基础CSE：从事计算机软件工作所应具备的软件专业基础知识；z软件工程SE：软件工程知识；z数学、工程和职业基础MEP：从事计算机软件工作所应具备的数学、工程和职业知识；z软件系统与应用SSA：从事某一方面计算机软件工作应具备的专业或领域应用知识；z软件工具与产品STP：从事计算机软件工作所应掌握的当前主流软件工具与软件产品。知识体系分类详见下图。第一个知识体系分类详见教育部和学校有关要求，本文后面部分将详细探讨后面5个知识体系分类。计算机软件基础CSE基本素质BAS软件工程SE软件系统与应用SSA：系统软件|嵌入式|信息技术|网络|…数学工程职业基础MEP软件工具软件产品STP南京大学软件工程学科的知识体系33计算机软件基础CSE(ComputerSoftwareEssentials)3.1离散数学基础CSE.DS(DiscreteStructures,CCCS-DS)CSE.DS1.函数，关系和集合z函数(满射，到内的映射，逆函数，复合函数)z关系(自反，对称，传递，等价关系)z集合(维恩图,补集,笛卡儿集,幂集)z鸽笼原理z基数性和可数性CSE.DS2.逻辑基础z命题逻辑z逻辑连接词z真值表z范式（合取式，析取式）z永真性z谓词逻辑z全称量词和存在量词z假言推理和否定性推理z谓词逻辑的局限性CSE.DS3.证明技术z蕴涵，逆，逆反，置换，非，永假z形式证明结构z直接证明z反例证明z逆反式证明z反证法z数学归纳法z强归纳法z递归数学定义z良序CSE.DS4.计数基础z计数变元„求和与相乘的规则南京大学软件工程学科的知识体系4„包含排斥原理„算术和几何级数„Fibonacci数列z排列和组合„基本定义„恒等式„二项式定理z递归关系„一般实例„Master定理CSE.DS5.图和树z树z无向图z有向图z生成树z遍历策略CSE.DS6.离散概率z有限概率空间，概率测量，事件z条件概率，独立事件，贝叶斯规则z整型随机变量，期望CSE.DS7.其它z有限状态机，正则表达式z语法z数值精度，精确性和误差z数论z代数结构3.2程序设计与算法基础CSE.PF(ProgrammingFundamentals,CCCS-PF)CSE.PF1.面向机器的程序设计基础z数值表示与数制z定点数与浮点数z有符号数的表示方法（原码与补码）z非数值数据的表示方法（字符、图像等）南京大学软件工程学科的知识体系5z指令格式z数据存储方式与寻址方式z指令集及其分类（数据操作，控制，输入输出）z子程序调用与返回机制z汇编语言与机器语言编程基础CSE.PF2.结构化程序设计基础Fundamentalprogrammingconstructsz高级语言的基本语法和语义z变量、类型、表达式与赋值z数据类型：原子类型、数组类型、记录类型z基本语句：顺序、条件和循环控制结构z简单输入输出z函数定义、函数调用和参数传递z指针与引用、链接结构z字符串与字符串处理z内存的数据表示z结构化程序设计与程序结构分解CSE.PF3.递归z递归的概念z递归数学函数z简单递归过程z分而治之策略z回溯法z递归的实现CSE.PF4.声明与类型z类型的概念（值的集合及其施于其上的操作的集合）z变量声明(绑定，可见，作用域，生存期)z类型检查z垃圾回收CSE.PF5.抽象机制z过程，函数，迭代作为抽象机制z参数机制(引用与值)z活动记录与内存管理z类型参数和参数化类型z模块南京大学软件工程学科的知识体系6CSE.PF6.面向对象程序设计z面向对象程序设计z封装与信息隐蔽z行为和实现的分离z类与子类z继承(重载，动态分派)z多形性(多形性与继承)z类层次z类的收集与重用z聚集类及其迭代CSE.PF7.事件驱动的程序设计z事件处理方法z事件的传播z异常处理CSE.PF8.算法和问题求解z问题求解策略z算法在问题求解过程中的角色z算法实现策略„穷举算法„贪心算法„分而治之算法„回溯法„分支界限法„试探法„模式匹配与字符串/正文算法„数值近似算法z调试策略z算法的概念与特性CSE.PF9.基本数据结构z数据在存储器中的表示z静态分配，栈和堆的静态分配z运行时间存储管理z顺序结构与链式结构z栈、队、哈希表的实现策略南京大学软件工程学科的知识体系7z字符串与字符串处理z图与树的实现策略z选择正确数据结构的策略CSE.PF10.基本计算算法z简单数值算法z顺序和折半查找算法z排序算法z哈希表与冲突解决办法z二叉排序树z图的表示（邻接表，邻接矩阵）z深度和广度遍历z最短路径算法(Dijkstra算法和Floyd算法)z传递闭包算法(Floyd算法)z最小生成树(Prim算法和Kruskal算法)z拓扑排序CSE.PF11.基本算法分析z最高和平均复杂度的渐进分析z识别最佳、平均和最差情况的差异zO、o、Ω和θ符号的意义z标准复杂性类别z性能的经验主义度量z算法中时间与空间代价的权衡z使用递推关系分析递归算法z自动机z易解问题与难解问题z不可计算函数z停机问题z不可计算性的含义zP与NP问题3.3计算机硬件基础CSE.CH(Computerhardwarebasics,CCCS-AR)CSE.CH1.数字逻辑与数字系统z计算机系统发展历史回顾南京大学软件工程学科的知识体系8z基本元件(逻辑门，触发器，计数器，寄存器，PLA)z逻辑表达式，最小化，积之和z寄存器传输的表示z物理特性(门延迟、扇入、扇出)CSE.CH2.计算机硬件的基本组织zvonNeumann计算机的基本组织z控制单元：取指令、解码、执行z指令与指令级程序设计（参见面向机器的程序设计）CSE.CH3内存系统的组织与结构z存储系统及其技术z编码、数据压缩与数据完整性z内存的层次z主存的组织与操作z存储器的延迟，周期时间，带宽,，交叉存储技术zCache内存(地址转换，块大小，置换和存储策略)z虚拟存储(页表，TLB)z出错处理与可靠性CSE.CH4.接口与通信z输入输出的基本原理，信号交换，缓冲存储z输入输出控制方式：程序控制输入输出，中断驱动输入输出，DMAz中断机构：中断向量、优先级、中断获取z外部存储器：物理组织和驱动程序z总线：总线协议、仲裁、DMAz网络接口z多媒体支持zRAID结构CSE.CH5.功能组织z简单数据通路的实现z控制单元，硬连线实现与微程序实现z指令读取、解码和执行z指令流水线z指令级并行性简介(ILP)CSE.CH6.多处理器结构zSIMD,MIMD,VLIW,EPIC简介南京大学软件工程学科的知识体系9z网络互连(超立方体，混洗交换，网格结构，交叉开关结构)z共享存储系统zCache一致性z存储模型与存储一致性CSE.CH7.性能演化技术z超标量结构z分支预测z指令预取z推测执行z多线程z可伸缩性3.4系统软件基础CSE.SS(SystemSoftwarebasics,CCCS-OS)CSE.SS1.操作系统概述z操作系统的角色z操作系统发展史z操作系统的功能z进程与资源z应用程序接口(APIs)z运行环境：用户/内核模式，模式切换，中断，地址转换，设备组织z操作系统结构(单块,分层,模块,微内核)CSE.SS2.进程管理z进程„状态与状态转换„进程数据结构z线程z指派和上下文切换„抢占和非抢占式调度„调度程序„最终期限与实时调度z并发程序设计„并发执行的优缺点„互斥问题与解决方案南京大学软件工程学科的知识体系10„死锁：产生，条件与防止„模型与机制(信号量，管程，条件变量)„生产者/消费者问题与同步z多处理器(spin-locks,reentrancy)CSE.SS3.硬件资源管理z内存管理„物理内存与内存管理硬件„覆盖，交换和分区„分页与分段„放置与置换策略„工作集模型„CachingzCSE.OS6.设备管理„串行和并行设备的特征„抽象设备的差异„缓冲策略„直接内存访问„故障恢复CSE.SS4.信息管理的实现z简单文件系统„文件：数据，元数据，操作，组织，缓冲区„目录：内容与结构„文件系统：分区，安装，VFS„标准开发技术„内存映射文件„文件系统的特殊作用„命名，搜索，访问和备份z记录式文件系统的实现zPile文件系统的实现z数据库管理系统的实现CSE.SS5.脚本z脚本和脚本语言的作用z基本系统命令z创建脚本，参数传递南京大学软件工程学科的知识体系11z脚本的执行z脚本语言程序设计CSE.SS6.安全与保护z系统安全概述z策略与机制的分离z安全方法z保护、访问与授权z保护模型z内存保护z保密z恢复管理CSE.SS7.程序设计语言概述z程序设计语言的历史z程序设计语言的简单综述(过程式语言，面向对象语言，函数式语言，逻辑式语言，脚本语言)z程序设计方法学的重要作用z程序设计语言设计概述(基本原理，设计目标，类型机制，Typingregimes,数据结构模型，控制结构模型，抽象机制)CSE.SS8.语言翻译系统的形式化基础z有穷状态自动机„确定有穷状态自动机(DFAs)„非确定有穷状态自动机(NFAs)„DFAs和NFAs等价性z上下文无关语法及其特性z正则表达式及其pumping引理CSE.SS9.语言转换系统z编译器与解释器z语言转化的步骤(词法分析，分解，代码生成，优化)z虚拟机，中间表示语言z语言转换中独立于机器和依赖于机器的侧面z在词法分析中应用正则表达式z分解（具体语法与抽象语法分析，抽象语法分析树）z表驱动和递归下降分析中上下文无关文法的应用z符号表管理南京大学软件工程学科的知识体系12z遍历树生成代码z与机器有关的操作:指令生成与寄存器选择z优化技术z支持语言转换过程的工具及其优点z程序库与分别编译z语法生成工具的构造3.5数据库基础CSE.DB(Databasebasics,CCCS-IM)CSE.DB1.数据库系统简介z数据库系统历史z数据库系统的组成、zDBMS的功能z数据库结构与数据独立性z数据