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

Question

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

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

Answer 1

当我大学毕业时，我认为我和其他人一样：<！>“我有CS的学士学位，很多其他人也有，我们都可以做同样的事情。<！> QUOT;我最终发现我的假设是假的。我脱颖而出，我的背景与它有很大关系 - 特别是我的学位。

我知道有一个<！>“轻微的<！>”;差异，因为我有一个<！>“B.S。<！>”;在CS，因为我的大学是全国第一个获得CS学位课程认证的学生之一（据说是1987年的＃2），我在二年级毕业，获得了认证。当时，我认为这不重要。

我在高中和大学期间也注意到我在CS方面做得特别好 - 比我的同龄人要好得多，甚至比我的许多老师都要好。我被要求帮助很多，做了一些辅导，被要求帮助研究项目，并且被允许在没有其他人的情况下进行独立研究。我很高兴能够提供帮助，但我对这种差异没有太多考虑。

大学毕业后（USAFA），我在空军工作了四年，其中两年正在申请我的CS学位。在那里，我注意到我的同事很少有学位或甚至与计算机相关的培训。空军给了我五个月的认证培训，在那里我再次发现缺乏学位或培训。但在这里我开始注意到差异 - 很明显，我遇到的许多人并不真正知道他们在做什么，包括那些接受过培训或学位的人。请允许我说明一下。

在我的空军认证培训中共有十三人（包括我）。作为空军军官或同等学历，我们都拥有学士学位。我根据年龄和等级处于中间位置（我是六个O-1和六个O-3及以上的O-2）。在这次培训结束时，空军给我们所有人提供橡皮图章，同样有能力为国防部的任何部分获取，建造，设计，维护和操作任何计算机或通信系统。

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

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

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

第二天早上（第二天），我的团队私下告诉我，我们的另外两名队友没有取得任何进展（其中一人实际上没有写过<！> qUOT; <！>如果QUOT;会编译的声明），他让我接受他们的工作。我在下午中午完成了整个项目，我的团队花了一整天的时间来驾驶模拟器。

另一个具有可比CS学位的人也被指派为他的团队的技术负责人，他们在第三天结束时完成。他们也开始飞行他们的模拟器。本周末，其他两支队伍尚未完成，甚至没有取得重大进展。我们不被允许帮助其他球队，所以就这样了。

与此同时，到第三天中午，我注意到飞行模拟器似乎只是表现出错误的<！>“错误<！>”。由于我的一个同学拥有航空学位，我问过他。他很神秘，然后承认他实际上并不知道是什么让飞机飞了！？！我傻眼了！事实证明，他的整个学位课程都是关于安全和碰撞调查 - 没有真正的数学或科学背后的飞行。另一方面，我可能是航空领域的未成年人（还记得USAFA吗？），但我们设计了机翼并进行了真正的风洞试验。因此，我悄悄地花了一周的剩余时间重写教师提供的飞行力学库，直到模拟器飞到<！>“右<！>”。

从那时起，我作为承包商花了将近二十年的时间，偶尔作为一名员工，总是从事软件开发和相关活动（DBA，建筑师等）。我继续发现更多相同的东西，最终我放弃了我年轻的假设。

那么，我究竟发现了什么？不是每个人都是平等的，这是可以的 - 我不是一个更好的人，因为我可以有效地编程，但我更有用，因为这是你需要我。我了解到我的背景真的很重要：     在一个电工和电气工程师的家庭中成长，     建筑电子工具包，     阅读学校/公共图书馆的每本计算机书，因为我无法访问真正的计算机，     然后搬到我的高中确实有电脑的新城市，     然后把我自己的电脑作为礼物，     去有不同大小和种类的电脑的学校（电脑到大型机），     从一所非常好的工程学院获得认可的学位，     不得不在不同类型的计算机上用不同语言编写大量程序，     必须编写硬件程序（如我自己的虚拟机，使用自定义汇编语言，或霍夫曼压缩实现等），     不得不为自己排除故障，     从部件构建我自己的计算机并安装所有软件，     等

最终，我了解到我的能力建立在了解计算机如何从电气水平起作用的基础上 - 分立电子元件，电路，子系统，接口，协议，位，字节，处理器，设备，驱动程序，图书馆，程序，系统，网络，以及我现在经常工作的大型企业级集团。所以，当那该死的东西行为不端时，我完全知道如何以及为什么。我知道什么是不可能做的以及什么可以做到的。我对已经完成的工作，已经尝试过的工作以及相对未开发的工作知之甚多。

最重要的是，在我了解了所有这些之后，我了解到我不知道该死的东西。面对所有可能知道的事情，我的知识是微不足道的。

我对此非常满意。但我建议你试试。

Answer 2

真实的故事：

当我从研究生院开始我的第一份编程工作时，那些拥有我工作的公司的人都是飞行员。在我被雇用几周后，其中一人问我这个问题：

  

阿肯色州共有106个机场。   你能写一个会这样的程序吗？   找到必要的最短路径   他们每个人都有土地？

