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

计算机科学的分支领域体系 算法和数据结构 程序设计语言 体系结构 数值和符号计算 操作系统 软件方法学和工程 数据库和信息检索系统 人工智能和机器人学 人机通信 算法和数据结构 本领域研究一些特定类型的问题及它们的有效的解。基本问题包括： 1.对给定类型的问题，最好的算法是什么？ 2.它们要求多少存储空间和时间？ 3.空间与时间的折衷方案是什么？ 4.存取数据最好的方法是什么？ 5.最好算法的最坏情况是什么？ 6.算法的运行按平均来说好到何种程度？ 7.算法一般化到何种程度--即什么类型的问题可以用类似的方法处理？ 1．理论 算法和数据结构领域理论的主要原理是： (1) 可计算性理论。它定义机器能干什么、不能干什么。 (2) 计算复杂性理论。它告诉你如何测度可计算函数的时空要求，把问题的大小和解决该问题算法的最好或最坏情况的性能联系起来，并提供证明对问题的任何可能解的下界的方法。 (3) 算法和算法类的时间和空间界限。 (4) 难解性(intractability) 水平。例如，确定性的多项式时间内可解的问题(P问题入非确定性的多项式时间内可解的问题(NP问题) ；以及有效的并行机可解问题(NC问题) 。 (5) 从算法的数据流要求到机器通讯通路的并行计算、下界和影射。 (6) 在时空上比确定性算法更加有效、且以足够高的概率获得正确结果的概率算法。蒙特卡洛方法。 (7) 密码术。 (8) 图论、递归函数、递推关系、组合论、微积分、归纳、谓词逻辑和时态逻辑(Temporal Logical) 、语义学、概率和统计等支撑领域。 2．抽象 算法和数据结构的抽象的主要部分是： (1) 对重要问题类的有效的最优的算法和对最好、最坏和一般性能的分析。· (2) 控制和数据结构对各种问题时空要求的影响的分类。 (3) 重要的技术类型，像分治(divide－and－conquer) 、格里地算法、动态规划、有限状态机解释器、堆栈机解释器。 (4) 并行和分布式算法；把问题分为可以在不同处理器上执行的任务的划分方法。 3．设计 算法和数据结构领域的设计和实验的主要内容是： (1) 对重要问题类的算法的选择、实现和测试。这些问题类包括有哪些信誉好的足球投注网站、排序、随机数产生和结构模式匹配。 (2) 对于许多类型的问题都可以使用的通用方法的实现和测试。如杂凑法(harshing图和树)。 (3) 分布式算法的实现和测试。例如网络协议、分布式数据更新、信号(semaphores) 、死锁检测器和同步方法。 (4) 存储管理的实现与测试。例如无用单元收集、伙伴系统(buddy System) 、表(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，Concurrent Pascal，Modula2) 。 (2) 特定类型语言的指定的实现方法