变化无处不在，但历史上从来没有一个时代的技术与社会变化像现在这样迅速，特别是技术的变化令人眼花缭乱。处于最前沿的计算机教育者不得不面对一个疑问：我们根深蒂固的基于“知识点和知识体系”构建的教学到底应该怎样适应变化。
人类智慧的核心就是在变化中寻找稳定点（不变），而在稳定中寻找创新点（变化）。我们如何将这样的思想传递给学生，使学生获得解决不断变化的问题的“内生”动力？这是课堂改革的基本方向。
1 从变到不变：如何解决问题？
在纷繁的变化场景中，一定会有一些不变的东西，否则科学就会落入“否定一切”的虚无状态。著名计算机科学家David Harel在《算法学：计算精髓》中说：“尽管技术进步的速度令人炫目，一些‘技术创新’很快又会被更新的技术取代，但‘计算科学’中最基本的内涵变化就算发生，也比较缓慢”[1]。图灵奖获得者John Hopcroft在2020年出版的《数据科学导论》的前言中说：“基于计算科学的重点向充分利用积累的大数据方面变化，期望这本书的内容能够涵盖未来40年仍然有用的理论”[2]。正如近40年前他出版的《自动机理论、语言和计算导论》一书，里面的内容几十年来一直在计算机科学中发挥着基础作用。
那么在问题求解过程中有哪些“思维方式”能够保持不变呢？我们从一个非常简单的问题谈起，如下图所示，有7个完全一样（包括面上的字母）的立方体被放置在桌上，问题是7个朝下的面上的字母构成一个什么单词？
立方体可以自由旋转，因此面对我们的“正面”是可以变化的，而正面的4个“邻面”虽然作为集合不会变化，但是可见的两个邻面可以变化。人们经常说“这个问题有点绕人”，其实就是看到变化因素比较多，而求解往往从“不变”因素入手。那么这里什么因素不变呢？
稍有一点几何知识就知道“哪两个面相对”是不变的，这个问题非常简单。从显示的画面很容易看出每个立方体的6个面没有相同字母（因为图中出现了6个不同的字母），相邻的就不可能相对，由此立即可以判定，3组相对面是C—U，E—O，N—S，因此答案是SUCCESS。
如果觉得这个问题太简单，寻找“不变”因素的意义不够明显，那么再考虑一个“难”一点的问题。假如我们面前有11个大号的空纸箱，选中其中的若干纸箱，里面放进8个中号的空纸箱；再选中若干个中号空纸箱，各自放入8个小号的空纸箱。结果数数有102个空纸箱，问题是总共有多少纸箱，包括空的和不空的？
如果基于“刷题”的惯性思维，可能有人会想题目中的“若干”是未知数，于是假设选中的大纸箱和中纸箱数分别为x和y，但当真需要知道这两个值吗？题目的核心逻辑是能否根据空纸箱数确定纸箱总数。显然，如果在题目描述的过程中，这两个值的关系“始终不变”，那结果应该很容易求出。
于是问题归结为是否能找到这两者之间的“不变”关系（当然刚开始还不知道是否存在这样的不变关系，这就是“探索性学习”）。对于学过一点编程的人，这个问题比较容易考虑，不妨将题目描述的装箱过程想成一个由若干次操作构成的循环，每次操作就是选定一个空箱子，往里面装8个小一号的纸箱。
初始状态纸箱总数和空纸箱数均为11，每执行一次“操作”，箱子总数会增加8个，但原来的空箱子会少一个，于是空箱子数增加7个。换句话说，每循环一次，空箱子数与纸箱总数之间的差增加1。这当然也可以看作两者之间的“不变”关系，可是其中涉及一个未知数，即循环次数。题目并没有提供做多少次装箱操作的信息，但其实只要一点代数处理，就可以将这个未知数消去，得到的不变关系是空箱数×8 =装箱总数×7 + 11，因此问题的结果是115。
学计算机的同学都应该知道，“逻辑不变量”是计算思维中的一个重要概念，因为基于循环的算法正确性证明的基本方法就是利用这个概念。
大家都非常熟悉解决没有负权值的带权图中最短通路问题的Dijstra算法。这个算法的基本框架是循环，基本方法是建立一个集合S，开始时只包括起始结点，标号置为0，其他结点初始标号均为无穷大。每次循环会修改部分结点标号为有限值，并选择其中一个加入S。正确性证明就基于下面的“逻辑不变量”：S中任一结点的标号值即为起始结点到该结点的最短通路长度值。具体细节可以查阅任一流行的算法教科书。
有意思的一点在于，学计算机的学生在上算法课时是否意识到“不变”这个概念除了证明算法正确，还可普遍用于一般问题求解。
2 从不变到变：拓展与创新
有些学生觉得算法课“没意思”，课上讲到的多数算法都是“经典”算法，甚至都有现成的软件包可用，如上面提到的Dijstra算法，从模型建立到算法步骤再到分析都似乎已经成为“不变”的知识点，我们花工夫学还有意义吗？如果我们学到的只是不变的知识点，真的没有多大意义；如果能从变化的因素中找出不变的因素，理解知识点的来龙去脉，意义会大一点，能拓展到解许多其他问题。即便这样，也还只是“举一反三”，停留在知识层面的运用。我们要说的是，能否通过在不变中挖掘“变”来拓展新知识呢？
Dijstra算法称为解决“单源最短路问题”的算法，就是计算出从一个指定的起点到所有其他结点的最短路。同学们都能记住这个算法属于平方复杂度的算法（尽管并非所有学计算机的学生理解这个描述究竟是什么意思），还算是“不错”吧。这里是否有个问题：我只需要知道某个点到某个特定点的最短路，这算法要算就算出到所有点的最短路，是否没必要？如果问老师，老师可能会告诉你，反正算一个和算多个“最坏情况复杂度”是一样的。这是不是很不合乎常理！做一件事和做一百件事代价一样，你不觉得奇怪吗？
可以这样解释：尽管我们有“最优化原则”，即如果有条路从A经过B到C，假如这条路是从A到C的最短路，那么其中那一段从A到B的路也一定是从A到B的最短路；但反之不成立，即使确定从A到B是最短路，也不能说将其延伸到C就会是从A到C的最短路。换句话说，从A到C的最短路究竟会经过其他哪些中间点，我们没有更好的办法判定，于是只好同时求出从起点到所有其他结点的最短路，并且能证明最坏情况下二者代价是一样的，但这并不能消除我们对这个不变的算法的疑问。前面说到“平方复杂度算法”还“不错”是基于什么呢？在图算法中，一般将结点个数作为“渐进复杂度函数”的自变量，即问题规模。设想一下，如果以道路交叉口为图的结点，北京道路图该有多少结点？利用GPS导航，从S到T的通路可能经过的结点数与整个道路图的结点数有几个数量级的差别，这时还能说是“平方复杂度”算法吗？
到这里其实已经引出了原问题的“变化”，原来的算法已经不能很好地解决我们对问题的新认识，于是就有了“创新”的可能性。关于这个问题，有关技术性的内容已经超出了本文的范围，感兴趣的读者可以参考文献[3]。
面对智能化的新时代，引导学生学习，在变化中寻找不变，以解决以前没有见过的新问题；而学习过程中，在表面“静态”的知识点中发现可能变化的新问题，努力拓展创新。这样的局面应该成为教学的常态。
荀子《劝学篇》说“不积跬步无以至千里”。创新总是在相对不变与变化之间发生。我们绝不应该有意无意地让学生以为科技创新可以靠“突发奇想，一夜爆发”（个例可能会有，但不是教育的产出）。
参考文献：
[1] Harel D. Algorithmics: The spirit of computing[M]. 3rd ed. Boston: Addison-Wesley, 2004.
[2] Blum A, Hopcroft J, Kannan R. Foundations of data science[M]. Cambridge: Cambridge Univ. Press, 2020.
[3] Dametcrescu C. The quest for the shortest route, in the power of algorithms: Inspiration and examples in everyday life[M]. Berlin: Springer, 2013.
作者简介
陈道蓄，南京大学教授、博士生导师；近 10 年来，致力于计算机专业核心基础课程的教学改革，创建 了内容涵盖计算导论、离散数学、程序设计、数据结构以及计算机算法的全新课程“计算机问题求解”；同时积极 参与了中国工程教育专业认证体系的建立，该课程的建设思想充分考虑了对专业认证所要求的学习产出的支撑。
转自：“计算机教育”微信公众号
如有侵权，请联系本站删除！
