计算机专业图论课程教学改革探索

王桂平 冯 睿

摘要:本文分析了图论教学的重要性及图论课程教学现状,针对应用型人才培养目标和计算机专业的特点,对图论课程教学提出了一些改革思路,主要思想是通过程序设计竞赛激发学生的学习兴趣和积极性,并通过在线程序实践理解和实现图论算法,让学生掌握图论算法及其应用。最后总结了一些有效的课堂教学和实践教学方法。

关键词:图论;计算机专业;程序设计竞赛;在线实践

中图分类号:G642 文献标识码:B

1图论及图论教学

图论(Graph Theory)是数学的一个重要分支,以“图”为研究对象。图论中的图是由若干个给定的顶点及若干条连接两个顶点的边所构成的图形。这种图形通常用来描述某些事物之间的某种特定关系:用顶点代表事物,用连接两个顶点的边表示相应两个事物间具有这种关系。这种图提供了一个很自然的数据结构,可以对自然科学和社会科学中许多领域的问题进行恰当的描述或建模,因此图论研究越来越得到这些领域的专家和学者的重视。

基于图论的重要性,目前很多高校课程都涉及到图论知识,如离散数学、数据结构、算法分析与设计、运筹学、组合数学、拓扑学、网络优化等。越来越多的大学将图论单独作为一门课程来开设,作为数学、计算机科学与技术、电子科学与技术、管理学等专业本科生和研究生的必修课或选修课。

图论的教学具有如下特点:

(1) 概念、定理特别多,定理的证明通常都很难,在一定程度上造成教学比较难而且枯燥。

(2) 图论里很多问题都有具体的应用背景,但通常难以转换成图论中的模型,从而求解比较难,所以学生对图论课程有一定的兴趣,但往往会望而却步。

(3) 图论中的算法丰富,几乎每个应用问题都有不同复杂度的算法。例如,最短路径问题常用的算法有Dijkstra算法、Bellman-Ford算法、SPFA算法、Floyd算法,如果要用程序实现这些算法并求解实际问题,对学生的程序设计和算法分析能力有比较高的要求。

(4) 图论课程对锻炼计算机科学与技术等专业学生的算法分析与设计能力有很好的作用。

作者调查发现,国内高校图论课程的教学或者是侧重于完整的图论知识体系介绍、复杂的图论定理证明,或者是侧重于从应用数学的角度介绍图论在各领域的应用。我们在教学中发现,许多学生(特别是计算机专业的学生)在学习图论时,都不满足于图论算法的手工和草稿纸演算,迫切地想知道如何用程序来实现图论中的算法,以及如何用这些算法思想求解实际问题,这就对计算机专业的图论教学提出了新的要求。

2教学改革背景

随着我国的高等教育进入大众化阶段,许多高校将人才培养目标定位成应用型人才的培养。这就要求高校培养的学生不仅具备扎实的专业知识,还要有过硬的应用性知识。

对计算机科学与技术专业来说,应用型人才的培养目标要求注重培养学生软硬件系统的研发能力,强调学生对非计算机学科(专业)知识的融会贯通,学生应具备扎实的计算机基础理论知识和较强的实践能力。

发展应用型教育,培养应用型人才,应该贯穿于整个教学活动中,包括专业设置、教学管理、课程设计、教学手段和方法以及教学制度建设等方面。

在这样的背景下,我们在图论教学中一直在思考以下几个问题:

(1)“图论算法实现及应用”在我校是作为一门选修课开设的,如何让学生在感受到图论知识魅力的同时提高学习兴趣,调动学生的学习积极性。

(2) 如何针对计算机专业学生设计合适的教学方法,以适应他们的专业特点和专业发展方向。

(3) 如何设计新颖的实践教学形式和内容,引导和加强实践教学,让学生真正理解图论算法思想并能编程实现,灵活运用图论算法求解各种应用问题,以适应应用型人才培养的要求。

3图论课程教学改革

3.1改革思路

针对图论课程的教学现状和应用型人才培养的要求,我们尝试按以下思路进行教学改革:以培养学习兴趣入手,引导学生进入丰富的图论知识领域;向学生阐述有具体应用背景的图论算法思想;侧重图论算法的复杂度分析和程序实现;通过在线实践引导学生运用图论算法求解问题。

为此,我们在充分调研和积极探索的基础上,提出以下教学改革措施:(1)以大学生程序设计竞赛这一学科竞赛为驱动,激发学生的学习热情和积极性。(2)以“在线实践”这种新颖的实践方式为导向,丰富课程的实践教学并提高学生的实践能力。(3)加强“程序与算法设计”课程群的建设,构建完整的、系统的知识体系。(4)做好教材建设,编写适合这种教学思路的图论讲义、教材和实验指导书。

3.2以程序设计竞赛激发学生的学习积极性