我认真地认为他是根据我对旅行商问题和NP完全性的了解来测验我的。但事实证明他不是。他对此一无所知。他真的想要一个能找到最短路径的程序。当我解释说有106个因子解决方案并且发现最好的解决方案是一个众所周知的计算难以处理的问题时，他感到很惊讶。

这就是一个例子。

Answer 3

当然，这很有用。

想象一下开发人员正在使用模板引擎。你知道那种事......

Blah blah blah ${MyTemplateString} blah blah blah.

它开始时很简单，用一个厚脸皮的小正则表达式来表示替换。

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

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

在CS中具有理论背景的人会认识到模板语言正逐渐变得图灵完成，并且解释器模式可能是实现它的好方法。

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

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

但等等!!!团队中的某个人指出，如果模板语言确实是图灵完成的，那么估算每个渲染操作的执行时间的任务就是停止问题的一个例子!!哎呀，不要那样做！

在实践中，关于理论的是所有实践都是基于理论的。理论上

Answer 4

我最常用的东西：

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

至于图灵机等上的东西。我认为这很重要，因为它定义了我们所有人运作的限制。欣赏这一点很重要。

Answer 5

这是学习代数和被教导如何使用计算器之间的区别

如果你知道代数，你会发现同样的问题可能以不同的形式出现，你理解将问题转化为更简洁的形式的规则

如果你只知道如何使用计算器，你可能会浪费大量时间在一个问题上按下按钮，这个问题要么（a）已经解决，（b）无法解决，要么（c）像其他一些问题（已解决或未解决）您无法识别，因为它的形式不同

暂时假装计算机科学是物理学......这个问题看起来很愚蠢吗？

Answer 6

我的一位朋友正在研究一种带有一些模板的语言。我被要求做一点咨询。我们讨论的部分内容是模板功能，因为如果模板是图灵完成的，他们必须真正考虑VM-ish属性以及他们的编译器如何/如果支持它。

我的故事就是这样：自动教学理论仍在教授，因为它仍具有相关性。暂停问题仍然存在，并限制了您可以做的事情。

现在，这些事情是否与数据库管理员敲定C＃代码有关？可能不是。但是当你开始进入更高级别时，你会想要理解你的根源<！> amp;基础。

Answer 7

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

当他们学习它时，它似乎毫无用处;但我敢打赌，你的同学最终会遇到一个问题，他们会使用他们所教的内容，或者至少是它背后的思维模式......

Wax on ... Wax off ... Wax on ... Wax off ...这与空手道有什么关系呢？

Answer 8

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

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

至少快两个数量级，三个在很长的下游痕迹上。

令人遗憾的是，我必须实际教授n-trees，二叉树，指针和双向链接列表中的一些类，这些程序员已经接受过数据库和VB方面的培训，以便他们理解算法。

Answer 9

这是一个经典的二分法，在<！>之间，如何<！>和<！>“什么<！>”;你的同学正在看<！>“如何<！>”;编程软件，他们非常专注于近距离焦点;从这个角度来看，从实施的角度来看，似乎知道停止状态和图灵机等事情并不重要。

<！>

QUOT;如何QUOT <！>;但是，与计算机科学相关的实际工作却很少。事实上，我所知道的大多数成功的工程师可能会把它放在实际工作的不到20％。 <！> QUOT;什么QUOT <！>;要做的更重要;为此，计算机科学的基础是至关重要的。 <！> QUOT;什么QUOT <！>;你想做的事与设计有关，而不是实现;好的设计就是......好吧，我们只需称它为“！”，“非平凡的<！>”。

<！>“构建软件设计有两种方法：一种方法是使其变得如此简单，以至于显然没有任何缺陷，另一种方法是使其变得如此复杂以至于没有明显的缺陷。第一种方法要困难得多。<！> - C.A.R.霍尔

祝你学习顺利！

Answer 10

我认为理解计算的基本模型很有用：确保你在实践中永远不需要能够将图灵机翻译成注册机，但学习如何看待这两个非常不同的问题实际上是同一个概念的实例是一项关键技能。

Answer 11

大多数知识不是<！>“实用<！>”，但可以帮助您以无法预料的方式连接点，或者为描述更复杂的想法提供更丰富的词汇。

Answer 12

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

Answer 13

如果您在一家开展突破性工作的公司工作，那么能够与建筑师和开发人员沟通的好处是很重要的。关于各种技术的炒作很多，定位自己可能很困难。当您在科学和理论方面构建您的创新时，您肯定处于优势，客户感觉您是真实的。我可以告诉人们：有一种处理状态，编码和非确定性（即复杂性）的新方法，你绝对可以比现在更富有成效。

如果你在职业生涯中学习长远的理论，理论会给你深度，你需要的深度。学习第5或第6编程语言的投资回报将比学习第2和第3编程语言少得多。接触理论将使您对真正的工程，自由度的位置以及如何做出正确的权衡取舍有所了解。

重要概念1）状态，2）编码，3）非确定性。如果你不了解他们，他们将无法帮助你。理论应该为您提供的是大局观和基本概念如何融合在一起的感觉。它应该可以帮助你磨练自己的直觉。

