ACM通信
的观点
计算机程序的应用与计算理论教学中的问题探究
图片来源:Andrij Borys Associates, Stutterstock
计算理论是计算机科学课程皇冠上的宝石之一。它从发现数学问题，如计算机无法解决的停顿问题，延伸到当今计算机科学中最著名的开放问题:P vs NP问题。自从丘奇和图灵在20世纪30年代创立我们这门学科以来，计算理论已经解决了关于计算机的一些最基本的问题:计算一个问题的解决方案意味着什么?哪些问题可以用计算机解决?哪些问题可以在理论上和实践中得到有效解决?
然而，计算理论在本科课程中占据着一个模糊的角色。在许多院校，它是计算机科学专业的必修核心课程，而在其他许多院校，它是一门高级选修课程。无论是否被要求，理论课都可能被认为是一门严肃的、甚至可能是无关紧要的小众课程，与构成计算机科学的技能和思想脱节。这并不是一个新现象，近几十年来，CS界一直在努力提高理论课程的可访问性和感知相关性。值得注意的贡献包括用于自动机实验的JFLAP软件，8以及通过可视化和实际的实验室练习来促进“所有人的np完整性”的各种努力。1
这一观点提出了在保持理论课严密性的前提下，继续提高理论课可达性的两个具体建议:一是强调搜索问题而不是课程中某些部分的决策问题;第二,用人计算机程序它是用真正的编程语言编写的标准计算模型之一，是图灵机等自动机的补充。这里的建议特别适用于学生第一次接触计算理论的本科课程。这类课程的内容千差万别，下面的建议最适用于既包含可计算性又包含复杂性理论的入门课程。
强调搜索问题
计算理论通常用决定问题:单位是/否回答的问题。然而，在计算机科学的其他领域，我们通常感兴趣搜索这些问题的解决方案由多个比特组成。举个例子，考虑一下在图中寻找汉密尔顿循环的问题——也就是说，一条路径只访问每个顶点一次。理论课通常讨论决策问题，“图G包含汉密尔顿循环吗?”但如果答案是肯定的，我们仍然不知道汉密尔顿循环的路径G．考虑相关的搜索问题“找到并输出的汉密尔顿循环”更自然、更有用G如果有的话。”
一旦他们完成了第一门理论课程，计算机科学专业的本科生就会认识到搜索和决策问题之间的联系。但是搜索问题更熟悉，更直接适用，所以有很好的理由教授理论课程中更基本的部分，强调搜索问题。值得注意的是，Knuth奖得主Oded Goldreich是这种方法的倡导者2；他的书是为数不多的现代教科书之一3.，6它采用搜索问题作为主要范式。但是搜索问题可以很容易地合并到更传统的方法中，这些方法保留了决策问题作为标准模型，我推荐这种方法将理论课程与本科CS课程的其他部分更紧密地联系起来。
数字Python程序的例子。
通过搜索问题来教授CS理论的优点和技巧已经在其他地方详细讨论过。5一个有趣的结果是，基于对计算机科学本科生的调查，搜索问题被认为明显比决策问题更有用。因为已知的感知相关性是获得良好学习结果的一个因素，这提供了间接的证据证明这种方法是有益的。
用真正的计算机程序对自动机进行补充
另一种增加学生参与和与CS课程其他部分联系的技术是使用真正的编程语言编写代码。这可以为自动机和语法提供有益的补充，这些自动机和语法通常在计算理论课程中占主导地位。形式化的模型，如图灵机，当然是必不可少的，特别是为计算本身提供一个严格的定义。然而，使用编程语言作为计算的主要模型来教授一门数学上严谨的理论课程是可能的。在这种方法中，程序模型作为底层模型分层于图灵机之上，在某些证明和定义中需要使用图灵机。绝大多数CS理论教科书并不使用编程语言作为主要的计算模型，但一些作者这样做了，例如使用Python，6红宝石,9和LISP的变体。4，7作为该方法的一个示例，请考虑图中所示的Python程序。
这段代码提供了反证法的基础，证明了一个计算问题是不可解的。具体来说，它证明了以下问题的不可解性:“给定一个Python函数(页)和输入字符串我,P返回值'是的'时用输入调用我吗?对证据的详细解释超出了本观点的范围;在这里，我将重点放在第一次接触这类材料的本科生的潜在优势上。请注意，在实践中，图中所示的代码只有在接触和实验了先决条件的概念之后才会在课堂上呈现，例如将其他Python函数的源代码作为输入并对其进行分析或以某种方式转换的Python函数。然而，在这个观点的具体和紧凑，我描述了潜在的好处，学生直接出现在这个证明。
首先，注意不可测性结果本身可以用Python程序来描述:“不可能编写一个Python程序来决定其他Python程序是否会输出。”是的’。”从某种角度来看，这与图灵机的等价表述相比，纯粹是一种装饰性的改变:“不存在一个图灵机，它可以决定其他图灵机是否接受给定的输入。”毕竟，任何理论课的学生都必须理解图灵机和计算机程序之间的等价性。然而，用与计算机科学的其他领域有明确联系的计算机程序来讨论结果的实践为教师提供了增加参与的机会;这当然是我自己的经历。
其次，在理论证明中，有些步骤用图灵机表示时是出奇地微妙，但在编程语言中就变得明显和熟悉了。图中的一个例子是使用单个参数的技巧P是否在两个单独的角色中复制并传递给双参数函数yesOnStr (P, P)．在类中，可以通过在调试器中逐步遍历程序并显示的双重角色来进一步说明这一点P:第一个参数作为源代码，第二个参数作为文本字符串。(甚至艾伦·图灵也认识到基于自动机的证明所固有的挑战。在1936年那篇开创性的介绍图灵机的论文中，他同情那些可能会觉得他的第一次证明“肯定有什么问题”的读者。10）
第三，学生可以通过积极的代码实验建立对基于代码的证明的直观理解。在图中的例子中，可以提供一个近似的版本yesOnStr ()它在有限的输入类型上正常工作。然后学生可以预测的输出diagYesOnStr ()，并通过运行代码检查他们的答案。他们可以构建代码的变体，讨论哪些变体会产生所需的矛盾，哪些不会。通过实现yesOnStr ()通过模拟，学生可以发现这个结果的一个重要扩展:我们实际上可以编写一个Python程序，在这个问题的正实例中总是正确地终止，所以问题是可辨认的但不是可决定的。
许多理论课程可以通过与计算机科学课程的其他部分建立更明确的联系而受益。
第四，一些学生可能会发现编程方法更容易转化为新问题。近年来，我向所有学生教授了三种不同的不可测性证明方法:使用图灵机的散文描述进行传统约简;显式Python程序(类似于图中的示例)，并辅以对所需矛盾的简单解释;以及赖斯定理的应用。在测试和考试中，学生可以选择使用哪一种证明方法，这三种证明方法的比例大致相当。特别是，相当一部分学生选择编写Python程序作为他们考试答案的一部分。这为编程方法对一些学生是有益的提供了经验证据，而且所有学生都能从看到多种方法中获得更好的理解是合理的。
结论
在过去的8年里，我尝试了各种方法，使本科理论课更容易上手、更吸引人。这种观点提出了两种可能性:强调搜索问题和使用真正的计算机程序。我不主张普遍或完全采纳这些建议。我自己已经放弃了这种方法的某些方面。例如，在尝试了基于搜索问题的np完整性教学后，我得出的结论是，当以传统的决策问题为重点进行教学时，这部分课程效果更好。类似地，我发现有一些关于多项式时间验证器的技术结果可以用图灵机而不是计算机程序来证明——对于本科生新手的目标受众更有指导性。
每个老师和每一群学生都是不同的;教师必须采用一种真实的教学风格，实现学生的目标，并以学生的准备水平为现实基础。我确实相信，许多理论课程可以从与计算机科学课程的其他部分建立更明确的联系中受益，而且这是有可能逐步实现的。如果决策问题和图灵机被保留为中心范式，搜索问题仍然可以在相关的时候被提及，代码片段可以用来说明微妙之处。
无论这里建议的具体想法是否被采纳，我们继续努力在本科理论课程中实现可访问性和参与性似乎很重要。计算理论是计算机科学的重要基石;我希望在未来的岁月里，越来越多的学生将欣赏它的美丽，以及它与计算机科学课程其他部分的重要联系。
参考文献
1.Crescenzi, P.， Enstrom, E.和Kann, V.从理论到实践:每个CS学生的np完整性。在ITiCSE学报》, 2013年。
2.论复杂性理论基础的教学。理论计算机科学:纪念西蒙·埃文的随笔。(2006), 348 - 374。
3.Goldreich, o . P,NP和NP-完备性:计算复杂性的基础。剑桥大学出版社，2010。
4.菲尔特琼斯可计算性和复杂性:从编程的角度。麻省理工学院出版社,1997年。
5.基于非决策问题的CS理论课程的策略。在会议记录thACM计算机科学教育技术研讨会（SIGCSE的18), 2018年。
6.MacCormick, J。什么可以计算?:《计算理论实践指南》。普林斯顿大学出版社，2018年。
7.Reus B。从编程的角度看计算的极限。施普林格,2016年。
8.罗杰，S.H.芬利，T.W.JFLAP:一个交互式形式语言和自动机包。Jones & Bartlett, 2006。
9.斯图亚特,T。理解计算:从简单的机器到不可能的程序。O ' reilly, 2013年。
10.图灵,点可计算数及其在赋值问题中的应用。在伦敦数学学会。， Vol. 2 - 42,1，(1937)， 230-265。
数字图书馆是由计算机协会出版的。版权所有©2020 ACM, Inc.
评论
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评论