理论计算机科学何时有用？

Question

理论计算机科学何时有用？

theoryturing-machineshalting-problemcomputation

29

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

理论为什么有用？你是否在日常编码中使用它？

- Claudiu

1

学习抽象概念和事物的工作原理并不是无用的，即使你在日常工作中从未直接应用它。这是我的两分钱。那么，“理论计算机科学”到底是什么呢？观察此处 - Matthew Scharley

“理论性”的定义不是意味着它的实际应用受到限制吗？ - davr

“理论的”可以简单地理解为“未经证实的”。例如：大多数数学理论。有些理论无法被绝对证明，但它们却一直被使用着。以欧拉的工作为例，其中一些直到最近才被绝对证明，而且只有全世界少数人能够理解。 - Matthew Scharley

5

理论并不意味着未经证实，它的意思是实验室相反的概念。它指的是在纸上推导出来的，而不是在实验室中得出的。图灵机就是一个例子，因为它的属性在机器被建造之前就被发现了。 - Jeffrey L Whitledge

@[davr]：实践从理论中演化并为其做出贡献。牛顿的万有引力定律是关于重力的一种理论，它为许多实际应用提供了基础，并解释了许多事物的可观察行为...但并非所有事物都能被解释。例如，水星的轨道直到爱因斯坦应用他的新理论（相对论）之后才能被解释。如此循环往复。 - Steven A. Lowe

显示剩余4条评论

24个回答

24

当然，它很有用。

想象一个开发者正在开发一个模板引擎。你知道那种东西……

Blah blah blah ${MyTemplateString} blah blah blah.

它最开始很简单，只是用一个调皮的正则表达式来执行替换。

但渐渐地，模板变得更加复杂，开发者添加了对字符串列表和映射的模板化特性。为此，他编写了一个简单的语法，并生成了一个解析器。

非常巧妙的是，模板引擎最终可能包括一种条件逻辑语法，根据参数的值显示不同的文本块。

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

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

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

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

关于理论，实践上所有的实践都是基于理论的。从理论上说。

- benjismith

24

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

我知道有一个“轻微”的区别，那就是我有一个计算机科学“学士学位”，因为我的大学是全国第二所获得计算机科学专业认证的学校之一（据说是在1987年），我是第二个获得该认证的班级的毕业生。当时，我认为这并不重要。

在高中和大学期间，我还注意到，在计算机科学课程方面，我表现特别好——比我的同龄人甚至比许多老师都要好。我经常被人请教，做过一些辅导工作，被要求协助研究项目，并被允许在没有其他人参与的情况下进行自主研究。我很高兴能够帮助别人，但我并没有想太多这种差异。

大学毕业后（美国空军学院），我在空军服役了四年，其中两年应用了我的计算机科学学位。在那里，我注意到很少有同僚拥有与计算机相关的学位或培训经历。空军将我派去接受为期五个月的认证培训，在那里我再次发现缺乏学位或培训。但是在这里，我开始注意到不同之处——显然，我遇到的许多人并不真正知道他们在做什么，这包括那些接受过培训或拥有学位的人。请允许我举个例子。

在我参加的空军认证培训中，共有十三个人（包括我）。作为空军军官或相当职务的人，我们都拥有学士学位。根据年龄和军衔，我排名中等（我是六个O-1和六个O-3以上的人中间的一个O-2）。在此培训结束时，空军将我们所有人一视同仁地认为能够获取、构建、设计、维护和操作国防部任何部门的任何计算机或通信系统。

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

在我们为期五个月的培训即将结束时，班里被分成四组，各自承担一个编程项目。为了公平分配“编程天才”，我们的导师们将班级划分，并分配团队领袖、技术领袖和开发人员的角色。每个小组被要求在一周内使用Ada实现（这是1990年）一个全屏幕、基于文本的用户界面，用于一个由导师提供的飞行力学库的模拟器。我被分配为我的四人团队的技术领袖。

我的团队领袖（没有计算机学位）让我们三个人将项目分解为任务，然后将其中的三分之一分配给每个人。我在第一天中午就完成了我的任务，然后花费其余的时间帮助我的其他两个队友，与我的团队领袖交谈（闲聊 ;^），以及玩电脑游戏。

