计算机程序设计艺术符号问题

Q =一组状态(因此 (s, j) 表示状态 s 在时间 j )
I =初始状态(因此要求 j == 0 )
Omega =最终状态(因此要求 j == N )
f =过渡函数

另外,没有三个函数 f 而是 f 由三个方程分段定义。

为了充分披露,我最近 wrote an article 对Knuth算法的形式定义的理解。下面的大部分内容只是文章的相关文本的拷贝/粘贴,这些文本深度地回答了您的第一个问题;

你的第一个问题是(q,i,_,_,f)

让我们正式定义一个计算方法为四重(q,i, _,_,f),其中q是包含子集i和_,_,_,f是 从q到自身的函数。

当Knuth将一种计算方法称为四重方法时,他只是简单地说一种计算方法由四个明确定义的部分组成。他把这四部分标为 (Q, I, Ω, f) . 然后他继续简单地描述这四个部分的每个部分。 I 和 Ω 是集合(事物的集合),以及 Q 也是包含集合中的内容的集合 我 和 艾斯 . 在这一点上,很容易错误地认为他是指 Q 仅包含集合 我 和 艾斯 没有别的了。但我们后来发现情况并非如此。最后他描述了 f 作为函数来自 Q 进入自身。这意味着什么 f 是从集合中获取元素输入的进程。 Q 并从返回或输出另一个元素 Q .

此外,f应保持和点固定;也就是说,f(q)应 所有元素q的q等于。

这实质上意味着,如果参数是集合(thing in)的成员或元素,我们的函数f返回的值将与其参数相同(即,值不会改变)。 艾斯 . 当Knuth在他的下一个声明中澄清时,这就更有意义了;剧透警报- 艾斯 是我们计算方法的一组可能的输出。一旦我们知道了这一点,它就更容易理解了。将输出返回到函数中不会改变它。

四个量q,i,_,f分别表示 计算、输入、输出和 计算规则。

所以 Q 一个集合,包含所有可能的计算状态,即输入、输出和其间所有阶段的所有可能变化。集合 我 包含所有可能的输入。集合 艾斯 包含所有可能的输出(很抱歉,如果我早点破坏了你的启示)。最后, f 表示计算规则;也就是说,应用到每个状态以获得下一个状态的进程,最终(希望)直到我们得到输出。

澄清, f 表示一个函数,该函数的输出是根据其可能的输入定义的。在这个特定的例子中,它只有三个可能的输出,在其他算法中可能有更多(或更少)的输出。那么,用这种方式定义算法的组件有什么目的呢?通过使用形式符号对它们进行定义,它们也可以在分析特定算法时进行分析和数学检查。

关于将算法视为一组字符串的问题

我回答 another question on this subject here . 但实际上,克努斯在这里所做的就是 Markov's algorithm 实现他已经描述的目标。有必要研究(并通过几个例子)马尔可夫算法来帮助您准确理解这里发生的事情。

工具书类

1. Markov's Algorithms Wiki
2. My Defining an Algorithm article.
3. Knuth the art of computer programming ex 1.1.8

我不是100%确定,但看起来q是0<=j<=n的所有有序对(s,j)的集合。这将是您的域。它是给定一些n和字符串s的所有可能状态的集合。

i是q的子集,其中所有有序对都包含j=0或初始状态。 ω是q的子集,其中所有的有序对都包含j=n,或者最终状态。

F是Q域上的实际函数。

编辑

把函数定义看作是沿着一个函数的线的东西,但是根据给定的输入,情况不同。想想你会用一种语言写的函数。前任:

tuple f(string s, int i)
{
    if (Tj not in s)
        (s, aj)
    else if ( p is shortest possible length such that s = pYjw)
        (pYjw,bj)
    else if ( i == N )
        (s, N)
}

另一个例子是 Fibonacci function definition . 看看这是怎么定义的? 有道理?

如果你能通过他在书中前面提到的欧几里得GCD算法。其思想是将每次迭代的开始标记为初始阶段,然后定义将在一次循环迭代(即n)中出现的状态数。现在,你们会记住,我们接受了这个答案,当m的余数除以n等于零时,停止了计算。也就是说,我们在搜索一个特定的字符串yj。当计算达到循环中的itz最后阶段时,它必然停止或重复。

记住,我们定义的是“计算方法”,而不是算法。什么是天真的计算方法?

一个“过程”除了可能缺乏有限性之外,具有算法的所有特征,可以称为计算方法。

简而言之,Q是一种计算方法。

Q = {all possible states of computations, I, Ω}
I = {all possible inputs}
Ω = {all possible outputs}
f = computational rule

f是从q到自身的函数。

f: Q  --->  Q
  [I]      [Ω]

F应离开 pointwise 固定,即:

f(q)=q,__q___ 注意,它不是任何不同的函数,而是同一个计算规则,只是分隔为

现在一个过程将有一个序列。显然,计算方法也必须有一个序列。 因此,

集合i中的每个输入x定义一个计算序列x _零 ,X _一 ,X _二 ,…,如下: X _零 =x和x _{K+ 1} = f(x) _K )对于k_0。

X如何 _零 = x? 不要忘记输入x是一个序列,所以初始输入序列是x _零 . 当我们处理一个序列时,当我们考虑“k”状态时,序列中元素的顺序和位置很重要。因此,计算规则f是这样的,k的位置或者更精确的单词“状态” ^钍 元素为k+1 ^钍 状态。 这样,我们可以单独地将函数应用于每个新状态,以获得随后的状态。

如果X _{K+ 1} 不在因此Knuth的措辞。

如果k是其中x的最小整数,则计算序列以k步终止。 _K 式中为_,在这种情况下,它被称为产生输出x _K 从X.

这就是计算方法的定义。计算规则就是算法。