理论计算机科学什么时候有用？

Question

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

为什么理论有用？ 您在日常编码中使用过它吗？

Answer 1

真实的故事：

当我从研究生院毕业后找到第一份编程工作时，我工作的公司的老板都是飞行员。 我被录用几周后，其中一个人问了我这个问题：

阿肯色州有 106 个机场。
你能写一个程序吗
找到所需的最短路线
落在他们每一个身上？

我认真地认为他是在考验我对旅行商问题和 NP 完备性的了解。 但事实证明他不是。 他对此一无所知。 他真的想要一个能够找到最短路径的程序。 当我解释说存在 106 个阶乘解并且找到最佳解是一个众所周知的计算难题时，他感到很惊讶。

这就是一个例子。

Answer 2

当我大学毕业时，我认为我和其他人一样：“我拥有计算机科学学士学位，其他很多人也是如此，我们基本上都可以做同样的事情。” 我最终发现我的假设是错误的。 我脱颖而出，与我的背景有很大关系——尤其是我的学位。

我知道有一个“轻微”的区别，因为我拥有计算机科学的“BS”，因为我的大学是全国第一所获得计算机科学学位课程认证的大学之一（据说在 1987 年排名第二），而且我以第二级毕业获得该认证。 当时，我并不认为这有什么大不了的。

我还注意到，在高中和大学期间，我在计算机科学方面表现得特别好——比我的同龄人好得多，甚至比我的许多老师都好。 我被要求了很多帮助，做了一些辅导，被要求帮助一个研究项目，并被允许在没有人的情况下进行独立研究。 我很高兴能够提供帮助，但我并没有过多考虑其中的区别。

大学毕业后（美国空军学院），我在空军服役了四年，其中两年是在申请计算机科学学位。 在那里，我注意到我的同事中很少有人拥有与计算机相关的学位，甚至没有接受过计算机相关的培训。 空军派我参加了五个月的认证培训，在那里我再次发现缺乏学位或培训。 但在这里我开始注意到差异——很明显，我遇到的许多人并不真正知道自己在做什么，其中包括受过培训或拥有学位的人。 请允许我举例说明。

参加我的空军认证培训的共有十三个人（包括我在内）。 作为空军军官或同等人员，我们都拥有学士学位。 根据年龄和级别，我处于中间位置（在 6 个 O-1 和 6 个 O-3 及以上级别中，我是 O-2）。 在本次培训结束时，空军给我们所有人颁发了橡皮图章，让我们所有人都同样有能力为国防部的任何部门采购、建造、设计、维护和操作任何计算机或通信系统。

然而，在我们十三个人中，只有六人拥有任何形式的计算机相关学位； 其他七人拥有从航空学到化学/生物学再到心理学的学位。 在我们六个拥有计算机科学学位的人中，我了解到其中两个人从未编写过任何类型的程序，并且从未使用过计算机（写论文、玩游戏等）。 我了解到，我们另外两个人在计算机科学学位课程期间在一台计算机上编写了一个程序。 只有我和另外一个人编写了不止一种程序或使用了不止一种计算机——事实上，我们发现我们两个编写了很多程序并使用了多种计算机。

五个月的培训快结束时，我们班被分配了一个编程项目，我们被分成四个小组分别进行。 我们的导师为了公平地分配“编程人才”而对班级进行了划分，他们分配了团队领导、技术领导和开发人员的角色。 每个小组都有一周的时间（在 Ada 中）在教练提供的飞行力学库之上为飞行模拟器实现一个全屏、基于文本的用户界面（这是 1990 年）。 我被任命为我的四人团队的技术主管。

我的团队领导（没有计算机学位）要求我们其他三个人将项目划分为任务，然后将其中的三分之一分配给我们每个人。 我在第一天的中间完成了第三个任务，然后用这一天剩下的时间帮助我的另外两个队友，与我的团队领导交谈（BSing;^），并在我的电脑上玩。

第二天早上（第二天），我的团队负责人私下告诉我，我们的另外两个队友没有取得任何进展（其中一个实际上无法写出可以编译的“if”语句），他让我承担他们的工作。 我在下午三点左右完成了整个项目，我的团队在当天剩下的时间里都在驾驶模拟器。

