电脑科学-一门科学领域-中文百科全书

简介

电脑科学(英语:computer science，有时缩写为CS)是系统性研究信息与计算的理论基础以及它们在电脑系统中如何实现与套用的实用技术的学科。它通常被形容为对那些创造、描述以及转换信息的演算法处理的系统研究。电脑科学包含很多分支领域;有些强调特定结果的计算，比如电脑图形学;而有些是探讨计算问题的性质，比如计算复杂性理论;还有一些领域专注于怎样实现计算，比如程式语言理论是研究描述计算的方法，而程式设计是套用特定的程式语言解决特定的计算问题，人机互动则是专注于怎样使电脑和计算变得有用、好用，以及随时随地为人所用。

有时公众会误以为电脑科学就是解决电脑问题的事业(比如信息技术)，或者只是与使用电脑的经验有关，如玩游戏、上网或者文字处理。其实电脑科学所关注的，不仅仅是去理解实现类似游戏、流览器这些软体的程式的性质，更要通过现有的知识创造新的程式或者改进已有的程式。

研究领域

电脑是一种进行算术和逻辑运算的机器，而且对于由若干台电脑联成的系统而言还有通信问题,并且处理的对象都是信息,因而也可以说，电脑科学是研究信息处理的科学。电脑科学分为理论电脑科学和实验电脑科学两个部分。在数学文献中所说的电脑科学，一般是指理论电脑科学。实验电脑科学还包括有关开闢电脑新的套用领域的研究。

电脑科学的大部分研究是基于"冯·诺依曼电脑"和"图灵机"的，它们是绝大多数实际机器的计算模型。作为此模型的开山鼻祖，邱奇-图灵论题(Church-Turing Thesis)表明，尽管在计算的时间，空间效率上可能有所差异，现有的各种计算设备在计算的能力上是等同的。尽管这个理论通常被认为是电脑科学的基础，可是科学家也研究其它种类的机器，如在实际层面上的并行电脑和在理论层面上概率电脑、oracle 电脑和量子电脑。在这个意义上来讲，电脑只是一种计算的工具:着名的电脑科学家 Dijkstra 有一句名言"电脑科学之关注于电脑并不甚于天文学之关注于望远镜。"。

科学领域

作为一个学科，电脑科学涵盖了从演算法的理论研究和计算的极限，到如何通过硬体和软体实现计算系统。CSAB(以前被叫做Computing Sciences Accreditation Board)，由Association for Computing Machinery(ACM)和IEEE Computer Society(IEEE-CS)的代表组成，确立了电脑科学学科的4个主要领域:计算理论，演算法与资料结构，编程方法与程式语言，以及电脑元素与架构。CSAB还确立了其它一些重要领域，如软体工程，人工智慧，电脑网路与通信，资料库系统，并行计算，分散式计算，人机互动，机器翻译，电脑图形学，作业系统，以及数值和符号计算。

理论电脑

主条目:理论电脑科学

广义的理论电脑科学包括经典的计算理论和其它专注于更抽象、逻辑与数学方面的计算。

计算理论

主条目:计算理论

按照Peter J. Denning的说法，电脑科学的最根本问题是"什麽能够被有效地自动化?"计算理论的研究就是专注于回答这个根本问题，关于什麽能够被计算，去实施这些计算又需要用到多少资源。为了尝试回答第一个问题，递归论检验在多种理论计算模型中哪个计算问题是可解的。而计算复杂性理论则被用于回答第二个问题，研究解决一个不同目的的计算问题的时间与空间消耗。

着名的"P=NP?"问题，千禧年大奖难题之一，是计算理论的一个开放问题。

信息编码论

主条目:资讯理论和编码理论

资讯理论与信息量化相关，由Claude E. Shannon建立，用于寻找信号处理操作的根本极限，比如压缩资料和可靠的资料存储与通讯。编码理论是对编码以及它们适用的特定套用性质的研究。编码(code)被用于资料压缩，密码学，前向纠错，也被用于网路编码。研究编码的目的在于设计更高效、可靠的资料传输方法。

演算法

演算法指定义良好的计算过程，它取一个或一组值作为输入，经过一系列定义好的计算过程，得到一个或一组输出。演算法是电脑科学研究的一个重要领域，也是许多其他电脑科学技术的基础。演算法主要包括资料结构、计算几何、图论等。除此之外，演算法还包括许多杂项，如模式匹配、部分数论等。

