13

我刚开始阅读 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* 中的字符串,我们说 T 出现在 s 中,如果 s 对字符串 p 和 w 具有 pTw 的形式。

f(s,j) = (s,a j ) 如果 T j不在 s 中出现;
f(s,j) = (pY j w,b j ) 如果 p 是 s = pY j w的最短可能字符串
f(s,N) = (s,N)

我理解制作字符串集的概念,但不理解他在这里想说的所有内容。为什么我需要Q、I、Omega?f 真正向我解释了什么(为什么我需要 f 中的 3 个函数?)?

任何人都可以帮忙阐明一下吗?

4

5 回答 5

16
于 2015-02-22T15:36:33.873 回答
15

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

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

于 2009-02-19T18:35:12.360 回答
1

我不是 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)
}

另一个例子是斐波那契函数定义。看看这是怎么定义的?有道理?

于 2009-02-19T18:35:59.910 回答
1

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

于 2011-06-14T11:12:13.790 回答
1

remember we are defining a 'computational method' and not an algorithm. what is a computational method naively?

a "procedure" that has all characteristics of an algorithm except that it possibly lacks finiteness, may be called a computational method.

simply put Q is a computational method.

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

f is a function from Q into itself.

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

f should leave Ω pointwise fixed which means:

f(q) = q, ∀ q ∈ Ω note it is not any different function but the same computationalrule just seperated to Ω</p>

Now a procedure will have a sequence. And obviously, a computational method must also have a sequence. Hence,

Each input x in the set I defines a computational sequence x0, x1, x2, ..., as follows: x0 = x and xk+1 = f(xk) for k ≥ 0.

How x0 = x? Don't forget the input x is a sequence and so the initial input sequence would be x0. As we are dealing with a sequence, and when we are concerning about 'k' states, the order and the position of elements in the sequence matters. And so, the computational rule f is such that the position or more precise word 'state' of the kth element would be k+1th state. that way, we can seperately apply the function to each new state to get the state that follows.

if xk+1 is not in Ω, then it makes no sense by definition of a function. Hence the wording of Knuth.

The computational sequence is said to terminate in k steps if k is the smallest integer for which xk is in Ω and in this case, it is said to produce the output xk from x.

Thus this is the definition of a computational method. the computational rule is the algorithm.

于 2016-11-01T12:31:56.417 回答