数据结构课程中理论证明的不足及加强策略

数据结构课程中理论证明的不足及加强策略一文创作于：2023-08-16 04:19:17，全文字数：13192。

数据结构课程中理论证明的不足及加强策略

��生，空出教学时间。作为专业核心基础课，学生学习数据结构课程的热情本身很高，授课教师不需要大量重复演算一些案例。如果每个案例从第一个步骤重复操作到最后一个步骤，会占据课堂大量时间，要相信学生有举一反三的能力，可以通过习题和复习掌握好要求的概念和操作方法。在总学时有限的情况下，只有优化好教学时间，才能更好地引导学生思考诸如理论正确这样的深入内容。

（2）启发和尊重学生的求知欲。让学生认为自己不是“工具人”，不只会按规定动作操作数据，编写代码。教师可以通过收集一定的案例，让学生知道：一个算法碰巧能对，是很不严谨的一件事，甚至教科书直接讲授而未证明的算法，都是可以质疑的。而质疑的最好武器，就是掌握证明技术。

（3）在考核环节加入正确性考察。对于数据结构课程而言，选择题、填空题可以出现考察算法和数据结构的性质，比如某种排序的稳定性、某个算法最坏情况下的运算次数，自然也可以考察某个算法是否一定会得到正确结果。至于简答题，直接可以加入证明题，给出某个经典的数据结构算法，或者类似的算法，让学生证明或者证伪。

4 启发式证明及证伪的教学方法

如同数据结构和算法有设计思路，证明也是有思路的。证明方法是如何想到的，往往比证明文本更重要。除使用的针对特定语言操作数据结构［8］的形式化证明，本文提出一些更适用于教学的证明方式，并在实际教学中进行了实践。

4.1 划分错误类型，逐一排除

第一种教学方法是划分错误类型，受PBL教学模式［9］启发，以KMP为例，首先抛出疑问：“KMP算法比每次失配都重新对比的蛮力匹配算法高效，那如何证明其正确性？”，该问题很笼统，只能将学生注意力吸引过来。接着启发：“换一种提法，如果一个字符串匹配算法运行结果不正确，可以分为哪些类型的错误？”多数学生仍然可能无法对答。教师再进行启发：“一种情况是该匹配的没匹配上，另外一种情况是？”学生必然能够回答“不该匹配的给匹配上了”。教师约定第一种情况叫漏配，然后又与学生讨论漏配是不是只发生在滑动过快了？KMP在滑动时，有没有可能漏配？最后形成一个比较严密的证明。

4.2 划分数据类型，逐一求证

一个算法面对各种输入的组合，如何证明其都能够正确处理？同样需要抽象和归类的方法。其中，数学归纳法能够将规模不同的数据，归为一类情况统一证明，包括各种排序、最小生成树、最短路径、Huffman树等贪心选择算法，均可以采用此技术。

4.3 反例构造技术

证伪一个算法，难在构造一个实例。如何攻击一个算法的软肋？首先需要暴露这个软肋。本文方法有如下3种：①反例的实例规模不必大；②识别哪些数据无关紧要，尽量取一些较小的值即可；③从错误结果逆操作，可以帮助构造导致算法错误的合理输入。该思想与对抗神经网络训练攻击样本［10］一致。

以证明希尔排序不是稳定的为例，只考虑2趟，结果为有序的4个数（1b，1a，2，3），其中1a和1b均为1的两个实例，1b在输入序列中处于1a之后，被希尔排序交换到1a前面，由此取增量序列为｛3，1｝，输入序列为（3，1a，2，1b），就能证明希尔排序不稳定。

这种反例的构造，在不同案例中反复使用，同样通过启发的方法，让学生先于教师构造出来，学生自然就容易掌握其中的规律。

在实际教学实践中，本文对贵州大学计算机科学与技术学院2019级计科专业3个班的学生讲授KMP、最短路径两个算法后进行了对比。实验班级采用了质疑+启发教学方法，对比班级为传统的算法步骤，演示操作数据的方法。在实验班级讲解了构造反证的思路后，给足10min的理解思考时间，要求对扩展问题自行思考构造反例，实验班级成功了81%，对比班级仅成功了38%，并且实验班级构造的用例明显简洁。

5 结语

数据结构课程是计算机专业的一门重要核心课程，现有的教材、授课及考核中，几乎不涉及各种经典案例的理论证明。本文从不重视算法正确性证明的原因、相应危害性、改进策略等方面进行了阐述。总而言之，教师应对所授课程不断进行研究，立足理论，深入实践，探索教学改革新思路，引导学生更进一步提高自己的基础理论能力和持续创新能力。

《数据结构课程中理论证明的不足及加强策略》在线阅读地址：数据结构课程中理论证明的不足及加强策略