计算机编程艺术记号问题

Question

我刚刚开始阅读 TAOCP 第 1 卷，但无法理解其风格。

Knuth 提到一种计算方法是四元组（Q、I、Omega、f）——但我很难理解其中每一个的含义。 我理解他的第一个例子，但不理解他的第二个例子，

我正在看第三版的第8页。

---

在本章末尾处有一个讨论字符串集的算法。

（我已经用一些更容易输入的变量替换了希腊变量 - 抱歉）

令 A 为有限字母集，并令 A* 为 A 上所有字符串的集合。 这个想法是对计算的状态进行编码，以便它们由 A* 的字符串表示

Q = (s,j) where s is in A* and j is an integer, 0 <= j <= N 
I = subset of Q with j = 0
Omega = subset with j = N
f = function below  

（注意 p 和 w 是字符串） 如果 和 s 是 A* 中的字符串，如果 s 对于字符串 p 和 w 具有 pTw 形式，则我们说 T 出现在 s 中。

f(s,j) = (s,aj)             if Tj does not occur in s;
f(s,j) = (pYjw,bj)   if p is the shortest possible string for which s = pYjw
f(s,N) = (s,N)

我理解制作字符串集的概念，但不理解他在这里试图说的全部。 为什么我需要 Q、I、Omega？ f 真正向我解释的是什么（为什么 f 中需要 3 个函数？）？

任何人都可以帮忙阐明一些情况吗？

Answer 1

Q = 状态集（以便 (s, j) 表示 s 在时间 j 的状态）
I = 初始状态（因此要求 j == 0）
Omega = 最终状态（因此要求 j == N）
f = 转换函数

此外，不存在名为 f 的三个函数，而是 f 由三个方程分段定义。

Answer 2

为了充分披露，我最近写了一篇文章，关于理解 Knuth（示例前）的正式定义算法。 下面的大部分内容只是深入回答您的第一个问题的文章中相关文本的复制/粘贴；

您关于 (Q, I, Ω, f) 的第一个问题

---

让我们正式定义一个计算方法为四元组 (Q, I,
Ω, f)，其中 Q 是包含子集 I 和 Ω 的集合，f 是
从 Q 到自身的函数。

当 Knuth 将计算方法称为四元组时，他只是说计算方法由四个明确定义的部分组成。 他将这四个部分标记为(Q, I, Ω, f)。 然后他继续简要描述这个四元组的每个组成部分。 I 和 Ω 是集合（事物的集合），Q 也是包含集合 I< 中的事物的集合/code> 和 Ω。 此时，很容易错误地认为他的意思是 Q 仅包含集合 I 和 Ω 而没有其他内容。 但后来我们发现事实并非如此。 最后，他将 f 描述为从 Q 到自身的函数。 这意味着 f 是一个进程，它接受来自集合 Q 中的一个元素的输入，并返回或输出 Q 中的另一个元素。

此外，f 应该使 Ω 逐点固定； 也就是说，f(q) 应该
Ω 的所有元素 q 都相等。

这本质上意味着，如果参数是集合Ω（中的事物）的成员或元素，我们的函数 f 返回的内容将与其参数相同（即值不会改变） 。 当 Knuth 在他的下一个声明中做出澄清时，这就更有意义了； 剧透警告 - Ω 是我们计算方法的一组可能输出。 一旦我们知道了这一点，就更容易理解了。 将输出传递回我们的函数不会改变它。

四个量Q、I、Ω、f分别表示
计算、输入、输出和
计算规则。

所以Q是一个包含所有可能的计算状态的集合，即输入、输出以及其间所有阶段的所有可能的变化。 集合I包含所有可能的输入。 集合Ω包含所有可能的输出（很抱歉，如果我之前破坏了你的启示）。 最后，f代表计算规则； 也就是说，应用于每个状态的过程以获得下一个状态，最终（希望如此）直到我们得到输出。

---

为了澄清，f 表示一个函数，该函数的输出是根据其可能的输入定义的。 在此特定示例中，它仅具有三种可能的输出，并且在其他算法中可能具有更多（或更少）。 那么，以这种方式定义算法的组成部分的目的是什么？ 通过使用形式符号定义它们，在分析特定算法时也可以对它们进行分析和数学检查。

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

我回答了关于此主题的另一个问题。 但本质上，Knuth 在这里所做的是使用马尔可夫算法来实现他已经描述的内容。 值得研究（并研究一些示例）马尔可夫算法，以帮助您准确理解这里发生的情况。

参考文献

1. 马尔可夫算法 Wiki
2. 我的定义算法文章。
3. Knuth 计算机编程艺术 ex 1.1.8

Answer 3

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

I 是 Q 的子集，其中所有有序对都包含 J=0，或您的初始状态。
Omega 是 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)
}

另一个例子是斐波那契函数定义。 看看它是如何定义的？
合理？

Answer 4

如果你已经完成了他在书前面提到的欧几里得的最大公约数算法。 这个想法是将每次迭代的开始标记为初始阶段，然后定义循环的一次迭代中将出现的状态数（即 N）。 现在您会记得，我们接受了答案，并在 m 除以 n 的余数等于零时停止计算。 即我们正在搜索字符串 Yj 的特定出现位置。 当计算到达循环的最后阶段时，它必然会停止或重复。

Answer 5

请记住，我们正在定义“计算方法”而不是算法。 天真的计算方法是什么？

具有算法所有特征（除了可能缺乏有限性）的“过程”可以称为计算方法。

简单来说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^th 元素的位置或更精确的单词“state”将是 k+1^th 状态。
这样，我们可以将该函数单独应用于每个新状态以获得后续状态。

如果 x_k+1 不是 Ω，那么根据函数的定义它就没有意义。 这就是高德纳的措辞。

如果 k 是 x_k 为 Ω 的最小整数，则计算序列将在 k 步中终止，在这种情况下，据说会产生输出 x_k 来自 x。

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