计算机科学的分支领域体系

计算机科学的分支领域体系算法和数据结构程序设计语言体系结构数值和符号计算操作系统软件方法学和工程数据库和信息检索系统人工智能和机器人学人机通信算法和数据结构本领域研究一些特定类型的问题及它们的有效的解。基本问题包括：1.对给定类型的问题，最好的算法是什么？2.它们要求多少存储空间和时间？3.空间与时间的折衷方案是什么？4.存取数据最好的方法是什么？5.最好算法的最坏情况是什么？6.算法的运行按平均来说好到何种程度？7.算法一般化到何种程度--即什么类型的问题可以用类似的方法处理？1．理论算法和数据结构领域理论的主要原理是：(1)可计算性理论。它定义机器能干什么、不能干什么。(2)计算复杂性理论。它告诉你如何测度可计算函数的时空要求，把问题的大小和解决该问题算法的最好或最坏情况的性能联系起来，并提供证明对问题的任何可能解的下界的方法。(3)算法和算法类的时间和空间界限。(4)难解性(intractability)水平。例如，确定性的多项式时间内可解的问题(P问题入非确定性的多项式时间内可解的问题(NP问题)；以及有效的并行机可解问题(NC问题)。(5)从算法的数据流要求到机器通讯通路的并行计算、下界和影射。(6)在时空上比确定性算法更加有效、且以足够高的概率获得正确结果的概率算法。蒙特卡洛方法。(7)密码术。(8)图论、递归函数、递推关系、组合论、微积分、归纳、谓词逻辑和时态逻辑(TemporalLogical)、语义学、概率和统计等支撑领域。2．抽象算法和数据结构的抽象的主要部分是：(1)对重要问题类的有效的最优的算法和对最好、最坏和一般性能的分析。·(2)控制和数据结构对各种问题时空要求的影响的分类。(3)重要的技术类型，像分治(divide－and－conquer)、格里地算法、动态规划、有限状态机解释器、堆栈机解释器。(4)并行和分布式算法；把问题分为可以在不同处理器上执行的任务的划分方法。3．设计算法和数据结构领域的设计和实验的主要内容是：(1)对重要问题类的算法的选择、实现和测试。这些问题类包括搜索、排序、随机数产生和结构模式匹配。(2)对于许多类型的问题都可以使用的通用方法的实现和测试。如杂凑法(harshing图和树)。(3)分布式算法的实现和测试。例如网络协议、分布式数据更新、信号(semaphores)、死锁检测器和同步方法。(4)存储管理的实现与测试。例如无用单元收集、伙伴系统(buddySystem)、表(lists)、表格(tables)和分支。(5)对组合问题启发式算法的大量实验测试。(6)能够安全可靠和秘密通信的密码协议。程序设计语言本领域研究执行算法的虚拟机的符号表达、算法和数据的符号表达以及从高级语言到机器码的有效的翻译。基本问题包括：1.由一种语言绘出虚拟机可能的组织(数据类型、运算、控制结构、引入新类型和运算的机制)是什么？2.这些抽象怎样在计算机上实现？3.用什么样的符号表达(语法)可以有效地指明计算机应该做什么？1．理论程序设计语言领域的理论的主要部分是：(1)形式语言和自动机，包括语法分析和语言翻译的理论。(2)图灵机(过程性语言的基础)。(3)形式语义：定义计算机数学模型及模型、语法和实现之间关系的方法。主要的方法包括标志的、代数的、操作的和公理的语义。(4)支撑领域：谓词逻辑、时态逻辑、近世代数和数学归纳。2．抽象程序设计语言领域的抽象的主要部分包括：(1)基于语法和动态语义模型的语言的分类：即静态型的、动态型的、功能的、过程性的、面向对象的、逻辑的、说明性的、报文传递和数据流。(2)语言按应用领域的分类：即商业数据处理、模拟表处理和图形。(3)程序结构的主要语法和语义模型的分类：即过程分级、功能合成、抽象数据类型和通信的并行过程。(4)每一种语言的主要类型的抽象实现模型。(5)语法分析、编译、解释和目标码优化的方法。(6)语法分析器、扫描器、编译器部件和编译器自动产生的方法。3．设计程序设计语言领域的设计与实验的主要内容是：(1)和特定抽象机器(语义)和语法一起，能形成统一的可实现的整体的特定语言。例如，过程性的(COBOL，FORTRAN，ALGOL，Pascal，Ada，C)、功能的(LISP)，数据流(SISAL，VAL)、面向对象的(Smalltalk，CLU)，逻辑(Prolog)，单处理(SNOBOL)，和并行性(CSP，Occam，ConcurrentPascal，Modula2)。(2)特定类型语言的指定的实现方法：运行时间模型、静态和动态执行方法、打印检查、存储和寄存器分配、编译器、交叉编译器和解释器、在程序中寻找并行性的系统。(3)程序设计环境。(4)语法分析器和扫描器的产生器(例如YACC，LEX)、编译器产生器。(5)语法和语义错误检查程序、剖面(grofiling)、查错和跟踪。(6)程序设计语言方法对文件处理功能的应用，如制表、图、化学公式、展开片、方程式、输入和输出以及数据开关。其他应用，如统计处理。体系结构本领域研究将硬件(和相应软件)组织成有效和可靠系统的方法。基本问题包括：1.在一个机器中实现处理器、存贮和培讯的好方法是什么？2.我们如何设计和控制大的计算系流并且有说服力地表明，它们能够在有错误和故障的情况下完成预期的工作？3.什么类型的体系结构能使许多处理单元有效地协同工作，实现一个计算的并行？4.我们怎样测度计算机的性能？1．理论体系结构领域的理论主要部分是：(1)布尔代数(2)开关理论(3)编码理论(4)有限状态机理论(5)统计、概率、排队论、可靠性理论、离散数学、数论和不同数制下的算术等支撑领域。2．抽象体系结构领域的抽象主要部分是：(1)把功能和行为联系起来的电路的有限状态机和布尔模型。(2)由基本元件综合出系统的其他一般的方法。(3)在有限域上计算算术函数的电路和有限状态机的模型。(4)数据通路和控制结构的模型。(5)对各种模型和工作负荷情况下指令系统的优化。(6)硬件可靠性：冗余，差错检测，恢复和测试。(7)在VLSI装置设计中空间、时间和组织的折衷。(8)各种计算模型的机器的组织：时序的数据流、表处理、阵列处理、向量处理和报文传送。(9)分级设计的确定：即系统构成级、程序级、指令系统级、寄存器级和门级。3．设计体系结构领域的设计与实验的主要内容是：(1)快速计算的硬件单元。例如算术逻辑单元、高速缓冲存储器。(2)所谓冯、诺依曼机器(单指令序列存贮程序式计算机)：简单指令系统计算机(RISC)和复杂指令系统计算机(CISC)实现。(3)存储和记录信息、检测和改正差错的有效方法。(4)对差错的特殊处理途径：恢复、诊断、重构和后备过程。(5)为VISI电路设计的计算机辅助设计(CAD)系统和逻辑模拟、版图生成程序、故障诊断、硅编译器。(6)各种计算模型的机器实现；如数据流、树形LISP、超立方(hyper。ube)向量和多微处理机。(7)超级计算机，如Cray和Cyber机。数值和符号计算本领域研究有效和精确地求解由系统的数学模型导出的方程的一般方法。基本问题包括：1.我们怎么才能用有穷离散过程去精确地逼近连续或无穷的过程？2.我们怎么处理逼近导致的误差？3.怎样才能按照给定精度很快地解出给定类型的方程？4.怎样对方程进行符号运算，例如积分、微分和化简为最小项等？5.怎样把这些问题的回答加入到有效的、可靠的、高质量的数学软件包中去？1．理论数值和符号计算领域的理论的主要部分是：(1)数论(2)线性代数(3)数值分析(4)非线性力学(5)微积分、实分析、复分析和代数等支持领域。2．抽象数值和符号计算领域抽象的主要部分是：(1)把物理问题形式化为连续的(有时离散的)数学模型。(2)连续问题的离散逼近。线性和非线性系统解的向后误差分析、误差传播和稳定性。特殊情况下的特殊方法，例如快速富里叶变换和泊松解答器。(3)可由正规网孔和边界值给定的一大类问题的有限元模型，相应的迭代方法和收敛理论：直接、隐含、多栅格、收敛率。并行解法。数值积分时自动格栅精炼。(4)符号积分和微分3．设计数值和符号计算领域设计和实验的主要内容是：(1)高级问题形式化系统，如CHEM和WEB。(2)为线性代数、常微分方程、统计、非线性方程和优化而特殊设计的程序库和程序包，例如LINPACK，EISPACK，ELLPACK。(3)将有限元算法影射到特定结构的方法。例如，这些特定结构可能是超立方体上的多栅格。(4)符号运算，例如MACSYMA和REDUCE，能进行有力的非显然的运算，特别是微分、积分和表达式到最小项的简化。操作系统本领域研究允许多种资源在程序执行中有效配合的控制机制。基本问题包括：1.在计算机系统运行的各级上可见对象和允许的操作是什么？2.对每一类资源(某一级上的可见对象)，允许它们有效使用的最小操作集是什么？3.怎样组织接口，使得用户只处理资源的抽象形式，而可以不管硬件的实际细节？4.对作业调度、存储器管理、通信、软件资源存取、并发任务间的通信、可靠性和安全的有效控制策略是什么？5.系统应该在功能上可以扩展，只要反复应用少量的构造规则就可以了。那么，这种扩展应遵循的原则是什么？7.怎样组织分布式计算，使得许多由通信网络连结起来的自治的机器能够参与同一计算，而详细的网络协议、主机位置、带宽和资源名称。大都是不可视的？1．理论操作系统领域理论的主要部分是：(1)并发性理论：同步、确定性和死锁。(2)调度理论，特别是处理器调度。(3)程序成为存储器管理的理论，包括存储分配的最优策略。(4)性能模型化与分析。(5)存储器包装、概率论、排队论、排队网络、通信和信息论、时态逻辑和密码学等支撑领域。2．抽象操作系统领域抽象的主要部分是：(1)允许用户不考虑实际细节对同一类型资源进行操作的抽象原理(例如，面向进程而不是处理器，虚拟存储器而不是主从分级，文件而不是磁盘)。(2)用户接口可以察觉对象到内部计算结构的束缚(bindling)。(3)重要子问题的模型，这些子问题的例子有进程管理、存储器管理、作业调度、二级存储管理和性能分析。(4)分布式计算的模型。例如顾客和服务器、合作时序进程、消息传送和远程过程调用。(5)安全计算模型。例如存取控制,鉴别(Authentication)和通信。(6)网络。包括分层协议、命名、远程资源使用、帮助服务和局部网络协议，如记号传送、分时总线。3．设计操作系统领域的设计与实验的主要内容是：(1)分时系统、自动存储分配器、多级调度器、存储管理器、分级文件系统、及其他作为商业性系统基础的系统部件等销样机。(2)建造操作系统的技术，这些操作系统的例子是UNIX，Multics，Mach，VMS和MS－DOS。(3)建造实用程序库的技术，这些实用程序包括编辑器、文件形成器、编译器、连接器和设备驱动器。(4)文件和文件系统。(5)排队网络模型和实际系统性能评估的模拟程序包。(6)网络结构，如以太网、FDDI、令牌环网、SNA和DECNET。(7)包含在国防部协议集(TCP／IP)中的协议技术、虚拟电路协议、交互式网络(internet)、实时会议和X.25。软件方法学和工程本领域研究满足技术要求、安全、可靠、可信的程序和大型软件系统的设计。基本问题包括：1.在程序和程序设计系统的开发背后的原理是什么？2.怎样去证明程序或系统满足它的技术要求？3.怎样去给定技术要求，使不遗漏重要的情况，而且可以分析它的安全性？4.怎样使软件系统通过不同阶段不断改进？5.怎样使软件设计得易理解和易修改？1．理论软件方法学和工具练域理论的主要部分是：(l)程序验证和证明。(2)时态逻辑。(3)可靠性理论。(4)谓词演算、公理语义学、和认知心理学等支撑领域。2．抽象软件方法学和工具抽象的主要部分是：(1)定义技术要求的方法。如调词变换器、程序设计演算、抽象数据类型和弗洛依德一霍尔(Floyd-Hoare)公理化符号。(2)方法学，如逐步提炼、模块化设计、模块、分离编译、信息隐藏(informationbiding)、数据流和抽象层次。(3)程序开发自动化的