第二天早上（第二天），我的团队领袖私下告诉我，我们的另外两个队友没有取得任何进展（其中一个甚至无法编写可编译的“if”语句，并要求我接手他们的工作。我在下午中期完成了整个项目，我的团队花了剩下的时间来操作模拟器。

另外一个有计算机科学学位的人也被指定为他团队的技术领袖，他们在第三天结束时完成了项目。他们也开始使用模拟器。另外两个团队在那周内没有完成或取得重大进展。我们不允许帮助其他团队，因此就这样结束了。

同时，在第三天中午，我注意到飞行模拟器似乎表现“不正确”。由于我的同学拥有航空学位，我询问了他。他很惊讶，然后坦白地说他并不知道飞机是怎么飞的？！我感到震惊！原来他的整个学位项目都是关于安全和事故调查--没有真正的飞行数学或科学。另一方面，我可能只是航空学的辅修生（还记得美国空军学院吗？），但我们设计了机翼并进行了真实的风洞测试。因此，我悄悄地花了整个周末重新编写了导师提供的飞行力学库，直到模拟器飞行“正确”为止。

从那时起，我已经做了将近20年的承包商，并且偶尔担任职员，总是从事软件开发及相关活动（数据库管理员、架构师等）。我继续找到了更多相同的事情，最终放弃了我的青春期假设。那么，我到底发现了什么？并不是每个人都是平等的，这很正常——我不是一个更好的人，只因为我能够有效地编程，但是如果你需要我这样的技能，我就更有用。我意识到我的背景真的很重要：在一个电工和电气工程师家庭中成长，组装电子套件，在学校/公共图书馆里阅读每一本电脑书，因为我没有真正接触到电脑，然后搬到一个新城市，我的高中有了电脑，然后收到自己的电脑作为礼物，上了许多有不同规模和种类电脑的学校（从个人电脑到大型机），从一个非常好的工程学院获得了认证学位，在不同种类的电脑上用不同的编程语言编写大量程序，编写难度较大的程序（例如使用自定义汇编语言编写自己的虚拟机或Huffman压缩实现等），自己排除故障，从零部件组装自己的电脑并安装所有软件等等。

最终，我意识到，我的能力建立在了了解电脑从电气层面开始如何工作的基础上——离散电子元件、电路、子系统、接口、协议、位、字节、处理器、设备、驱动程序、库、程序、系统、网络，一直到我现在经常处理的大型企业级集成。所以，当这该死的东西出现问题时，我知道如何以及为什么会出现问题。我知道什么不能做以及什么可以做。我也知道很多已经完成的工作、已经尝试的事情以及仍然相对未开发的事情。

最重要的是，在我学习了所有这些之后，我意识到我什么也不知道。面对所有潜在的知识，我的知识微不足道。

但我对此非常满足。但我建议你也尝试一下。

- Rob Williams

我毕业于全国为数不多的获得认证的软件工程专业之一。现在我已经进入了职场，我看到那些没有接受过像我这样优质教育的人与我之间存在巨大差距。此外，自从我10岁开始就一直在折腾电脑，这也有所帮助。 - Kibbee

2

好帖子 :) 最近我上了几门与数学相关的课程（偏微分方程，张量，密码学，图像处理等），我相信这将会有所回报。 - Nils

2

你能否稍微简洁一下这个答案，并真正关注回答实际问题吗？ - nbro

17

我最常使用的技术：

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

至于图灵机等方面的内容，我认为这很重要，因为它定义了我们所有人所操作的约束条件。这很重要需要被认识到。

- Nick

复杂度是一个有用的概念。它有助于开发设计部分 - 实际编码并不那么重要。 - aehlke

请您能否举一个应用计算复杂度知识编写实际程序算法的例子？同时，通过给出具体的例子，说明理解内存分配、页面调度等数据结构、多任务等的重要性。 - nbro

17

这就像学习代数和学会使用计算器的区别。

如果你懂代数，你会意识到同一个问题可能以不同的形式呈现，而且你也了解如何把问题转化为更简洁的形式的规则。

如果你只知道如何使用计算器，你可能会在一个已经被解决的问题上浪费很多时间，或者是对于一个无法解决的问题一直按键，还有可能是遇到一个与其他问题相似（已解决或未解决）但你因为问题形式不同而无法识别的问题。

