APP下载

“数据结构”课程强化算法应用的教学实践

2021-09-13王景珊

无线互联科技 2021年12期
关键词:数据结构协同育人

王景珊

摘 要:“数据结构”是计算机类专业的核心课程,学习内容抽象难理解,理论教学与实际应用容易脱节,教学中应将抽象的数据类型与现实建立对应,加强学生对理论知识的感性认识。文章以Dijkstra算法和Floyd算法为例,分析强化算法应用的教学实践,同时挖掘算法内涵开展协同育人教学。

关键词:算法应用;Dijkstra算法;Floyd算法;协同育人

0 引言

数据结构是20世纪60年代提出并研究,20世纪70年代科学家Niklaus Wirth的著作《Algorithm+Data Structures=Programs》使得数据结构研究不断深入,20世纪80年代研究日臻成熟,成为一门完整的学科。它是一门介于数学、计算机软件、计算机硬件之间的综合学科,是程序设计的基础。

在知识飞速更新的时代,提高学生获得知识的能力,真正做到“授人以鱼不如授人以渔”,是教师应尽的责任。作为一门理论和实践并重的课程,理论教学讲授算法思想,实践教学实现由抽象到具体的过渡,将不同的数据结构及算法,应用于不同的场景,并优化算法,对提高学生的能力非常重要[1]。

1 分层教学的实施

教学中因材施教,合理进行分层次的教学是有必要的,可使不同层次的同学都能够有所收获,充分调动每个学生的积极性,提高程序设计能力和算法实现的能力,体验成功的快乐。具体开展以下分层次教学。(1)教学内容分层。根据教材内容,总体分为两个部分:一是基础部分,算法相对简单的内容;二是提高部分,相对比较抽象,算法复杂。前一部分内容所有同学都必须掌握,后一部分对学习能力强的同学有很大帮助。(2)课后作业分层。同样分为基础部分和提高部分,把需要完成的作业设置不同的难度系数,学生根据自己的实际能力完成不同难度系统的作业,这样,在他们的能力范围内都有所提高,可增强学生的自信心。当然,不同的难度系数进行考核时其分值是不一样的。(3)实践项目分层。在项目实踐环节,依然是遵循力所能及的原则,而不是强求功能全、难度大的项目,只要同学们用心了,努力了就好[2]。

2 实践教学环节的设计

“互联网+”时代,积极探索改革教学模式,O2O混合式教学模式在本课程的实施中得以充分实现。无论线上线下,实践教学都是由浅入深、由易到难,具体的过程由3步完成:(1)验证性基础实验。教材中已给出的基本算法,比如,线性表的增、删、改、查,二叉树的生成、遍历等,通过上机实践,验证其算法的结果,难度小,提高学生的学习兴趣。(2)综合性实验。完成验证性基础实验之后,掌握了一些基本的算法,为进一步提高学生的分析和应用的能力,要求学生完成一些综合性的实验,比如串的模式匹配算法,教材中一般是精确匹配,我们要求学生使用通配符模糊匹配。         (3)项目设计实验。难度加大,完成一个相对完整的项目设计,提高综合运用能力,培养学生的创新能力。选题的原则是实用,包含较多的知识点,学生可以根据自己的生活学习环境确定,比如,“学生成绩管理软件”不仅包含基本的增、删、改、查,还要求有学生的成绩统计与分析,基本满足教务系统对学生成绩的管理要求;“线下实体书店自助导购软件”通过对图书的管理,让读者能够在一个大型实体书店迅速找到所需要的书籍[3]。

3 强化算法应用的教学案例

数据结构是计算机科学的支柱,程序设计的基础。教学中教师不能只停留在抽象的理论教学层面,一定要强化算法应用才是有效的。本文以最短路径的Dijkstra算法和Floyd算法为例,分析强化算法应用的教学实践。

3.1 将抽象的数据类型与现实建立对应

最短路径是图的最常见的应用之一,图是一种典型的复杂多对多的非线性数据结构。在讲解这部分内容之前,课前布置了预习任务,同学们通过各种线上线下资源,查阅资料,了解图的应用,引导学生的学习兴趣。通过查阅相关资料,就会发现图的应用已经渗入语言学、逻辑学、物理、化学、电信工程及计算机科学与数学学科的其他分支,当今最前沿的科技图神经网络机器学习,都源于图的应用。同学们感叹,学好算法真的是大有用武之地。Dijkstra算法和Floyd算法就从大家生活中非常熟悉的导航系统导入。

3.2 最短路径的概念

