theory - 计算理论中的重要主题

Question

关闭。这个问题是 opinion-based 。目前不接受答案。

---

想要改进这个问题吗？更新问题，以便 editing this post 可以用事实和引文来回答它。 .

去年关闭。

Improve this question

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

我想知道这是否是个人问题，或者我们是否只是必须学习很多(或多或少)无用的东西。

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

就我个人而言，我很高兴听说 theory of languages (特别是正则语言 => 正则表达式 - 何时可以应用，何时不可以)以及不同的 time (and space) complexities ，特别是 O(n) 表示法。

但是我们必须研究更多，包括:

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

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

我知道这个问题是主观的，答案会有很大差异取决于您的日常工作和个人经验。但我想了解可能比我内存中更有趣的主题。

Answer 1

What topics in the field of the theory of computation do you think are most important

这个问题很模糊。对谁重要？

which parts are worth learning about?

所有这些都值得学习。这是一个特例，说明所有人类的努力本质上都值得学习。

如果您的问题是“哪些主题给我带来的好处大于我学习这些主题所花费的时间和精力的成本？”那么这个问题只有你自己才能回答。例如，学习古希腊历史对我的好处与它如何影响我完成工作的能力无关。

Which topics do you use during your normal work?

我使用了你列出的所有主题——语言理论、渐近阶分析、可判定性、复杂性理论、定理证明系统等等。

我不会在正式意义上使用它们；我没有坐在办公 table 前使用主定理来导出特定算法的阶次分析。我使用它们的意义是，能够非常方便地采用提议的语言功能并快速计算出实现它是否需要编译器解决线性、多项式、指数、NP 困难或等价于的问题停机问题。

例如，很容易计算出 C# 3 中嵌套 lambda 的重载解析是 NP 困难的，但并不等同于停止问题。因此，我们知道(1)即使尝试在多项式时间内解决问题也是浪费时间，(2)至少我们知道可以在一定时间内找到解决方案，(3)我们可以想出简单的启发式方法来检测不良场景，并在需要时快速失败。

我个人不太使用证明系统，尽管将问题视为定理证明者的特殊情况是有帮助的。有各种各样的语言特性相当于你向定理证明者提出的问题，特别是在类型推断和流分析领域。幸运的是，C# 的任何功能实际上都不需要实现定理证明器；在此建筑中实现的其他语言确实具有该属性，例如 F#。