[关闭]
@devilogic 2019-03-10T09:07:26.000000Z 字数 5752 阅读 808

计算机程序设计艺术研修笔记(1.1 算法)

TAOCP


这节主要涉及下面三个内容。

  1. 算法(algorithm)一词的由来
  2. 算法的使用集合论的一个表示
  3. 算法的一个限制表示

这里有趣的是使用集合论的形式来定义计算,以及对于涉及仅是某种初等运算的举例表示,从中可以看出从一个数学家的角度来思考事物,作者从日常对象中进行抽象并形成理论,这是科学家的一种思考方式,将具体的对象抽象化、系统化。将简单变复杂是科学家的想法。工程师的角度愿意将复杂的问题变简单,便于实现。

我们形式地定义一个计算方法为一个四元组,其中是包含子集的一个集合,而是从到其自身的一个函数。其次,应保持逐点不动;即,对于中的所有元素应等于。四个量分别用于表示计算的状态输入输出以及计算规则。集合中的每一个输入定义一个计算序列如下:


如果是使中最小的整数,就说计算序列在步中终止,而且在此情况下,说从产生出输出(注意,如果中,则也是。因为在这样的情况下,。)某些计算序列可能永不终止;一个算法是对于中所有的在有限多步中终止的计算方法。

以上是摘自第一卷的第7页,主要是将算法这一个抽象概念符号化的一个表示。这里还比较容易理解,就是用集合表示算法,难理解的是这句:“注意,如果中,则也是。因为在这样的情况下,。”。这里应该是指得算法的收敛性。在之前作者提出了算法所要具备的五个特征:

  1. 有限性
  2. 确定性
  3. 输入
  4. 输出
  5. 能行性

以上描述覆盖了个特征。对算法这个概念的表述进行了能行性的限制。
这里的应等于指得是通过计算得到的值也在同一空间内,有域的概念在里面。

如果我们希望对算法的概念加上限制,使得它仅涉及初等的运算,我们就可以对加上一些限制。比如说,令是字母的有限集合,并令上的所有串的集合(即所有有序序列的集合,其中 且对于中)。想法是对计算的状态进行编码使得它们可以由的串来表示。现在设是非负整数,而是所有的集合,其中中,而是一个整数,;设的子集,设的子集。如果都是中的串,我们说如果对于串的形式,则中出现。为了完成我们的定义,令是对于,由串和整数所定义的下列类型的一个函数:

,如果不在中出现;
,如果是使最短的串;

以上指明了是初等运算,这里可以理解为线性运算,非线性的组合应该会使得结果不在定义的计算机状态全集内,而表示了通过初等运算可以组成的所有得到的状态。这个二元组,表示当前的计算机状态,而应该是表示算法运行到第几次。的时的计算状态,也就是初始状态,而表示的计算状态也就是算法结束时的状态,也就是输出。随后定义了一个算法的完成状态就是定义的最终输出是由目标状态以及的一个组合来表示。最后定义了三种算法的结果。一、算法正常运行,但是未找到有效解。二、算法正常运行,找到有效解。三、算法遍历完所有的参数空间(这里由的步数来指代)但是未找到解。
可以看出所有大师的一个思想方式,将具体的事物进行抽象,抽象之后进行符号化,从而可以使得事物可以满足某种运算规律,最后形成一套系统。
具体事物->抽象->符号化->可计算性->新的系统,这也是有特殊到一般的要给过程。

习题

正文中说明了如何使用替代符号,通过设置来交换变量的值。说明如何通过一系列的替代,把四个变量的值重新安排成。换言之,的新值是原来的值,等等。试使用最少的替代次数。

解:

这是一个左移操作,需要次。

证明,在步骤开始时,总是大于的,除了这一步头一次出现时可能出现相反情况外。

这里首先列出算法

算法()(欧几里得算法) 给定两个正整数,求它们得最大公因子,即能够同时整除的最大正整数。
[求余数] 以并令为所得余数。(我们将有。)
[余数为零?] 若,算法结束,即为答案。
[减少] 置,并返回步骤

证明:
中如果,如果这里的等号成立,那么余数,算法结束,如果是的情况,则它们的余数本身,进入到中,, 其中, 相当于在中完成了交换。
中如果,根据余数必定小于除数的定理。则在中永远保证了的交换。

(为了提高效率)改变算法使得像这样平凡的替代运算都加以避免。以算法的风格来写出这个新算法,并称之为算法

