ACM通信
计算机程序的应用与计算理论教学中的问题探究
图片来源:Andrij Borys Associates, Stutterstock
计算理论是计算机科学课程皇冠上的宝石之一。它从发现数学问题，如计算机无法解决的停顿问题，延伸到当今计算机科学中最著名的开放问题:P vs NP问题。自从丘奇和图灵在20世纪30年代创立我们这门学科以来，计算理论已经解决了关于计算机的一些最基本的问题:计算一个问题的解决方案意味着什么?哪些问题可以用计算机解决?哪些问题可以在理论上和实践中得到有效解决?
然而，计算理论在本科课程中占据着一个模糊的角色。在许多院校，它是计算机科学专业的必修核心课程，而在其他许多院校，它是一门高级选修课程。无论是否被要求，理论课都可能被认为是一门严肃的、甚至可能是无关紧要的小众课程，与构成计算机科学的技能和思想脱节。这并不是一个新现象，近几十年来，CS界一直在努力提高理论课程的可访问性和感知相关性。值得注意的贡献包括用于自动机实验的JFLAP软件，8以及通过可视化和实际的实验室练习来促进“所有人的np完整性”的各种努力。1
评论
Bengt尼尔森
我相信这是一个共同的转变，已经进行了至少20年。
对于计算机科学家的复杂性课程，人们甚至可以更进一步，甚至不讨论类P或NP(或超越的层次结构)。相反，只要假设SAT是一个困难的(指数时间)问题，就可以使用标准编程语言将标准简化为3SAT、Vertex Cover、CLIQUE等。
然后花一点时间在搜索问题和优化问题之间的简化上(通常一方面很简单，另一方面需要二进制搜索方法)，说明它们之间的计算关系。
对于大多数CS学生来说，完整性论证和问题分类的数学之美没有多少兴趣，他们更感兴趣的是区分什么是难，什么是容易。使用他们已经熟悉的编程概念语言，直接进入复杂性问题的核心，大大简化了学习任务。
Ganesh葛
麦考密克的观点是对这一理论价值的及时探讨
以及如何以创新的方式提供计算。我想
指出两个可能引起广泛兴趣的发展。
首先是一个名为Automaton Tutor的工具，它可以自动对问题进行评分
也能让人产生新的
问题实例(参见https://link.springer.com/chapter/10.1007/978-3-030-53291-8_1)。
它已经被广泛使用，上面的文章包括许多奖状。
第二个是一个叫做Jove (https://github.com/ganeshutah/Jove.git)的工具
提供木星笔记本涵盖所有传统的计算理论主题
再加上许多更及时的补充(例如，在正式版中使用的二元决策图
方法-可见为最小DFA)。它在实践中引入了与上下文无关的解析
通过一个计算器，要求学生用新的运算符来扩展它。
Jove不需要安装任何软件:它可以直接从它的
谷歌的Colab上的Github页面。
Jove包括最好的JFLAP(多种动画模式直接在笔记本电脑
cells)和REPL接口
(构造和显示大型自动机的可脚本执行)。它的主要
声明性代码增加了人们的理解。人们可以验证机器结构
通过动画、脚本执行和全面严格的检查(例如，同构
最小化DFA)。
朱弗在书中收录了一些迷失在时间迷雾中的重要话题:布左佐夫斯基的《DFA》
最小化是一行Python代码("Reverse;Determinize;反向;
和Brzozowski's Derivatives来处理扩展正则表达式。
基于增量规则的导数本质让人想起微积分规则，
也直接适用于结构化操作语义规则的编写。
一个完整的本科课程的形式，每周Jupyter笔记本为基础的练习
在远程教育中尤其有帮助。
总之，我完全同意麦考密克的观点;这个题目远非如此
古板的;相反，它是许多人未来教学冒险的跳板。
从实例和马尔可夫模型自动学习DFA是一个小步骤!
Ganesh葛
犹他大学计算机学院教授
显示所有2评论