1、计算机科学的分支领域体系教案资料计算机科学的分支领域体系计算机科学的分支领域体系算法和数据结构 程序设计语言体系结构数值和符号计算操作系统软件方法学和工程数据库和信息检索系统人工智能和机器人学人机通信算法和数据结构本领域研究一些特定类型的问题及它们的有效的解。基本问题包括：1.对给定类型的问题，最好的算法是什么？2.它们要求多少存储空间和时间？3.空间与时间的折衷方案是什么？4.存取数据最好的方法是什么？5.最好算法的最坏情况是什么？6.算法的运行按平均来说好到何种程度？7.算法一般化到何种程度-即什么类型的问题可以用类似的方法处理？1理论算法和数据结构领域理论的主要原理是：(1) 可计算性理
2、论。它定义机器能干什么、不能干什么。(2) 计算复杂性理论。它告诉你如何测度可计算函数的时空要求，把问题的大小和解决该问题算法的最好或最坏情况的性能联系起来，并提供证明对问题的任何可能解的下界的方法。(3) 算法和算法类的时间和空间界限。(4) 难解性(intractability) 水平。例如，确定性的多项式时间内可解的问题(P问题入非确定性的多项式时间内可解的问题(NP问题) ；以及有效的并行机可解问题(NC问题) 。(5) 从算法的数据流要求到机器通讯通路的并行计算、下界和影射。(6) 在时空上比确定性算法更加有效、且以足够高的概率获得正确结果的概率算法。蒙特卡洛方法。(7) 密码术。(
3、8) 图论、递归函数、递推关系、组合论、微积分、归纳、谓词逻辑和时态逻辑(Temporal Logical) 、语义学、概率和统计等支撑领域。2抽象算法和数据结构的抽象的主要部分是：(1) 对重要问题类的有效的最优的算法和对最好、最坏和一般性能的分析。(2) 控制和数据结构对各种问题时空要求的影响的分类。(3) 重要的技术类型，像分治(divideandconquer) 、格里地算法、动态规划、有限状态机解释器、堆栈机解释器。(4) 并行和分布式算法；把问题分为可以在不同处理器上执行的任务的划分方法。3设计算法和数据结构领域的设计和实验的主要内容是：(1) 对重要问题类的算法的选择、实现和测试
4、。这些问题类包括搜索、排序、随机数产生和结构模式匹配。(2) 对于许多类型的问题都可以使用的通用方法的实现和测试。如杂凑法(harshing图和树)。(3) 分布式算法的实现和测试。例如网络协议、分布式数据更新、信号(semaphores) 、死锁检测器和同步方法。(4) 存储管理的实现与测试。例如无用单元收集、伙伴系统(buddy System) 、表(lists) 、表格(tables) 和分支。(5) 对组合问题启发式算法的大量实验测试。(6) 能够安全可靠和秘密通信的密码协议。程序设计语言本领域研究执行算法的虚拟机的符号表达、算法和数据的符号表达以及从高级语言到机器码的有效的翻译。基本
5、问题包括：1.由一种语言绘出虚拟机可能的组织(数据类型、运算、控制结构、引入新类型和运算的机制) 是什么？2.这些抽象怎样在计算机上实现？3.用什么样的符号表达(语法) 可以有效地指明计算机应该做什么？1理论程序设计语言领域的理论的主要部分是：(1) 形式语言和自动机，包括语法分析和语言翻译的理论。(2) 图灵机(过程性语言的基础) 。(3) 形式语义：定义计算机数学模型及模型、语法和实现之间关系的方法。主要的方法包括标志的、代数的、操作的和公理的语义。(4) 支撑领域：谓词逻辑、时态逻辑、近世代数和数学归纳。2抽象程序设计语言领域的抽象的主要部分包括：(1) 基于语法和动态语义模型的语言的分
6、类：即静态型的、动态型的、功能的、过程性的、面向对象的、逻辑的、说明性的、报文传递和数据流。(2) 语言按应用领域的分类：即商业数据处理、模拟表处理和图形。(3) 程序结构的主要语法和语义模型的分类：即过程分级、功能合成、抽象数据类型和通信的并行过程。(4) 每一种语言的主要类型的抽象实现模型。(5) 语法分析、编译、解释和目标码优化的方法。(6) 语法分析器、扫描器、编译器部件和编译器自动产生的方法。3设计程序设计语言领域的设计与实验的主要内容是：(1) 和特定抽象机器(语义) 和语法一起，能形成统一的可实现的整体的特定语言。例如，过程性的(COBOL， FORTRAN， ALGOL，Pas
7、cal，Ada，C) 、功能的(LISP) ，数据流(SISAL，VAL) 、面向对象的(Smalltalk， CLU) ，逻辑(Prolog) ，单处理(SNOBOL) ，和并行性(CSP， Occam，Concurrent Pascal，Modula2) 。(2) 特定类型语言的指定的实现方法：运行时间模型、静态和动态执行方法、打印检查、存储和寄存器分配、编译器、交叉编译器和解释器、在程序中寻找并行性的系统。(3) 程序设计环境。(4) 语法分析器和扫描器的产生器(例如YACC，LEX) 、编译器产生器。(5) 语法和语义错误检查程序、剖面(grofiling) 、查错和跟踪。(6) 程序
8、设计语言方法对文件处理功能的应用，如制表、图、化学公式、展开片、方程式、输入和输出以及数据开关。其他应用，如统计处理。体系结构 本领域研究将硬件(和相应软件) 组织成有效和可靠系统的方法。基本问题包括：1.在一个机器中实现处理器、存贮和培讯的好方法是什么？2.我们如何设计和控制大的计算系流并且有说服力地表明，它们能够在有错误和故障的情况下完成预期的工作？3.什么类型的体系结构能使许多处理单元有效地协同工作，实现一个计算的并行？4.我们怎样测度计算机的性能？1理论体系结构领域的理论主要部分是：(1) 布尔代数(2) 开关理论(3) 编码理论(4) 有限状态机理论(5) 统计、概率、排队论、可靠性
9、理论、离散数学、数论和不同数制下的算术等支撑领域。2抽象体系结构领域的抽象主要部分是：(1) 把功能和行为联系起来的电路的有限状态机和布尔模型。(2) 由基本元件综合出系统的其他一般的方法。(3) 在有限域上计算算术函数的电路和有限状态机的模型。(4) 数据通路和控制结构的模型。(5) 对各种模型和工作负荷情况下指令系统的优化。(6) 硬件可靠性：冗余，差错检测，恢复和测试。(7) 在 VLSI装置设计中空间、时间和组织的折衷。(8) 各种计算模型的机器的组织：时序的数据流、表处理、阵列处理、向量处理和报文传送。(9) 分级设计的确定：即系统构成级、程序级、指令系统级、寄存器级和门级。3设计体
10、系结构领域的设计与实验的主要内容是：(1) 快速计算的硬件单元。例如算术逻辑单元、高速缓冲存储器。(2) 所谓冯、诺依曼机器(单指令序列存贮程序式计算机) ：简单指令系统计算机( RISC) 和复杂指令系统计算机( CISC) 实现。(3) 存储和记录信息、检测和改正差错的有效方法。(4) 对差错的特殊处理途径：恢复、诊断、重构和后备过程。(5) 为 VISI电路设计的计算机辅助设计(CAD) 系统和逻辑模拟、版图生成程序、故障诊断、硅编译器。(6) 各种计算模型的机器实现；如数据流、树形 LISP、超立方(hyper。ube)向量和多微处理机。(7) 超级计算机，如Cray和Cyber机。数
11、值和符号计算 本领域研究有效和精确地求解由系统的数学模型导出的方程的一般方法。基本问题包括：1.我们怎么才能用有穷离散过程去精确地逼近连续或无穷的过程？2.我们怎么处理逼近导致的误差？3.怎样才能按照给定精度很快地解出给定类型的方程？4.怎样对方程进行符号运算，例如积分、微分和化简为最小项等？5.怎样把这些问题的回答加入到有效的、可靠的、高质量的数学软件包中去？1理论数值和符号计算领域的理论的主要部分是：(1) 数论(2) 线性代数(3) 数值分析(4) 非线性力学(5) 微积分、实分析、复分析和代数等支持领域。2抽象数值和符号计算领域抽象的主要部分是：(1) 把物理问题形式化为连续的(有时离
12、散的) 数学模型。(2) 连续问题的离散逼近。线性和非线性系统解的向后误差分析、误差传播和稳定性。特殊情况下的特殊方法，例如快速富里叶变换和泊松解答器。(3) 可由正规网孔和边界值给定的一大类问题的有限元模型，相应的迭代方法和收敛理论：直接、隐含、多栅格、收敛率。并行解法。数值积分时自动格栅精炼。(4) 符号积分和微分3设计数值和符号计算领域设计和实验的主要内容是：(1) 高级问题形式化系统，如 CHEM和 WEB。(2) 为线性代数、常微分方程、统计、非线性方程和优化而特殊设计的程序库和程序包，例如 LINPACK，EISPACK，ELLPACK。(3) 将有限元算法影射到特定结构的方法。例
13、如，这些特定结构可能是超立方体上的多栅格。(4) 符号运算，例如 MACSYMA和 REDUCE，能进行有力的非显然的运算，特别是微分、积分和表达式到最小项的简化。操作系统 本领域研究允许多种资源在程序执行中有效配合的控制机制。基本问题包括：1.在计算机系统运行的各级上可见对象和允许的操作是什么？2.对每一类资源(某一级上的可见对象) ，允许它们有效使用的最小操作集是什么？3.怎样组织接口，使得用户只处理资源的抽象形式，而可以不管硬件的实际细节？4.对作业调度、存储器管理、通信、软件资源存取、并发任务间的通信、可靠性和安全的有效控制策略是什么？5.系统应该在功能上可以扩展，只要反复应用少量的构
14、造规则就可以了。那么，这种扩展应遵循的原则是什么？7.怎样组织分布式计算，使得许多由通信网络连结起来的自治的机器能够参与同一计算，而详细的网络协议、主机位置、带宽和资源名称。大都是不可视的？1理论操作系统领域理论的主要部分是：(1) 并发性理论：同步、确定性和死锁。(2) 调度理论，特别是处理器调度。(3) 程序成为存储器管理的理论，包括存储分配的最优策略。(4) 性能模型化与分析。(5) 存储器包装、概率论、排队论、排队网络、通信和信息论、时态逻辑和密码学等支撑领域。2抽象操作系统领域抽象的主要部分是：(1) 允许用户不考虑实际细节对同一类型资源进行操作的抽象原理(例如，面向进程而不是处理器
15、，虚拟存储器而不是主从分级，文件而不是磁盘) 。(2) 用户接口可以察觉对象到内部计算结构的束缚(bindling) 。(3) 重要子问题的模型，这些子问题的例子有进程管理、存储器管理、作业调度、二级存储管理和性能分析。(4) 分布式计算的模型。例如顾客和服务器、合作时序进程、消息传送和远程过程调用。(5) 安全计算模型。例如存取控制,鉴别(Authentication) 和通信。(6) 网络。包括分层协议、命名、远程资源使用、帮助服务和局部网络协议，如记号传送、分时总线。3设计操作系统领域的设计与实验的主要内容是：(1) 分时系统、自动存储分配器、多级调度器、存储管理器、分级文件系统、及其他
16、作为商业性系统基础的系统部件等销样机。(2) 建造操作系统的技术，这些操作系统的例子是UNIX，Multics，Mach，VMS和MSDOS。(3) 建造实用程序库的技术，这些实用程序包括编辑器、文件形成器、编译器、连接器和设备驱动器。(4) 文件和文件系统。(5) 排队网络模型和实际系统性能评估的模拟程序包。(6) 网络结构，如以太网、FDDI、令牌环网、SNA和DECNET。(7) 包含在国防部协议集(TCPIP) 中的协议技术、虚拟电路协议、交互式网络(internet) 、实时会议和X.25。软件方法学和工程 本领域研究满足技术要求、安全、可靠、可信的程序和大型软件系统的设计。基本问题
17、包括：1.在程序和程序设计系统的开发背后的原理是什么？2.怎样去证明程序或系统满足它的技术要求？3.怎样去给定技术要求，使不遗漏重要的情况，而且可以分析它的安全性？4.怎样使软件系统通过不同阶段不断改进？5.怎样使软件设计得易理解和易修改？1理论软件方法学和工具练域理论的主要部分是：(l) 程序验证和证明。(2) 时态逻辑。(3) 可靠性理论。(4) 谓词演算、公理语义学、和认知心理学等支撑领域。2抽象软件方法学和工具抽象的主要部分是：(1) 定义技术要求的方法。如调词变换器、程序设计演算、抽象数据类型和弗洛依德一霍尔(Floyd-Hoare) 公理化符号。(2) 方法学，如逐步提炼、模块化设
18、计、模块、分离编译、信息隐藏(information biding) 、数据流和抽象层次。(3) 程序开发自动化的方法。例如，文本编辑程序，面向语法的编辑程序和屏幕编辑程序。(4) 可信计算的方法学；例如，容错，安全性，可靠性，恢复，N版本程序设计，多方式冗余，和检查点插入。(5) 软件工具和程序设计环境。(6) 程序和系统的测度和评估。(7) 软件系统到特定机器结构的匹配问题域。(8) 软件研制的生命周期模型。3设计软件方法学和工具领域设计和实验的主要内容是：(1) 技术要求描述语言(如PSL 2，IMA JO) 、构造管理系统(如在Ada APSE) 和修改控制系统(如 RCS，SCCS)
19、 。(2) 指向语法的编辑器、行编辑器、屏幕编辑器和字处理系统。(3) 在软件开发实践中倡导和使用的特定方法，如HDM，及Dijkstra，Jackson，Mills或Yourdon等人倡导的方法。(4) 测试的过程和实践(例如，遍历、手模拟、模块间接口的检查、测试集的程序通路列举和事件跟踪) ，质量保证和计划管理。(5) 程序开发和查错，剖面分析，文本格式化和数据库操作的软件工具。(6) 像国防部那样的安全计算系统的标准级和验证过程的技术要求。(7) 用户接口的设计。(8) 设计非常大的、可靠的、容错的和可信的系统的方法。人工智能和机器人学 本领域研究动物和人类(智能) 行为模型。基本的问题
20、包括：基本的行为模型是什么和我们怎样建造机器来模拟它们？由规则赋值、推理、演绎和模式计算所描写的智能可以达到什么程度？由这些模型模拟行为的机器最终能达到什么性能？感知的数据应如何编码，使得类似的模式有类似的码字？驱动码怎样和感知码相联？学习系统的体系结构如何，以及这些系统如何表示他们对外部世界的知识？1理论人工智能和机器人学领域理论的主要部分是：(1) 逻辑：即单调的、非单调的和模糊的。(2) 概念相依性。(3) 识别。(4) 自然语言理解的语法的和公理的模型。(5) 机器人运动和机器人用的外部世界模型中的运动学和力学。(6) 结构力学、图论、形式语法、语言学、哲学和心理学等支持领域。2抽象人
21、工智能和机器人学领域抽象的主要部分是：(1) 知识表示(例如，规则、框架、逻辑) 和处理它们的方法(例如，演绎、推理) 。(2) 自然语言理解和自然语言表示的模型，包括青素表示、机器翻译。(3) 语音识别和合成、正文到语音的翻译。(4) 推理和学习模型，例如，非必然性、非单调逻辑、贝叶斯推断、信念。(5) 启发式搜索方法、分枝眼界法、控制搜索。(6) 模仿生物系统的机器结构，例如，神经网络、连接机制、稀疏分布式存储器。(7) 人类存储模型、自动学习和其他机器人系统元件。3设计人工智能和机器人学领域设计的主要部分包括：(1) 为逻辑程序设计、定理证明和规则赋值的软件系统的设计技术。(2) 小范围
22、专家系统(如Mycin，Xcon) 和为在新范围内编程用的专家系统外壳技术。(3) 逻辑程序设计的实现(如PROLOG) 。(4) 自然语言理解系统(如Margie，SHRDLU和选择语义学) 。(5) 神经网络和稀疏分布式存储器的实现。(6) 玩跳棋、象棋和其他策略性游戏的程序。(7) 工作语音合成、识别。(8) 工作机器人，静态的和移动的。人机通信 本领域研究人类和机器通过各种类似于人的传感器和电动机进行的有效的信息交换，并研究反映人类的概念化的信息结构。基本问题包括：表示对象并自动创造视见画面的有效方法是什么？接收输入或给出输出的有效方法是什么？怎样使错误理解及其后的人的差错导致的危险减
23、到最小限度？怎样用图形和其他工具通过存储在数据集中的信息去理解自然现象？1理论人机通信理论的主要部分是：(1) 二维和高维几何，包括解析几何、投影几何，仿射几何和计算几何。(2) 着色理论。(3) 认知心理学。(4) 傅利叶分析、线性代数、图论、自动机、物理和分析等支撑领域。2抽象人机通信领域抽象的主要部分是：(1) 画面显示算法，包括解决以下问题的方法：光滑化、浓淡渐变(shading) 、隐藏线、声线描迹、隐藏面、透明面、阴影、明暗分布、边缘、着色图、样条表示、透视图、纹理化、防误认、统一性、动画片、画面作为对象的分级表示。(2) 计算机辅助设计(CAD) 模型。(3) 实体对象的计算机表
24、示。(4) 图象处理和增强方法。(5) 人机通信，包括为减少人为错误和提高人的生产率而引入的交互方式的心理学研究。3设计人机通信领域设计与实现的主要部分是：(1) 图形算法在各种图形装置上的实现，这些图形装置包括向量和光栅显示和许多硬拷贝装置。(2) 不断增多的模型和现象的实验性的图形算法的设计与实验。(3) 在显示中彩色图的适当使用；在显示和硬拷贝装置上彩色的精确重现。(4) 图形标准(如GKS，PHIGS，VDI) ，图形语言(如PostScript) ，和特殊图形包(如化学的MOGLI) 。(5) 各种用户接口技术的实现，包括位映象装置上的直接处理和字符装置的屏蔽技术。(6) 为了不同系统和机器之间信息传送的各种标准文件交换格式的实现。(7) 工作CAD系统。(8) 工作图象增强系统(如在从空间探测接收来的画面JPL上) 。
