1.1 RAM模型的引入
1.1.1 计算的基本概念计算技术已经渗透到我们日常生活的方方面面，显著地改变了我们的生活。计算技术的广泛应用与巨大成功让我们不禁思考：“为什么计算机似乎无所不能。”例如，我们平时的工作、娱乐、交流都得益于计算机的支持。但是经过稍加深入的思考，我们则可以提出一个更加深入的问题：“为什么有些事情对人来说不难，而对计算机来说却非常困难；反之亦然，为什么有些事情对计算机来说很容易，而对人来说却非常困难。”例如，我们很容易理解一个人所讲的话，这对计算机来说却十分困难。再例如，从海量的歌曲信息中查找某首特定的歌曲对于计算机来说很容易，而对于人来说却非常困难；但是歌曲是由人来谱曲的，而对于计算机来说，哪怕“创作”很短的一段曲调都是非常困难的事情。上述问题与计算技术的本质特征紧密关联。计算的首要使能技术(enabling technology)是0/1编码。所有需要计算机处理的信息均首先进行0/1比特“编码”，然后以0/1比特的形式进行处理，最终再从0/1比特“解码”为用户易于理解的形式输出。能够进行0/1编解码的信息均可以用计算机进行处理，而计算机几乎无所不能的原因在于，很多常见的信息均可以有效地进行0/1编解码。例如，我们要拍一张照片发送给远在地球另一端的朋友。首先，数码相机将我们的物理影像信息0/1编码成特定格式的图片。这些包含影像信息的0/1比特则可以在计算设备上存储、复制，还可以通过网络进行传输。同时，收到这些0/1比特的人也可以用特定的软件将它解码并在显示设备上显示。0/1编解码的“魔术”使得计算机只需要通过种类有限的、较为简单的操作就可以对信息进行处理。计算机能完成复杂的任务，其关键不在于计算机能做各种复杂的操作，而是在于计算机能组合简单的操作来完成复杂的任务。因而我们总结计算的关键特征在于：基于有限种操作的灵活组合来完成复杂的计算任务。这可以用大家熟悉的积木作一个类比。在一套积木中，积木块的种类是有限的，但是积木块的组合方式却是任意多的(假设每一种积木块都有充分多个)。搭积木的意义在于用有限种类的积木块作出各种(创造性)组合。计算的这一本质特征也解释了计算机的擅长与不擅长：计算机并无创造能力，它只不过是根据预先指定的操作序列在依次执行。计算机的优势在于它执行操作的速度很快，不知疲倦，并且在高强度的工作负载下很少犯错(相对人而言)。这就解释了对于海量信息的简单处理(如检索海量歌曲信息)，计算机远比人类要擅长。但是对于自然语言的理解、艺术创作等“创造性”的事情，计算机就难以做到，或者说计算机必须依赖人将这些创造性的事情先转换成简单操作的组合，计算机才能按照人的安排机械地完成。有了计算的基本概念，我们可以给算法下一个宏观的定义：算法就是一组计算机操作的序列，遵循算法的指示，计算机对任意合法输入执行一系列操作，并给出正确的输出。1.1.2 计算模型的基本概念通过上面对计算的基本概念的讨论，我们知道算法首先依赖于一台机器。机器能执行种类有限的操作(我们称之为指令)，但每个指令的执行次数可以是任意多的。算法描述了一种指令的序列，它能对任意合法的输入完成计算，给出正确的输出。基于上述算法与机器二者的关系，我们又可以引出一个更进一步的问题。具体而言，假设大家有计算机程序设计的基本知识与动手经验。回顾我们的编程活动，大家会发现：我们解决计算问题时的思考和处理是机器无关的、实现语言无关的。一方面，假设你会在普通的PC上对一组元素进行排序，现在把计算设备换成一部手机。如果你预先了解了手机编程的基础知识，那么你对于排序的思考和理解，可以帮助你很容易在新的手机平台上完成相应的排序程序。另一方面，假设你用C语言实现了一个排序算法，现在我们把实现语言换成Java。如果你充分了解Java语言的知识，那么你对于排序的思考和理解，可以帮助你很容易用新的Java语言实现同样的排序算法。我们可以从两个不同的角度来思考上述现象背后的原因。●自顶向下地看：我们掌握的是一种抽象的原则，它与具体的机器和语言是无关的。换成算法的语言来说，我们是在一台抽象的机器上完成了算法的设计与分析。当熟悉机器的细节和语言的细节时，我们可以很容易地将抽象的算法“实例化”(instantiate)成一个具体机器、具体语言的算法实现(程序)。●自底向上地看：虽然各种计算设备千差万别，但是我们可以在汇编语言的层次上思考它们的共通之处。不考虑体系结构的不同，不同机器的主要差别是寄存器数目和字长的不同。但是这些参数虽然不同，却都在一个接近的范围内。我们可以将每一种计算设备都看成这样一种机器，即提供一组基本操作，完成数学、逻辑计算和存储器访问。不同机器上的一个操作在另外一个机器上总可以用常数个操作来模拟。这样，不同具体机器的操作代价至多相差常数倍，它们在本质上是一样的。上面的论述中提到的“抽象的机器”就是计算模型（model of computation），它是抽象的算法设计与分析的基础。计算模型可以执行数学运算、逻辑运算、存储器访问等基本操作。它仅存在于我们的思维之中，但是它包含了计算设备进行计算的核心运作机理。提到计算模型，最有名的是图灵机 ?ttp://en.wikipedia.org/wiki/Turing_machine。 。 它是英国数学家阿兰・图灵于1936年提出的一种抽象计算模型。但是图灵机的描述能力过于强大而不便于使用。对于讲授算法设计与分析的基础知识而言，更合适的计算模型是简单易用的RAM模型。1.1.3 RAM模型我们使用RAM(Random Access Machine)模型作为我们讲解抽象的算法设计与分析的计算模型。根据上面的讨论，我们可以把RAM模型理解成一台抽象的逻辑上的计算机，其基本构成如图1.1所示。RAM模型包含一个只读的输入纸带和一个只写的输出纸带。输入纸带由一个个空位组成，每个空位存储一个整数。每当一个空位的值被读入后，读写头向右移动一个空位。输出纸带同样由多个空位组成，它开始全部为空。当写指令执行的时候，RAM模型首先在当前的空位写下数值，然后读写头向右移动一个空位。一旦某个值被写到纸带上，它不能够再被更改。存储空间由一系列的寄存器r0,r1,…,ri,…构成，每个寄存器可以存储一个任意大小的整数值。我们假设问题的规模不是特别大，能够在存储器中处理。同时我们假设计算所涉及的整数不是特别大，可以在机器的字长内表示。图1.1 RAM模型的基本构成RAM模型执行的程序不是存放在存储器内的，因而程序不能修改其自身。程序只是一组指令的序列，我们对RAM模型所执行指令的细节并不关心，只是将它们粗略地分为3类。●简单操作：RAM模型可以执行常见的简单操作(simple operation)。我们不详细讨论每个简单操作的细节，只是假设对于现实计算机上常见的、合理的简单操作RAM 模型都能完成。例如，在排序时，RAM 模型能完成两个待排元素的比较；在串匹配时，RAM模型能完成两个字符的比较；在图遍历时，能对一个节点染色等。●复杂操作：复杂操作主要包括“循环”和“子程序调用”，在分析这些复杂操作时，需要把它们分解成简单操作的组合。●存储访问：存储单元的读/写是简单操作。假设RAM模型有充分大的存储空间，并且每次存储访问操作需要单位时间。注意，从理论上讲我们可以将任意操作定义为简单操作。但是如果将一个实际很复杂的操作定义为简单操作，则得到的计算模型就会明显地偏离现实，未能对现实问题进行准确、有效的抽象，因而其本身就没有存在的意义。所以我们需要合理地使用定义RAM模型的简单操作的能力。在本书的讨论中，我们并不会显式地列出RAM模型所有的简单操作，而是以现实计算机的指令集为指导，针对不同的算法问题，约定合理的简单操作集。除了约定合理的简单操作集之外，即使针对一个简单操作，当操作数的值特别大时，我们还需要合理地度量它的代价。具体而言，上面使用的是单位代价RAM(unit-cost RAM，uniform RAM)模型，即每个简单操作，无论它的操作数多大，均可以在单位时间完成。当操作数特别大时，这一代价计算方式就不太合理。此时，一个更准确的方式是使用对数代价(log-cost)RAM 模型，即操作的代价与操作数的比特数成正比。为了表述方便，一般不作说明的时候我们均使用单位代价RAM 模型。同时我们会注意不滥用这一模型。在特定的问题中，我们会显式地说明需要使用对数代价RAM模型。例如，当算法的输入跟数值相关的时候，包括背包问题、数论相关的算法问题等， 我们往往需要使用对数代价RAM模型。1.1.4 计算模型的选择：易用性和精确性通过上面对RAM模型的介绍，我们可以很鲜明地感觉到RAM模型的特点：一方面它是简单易用的；另一方面它对诸多要素的刻画是比较粗略的。RAM模型正是在自身的易用性和建模的精确性这两个矛盾的方面做到了比较好的权衡。我们首先来看RAM模型的不精确性。在RAM模型中，很多特性各异的操作被统一抽象为简单操作，在后续的算法分析中，对它们的执行代价是不作区分的。这显然是一种简化处理。例如，两个数的加法和乘法都被抽象为简单操作，但是乘法操作一般比加法操作的代价要高一些。又例如，编译器对于循环操作的优化，以及多线程技术的使用，可以使某些复杂操作和一些简单操作之间并没有太大的差异。再例如，当存储空间特别大的时候，实际的存储系统往往要分级，而不同速度的存储介质（如缓存、内存、硬盘、网络存储）的访问代价是有显著差异的。即便上述3个实例(还有更多的例子)使得我们对RAM模型定义的3个关键假设(简单操作、复杂操作、存储访问)都不严格成立，但RAM模型仍然是我们讨论抽象的算法设计与分析的一个很好的载体。每个模型都有它的适用范围，作一个类比，我们经常会将地球表面建模为一个平面。这显然不是一种精确的建模，因为我们都知道地球表面是一个球面。因而在航海等活动中，这个模型是不适用的。但是，在诸如建一间房屋这样的活动中，平面模型又是一个简单实用的模型。定义RAM模型的核心是要在模型的易用性和精确性之间进行高效的权衡。虽然RAM模型的一些假设比较理想化，在现实中往往得不到完全的满足，但是在RAM 模型中进行的抽象和假设都是在一般意义下比较合理的。面对现实中的问题，RAM模型不会给出基本原则上错误的结论，只会在细节上有所不精确。RAM模型捕捉了算法设计与分析的本质，适合我们展开算法设计与分析基础知识的讨论。正是由于RAM模型上述种种不精确性，在特定的更深入的研究领域中，研究者设计了更精确的计算模型。除了前面提到的图灵机，我们再简要介绍两个面向具体领域的计算模型，以帮助大家更好地对照着理解RAM模型在易用性和精确性方面的权衡。●外部存储模型(external memory model)：RAM模型的一个重要的特点在于对数据存储的简单建模。存储空间原则上是无穷的，并且存储访问的代价是统一的。随着数据量越来越大，这一存储模型在很多场合下有严重的不足。存储海量数据往往需要一组多级的存储空间(memory hierarchy)，包括寄存器、(多层)缓存、内存、本地硬盘、网络存储等。每级存储的访问速度和存储容量有巨大的(经常超过100倍的)差异。针对数据密集型的应用，研究者提出了外部存储模型，对不同存储介质的不同访问代价作了更精细的建模。●PRAM(Parallel Random Access Machine)模型：随着多核处理器、并行计算、分布式计算等技术的发展，现代的计算设施越来越多地不再是简单的串行计算。但是RAM模型并不具备刻画并行分布式计算的能力。为此研究者基于RAM模型扩充出针对并行计算的PRAM 模型。PRAM模型中有多个处理器，均连接到一个共享内存上。处理器之间的通信是通过共享内存的读写来实现的，算法设计者需要处理并发读写的冲突。PRAM模型中没有建模通信的开销，因为通信完全是通过共享存储访问实现的。基于RAM模型这台“抽象的计算机”，我们可以讨论抽象的算法设计与分析：可以定义清楚什么是需要完成的计算任务(即算法问题)，进而可以论证这台机器需要以何种顺序执行哪些操作才能完成指定的任务(即算法设计)；还需要统计完成任务所需的开销(即算法分析)。
相关资源：HIMSS大中华区EMRAM评级模型与评级流程