示例：上面的一些答案提到了暂停问题和图灵机。当我在大学读到图灵的论文时，我根本没有感到开悟。有一天，我偶然发现了Goedel的不完备性定理和Goedel编号。事情开始变得很有意义。多年后，我在一家书店读到了Georg Cantor。现在我真的开始了解图灵机和停止问题了。试试自己，然后查找<！>“康托尔的对角线论据<！>”;在维基百科上。这是你将遇到的最智能的事情之一。

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

通过阅读本书，您可以更有效地让自己了解这些见解。链接在这篇文章的底部。 （至少，请查看亚马逊上的目录，了解这是什么）：

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

Answer 14

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

有一次，例如我正在开展一个项目，包括大量的数学计算，在某些时候我们的软件失败了。调试时，我发现在经过一些数学运算后，我得到一个数值为DOUBLE的值为1.000000000002，但是从数学的角度来看，不能<！> gt; 1在程序的某个后期阶段，它给出了传奇的 NaN 例外。我花了一些时间来弄清楚这一点，但如果我更加关注<！>“近似Double和Float <！>”;我不会浪费那段时间。

Answer 15

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

Answer 16

我发现我从CS理论世界获得的每日幸福所需要的只是咒语<！>“低耦合和高内聚<！>”的话语。 Roger S. Pressman 在 Steve McConnell 让它变得时髦。

Answer 17

Ya，我通常使用状态图来设计程序的形状和流程。 一旦它理论上起作用，我开始编码和测试，在我去的时候检查状态。

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

Answer 18

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

Answer 19

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

Answer 20

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

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

Answer 21

即使不直接使用理论课程，也可能有助于你更好地思考。

你不知道老板会要求你做什么，你可能不得不使用你认为不会有益的东西，正如Jeffrey L Whitledge所说。

Answer 22

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

当我决定将类型推断放在我的玩具（命令式）编程语言中时，我首先查看了五篇论文，盯着一些名为<！>的东西，输入了lambda calculus <！>;去...... .... **** ....？起初我尝试使用<！>“泛型变量<！>”来实现一些东西。和<！>“非通用变量<！>”;并且不知道发生了什么。然后我把它全部废弃了，坐在那里用笔记本弄清楚我是如何实现它的，实际上支持我需要的所有东西（子类型，一流函数，参数化类型等）。经过几天的思考<！>安培;在编写测试程序时，我吹走了超过一周的时间来试图找出理论上的废话。

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

Answer 23

我知道这是陈旧的，但我对那些声称理论是“无用的”并且没有它可以实践他们的职业的人的简短回答是：

没有基础理论，没有实践。

  

为什么理论有用？

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

今天考虑使用计算机。今天的普通计算机是在图灵机的基础上建模的，为了简单起见，它是一个抽象/理论的计算模型。这个理论模型位于计算的基础，我们今天使用的所有计算设备，从高端服务器到袖珍手机，都起作用，因为底层基础是合理的。

考虑算法分析。简单来说，算法分析和时间复杂度理论已被用于分类问题（例如P，NP，EXP等）以及我们的算法如何表现当试图解决不同阶级的不同问题时。

假设你的一个朋友在某个地方获得了一份工作X，而在那里，经理会提出一些简单的请求，例如：

  

Ex 1：我们拥有庞大的运载车队，可以访问多个州的不同城市。我们需要你来实现一个系统，以确定每辆车的最短路线，并从所有可能性中选择最佳。你能做到吗？

认为理论是“无用的”你的朋友没有意识到他们刚刚被给予旅行商问题（TSP）并开始设计这个系统而没有经过深思熟虑，只是发现他们天真的检查所有根据最初的要求，它们的系统无法用于任何实际目的。

事实上，他们不知道为什么系统在“可接受”的情况下工作。检查5个城市时的水平，但在10个城市变得非常缓慢，只有40个城市才冻结。他们认为它只是 <5>比5个城市测试的城市多2倍和8倍的城市“并且想知道为什么该计划不仅仅需要“2倍和8倍的时间”。分别...

理解这个理论会让他们意识到以下情况，至少一目了然：

1. 这是TSP
2. TSP是NP-hard
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
+--------------+-------+-----------------------------------------------------------------+

他们可能在一开始就意识到他们的系统不正如他们想象的那样工作。该系统后来被认为是不切实际的，并且在大量的时间，精力和其他资源被分配给项目并最终被浪费在项目上之后被取消 - 而且所有这些都是因为思想“理论无用”。

所以在这次失败之后，经理人会想：“好吧，也许这个系统被低估了;毕竟，我们国家有很多城市，而我们的计算机根本不像我们最近取消的系统那样快速地取得成功“。

管理团队将缓慢的计算机归咎于项目失败的原因。毕竟，他们不是CS理论的专家，不需要，并且那些应该成为该主题的专家并且可以告知他们的人不会。

但他们还有另一个项目。实际上更简单。一周后他们来了，请问以下内容：

  

Ex 2：我们只有几台服务器，我们的程序员不断提交程序，这些程序由于未知原因，最终会无限循环并导致服务器停顿。我们需要你来编写一个程序

Answer 24

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