下书网

故事栏目

外国小说文学理论侦探推理惊悚悬疑传记回忆杂文随笔诗歌戏曲小故事
下书网 > 小故事

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

时间:2023-08-16 04:19:17

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

程欣宇,张 丽,汪 健,叶 晨

(贵州大学 计算机科学与技术学院,贵州 贵阳 550025)

0 引言

数据结构课作为计算机专业的核心课程,既有理论分析数据之间的逻辑关系、存储效率和算法执行效率,又有解决实际问题的案例。但目前的教材、教学案例、考核中,几乎没有各种经典案例的理论证明[1-2]。例如:为什么最小生成树的Kruskal算法每次选择两个联通代价最小的连通分量进行连通?Dijkstra算法为什么选择离源顶点直接路径最短的顶点?Huffman树为什么选择权值和最小的两个根结点合并?匹配字符串的KMP、BM算法效率高,但会漏配错配吗?通过教学,学生学会了这些算法的操作步骤,能通过画图、填表和分析复杂度,完成相应的作业和考试,也能编写程序对输入的问题实例进行求解。但是,学生大概率并不知道,也未曾思考过:这些数据结构的操作算法在任何情况下都能保证正确性吗?如何证明这些算法的正确性?更进一步地,这些算法是如何被前人设计出来的?有没有更统一的规律存在,以指导人们获得更广泛的问题求解能力?“道技关系”是教书育人者应该思考的[3]。若不引导学生思考这些问题,当出现的实际问题需要学生设计数据结构和算法时,学生即便能够设计出高性能的数据结构和算法,也很难去证明或者证伪一个算法的正确性。本文重点讨论形成这种现象的原因、可能产生的危害以及相应的改进对策。

1 数据结构课程不重视算法理论证明的原因

数据结构算法的理论证明包括性能、性质和正确性的证明。定量分析在教学中有大量讨论,如二叉树的度为2的结点数量是多少?合并排序最坏情况的比较次数是多少?但是,性质和正确性的证明鲜有讨论,如搜索匹配的错配漏配问题、最优化目标是否能够保证的问题,本文归纳原因如下:

1.1 课程侧重点

数据结构课程信息量大,各种逻辑结构、物理结构的组合繁多,对应可以解决的问题案例也非常多。需要讲授大量概念、方法和案例分析,又要强调掌握计算步骤,要能够上机实践,还要做性能分析,再加上学时数有限,导致教学中很容易放弃对理论证明的要求。虽然实验验证仅仅是证明了相关算法在少量的典型数据上有效,但其并不能像理论证明一样,能够更全面地证明算法的正确性,后者仍然被挤占掉。

1.2 学科侧重点

计算机科学与技术作为最热门的学科,新理论新技术层出不穷,新应用遍地开花。编程动手能力成为评价学生的一大指标,编程本身就容易出现各种问题导致学生放弃,因此但凡学生能够熟练编程,甚至做出一些直观演示效果好的程序或应用,教师就会给予很大鼓励,很容易放松对理论严谨性的要求。

计算机科学与技术作为可以授予理科或者工科的一级学科,一流学科建设中的大多数学校选择了授予工科学位,也导致了对理论深度要求的欠缺。

1.3 教学与考核难点

教学和考核数据结构的基本概念、基本性质、基本运算方法,如记住什么叫稳定的排序、学会将插入结点后的AVL树调整平衡、分析一个数据操作最坏情况下的复杂度相对容易。但是理论证明或者证伪一个算法,就如同考核一个现实问题的算法设计到程序设计一样难。由于涉及到不同的算法规模、底层逻辑,因此解题思路灵活,非常难以判卷给分,出题难度和灵活性也不好控制,一不小心就难住大部分学生。

本文举一个真实的教学案例,用以反映OJ测试可能存在的不严谨性。在某大学的OJ系统中,为了考察学生对字符串快速匹配算法的掌握情况,有这么一道题:输入为两个字符串A和B,要求设计程序判断A是否为B循环左移的结果。命题者希望学生能够将A复制拼接成AA后,判断B是否在AA中出现。但在给测试用例时,没有考虑到:如果A和B满足循环左移后的相等关系,A、B循环相邻字符的共生矩阵也必然相等,而计算共生矩阵只需要线性时间[4]。因此,用很短的代码,只检查了必要性,未真正用高性能字符串匹配算法检查充分性,也能欺骗过OJ,拿到此题的满分,运行耗时还比严谨正确的算法快不少。

2 数据结构课程中理论性证明不足的危害性

从本科生到工程师或者研究生,总会面临一些数据结构和算法设计,如果对正确性证明认知不足[5],迟早会暴露以下问题:

2.1 理论支撑欠缺,学生理论水平难获提升

即便所设计的算法高效可靠,但是因为缺乏理论证明方法,哪怕通过大量测试,也无法在根本上保证算法程序的正确性[6],客户和团队也担心关键时刻失效。面对重大项目就不敢上马,不能承担重任,难以获得技术创新的红利。这在教学时不能立即感受到,需要持续和重点关注一定量的学生工作后的长期发展,具有丰富项目经验的教师越能体会到这点。如一个动手能力较强的学生,参与了实战型的毕业设计,他采用邻接矩阵存储3 000个道路卡口的连接情况。答辩时提问:“你用邻接矩阵存储,难道不考虑存储的代价是n?0?5吗?”,学生回答是:“我用了json存储,比较紧凑。”其实,不管是json还是yml、bson,都是一种紧凑的数据交换格式,仅仅能够将系数的存储空间优化,并不能解决稀疏矩阵的存储和高效检索。这个案例很典型,反映了不少学生和教师,一旦重视动手能力培养,就容易放松理论水平的修炼。

2.2 严谨性不足,算法“失效”情况难以预料

与上述难以证明导致无法上马的情况不同,市场讲究竞争、业绩和“快鱼吃慢鱼”,更多算法的理论正确性证明会以各种测试进行代替,继而上线。如上文所举例子,测试用例本身是难以全面覆盖的,稍有疏忽,系统就会出现漏洞,继而导致数据完整性、一致性和计算结果可靠性降低。

再以数据结构循环队列的一个应用教学案例为例。循环队列的应用很多,一个抽象但能够映射很多现实问题的案例[7]是这样的:已知一个集合A中有n个元素及其冲突关系矩阵R,希望将A划分为若干个子集,使得相同子集中的元素不冲突。此案例充分利用了循环队列:将A中元素所有入队,循环从A中取出队首元素,若该元素与当前子集中的元素不冲突,就放入当前子集,否则就放回队尾。队列中的元素出队一遍前,创建一个当前子集,直到队列空。案例中9个元素的冲突关系为:R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)}。按方法操作下来划分的子集为:{1,3,4,8}、{2,7}、{5}、{6,9}。但更好的划分方案为:{1,3,5,8}、{2,4,7}、{6,9}。如果不讲清楚这个算法的不足,学生会默认这是一个高效且完全正确的算法。数据结构课程中理论证明的不足及加强策略

3 改进对策

针对数据结构课程中理论性证明不足的原因及危害,提出以下改进对策:

3.1 指导思想上,“术”“道”兼备

在学科指定培养方案时,要有理工兼备的指导思想,既传授“术”,也探讨“道”。具体到数据结构课程中,除强调数据的逻辑关系、存储结构、访问效率,也应当注重数据访问算法的正确性。

3.2 教学实操上,以学生为中心,注重正确性考察

(1)充分相信

提醒您:因为《数据结构课程中理论证明的不足及加强策略》一文较长还有下一页,点击下面数字可以进行阅读!

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

12

热门书籍

热门书评

推荐小故事