由美国计算机协会组织的ACM/ICPC国际大学生程序设计竞赛已经有30年的历史了,中国大陆的高校在上世纪90年代中期陆续参赛,很多高校在总决赛中取得了优异的成绩。ACM/ICPC竞赛在公平竞争的前提下,提供了一个让大学生充分展示用计算机分析问题、解决问题的能力与才华的平台。ACM/ICPC竞赛鼓励创造性和团队协作精神,鼓励在编写程序时的开拓与创新。

近十年来,很多高校开始举办全校性的程序设计竞赛,并逐渐发展成为全省(市)性质的比赛,这极大地推动了这项学科竞赛在中国大陆高校的开展。

图论是这项程序设计竞赛中重要的题目类型之一。图的遍历、活动网络、最小生成树、最短路径、图的行遍性问题、网络流问题、匹配问题、图的连通性、图的着色等都有大量经典的题目,几乎涵盖了图论完整的知识体系。

例如,我们在举办竞赛时曾经出了这样一道题:由M×N个方格组成的网格表示敌占区,通讯员要从初始方格S出发,送情报到达目标方格T,其他符号的含义如图1所示。初始时,通讯员具有一定的体力。通讯员从某个方格出发,到达上、右、下、左4个方向上的相邻方格需要花费的时间和消耗的体力如图1所示。另外,从目标方格的相邻方格到达目标方格,花费时间1,消耗体力1。本题要求解的是:通讯员能否到达目标方格?如果能到达,所需最少的时间是多少(只需要保证到达目标方格时,通讯员的体力>0即可)。本题的求解要用到广度优先搜索算法。图1中给出了一条花费时间最少为13的路线(初始体力为8),到达目标方格时剩余体力为1。

我们在教学中以这些题目为例阐述图论算法思想、分析算法的复杂度并用程序实现,让学生切实地理解算法思想、直观地体会到算法的具体应用,同时我们也布置相应的题目作为练习题。这些题目的趣味性和挑战性能吸引学生投入较多的时间和精力去完成,在丰富知识结构的同时提高学生的程序设计和算法分析实践能力。

3.3以在线实践提升学生的程序实践能力

随着ACM/ICPC程序设计竞赛的推广,各种在线程序评判(Online Judge,简写为OJ)网站也应运而生,这为程序设计爱好者提供了一种新的程序实践方法:在线程序实践。

在线程序实践是指由OJ网站提供题目,学生在线提交程序,OJ网站的在线评判系统实时评判并反馈评判结果。这些题目一般具有较强的趣味性和挑战性,评判过程和结果也公正及时,因此能引起学生的极大兴趣。

学生可以根据OJ系统反馈回来的评判结果反复修改程序,直到最终收获Accept(程序正确)。这不仅能培养学生独立分析问题、解决问题的能力,而且每成功解决一道题目都能给学生带来极大的成就感。

在教学中,我们以组织学生开发的OJ系统作为实践教学平台,该平台主要起到了以下作用:(1)作为教学演示平台。对课程中涉及到的算法都尽量用程序实现,并提交到OJ系统进行验证和演示。(2)作为算法分析平台。针对图论算法丰富的特点,我们在教学中对同一个应用问题采用不同算法实现,并提交到OJ系统,以测试程序的运行时间,让学生直观观察到算法的优劣。(3)作为实验教学的平台。在实验课上,学生可以用程序求解练习题并提交到OJ系统验证。(4)作为课程考核平台。对图论课程进行教学改革后,我们认为不适合采用笔试方式考核,因此采用在OJ系统上机考试的形式。这种考核方式过程更直观、结果更客观。

3.4以课程群建设推动知识体系的系统性构建

教学改革后,图论课程的教学目标定位为培养学生图论算法分析、设计和应用能力。这跟我们建设的“程序与算法设计”课程群的知识体系、知识目标、能力目标是吻合的,因此我们将图论课程纳入该课程群。

“程序与算法设计”课程群的知识体系设计为:程序设计思想和方法、数据结构设计与运用、算法分析与设计、面向对象的软件开发、图论算法分析与应用。为此,我们精选了6门课程组成该课程群,如图2所示。

课程群的知识目标为:通过课程群中各门课程的学习,掌握基本的程序设计思想和方法;理解面向对象程序设计的思想并能熟练运用;理解各种数据结构的原理和使用方法;熟练掌握常用算法分析和设计技巧,掌握常用算法的综合运用;掌握系统分析与设计的基本方法。

课程群的能力目标为:掌握基本的程序设计、测试、调试能力;能运用面向对象程序设计思想和方法开发较大规模的软件;能综合运用各种数据结构对软件功能进行描述和建模;具备基本的数据结构和算法分析和设计能力;能针对各种图论应用问题设计合理的算法并用程序实现;在软件开发中运用系统观点,对应用问题进行初步的分析和设计;在实践活动中锻炼毅力,树立克服困难的信心,培养竞争和创新的意识。

图论算法实现及应用课程是第四学期作为选修课开设的。在此之前,学生通过前期课程的学习,已经掌握了基本的程序设计思想、方法以及基本的数据结构使用,该课程与算法分析与设计课程同步开设。

