在课堂上，我们学习了停机问题，图灵机，归约等。很多同学说这些都是抽象无用的概念，了解它们没有任何意义（即，一旦课程结束就可以忘记它们）结束并且不会丢失任何东西）。
为什么理论有用？您是否曾经在日常编码中使用它？
Claudiu
问问题
10763 次
24 回答
29
真实的故事：
当我从研究生院毕业获得第一份编程工作时，拥有我工作的公司的人是飞行员。在我被录用几周后，其中一个人问我这个问题：
阿肯色州有106个机场。你能写一个程序来找到降落在每个人身上所需的最短路线吗？
我认真地认为他是在问我关于旅行商问题和 NP 完备性的知识。但事实证明他不是。他对此一无所知。他真的想要一个能找到最短路径的程序。当我解释说有 106 个因子解决方案并且找到最好的一个是众所周知的计算上难以解决的问题时，他感到很惊讶。
这就是一个例子。
于 2008-10-24T22:12:09.493 回答
24
当我大学毕业时，我以为我和其他人一样：“我有 CS 学士学位，很多其他人也是如此，我们基本上都可以做同样的事情。” 我最终发现我的假设是错误的。我脱颖而出，这与我的背景有很大关系——尤其是我的学位。
我知道有一个“轻微”的区别，因为我的大学是美国第一所（据说是 1987 年的第二个）获得其 CS 学位课程认证的大学之一，我在 CS 中获得了“BS”，而我在第二类毕业以获得该认证。当时，我认为这并不重要。
在高中和大学期间，我还注意到我在 CS 方面做得特别好——比同龄人好得多，甚至比我的许多老师还要好。我经常被要求帮助，做过一些辅导，被要求帮助完成一个研究项目，并且在没有其他人的情况下被允许进行独立学习。我很高兴能够提供帮助，但我并没有考虑太多不同之处。
大学毕业后（美国足协），我在空军呆了四年，其中两年正在申请我的计算机科学学位。在那里，我注意到我的同事中很少有人拥有与计算机相关的学位甚至培训。空军让我参加了五个月的认证培训，在那里我再次发现缺乏学位或培训。但在这里我开始注意到不同之处——很明显，我遇到的许多人并不真正知道他们在做什么，其中包括受过培训或获得学位的人。请允许我举例说明。
在我的空军认证培训中，总共有 13 人（包括我）。作为空军军官或同等学历，我们都有学士学位。根据年龄和等级，我处于中间（我是六名 O-1 和六名 O-3 及以上的 O-2）。在这次培训结束时，空军给我们所有人盖上橡皮图章，让我们所有人都同样有能力为国防部的任何部门获取、建造、设计、维护和操作任何计算机或通信系统。
然而，在我们十三个人中，只有六人拥有任何形式的计算机相关学位；其他七人拥有从航空到化学/生物学再到心理学的学位。在我们六个拥有计算机科学学位的人中，我了解到有两个从未编写过任何类型的程序，并且从未使用过电脑，只是随便（写论文、玩游戏等）。我了解到，我们中的另外两个人在他们的计算机科学学位课程中已经在一台计算机上编写了一个程序。只有另外一个人和我自己写过不止一种程序，或者使用过不止一种计算机——事实上，我们发现我们两个写过很多程序，使用过很多种计算机。
在我们为期五个月的培训即将结束时，我们班被分配了一个编程项目，我们分成四组分别进行。为了公平地传播“编程人才”，我们的导师分班，他们分配了团队负责人、技术负责人和开发人员的角色。每个小组都有一周的时间在教练提供的飞行力学库之上为飞行模拟器实施（在 Ada 中）全屏、基于文本的用户界面（这是 1990 年）。我被指派为我的四人团队的技术主管。
我的团队负责人（没有计算机学位）要求我们三个人将项目分成任务，然后将其中的三分之一分配给我们每个人。我在第一天的中间完成了我的第三个任务，然后在剩下的时间里帮助我的另外两个队友，和我的团队负责人交谈（BSing ;^），并在我的电脑上玩。
第二天早上（第二天），我的团队负责人私下告诉我，我们的另外两个队友没有取得任何进展（其中一个实际上无法写出能够编译的“如果”语句），他让我接手他们的工作。我在下午三点前完成了整个项目，我的团队花了一整天的时间在模拟器上飞行。
另一个具有同等 CS 学位的人也被指定为他团队的技术主管，他们在第三天结束时完成了工作。他们也开始飞行他们的模拟器。到本周末，另外两支球队还没有完成，甚至没有取得重大进展。我们不被允许帮助其他球队，所以就这样了。
与此同时，到第三天中午，我注意到飞行模拟器似乎表现“错误”。因为我的一个同学有航空学学位，所以我问他这件事。他一头雾水，然后坦白自己根本不知道是什么让飞机飞起来的！？！我傻眼了！事实证明，他的整个学位课程都是关于安全和坠机调查的——飞行背后没有真正的数学或科学。另一方面，我可能辅修过航空学（还记得 USAFA 吗？），但我们设计了机翼并进行了真正的风洞测试。因此，我在本周剩下的时间里悄悄地重写了教练提供的飞行力学库，直到模拟器“正确”飞行。
从那时起，我作为一名承包商和偶尔作为一名员工度过了近 20 年，一直从事软件开发和相关活动（DBA、架构师等）。我继续找到更多相同的东西，最终我放弃了我年轻的假设。
那么，我到底发现了什么？不是每个人都是平等的，这没关系——我不是一个更好的人，因为我可以有效地编程，但如果你需要我的话，我会更有用。我了解到我的背景真的很重要：在一个电工和电气工程师家庭长大，制造电子套件，从字面上阅读学校/公共图书馆的每一本计算机书籍，因为我没有真正的计算机，然后搬到新的我的高中确实有电脑的城市，然后得到了我自己的电脑作为礼物，去有许多不同大小和类型的电脑（PC到大型机）的学校，从一所非常好的工程学校获得认可的学位，不得不写作在不同类型的计算机上使用不同语言的大量程序，
最终，我了解到我的能力建立在了解计算机如何从电气层面向上工作的基础之上——离散电子元件、电路、子系统、接口、协议、位、字节、处理器、设备、驱动程序、库、程序、系统、网络，一直到我现在经常工作的大型企业级企业集团。所以，当这该死的东西行为不端时，我确切地知道如何以及为什么。我知道什么不能做，什么可以做。而且我知道很多关于已经完成的事情，已经尝试过的事情，以及相对未探索的事情。
最重要的是，在我学会了所有这些之后，我才知道我什么都不知道。面对所有可能知道的事情，我的知识是微不足道的。
我对此很满意。但我建议你试试。
于 2008-10-25T00:06:00.527 回答
23
当然，它很有用。
想象一个开发模板引擎的开发人员。你知道那种事...
Blah blah blah ${MyTemplateString} blah blah blah.
它开始很简单，用一个厚脸皮的小正则表达式来执行替换。
但渐渐地，模板变得更加花哨，开发人员包括模板化列表和字符串映射的功能。为此，他编写了一个简单的小语法并生成了一个解析器。
变得非常狡猾，模板引擎最终可能包含条件逻辑的语法，以根据参数的值显示不同的文本块。
具有 CS 理论背景的人会认识到模板语言正在慢慢变得图灵完备，也许解释器模式将是实现它的好方法。
为模板构建解释器后，计算机科学家可能会注意到大多数模板请求是重复的，一遍又一遍地重新生成相同的结果。因此开发了一个缓存，所有请求在执行昂贵的转换之前都通过缓存进行路由。
此外，一些模板比其他模板复杂得多，渲染时间也更长。也许有人想到在渲染每个模板之前估计它的执行。
可是等等！！！团队有人指出，如果模板语言真的是图灵完备的，那么估计每个渲染操作的执行时间的任务就是Halting Problem的一个实例！！咳咳，不要这样！！！
在实践中，关于理论的事情是，所有的实践都是基于理论的。理论上。
于 2008-10-24T22:23:24.960 回答
17
我最常用的东西：
- 编写可优雅扩展的算法的计算复杂度
- 了解内存分配、分页和 CPU 缓存的工作原理，以便编写高效的代码
- 对数据结构的理解
- 了解线程、锁定和相关问题
至于图灵机等方面的东西。我认为这很重要，因为它定义了我们所有人操作的约束条件。欣赏这一点很重要。
于 2008-10-24T22:05:00.240 回答
16
这是学习代数和被教如何使用计算器之间的区别
如果您了解代数，您就会意识到同一个问题可能以不同的形式表现出来，并且您了解将问题转换为更简洁形式的规则
如果您只知道如何使用计算器，您可能会浪费大量时间来处理（a）已经解决、（b）无法解决或（c）与其他问题类似（已解决或未解决）您无法识别，因为它的形式不同
假装一下，计算机科学是物理学……这个问题看起来很傻吗？
于 2008-10-26T17:10:59.387 回答
8
我的一个朋友正在研究一种带有一些模板的语言。我被要求做一些咨询。我们讨论的部分内容是关于模板功能，因为如果模板是图灵完备的，他们将不得不真正考虑 VM-ish 属性以及他们的编译器如何/是否支持它。
我的故事是这样的：自动机理论仍然被教授，因为它仍然具有相关性。停止问题仍然存在，并且限制了您可以做的事情。
现在，这些事情是否与数据库管理员敲定 C# 代码有关？可能不是。但是当你开始进入更高级的水平时，你会想要了解你的根源和基础。
于 2008-10-24T22:07:19.987 回答
7
虽然我没有将它们直接应用到日常工作中，但我知道我对正规计算机科学的教育影响了我的思维过程。我当然从一开始就避免了某些错误，因为我从灌输给我的正式方法中吸取了教训。
在他们学习的时候，它可能看起来毫无用处；但我敢打赌，你的同学最终会遇到一个问题，他们将使用他们所教的东西，或者至少是它背后的思维模式......
打蜡...打蜡...打蜡...打蜡...这与空手道有什么关系？
于 2008-10-24T22:31:19.813 回答
6
在一项工作中，我的任务是改进我们的配电模型的网络跟踪算法，因为他们使用的算法太慢了。三相网络本质上是三个 n 树（因为电网中不允许使用环路）。网络节点在数据库中，一些原始团队无法弄清楚如何构建内存模型，因此跟踪是通过数据库上的连续深度 SELECT 完成的，在每个阶段进行过滤。因此，要从变电站跟踪一个节点，十个节点至少需要 10 个数据库查询（最初的团队成员是数据库专家，但缺乏良好的算法背景）。
我编写了一个解决方案，将数据库中的 3 个 n-tree 节点网络转换为一个数据结构，其中每个节点在节点结构数组中存储一次，并且使用内部的双向链接指针将 n-tree 关系转换为三个二叉树阵列，以便可以轻松地在任一方向上跟踪网络。
它至少要快两个数量级，在很长的下游轨迹上要快三个数量级。
可悲的是，为了让他们理解算法，我不得不向其他几位接受过数据库和 VB 培训的程序员实际教授一门关于 n 树、二叉树、指针和双向链表的课程。
于 2008-10-27T21:33:42.630 回答
4
这是一个经典的二分法，在“如何”和“什么”之间。你的同学正在研究“如何”编写软件，他们非常关注近焦；从这个角度来看，从实现的角度来看，似乎了解诸如停止状态和图灵机之类的东西并不重要。
但是，“如何”在计算机科学领域所期望的实际工作中很少。事实上，我认识的大多数成功的工程师可能会认为它不到实际工作的 20%。“做什么”要重要得多；为此，计算机科学的基础知识至关重要。您想做的“什么”与设计有关，而不是与实施有关；好的设计是……好吧，我们就称它为“不平凡的”。
“构建软件设计有两种方法：一种方法是简单到没有明显的缺陷，另一种方法是复杂到没有明显的缺陷。第一种方法要困难得多。” - 汽车霍尔
祝你学业顺利！
于 2008-10-25T00:48:30.893 回答
3
我认为理解计算的基本模型是有用的：确保在实践中你永远不需要能够将图灵机转换为寄存器机，但是学习如何看到两个非常不同的问题实际上是同一概念的实例是至关重要的技能。
于 2008-10-24T22:10:10.290 回答
3
大多数知识不是“实用的”，而是帮助您以您无法预料的方式连接点，或者为您提供更丰富的词汇来描述更复杂的想法。
于 2008-10-24T22:10:19.357 回答
3
重要的不是你研究的具体问题，而是你通过研究它们学到的原理。我每天在工作中都会使用有关算法、数据结构、编程语言和操作系统的概念。如果你是一名程序员，你会一直做出影响系统性能的决定。你需要在基本的抽象概念上有坚实的基础才能做出正确的选择。
于 2008-10-25T00:26:02.250 回答
3
从 CS 毕业后，我也有类似的想法：我们研究的一堆理论在实践中完全没用。这在短时间内被证明是正确的，但是当您处理复杂的任务时，理论绝对比实践更有价值。经过几年的编码，每个人都可以编写一些“工作”的程序，但并不是每个人都能理解如何。无论我们大多数人在某个时候会处理什么性能问题、网络延迟、精度、可扩展性等。在这个阶段，理论是至关重要的。为了在处理复杂系统时设计一个好的解决方案，了解内存管理的工作原理、进程和线程的概念、内存是如何分配给它们的，或者用于性能的高效数据结构等非常重要。
例如，有一次我正在做一个包含大量数学计算的项目，但在某个时候我们的软件失败了。在调试时，我发现经过一些数学运算后，我收到了一个数值为 1.000000000002 的数字，但从数学的角度来看，它不能 > 1，这在程序的某个后期阶段给出了传说中的NaN异常。我花了一些时间来解决这个问题，但如果我更加关注“ Double and Float 的近似”课程，我就不会浪费时间了。
于 2014-08-19T18:35:00.780 回答
2
如果您在一家从事开创性工作的公司工作，那么能够与架构师和开发人员交流其好处是很重要的。有很多关于各种技术的炒作，定位自己可能很困难。当你用科学和理论的术语来构建你的创新时，你肯定处于优势，客户会觉得你是真实的东西。我可以告诉人们：有一种处理状态、编码和非确定性（即复杂性）的新方法，你绝对可以比现在更有效率。
如果你在你的职业生涯中放眼长远，学习理论会给你带来深度，你需要成长的深度。学习第 5 或第 6 种编程语言的投资回报将远低于学习第 2 和第 3 语言。接触理论将使您了解真正的工程，了解自由度在哪里以及如何做出正确的权衡。
重要概念 1) 状态，2) 编码，3) 非确定性。如果你不认识他们，他们不会帮助你。理论应该为您提供的是大局和基本概念如何组合在一起的感觉。它应该可以帮助你磨练你的直觉。
示例：上面的一些答案提到了停机问题和图灵机。当我在大学里看到图灵的论文时，我一点也不觉得开悟。有一天，我遇到了 Goedel 的不完备性定理，尤其是 Goedel 编号。事情开始变得很有意义。多年后，我在一家书店读到了 Georg Cantor 的故事。现在我真正开始了解图灵机和停机问题。自己尝试并在 Wikipedia 上查找“康托尔对角线论证”。这是您在智力上会遇到的最令人敬畏的事情之一。
深思熟虑：典型的图灵机并不是设计状态转换机的唯一方法。具有两个而不是一个磁带的图灵机将为您提供更多算法的速度。http://www.math.ucla.edu/~ynm/papers/eng.ps
通过阅读本书，您可以比我更有效地接触这些见解。链接在这篇文章的底部。（至少，请查看亚马逊上的目录以了解这一切）：
我发现罗森伯格的这本书耸人听闻。http://www.amazon.com/The-Pillars-Computation-Theory-Nondeterminism/dp/0387096388如果你只有一本关于理论的书恕我直言，这应该是一本。
于 2014-08-19T14:57:18.217 回答
1
我不是每天都使用它。但它给了我很多理解，这对我每天都有帮助。
于 2008-10-24T22:06:46.290 回答
1
我发现我每天都需要从 CS 理论世界获得幸福，就是说出“低耦合和高内聚”的口头禅。罗杰·S·普雷斯曼在史蒂夫·麦康奈尔让它成为时尚之前就让它变得学术化了。
于 2008-10-24T22:45:57.100 回答
1
是的，我通常使用状态图来设计程序的形状和流程。一旦它在理论上起作用，我就开始编码和测试，同时检查状态。
我发现它们也是向其他人解释流程行为的有用工具。
于 2008-10-25T01:02:32.317 回答
1
简单的。例如：如果我使用的是RSACryptoServiceProvider，我想知道那是什么以及为什么我可以信任它。
于 2008-10-26T17:39:20.890 回答
1
因为 C++ 模板实际上是某种 lambda 演算。见 www.cs.nott.ac.uk/types06/slides/michelbrink_types_06.pdf
于 2008-10-27T20:57:41.377 回答
1
我现在正在学习我的分布式算法课程。有一章是关于容错的，它包含一些关于有多少进程可能失败（或行为不端）的上限的证明，以便分布式算法可以正确处理它。
对于许多问题，行为不端的进程的界限高达进程总数的三分之一。我认为这非常有用，因为您知道尝试开发更好的算法（在给定的假设下）是没有意义的。
于 2009-01-06T19:05:02.237 回答
1
即使不直接使用理论课程，它也可以帮助您更好地思考某些事情。
你不知道你的老板会要求你做什么，你可能不得不使用一些你认为不会有好处的东西，正如 Jeffrey L Whitledge 所说。
于 2009-02-01T18:35:16.477 回答
1
老实说，我有点不同意这里的很多答案。我写了我的第一个编译器（为了好玩；我真的有太多的咖啡/空闲时间）而没有参加编译器课程；基本上我只是扫描了另一个编译器的代码并遵循了模式。我可以用 C 语言编写一个解析器，但如果我的生活依赖于它，我想我不记得如何绘制下推自动机了。
当我决定要在我的玩具（命令式）编程语言中加入类型推断时，我首先查看了大约五篇论文，盯着一个叫做“类型化 lambda 演算”的东西……………… **** ……？起初我尝试用“泛型变量”和“非泛型变量”来实现一些东西，但不知道发生了什么。然后我把它全部报废了，拿着一个笔记本坐在那里，思考如何在支持所有我需要的东西（子类型、一流函数、参数化类型等）的情况下实际实现它。经过几天的思考和编写测试程序，我花了一个多星期的时间试图弄清楚理论上的废话。
了解计算的基础知识（即虚拟内存如何工作、文件系统如何工作、线程/调度、SMP、数据结构）都被证明非常有用。复杂性理论和 Big-O 的东西有时被证明是有用的（特别是对诸如 RDBMS 设计之类的东西有用）。停机问题和自动机/图灵机理论？绝不。
于 2010-01-14T06:39:37.317 回答
1
我知道这已经过时了，但我对那些声称理论“无用”并且他们可以在没有理论的情况下实践他们的职业的人的简短回复是这样的：
没有基础理论，就没有实践。
为什么理论有用？
理论是建立其他事物的基础。当理论应用时，实践就是结果。
考虑今天的计算机。今天的普通计算机是在图灵机之上建模和构建的，为了简单起见，图灵机是一个用于计算的抽象/理论模型。这个理论模型是计算的基础，我们今天使用的所有计算设备，从高端服务器到袖珍手机，都可以工作，因为底层基础是健全的。
考虑算法分析。简单来说，算法分析和时间复杂性理论已被用于对问题进行分类（例如 P、NP、EXP 等）以及我们在尝试解决不同类别中的不同问题时的算法行为。
假设您的一个朋友在某个地方 X 找到了一份工作，并且在那里，一位经理提出了一些简单的请求，例如以下示例：
示例 1：我们拥有一支庞大的送货车队，他们前往多个州的不同城市。我们需要您实施一个系统来确定每辆车的最短路线是什么，并从所有可能性中选择最佳路线。你能做到吗？
认为这个理论是“无用的”，你的朋友没有意识到他们刚刚遇到了旅行商问题 (TSP) 并开始不假思索地设计这个系统，只是发现他们检查所有可能性的天真尝试，因为最初要求，太慢了，他们的系统无法用于任何实际目的。
事实上，他们不知道为什么系统在检查 5 个城市时工作在“可接受”的水平，但在 10 个城市时变得非常缓慢，并且在只检查 40 个城市时就卡住了。他们认为它只是“比 5 城市测试多 2 倍和 8 倍的城市”，并想知道为什么该程序不简单地分别需要“多 2 倍和 8 倍的时间”......
理解该理论将使他们至少一目了然地意识到以下几点：
- 这是TSP
- TSP 是 NP 难的
- 他们算法的增长顺序是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 理论专家，也不必如此，而那些本应是该主题的专家并且可以告知他们的人却没有。
但他们有另一个项目。其实比较简单。他们一周后来，要求说以下内容：
例 2：我们只有几台服务器，我们有程序员不断提交程序，由于未知原因，最终陷入无限循环并占用服务器。我们需要你编写一个程序，对提交的代码进行处理，检测提交的程序在运行过程中是否会造成无限循环，并在此基础上决定是否允许提交的程序运行。你能做到吗？
你亲爱的朋友再次接受挑战并立即开始工作。工作几个星期后，没有任何结果，你的朋友压力很大，不知道该怎么办。又一次失败……你的朋友现在因为没能解决这个“简单的问题”而感到“愚蠢”……毕竟，请求本身使它听起来很简单。
不幸的是，您的朋友虽然坚持“理论是无用的”，但并没有意识到，据称简单的请求实际上是一个关于可判定性的棘手问题（即停止问题本身），并且没有已知的解决方案。这是一项不可能完成的任务。
因此，即使开始着手解决该特定问题也是一个可避免和可预防的错误。如果有理解所要求内容的理论框架，他们可以提出一个不同的、可实现的解决方案......例如实施一个可以简单地监控kill -SIGTERM <id>任何用户进程的监控进程（根据用户列表) 在某些假设下（例如，我们知道每个程序运行都应该在 10 分钟内终止，因此任何运行超过 20 分钟的实例都应该被kill编辑），从而在某些任意/合理的时间间隔内垄断 CPU。
总之，没有理论的实践就像没有地基的建筑。迟早，来自正确角度的适量压力会使它自行塌陷。没有例外。
您是否曾经在日常编码中使用它？
是的，但不是直接的。相反，我们间接依赖它。这里需要注意的是，不同的理论概念将或多或少适用，具体取决于您碰巧正在研究的问题领域。
当然，我们：
- 每天使用计算机，这依赖于计算模型（例如图灵机）
- 编写代码，这依赖于可计算性理论（例如什么是可计算的）和 lambda 演算（例如用于编程语言）
- 依靠色彩理论和模型（例如 RGB 和 CMYK 颜色模型）进行彩色显示和打印等。
- 计算机图形学中的欧拉定理，以便可以构建矩阵以围绕任意轴旋转对象，等等......
事实是，仅仅使用飞机旅行的人不需要理解甚至允许飞机首先建造和飞行的理论……但是当人们期望有人建造所说的机器并使它们工作时。 .. 你真的能期待一个连飞行原理都不懂的人会有好的结果吗？
Was it really a coincidence that, for most of history, no one was able to build a flying machine (and a few even died testing theirs) until the Wright brothers understood certain theoretical concepts about flight and managed to put them into practice?
It's no coincidence. We have a lot of working technology today because the people who built them understood, and applied, the theoretical principles that allowed them to work in the first place.
于 2017-02-21T13:51:41.943 回答
-1
我想这取决于你进入哪个领域。
于 2008-10-24T22:15:45.897 回答