计算机科学基础/什么是计算

什么是计算

在本课程中，我们将重点关注计算原理（重大理念），而不是计算机技术，计算机技术是原理的工具和应用。 计算 由一组原理或理念定义，这些原理或理念构成了基于这些原理创建的众多技术的基础。 技术可能是复杂的且不断发展变化的，但原理保持不变。 在课程的后半部分，我们将学习各种技术以展示计算的能力以及如何应用原理。

除了计算原理和技术之外，还有计算实践 - 专业人士为促进计算而做的事情。

右边的图表说明了计算原理和计算实践之间的区别。 原理是技术和实践的基础。 消费者通过为他们构建的各种任务的应用程序来利用计算的能力。 我们相信每个人都需要了解计算原理，因为这些原理具有广泛的适用性。 作为计算领域的专业人士，我们需要了解两端和中间的一切 - 实践（使计算有用和有效的活动和技能）。

在整本书中，我们将交替使用计算和 计算 这两个术语。

计算原理

计算从根本上来说是关于信息过程的。 计算的重大理念之一是信息过程可以通过纯粹的机械方式通过符号操作来执行。 执行计算的代理，无论是思考的人类还是机器（计算机），都无关紧要。 在本书的结尾，我们将看到这对所有现代计算机都是正确的 - 数字计算机根据指令盲目地操作两个符号（零和一）。

一个类比

来自“思考即计算”一书 的以下类比说明了这一理念。 想象一下我们有以下符号表。

	a	b	c	d	e	f	g	h	i	j
a	aa	ab	ac	ad	ae	af	ag	ah	ai	aj
b	ab	ac	ad	ae	af	ag	ah	ai	aj	ba
c	ac	ad	ae	af	ag	ah	ai	aj	ba	bb
d	ad	ae	af	ag	ah	ai	aj	ba	bb	bc
e	ae	af	ag	ah	ai	aj	ba	bb	bc	bd
f	af	ag	ah	ai	aj	ba	bb	bc	bd	be
g	ag	ah	ai	aj	ba	bb	bc	bd	be	bf
h	ah	ai	aj	ba	bb	bc	bd	be	bf	bg
i	ai	aj	ba	bb	bc	bd	be	bf	bg	bh
j	aj	ba	bb	bc	bd	be	bf	bg	bh	bi

这些符号可以是任何符号集，为了简单起见，我们选择英语字母表中的字母。 我们可以定义一个过程 P，它将两个符号（'a' 到 'j'）作为输入并生成同一集中两个符号作为输出。 在内部，该过程使用第一个输入符号来查找以相同符号开头的行，然后使用第二个输入符号来查找顶部具有相同符号的列，然后报告/返回交叉点的符号。 不难想象这样的表格查找过程可以由简单的代理（例如设备或机器）通过纯粹的机械方式（盲目地）完成。 当然，人类可以做到这一点，但这种类型的符号操作不需要人类智力。 从这个思想实验中可以得出两个结论

• 符号操作可以机械地完成。
• 执行操作的机器不需要知道符号的含义，也不需要知道操作的目的。

如果我们知道如何解释符号，这个过程是有意义的。 例如，如果符号 'a' 到 'j' 分别代表 0 到 9 的数量，那么此过程执行一位十进制加法。 例如，p(d, f) = p(3, 5) = ai = 08，这是 3+5 的正确结果。 下面的表格本质上与前面的表格相同，只是它使用了对人类有意义的符号。

	0	1	2	3	4	5	6	7	8	9
0	00	01	02	03	04	05	06	07	08	09
1	01	02	03	04	05	06	07	08	09	10
2	02	03	04	05	06	07	08	09	10	11
3	03	04	05	06	07	08	09	10	11	12
4	04	05	06	07	08	09	10	11	12	13
5	05	06	07	08	09	10	11	12	13	14
6	06	07	08	09	10	11	12	13	14	15
7	07	08	09	10	11	12	13	14	15	16
8	08	09	10	11	12	13	14	15	16	17
9	09	10	11	12	13	14	15	16	17	18

现在我们有了可以指示简单代理添加两个一位十进制数字的简单过程 P，我们可以设计一个新的过程 P1，该过程可以像下面图表中所示那样添加三个一位十进制数字。

新的过程 P1 使用三个 P 过程实例来添加三个十进制数字并返回两个数字作为结果。 我们可以将过程视为具有输入和输出的机器，线条是管道，允许符号从一个地方移动到另一个地方。 不难想象，可以执行 P 的代理可以执行 P1，因为 P1 完全由 P 组成。 请注意，虚线矩形代表由 P 实例组成的新的过程 P1，并且 P1 给出的样本输入的答案是正确的。 同样，在此过程中使用的符号可以是任何符号集，因为内部执行的是简单的表格查找。

现在想象一下，我们可以使用 P1 来构建更复杂的过程，例如下面图表中的过程 P2。

P2 使用 P1 来添加两个两位数，实际上我们可以简单地向设计中添加更多 P1 来处理任意数量的数字。

到目前为止，我们可以得出以下结论

• 任何可以执行 P 的机器都可以执行 P1、P2 等。
• 我们已经通过使过程更复杂来创建执行看似智能活动的程序，同时让简单的机器仍然可以完成这些程序。

