谈专业竞赛对教学实践改革的促进作用

程玉胜 程树林 庞淑芳

摘要:本文结合“数据结构”实践教学,探讨了高等教育大众化教育背景下计算机专业人才培养模式。通过介绍近年来我校参加的计算机专业竞赛,说明改革实践教学模式的必要性。

关键词:实践教学;竞赛;基数排序;最小生成树;哈希函数

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

1引言

近年来,随着高等教育规模的不断扩大,我国高等教育已经进入大众化发展阶段,社会对计算机专业人才的需求呈现多样化的特点。在这种背景下,教育部高等学校计算机科学与技术教学指导委员会制定了专业规范的“三种类型、四个方向”,其中计算机工程方向是工程型人才培养模式之一。根据这样的专业规范,探索大众化高等教育阶段如何培养高质量的计算机专业人才,是计算机教育者面临的一大课题。根据教育部质量工程建设的指导思想以及计算机工程方向人才建设的需求,结合“数据结构”课程,本文主要探讨了专业竞赛对计算机工程方向人才培养的促进作用。

近五年来,我们按照“以学生为主体,注重对学生综合能力的培养”为教学思路,在帮助学生掌握计算机程序设计基本理论和方法的基础上,为了充分利用有限的教学时间,组织好实验课堂教学,完成教学目标,课程组在实验教学中引入了应用背景驱动的学习策略和方法,探讨和实践了“数据结构”应用背景驱动的课程实践教学方法的改革。主要包括:(1)分层教学法,根据学生的接受能力,充分发挥不同层次学生能动性,循序渐进的开展实验任务。(2)创造学习“情境”,将新知识点与实际应用联系起来,建立学习者知识的内外联系。(3)将应用背景驱动的教学策略应用到组织部分优秀学生参加计算机仿真,程序设计大赛等,在提高学生的理论学习成绩与实际操作能力方面收到良好效果。

2数据结构中的实践教学

“数据结构”课程是计算机科学的算法理论基础和软件设计的技术基础,主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现。学习本课程的过程也是进行复杂程序设计的训练过程,要求学生书写的程序结构清楚、正确易读,符合软件工程的规范。上机实习着眼于原理与应用的结合,使学生学会如何把书本知识用于解决实际问题,培养软件工作所需要的动手能力;同时还能使书本知识变活,进一步深化理解和灵活掌握教学内容。通过上机实验可以培养学生分析具体问题、建立数学模型并解决实际问题的能力,培养学生创新意识和提高动手实践的能力。

“数据结构”课程算法很多,由于受到教学时间的限制,要求全部实现不大可能,我们共提炼出8个实验,要求学生在实验课时中必须完成,也是基础层中设置的基本实验。而为了进一步培养学生分析问题、解决实践问题的能力,我们又构思了一些知识点的应用“情境”,通过引导和分析,进一步提高学生的动手能力。最后通过选拔部分学生参加专业竞赛,激发学生的创新思维。

因此,在“数据结构”实践教学中,主要采取以下步骤进行:

第一步:要求学生掌握基本算法及其实现;

第二步:布置相应的“情境”,要求学生去分析问题,即“建模→设计算法→选择存储结构”;

第三步:进行“性能分析→算法模拟→优化模型”;

第四步:编程调试解决问题。

例如关于基数排序算法应用到数据分类中。在粗糙集理论中,对象的划分求解是通过不可分辨关系实现的。例如表1中U/IND(a)={{x1,x3},{x2,x4,x5}}。

通过基数排序算法,可以求出U/IND(a,b,c),过程如下:

第1趟“分配”:

Front[1]->x1->x3<-End[1]

Front[2]->x2->x4->x5<-End[2]

第1趟“收集”结果:

x1(111)-->x3(111)-->x2(222)-->x4(232)-->x5(222)

第2趟“分配”:

Front[1]->x1->x3<-End[1]

Front[2]->x2->x5<-End[2]

Front[3]->x4<-End[3]

第2趟“收集”结果:

x1(111)-->x3(111)-->x2(222)-->x5(222)-->x4(232)

第3趟“分配”:

Front[1]->x1->x3<-End[1]

Front[2]->x2->x5->x4<-End[2]

第3趟“收集”结果:

x1(111)-->x3(111)-->x2(222)-->x5(222)-->x4(232)

数据分类结果(见图1):{ x1 ,x3 },{ x2 ,x5 },{ x4 }

3专业竞赛实例分析

我们组织了部分优秀学生前后参加了两届全国计算机仿真大奖赛,均获得好成绩。在2004年“首届全国计算机仿真大奖赛”中,针对竞赛的内容,我们将hash函数的方法,用计算机仿真的方法成功地解决了一元高次方程的求解,获得了全国第二名的成绩。在2006年“第二届全国计算机仿真大奖赛”中,将数据结构图的优化问题应用到关于控制理论中共振点的求解方法,获得了全国二等奖,以及在成功利用数据结构中表的查找操作后,关于信息检索的体育馆买票智能推荐系统获得全国三等奖。另外,关于最短路径的优化问题在“第二届全国计算机仿真大赛”中成功参赛。下面简单介绍数据结构中相关知识点“情境”构造。

3.1哈希函数的“情境”构造

下面是“第一届全国计算机仿真大奖赛”参赛并获得全国第二名作品(指导老师:程玉胜),问题描述如下:

已知一个n元高次方程: ,x1,x2,…,xn是未知数,k1,k2,…,kn是系数,p1,p2,…,pn是指数,取值为正数;且方程中的所有数均为整数;假设未知数1≤ xi ≤M(i=1,2,……n),求这个方程整数解的个数(方程整数解的个数小于231)。其中约束条件1≤n≤6;1≤M≤150;