程式设计理论

主条目:程式语言理论

程式语言理论是电脑科学的一个分支，主要处理程式语言的设计、实现、分析、描述和分类，以及它们的个体特徵。它属于电脑科学学科，既受影响于也影响着数学、软体工程和语言学。它是公认的电脑科学分支，同时也是活跃的研究领域，研究成果被发表在众多学术期刊，电脑科学以及工程出版物。

形式化方法

主条目:形式化方法

形式化方法是一种特别的基于数学的技术，用于软体和硬体系统的形式规範、开发以及形式验证。在软体和硬体设计方面，形式化方法的使用动机，如同其它工程学科，是通过适当的数学分析便有助于设计的可靠性和健壮性的期望。但是，使用形式化方法会带来很高的成本，意味着它们通常只用于高可靠性系统，这种系统中安全或保全(security)是最重要的。对于形式化方法的最佳形容是各种理论电脑科学基础种类的套用，特别是电脑逻辑演算，形式语言，自动机理论和形式语义学，此外还有类型系统、代数资料类型，以及软体和硬体规範和验证中的一些问题。

并发，并行和分散式系统

主条目:并行性和分散式计算

并行性(concurrency)是系统的一种性质，这类系统可以同时执行多个可能互相互动的计算。一些数学模型，如Petri网、进程演算和PRAM模型，被建立以用于通用并发计算。分散式系统将并行性的思想扩展到了多台由网路连线的电脑。同一分散式系统中的电脑拥有自己的私有记忆体，它们之间经常交换信息以达到一个共同的目的。

资料库和信息检索

主条目:资料库和资料库管理系统

资料库是为了更容易地组织、存储和检索大量资料。资料库由资料库管理系统管理，通过资料库模型和查询语言来存储、建立、维护和搜寻资料。

套用电脑科学

尽管电脑科学(computer science)的名字裏包含电脑这几个字，但实际上电脑科学相当数量的领域都不涉及电脑本身的研究。因此，一些新的名字被提议出来。某些重点大学的院系倾向于术语计算科学(computing science)，以精确强调两者之间的不同。丹麦科学家Peter Naur建议使用术语"datalogy"，以反映这一事实，即科学学科是围绕着资料和资料处理，而不一定要涉及电脑。第一个使用这个术语的科学机构是哥本哈根大学Datalogy学院，该学院成立于1969年，Peter Naur便是第一任教授。这个术语主要被用于北欧国家。同时，在计算技术发展初期，《ACM通讯》建议了一些针对计算领域从业人员的术语:turingineer，turologist，flow-charts-man，applied meta-mathematician及applied epistemologist。三个月后在同样的期刊上，comptologist被提出，第二年又变成了hypologist。术语computics也曾经被提议过。在欧洲大陆，起源于信息(information)和数学或者自动(automatic)的名字比起源于电脑或者计算(computation)更常见，如informatique(法语)，Informatik(德语)，informatika(斯拉夫语族)。

着名电脑科学家Edsger Dijkstra曾经指出:"电脑科学并不只是关于电脑，就像天文学并不只是关于望远镜一样。"("Computer science is no more about computers than astronomy is about telescopes.")设计、部署电脑和电脑系统通常被认为是非电脑科学学科的领域。例如，研究电脑硬体被看作是电脑工程的一部分，而对于商业电脑系统的研究和部署被称为信息技术或者信息系统。然而，现如今也越来越多地融合了各类电脑相关学科的思想。电脑科学研究也经常与其它学科交叉，比如心理学，认知科学，语言学，数学，物理学，统计学和经济学。

电脑科学被认为比其它科学学科与数学的联系更加密切，一些观察者说计算就是一门数学科学。早期电脑科学受数学研究成果的影响很大，如Kurt Gödel和Alan Turing，这两个领域在某些学科，例如数理逻辑、範畴论、域理论和代数，也不断有有益的思想交流。

电脑科学和软体工程的关系是一个有争议的话题，随后关于什麽是"软体工程"，电脑科学又该如何定义的争论使得情况更加混乱。David Parnas从其它工程和科学学科之间的关系得到啓示，宣称电脑科学的主要重点总的来说是研究计算的性质，而软体工程的主要重点是具体的计算设计，以达到实用的目的，这样便构成了两个独立但又互补的学科。

人工智慧

主条目:人工智慧