另一个拥有类似计算机科学学位的人也被任命为他团队的技术主管，他们在第三天结束时完成了工作。 他们还开始驾驶模拟器。 到本周末，其他两支球队尚未完成，甚至没有取得重大进展。 我们不被允许帮助其他球队，所以就这样了。

与此同时，到了第三天中午，我注意到飞行模拟器似乎表现“错误”。 因为我的一个同学拥有航空学位，所以我向他询问了这件事。 他很困惑，然后承认他实际上不知道是什么让飞机飞起来！？！ 我当时就傻眼了！ 事实证明，他的整个学位课程都是关于安全和坠机调查的——飞行背后没有真正的数学或科学。 另一方面，我可能辅修了航空学（还记得美国空军协会吗？），但我们设计了机翼并进行了真正的风洞测试。 因此，我悄悄地花了一周剩下的时间重写教练提供的飞行力学库，直到模拟器“正确”飞行。

从那时起，我花了近二十年的时间作为承包商，偶尔作为雇员，一直从事软件开发以及相关活动（DBA、架构师等）。 我不断地发现更多相同的东西，最终我放弃了我年轻时的假设。

那么，我究竟发现了什么？ 并不是每个人都是平等的，这没关系——我不是一个更好的人，因为我可以有效地编程，但如果这正是你需要我做的，我会更有用。 我了解到我的背景真的很重要：
成长于电工和电气工程师家庭，
建筑电子套件，
阅读学校/公共图书馆中的每一本计算机书籍，因为我无法使用真正的计算机，
然后搬到一个新城市，我的高中确实有电脑，
然后得到我自己的电脑作为礼物，
去拥有多种不同尺寸和类型的计算机（PC 到大型机）的学校，
获得一所非常好的工程学校认可的学位，
必须在不同类型的计算机上用不同语言编写大量程序，
必须编写困难的程序（例如我自己的具有自定义汇编语言的虚拟机，或霍夫曼压缩实现等），
必须自己解决问题，
用零件组装我自己的计算机并安装所有软件，
最终

，我了解到我的能力建立在从电气层面上了解计算机如何工作的基础上——分立电子元件、电路、子系统、接口、协议、位、字节、处理器、设备、驱动程序、库、程序、系统、网络，直到我现在经常工作的大型企业级企业集团。 所以，当这该死的东西行为不端时，我确切地知道如何和为什么。 我知道什么不能做，什么可以做。 我对已经做过的事情、尝试过的事情以及相对尚未探索的事情了解很多。

最重要的是，在我了解了这一切之后，我发现我什么都不知道。 面对所有可能知道的事情，我的知识是微乎其微的。

我对此很满意。 但我建议你尝试一下。

Answer 3

当然，它很有用。

想象一下开发人员正在开发模板引擎。 你知道这样的事情......

Blah blah blah ${MyTemplateString} blah blah blah.

一开始很简单，用一个厚颜无耻的小正则表达式来执行替换。

但渐渐地，模板变得更加奇特，开发人员包括了模板化列表和字符串映射的功能。 为了实现这一目标，他编写了一个简单的小语法并生成了一个解析器。

模板引擎变得非常狡猾，最终可能会包含条件逻辑语法，以根据参数的值显示不同的文本块。

具有计算机科学理论背景的人会认识到模板语言正在慢慢变得图灵完整，也许解释器模式将是实现它的好方法。

为模板构建了解释器后，计算机科学家可能会注意到大多数模板请求都是重复的，一遍又一遍地重新生成相同的结果。 因此开发了一个缓存，所有请求在执行昂贵的转换之前都会通过缓存进行路由。

此外，某些模板比其他模板复杂得多，并且需要更长的时间来渲染。 也许有人想到在渲染每个模板之前估计它的执行情况。

可是等等！！！ 团队中有人指出，如果模板语言真的是图灵完备的，那么估计每个渲染操作的执行时间的任务就是停机问题的一个实例！ 哎呀，不要这样做！

理论在实践中的作用是，所有的实践都是基于理论的。 理论上来说。

Answer 4