从方程的已知条件可知,此方程在最坏的情况下有6个未知数,每个未知数xi的取值范围最大为M。如果采用简单的枚举方法来实现,那么它的时间复杂度是O(M6)。假设未知数个数为n,未知数的值不超过M,F(n)表示二分法后解的最大规模,因此该问题的时间复杂度主要集中在利用哈希技术存储左表达式A所有可能取值到 数组对应位置,对应时间复杂度为O( )。而右表达式值B利用哈希查找方法进行定位,时间复杂度为O( )。因此总的时间复杂度T(n)为。考虑A式:的可能取值并利用哈希技术来存放A式的值s,考虑到s在最坏的情况下有1503=3375000个不同的取值,因此定义长度为3375000的线性表来构造哈希表,并令哈希数取3375000。并且考虑到相同的s值可能出现多次,为了统计次数将线性表的存储结构定义为两个域:一个存放s值,另一个统计这个值出现的次数。

在实验中选择“除余法”构造了哈希函数:由于哈希表的长度为3375000,因此可取p=3375000令h(k)= k mod p;当不同的s值具有相同的哈希值时,便会产生冲突,可采用线性重新散列技术解决冲突。令数组元素个数为p,则当h(k) 位置已存储有元素时,依次探查(h(k)+i) mod p,i=1,2,3……,直到找到空的存储单元为止。

例1给定n=4,M=150k1=k2=-1,k3=k4=1,pi=2(i=1,2,3),p4=3,该n元高次方程解的个数通过计算机仿真后,结果为5167,如图2所示。表2给出该方程所有可能含对约束条件检测的仿真结果:

3.2最短路径算法“情境”构造

下面是“第二届全国计算机仿真大奖赛”成功参赛作品(指导老师:程树林),问题描述如下:

某省的七个城市需要架设通信网络系统,以连接这七个城市,每两个城市之间的距离如表3所示。考虑地理环境的影响,综合考虑各城市之间的距离和每公里修建通信网络的费用,各个城市之间修建网络每公里的费用可用于10000元之间的比较如表4所示。试问如何架设通信网络,使总费用最小?

在七个城市之间架设通信网络系统,要使任何两个城市之间都能相互通信,最少需要6(7-1=6)条线路。总共有7*6/2=21条通信线路可供选择,本题要求所架设的通信线路总费用最少,也就是在21条线路中选择6条线路,所选择的6条线路必须使七个城市之间可以相互通信,并且所消耗的费用是最小的。现在要求架设通信网络的最低耗费问题也就相应地转化成求相对应的无向完全图的最小生成树的问题。另外,九个模糊词:“完全是、可认为是、差不多是、非常接近、十分接近、很接近、比较接近、大致接近、相当接近”,我们并不能确定这些模糊词的精确值,而且程序中并没有约定它们具体的值,我们可以尝试采取如下方案(图3):

第一步:给这九个模糊词指定一个大致的取值范围,如(0.8～1);

第二步:用户可以根据自己对模糊词强弱的理解或者根据实际需要,给每个模糊词输入一个具体的范围;

第三步:在每个模糊词相应的范围中选择一个值;

第四步:根据上面所输入的参数计算各边的权值(每两个城市之间线路的费用),即长度*模糊词量化值。

4专业竞赛对实践教学的促进作用

2004年首届全国计算机仿真大赛,我们选拔了最优秀的学生参赛,通过15天的艰苦奋战,在大赛中取得了全国第二名的优异成绩。2006年,学生参赛热情空前高涨,最后通过选拔,组成了5支参赛队伍、每队3人,并且为每支代表队配了一名指导老师。我们邀请了部分优秀老师对学生进行参赛前的集训,这次集训为大赛取得更好的成绩打下了一定基础。在老师的精心指导下,15天后学生完成了作品,最终程玉胜老师指导的作品获得了全国二等奖。

计算机仿真大赛,不仅教会了学生集体攻关的能力,培养了学生的团队精神,更重要的还培养了学生的创新思维和动手能力。同时,对实践指导老师提出了更高的要求,要求把创新的思想、计算机工程方法加入对实践教学模式和内容的改革中。

5结论

通过专业竞赛,充分调动了同学们学习的自觉性,激发了学生分析问题、解决问题能力。以上成果与我院近几年来开展的一系列“要求培养学生动手能力和创新思维”活动是分不开的,是我院在高等教育大众化背景下面向计

算机工程型人才培养模式的一次大探索。

致谢:感谢我校计算机系04届叶敏、汪智华、齐乐,06届刘伟、袁绪广、刘玉龙,07届吴萍,08届瞿鹏和程树林、钱萌老师等参与的专业竞赛和相关“情境”材料的编写和程序设计。

参考文献:

[1] 程玉胜,庞淑芳,章晓良. Application-Driven Background Model about Hierarchical Practice Learning in Data Structure[C]. International Symposium On Education And Computer Science(ECS2009),Wuhan,2009:274-277.

[2] 钱萌,程玉胜,程树林. 基于分治策略求解方程根的个数[J]. 计算机技术与发展,2006,16(9):41-43.

[3] 严蔚敏,吴伟民. 数据结构[M]. 北京:清华大学出版社,1997.

[4] 江效尧,江克勤.“协作式学习”理论在“数据结构”实验教学中的实践[J]. 安庆师范学院学报,2006,12(04):25-27.

Discuss about Special Competition to Accelerate the Experiment Learning Reform

CHENG Yu-sheng, CHENG Shu-lin, PANG Shu-fang

(Dep. of Computer, Anqing Teachers College, Anqing 246011, China)

Abstract: This paper discusses the model of training professional man for computer under popular high education combined experiment learning of data structure. Our school takes an active part in some computer competition which shows that it is necessary to reform our experiment learning.

Key words: experiment learning; competition; radix sort; minimum cost spanning tree; hash function