这个电脑科学分支旨在创造可以解决计算问题，以及像动物和人类一样思考与交流的人造系统。无论是在理论还是套用上，都要求研究者在多个学科领域具备细致的、综合的专长，比如套用数学，逻辑，符号学，电机工程学，精神哲学，神经生理学和社会智力，用于推动智慧型研究领域，或者被套用到其它需要计算理解与建模的学科领域，如金融或是物理科学。人工智慧领域开始变得正式源于Alan Turing这位人工智慧先驱提出了图灵试验，以回答这样一个终极问题:"电脑能够思考吗?"

机器翻译

主条目:机器翻译

1947年，美国数学家、工程师沃伦·韦弗与英国物理学家、工程师安德鲁·布思提出了以电脑进行翻译(简称"机译")的构想，机器翻译从此步入历史舞台，并走过了一条曲折而漫长的发展道路。机译被列为21世纪世界十大科技难题。与此同时，机译技术也拥有巨大的套用需求。

机译消除了不同文字和语言间的隔阂，堪称高科技造福人类之举。但机译的译文质量长期以来一直是个问题，离理想目标仍相差甚远。中国数学家、语言学家周海中教授认为，在人类尚未明了大脑是如何进行语言的模糊识别和逻辑判断的情况下，机译要想达到"信、达、雅"的程度是不可能的。这一观点恐怕道出了製约译文质量的瓶颈所在。

电脑体系结构与工程

主条目:电脑体系结构和电脑工程

电脑系统结构，或者数位电脑组织，是一个电脑系统的概念设计和根本运作结构。它主要侧重于CPU的内部执行和记忆体访问地址。这个领域经常涉及电脑工程和电子工程学科，选择和互连硬体组件以创造满足功能、性能和成本目标的电脑。

电脑图形与视觉

主条目:电脑图形学

电脑图形学是对于数位视觉内容的研究，涉及图像资料的合成和操作。它跟电脑科学的许多其它领域密切相关，包括电脑视觉、图像处理和计算几何，同时也被大量运用在特效和电子游戏。

电脑安全和密码学

主条目:电脑安全和密码学

电脑安全是电脑技术的一个分支，其目标包括保护信息免受未经授权的访问、中断和修改，同时为系统的预期使用者保持系统的可访问性和可用性。密码学是对于隐藏(加密)和破译(解密)信息的实践与研究。现代密码学主要跟电脑科学相关，很多加密和解密演算法都是基于它们的计算复杂性。

计算科学

计算科学(或者科学计算)是关注构建数学模型和量化分析技术的研究领域，同时通过电脑分析和解决科学问题。在实际使用中，它通常是电脑模拟和计算等形式在各个科学学科问题中的套用。

信息科学

主条目:信息科学

软体工程

主条目:软体工程

软体工程是对于设计、实现和修改软体的研究，以确保软体的高质量、适中的价格、可维护性，以及能够快速构建。它是一个系统的软体设计方法，涉及工程实践到软体的套用。

研究课题

①、电脑程式能做什麽和不能做什麽(可计算性);

②、如何使程式更高效的执行特定任务(演算法和复杂性理论);

③、程式如何存取不同类型的资料(资料结构和资料库);

④、程式如何显得更具有智慧型(人工智慧);

⑤、人类如何与程式沟通(人机互动和人机介面)。

系统分类

电脑系统可划分为软体系统与硬体系统两大类。

硬体

结构控製和指令系统

演算法和逻辑结构

存储器结构

冯·诺伊曼结构

哈佛结构

输入/输出和资料通信

数位逻辑

逻辑设计

积体电路

电脑系统组织

电脑系统结构

电脑网路

分散式计算

网路安全

电脑系统实现

软体

系统软体

作业系统

编译器

套用软体

电脑游戏

办公自动化

网路软体

CAD软体

电脑程式

程式设计和程式设计实践

面向对象技术

程式语言

软体工程

软体复用

驱动程式

电脑模拟

程式设计方法学

资料和信息系统

资料结构

资料存储表示

资料加密

资料压缩

编码与资讯理论

档案

信息系统

管理信息系统

决策支持系统- 专家系统

资料库

信息存储和资料存取

信息互动与表达

主要的研究领域

形式化基础

逻辑学

谓词逻辑

模态逻辑

时序逻辑

描述逻辑

数学

泛代数

递归论

模型论

概率论和数理统计

逻辑代数

布尔代数

离散数学

组合数学

图论

网论

资讯理论

理论电脑科学

形式语言

