计算机学科一个新知识框架
摘要 : 這是计算机科学核心攻关组的最后报告它给出计算机学科一个新知识框架，和
计算课程的一个新基础本报告已经过美计算机协会 (ACM) 教育委员会认可并批准发行。
美国计算机协会 (ACM) 已成立 42 年了但一场老问题的争论仍在继续。计算机科学是科学还是工程学科 ?
或者只是一门技术、一个计算商品的研制者和销售者 ? 学科的智力本质是什么 ? 它将持续兴旺下去或者在我们的下一代衰落下去 ? 计算机科学和工程目前的核心课程是否反映了这一领域 ?
怎样把理论和实验室的工作 集成在计算课程中 ? 各核心课程培养计算方面的能力吗 ?
我们建议一种面向技术的学科描述其基础是数学和工程。例如我们把算法当作最基本 的研究对象，而程序设计和硬件设计则当作正要的研究活动认为 " 计算机科学等于程序设计 "
的观点在我们的许多课程里是很占上风的。导引性的课程是程序设 计程序设计技术安排在各核心课程中，而科学则在选修课中这外观点阻止了重新组织各课程的进展，使心怀大志的最好的学生远离我们而去它拒绝了一条统一 的途径，以便把实验的和理论的计算机科学集成为课程的有机组成部分
今天，本领域已经足够成熟使我们能用新的水到渠成的方式来描述它的 知识本质。这在计算机科學与工程博士单位评审部的领导者们 1984 年 7
月在犹他州召开的会议上进行了讨论这一讨论及其他类似的讨论推动 ACM 和 IEEE 计算机学会组成攻关组去開创
在 IEEE 计算机学会热心合作之下，任命了这个计算机科学核心攻关组同时，计算机学会在 ACM 的热心合作下组成了计算机 实验工作攻关组。
我们希望本报告所反映的核心攻关组的工作能产生比预定更多的效益。有了对本学科的核心的共同的认识就能理顺利协调这 两个学會发展行各分支学科和课题的进程。本报告可以作为进一步讨论计算机科学与工程作为一个专业的基础刺激中学计算课程的提高，导致哽大范围地承认计算科学是
我们的目的是创造一个关于本领域的新的思想方法希经把一般性的议论融入学科的性质，寻求一个框架但鈈是一个清单、一个导引，而不是一道命令我们希望你采纳这一框架，并使之适合你自身的情况我们高兴地介绍本学科的新的知识框架和各课程的新基础。
(1) 给出计算机科学的描述该描述要强调基本问题及已有的重要成就。这个定义必须确认本领域在不断变化，现在說的不过是持续进步过程中抢拍的一个镜头
(2) 提出计算机科学的教学规范。该规范要符合传统的科学标准强调本学科能力的培养，并且紦理论、实验相设计紧密地结合在一起
(3) 基于课程模型和学科描述，详尽地给出计算机科学导引性课程系列的一个例子
我们当即把我们嘚任务扩展到包括计算机科学与汁算机工程，因为这两个领域的核心材料没有基本区别区别仅表现在处理这些核心材料的方式不同：计算机科学注重分析和抽象；计算机工程注重抽象和设计。这里计算学科 (discipline of computing)
一词用来包括计算机科学和工程。
有两件重要的事情没有包括在攻关组的任务之内第一，本报告的课程推荐只列出了导引性的课程序列末涉及整个核心课程的设计这样 ? 个重大问题。而实际上如
果对核心的其余部分没有新的设计所建议的导引性课程也就没多大意义了。第二导引性课程的目的是用严格而富有挑战性的方式把学生引箌整个学科领域中去。 我们所列的不过是这种途径的 ? 个例子或者说是我们关于计算的定义的一个 " 存在性证明
" 。我们希望各系应用本框架詓确定他们自己的导引性课程以满足自己 的需要。
籍以从事本领域工作的三种主要形态或称文化方式，提供了我们定义计算学科的条件
第一个形态是理论 (theory) ，基于数学按统一的合理的理论发展过程．包含以下四个步骤：
数学家们认为，当发现错误和矛盾时上述过程應该反复进行。
第二种形态是抽象 (abstraction) 或称模型化，基于实验科学方法按客观现象的研究过程，包含以下四步：
科学家们希望当模型的預言与实验结果不符时，这些步骤应该反复进行虽然这一形态也可以称为 " 模型化 " 或 " 实验
" ，但我们仍采用 " 抽象 " 一词因为它在学科里面比較通用。
第三种形态是设计 (design) 基于工程，按为解决某一个问题而构作系统或装置的过程包含以下四步：
工程师希望，当测试表明当的系統不满足技术条件时上述步骤须反复进行。
理论是数学科学的根本：应用数学家们都认为科学的进展都是基于纯数学的。抽象 ( 模型化 )
昰自然科学的根本：科学家们相信科学进展的过程基本上都是形成假设，然后用模型化过程去求证类似地，设计是工程的根本：工程師们认为工程进展基本上都是提出问题，然后通过设计去构造系统以解决问题。关于数学、 科学、工程三者哪一个更加重要的许多争論实质上都基于一个假定：三个过程 (
理论、抽象或设计 ) 的某一个是最基本的
然而，仔细考察计算学科可以发现关于计算的这三个过程昰如此紧密的交织在一起，以致无法分清哪一个更加基本有许多例子分别表明，抽象和设计阶段出现了理论；理论和设计阶段需要模型型化而理论和抽象阶段，始终离不开设计
虽然这三种形态是紧密相关的，但毕竟是三种不同的形态因为它们代表能力不同的领域。悝论关心的是揭示和证明对象之间相互关系的能力抽象关心的是应用这些关系去做出对现实世界的预言的能力。而设计则关心这些关系嘚某些特定的实现并应用它们去完成有用的任务。应用数学家、计算科学家和设计工程师一般具有
并且计算领域的人们要研究计算工具，以支持人们需要的信息变换过程例如，从设计方面说复杂的 VLSI 设计和模拟
系统处我们能进行微型电路的有效和正确的设计，程序设計环境使我们能有效地进行软件设计从模型化来说．超级计算机能评估数学模型，并做出对现实世界的预言网络有助于传播科学实验嘚成果。从理论来说计算机可以做定理证明，检查技术条件的相容性检查反例，演示测试情况
计算处于应用数学、科学和工程三者嘚主要过程的交叉路口。这三个过程在本学科是同等重要和基本的它是理论、抽象和设计三者唯一的交汇点。维护它们的力量是把实验囷设计作为信息变换器的共同兴趣、在这些过程各阶段的计算支持的共同兴趣、和在有效性方面的共同兴趣
计算领域的许多活功并不是程序设计 ?? 例如，硬件设计、体系结构、操作系统结构、数据库的应用和模型验证 ?? 因此认为 "
计算机科学等于程序设计 " 是错误的。那么程序设计在本学科中的作用是什么 ? 在课程中地位如何 ?
显然，程序设计是本学科标准的实践活动的一部分每一个计算工作者都必须有程序设計的能力。但这并不意味着本学科就建筑在程序设计的基础上，也不意味着
导引性课程必须是程序设计方面的课程同样明显的是，涉忣任何领域的特色都要通过语言而计算学科的特色则大都寓于程序设计符号中。程序设计语言是涉足本 领域特色的工具因此．我们建議，程序设计作为核心课程的一部分并把程序设计语言作为涉足计算学科重要特色的有用媒介。
分支领域的内容我们的描述分四遍扫描，每一遍都大大详尽 ? 步
我们这里所说的仅仅是一个变化着的动态领域的抢拍镜头。它是一个 " 活的定义 "
它可以随时修改，以反映本领域的成熟性和变化我们希望，各分支领域的内容可以经常修改各分支领域的分法可以偶尔有修改，而简短的定义则很少修改
形成一個定义有许多方式。我们提出五个要求：
在形成描述的过程中．我们考虑了原有的几个定义并且得出结论，满足这些要求的描述必须按複杂程度分层次这里，简单地综述一下其他的定义 1967 年． Newell ，
主张计算机科学是研究计算机及围绕它的主要现象的科学，而且说反对這个定义就无异于表明其他科学都不是科学。但不管怎么争辩许多人认为，这是一个循环定义而且对外行人过于简略。不过它仍是┅个好的出发点，因为我们的定义可以看作是列出了围绕汁算机的主要现象
" 计算机科学是关于计算机和计算的知识的总体。它有理论、實验和设计三部分并且包括 (1) 理解计算装置、程序和系统的理论； (2) 为概念的发展和测试所进行的实验； (3)
设计方法论，算法和实现工具；以忣 (4) 验证这些实现满足要求的分析方法 "
第三个定义说， " 计算机科学是研究知识表达及其实现的科学 " 这个定义过于抽象，很少人能够对知識表达有相同的理解具有同样一个问题的另一个定义是， "
计算机科学是关于抽象和复杂性控制的研究 " 是一个对物理、数学或哲学也适鼡的定义。
这种变化的本质是所谓过程性认识论的出现 ?? 它是从命令性的观点来研究知识的结 构，而不是象经典数学那样用陈述性的观点來研究数学提出一个精确处理 " 是什么 "
的问题的框架，而计算则提出精确处理 " 怎样做 " 的问题的框架 [ 1]
计算学科是对描述和变换信息的算法過程的系统研究，包括它的理论、分析、设计、有效性、实现和应用全部计算科学的基本问题是 " 什么能 ( 有效地 )
5.3 划分为分支领域
我们花了楿当的力气，把整个学科分为若干分支领域一开始，我们想尽量少分一些分支领域．例如模型化和实现或者算法和机器。然而我们提出的各种分支都太抽象，界限也很模糊恐怕大部分人都无法顺利地确认它们。
然后我们认识到，学科的基础包含在三个基本过程中 ?? 悝论、抽象和设计各分支领域也是用这些基本过程来完成它们自身的目的的。因此各分支领域及其与这三个基本过程的关系的描述将昰有用的。必须满足下列四个条件才能算得上一个分支领域。
并且每一个分文必须被一个研究群体或几个相关的研究该分支的群体所確认。
理论包括发展本分支数学基础的过程这些过程又由其他领域的理论来支持。例如算法和数据结构分支包括复杂性理论，它本身叒需要图论支持抽象处理潜在实 现的模型化。这些模型忽略 ?
些技术细节而保存本质特性，服从分析的需要提供计算被模型化系统行為的预言所需的工具。设计的过程是给定问题、把问题变换 为设计的技术条件然后，反复设想和考察各种各样的解直到一个可靠的、鈳维护的、有详细资料的、经过验证的、付出的代价大小也符合要求的设计做比来为止。
5.4 分支领域的进一步研究
矩阵是有用的每一行对應一个分支领域，各列分别定义它的理论、抽象和设计每一格填入相应的句子，以描述有关事项及有意义的成就理论 抽象 设计
图 1.1 计算學科的定义矩阵课程设置模式
已有大量科学文献的某些带共同性的群体没有作为分支领域来看待，出为它们在整个学科内部是基本的东西例如，并行性渗透到所有分支领域 ( 包括并行算法、并行语言、并行结构等 )
也遍及到理论、抽象和设计。类似的情况还有安全性、可靠性和性能评估计算机科学家关心的是矩阵的前两列，而计算机工程师关心的是 后两列这给出的计算学科的全部描述见本文附录。
6.1 学科能力的培养
教育的目的是培养在某一领域的工作 能力工作能力，也就是有效的活动能力是评价一个人在本领域进行独立实践活动的水岼的标准。这个评价标准是基于本领域的历史的培养能力的教育过程有五 个步骤： (1)
引起学习某领域的动机； (2) 表明该领域能做什么； (3) 揭示夲领域的特色； (4) 这些特色的历史根源； (5) 实践这些特色 [
4] 。 这 ? 模型隐含了课程设置中一些有趣的问题第一个问题是，计算领域的工作者应该具备什么能力 ? 有两类能力：
1 ．面向学科的思维能力 : 发现本领域新的特性的能力这些特性导致新的活动方式和新的工具，以便使这些特性能被其他人所利用
2 ．使用工具的能力：使用本领域的工具有效地进行其他领域实践活动的能力。
我们建议把面向学科的思维能力作为計算专业课程设置的主要目的。同时计算专业工作者必须充分熟悉工具，以便与其他学科的人们有效地合作进行那些学科的设计活动。
对能力的调查表明某些领域目前设置的核心计算课程是不合适的。例如计算领域的历史内容常不被强调，以致许多毕业生忽视计算學科历史重复原来的错误。
许多计算专业的学生毕业后进入商业数据处理而他们学习的课程并没有注重培养这方面的能力。这种能力究竟应该由计算系来培养还是由商业系来培养是一个长期争论的老问题。面向学科的思维能力必须基于坚实的数学基础而理论目前还沒有成为大多数计算课程的有机组成部分。计算领域典型的实践活动包括设置和进行
实验、为大型协作课题作贡献、以及和其他学科的交鋶以便让他们能有效地运用计算学科。但是大多数课程忽视实验室操作、集体项目和交叉学科研究。
前面的讨论还没有完全说清楚計算课程究竟应该取得什么结果。我们在这里也不打算作彻底的分析。我们希望这个问题在新的核心计算课程设计时优先加以考虑。
應该设计一个课程使毕业生们感到他们需要毕生学习。许多课程都是按讲授的形式给出 " 答案 "
，而不是强调寻求全部学习基础的过程峩们建议下属委员会考虑改变教学规范，使学生们能够善于提出问题查阅计算科学文献，并准备学习一辈子
在本课程设置模式中，引絀本领域的学习目的和显示本领域的内容必须在课程的讲授和实践之前导引性课程系列的目的就在于此。要培养学生能力的那些主要的計
算领域必须充分深入和严格的教给学生使他们领会学科的力量，以从取得在这些学科独立工作能力能够带来的利益然后，课程再系統介绍该领域揭露新概念和 新性质，并让学生们实践
因此，我们建议导引性课程包含正规讲授和密切相关的每周一次实验讲授强调基本原理、实验室技术知道怎么做。
这种方式和过去物理科学和工程所用的一样讲授强调长久不变的原理和概念，而实验室强调暂时性嘚材料和与当前技术有关的技能例如，课堂上讲授算法的设计
与分析或者功能层网络协议的组织。而在相应的实验课上学生们将为課堂上分析的算法写程序，并测量其远行时间或者安装和测试网络接口，并测量他们的包 吞吐量
根据这个意见，计算机科学的第一门課将不仅是介绍程序设计、算法和数据结构还要介绍其他各分支学科的材料。数学和其他理论也要 在合适的地方融合进去我们希望导引性课程能够包含对整个学科严格而富有挑战性的综述。 Feynman
的物理讲座是我们所希望的的导引性课程的范例
如果我们只强调按照本建议重噺设计导引性性课程，而不重新设计全部的大学课程那将是一个严重的错误。物理系的经验就包含了许多值得计算系借鉴的教训
我们假定计算专业的学生在下列方面有一定基础：某种语言的程序设计、某些基于
计算机的工具的使用经验，如字处理、展开片 (Spreadsheet)[ 注 ] 和数据库甴于计算机在高中和家庭的广泛使用，似乎可以假定大多数进入大学的学生已有这种基础．而只是对其他学生提供程序设计的一个补习性嘚课程就
可以了然而，我们发现在高中对程序设计进行适当准备的假定是大有争议的。事实上很少有适当的准备因此，我们建议计算系在导引性课程之前提供程序设 计和计算机工具的初等教程作为预备知识。并且建议系里允许在高中已有适当准备的学生免修该课
數学方面的正式的预备知识和公用基础知识 就更难说清楚，而必须因地制宜然而，计算科学资格审查部要求相当的数学知识包括离散數学、微积分、概率论和统计。这些要求有些过分在我们的初等计算
课程的描述中，给出了这九个分支领域所需要的数学知识我们还盡可能的给出了每一个课程模块所需要的数学基础。这样各系可以自己去平衡他们所开的课程及 对数学知识的要求。有时为了某个特萣的计算课题，而需要引入适当的数学基础这是合适的。一般来说应该让学生们尽早看到在他们学习计算的过程中
需要用到的有关的數学。
[ 注 ] : 译文为展开片实际指的应该是电子表格
导引性课程应能给出本领域统一的基础，又能按灵活而自然的方式由上一个题目转向下┅个题目因此，把这个课程分为九部分每一部分对应一个分支领域是不合适的。这种简单的对应将使课程变成一个大众烩各部分之間很难连接。
满足这一要求的题目顺序是 :
我们把题目分成 11 个模块每一模块包括该科目的有代表性和挑战性的材料，而不是对每一部分材料肤浅的拼凑每一模块从定义矩阵的几个方块中抽取材料。
因而许多模块将不与定义矩阵的各行一一对应。例如我们给出的课程的苐一个模块题为基本算法概念。它只限于研究时序算法包括形式化和理论的作用、程序 设计方法、程序设计概念、有效性和特定算法。咜抽取定义矩阵的第一、第二、第四和第六行的信息后面关于分布式计算和网络以及关于并行计算的模块推广第一
模块的材料，并从定義矩阵的第三和第五行中抽取新的材料
一般来说，每一模块包括讲授所需的理论和大部分抽象的课时理论一般只在需要时才引入。每┅模块都紧密结合实验课实验作业的种类包含在模块规范中。我们草拟的规范是一个三个学期的课程系列每学期讲授 42 次并进行 35
次实验。 该规范本文未予列出但已收入报告全文中。
我们重申本规范只是企图提供从学科描述到导引性课程系列的对应关系的一个实例，并鈈是所有导引性课程的一个清单其他方式可参考某些学院和大学现有的导引性课程
我们描述了一个课程，它把原理和技术分开但保持②者的统一。我们已经推荐课堂上讲授原理，实验室培养技术使二者得以紧密结合。
实验室工作有三个目的：
1. 实验室工件应该表明課堂上讲授的原理怎样运用于实际软件和硬件的设计、实现和测试。实验室必须提供具体经验以帮助学生理解抽象概念。这些经验对提煉学生关于实际计算的直觉知识、对强调建造正确有效的计算机程序和系统所需的脑力劳动都是极其必要的
2 ． 实验室要强调怎样做才能導致一个好的计算的过程。必须强调程序设计而不光是程序本身。必须强调实验室技术、硬件能力的理解、软件工具的正确使用；文档嘚 正确使用以及实验和方案的适当文档主机上要求许多的软件工具，以利于在附加的子系统
上构作、控制和监控实验实验室应教会学苼如何适当的使用这些工具。
3. 实验室应介绍试验方法包括试验的使用和设计、软件和硬件监控器、结果的统计分析以及研究结果的适当陳述。学生们必须学会把细心地试验和粗心地观察区别开
来为了达到这些目的，必须仔细计划和管理实验室的工作学生们必须按时到達实验室。一般每周三小时实验主作业必须事先计划好，并且给每一个学生书面的 实验目的与方法这份幅面材料的深度要和学生过去嘚实验经验相适应。对最初的几个实验这份材料需要更加详细。实验室作业应在实验主教师的指导下进行以
保证每个学生运用正确的方法。导引性课程的实验需要仔细辅导而且需要详细计划试验步骤。因此平均每个学生所需的实验室工作人员人数应该比高级实验室哆 一些。
验课题应与课堂讲授的材料相协调个人实验课题一般探讨硬件与软件的结合。某些实验室作业强调简化软件开发过程的技术与笁具；有些则强调分析和测量已有软件或比较已知的算法；有的则强调基于课堂上所学原理的程序开发
实验室作业必须是自包含的。也僦是说中等水平的学生应能在指定时间内完成。实验室作业应该鼓励学生自己发现和学习一些东西应该要求学生有一个试验记录本，鉯记录试验、观察和数据同时，要求学生保存他们的软件并建立软件库，以备以后实验课
我们希望实验窒应该和课堂一样，给学生留家庭作业并要求使用实验室管辖之外的计算机。换句话说有组织的实验课是补充，而不是代替通常的程序设计作业和书面作业
在楿当数量的程序开发实验室里，作业是修改或完成由教师给出的一个已有的程序这就强制学生去读写好了的程序，并提供软件集成的经驗产生更大、更使学生满意的程序。
计算技术是在不断变化的因此，对实验室应该有的硬件系统、软件系统、仪器和工具很难给出詳细的技术要求。实验室设备和人员的选择应遵循下列原则：
1 ．实验室必须装备有跟上时代的系统和语言程序设计语言对学生形成对计算的看法有重要影响。实验室应该使用那些能使学生养成良好习惯的系统尤其重要的是，在核心课程里要避免使用过时的系统 ( 硬件和软件 )
2 ．硬件和软件要加强维护有故障的装置将使学生受挫，干扰他们的学习必须配备合适的工作人员来维护实验室的硬件和软件。这和其他学科的实验室情况类似
3 ．功能齐全是重要的 ( 这包括分时系统的适当的响应时间 ) 。在学生刚开始接触系统时限制学生在语言或系统嘚一个小的子集中也许是有用的，但当学生有了进步这些限制就应该取消。
4 ． 好的程序设计工具是需要的编译器受到很大重视，但其怹程序设计工具也同样经常用到例如，在 UNIX 系统中学生们必须用像 emacs 那样的编辑
器，并学会使用像 shell grep,awk 和 make 等工具。存储和处理的软件工具必須充足使实验室里随时都可以用这些工具。
5. 必须提供硬件和仪器方面必要的支持某些课题要求学生连接硬件单元的线路，进行信号测量监视数据通路等。应该能充分提供小部件、连接器、电缆线、监视装置和测试仪器等
IEEE 计算机学会的面向目的的实验室开发攻关组对此作了深入的研究。他们的报告
讨论了本课程各种水平的实验室所需资源 ( 即人力和设备 )
以本课程为倒的资格审查工作在计算科学资格审查蔀 (CSAB) 的标准指导下已经完成
如何适应 CSAB 标准的详细情况超出了本委员会的范围
本报告企图提出关于计算科学作为一个学科的新思路，即在揭礻内容时强调基本概念、原理和特性。同时也建议按照其他学科的教育模式重新设计本学科的核心课程。先讲解有用特性的存在性嘫后进行培养能力的实践。这一方法用一个严谨的导引性课程为例说明如何在课堂卜讲授概念和原理，在有关的公共实验里教授
系里不能简单地用新课取代现有的导引性课程必须重新设计该课，使新的导引成为统一整体的一部分因此，我们建议 ACM 成立一个委员会继续工莋以完仝核心课程的重新设计。为了使新课程成为本领域的有机组成部分许多实际问题有待研究。例如：
1. 基于新概念形式化教师需偠重新设计他们的课程。
2. 现在还没有基于本文框架的教材或教科书
3 ．为了本文建议的教育使命，目前大多数系的实验室、设备和材料都尛相适应
4. 助教和教师都不熟悉这一新观点。
5. 在高中阶段对计算科学准备很好的不多我们知道，我们的许多建议是有挑战性的距离实現还有很长的路要走。但是我们相信
，按照本建议改进计算科学教学的努力是有价值的欢迎你和我们一起为此而努力。
11 附录 计算科学莋为一个学科的定义
计算机科学与工程是对描述和变换信息的算法过程 其理论、分析、设计、效率、实现和应用 ?? 的系统的研究全部计算科学的基本问题是，什么能 ( 有效地
) 自动进行 [ 2 3] 。本学科和算法理论、数理逻辑和存储程序式电子计算机的发明一起形成于 40 年代初。
计算嘚渊源可以深入扩展到数学和工程数学把分析分到这一领域，而工程把设计分到这领域本学科包括它自己的理论、实验方法和工程。這与许多其他的自然科 学不同许多其它的自然科学和运用其成果的工程学科是分开的 (
例如化学和化学工程原理 ) 、计算机科学与工程却是鈈可分的，因为本学科的科学与工程形态从根 本上是相互渗透的
计算作为数学的主要对象已有几千年了自然现象的许多模型被用来导出方程，它的解就导致那些自然现象的预言例如轨道 的弹道计算、天气预报和流体的流动等。解这些方程的许多方法已经给出例如线性方程组的解法、微分方程的解法和求函数的积分。几乎在这同时机械系统设计
中所需要的计算成为工程主要关注的对象。例如计算静态粅体压力的算法、计算运动物体惯量的算法和测量比我们直觉要大得多或小得多的距离的方法
工程和数学长期合作的一个成果一直是用於计算的机械工具。某些测量员和航海家的仪器可追溯到几千年前 Pascal 和 LEIBNIZ 在 17
世纪中叶 制造了算术计算器。在 19 世纪 30 年代 Babbage 设想了一个 " 分析机 "
，鈳以用机械无误地计算对数、三角函数和其他般的算术函数。他的机器 虽然没有完成却给后来的工作以启发。到 20 世纪 20 年代 Bush
制造了一囼电子模拟计算机，来解一般的微分方程组同时，出现了能做加．减、 乘、除和开平方的电动计算机后来，电子触发器成为从这些机器到无运动部件的数字计算机的桥梁
逻辑是数学的一个分支，研究推断合理性准 则和推理的形式原理自从欧几里得时代以来，它一直昰严格的数学和科学论证的工具从十九世纪开始，人们开始寻找通用的逻辑系统它应该在已知的演绎系统
中看不到不完全性。在完全系统中就可以机械地确定任何给定的陈述是真还是假。 Godel 在 1931 年发表了他的 " 不完全性定理 " 指出这种系统是不
存在的。到 20 世纪 30 年代后期图靈探索了通用计算机的想法，这种通用计算机能够模仿任何其他计算机器上一步一步运箅的过程他的发现与 GODEL
的想法类似，即某些良好定義的问题不能用任何机械的过程来解决逻辑之所以重要，不仅因为它深刻地看到了自动计算的限制而且因为注意到了符 号串，或者已經编码的数字既可解释成数据，又可解释成程序
这一看法成为区别存储程序式计算机和运算机械的关键的想法。算法步骤被编码成机器表示并存放在存储器中，以后使用时译码并由处理器执行。机器码可以从高级符号形式 ( 程序设计语言 ) 机械地推导出来
这就是关于古代计算和逻辑符号运算错综复杂的历史渊源，以及近代关于电子学和信息的电子表示的线索它们导致了计算学科的诞生。
我们确认了計算科学的几个分支领域：
6. 软件方法学和工程
7. 数据库和信息检索
8. 人工智能和九号机器人E系列学
每一分支领域都有科目的公用基础、本质的悝论部分、有意义的抽象和重要的设计与实现问题理论研究作为该分支领域基础的数学的发展。包括支撑理论象图 论、组合论或形式語言。抽象 ( 模型化
) 处理潜在的实现模型这些模型忽略一些技术细节，而保存本质特性并提供预言未来行为的工具。设计的过程是给定問 题、导出要求和技术条件、反复研制和测试样机从而实现个系统。设计包括实验方法计算科学中的实验方法有好几种形式：测量程序和系统，验证假设的合理 性、通过样机使抽象变为现实
虽然软件方法学本质上说属于设计，但它包含理论和抽象的实质性成分因此，我们把它作一个分支领域另一方 面。并行和分布式计算渗透到所有分支领域和它们的个层次理论、抽象和设计 )
它们既未作为一个分支领域，也不作为某分支领域的一个层次以下各节提供各分 支领域的三个层次的细节。理论与抽象、抽象设计的界限必然是模糊的随各人的胃口可能会有所不同。
我们的目的是通过列出学科的土要特点来提供学科的指南但不是详尽的罗列。应该记住这个学科指南小昰一个课程计划，它只是设计一个课程所需的框架同时应该记住，这个学科指南是一个不断变化着的有机体的瞬间抢拍镜头它需要不斷考验和定期修改
本领域研究一些特定类型的问题及它们的有效的解。基本问题包括：对给定类型的问题最好的算法是什么 ? 它们要求多尐存储空间和时间 ? 空间与时间的折衷方案
是什么 ? 存取数据最好的方法是什么 ? 最好算法的最坏情况是什么 ? 算法的运行按平均来说好到何种程喥 ? 算法一般化到何种程度
?? 即什么类型的问题可以用类似 的方法处理 ?
算法和数据结构领域理论的主要原理是：
(1) 可计算性理论。它定义机器能幹什么、不能干什么
(2) 计算复杂性理论。它告诉你如何测度町计箅函数的时空要求把问题的大小和解决该问题算法的最好或最坏情况的性能联系起来，并提供证明对问题的任何可能解的下界的方法
(3) 算法和算法类的时间和空间界限。
(4) 难解性 (intractability) 水平例如，确定性的多项式时間内可解的问题 (P- 问题 ) ；非确定性的多项式时问内可解的问题 (NP-
问题 ) ；以及有效的并行机可解问题 (NC- 问题 )
(5) 从算法的数据流要求到机器通讯通路嘚并行计算、下界和影射。
(6) 在时空上比确定性算法更加有效、且以足够高的概率获得 TF 确果的概率算法蒙特卡洛方法。
(8) 图论、递归函数、遞推关系、组合论、微积分、归纳、谓词逻辑和时态逻辑 (Temporallogic) 、语义学、概率和统计等支撑领域
算法和数据结构的抽象的上要部分是：
(1) 对重偠问题类的有效的最优的算法和对最好、最坏和一般性能的分析。
(2) 控制和数据结构对各种问题类时空要求的影响的分类
(3) 重要的技术类型，像分治 (divide-and-conquer) 、格里地算法、动态规划、有限状态机解释器、堆栈机解释器
(4) 并行和分布式算法，把问题分由可以在不同处理器上执行的任务嘚划分方法
算法和数据结构领域的避计和实验的主要内容是：
(1) 时最要问题类的算法的选择、实现和测试。这些问题类包括搜索、排序．隨机数产叶和结构模式匹配
(2) 对于许多类型的问题都可以使用的通用方法的实现和测试。如杂凑法 (hashing) 、图和树
(3) 分布式算法的实现和测试。唎如网络协议、分布式数据更新、信号 (semaphores) 、死锁检测器和同步方法
(5) 对组合问题启发式算法的大量实验测试。
(6) 能够安全可靠和秘密通信的密碼协议
本领域研究执行算法的虚拟机的符号表达、算法和数据的符号表达以及从高级语言到机器码的有效的翻译。基本问题包括：由一鍾语言给出的虚拟机的可能的组织 ( 数据类型、运算、控制结构、引入新类型和运算的机制 )
是什么 ? 这些抽象怎样在计算机上实现 ? 用什么样的苻号表达 ( 语法 ) 可以有效地指明计算机应该做什么 ?
程序设计语言领域的理论的主要部分是：
(1) 形式语言和自动机包括语法分析和语言翻译的悝论。
(2) 图灵机 ( 过程性语言的基础 )
(3) 形式语义：定义计算机数学模型及模型、语法和实现之间关系的方法。主要的方法包
括标志的、代数的、操作的和公理的语义
(4) 支撑领域：谓词逻辑、时态逻辑、近世代数和数学归纳。
程序设计语言领域的抽象的主要部分包括：
(1] 基于语法和動态语义模型的语言的分类：即静态型、动态型、功能的、过程性的、面向对象的、逻辑的说明性的、报文传递和数据流。
(2) 语言按应用領域的分类：即商业数据处理、模拟、表处理和图形
(3) 程序结构的主要语法和语义模型的分类：即过程分级、功能合成、抽象数据类型和通信的并行过程。
(4) 每种语言的主要类型的抽象实现模型
(5) 语法分析、编译、解释和开标码优化的方法。
(6) 语法分析器、扫描器、编译器部件囷编译器自动产生的方法
3. 设计程序设计语言倾向的设计与实验的主要内容是：
(1) 和特定抽象机器 ( 语义 ) 和语法一起，能形成统一的一可实现嘚整体的特定语言例如，过程性的 (COBOL FORTRAN
(2) 特定类型语言的指定的蛮现方法：运行时间模型，静态和动态执行方法、打印检查、存储和寄存器汾配、编详器、交叉编徉器和解释器、在程序巾寻找并行性的系统
(3) 程序设计环境。
(4) 语法分析器和扫描器的产生器 ( 例如 YAcc LEx) 、编译器产生器。
(5) 语法和语义错误检查程序、剖面 (profing) 、查错和跟踪
(6) 程序设计语言方法对文件处理功能的应用，如制表、图、化学公式、展开片、方程式、輸入和输出以及数据开关其他应用，如统计处理
本领域研究将硬件 ( 和相应软件 ) 组织成有效和可靠系统的方法。基本问题包括：在一个機器中实现处理器、存贮和通讯的好方法是什么 ?
我们如何设计和控制大的 计算系统并且有说服力地表明它们能够在有错误和故障的情况 r 唍成预期的 J ．作 ? 什么类型的体系结构能使许多处理单元有效地协同工作，实现一个计算的并
行 ? 我们怎样测度计算机的性能 ?
体系结构领域的悝论主要部分是：
(4) 有限状态机理论
(5) 统计、概率、排队论、可靠性理论、离散数学、数论和不同数制下的算术等支撑领域
体系结构领域的抽象主要部分是：
(1) 把功能和行为联系起来的电路的有限状态机和布尔模型。
(2) 由基本元件综合出系统的其它一般的方法
(3) 在有限域上计算算術函数的电路和有限状态机的模型。
(4) 数据通路和控制结构的模型
(5) 对各种模型和工作负荷情况下指令系统的优化。
(6) 硬件可靠性：冗余差錯检测，恢复和测试
(7) 在 VLSI 装置设计中空间、时间和组织的折衷。
(8) 各种计算模型的机器的组织：时序的、数据流、表处理、阵列处理、向量處理和报文传送
(9) 分级设计的确定：即系统构成级、程序级、指令系统级、寄存器级和门级。
体系结构领域的设计与实验的上要内容是：
(1) 赽速计算的硬件单元例如算术函数单元、高速缓冲存储器。
(2) 所谓冯 . 依曼机器 ( 单指令序列存贮程序式计算机 ) ：简单指令系统计算机 (RIsc) 和复杂指令系统计箅机
(3) 存储和记录信息、检测和改正差错的有效方法
(4) 对差错的特殊处理途径：恢复、诊断、重构和后备过程。
(5) 为 VISI 电路设计的计算机辅助设计 (CAD) 系统和逻辑模拟、版图生成程序、故障诊断、硅编译器
(6) 各种计算模型的机器实现；如数据流、树形、 LISP 、超立方 (hypercube) 、向量和多微处理机。
本领域研究有效和精确地求解由系统的数学模型导出的方程的一般方法基本问题包括：我们怎么才能用有穷离散过程去精确哋逼近连续或无穷的过程 ? 我们怎么处 理逼近导致的误差 ?
怎样才能按照给定精度很快地解出给定类型的方程 ? 怎样对方程进行符号运算，例如積分、微分和化简为最小项等 ? 怎祥把这些问题的回答加入 到有效的、可靠的、高质量的数学软件包中去 ?
数值和符号计算领域的理沦的主要蔀分是：
(5) 微积分、实分析、复分析和代数等支持领域
数值和符号计算领域抽象的主要部分是：
(1) 把物理问题形式化为连续的 ( 有时离散的 ) 数學模型。
(2) 连续问题的离散逼近线性和非线性系统解的向后误差分析、误差传播和稳定性。特殊情况下的特殊方法例如快速富里叶变换囷泊松解答器。
(3) 可由正规网孔和边界值给定的大类问题的有限元模型相应的迭代方法和收敛理论：直接、隐含、多栅格、收敛率。并行解法数值积分时自动格栅精炼。
(4) 符号积分和微分
数值和符号计算领域设计和实验的主要内容是：
(2) 为线性代数、常微分方程、统计、非线性方程和优化而特殊设计的程序库和程序包
(3) 将有限元算法映射到特定结构的方法 例如，这些特定结构可能是超立方体上的多栅格
(4) 符号运算例如 MACSYMA 和 REDUCE ，能进行有力的非显然的运算特别是微分、积分和表达式到最小项的简化。
本领域研究允许多种资源在程序执行中有效配合嘚控制机制基本问题包括：在计算机系统运行的各级上可见对象和允许的操作是什么 ? 对每一类资源 ( 某一级上的
可见对象 ) ，允许它们有效使用的最小操作集是什么 ? 怎样组织接口使得用户只处理资源的抽象形式，而可以不管硬件的实际细节 ? 对作业调度、存储器管理、通
信、軟件资源存取、并发任务间的通信、可靠性和安全的有效控制策略是什么 ? 系统应该在功能上可以扩展只要反复应用步量的构造规则就可鉯了。那么这种扩 展应遵循的原则是什么 ?
怎样组织分布式计算，使得许多由通信网络连结起来的自治的机器能够参与同一计算而详细嘚网络协议、主机位置、带宽和资源名称 , 人 都是不可视的 ?
操作系统领域理论的主要部分是：
(1) 并发性理论：同步、确定性和死锁。
(2) 调度理论特别是处理器调度。
(3) 程序行为和存储器管理的理论包括存储分配的最优策略。
(4) 性能模型化与分析
(5) 存储器包装、概率论、排队论、排隊网络、通信和信息论、时态逻辑和密码学等支持领域。
操作系统领域抽象的主要部分是：
(1) 允许用户不考虑实际细节对同一类型资源进行操作的抽象原理 ( 例如面向进程而不是处理器，虚拟存储器而不是主从分级文件而不是磁盘 ) 。
(2) 用户接口可以察觉的对象到内部计算结构嘚束缚 (binding)
(3) 重要子问题的模型，这些子问题的例子有进程管理、存储器管理、作业调度、二级存储管理和性能分析
(4) 分布式计箅的模型。例洳顾客和服务器、合作时序进程、消息传送和远程过程调用
(6) 网络。包括分层协议、命名、远程资源使用、帮助服务和局部网络协议如記号传送、分时总线。
操作系统领域的设计与实验的主要内容是：
(1) 分时系统、自动存储分配器、多级调度器、存储管理器、分级文件系统、及其他作为商业性系统基础的系统部件等的样机
(3) 建造实用程序库的技术，这些实用程序包括编辑器文件形成器、编译器、连接器和設备驱动器。
(4) 文件和文件系统
(5) 排队网络模型和实际系统性能评估的模拟程序包。
(7) 包含在国防部协议集 (TCP ／ IP) 中的协议技术、虚拟电路协议、茭互式网络 (internet) 、实时会议和 X.25
六、软件方法学和工程
软件领域研究满足技术要求、安全、可靠、可信的程序和大型软件系统的设计基本问题包括：在程序和程序设计系统的开发背后的原理是什么 ? 怎样去证明程序或 系统满足它的技术要求 ?
怎样上给定技术要求，使之不遗漏重要的凊况而且可以分析它的安全性 ? 怎样使软件系统通过不同阶段不断改进 ? 怎样使软件设计得易理 解和易修改 ?
软件方法学和工具领域理论的主偠部分是：
(1) 程序验证和证明。
(4) 谓词演算、公理语义学、和认知心理学等支撑领域
软件方法学和工具抽象的主要部分是：
(1) 定义技术要求的方法。如谓词变换器、程序设计演算、抽象数据类型和弗洛依德 - 霍尔 (Floyd-Hoare) 公理化符号
(2) 方法学，如逐步提炼、模块化设计、模块、分离编译、信息隐藏 (informationhiding) 、数据流和抽象层次
(3) 程序开发自动化的方法。例如文本编辑程序，面向语法的编辑程序和屏幕编辑程序
(4) 可信计算的方法学；唎如容错，安全性可靠性，恢复 N 版本程序设计，多方式冗余和检查点插入。
(5) 软件工具和程序设计环境
(6) 程序和系统的测度和评估。
(7) 软件系统到特定机器结构的匹配问题域
(8) 软件研制的生命周期模型。
软件方法学和工具领域殴计和实验的主要内容是：
(2) 指向语法的编辑器、行编辑器、屏幕编辑器和字处理系统
(4) 测试的过程和实践 ( 例如，遍历、手模拟、模块间接口的检查、测试集的程序通路列举和事件跟蹤 ) 质量保证和计划管理。
(5) 程序开发和查错．剖面分析．文本格式化和数据库操作的软什工具
(6) 像国防部那样的安全计算系统的标准级和驗证过程的技术要求。
(7) 用户接口的设计
(8) 设计非常人的可靠、容错和可信的系统的方法。
七、数据库和信息检索系统
本领域研究对大量持續的分享的数据集合的组织使之能够进行有效地查询和刷新。基本问题包括：用什么样的模型化概念去表示数据元和他们之间的关系 ? 怎樣把 存储、定位、匹配和检索等基本操作组合成有效的事务处理
? 这些事务处理怎么与用户有效地交互作用 ? 怎样把高级查询翻译成高性能的程序 ? 什么样的机器结构能 导致有效的检索和刷新 ?
怎样保护数据以抵制非法存取，泄露或破坏 ? 怎样保护大型数据库不会由于同时刷新而导致不相容 ? 当数据分散在许多机器 L 时怎样 使保护和性能二者得以兼顾
? 怎样索引和分类正文，以达到有效的检索 ?
数据库和信息检索系统领域悝论的主要部分是：
(1) 关系代数和关系演算
(3) 并发理论、特别是可串行的事务处理、死锁和多复制件的同步更新。
(7) 作为支持理论的密码学
數据库和信息检索系统抽象的主要部分是：
(1) 表示逻辑结构和数据元之间关系的模型，包括关系模型和实体关系模型
(2) 为快速检索的文件的表示，如索引、树、反演和相联存储
(3) 保证更新时数据库完整性 ( 相容性 ) 的方法，包括多复制件的并发更新
(4) 防止非法泄露或更改以及极小囮统汁推断的方法。
(5) 对不同类型数据库提出询问的语言 ( 例如超正文、正文、空间的、图形、图象、规则
集 ) 。对信息检索系统也类似
(6) 模型，例如超正文它允许文件包含多级正文．并包括显示、图形和声音。
(7) 人的因素和接口
数据库和信息检索系统领域设计的主要内容是：
(1) 设计关系、分级、网络和分布式数据库的技术。
(4) 安全数据库系统的设计
(6) 把大型数据库录入磁盘存储器的技术。
(7) 把大型只读数据库存入咣存储媒介的技术例如 CD ／ ROM 和 WORMS 。
八、人工智能和九号机器人E系列学
本领域研究动物和人类 ( 智能 ) 行为模型基本的问题包括：摹本的行为模型是什么和我们怎样建造机器来模拟它们 ?
由规则赋值、推理、演绎和模式计算所描写的 智能可以达到什么程度 ? 由这些模型模拟行为的机器朂终能达到什么性能 ? 感知的数据应如何编码，使得类似的模式有类似的码字 ?
驱动码怎样和感知码相联 ? 学习系统的体系结构如何以及这些系统如何表示他们对外部世界的知识 ?
人工智能和九号机器人E系列学领域理论的主要部分是：
(1) 逻辑：即单调的、非单调的和模糊的。
(4) 自然语訁理解的语法的和公理的模型
(5) 九号机器人E系列运动和九号机器人E系列用的外部世界模型中的运动学和力学。
(6) 结构力学、图论、形式语法、语言学、哲学和心理学等支持领域
人工智能和九号机器人E系列学领域抽象的主要部分是：
(1) 知识表示 ( 例如，规则、框架、逻辑 ) 和处理它們的方法 ( 例如演绎、推理 ) 。
(2) 自然语言理解和自然语言表示的模型包括音素表示、机器翻译。
(3) 语音识别和合成、正文到语音的翻译
(4) 推悝和学习模型，例如非必然性、非单调逻辑、贝叶斯推断、信念。
(5) 启发式搜索方法、分枝限界法、控制搜索
(6) 模仿生物系统的机器结构，例如神经网络、连接机制，稀疏分布式存储器
(7) 人类存储模型、自动学习和其他九号机器人E系列系统元件。
人工智能和九号机器人E系列学领域设计的主要部分包括：
(1) 为逻辑程序设计、定理证明和规则赋值的软件系统的设计技术
(2) 小范围专家系统 ( 如 Mycin ， Xcon) 和为在新范围内编程鼡的专家系统外壳技术 '
(5) 神经网络和稀疏分布式存储器的实现。
(6) 玩跳棋、象棋和其他策略性游戏的程序
(7) 工作语音合成、识别。
(8) 工作九号機器人E系列静态的和移动的。
本领域研究人类和机器通过各种类似于人的传感器和电动机进行的有效的信息交换并研究反映人类的概念化的信息结构。基本问题包括：表示对象并自动创造视见 画面的有效方法是什么 ? 接收输入或给出输出的有效方法是什么
? 怎样使错误理解忣其后的人的差错导致的危险减到最小限度 ? 怎样用图形和其他工具通过存储在数 据集中的信息去理解自然现象 ?
人机通信理论的主要部分是：
(1) 二维和高维几何包括解析几何、投影几何，仿射几何和计算几何
(4) 傅利叶分析、线性代数、图论，自动机、物理和分析等支撑领域
囚机通信领域抽象的主要部分是；
(1) 画面显示算法，包括解决以下问题的方法：光滑化、浓淡渐变 (shading) 、隐藏线、声线描迹、隐藏面、透明面、陰影、明暗分布、边缘、着色图、样条表示、透视图、纹理化、防误认、统一性、动画片、画面作为对象的分级表示
(3) 实体对象的计算机表示。
(4) 图象处理和增强方法
(5) 人机通信，包括为减少人为错误和提高人的生产率而引入的交互方式的心理学研究
人机通信领域设计与实現的主要部分是：
(1) 图形算法在各种图形装置上的实现，这些图形装置包括向量和光栅显示和许多硬拷贝装置
(2) 不断增多的模型和现象的实驗性的图形算法的设计与实验。
(3) 在显示中彩色图的适当使用；在显示和硬拷见装置上彩色的精确重现
(5) 各种用户接口技术的实现，包括位映象装置上的直接处理和字符装置的屏蔽技术
(6) 为了不同系统和机器之间信息传送的各种标准文件交换格式的实现。
(8) 工作图象增强系统 ( 如茬从空间探测接收来的画面 JPL 上 )
许多人对本报告的原稿慷慨地提出了书面意见，虽然无法采纳所有这些意见但我们在修改原稿时确实考慮了每一条意见。谨对下列各位提出的意见表示感谢
