在大学学习期间,我必须学习很多关于计算理论的知识 . 我研究了三个学期的主题 . 我很难过,我不得不承认我忘记了很多 .
我想知道这是个人问题,还是我们只需要学习很多(或多或少)无用的东西 .
所以我的问题是:您认为计算理论领域中哪些主题最重要,哪些部分值得学习,以及您在正常工作中使用哪些主题?
就我个人而言,我很高兴我听说theory of languages(特别是常规语言=>正则表达式 - 当它们可以应用时,何时不应用)和关于不同的time (and space) complexities,特别是O(n)符号 .
但我们还要研究更多,包括:
-
可计算性理论
-
停止问题
-
半自由的问题
-
复杂性理论
-
p = np?
-
逻辑理论
-
命题演算
-
谓词逻辑
听到这些话题很有意思,但我不确定深入研究它们是多么必要 .
我知道这个问题是主观的,答案会因您的日常工作和个人经历而有很大不同 . 但是我想知道可能比我记忆中更有趣的主题 .
2 回答
问题很模糊 . 谁重要?
所有这些都值得学习 . 这是一个特例,即所有人类的努力本身都值得学习 .
如果你的问题是“哪些主题给我带来的好处大于我花费时间和研究它们的成本?”那是一个只有你自己才能回答的问题 . 比如,古希腊历史研究对我有益,与它如何影响我完成工作的能力无关 .
我使用你列出的所有主题 - 语言理论,渐近阶次分析,可判定性,复杂性理论,定理证明系统等等 .
我不是在形式上使用它们;我没有坐在我的办公桌前使用主定理来推导特定算法的顺序分析 . 我使用它们是因为能够采用建议的语言特性并快速解决是否实现它是否需要编译器来解决线性,多项式,指数,NP-hard或等效的问题是非常方便的 . 停止问题 .
例如,很容易弄清楚嵌套lambda中C#3中的重载解析是NP难的,但不等于停顿问题 . 因此,我们知道(1)在多项式时间内尝试解决问题是浪费我们的时间,(2)至少我们知道在一段时间内可以找到解决方案,并且(3)我们可以提出简单的启发式方法来检测不良情况,并在需要时快速失败 .
我并不亲自使用证明系统,尽管将问题视为定理证明器的一个特例是有帮助的 . 有各种语言特征等同于你在定理证明器中抛出的问题,特别是在类型推断和流分析领域 . 幸运的是,C#的所有功能实际上都不需要实现定理证明器;在这个建筑物中实现的其他语言确实具有该属性,如F# .
我不确定我在工作中直接使用我在计算类理论中学到的东西 . 但我认为这不是重点 . 我也没有直接使用我在高中时期在欧几里德几何中学到的任何东西 . 但那是我在小学毕业时最重要的课程 .
计算理论是一个非常有趣的话题,对它的了解只能对生活有所帮助 . 我不能证明这一点,但我知道这是真的 .
对不起,如果这不是一个答案 .