自动机

可计算性

演算法

计算复杂性

描述复杂性

编译器

程式设计理论

资讯理论

类型理论

指称语义

微程式

遗传演算法

并行计算

计算方法学

人工智慧

机器翻译

电脑图形学

图像处理与电脑视觉

模式识别

语音识别

文字识别

签名识别

人脸识别

指纹识别

仿真与建模

数位信号处理

文档与文本处理

电脑套用

数值计算

数值分析

定理机器证明

电脑代数

工程计算

电脑化学

电脑物理

生物信息论

计算生物学

非数值计算

工厂自动化

办公室自动化

人工智慧

信息存储与检索

符号语言处理

电脑辅助科学

电脑辅助设计

电脑辅助教学

电脑辅助管理

电脑辅助软体工程

机器人学

多媒体技术

人机互动

电子商务

特定技术

测试基準

机器视觉

资料压缩

软体设计模式

数位信号处理

档案格式

信息安全

国际网际网路络

超大规模积体电路设计

网路传输协定

网路处理器技术

整数运算器

浮点运算器

矩阵运算处理器

格线

计算科学史

电脑历史

软体业历史

编程思想

专业院校

美国开设电脑科学专业的院校

普渡大学西拉法叶分校，弗吉尼亚大学，密西根大学安娜堡分校，乔治城大学，维克森林大学，耶鲁大学，哥伦比亚大学，华盛顿大学，卡内基梅隆大学，乔治亚理工学院，加州理工学院，麻省理工学院，斯坦福大学，加州大学伯克利分校，伊利诺伊大学香槟分校，威斯康星大学麦迪逊分校，伦斯勒理工学院，哈佛大学，俄勒冈大学。

发展历史

电脑科学中的理论部分在第一台数位电脑出现以前就已存在。电脑科学根植于电子工程、数学和语言学，是科学、工程和艺术的结晶。它在20世纪最后的三十年间兴起成为一门独立的学科，并发展出自己的方法与术语。

30年代

英国数学家A.M.图灵和美国数学家E.L.波斯特几乎同时提出了理想电脑的概念(图灵提出的那种理想机在后来的文献中称为图灵机)。

40年代

数位电脑产生后，计算技术(即电脑设计技术与程式设计技术)和有关电脑的理论研究开始得到发展。这方面构成了所说的理论电脑科学。至于图灵机理论，则可以看作是这一学科形成前的阶段。至于"电脑科学"一词则到60年代初才出现，此后各国始在大学中设定电脑科学系。学科内容电脑科学是一门年轻的科学，它究竟包括哪些内容,还没有一致公认的看法。一般认为,电脑科学主要包括理论电脑科学、电脑系统结构、软体工程的一部分和人工智慧。理论电脑科学理论电脑科学是在20世纪30年代发展起来的。40年代机电的与电子的电脑出现后，关于现实电脑及其程式的数学模型性质的研究以及计算复杂性(早期称作计算难度)的研究迅速发展起来，形成自动机论、形式语言理论、程式设计理论、演算法设计与分析和计算复杂性理论几个领域。电脑系统结构

50年代

50年代以来，电脑的性能在计算速度和编址空间方面已提高了几个数量级。但大部分是通过元件更新而获得的。在系统结构方面基本上仍是属于40年代后期形成的存储程式型，即所谓诺伊曼型机器。这种结构的主要特点是它属于控製流型。在这种结构中，一项计算先做什麽后做什麽是事先确定了的，程式中指令的顺序是事先确定了的。为了在电脑的性能方面取得大的进展，需要突破这种旧的形式。电脑系统结构方面的重要课题之一，是探索非诺伊曼型机器的设计思想。在非诺伊曼型机器中，有一种是70年代初提出的资料流机器(又名资料驱动机器)。美国、苏联和英国都已製成这种机器。这种机器的特点是，在一项计算中先做什麽后做什麽不是事先确定，所执行的指令是动态排序的。排序的原则是运算元已备妥的先做，因而称作资料驱动机器。这种类型的机器更便于实现并行计算。软体工程程式设计在相当长的时间内是一种类似"手艺"而不是类似现代工程的技术。

60年代

