基于计算思维与创新能力培养的计算理论课程教学改革探索

李占山，吕 帅

（吉林大学 计算机科学与技术学院，吉林长春 130012）

0 引 言

前一段时间网上流传中国科学院研制“龙芯”的胡伟武老师的一个视频，其中提到中国能够开发Java虚拟机的人才很少的问题，该问题的出现引人思考。我国计算机类专业的学生包括研究生毕业后做底层开发的人才很少，绝大多数人是把国外公司开发出来的编程语言拿过来直接使用，编程时直接调用软件包中的函数，至于这些函数是如何实现的并没有几个人认真思考。久而久之，学生（包括一些教师与软件开发人员）也很少思考或研究这一问题，突然遇到这样的问题就会束手无策、无从下手。所谓万丈高楼平地起，没有基本的思维训练很难做到基础性创新思维的能力培养。中兴事件给我们国家的原始创新问题敲响了警钟，有人在网上提出“假如微软、谷歌不让我们使用其操作系统怎么办”的问题，说明应用与创新缺一不可，只有应用的火热而没有创新就会受制于人。计算理论课程是从本质上介绍计算机科学的课程，是计算机学科发展的基石。为了计算机学科更好地发展，将计算理论作为一门必修课，作为培养高年级本科生或研究生计算思维和创新思维的重要一环是非常必要的，这是开设此门课程的现实选择，也是必然选择。

1 计算理论在研究生教学中的重要性

“计算机科学技术日新月异，新东西层出不穷，旧的东西迅速被淘汰，但是作为一门科学，它有其自身的理论基础，这些思想精华长久地、甚至永恒地放射光芒，这些理论在应用开发中好像是‘无用的’，但实际上，对于每一位从事计算机科学与技术的研究与开发的人来说，它们都是不可缺少的，就像能量守恒之类的物理定律对于每一位自然科学工作者和工程技术人员那样”[1]。“通过这些要点，我们对计算机科学的重要基石有了一些新的认知，有些之前我们认为可能比较新颖的东西（比如层次化存储），实际上在计算机诞生初期就被提出甚至进行了量化分析，每年顶级会议上出现的一些新成果都是这些思想的实现；有些之前我们认为可能比较陈旧的东西（比如虚拟化），实际上换一个角度可能是一种新的研究思路。真正具有本质的重要性的东西，无所谓“新”与“旧”，应该在历史发展中传承和保持下来”[2]。上述两段话充分说明计算理论在现代计算机科学与技术研究生教学中的核心意义。从科学基础理论角度来讲，可计算性理论是计算机科学最核心的基础理论，如果没有可计算性理论，计算机将难以称为计算机科学，这是学科发展需要，也是开设这门课程的根本原因。

图1所示为创新能力的培养与思维训练过程，这一系列过程从低到高不断升华，可逐步培养学生的计算思维与创新能力。在本科教学中，学生养成了“老师教什么，学生就记忆复述什么”的学习习惯，一般很少对教师讲授的内容提出异议和新的见解。只是在离散的抽象代数部分才开始涉及基本的运算系统，但由于过于抽象，一般学生也是一知半解。在研究生教学中，教师教什么、学生就记忆复述什么的学习习惯一定要打破，学生要养成“老师讲授的不一定是唯一的、最好的解决问题方法”的思想意识，教师要以“没有最好，只有更好，优化优化再优化”为教学理念。学生要勇于向老师提出问题，敢于向课本内容提出挑战，给出新的见解。研究生接受计算理论学位课程的学习已经不仅是为了掌握知识获得学分，还是对计算系统的了解逐步向更高级的计算系统（它的运算呈现出模型化的特征）过渡，并由此学会一种思维方式、一种创新能力，这种思维方式与创新能力对于从事任何工作都是受益终身的。作为一门研究生素养训练的学位课程，计算理论课程的教学改革必须跟上国家创新人才培养的时代步伐，精心设计、合理安排、科学谋划，这是计算机学科发展的需要，是国家积极推进培养创新人才赋予我们的使命与任务。

图1 计算思维与创新能力培养示意图

2 计算理论课程的教学内容

人工智能、大数据、云计算、边缘计算等领域正在蓬勃发展，越来越多的经验在实践中累积，但是理论基础都相对薄弱，需要构建各自领域中有较强针对性的基础理论[2]。面对新形势、新需求，计算理论要讲述的内容包括以下几方面。

1）以5条基本指令x=x+1、x=x-1、TO A IFx≠0、TO A和y=x为基础的元语言程序描述可计算函数。