我最常用的东西：

• 编写可以优雅扩展的算法的计算复杂性
• 了解内存分配、分页和 CPU 缓存如何工作，这样我就可以编写高效的代码
• 数据结构
• 了解线程、锁定和相关问题

了解 图灵机等。我认为这很重要，因为它定义了我们所有人操作的约束。 欣赏这一点很重要。

Answer 5

这就是学习代数和学习如何使用计算器之间的区别，

如果您了解代数，您意识到同一问题可能会以不同的形式表现出来，并且您了解将问题转化为更简洁形式的规则（

如果您只知道如何使用）要使用计算器，您可能会在以下问题上浪费大量时间：（a）已经解决，（b）无法解决，或者（c）与您不知道的其他问题（已解决或未解决）类似不认识，因为它以不同的形式

假装，暂时，计算机科学是物理学......这个问题会显得愚蠢吗？

Answer 6

我的一个朋友正在研究一种带有一些模板的语言。 我被邀请去做一些咨询。 我们讨论的一部分是模板功能，因为如果模板是图灵完整的，他们将必须真正考虑 VM 式属性以及他们的编译器如何/是否支持它。

我的故事是这样的：自动机理论仍然被教授，因为它仍然具有相关性。 停止问题仍然存在，并且限制了您的操作。

现在，这些事情与数据库管理员敲定 C# 代码有关吗？ 可能不会。 但当你开始进入更高的水平时，你会想要了解你的根源和根源。 基础。

Answer 7

虽然我不直接将它们应用到日常工作中，但我知道我接受的正规计算机科学教育影响了我的思维过程。 我当然从一开始就避免了某些错误，因为我从正式方法中吸取了教训。

当他们学习的时候，它可能看起来毫无用处； 但我敢打赌，你的同学最终会遇到一个问题，他们会使用所学的内容，或者至少使用其背后的思维模式...

打蜡...打蜡...打蜡...打蜡……这和空手道有什么关系呢？

Answer 8

在一份工作中，我的任务是改进配电模型的网络跟踪算法，因为他们使用的算法太慢了。 三相网络本质上是三个 n 树（因为电力网络中不允许出现环路）。 网络节点位于数据库中，一些原始团队无法弄清楚如何构建内存中模型，因此跟踪是通过数据库上的连续深度 SELECT 完成的，并在每个阶段进行过滤。 因此，要追踪一个节点（距变电站十个节点）至少需要 10 次数据库查询（最初的团队成员是数据库高手，但缺乏像样的算法背景）。

我编写了一个解决方案，将数据库中的 3 个 n 树节点网络转换为一个数据结构，其中每个节点在节点结构数组中存储一次，并且使用其中的双链接指针将 n 树关系转换为三个二叉树阵列，以便可以轻松地在任一方向追踪网络。

它至少快了两个数量级，其中三个数量级是在很长的下游轨迹上。

可悲的是，我实际上不得不向其他几位接受过数据库和 VB 培训的程序员教授一门关于 n 树、二叉树、指针和双向链表的课程，以便让他们理解算法。

Answer 9

这是“如何”和“什么”之间的经典二分法。 你的同学正在研究“如何”编程软件，他们非常关注近焦； 从这个角度来看，从实现的角度来看，了解诸如停止状态和图灵机之类的事情似乎并不重要。

然而，“如何”在计算机科学中所涉及的实际工作却很少。 事实上，我认识的大多数成功的工程师可能认为它只占实际工作的 20% 以下。 到目前为止，“做什么”更为重要。 为此，计算机科学的基础知识至关重要。 你想要做什么更多地与设计有关，而不是与实施有关； 好的设计是……好吧，我们就称其为“不平凡”吧。

“构建软件设计有两种方法：一种方法是使其简单到明显没有缺陷，另一种方法是使其复杂到不存在明显缺陷。第一种方法要困难得多。” - CAR Hoare

祝你学习顺利！

Answer 10

我认为理解计算的基本模型是有用的：当然，在实践中你永远不需要能够将图灵机转换为寄存器机，但是学习如何看到两个截然不同的问题实际上是同一概念的实例是至关重要的技能。

Answer 11

