1.1 计算机与算法

1.1.1 计算

计算首先是我们这门课程的直接研究对象和内容，也是我们这门课程的研究目的和目标。

对象：规律、一般性方法、技巧

目标：高效计算、低耗

绳索计算机

要求：通过直线l上给定的点A，作该直线的垂线。

过程：

计算机：长度为12 的绳索。

计算：重复机械的完成以上的过程。

尺规计算机

输入：任给平面上线段AB

输出：将其三等分的C和D点。

算法：

1.1.2 什么是算法？

计算=信息处理

借助某种工具，遵照一定规则，以明确而机械的形式进行

计算模型=计算机=信息处理工具

基于特定的计算模型，解决某一信息处理问题而设计的一个指令序列。

算法具备的要素：

输入：待处理的信息（问题）
输出：经处理的信息（答案）
正确性：的确可以解决指定的问题
确定性：任一算法都可以描述为一个由基本操作组成的序列
有穷性：对于任何输入，经有穷次基本操作，都可以得到输出
可行性：每一基本操作都可以实现，且在常数时间内完成

例如：如何把大象装进冰箱？

但是有一条是不能实现的：把大象赶进冰箱里面

1.1.3 有穷性

针对Hailstone sequence问题，详细介绍算法的有穷性。问题如下：

对于任何一个自然数都可以定义这样的序列：以递归的形式定义，实例如下：

以上这个程序未必是一个算法：无法证明其是有穷的。

补充：序列有时会下降有时会上升，虽然有可能持续下降，但是绝不会持续上升，原因是一个奇数乘3加1之后会成为偶数，再进行折半，而不会连续乘3加1。

程序未必是算法。程序如果要称作是一个算法，它就应该满足我们刚刚说过的有穷性。它对任何的输入，都应该能够在有限步之后退出返回。该程序对任何n都能做到这一点吗？这不取决于这个程序，而是取决于这个序列本身的定义。目前，这个问题还没有结论。

我们应该考虑的问题：

什么是好的算法？
什么是好的数据结构？
什么是好的计算过程？

算法：需要考虑如何设计、优化？

优劣：如何评判和比较好的算法？

1.1.4 好算法

正确：符合语法，能够编译、连接

正确处理简单输入
正确处理大规模输入
正确处理一般性的输入
正确处理退化的输入
正确处理任意合法的输入

健壮：能辨别不合法的输入并做适当处理，而不致非正常推出

可读：结构化+准确命名+注释+

效率（最重要）：速度尽可能快，存储空间尽可能少

Algorithm + Data Structures = Programs

(Algorithm + Data Structures)× Efficiency = Computation

1.1.5 复杂度的度量

算法分析：主要体现在两个方面

正确性：算法功能与问题要求是否一致

成本：运行时间 + 所需存储空间

特定算法+特定实例

定义： $T_{A}(P)$ =算法A求解问题实例P的计算成本

结论：问题实例的规模，往往是决定计算成本的主要因素

通常：规模接近，计算成本接近；规模扩大，计算成本也上升

特定算法+不同实例

$T_{A}(n)$ =用算法A求解某一问题规模为n 的实例（一类问题），所需的计算成本。讨论特定算法A（及对应的问题）时，简记 $T(n)$

观察：同一问题等规模的不同实例，计算成本不尽相同，甚至有是指差别。

特定问题+不同算法

同一问题通常有多种算法，如何评价其优劣？

最直接：实验统计，实际中不能足以反应算法的真正效率

可行方法：抽象出一个理想的平台或模型，不再依赖于具体的因素，从而直接而准确地描述，测量并评价算法。构建理想的平台或模型。

1.1.6 什么是图灵机？

图灵机模型具有以下要件：

Tape也就是带：通常称作纸带或磁带，被均匀地划分为一个一个的小格子，称作cell。每一个小格子上面都标注有某个字符，默认的初始情况下所有的格子中都标记有一个特定的符号，比如说我们这里约定是“﹟”号，所以相应的每个格中所标的字符，都是来自于一个字符表。而这个字符表的长度是有限的。

Head：头。在任何时刻Head，都是对准了Tape上的某一个cell，而整个的图灵机，按照一个节拍的节奏来运转，每经过一个节拍，这个头都可以向左或者是向右移动一个单元，转入下一个单元格。而在对准任何一个单元格的时候它都可以读取出这个单元格中所标注的那个字符。也可以修改这个单元格中所对应的字符。正因为这个原因，它确实应该叫作读写头。

具有两方面的功能：读和写。

State ：TM总是处于有限种状态中的某一种，每经过一个节拍，可（按照规则）转向另一个状态

规则：Transition Function：（q, c ; d, L/R, p）若当前状态为q且当前字符为c,则当前字符改写为d；转向左侧/右侧的领格；转入p状态，一旦转入特定的状态‘h'，则停机，计算任务完成。

实例：

如何利用图灵机来完成非负整数加1的功能？

约定：非负整数统一以二进制形式在纸带上用若干个单元表示。

要点：在其中的这样一个比特，从右向左，从最低位向更高位数，所能发现的第一个零比特。那么它后面那些比特都应该是1。我们要完成这项工作，实际上只需做这么样一件事，就是将这个比特后续的所有那些1 翻转为零。而原先最低位的这个零翻转为1。如下图所示。

转换过程：初始是向左状态，所对的字符是1，应该翻转为零，向左侧移动一步，继续保持原来的向左的状态。概括而言，扫描作为最低位那个零的，后缀的那些1比特将它们逐个的翻转为零，在这个过程中，保持图灵机向左的状态。如果我们终于不再碰到的是1，第一次碰到零，将这个零翻转为1。读写头开始向右。在此之前，原来的那些1比特都已经转化为了相应的零比特。将读写头完整的送回原来的位置，并停机。

为什么要把读写头复位到最初的位置？

规范，它有可能本身以后会成为一个算法的一部分，而那个算法在每次调用使用它之前，都会对它当时所处的整体状态，有一个严格的规范要求。