标签: taocp

经典算法书籍(TAOCP,CLR)(而不是经典算法书籍,如fxtbook)充满了命令式算法.对于其实现主要基于数组的算法而言,这是最明显的,例如组合生成(在算法中使用数组索引和数组值)或联合查找算法.

这些算法的最坏情况复杂性分析取决于数组访问是O(1).如果用array-ish持久性结构替换数组,例如Clojure,则数组访问不再是O(1),并且这些算法的复杂性分析不再有效.

这让我想到了以下问题:纯函数式编程是否与经典算法文献不兼容？

我从事软件开发的职业,拥有英语学位,而不是计算机科学或其他科学/工程背景.我在自学成才的基础上走了很长一段路,但经过10多年的努力,我想回去填补空白,尤其是数学.

给自己一个Comp-Sci教育的显而易见的地方是通过计算机程序设计的艺术.然而,由于我没有那么多的数学和我在大学的最后一个数学课是在1995年,我需要一些刷新和扩充甚至能够阅读TAOCP中的数学符号.

我的想法是去可汗学院并通过必要的主题作为阅读TAOCP的补救前提.但是,在Catch 22中,我试图找出实际需要经历哪些主题作为准备.

所以,我想知道的是,如果有人基本上只有高中数学(我有更多的东西,但我认为这是一个有效的问题,有人以高中作为背景来处理这个问题),什么数学"课程"是否需要从可汗学院这样的地方开始,以便开始TAOCP准备阅读和理解所包含的数学？

我刚开始阅读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 = …

我正在练习TAOCP第1版第3版,并且无法理解下面练习答案中使用的语法.

第1章练习8

通过指定T _j,s _j,a _j,b _j来计算正整数m&n的最大公约数

让你的输入用字符串a ^m b ^n表示(ma后跟n b)

回答:

设A = {a,b,c},N = 5.该算法将以字符串a ^{gcd(m,n)结束}

    j     Tj     sj    bj    aj
    0     ab  (empty)  1    2   Remove one a and one b, or go to 2.
    1   (empty)  c     0    0   Add c at extreme left, go back to 0.
    2     a      b     2    3   Change all a's to b's
    3     c      a     3    4   Change all c's …

TAOCP第1卷中的"练习笔记"部分中有一个问题,如下所示:

"证明13 ^ 3 = 2197.概括你的答案.(这是作者试图避免的一个可怕的问题)."

问题:

1. 你怎么会真正证明这一点？(直接乘法是一种方式,另一种方式可以是使用(a + b)^ 3的公式).解决方案是否需要使用某种方法来进行某种推广？

2. 这里的概括是什么？

3. 为什么这是一个可怕的问题？

4. 您知道哪些其他类似的可怕问题？

感谢任何答案.

PS我很抱歉,如果上面的问题陈述使它看起来像一个作业问题,但事实并非如此.要求人们不要将此标记为作业问题,以便更多人能够给出答案.

我试图在区间[0,1]中实现高斯分布随机数发生器.

float rand_gauss (void) {
  float v1,v2,s;

  do {
    v1 = 2.0 * ((float) rand()/RAND_MAX) - 1;
    v2 = 2.0 * ((float) rand()/RAND_MAX) - 1;

    s = v1*v1 + v2*v2;
  } while ( s >= 1.0 );

  if (s == 0.0)
    return 0.0;
  else
    return (v1*sqrt(-2.0 * log(s) / s));
}

这几乎是Knuth第二卷TAOCP第3版第122页中算法的直接实现.

问题是rand_gauss()有时返回区间[0,1]之外的值.

我希望能够学习 MIX/MMIX，但我不知道用来编写它的工具链。我过去曾使用 uVision 来处理 ARM 汇编器相关的事情，对于 MIX/MMIX 是否存在这样的等效项？

有人可以向我解释MIX中的划分(来自Knuth的TAOCP)是如何在字节到字节的基础上工作的？

rA = |-| . . . .0| 

rX = |+|1235|0|3|1|

存储位置1000包含|-|0|0|0|2|0|.

执行操作时

DIV 1000

寄存器变成了

rA = |+|0|617|?|?|

rX = |-|0|0|0|?|1|

现在我明白上的标志rA和rX,但以什么顺序的字节rAX填充和部门完成？

如果DIV 1000导致每一位除以2,那么我会期待

rAX = |+|617|0|1|0|-|0|1|0|1|1| 

其中rA包含除法结果和rX余数(从右侧填充).

我可能在这里遗漏了一些东西,而Knuth似乎认为我应该能够自己解决这个问题(因此关于它的10级问题,我也没有得到),但有人可以帮助我吗？

我无法弄清楚Knuth在第1.1章的练习8的指示中的含义.

任务是让两个正整数的高效GCD算法m,并n使用他的符号theta[j],phi[j],b[j]和a[j]其中θ和phi是字符串,a以及b-正整数表示在这种情况下计算步骤.

让输入成为表单的字符串a^mb^n.

这里给schnaader 给出了Knuth算法的一个很好的解释.

我的问题是如何将这与练习中给出的方向联系起来,使用他在书中给出的算法E,其中原始r(余数)被替换为|m-n|和n替换min(m,n).

我正在读 Knuth 的书 TAOCP。我只是在学习寄存器的简单数学运算。还有一个减法运算的例子：

rA before: - | 1234 | 0| 0| 9
Cell 1000: - | 2000 |  150| 0
SUB 1000    
rA after:  + | 766  | 149 | ?

我明白 -1234-(-2000) = 766 但是 (0 | 0) - 150 = 149 ??

为什么 9 - 0 = ？

这些都是“包装”的词。也许我需要阅读更多有关它们的内容。或者谁能​​解释一下？

这是一个例子:

1. [00] 2009年的二进制形式......
2. [05]其中一封信......
3. [10]四位量 - 半字节或十六进制数字......
4. [15]一千字节......
5. [M13]如果x是0和1的任何字符串......
6. [M20]证明或反驳......

[00],[05],[10],[15],[M13],[M20]是什么意思？

我试过了:

• 谷歌搜索 taocp exercises square brackets
• 寻找方括号内的数字模式.
  • 他们都增加和减少
  • 它们大多数但不是五个的倍数
  • 那些有M的人时不时出现
  • M是唯一的前缀
  • 代码是非唯一的
• 谷歌搜索 "the art of computer programming" exercises brackets
• 谷歌搜索 "the art of computer programming" M13
  • 查看http://dl.acm.org/citation.cfm?id=1312683,表示M表示里程碑.
• 谷歌搜索 "the art of computer programming" [00]
• 寻找书中的附录解释
• 考虑到那也是一些问题

没运气!

"lg"在以下短语中的含义是什么？

"......我们忽略至少显著LG 吨的比特X指到M时_吨 [ X ]".(Knuth,2005,pp.4-5).

从上下文来看,似乎"lg t"表示"t -1",因此lg 2将为1而lg 5将为4.那么,"lg"的严格含义在这里是什么？

参考

Knuth,DE(2005).计算机编程的艺术:第1卷,第1册:MMIX,新千年的RISC计算机.上萨德尔河,新泽西州:Addison-Wesley.

在 MMIX 机器mmix-doc第 3 页第 4 段的文档中：

我们使用记号代表由以下组成的数字 从位置开始的连续字节。（符号 表示将 k 的最低有效 t 位设置为 0，并且仅保留结果地址的最低 64 位。...