如果我们遵循相同的推理思路，不难想象我们可以创建越来越复杂的过程来指示简单的机器做越来越智能的事情，例如

• 整数减法
• 比较两个整数（减法并检查结果的符号）
• 整数乘法（重复加法）
• 使用一对整数表示分数，并在它们上进行算术运算
• 使用整数矩阵表示方程组，并使用矩阵运算来求解它们
• 使用方程组来建模复杂的物理系统，并对这些系统进行数值模拟

总之，从这个例子中我们可以看到，简单的符号操作可以组装起来形成更大的过程，通过计算过程来执行惊人的活动。 这些活动不仅限于数值计算。 如果我们可以将抽象概念表示为符号（就像我们将抽象量表示为具体数字一样），并设计过程来根据概念之间的关系操作符号，那么我们可以将推理建模为计算过程。 这就是计算机科学的本质 - 具有两个基本要素的信息过程：表示和一组用于操作表示的规则。 请注意，这与电子设备或物理学无关。 执行这些过程的机器不需要知道符号的含义，也不需要知道为什么该过程会产生正确的结果。 机器只需要盲目地遵循过程（一组规则）。

例如，您可以阅读关于 查尔斯·巴贝奇 设计的可以对多项式函数进行制表的机械计算机（差分机）的信息

另一个类比

理查德·费曼 在他的计算机启发式讲座（1 小时 15 分钟）中使用了另一个类似的类比（文件管理员）来解释计算机从内部到外部的工作方式：http://www.youtube.com/watch?v=EKWGGDXe5MA

历史

现在我们已经了解了什么是计算，本质上是某种符号操作。 计算机执行惊人任务的能力取决于其根据定义良好的规则操作符号的能力。 事实上，数字计算机只操作两个符号 - 零和一。 计算的智能在于规则/程序的设计和实现。

在将来，当谈论计算机机器时，我们将看到计算机是根据这些原理构建的。

你可能想知道这些想法从哪里来。历史上许多人对计算和计算机的概念做出了重大贡献。德国哲学家戈特弗里德·莱布尼茨（1646-1716）被认为是第一个梦想将推理简化为计算并制造出能够执行这种计算的机器的人。他观察到，在算术中，我们用符号来表示抽象的量，并根据规则操纵这些符号以获得有用的结果。他梦想着，我们可以用符号来表示抽象的思想，并通过类似于我们在算术中进行的具体的符号操作，根据思想之间的逻辑来推理这些思想。这种操作能得到正确的结果，不是因为做操作的人很聪明，而是因为操作规则反映了数量之间的关系以及思想之间的逻辑关系。

由于莱布尼茨的梦想，现在我们有了计算机科学和称为计算机的通用机器。计算机从根本上来说是一种物理设备，它可以根据非常简单的逻辑规则操纵符号。几乎所有的计算机都是电子设备，因为用这种方式建造起来比较便宜和容易。计算机科学从根本上来说是关于信息处理（处理抽象思想）的，信息处理通过符号操作进行，符号操作遵循一个配方（一组规则）。这种配方也被称为算法。难怪有这么多计算机编程书籍被称为食谱 :) 在计算机科学中，我们研究如何表示信息，以及如何设计和应用算法以获得有意义的结果。通常有许多方法可以执行相同的任务。比较算法以进行评估被称为算法（复杂性）分析。将算法（配方）传达给计算机称为编程/软件开发。我们用来进行这种通信的语言被称为计算机编程语言。编程的产物是计算机程序或软件。我们在软件开发过程中尝试应用的工程学科，以生产高质量的软件，被称为软件工程。所以计算机科学更多地是关于解决问题，而不是计算机。计算科学可能是这个学科更合适的名称。

计算实践

原则是在计算的各个方面都渗透的基本思想。实践不是原则，但非常有用，因为它们可以识别计算专业人士的核心实践。实践，有时也被称为“诀窍”，定义了一个人的技能组合和能力水平：初学者、熟练者和专家。计算的四个核心实践在计算大原则项目中被确定出来：

• 编程（包括多语言编程实践）
• 系统与系统思维
• 建模、验证、测试和度量
• 创新

编程是计算机科学不可分割的一部分，因为它让我们能够以具体的方式探索计算机科学中的抽象思想。它也是一个激动人心的创造过程，当我们能够让计算机做有用的事情时，它会带来极大的满足感。在本课程中，我们将使用一种非常高级的图形编程环境进行编程，以探索计算机科学中的思想。

唐纳德·克努特认为编程就像创作：写得好的程序让人们（包括你自己）读起来很愉快。他认为编程具有三方面的回报 

• 美丽的代码（审美）
• 做有用的工作（人道主义）
• 得到报酬（经济）

计算机编程本质上是教计算机如何做事。正如我们之前提到的，计算机是简单的机器，严格按照指令行事。为了让计算机执行正确的任务，我们程序中的指令必须正确且合乎逻辑。可以在计算机上执行的程序称为软件 - 充当计算机的大脑。有错误的软件被称为有bug（见这个名字的由来）的软件。在实际计算机上测试软件可以帮助捕获软件中的大多数bug。测试几乎可以立即反馈我们的程序的质量，以便我们可以修复bug并改进它。正因为如此，我们相信编程让我们成为更好的思考者和学习者。我们将看到为什么很难证明程序的正确性。