使用5条基本指令的元语言程序教学过程，就是训练学生使用最基本的指令编程实现复杂的可计算函数的抽象思维能力过程。近年来出现的Python语言是一个比较流行的易学易用的编程语言，其创始人Guido也是从编写Python的编译器开始，将其逐步演化成今天的流行语言。程序员中流行的“人生苦短，我用python”也说明其受欢迎的程度，但火热程度的背后是Guido及团队成员不懈努力的结果，没有开发人员的默默付出，将从底层搭建出来的结果呈现给我们，就没有今天的Python。对热议的中兴事件引起的处理器芯片设计问题来说，将指令集和程序区分开，可以以不变的少量指令构成万变的应用程序。指令集（如x86、MIPS、RISC-V）中不同类型的指令都是有限的，但可以编写的不同程序的数量极其庞大，这样硬件上的固定性与软件上的任意性矛盾就得到解决[2]。

2）从初始函数S(x)=x+1、n(x)=0和出发，通过利用复合、递归算子得到的原始递归函数以及利用复合、递归与取极小算子得到的部分递归函数与递归函数描述可计算函数。

递归函数是计算理论的核心概念，因为图灵可计算函数类就是递归函数类，两者完全等价。递归函数是构造更为复杂函数的基础，现代以神经网络为代表的机器学习是一个黑箱算法，可解释性不足，需要一个可被证明的理论作为基础。从递归函数解读深度学习过程，即一层神经网络的输出是下一层神经网络的输入，通过不断地复合与递归层层深入最后得到深度学习训练的结果[3]，递归可以构造出更复杂的函数，从而解决更复杂的计算机科学与工程问题。

3）使用两符号与多符号的波斯特图灵机、四元组图灵机、五元组图灵机、通用图灵机描述可计算函数。

此处的两符号（0和1）波斯特图灵机接近于我们熟悉的汇编语言，而两符号与我们现在所使用的计算机底层操作的符号是对应的；多符号波斯特图灵机是两符号图灵机的一种推广。现代计算机可以处理的数字、图像、音频、视频等各种形式的数据，其实质也是0和1两符号推广到多符号的扩展形式，形式语言与自动机理论也产生于此。四元组和五元组图灵机是以元组形式描述的产生式规则，其中的状态相当于现代编程语言中的环境；每个产生式的前提（也称为前件）和效果（也称为后件），相当于在不同状态下采取不同的动作需要的前提和产生的效果。通用图灵机是进行各种计算的元语言程序，可以完成各种计算操作，但其存在局限性，如计算机病毒作为一种具有特定功能的算法，同样可以用图灵机或通用图灵机进行描述，通用图灵机模型只限于分析一种单一的算法或程序，如果要分析两个或更多的算法和程序之间的联系，这种模型显然不够。文献[4]从计算机的基础理论模型——图灵机模型出发，提出一种扩展的通用图灵机模型EUTM，极大地简化了计算机病毒传染机制的形式化描述，开辟了计算机病毒传染特性和可传播性形式化描述的新领域，有助于正确地理解计算机病毒。

4）使用元语言程序描述不可判定性问题。

图灵机根据机器的程序处理初始格局，有的初始格局可能导致停机，有的则导致无限的格局序列，引出停机问题。图灵机停机问题的实质：是否存在一个算法，对于任意给定的图灵机都能判定任意的初始格局是否会导致停机。图灵已经证明，这样的算法是不存在的，即停机问题是不可判定的。

停机问题是研究许多不可判定问题的基础，人们往往把一个问题的判定归结为停机问题：“如果问题X可判定，则停机问题可判定”，从而证明问题X的不可判定性。停机问题有多种不同的叙述方式和证明方法，分别适用于具有不同特征的问题，如对于目前人们使用的智能手机，经常会出现某APP运行了计算模型上没有进行定义的操作的现象，导致手机对用户的任何操作都无法作出反应，我们称为“死机”。对于这种“死机”行为，手机开发商设计一个检测软件进行监控处理就是一个停机问题的现实反映。显然，根据上述论述，这样的软件是设计不出来的。

5）以产生式规则为基础的图厄系统描述可计算函数。

这一部分主要讲述图厄系统识别符号串。在形式语义学中图厄系统实际上被称为文法，在计算机科学中，文法是编译原理的基础，是描述一门程序设计语言实现其编译方法的基础，同时也是形式语义学的基础。形式语义学在自然语言处理、程序语言设计、网络搜索引擎以及计算复杂性上都有重要的影响，如通过设计类似于产生式系统的图厄系统识别需要的符号串，可联想到在网络搜索引擎的文本检索中常常涉及的问题[5]：给定一个单词集合，查找包含一个（或全部）单词的所有文档。搜索引擎是这一过程的通俗示例，搜索引擎使用一种称为“倒排索引”的特殊技术，对网络上出现的每个单词（有1亿种不同的单词）所有出现之处的列表进行保存，有非常大的主存的机器保持这些列表的最常见部分随处可见，允许许多人在瞬间搜索到这些文档。此外，图厄系统还是计算机文法的基础，对于语言的语法分析等也起着重要的基础性作用。

6）以单带与多带图灵机描述可计算函数。

