0.1 什么是计算机科学
计算机科学是研究计算机及其周围各种现象和规律的科学，亦即研究计算机系统结构、软件系统、人工智能以及计算本身的性质和问题的学科。计算机是一种由电能驱动，在一定控制下能够自动进行算术和逻辑运算的电子设备，通俗地说就是能够进行计算的机器。计算机处理的对象都是信息，因而也可以说，计算机科学是研究信息处理的科学。
0.1.1 计算机科学的提出
自计算机发明以来，曾经围绕着计算机科学能否独立地成为一门学科产生过许多争论。最早的计算机科学学位课程是由美国普度大学于1962年开设的，随后斯坦福大学也开设了同样的学位课程。但针对“计算机科学”这一名称在当时引起了激烈的争论。毕竟当时的计算机主要用于数值计算，因此大多数科学家认为使用计算机仅仅是编程问题，不需要做深刻的科学思考，没有必要设立学位。总而言之，当时很多人认为计算机从本质上说是一种职业而非学科。
20世纪七八十年代计算技术得到了迅猛的发展并开始渗透到大多数学科领域，但以往激烈的争论仍在继续。计算机科学能否作为一门学科，计算机科学是理科还是工科或者只是一门技术？针对激烈的争论，1985年ACM和IEEE-CS联手组成攻关组开始了对计算作为一门学科的存在性证明，经过近4年的工作ACM攻关组提交了计算作为一门学科（Computing as a Discipline）的报告，完成了这一任务。该报告的主要内容刊登在1989年1月的《ACM通讯》（Communications of the ACM）杂志上。
ACM：计算机协会
ACM（Association for Computing Machinery）是一个国际科学教育计算机组织，它致力于发展在高级艺术、最新科学、工程技术和应用领域中的信息技术。它强调在专业领域或在社会感兴趣的领域中培养、发展开放式的信息交换，推动高级专业技术和通用标准发展。
ACM于1947年创立，是世界上第一个也一直是最大的科学教育计算机组织。其创立者和成员都是数学家和电子工程师，其中之一约翰?迈克利（John Mauchly）是ENIAC的发明家之一。成立这个组织的初衷是使计算机和新兴工业领域的科学家和技术人员能有一个交换信息、经验知识和创新思想的场合。经过几十年的发展，ACM的成员们为今天我们所称谓的“信息时代”做出了贡献。他们所取得的成就大部分出版在ACM印刷刊物上，并获得了ACM颁发的各种领域中的杰出贡献奖，如A. M. Turing（图灵）奖。
国际公认的计算机科学领域的最高荣誉是ACM设立的图灵奖，被誉为计算机科学的诺贝尔奖。它的获得者都是本领域最为出色的科学家和先驱。华人中首获图灵奖的是姚期智先生，他于2000年以其对计算理论做出的根本性的、意义重大的贡献而获得这一崇高荣誉。
IEEE-CS：电气电子工程师学会计算机分会
电气电子工程师学会（Institute of Electrical and Electronics Engineers）是一个国际性的电子技术与信息科学工程师的协会，是世界上最大的专业技术组织之一，拥有来自170多个国家的数十万会员。IEEE设有37个专业分会（Society）和3个联合会（Council），37个专业分会覆盖了电力、电子、信息等广泛领域，其中计算机分会（Computer Society，CS）有10多万会员。
IEEE是定位在“科学和教育，并直接面向电子电气工程、通信、计算机工程、计算机科学理论和原理研究，以及相关工程分支的艺术和科学的组织”。IEEE承担着多个科学期刊和会议组织者的角色。IEEE制定了全世界电子和电气还有计算机科学领域超过900个现行工业标准，是主要的国际标准机构。
ACM对计算机科学是这样定义的：计算机科学（计算学科）是对描述和变换信息的算法过程的系统研究，包括它的理论、分析、设计、有效性、实现和应用。他们认为，全部计算科学的基本问题是“什么能够（有效地）自动进行”。如今“计算机科学”一词是一个非常广泛的概念，在本书里，我们将其定义为“与计算机相关的问题”。
计算机科学是一门实用性很强、发展极其迅速的面向广大社会的学科，它建立在数学、电子学（特别是微电子学）、磁学、光学、精密机械等多门学科的基础之上。但是，它并不是简单地应用某些学科的知识，而是经过高度综合形成一整套有关信息表示、变换、存储、处理、控制和利用的理论、方法和技术。它是一门包含各种各样与计算和信息处理相关的主题的系统学科，从抽象的算法分析、形式化语法等，到更具体的主题如编程语言、程序设计、软件和硬件等。作为一门学科，它与数学、电子学、机械学和管理学等学科之间存在不同程度的交叉和覆盖。
0.1.2 计算机科学领域
计算机科学的分支领域包括：数值和符号计算、体系结构、数据结构和算法、操作系统、程序设计、软件工程、数据库和信息检索、计算理论和人工智能等。
- 数值和符号计算
本领域研究有效和精确地求解由数学模型所导出方程的一般方法。基本问题包括：怎样才能按照给定精度很快地解出给定类型的方程；怎样对方程进行符号运算，如积分、微分和化简为最小项等；怎样把这些问题的回答加入到有效、可靠、高质量的数学软件包中去。 - 体系结构
本领域主要研究将硬件和软件组织成有效和可靠系统的方法。基本问题包括：在一个机器中实现信息处理、存储和通信的最好方法是什么；如何设计和控制大的计算系统并且使它们能够在有错误和故障的情况下完成预期的工作；什么类型的体系结构能使许多处理单元有效地协同工作，实现并行计算；怎样测度计算机的性能。 - 数据结构和算法
本领域主要研究一些特定类型的问题及相对应的数据结构和解决方法。基本问题包括：对给定类型的问题，最好的算法是什么；它们要求多少存储空间和时间；空间与时间的折中方案是什么；存取数据最好的方法是什么；最好算法的最坏情况是什么；算法的运行按平均来说好到何种程度；算法的一般化程度，即什么类型的问题可以用类似的方法处理。 - 操作系统
本领域研究允许多种资源在程序执行中有效配合的控制机制。基本问题包括：在计算机系统运行的各级上可见的对象和允许的操作是什么；每一类资源允许有效使用的最小操作集是什么；怎样组织接口，使得用户只处理资源的抽象形式，而可以不管硬件的实际细节；对作业调度、内存管理、数据传输管理、外存资源管理、并发任务间的协调控制、可靠性和安全性的有效控制策略是什么；系统应该在什么功能上扩展；怎样组织分布式计算，使得许多由通信网络连接起来的自治机器能够参与同一计算。 - 程序设计
本领域研究执行算法的虚拟机的符号表达、算法和数据的符号表达以及从高级语言到机器码的有效翻译。基本问题包括：由一种语言给出的虚拟机的可能的组织（数据类型、运算、控制结构、引入新类型和运算的机制）是什么；这些抽象怎样在计算机上实现；用什么样的符号表达（语法）可以有效地指明计算机应该做什么。 - 软件工程
本领域研究满足技术要求、安全、可靠、可信的程序和大型软件系统的设计。基本问题包括：程序和系统开发背后的原理是什么；怎样证明程序或系统满足技术要求；怎样给定技术要求，使之不遗漏重要的情况，而且可以分析它的安全性；怎样使软件系统通过不同阶段不断改进；怎样使软件设计得易理解和易修改。 - 数据库和信息检索
本领域研究对大量持续的可分享的数据集合进行组织，使之能够有效地查询和刷新。基本问题包括：用什么样的模型化概念表示数据元和它们之间的关系；怎样把存储、定位、匹配和检索等基本操作组合成有效的事务处理；这些事务处理怎样与用户有效地交互；怎样把高级查询翻译成高性能的程序；什么样的机器结构能有效地检索和刷新；怎样保护数据，以抵制非法存取、泄露或破坏；怎样保护大型数据库不会由于同时刷新而导致不相容；当数据分散在许多机器上时，怎样使安全保护和访问性能二者得以兼顾；怎样索引和分类正文，以达到有效的检索。 - 人工智能和计算理论
本领域研究动物和人类（智能）行为模型。基本的问题包括：摹本的行为模型是什么，我们怎样建造机器来模拟；由规则赋值、推理、演绎和模式计算所描写的智能可以达到什么程度；由这些模型模拟行为的机器最终能达到什么性能；感知的数据应如何编码，使得类似的模式有类似的码字；驱动码怎样与感知码相联系；学习系统的体系结构如何，以及这些系统如何表示它们对外部世界的知识；怎样才能用有穷离散过程精确地逼近连续或无穷的过程；怎么处理逼近导致的误差等。
读者在阅读上述内容及本章其他内容时可能会发现某些概念或术语比较生僻，这些概念和术语我们将在以后的章节逐一讲述。
0.1.3 计算机与计算机模型
阿兰?图灵在1937年首次提出了一个通用的计算设备的设想。他设想所有的计算都可能在一种特殊的机器上执行，这就是现在所说的图灵机。尽管图灵对这样一种机器进行了数学上的描述，但他更关注计算的哲学定义，而不是建造一台真实的机器。他将该模型建立在人们进行计算过程的行为上，并将这些行为抽象到用于计算的机器模型中，这才真正地改变了世界。
通用图灵机是对现代计算机的首次描述，只要提供合适的程序该机器就能做任何运算。图灵机是计算机的功能抽象模型，它可以实现真实计算机的所有功能，但仅限于功能描述，对于性能描述需要采用其他方式。
基于通用图灵机建造的计算机都是在存储器中存储数据。在1944 ~ 1945年期间，冯?诺依曼指出，鉴于程序和数据在逻辑上是相同的，因此程序也能存储在计算机的存储器中。基于冯?诺依曼模型建造的计算机分为4个子系统：存储器、算术/逻辑单元、控制单元和输入/输出单元。冯?诺依曼模型中要求程序必须存储在内存中，这与早期只有数据才存储在存储器中的计算机结构完全不同。现代计算机的存储单元主要用来存储程序及其响应数据，这意味着数据和程序应该具有相同的格式，实际上它们都是以位模式（0和1序列）存储在内存中的。
计算机科学的大部分研究是基于“图灵机模型”和“冯?诺依曼模型”的，它们是绝大多数实际机器的计算模型。作为此模型的开山鼻祖，邱奇-图灵论题（Church-Turing Thesis）表明，尽管在计算的时间、空间效率上可能有所差异，现有的各种计算设备在计算能力上是却等同的。尽管这个理论通常被认为是计算机科学的基础，可是科学家也研究其他种类的机器，如在实际层面上的并行计算机以及在理论层面上的概率计算机和量子计算机等。在这个意义上来讲，计算机只是一种计算的工具。著名的计算机科学家 Dijkstra 有一句名言：“计算机科学之关注于计算机，并不甚于天文学之关注于望远镜。”
0.1.4 计算机科学中的经典问题
在社会发展过程中人们提出过许多具有深远意义的科学问题，它们对计算机科学的一些分支领域的形成和发展产生了重要的作用。另外，在计算机科学的发展过程中，为了便于理解有关问题和概念，人们还给出了不少反映该学科某一方面本质特征的典型实例。计算机科学中典型问题的提出及研究不仅有助于我们深刻地理解该学科，而且还对该学科的发展有着十分重要的推动作用。下面分别对图论中有代表性的哥尼斯堡七桥问题、算法与算法复杂性领域中有代表性的梵天塔问题（又译为汉诺塔问题），以及并发和互斥领域中的哲学家共餐问题进行分析。计算机科学中其他的典型问题请读者参考有关资料。
- 哥尼斯堡七桥问题
18世纪的东普鲁士有一座名叫哥尼斯堡（Konigsberg）的城堡，城中有一个岛。普雷格尔（Pregel）河的两条支流环绕其旁，并将整个城市分成北区、东区、南区和岛区4个区域。全城共有7座桥，这7座桥将4个城区连起来，如图 0?1所示。人们常通过这7座桥到各城区游玩，于是产生了一个有趣的数学难题：寻找不重复地走遍这7座桥回到原出发点的路径。该问题就是著名的哥尼斯堡七桥问题。
1736年大数学家列昂纳德?欧拉发表了关于哥尼斯堡七桥问题的论文——《与位置几何有关的一个问题的解》。他在文中指出，从一点出发不重复地走遍7座桥最后又回到原出发点是不可能的。为了解决哥尼斯堡七桥问题，欧拉用4个字母A、B、C、D代表4个城区并用7条线表示7座桥，如图0?2所示。
在图0?2中，只有4个点和7条线，这样做是基于问题本质来考虑的。它抽象出问题最本质的东西，忽视问题非本质的东西如桥的长度等，从而将哥尼斯堡七桥问题抽象为一个数学问题，即经过图中各边一次且仅一次的回路问题。欧拉在论文中论证了这样的回路是不存在的，后来人们把存在这种回路的图称为欧拉图。
欧拉在论文中将问题进行了一般化处理，即对给定的任意一个河道图与任意多座桥，判定是否能每座桥恰好走过一次，并用数学方法给出了3条判定的规则：
1）如果通奇数座桥的地方不止两个，满足要求的路线是找不到的。
2）如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线。
3）如果没有一个地方是通奇数座桥的，则无论从哪里出发所要求的路线都能实现。
欧拉的论文为图论的形成奠定了基础，今天图论已广泛地应用于运筹学、信息论、控制论等学科之中，并已成为我们对现实问题进行抽象的一个强有力的数学工具。随着计算机科学的发展，图论在计算机科学中的作用越来越大，同时图论本身也得到了充分的发展。
在图论中还有一个很著名的哈密尔顿回路问题。该问题是1859年爱尔兰著名学者威廉?哈密尔顿爵士（W. R. Hamilton）提出的一个数学问题。其大意是在某个图G中能不能找到这样的路径，即从一点出发，不重复地走过所有结点，最后又回到原出发点。哈密尔顿回路问题与欧拉回路问题看上去十分相似，然而又是完全不同的两个问题。哈密尔顿回路问题是访问每个结点一次，而欧拉回路问题是访问每条边一次。对图G是否存在，前面已给出欧拉回路问题的充分必要条件，而至今仍未找到满足哈密尔顿回路问题的充分必要条件。
- 梵天塔问题
相传印度教的天神梵天在创造地球这一世界时，建了一座神庙。神庙里竖立三根宝石柱子，柱子由一个铜座支撑。梵天将64个直径大小不一的金盘子，按照从大到小的顺序依次套放在第一根柱子上，形成一座金塔，如图0?3所示，即所谓的梵天塔，又称汉诺塔。天神让庙里的僧侣们将第一根柱子上的64个盘子，借助第二根柱子，全部移到第三根柱子上，即将整个塔迁移。同时定下3条规则：
1）每次只能移动一个盘子。
2）盘子只能在三根柱子上来回移动，不能放在他处。
3）在移动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上。
天神说，当这64个盘子全部移到第三根柱子上后，世界末日就要到了。这就是著名的梵天塔问题。
用计算机求解一个实际问题，首先要从这个实际问题中抽象出一个数学模型，然后设计一个解此数学模型的算法，最后根据算法编写程序，经过调试、编译、链接和运行，从而完成该问题的求解。从实际问题中抽象出一个数学模型的实质，其实就是用数学的方法抽取其主要的、本质的内容，最终实现对该问题的正确认识。
梵天塔问题是一个典型的只能用递归方法，而不能用其他方法来解决的问题。递归是计算机科学中的一个重要概念，所谓递归就是将一个较大的问题，归约为一个或多个子问题的求解方法。当然要求这些子问题比原问题简单一些，且在结构上与原问题相同。
根据递归方法，我们可以将64个盘子的梵天塔问题，转化为求解63个盘子的梵天塔问题。如果63个盘子的梵天塔问题能够解决，则可以先将63个盘子先移动到第二个柱子上，再将最后一个盘子直接移动到第三个柱子上，最后将63个盘子从第二个柱子移动到第三个柱子上，这样则可以解决64个盘子的梵天塔问题。依此类推，63个盘子的梵天塔问题，可以转化为62个盘子的梵天塔问题。62个盘子的梵天塔问题，又可以转化为61个盘子的梵天塔问题，直到1个盘子的梵天塔问题。再由1个盘子的梵天塔问题的求解求出2个盘子的梵天塔问题，直到解出64个盘子的梵天塔问题。
下面用C语言对该问题的求解算法进行描述：
hanoi(int n,char left,char middle,char right)
{
if(n==1) move(1,one,_,three);
else
{
hanoi(n-1,left,right,middle);
move(1,left,_,right);
hanoi(n-1,middle,left,right);
}
}代码中，n表示n个盘子的梵天塔问题，left表示第一个柱子，middle表示第二个柱子，right表示第三个柱子。函数hanoi(n-1,left,right,middle)表示n-1阶梵天塔，从第一个柱子借助第三个柱子先移到第二个柱子上，函数move(1,left,_,right)表示将第一个柱子上最后一个盘子，直接放到第三个柱子上。函数hanoi(n-1,middle,left,right)表示n-1个盘子，从第二个柱子借助第一个柱子移到第三个柱子上。
在以上C语言描述的算法基础上做适当扩充，就可以形成一个完整的程序。经过编译和链接后，计算机就可以执行这个程序，并严格地按照递归的方法将问题求解出来。现在的问题是，当n=64时，即有64个盘子时需要移动多少次盘子和要用多少时间。按照上面的算法，n个盘子的梵天塔问题需要移动的盘子数是n-1个盘子的梵天塔问题需要移动的盘子数的2倍加1。于是：
h(n)=2h(n-1)+1
=2 (2h (n-2)+1)+1
=22h(n-2)+2+1
=23h(n-3)+22+2+1
…
=2nh(0)+2n-1+…+22+2+1
=2n-1+…+22+2+1
=2n-1 因此要完成梵天塔的搬迁需要移动盘子的次数为264-1=18 446 744 073 709 551 615次。如果每秒移动一次，一年有31 536 000秒，则需要花费大约5 849亿年的时间。假定计算机能够每秒移动1 000万次，也需要花费大约58 490年的时间。
由此可见：理论上可以计算的问题，实际上并不一定能行。这属于算法复杂性方面的研究内容。
- 哲学家共餐问题
对哲学家共餐问题可以做这样的描述：5个哲学家围坐在一张圆桌旁，每个人的面前摆有一碗面条，碗的两旁各摆有一根筷子。假设哲学家的生活除了吃饭就是思考问题（这是一种抽象，即对该问题而言其他活动都无关紧要），而吃饭的时候，需要左手拿一根筷子，右手拿一根筷子，然后开始进餐。吃完后，又将筷子摆回原处继续思考问题。那么一个哲学家的生活进程可表示为：
1）思考问题。
2）饿了停止思考，左手拿一根筷子，如果左侧哲学家已持有它则需等待。
3）右手拿一根筷子，如果右侧哲学家已持有它则需等待。
4）进餐。
5）放右手筷子。
6）放左手筷子。
7）重新回到思考问题状态。
现在的问题是如何协调5个哲学家的生活进程，使得每一个哲学家最终都可以进餐。
考虑下面两种情况：
1）按哲学家的活动进程，当所有的哲学家都同时拿起左手筷子时，则所有的哲学家都将拿不到右手的筷子，并处于等待状态。那么哲学家都将无法进餐并最终饿死。
2）将哲学家的活动进程修改一下，变为当右手的筷子拿不到时，就放下左手的筷子。这种情况是不是就没有问题？不一定。因为可能在一个瞬间所有的哲学家都同时拿起左手的筷子，则自然拿不到右手的筷子，于是都同时放下左手的筷子。等一会儿又同时拿起左手的筷子，如此这样永远重复下去，则所有的哲学家一样无法进餐。
以上两个方面的问题其实反映的是程序并发执行时进程同步的两个问题：一个是死锁（Deadlock），另一个是饥饿（Starvation）。
为了提高系统的处理能力和机器的利用率，广泛地使用并发程序。因此必须彻底解决并发程序中的死锁和饥饿问题，于是人们将5个哲学家问题推广为更一般性的n个进程和m个共享资源的问题，并在研究过程中给出了解决这类问题的不少方法和工具，如基于Petri网的并发程序语言等。
与程序并发执行时进程同步有关的经典问题，还有读者/写者问题（Readers/Writers Problem）、理发师睡眠问题（Sleeping Barber Problem）。
针对以上提到的这些计算机科学中的典型问题，人们提出了很多解决方法，我们后面章节的学习当中将会分别介绍。希望读者在阅读本书的时候，主要领会解决这些问题的方法，甚至可以经常跳出本书的框架，结合自己的经验，试试看能否找到更好的方法。