问题标签 [computation]

在课堂上，我们学习了停机问题，图灵机，归约等。很多同学说这些都是抽象无用的概念，了解它们没有任何意义（即，一旦课程结束就可以忘记它们）结束并且不会丢失任何东西）。

为什么理论有用？您是否曾经在日常编码中使用它？

给定一个项目数组，每个项目都有一个value和cost，确定以最小成本达到最小值所需的项目的最佳算法是什么？例如：

请注意，最后的总体价值：成本比是无关紧要的（A + A会给你最好的物有所值，但A + B + B它是一个更便宜的选择，它达到了最小值）。

对于一个项目，我有一个带有公式的规范，我必须实施。在这些公式中，存在累积标准正态分布函数，它采用浮点数并输出概率。该函数用 Φ 表示。是否存在计算此函数的 Java 库？

由于两个实例之间的内积计算，基于内核的分类器通常需要 O(n^3) 的训练时间。为了加快训练速度，可以预先计算内积值并将其存储在二维数组中。然而当没有。的实例非常大，例如超过 100,000，将没有足够的内存来执行此操作。

那么有什么更好的主意吗？

我有一个昂贵的计算，我想缓存它的结果。有没有办法用两个键制作地图？我在想类似的东西Map<(Thing1, Thing2), Integer>。

然后我可以检查：

伪代码。但是有些类似的东西。

我在 Ruby (MRI) 中的整数拒绝溢出。我注意到类从 fixnum 更改为 bignum，但我想知道这是如何建模的，以及 ruby​​ 使用哪种进程对这些大量整数执行算术运算。我已经在 SCHEME 以及其他环境中看到了这种行为。

我问是因为我想在 C 程序中实现类似的东西，并且想知道 bignum + bignum 如何简化为原始操作。

任何指针？

模块中使用的 Mersenne Twister 的周期random是（我被告知）2**19937 - 1。作为二进制数，即连续 19937 个 '1（如果我没记错的话）。Python 非常快地将其转换为十进制：

我猜第二个版本是需要转换的版本？

它不仅仅是二进制的。这也很快。（而不是显示数字，我显示转换为字符串的小数长度）：

定时：

问题是：这实际上是如何完成的？

我只是天真地被打动了吗？我发现 Python shell 在瞬间生成大约 5000 个位置的景象真的很壮观。

编辑：

@dalke 和 @truppo 建议的其他时间

因此，在我看来，这result = 0; result += 2**19937可能确实会强制转换。

在大学学习期间，我必须学习很多关于计算理论的知识。我学了三个学期。我很难过，我不得不承认我忘记了很多。

我想知道这是否是个人问题，或者我们只是不得不学习很多（或多或少）无用的东西。

所以我的问题是：您认为计算理论领域的哪些主题最重要，哪些部分值得学习，您在日常工作中使用哪些主题？

就个人而言，我很高兴我听说了语言理论（尤其是正则语言 => 正则表达式 - 什么时候可以应用，什么时候不可以）以及不同的时间（和空间）复杂性，特别是 O(n)符号。

但我们必须学习更多，包括：

• 可计算性理论
  • 停机问题
  • 半可判定问题
• 复杂性理论
  • p=np?
• 逻辑理论
  • 命题演算
  • 谓词逻辑

听到这些话题很有趣，但我不确定深入研究它们的必要性。

我知道这个问题是主观的，答案会根据您的日常工作和个人经历而有很大不同。但我想知道可能比我记得的更有趣的话题。

作为输入，我收到了一些平面的三角几何。现在，我需要计算边界矩形角的四个坐标。有任何想法吗？

我有方程 y = 3(x+1)^2 + 5(x+1)^4。

使用霍纳的方案，我可以以这种形式评估这个多项式，y = 8+x(26+x(33+x(20+5x)))，因此需要 8 次算术运算。

我也可以用这种形式评估它，y = (x+1)^2 * ((5x+10)x+8)，需要 7 次操作。

有人告诉我这可以在 5 次操作中完成，但霍纳的算法应该是最有效的，它只能在 7 次操作中完成。我错过了什么吗？