60年代以来出现了大程式。这些大程式的可靠性很难保证。到60年代后期，西方国家出现了"软体危机"。这是指有些程式过于庞大(包含几十万条以至几百万条指令)，成本过高而可靠性则比较差。于是提出了软体工程的概念，目的在于使软体开发遵守严格的规範，使用一套可靠的方法，从而保证质量。现代软体工程的方向是形式化和自动化，而形式化的目的在于自动化。这裏所说的自动化就是将程式设计中可以由机器来完成的工作，尽量交给机器去做。中心课题之一是程式工具和环境的研究。程式工具是指辅助人编程式的程式，如编译程式、编辑程式、排错程式等;程式环境则是指一套结合起来使用的用来辅助人编程式的程式工具。人工智慧用电脑模拟人的智慧型，特别是模拟思维活动的技术及其有关理论。由于人的思维活动离不开语言,而且人对于某一类问题进行思索和探索解法时,总是需要以关于这一类问题的基本知识(专业知识或常识)作为出发点。于是，知识表示和机器对自然语言的理解就构成人工智慧的两个重要领域。所谓知识表示，是指将原来用自然语言表示的知识转换成用符号语言表示的，从而可以储存在机器内供机器使用的知识。人工智慧的研究角度有探索法的角度和演算法的角度。通常所说的解题演算法是指机械的和总是有结果的方法，而这裏所说的演算法却是广义的，包括那些机械的而在使用时不一定有结果的演算法。这种方法时常称作半可判定的方法。

人在解决问题时，时常採用探索法。这种方法具有"试错法"的性质，也就是说，试验若干条途径，一条路走不通时再试另一条，直到问题得到解决时为止。机器可以模拟人用探索法解题的思维活动。但由于可能途径的数目非常之大，不可能进行穷举式的探索。人一般是只选出一些最有希望得到结果的途径去进行探索。人的这种能力，就是进行创造性思维的能力。这是机器极难模拟的事情。採用演算法角度，使用特定的解题演算法或半可判定的方法时，会遇到另一方面的困难。那就是当问题的复杂程度较高时(比如说是指数的)，即使问题是有结果的，机器也无法在实际可行的时间内得到结果。在电脑出现的初期，人们曾寄希望于机器的高速度，以为在模拟人的思维时，机器可能用它的高速度来换取它所不具有的创造性思维。但通过"组合性爆炸"问题("组合性爆炸"是指一些组合数学中的问题，在参数增大时，计算时间的成长率时常是指数的，甚至高于指数)，人们认识到，单纯靠速度不能绕过组合性爆炸所产生的障碍。有无办法来克服这种困难，尚有待于进一步研究。与其他学科的关系电脑是由物理元件构成的,迄今主要是由电子元件构成的。因此，物理学的一些分支和电子工程便构成电脑科学的基础。同时，电脑科学在一定意义上是演算法的科学，而演算法是一个数学概念。因此，数学的某些分支如演算法理论(即可算性理论，又名递归函式论)也构成电脑科学的基础。但电脑科学已发展成为一门独立的技术科学，既不是电子学的一个分支，也不是数学的一个分支。这是就这个学科的整体而言。至于理论电脑科学，由于它可以看作是电脑科学的数学基础，在一定意义上，可以看作是数学的一个分支。另一个与电脑科学有密切关系的学科是控製论。控製论作为套用数学方法来研究机械系统和生命系统中的控製和通信现象的学科，同电脑科学有内容上的交叉，但后者不是它的一部分。自从40年代製成数位电脑以来，电脑的性能有了很大的提高。但在系统结构方面变化不大。一些计算技术发达国家正在研製新一代的电脑。这种电脑的系统结构将与过去40年的机器很不相同，所用的程式语言也将是新型的。电脑科学将研究由此出现的新问题，如有关并行计算的问题。

对计算的数学性质的研究大都还是关于串列计算的，对并行计算性质的研究自70年代才发展起来，预计将成为电脑科学的中心课题之一。另一个问题是程式设计的自动化问题。在程式设计方面，明显的趋势是将机器能做的尽量交给机器去做。程式环境的研究构成了软体工程的一个中心课题。形式化方法越来越受到重视，因为它是提高自动化程度所必需的。

早期，虽然英国的剑桥大学和其他大学已经开始教授电脑科学课程，但它只被视为数学或工程学的一个分支，并非独立的学科。剑桥大学声称有世界上第一个传授计算的资格。世界上第一个电脑科学系是由美国的普渡大学在1962年设立，第一个电脑学院于1980年由美国的东北大学设立。多数大学都把电脑科学系列为独立的部门，一部分将它与工程系、套用数学系或其他学科联合。