大多数知识都不是“实用的”，但可以帮助您以无法预料的方式将各个点联系起来，或者为您提供更丰富的词汇来描述更复杂的想法。

Answer 12

重要的不是你研究的具体问题，而是你通过研究它们学到的原理。 我每天在工作中都会使用有关算法、数据结构、编程语言和操作系统的概念。 如果您是一名程序员，您将一直做出影响系统性能的决策。 您需要在基本抽象概念上打下坚实的基础，才能做出正确的选择。

Answer 13

我从CS毕业后我也有类似的想法：我们学的一大堆理论在实践中完全没有用。 这在短时间内被证明是正确的，但是当你处理复杂的任务时，理论绝对比实践更有价值。 每个人经过几年的编码后都可以编写一些“有效”的程序，但并不是每个人都能理解如何工作。 不管怎样，我们大多数人在某个时刻都会处理性能问题、网络延迟、精度、可扩展性等。在这个阶段，理论是至关重要的。 为了在处理复杂系统时设计一个好的解决方案，了解内存管理的工作原理、进程和线程的概念、如何为它们分配内存或提高性能的高效数据结构等非常重要。

例如，有一次我正在开发一个包含大量数学计算的项目，但在某个时候我们的软件失败了。 在调试时，我发现经过一些数学运算后，我收到了一个值为 1.000000000002 的 DOUBLE 数字，但从数学角度来看不能 > 1 在程序的后期阶段给出了传奇的 NaN 异常。 我花了一些时间来解决这个问题，但如果我更多地关注“双精度和浮点数的近似”课程，我就不会浪费时间。

Answer 14

如果您在一家从事开创性工作的公司工作，那么能够向架构师和开发人员传达其好处是什么就很重要。 各种技术都有很多炒作，给自己定位可能很困难。 当您用科学和理论术语来构建您的创新时，您绝对具有优势，并且客户会感觉到您是真实的。 我可以告诉人们：有一种新的方法来处理状态、编码和不确定性（即复杂性），并且您绝对可以比今天更有效率。

如果你在职业生涯中放眼长远，学习理论会给你带来深度，你需要成长的深度。 学习第五种或第六种编程语言的投资回报将比学习第二种和第三种编程语言少很多。 接触理论将使您对真正的工程有所了解，了解自由度在哪里以及如何做出正确的权衡。

重要概念 1) 状态，2) 编码，3) 非确定性。 如果你不认识他们，他们不会帮助你。 理论应该为你提供的是大局观以及基本概念如何组合在一起的感觉。 它应该可以帮助你磨练你的直觉。

示例：上面的一些答案提到了停机问题和图灵机。 当我在大学里看到图灵的论文时，我并没有感到任何启发。 有一天，我偶然发现了哥德尔不完备定理，尤其是哥德尔数。 事情开始变得有意义了。 多年后，我在一家书店读到了关于格奥尔格·康托的文章。 现在我真正开始理解图灵机和停机问题。 亲自尝试并在维基百科上查找“康托尔对角线论证”。 这是你在智力上遇到过的最棒的事情之一。

深思：典型的图灵机并不是设计状态转换机的唯一方法。 拥有两盘而不是一盘磁带的图灵机可以为许多算法提供更快的速度。 http://www.math.ucla.edu/~ynm/papers/ eng.ps

通过阅读这本书，你可以比我更有效地了解这些见解。 链接在这篇文章的底部。 （至少，请查看亚马逊上的目录，了解这本书的全部内容）：

我发现罗森伯格的这本书非常精彩。 http://www.amazon.com/The-Pillars-Computation-Theory-Nondeterminism/ dp/0387096388 如果你只有一本理论书，恕我直言，这应该是一本。

Answer 15

我不会每天使用它。 但它给了我很多理解，对我每天都有帮助。

Answer 16

我发现我每天在CS理论世界的幸福只需要一句“低耦合、高内聚”的口头禅。 Roger S. Pressman 在Steve McConnell 让它变得时尚。

Answer 17

是的，我通常使用状态图来设计程序的形状和流程。
一旦理论上可行，我就开始编码和测试，边检查状态边进行。

