首页 文章

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

提问于
浏览
24

在课堂上,我们了解了暂停问题,图灵机器,减少等等 . 许多同学都说这些都是抽象和无用的概念,而且知道它们并没有真正的意义(即,一旦课程结束,你就会忘记它们结束而不是失去任何东西) .

为什么理论有用?你有没有在日常编码中使用它?

24 回答

  • 1

    我发现从CS理论世界我所需要的每日幸福就是咒语"Low coupling and High Cohesion"的话语 . Roger S. Pressman在_2551285之前做出了学术性的决定 .

  • 3

    Ya,我通常使用状态图来设计程序的形状和流程 . 一旦它在理论上工作,我开始编码和测试,随着我去检查状态 .

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

  • 2

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

  • 2

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

  • 1

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

    对于许多问题,行为不当过程的界限高达过程总数的三分之一 . 这在我看来非常有用,因为你知道尝试开发更好的算法(在给定的假设下)是没有意义的 .

  • 1

    即使理论课程不会直接使用,也可能有助于你更好地思考某些事情 .

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

  • 27

    当我从大学毕业时,我认为我与其他所有人都相提并论:“我拥有CS的学士学位,其他人也很多,我们都可以做同样的事情 . ”我最终发现我的假设是假的 . 我脱颖而出,我的背景与它有很大关系 - 特别是我的学位 .

    我知道有一个“轻微”的区别,因为我有一个“B.S.”在CS,因为我的大学是全国第一个获得CS学位课程认证的学生之一(据说是1987年的#2),我在二年级毕业,获得了认证 . 当时,我认为这不重要 .

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

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

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

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

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

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

    第二天早上(第二天),我的团队私下通知我,我们的另外两名队友没有取得任何进展(实际上没有人写出“if”语句会编译),他让我接受他们的工作 . 我在下午中午完成了整个项目,我的团队花了一整天的时间来驾驶模拟器 .

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

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

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

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

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

    最重要的是,在我了解了所有这些之后,我了解到我不知道该死的东西 . 面对所有可能知道的事物,我的知识微乎其微 .

    而且我对此非常满意 . 但我建议你试试 .

  • 1

    真实的故事:

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

    阿肯色州共有106个机场 . 你能写一个能找到最短路径的程序吗?

    我认真地认为他是根据我对旅行推销员问题和NP完全性的了解而对我进行测验的 . 但事实证明他不是 . 他对此一无所知 . 他真的想要一个能找到最短路径的程序 . 当我解释说有106个因子解决方案并且发现最好的解决方案是众所周知的计算上棘手的问题时,他感到很惊讶 .

    这就是一个例子 .

  • -1

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

    有一次,例如我正在开展一个项目,包括大量的数学计算,在某些时候我们的软件失败了 . 在调试时,我发现经过一些数学运算后,我收到的数字为值为1.000000000002的DOUBLE,但从数学角度来看,不能超过1,这在程序的某个后期阶段给出了传奇的 NaN 异常 . 我花了一些时间来弄清楚这一点,但如果我更加关注“Double and Float”的近似课程,那我就不会浪费时间 .

  • 3

    当然,这很有用 .

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

    Blah blah blah ${MyTemplateString} blah blah blah.
    

    它开始时很简单,有一个厚脸皮的小正则表达式来替换 .

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

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

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

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

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

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

    在实践中,关于理论的是所有实践都是基于理论的 . 理论上 .

  • 1

    我最常用的东西:

    • 计算复杂性来编写可以优雅扩展的算法

    • 了解内存分配,分页和CPU缓存如何工作,这样我就可以编写高效的代码了

    • 了解数据结构

    • 了解线程,锁定和相关问题

    至于图灵机等的那些东西,我认为这很重要,因为它定义了我们所有人都在运作的约束条件 . 这很重要,值得欣赏 .

  • 6

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

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

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

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

  • 16

    我的一个朋友正在使用一些模板来处理语言 . 我被要求做一点咨询 . 我们讨论的部分内容是模板功能,因为如果模板是图灵完成的,他们必须真正考虑VM-ish属性以及他们的编译器如何/如果支持它 .

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

    现在,这些事情是否与数据库管理员敲定C#代码有关?可能不是 . 但是当你开始进入更高级别时,你会想要了解你的根源和基础 .

  • 1

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

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

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

  • 1

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

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

    它至少快两个数量级,三个在非常长的下游迹线上 .

    可悲的是,我必须在n树中教授一堂课,二进制树,指针和双向链接列表给几个已经接受过数据库和VB训练的程序员,以便他们理解算法 .

  • 1

    这是一个经典的二分法,介于“如何”和“什么”之间 . 你的同学正在研究如何编程软件,他们非常关注近距离的焦点;从这个角度来看,从实施的角度来看,似乎知道诸如停止状态和图灵机之类的东西并不重要 .

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

    "There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult." - C.A.R.霍尔

    祝你学习顺利!

  • 7

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

  • 21

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

  • 8

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

  • 24

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

    如果你在职业生涯中学习长远的理论,理论会给你深度,你需要的深度 . 学习第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如果你只有一本理论恕我直言的书,这应该是一本书 .

  • 4

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

  • 3

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

    当我决定将类型推理用于我的玩具(命令式)编程语言时,我首先查看了大约五篇论文,盯着一种叫做“打字的lambda演算”的东西...... .... **** ....?起初我尝试使用“泛型变量”和“非泛型变量”来实现,并且不知道发生了什么 . 然后我把它全部废弃了,坐在那里用笔记本弄清楚我是如何实现它的,实际上支持我需要的所有东西(子类型,一流函数,参数化类型等) . 经过几天的思考并且编写测试程序,我吹走了超过一周的时间来试图找出理论废话 .

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

  • 1

    我知道这已经过时了,但我对那些声称理论“无用”且他们可以在没有它的情况下练习他们的职业的人的简短回答是这样的:

    Without the underlying theory, there is no practice.

    为什么理论有用?

    理论是 Build 其他事物的基础 . 什么时候理论应用,实践是结果 .

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

    Consider algorithm analysis. 简单来说,算法分析和时间复杂性理论已被用于分类问题(例如P,NP,EXP等)以及我们在尝试解决不同类别中的不同问题时的行为方式 .

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

    例1:我们拥有大量的运载工具,可以访问多个州的不同城市 . 我们需要您实施一个系统来确定每辆车的最短路线,并从所有可能性中选择最佳路线 . 你可以做到吗?

    认为这个理论是'useless'你的朋友只是被给予旅行商问题(TSP)并开始设计这个系统而没有第二个想法,只是发现他们天真的尝试检查所有可能性,如最初的要求,是如此缓慢他们的系统无法用于任何实际目的 .

    事实上,他们不知道为什么系统在检查5个城市时工作在一个水平,但在10个城市变得非常慢,而在上升到40个城市时只是冻结 . 他们认为它只是"2x and 8x more cities than the 5 city test"并且想知道为什么程序不仅仅需要"2x and 8x more time" ...

    了解这一理论将使他们能够实现以下目标,至少一目了然:

    • 这是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
    +--------------+-------+-----------------------------------------------------------------+
    

    他们可能在一开始就意识到他们的系统不像他们想象的那样工作 . 该系统后来被认为是不切实际的,并且在将大量时间,精力和其他资源分配给项目并最终浪费在项目上之后被取消 - 所有这些都是因为思想"theory is useless" .

    因此,经过这次失败后,经理们认为“好吧,也许这个系统被低估了;毕竟,我们国家有很多城市,我们的计算机根本不像我们最近取消的系统那样快 . 取得了成功“ .

    管理团队将缓慢的计算机归咎于项目失败的原因 . 毕竟,他们不是CS理论的专家,不需要,而那些应该是这个主题的专家并且能够通知他们的人却没有 .

    但他们还有另一个项目 . 实际上更简单 . 一周后他们来了,请问如下:

    例2:我们只有几台服务器,而且我们的程序员不断提交程序,这些程序由于未知原因,最终会无限循环并导致服务器停顿 . 我们需要您编写一个程序来处理正在提交的代码,并检测提交的程序是否会在运行期间导致无限循环,并决定是否允许提交的程序在此基础上运行 . 你可以做到吗?

    亲爱的朋友再次接受挑战并立即开始工作 . 经过几周的工作,我们知道该怎么做 . 还有另一个失败......你的朋友现在感觉"dumb"因为没能解决这个问题......毕竟,请求本身让它听起来很简单 .

    不幸的是,你的朋友在坚持“理论毫无用处”的同时没有意识到,据称简单的请求实际上是一个关于可判定性的棘手问题(即停止问题本身),并且没有已知的解决方案 . 这是一项不可能的任务 .

    因此,即使开始解决该特定问题的工作也是可以避免和可预防的错误 . 如果有理论框架来理解所要求的内容,他们可能只是提出了一个不同的,可实现的解决方案......例如实施一个监控流程,只需 kill -SIGTERM <id> 任何用户流程(根据列表用户)在某些假设下垄断CPU一些任意/合理的间隔(例如,我们知道每个程序运行应该在10分钟内终止,因此任何运行20分钟的实例都应该是 kill ) .

    在结论,没有理论的实践就像没有基础的建筑 . 迟早,从正确的角度施加适量的压力会使其自身崩溃 . 没有例外 .

    您是否曾在日常编码中使用它?

    是的,但不是直接的 . 相反,我们间接地依赖它 . 需要注意的是,根据您碰巧正在处理的问题域,不同的理论概念或多或少都适用 .

    当然,我们:

    • 每天使用计算机,它依赖于计算模型(例如图灵机)

    • 写代码,它依赖于可计算性理论(例如甚至可计算的)和lambda演算(例如编程语言)

    • 依靠色彩理论和模型(例如RGB和CMYK颜色模型)进行彩色显示和打印等 .

    • 欧拉在计算机图形学中的定理,以便可以构建矩阵以围绕任意轴旋转对象,等等......

    事实上,只是简单地使用飞机旅行的人不需要理解甚至允许飞机建造并首先飞行的理论......但是当人们期望建造所述机器并使其工作时 . 你能真正期待一个甚至不了解飞行原理的人会得到一个好结果吗?

    在历史的大部分时间里,没有人能够建造一架飞行机器(有些人甚至死于测试他们的飞机),直到莱特兄弟理解了关于飞行的某些理论概念并设法将它们付诸实践,这真的是巧合吗?

    这不是巧合 . 我们今天拥有大量的工作技术,因为构建它们的人理解并应用了允许他们首先工作的理论原则 .

  • 14

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

相关问题