如果假装计算机科学是物理学……那这个问题是不是看起来很傻？

- Steven A. Lowe

8

我的一个朋友正在开发一种带有一些模板的语言。我被邀请来进行一些咨询。我们讨论的一部分是关于模板功能，因为如果这些模板是图灵完备的，他们就必须考虑虚拟机属性以及他们的编译器是否支持它。

我的观点是：自动机理论仍在教授，因为它仍然具有相关性。停机问题仍然存在并限制了你能做什么。

现在，这些东西对于一个数据库工程师打出C#代码是否有意义？可能没有。但当你开始进入更高级别时，你会想要了解你的根和基础。

- Vlion

7

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

他们在学习时可能觉得这些知识毫无用处；但我敢打赌，你的同学最终会遇到一个问题，他们会运用所学的知识，或者至少是背后的思维模式...

上蜡...下蜡...上蜡...下蜡...这跟空手道有什么关系呢？

- Toybuilder

6

在一份工作中，我被分配任务改进我们的电力分配模型的网络追踪算法，因为他们使用的那个太慢了。三相网络本质上是三个n-树（因为电力网络中不允许循环）。网络节点存储在数据库中，一些原始团队成员无法构建内存模型，所以追踪是通过对数据库进行连续深度SELECT查询并在每个相位上进行过滤来完成的。因此，要跟踪离变电站十个节点的节点，至少需要10个数据库查询（原始团队成员是数据库高手，但缺乏良好的算法背景）。

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

它至少快了两个数量级，对于非常长的下游跟踪则快了三个数量级。

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

- CMPalmer

4

这是一个经典的二分法，分别涉及“如何”和“什么”。你的同学们正在关注“如何”编写软件，并且非常专注于近期目标；从这个角度来看，也就是实现的角度，似乎了解像停机状态和图灵机之类的内容并不重要。

然而，“如何”只占计算机科学实际工作的很小一部分。事实上，我认识的大多数成功工程师可能把它归为实际工作的不到20%。“做什么”远比“如何”重要得多；而在此方面，计算机科学的基础知识至关重要。“做什么”更多地涉及设计而非实现；而好的设计是……嗯，我们只能称其为“非平凡的”。

“有两种方法可以构建一个软件设计：一种方法是使它变得简单，以至于显然没有缺陷；另一种方法是使它变得如此复杂，以至于没有明显的缺陷。第一种方法要难得多。”- C.A.R. Hoare 祝你学业有成！

- McWafflestix

3

我从计算机科学专业毕业后也曾认为，我们所学的理论在实践中完全没用。然而，在处理复杂任务时，理论却比实践更有价值。几年编程经验后，每个人都可以写出一些“可行”的程序，但并不是每个人都能理解其中原理。不管怎样，我们大多数人在某个时间点都会遇到性能问题、网络延迟、精度、可扩展性等等。此时，理论显得尤为关键。为了设计一个好的解决方案，就必须了解内存管理的工作方式，进程和线程的概念，以及如何将内存分配给它们，或者高效数据结构以提高性能。

例如，有一次我正在开发一个包含大量数学计算的项目，但软件失败了。调试时，我发现某些数学运算会返回一个值为 1.000000000002 的 double 类型数字，但从数学角度来看，它不可能＞1。这个问题在程序的后续阶段引发了传说中的NaN异常。我花费了一些时间才找到问题所在，但如果我更加注意「Double 和 Float 的近似」这节课，那么就不会浪费那么多时间了。

- eldjon

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jeffrey L Whitledge · Accepted Answer

真实故事：

当我从研究生院毕业后得到我的第一份编程工作时，我所工作公司的老板是飞行员。在我入职几周后，其中一个老板问了我这个问题：

阿肯色州有106个机场。你能写一个程序，找出降落在每个机场所需的最短路径吗？

我当时认为他在考验我对于旅行推销员问题和NP完全性知识的掌握。但结果表明他并不知道这些。他真正想要的是一个能够找到最短路径的程序。当我解释说有106的阶乘种可能性，并且找到最佳解决方案是一个已知的计算难题时，他感到惊讶。

这就是一个例子。