我发现它们也是向其他人解释流程行为的有用工具。

Answer 18

简单的。 例如：如果我正在使用 RSACryptoServiceProvider，我想知道那是什么以及为什么我可以信任它。

Answer 19

因为 C++ 模板实际上是某种 lambda 演算。 请参阅 www.cs.nott.ac.uk/types06/slides/michelbrink_types_06.pdf

Answer 20

我现在正在学习分布式算法课程。 有一个关于容错的章节，它包含一些关于有多少进程可以失败（或行为不当）的上限的证明，以便分布式算法可以正确处理它。

对于许多问题，行为不当的进程最多可达进程总数的三分之一。 在我看来，这非常有用，因为您知道尝试开发更好的算法（在给定的假设下）是毫无意义的。

Answer 21

即使理论课程不会直接使用，它也可能会帮助你更好地思考某些事情。

正如杰弗里·L·惠特利奇所说，你不知道老板会要求你做什么，你可能不得不使用一些你认为没有好处的东西。

Answer 22

说实话，我不太同意这里的很多答案。 我编写了我的第一个编译器（为了好玩；我真的有太多的咖啡/空闲时间），而没有上过编译器课程； 基本上我只是扫描了另一个编译器的代码并遵循了模式。 我可以随心所欲地用 C 语言编写一个解析器，但如果我的生活依赖于它，我想我不记得如何绘制下推自动机。

当我决定将类型推断放入我的玩具（命令式）编程语言中时，我首先查看了大约五篇论文，盯着一种叫做“类型化 lambda 演算”的东西............**** ....？ 起初，我尝试用“通用变量”和“非通用变量”来实现一些东西，但不知道发生了什么。 然后我放弃了这一切，拿着笔记本坐在那儿，思考如何在支持我需要的所有东西（子类型、一流函数、参数化类型等）的情况下实际实现它，经过几天的思考& 在编写测试程序时，我花费了一个多星期的时间试图弄清楚理论上的废话，结果却大吃一惊。

事实证明，了解计算基础知识（即虚拟内存如何工作、文件系统如何工作、线程/调度、SMP、数据结构）都非常有用。 复杂性理论和 Big-O 的东西有时被证明是有用的（特别是对于 RDBMS 设计之类的事情有用）。 停机问题和自动机/图灵机理论？ 绝不。

Answer 23

我知道这已经过时了，但我对那些声称理论“无用”并且没有理论就可以实践自己的职业的人的简短答复是：

没有基础理论，就没有没有练习。

为什么理论有用？

理论是构建其他事物的基础。 当理论被应用时，实践就是结果。

考虑今天的计算机。今天的普通计算机是在图灵机之上建模和构建的，为了简单起见，图灵机是一个用于计算的抽象/理论模型。 这个理论模型是计算的基础，我们今天使用的所有计算设备，从高端服务器到袖珍电话，都能正常工作，因为底层基础是健全的。

考虑算法分析。简单来说，算法分析和时间复杂度理论已用于对问题进行分类（例如 P、NP、EXP 等），以及我们在尝试解决问题时算法的行为方式。解决不同班级的不同问题。

假设您的一个朋友在某个地方 X 找到了工作，在那里，经理提出了一些简单的要求，例如以下示例：

示例 1：我们拥有庞大的送货车队，可以访问多个州的不同城市。 我们需要您实施一个系统来找出每辆车的最短路线，并从所有可能性中选择最佳路线。 你能做到吗？

认为该理论“无用”的你的朋友没有意识到他们刚刚遇到了旅行商问题 (TSP)，并且不假思索地开始设计这个系统，结果却发现他们天真的尝试检查所有< /em> 正如最初所要求的，这种可能性是如此之慢，以至于他们的系统无法用于任何实际目的。

事实上，他们不知道为什么系统在检查 5 个城市时运行在“可接受”的水平，但在检查 10 个城市时变得非常慢，而在检查到 40 个城市时就冻结了。 他们的理由是“仅比 5 个城市测试多 2 倍和 8 倍的城市”，并想知道为什么该计划不简单地分别需要“多 2 倍和 8 倍的时间”……

理解这一理论就会让他们至少一眼就能认识到以下内容：

