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

《计算机科学的分支领域体系》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.计算机科学的分支领域体系算法和数据结构程序设计语言体系结构数值和符号计算操作系统软件方法学和工程数据库和信息检索系统人工智能和机器人学人机通信算法和数据结构本领域研究一些特定类型的问题及它们的有效的解。基本问题包括：1.对给定类型的问题，最好的算法是什么？2.它们要求多少存储空间和时间？3.空间与时间的折衷方案是什么？4.存取数据最好的方法是什么？5.最好算法的最坏情况是什么？6.算法的运行按平均来说好到何种程度？7.算法一般化到何种程度--即什么类型的问题可以用类似的方法处理？1．理论算法和数据结构领域理论的

2、主要原理是：(1)可计算性理论。它定义机器能干什么、不能干什么。(2)计算复杂性理论。它告诉你如何测度可计算函数的时空要求，把问题的大小和解决该问题算法的最好或最坏情况的性能联系起来，并提供证明对问题的任何可能解的下界的方法。-..(3)算法和算法类的时间和空间界限。(4)难解性(intractability)水平。例如，确定性的多项式时间内可解的问题(P问题入非确定性的多项式时间内可解的问题(NP问题)；以及有效的并行机可解问题(NC问题)。(5)从算法的数据流要求到机器通讯通路的并行计算、下界和影射。(6)在

3、时空上比确定性算法更加有效、且以足够高的概率获得正确结果的概率算法。蒙特卡洛方法。(7)密码术。(8)图论、递归函数、递推关系、组合论、微积分、归纳、谓词逻辑和时态逻辑(TemporalLogical)、语义学、概率和统计等支撑领域。2．抽象算法和数据结构的抽象的主要部分是：(1)对重要问题类的有效的最优的算法和对最好、最坏和一般性能的分析。·(2)控制和数据结构对各种问题时空要求的影响的分类。(3)重要的技术类型，像分治(divide－and－conquer)、格里地算法、动态规划、有限状态机解释器、堆栈机解释

4、器。(4)并行和分布式算法；把问题分为可以在不同处理器上执行的任务的划分方法。3．设计算法和数据结构领域的设计和实验的主要内容是：(1)对重要问题类的算法的选择、实现和测试。这些问题类包括搜索、排序、随机数产生和结构模式匹配。(2)对于许多类型的问题都可以使用的通用方法的实现和测试。如杂凑法(harshing图和树)。(3)分布式算法的实现和测试。例如网络协议、分布式数据更新、信号(semaphores)、死锁检测器和同步方法。(4)存储管理的实现与测试。例如无用单元收集、伙伴系统(buddySystem)、表(

5、lists)、表格(tables)和分支。(5)对组合问题启发式算法的大量实验测试。(6)能够安全可靠和秘密通信的密码协议。-..程序设计语言本领域研究执行算法的虚拟机的符号表达、算法和数据的符号表达以及从高级语言到机器码的有效的翻译。基本问题包括：1.由一种语言绘出虚拟机可能的组织(数据类型、运算、控制结构、引入新类型和运算的机制)是什么？2.这些抽象怎样在计算机上实现？3.用什么样的符号表达(语法)可以有效地指明计算机应该做什么？1．理论程序设计语言领域的理论的主要部分是：(1)形式语言和自动机，包括语法分析

6、和语言翻译的理论。(2)图灵机(过程性语言的基础)。(3)形式语义：定义计算机数学模型及模型、语法和实现之间关系的方法。主要的方法包括标志的、代数的、操作的和公理的语义。(4)支撑领域：谓词逻辑、时态逻辑、近世代数和数学归纳。2．抽象程序设计语言领域的抽象的主要部分包括：(1)基于语法和动态语义模型的语言的分类：即静态型的、动态型的、功能的、过程性的、面向对象的、逻辑的、说明性的、报文传递和数据流。(2)语言按应用领域的分类：即商业数据处理、模拟表处理和图形。(3)程序结构的主要语法和语义模型的分类：即过程分级、

7、功能合成、抽象数据类型和通信的并行过程。(4)每一种语言的主要类型的抽象实现模型。(5)语法分析、编译、解释和目标码优化的方法。(6)语法分析器、扫描器、编译器部件和编译器自动产生的方法。3．设计-..程序设计语言领域的设计与实验的主要内容是：(1)和特定抽象机器(语义)和语法一起，能形成统一的可实现的整体的特定语言。例如，过程性的(COBOL，FORTRAN，ALGOL，Pascal，Ada，C)、功能的(LISP)，数据流(SISAL，VAL)、面向对象的(Smalltalk，CLU)，逻辑(Prolog)，

8、单处理(SNOBOL)，和并行性(CSP，Occam，ConcurrentPascal，Modula2)。(2)特定类型语言的指定的实现方法：运行时间模型、静态和动态执行方法、打印检查、存储和寄存器分配、编译器、交叉编译器和解释器、在程序中寻找并行性的系统。(3)程序设计环境。(4)语法分析器和扫描器的产生器(例如YACC，LEX)、编译器产生器。(5)语法和语义错误检查