单带图灵机由3部分组成：一条带、一个读写头和一个控制器。图灵机的格局由当前状态、当前带内容、读写头的当前位置组成。图灵机开始运行后，根据转移函数所描述的规则进行计算，图灵机就从一个格局到另一个格局进行转换。图灵机本质上是一个程序或算法的高度抽象，当给定一个输入x以后，就可以计算出f(x)。除了前面描述的计算模型外，人们还研究了图灵机的各种变型，如非确定的图灵机、多道图灵机、多带图灵机、多维图灵机、多头图灵机、带外部信息源的图灵机等，这些图灵机变型对今天的计算机体系结构设计仍具有重要的指导作用。除极个别情形外，这些变型并未扩展图灵机的计算能力，它们计算的函数类与基本图灵机是相同的，但为研究不同类型的问题提供了方便的理论模型。上述图灵机的组合变型演化出当今的计算机硬盘存储表示形式（通过磁头、磁道、扇区等参数），而多带图灵机是研究计算复杂性理论的重要计算模型。人们还在图灵机的基础上提出不同程度的近似于现代计算机的抽象机器，如具有随机访问存储器的程序机器等。

3 计算理论启发式案例教学

计算理论课程讲述多种模型，一方面是为了让学生了解与掌握计算理论知识并证明它们的等价性，因而论证Church-Turing问题；另一方面也是为了训练学生创新思维，打破思维框架束缚，培养学生从不同角度解决问题的能力。各种模型具有不同的特点，针对不同的问题各有其价值。不同研究者在解决同一科学问题时，会给出不同的算法：这些算法或者演化于某些著名学者提出的基本方法，或者是自己提出的一个不同于常人的方法（这也相当于一个个小的具有针对性的计算模型）。之所以有脍炙人口的三国演义产生，就在于有陈寿的三国志，三国志相当于我们上述描述的某一“计算模型”，而三国演义就在此“计算模型”下加上民间传说在罗贯中的笔下演化而来的，妙笔生花（从计算机科学角度看就是组合新的理论与方法到原有模型中用于解决新的问题）更加接地气。以具体案例对启发式案例教学作进一步说明如下。

案例1：在递归函数的谓词递归性证明中，首先通过使用真值表分析法得到证明过程的特征函数，进一步引入广义德·摩根律，并通过启发使少部分学生给出不同于原有教案上的证明方法。

案例2：在讲授四元组、五元组图灵机过程中，引入三国演义中的刘备东吴招亲、诸葛亮授赵云3条锦囊妙计的故事展开图灵机的状态变化与操作过程，将深奥的教学内容与大家熟悉的故事巧妙结合，达到寓教于乐的目的。

计算理论的讲述一方面可以使学生了解这些计算模型的知识，看到它们的现代应用演化。在教学中，注重启发学生将这种“演化”方法融入自己的科学研究中，利用自己所研究领域先驱学者提出的原创方法加上其他方法及所解决问题的特性解决问题，把“共性”+“特性”解决问题的思想融进计算思维与创新能力的培养过程中。另一方面，在各章不同计算模型讲授过程中，以问题启发学生思考，问题可以是：这些计算模型有什么区别？共同点又是什么？在不同讲述内容中可计算是如何定义的？通过学生思考与教师释疑，学生可意识到同样的问题有不同的解决方法，学会从不同角度思考问题，勇于探索并打破思维框架的束缚，寻求问题新的解决方案，这是创新能力培养的必要过程；同时，学生可在这个过程中充分理解和掌握计算机科学先驱们对问题的定义、方法的描述、性质的验证或证明，这也是今后从事科学研究的研究生应该掌握的必要方法与思维方式。

4 结 语

吉林大学是一所综合性双一流国家重点建设大学，研究生的培养更加应该以思维方式与创新能力为主，计算机学院的研究生从20世纪80年代开始学习计算理论这门课程，一直持续至今。在教学实践中，我们发现很多学生学习以后并不了解这门课程的真正内涵，创新思维的训练更是无从谈起。计算机学科研究生从基础知识掌握与编程能力培养到计算思维与创新能力的养成，是对高校计算机学科研究生理论教学的一个挑战。计算思维与创新是运用计算机科学的基本知识进行分析问题、发现问题与解决问题所涉及的计算机科学各个方面的一系列思维活动与创新设计过程，其中计算思维着眼于求解问题思维模式的养成与训练，而创新着眼于突破原有思维定式与框架，敢于打破常规的思维能力培养。

计算理论课程的教学内容和教学方法，是训练学生计算思维和创新思维的有效手段。前者从不同计算模型的角度研究相同问题的可计算性，后者以对比分析的形式完美地呈现计算模型的表示方法、计算过程、计算能力，二者异曲同工，紧紧围绕训练计算思维、培养创新能力的目的展开。我们从计算理论课程的意义、研究生培养中的作用、课程讲述内容与演化、启发式教学几方面进行描述，力图探索计算机科学与技术学科研究生计算思维与创新能力培养的新模式，希望为高水平创新型人才培养提供可供借鉴的教学模式与方法。