图论课程在课程群中利用其算法丰富、应用问题多而广的特点,给学生提供算法分析与设计的实践机会。通过图论课程的学习,学生不仅能掌握丰富的图论知识,程序设计、算法分析能力也将得到进一步巩固和提高。

3.5完善教材建设,适应新的教学思路

教材建设是课程建设的重要工作,教材包括课堂教学使用的教材或讲义、实验教学使用的实验指导书、辅导教材等。为适应新的教学思路和方法,我们编写了讲义和实验指导教材。讲义立足于图论算法思想的描述及程序实现,并以大量的ACM/ICPC题目阐述图论算法思想在求解这些题目中的应用。该讲义在内容取材、描述上具有如下特点:(1)许多图论教材对图论概念的描述不一致,造成读者的阅读和使用困难,该讲义试图改变这一现状。对每个概念的表述,我们查阅了大量的图论著作并进行比较分析。在讲义中,我们对每个概念采用大多数图论教材采用的名词和描述方式。(2)忽略所有图论定理的证明,着重分析图论算法的思想,重点在于这些图论算法的程序实现和应用。对图论算法的程序实现是以经典的ACM/ICPC例题来阐述的。(3)分析每一个算法的复杂度,并对同一个问题不同算法的复杂度进行对比分析。(4)采用浅显易懂的语言、丰富的图表来描述图论算法思想。

4教学方法

一种新的教学思路必须辅以一套新颖的、有效的教学方法,因此我们注重探索合适的教学方法。

4.1课堂教学

课堂教学是教学的重点,我们在教学中采取以下教学方法加强课堂教学效果。

(1) 上好第一堂课。第一堂课的教学效果会决定学生是否会认真听这门课,特别是选修课。对图论的第一堂课,我们往往从一些有趣的问题入手引入图论的研究内容,如哥尼斯堡七桥问题、中国邮递员问题、周游世界问题、图的着色等。这些问题通俗易懂,比较有趣,更重要的是,这些问题可以把图论里的主要研究内容串接起来,从而让学生对图论研究的概况有一定的了解。

(2) 加强课堂互动。图论的很多问题来自于生产生活,在学生的学习生活中也能找到应用的例子。在课堂上,我们经常邀请学生在黑板上演示算法的求解过程,这能帮助学生理解算法的思想和求解过程。

(3) 加强算法的对比分析和演示。为了让学生对图论算法的复杂度有直观的认识,我们通常在分析完算法的复杂度后,对一些例题进行程序实现,并提交到OJ系统,通过反馈回来的运行时间来验证算法的时间复杂度。

4.2实践教学

这里谈的实践教学不局限于实验课。为提高学生对图论课程的兴趣,并引导学生开展基础的论文阅读和文献综述,为今后的专业发展奠定基础,我们在教学中开展了丰富的实践教学内容。

(1) 在解题时,指导学生阅读相关论文,启迪他们的论文查阅意识和能力。比如学生在求解网络最大流问题时指导他们阅读文献[3],这篇文献综述了网络流算法的研究历史和现状。

(2) 图论里有很多问题至今都没有得到解决,比如汉密尔顿回路、图的着色等,国内外学者对这些问题的研究也一直没有中断。我们指导学生综述这些研究,这对培养学生的探索性思维有很大的帮助。

(3) 指导学生定期对求解过的题目进行总结,以解题报告或小论文的形式提交,作为平时成绩的一部分。

(4) 为了丰富OJ系统的题库,我们采取一系列措施鼓励学生出题,比如在题目中对出题学生进行署名,组织学生的个人专场比赛等。学生出的题目大多来源于平时的学习和解题的积累,因此这些激励措施也能提高学生的学习积极性。

5结束语

图论是一门既有趣又具有较大难度的课程。对计算机专业的学生来说,图论课程不仅丰富了他们的数学知识,更锻炼了他们的算法分析与设计能力。采取新的教学思路后,选修这门课的学生逐年增多,许多学生的程序设计和算法设计能力得到了极大提升,并在程序设计竞赛中取得了很好的成绩。

参考文献:

[1] 徐俊明. 图论及其应用[M]. 2版. 合肥:中国科学技术大学出版社,2004.

[2] 徐俊明. 《图论及其应用》课程建设探索[J]. 教育与现代化,1997(2):41-46.

[3] 张宪超,陈国良,万颖瑜. 网络最大流问题研究进展[J]. 计算机研究与发展,2003,40(9):1281-1292.

[4] 钱建国. 浅谈算法实例在图论教学中的作用[J]. 莆田学院学报,2004,11(3):70-71.

[5] 谢政,戴丽,陈挚. 关于图论课教学的思考[J]. 数学理论与应用,2005,25(4):139-140.

[6] 杜承铭. 本科应用型人才培养目标的选择、构建及实现[J]. 教育与职业,2006(32):20-22.