### 1.1.1 计算机与计算 计算机是当代最伟大的发明之一。自从人类制造出第一台电子数字计算机，迄今已近 70 年。经过这么多年的发展，现在计算机已经应用到社会、生活的几乎每一个方面。人们用计 算机上网冲浪、写文章、打游戏或听歌看电影，机构用计算机管理企业、设计制造产品或从 事电子商务，大量机器被计算机控制，手机与电脑之间的差别越来越分不清，……总之计算 机似乎无处不在、无所不能。那么，计算机究竟是如何做到这一切的呢？为了回答这个问题， 需要了解计算机的工作原理。 提到计算机，人们头脑中会首先浮现出显示器、键盘、主机箱等一堆设备——计算机硬 件。了解一点硬件设备的基本知识自然是需要的，不过从学习用计算机解决问题这个层次看， 并不需要掌握多少底层硬件知识。在此我们仅介绍现代计算机的主要功能部件，目的是要了 解用计算机解决问题的计算机制。现代计算机的主要功能部件如图 1.1 所示。  CPU、指令与程序 中央处理单元（CPU）是计算机的计算部件，能够执行机器指令，或简称指令（instruction）。 每条指令表达的是对特定数据执行特定操作。某种 CPU 能执行的全体指令是由该 CPU 的制 造商设计并保持固定不变的，称为该 CPU 的指令集。例如，Intel 公司为它的 80x86 系列处 理器设计了上百条的指令。 外行人也许会以为，计算机功能如此强大，必定是因为它能执行功能强大的指令。然而 事实并非如此。即使是当今技术最先进、计算能力最强大的计算机，它的 CPU 也只会执行一 些非常简单的指令，例如将两个数相加、测试两个数是否相等、把数据放入指定的存储单元 等等。 由于每条机器指令都只能完成很简单的操作，因此仅靠少数几条指令是做不了什么复杂 的事情的。但是，如果将成千上万条简单指令组合起来，却能解决非常复杂的问题！亦即， 复杂操作可以通过执行按特定次序排列的许多简单操作而实现。这种由许多指令按次序排列 而成并交给计算机逐条执行的指令序列称为程序（program）。为了用计算机解决问题，把问 题的解法表达成一个指令序列（即程序）的过程，称为程序设计或编程（programming）。可 见，计算机所做的所有神奇的事情，都是靠一步一步执行的、平凡而乏味的简单指令序列做 到的。计算机一点也不神奇，它唯一会做的事情就是机械地执行预定的指令序列。 存储器 存储器是计算机的记忆部件，用于存储数据和程序。 存储器分为主存储器和次级存储器，它们是用不同的物理材料制造的。CPU 只能直接访 问主存储器，也只有主存储器才能提供与 CPU 相匹配的存取速度。但主存储器需要靠持续供 电来维持存储，一旦断电，存储的数据或程序就会消失。为了持久存储信息，可以使用即使 断电也能维持存储的次级存储器，如当前普遍使用的磁盘。CPU 不能直接访问次级存储器， 次级存储器上的数据或程序必须先送到主存储器中，才能被 CPU 存取或执行。次级存储器的 读写速度远远低于主存储器，这个差别极大地影响了用计算机解决问题时所使用的方法。 现代计算机在体系结构上的特点是：数据和程序都存储在主存储器中，CPU 通过访问主 存储器来取得待执行的指令和待处理的数据。这称为冯·诺伊曼（von Neumann）体系结构。 输入/输出设备 输入和输出设备提供了人与计算机进行交互的手段。我们通过输入设备向计算机输入信 息，计算机则通过输出设备将计算结果告诉我们。传统的输入设备有键盘和鼠标等，输出设 备有显示器和打印机等。现代的触摸屏则兼具输入和输出的功能。 计算 了解了计算机的组成，就能理解计算机解决问题的过程是怎样的。我们来看一个常见任 务——用计算机写文章——是如何解决的。为了解决这个问题，首先需要编写具有输入、编 辑、保存文章等功能的程序，例如微软公司的程序员们所写的 Word 程序。如果这个程序已 经存入我们计算机的次级存储器（磁盘），通过双击 Word 程序图标等方式可以启动这个程序， 导致该程序从磁盘被加载到主存储器中。然后 CPU 逐条取出该程序的指令并执行，直至最后 一条指令执行完毕，程序即告结束。在执行过程中，有些指令会导致与用户的交互，例如用 户利用键盘输入或删除文字，利用鼠标点击菜单进行存盘或打印等等。就这样，通过执行成 千上万条简单的指令，最终解决了用计算机写文章的问题。 针对一个问题，设计出解决问题的程序（指令序列），并由计算机来执行这个程序，这 就是计算（computation）。 通过计算，使得只会执行简单操作的计算机能够完成神奇的复杂任务，所以计算机的神 奇表现其实都是计算的威力。如果读者对计算的能力还有疑问，下面这个例子或许能打消这 个疑问。Lucy 是一个只学过加法的一年级小学生，她能完成一个乘法运算任务吗？答案是肯 定的！解决问题的关键在于编写出合适的指令序列让 Lucy 机械地执行。例如下列“程序” 就能使 Lucy 算出 m×n： ``` 在纸上写下 0，记住结果； 给所记结果加上第 1 个 n，记住结果； 给所记结果加上第 2 个 n，记住结果； …… 给所记结果加上第 m 个 n，记住结果。至此就得到了 m×n。 ``` 不难看出，这个指令序列的每一步都是 Lucy 能够做到的，因此最后确实能完成乘法运 算。这就是“计算”所带来的成果①。 计算机就是通过这样的“计算”来解决所有复杂问题的。执行大量简单指令组成的程序 虽然枯燥繁琐，但计算机作为一种机器，其特长正在于机械地、忠实地、不厌其烦地执行大 量简单指令！ > ① 当然，这种计算看上去就很繁琐，原因在于用到的基本指令（加法）太简单。如果 Lucy 学习了更“高级” 的指令（如乘法口诀等），就可以更快捷地完成乘法运算。 计算机的通用性 通过前面的介绍，可知计算机就是进行“计算”的机器。显然，这里的“计算”并不是日常说的数学计算。事实上，计算机在屏幕上显示信息，在 Word 文档中查找并替换文本， 播放 mp3 音乐，这些都是计算。 理解了计算机是如何计算的，也就能理解为什么计算机具有通用性，能解决各种不同类 型的问题。其中的奥秘就在于程序。如果想用计算机写文章，就将 Word 之类的程序加载到 主存中让 CPU 去执行，这时计算机就成了一台电子打字机；如果想用计算机听音乐，就将 Media Player 之类的程序加载到主存中让 CPU 去执行，这时计算机就成了一台音频播放机； 如果将 IE 之类的程序加载到主存中让 CPU 去执行，计算机就可以在互联网上浏览信息。总 之，一台计算机的硬件虽然固定不变，但通过加载执行不同的程序，就能实现不同的功能， 解决不同的问题。 我们平时说的计算机都是指通用计算机，能够安装执行各种不同的程序。其实在工业控 制和嵌入式设备等领域，也存在专用计算机，它们只执行预定的程序，从而实现固定的功能。 例如号称电脑控制的洗衣机，其实就是能执行预定程序的计算机。 计算机科学 为了更好地利用计算机解决问题，人们深入研究了关于计算的理论、方法和技术，形成 了专门研究计算的学问——计算机科学（computer science）①。 计算机科学包含很多内容，本书的主题是计算机科学家在用计算机解决问题时建立的一 些思想和方法，这些思想和方法普遍存在于计算机科学的各个分支之中。作为例子，我们来 看计算机科学家思考的一个根本问题：到底什么问题是计算机可计算的？一般人会以为，一 个问题能不能用计算机计算，取决于该计算机的计算能力；而计算机的计算能力又取决于 CPU 的运算速度、指令集、主存储器容量等硬件指标。真如此的话，显然巨型计算机应该具 有比微型计算机更强大的计算能力。然而，作为计算机科学理论基础的可计算性理论却揭示 了一个出人意料的结论：所有计算机的计算能力都是一样的！尽管不同计算机有不同的指令 集和不同性能的硬件，但一台计算机能解决的问题，另一台计算机肯定也能解决。