Mic*_*and
27
它们是计算机科学和编程中广泛使用的概念的理论基础,理解它们可以帮助您更好地理解如何使用它们(以及它们的极限).你应该遇到的三个基本问题是:按照权力的增加顺序:
- 有限自动机,相当于正则表达式.正则表达式广泛用于编程以匹配字符串和提取文本.它们是使用基本字符,分组和重复描述一组有效字符串的简单方法.他们可以做很多事,但他们无法匹配平衡的括号.
- 下推自动机,相当于无上下文语法.当正则表达式不够强大时,文本/输入解析器和编译器会使用这些(在学习有限自动机时学到的东西之一就是正则表达式不能做的事情,这对于知道何时编写正则表达式以及何时编写是至关重要的使用更复杂的东西).无上下文语法可以描述"语言"(有效字符串集),其中解析字符串中某一点的有效性不依赖于已经看到的其他内容.
- 图灵机,相当于一般计算(你可以用电脑做的任何事情).当您了解这些内容时,您学到的一些知识可以让您了解计算本身的局限性.一个好的理论课程将教你停止问题,它可以让你找出无法编写程序的问题.一旦你发现了这样的问题,那么你就知道要停止尝试(或者将其改进为可能的东西).
了解这些不同计算机制的理论和局限性使您能够更好地理解问题和程序,并更深入地思考编程.
大约一年前,在一个自由编码交换网站上发布了一份工作请求,主要是要求一个解决停机问题的程序.有几个人回应了提议,称他们"理解要求"并且可以"立即开始".编写满足要求的程序是不可能的.理解计算理论使您不会成为那个在公开场合表明他真的不懂计算的投标人(并且在宣布理解和提出要约之前并不打算彻底调查问题).