日常出行,选择的是路程最短(通常路程与时间成正比)。如果路程较短的道路比较拥堵,需要花费较长时间,我们会选择实际时间短的线路,有的可能考虑的是交通费用最少。交通的便利给人们带来了更多的选择。所以,首先明确最短路径问题,不能狭义认为只是距离最短,可以是距离,可以是时间,也可以是其他,是解决关于有向带权图的问题。最短路径问题有两大类:第一,从某个源点到其余各顶点的最短路径,用一维数组表示源点到其余各顶点的最短距离;第二,任意两个顶点之间的最短距离,用二维数组表示任意两个顶点之间的最短距离。

3.3  Dijkstra算法思想

Dijkstra是单源最短路径算法,用于计算一个顶点(称源点)到其他所有顶点的最短路径。对于给定的有向网,把所有顶点分成两组,第一组是已求出最短路径的顶点集合S,其初值为源点(顶点v);第二组是尚未确定最短路径的顶点集合T(即V-S),T的初值包含除源点之外的所有顶点。具体步骤:① 假设用带权的邻接矩阵来表示有n个顶点的带权有向图。arcs[i][j]表示弧上的权值,若不存在,则为∞(表示时用INF),最短路径长度(用dist[]表示)初值为dist[i]=arcs[v][i]。②从T集合中选择w,使得dist[w]=MIN{dist[i]|Vi∈V-S},就是当前求得的一条从v出发最短路径的终点。从T集合中删除w,并入S集合,令S=S∪{w}。③修改从v出发到T集合中各顶点的最短路径长度。如果dist[w]+arcs[w][i]

3.4  Floyd算法思想

Floyd是求任意顶点对之间的最短路径算法。在给定的有向网中,依然假定用带权的邻接矩阵来表示有n个顶点的带权有向图。初始状态是,若存在,则存在一条长度为arcs[i][j]的路径{vi,vj},若不存在,则为∞(表示时用INF),最短路径长度(用dist[]表示)初值为dist[i][j]=arcs[i][j]。因为该路径不一定是最短路径,然后进行n次试探,具体步骤如下。①首先试探从vi到vj是否有以顶点v1为中间点的路径,若存在,则有路径{vi,v1,vj},距离为长度之和,与最初的最短距离比较,取较短者为当前最短路径。②再添加顶点2为中间点,添加顶点3为中间点,……,依次类推,添加顶点n为中间点,每次添加后总是取路径较短者为当前最短路径,即在n次的试探过程中,如果存在一个k,使得dist[i][k]+dist[k][j]

在最短路径的理论教学过程中,重点分析讲解Dijkstra算法和Floyd算法的思想,再引导同学写出相应的算法代码,最后在实践教学过程中完成一个功能较为完善的交通咨询系统,交通网络区域可以大,也可以小,但一定要使用实际数据,这样才能把算法应用落实到实处。

3.5  算法思想的协同育人教学

“数据结构”课程蕴含着丰富的育人资源,正确引导学生,把树立“中国梦”的理想与“专业梦”的规划有效结合起来,挖掘算法的思想内涵,开展协同育人教学。

学习了最短路径的Dijkstra算法和Floyd算法之后,激发学生“时不我待、舍我其谁”的爱国热情。图神经网络是近年来倍受大家关注的前沿科技,AI是未来重要的发展方向,引导学生发现其中蕴含的机遇与挑战,从而教育学生一定要有认真、仔细、严谨、求真、求实的学习态度,担当起科技强国的使命和责任。

迪杰斯特拉(Dijkastra)算法,源点到其余各点最短距离路径长度是按递增顺序一个一个求出,就像我们在人生路上必须求真务实,一步一步踏踏实实往前走,才能到达理想的彼岸,寻找属于自己的最优路径。

4 结语

“数据结构”课程的理论知识看似抽象枯燥,但其应用无处不在,加强算法应用的教学十分重要。新时代的教师要成为学生学习的引导者,不断进行教学理论的研究,设计好每一个教学过程,体现以“教师为主导,学生为主体”的教学理念,同时牢记教书育人的职责,实现知识教育与价值教育的内在契合,开展协同育人教学。

[参考文献]

[1]霍清华.应用型人才培养下的数据结构与算法课程改革[J].电脑知识与技术,2018(14):209-210.

[2]严蔚敏.数据结构(C语言版)[M].北京:清华大学出版社,2018.

[3]周蓓.数據结构与算法(C语言版)[M].北京:清华大学出版社,2019.

(编辑 王雪芬)

猜你喜欢

数据结构协同育人
数据结构课程教学网站的设计与实现
校企合作协同育人在大学生就业工作中的作用研究
专业教师与思想政治教师协同育人机制研究
协同育人视角下高校创新应用型人才培养研究
由“依附”走向“联动”:学校与政府协同育人策略研究
“翻转课堂”教学模式的探讨——以《数据结构》课程教学为例
现代建筑技术协同育人基地的构建研究
TRIZ理论在“数据结构”多媒体教学中的应用
《数据结构》教学方法创新探讨