1. 这是 TSP TSP
2. 是 NP 难的
3. 他们算法的增长顺序是 O(n!)

这些数字不言而喻：

+--------------+-------+-----------------------------------------------------------------+
|  No. Cities  | O(N!) |  Possibilities                                                  |
+--------------+-------+-----------------------------------------------------------------+
|       5      |   5!  | 120                                                             |
|      10      |  10!  | 3,628,800                                                       |
|      40      |  40!  | 815,915,283,247,897,734,345,611,269,596,115,894,272,000,000,000 |  <-- GG
+--------------+-------+-----------------------------------------------------------------+

他们本可以一开始就意识到他们的系统不会按照他们想象的那样工作。 在为该项目分配了大量时间、精力和其他资源并最终浪费在该项目上之后，该系统后来被认为不切实际并被取消，而这一切都是因为认为“理论毫无用处”。

因此，在这次失败之后，经理们认为“好吧，也许这个系统被低估了；毕竟，我们国家有很多城市，而我们的计算机根本没有我们需要的那么快，因为我们最近取消了系统已经成功”。

管理团队将项目失败的原因归咎于计算机速度慢。 毕竟，他们不是计算机科学理论专家，也没有必要成为专家，而那些本应是该主题专家并且本可以通知他们的人却没有。

但他们还有另一个项目。 其实是一个更简单的。 一周后他们来询问以下内容：

Ex 2：我们只有几台服务器，而程序员不断提交程序，由于未知的原因，最终陷入无限循环并占用服务器。 我们需要你编写一个程序来处理正在提交的代码并检测提交的程序在运行过程中是否会导致无限循环，并决定是否允许提交的程序运行在这个基础。 你能做到吗？

你亲爱的朋友再次接受挑战并立即开始工作。 经过几周的工作，没有任何结果，你的朋友压力很大，不知道该怎么办。 又是一次失败……您的朋友现在因为无法解决这个“简单的问题”而感到“愚蠢”……毕竟，请求本身听起来很简单。

不幸的是，你的朋友虽然坚持认为“理论是无用的”，但没有意识到这个看似简单的请求实际上是一个关于可判定性的棘手问题（即停止问题本身），并且没有已知的解决方案。 这是一项不可能完成的任务。

因此，即使开始努力解决该特定问题也是一个可以避免和预防的错误。 如果有理论框架来理解所请求的内容，他们就可以提出一个不同的、可实现的解决方案......例如实现一个可以简单地杀死的监控进程-SIGTERM任何用户进程（根据用户列表），在某些假设下（例如我们知道每个程序运行应该在 10 分钟内终止，因此任何运行超过 20 分钟的实例都应该被杀死）。

总之，没有理论的实践就像没有地基的建筑。 迟早，从直角施加适量的压力会使它自行塌陷。 没有例外。

您在日常编码中使用过它吗？

是的，但不是直接。 相反，我们间接依赖它。 这里需要注意的是，不同的理论概念或多或少适用，具体取决于您正在处理的问题领域。

当然，我们：

1. 每天使用计算机，依赖于计算模型（例如图灵机）
2. 编写代码，依赖于可计算性理论（例如什么是可计算的） 以及 lambda 演算（例如用于编程语言）
3. 依赖于颜色理论和模型（例如 RGB和 CMYK 颜色模型）用于彩色显示和打印等。
4. 计算机图形学中的欧拉定理，以便可以构建矩阵来围绕任意轴旋转对象，等等......

这是一个事实，简单使用的人 一架飞机旅行不需要理解甚至允许飞机被建造并飞行的理论......但是当有人期望建造所说的机器并让它们工作时...你真的能指望一个连飞行原理都不懂的人能得到好的结果吗？

在历史的大部分时间里，直到莱特兄弟理解了某些关于飞行的理论概念并设法将其付诸实践之前，没有人能够制造出一架飞行器（有些人甚至在测试中死去），这真的是巧合吗？

这并非巧合。 今天我们拥有许多可用的技术，因为建造它们的人首先理解并应用了使它们能够工作的理论原理。

Answer 24

我想这取决于你进入哪个领域。