解:
算法() 给定两个正整数,求它们得最大公因子,即能够同时整除的最大正整数。
[求余数] 以并令为所得余数。(我们将有。)
[余数为零?] 若,算法结束,即为答案。
[求余数] 以并令为所得余数。(我们将有。)
[余数为零?] 若,算法结束,即为答案。
[跳转到求余数] 跳转到流程

的最大公因子是多少?
解:

证明出现前言后的“阅读本套书的流程”,按我们给出的五条准则的三条,实际上不是一个真正的算法!并指出它和算法之间格式上的差别。

本书给出了算法的五项特性:一、有限性,二、确定性,三、输入,四、输出,五、能行性。

证明:
阅读流程并不是有限的,因为并无一个明确退出算法的步骤。因为无法合理的评估阅读这一事件的完成的具体时间,因此它并非确定的。其次阅读流程并不一个明确的输入与输出。由于无明确退出的步骤,以及无法评估具体月底某节的具体时间,那么并不能通过纸笔进行手工运算来确定算法,因此它是不可行的。综上所述本书的阅读流程并不是一个真正的算法。

时,执行步骤的平均次数是多少?
解:
平均次数就是遍历的全部情况后除以当前遍历的次数。根据同余定理,这里当后会形成一个循环。,所以当时,的执行次数都相同。这里仅需要遍历即可。而的取模与的次数一致。这里可以得到一组运行的平均次数:

无论有多大,我们都可以将它以进行分组。由于,所以这里自然的分为组。最后的余数可以想想它的值是小于的,但是这里的是不确定,除去最后整除的数字。最多超不过。综上所述我们可以得出当的平均运行次数的上下限:

上式中上界为
这里使用来替代来替代,那么在某个固定数下,其通解形式为:

其中是在固定下的常量。

假设已知而允许取遍所有的正整数;令是在算法中执行步骤的平均次数。证明是明确定义的。有什么关系吗?

题目中所说的是明确定义的,这里理解为是固定的。不会出现值不确定的情况。

证明:
这里分为两个阶段来讨论。当取遍的过程中,,当
时,这里需要考虑两种情况,一种是可以被整除,一种是不可以。前者的平均次数为,后者相当于当时题目中的,但是排除了整除的情况,所以这里,其中的表示在固定下的取值。综上所述,当时:


时,也分为两种情况,一种是可以被整除,一种是不可以。那么前者的平均次数为,而后者由于,则必执行一次,在中进行交换,同理
综合以上两种情况的平均次数是一样的。固定一方,取另外一边的所有正整数情况。都会出现一方比另外一方:等于三种情况。如果出现除数大于被除数而在都会进行交换。所以两者没有区别,但是由于一开始的,所以必然会执行一次。所以:

通过描述等式中的,给出计算正整数的最大公因子的一个“能行的”形式算法。令输入由串表示,即后边跟着。试尽可能简单地给出你的解。[提示:使用算法,但替代步骤中的除法,置。]

这道题感觉是要探讨整数的素数分解的算法。从题目所说的:“令输入由串表示”这句话来看。整数分解有非常多的算法,而现代密码学的基础也是基于大整数难以分解的基础上。我之前写过一篇对最新素数分解算法AKS分析的文章玩命的销售日志 2017.10.23。这篇论文证明了在多项式时间下可以完成对大整数的分解并提出了一套基于多项式分解的算法。
这道题我确实不知道应该如何下手,主要是理解不了题目的意思。所以这边翻看了答案,帮助理解题意。

解:

。这个算法将以字符串结束。

让我们从答案来理解一下题意。

给定两个正整数,求它们得最大公因子,即能够同时整除的最大正整数。
[求余数] 。(我们将有。)
[余数为零?] 若,算法结束,即为答案。
[减少] 置,并返回步骤

假设是计算方法。例如:可代表等式中的算法,但在数量上要加限制,而可代表实现算法的计算机程序。(因此可以是机器的所有状态的集合,即它的内存和寄存器所有可能的配置;可以是单个机器动作的定义;可以是初始状态,包括确定最大公因子的程序以及的值。)
试表述“的表示”或“模拟”的概念的集合论定义。这在直观上意味着的任何计算序列都由加以模拟,除在计算中采用更多的步骤以及在它的状态中它可能保留更多的信息外。(我们因此得到对于“程序是算法的一个实现”这一语句的一个严格的解释。)

涉及的书籍

the_theory_of_algorithms.jpg-12.5kB

The Theory of Algorithms

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注