计算机编程符号问题的艺术

我刚开始阅读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为字符串p,则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中使用3个函数？)??

任何人都可以帮忙解决一些问题

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

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

为了完整披露,我最近写了一篇关于理解Knuth(前例)正式定义算法的文章.下面的大部分内容只是文章中相关文字的复制/粘贴,深入回答了您的第一个问题;

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

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

当Knuth将计算方法称为四元组时,他只是说计算方法由四个明确定义的部分组成.他将这四个部分标记为(Q, I, ?, f).然后他继续简要描述这个四重奏的每个组成部分.I和?是一组(事物集合),并且Q也是一组其包含在所述组的东西I和?.在这一点上很容易误以为他的意思是Q只包含组I和?,没有别的.但我们后来发现事实并非如此.最后,他将其描述f为一种功能Q.这意味着这f是一个进程,它接受一个来自集合的元素的输入Q并返回或输出另一个元素Q.

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

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

四个量Q,I,Ω,f旨在分别表示计算的状态,输入,输出和计算规则.

因此Q,该集合包含计算的所有可能状态,即输入,输出和其间所有阶段的所有可能变化.该集I包含所有可能的输入.该集合?包含所有可能的输出(抱歉,如果我之前为您破坏了这个启示).最后,f代表计算规则; 也就是说,进程/ es应用于每个状态以获得下一个状态,最终(希望)直到我们获得输出.

为了澄清,f表示具有基于其可能输入定义的输出的单个函数.在此特定示例中,它只有三个可能的输出,并且在其他算法中可能有更多(或更少).那么,以这种方式定义算法组件的目的是什么呢？通过使用正式表示法定义它们,它们也可以在分析特定算法时进行分析并进行数学检查.

关于将算法作为一组字符串处理的问题

我在这里就这个问题回答了另一个问题.但基本上Knuth在这里所做的就是使用马尔可夫算法来实现他已经描述的内容.值得研究(并通过几个例子)Markov算法来帮助您准确理解这里发生的事情.

参考

马尔可夫的算法维基

我的定义算法文章.

Knuth是计算机编程的艺术,见1.1.8