时间:2023-03-15 14:56:14
引言:寻求写作上的突破?我们特意为您精选了12篇数据结构与算法范文,希望这些范文能够成为您写作时的参考,帮助您的文章更加丰富和深入。
作者简介:李永(1978-),男,安徽宿州人,盐城师范学院信息科学与技术学院,讲师。(江苏 盐城 224002)
中图分类号:G642.0?????文献标识码:A?????文章编号:1007-0079(2012)31-0057-02
“算法与数据结构”主要研究数据在计算机中的表示方法、存储方法以及其上的操作。[1]在美国IEEE/ACM课程体系和我国教育部学科规范中,[2,3]“算法与数据结构”被列为核心课程之一。它是操作系统、数据库、软件工程和人工智能等课程的基础。算法与数据结构蕴含的思想对学生在软件设计方面有很强的导向性,它的教学效果直接影响学生的数据抽象和程序设计能力的培养。学习该课程,一方面,使学生学会分析数据对象的特征,掌握数据组织的方法和在计算机中的表示方法,为数据选择合适的逻辑结构、存储结构和算法;另一方面,培养学生良好的程序设计风格,进行复杂程序设计的训练。[1]
为了在课时约束、学生基础、课程难度、教学目标等约束下最大化教学质量,使学生最大限度地得到提升和发展,本文从分析“算法与数据结构”课程存在的问题出发,在教学内容、教学方法、实验教学等方面进行了一些探索和实践。
一、“算法与数据结构”教学中存在的问题
1.课程本身难度大
“算法与数据结构”是抽象与具体的统一,理解与掌握它需要跨越横亘在抽象与具体之间的鸿沟。学习该课程有两个难点:一是从算法与数据结构到程序实现的跨越;二是从实际应用到数据结构抽象的跨越,即如何利用算法与数据结构解决实际问题。[4]“算法与数据结构”的内容抽象、繁多、逻辑性强,难于理解掌握。学生学完后不知道学了什么,当需要解决实际问题时感到无从下手。“算法与数据结构”综合性、技巧性强,各种算法中凝结了大量杰出计算机科学家的智慧,在有限的教学时间内部分学生因无法领悟其中的思想与精髓而产生厌学情绪。
2.前导课程基础不扎实
“C语言程序设计”、“高等数学”、“离散数学”等是数据结构的前导课程,其中“C语言”与“数据结构”课程的联系最为密切。“C语言”一般开设在大一第一学期,是学生最先接触的程序设计语言。由于内容多、难度较大、大班教学、课时有限等原因,教学时间大部分花在基本概念及简单程序的编写上,对结构体、指针、参数传递等难度较大的知识点讲解不深入,为“算法与数据结构”的学习埋下了隐患。
3.教学方法有待改进
“算法与数据结构”的教学方法主要为板书结合PPT课件,教学方式采用“教师讲—学生听”的灌输式授课模式,与学生互动少,课堂气氛沉闷。教学方法中以教师为中心按照教学大纲教学,存在照本宣科、就事论事、内容堆砌、缺乏新意等缺点。由于没有考虑学生的接受能力、思维能力以及编写代码的能力,学生只是不加思考地被动的接受知识,限制了学生的积极性与主动性的发挥。
4.实验教学中存在的问题
目前课程实验中存在的问题主要有下面三个方面。首先,大多高校“算法与数据结构”实验的教学方式仍是以教师为中心,以灌输、模拟、验证为主;教师按教材单元布置实验任务并做适当的引导和提示,然后学生动手实践。没有考虑实验的实用性以及是否适合学生,不能调动学生的学习热情。其次,学生的程序设计能力普遍较弱,面对问题时难以有清晰的算法思想,无法将算法思想转变为正确的程序代码,上机调试和运行程序时面对众多的错误提示无法正确解决,实验课教学效果大打折扣。再次,由于实验课时有限,且实验内容具有相互依赖和递进的特点,部分学生又不能充分利用课余时间,造成问题堆积。
二、“算法与数据结构”的教学探索
1.合理组织教学内容
贯穿“算法与数据结构”课程的主线是逻辑结构、存储结构及操作,即线性表、树、图三种逻辑结构;顺序和链式两种存储结构;插入、删除、查找、遍历等操作。这些内容不是孤立的,在教学过程中将它们联系起来形成一条主线,由线性到非线性,由简单到复杂,方便学生理解和掌握。在教授课本内容时,根据教学大纲的要求梳理并提炼出各章节的知识框架,根据学生情况和教学目的合理划分课时,控制课程节奏。课堂上主要针对程度一般的多数学生从数据结构的逻辑结构、存储结构和数据的运算三个方面去组织教学内容,做到重点突出、内容简洁。对于程度差的学生进行个别辅导,通过补习和细化教学内容帮助其跟上教学进度。对于程度较好的学生,通过指定课外读物、布置思考题等,让其能力得到充分发挥。
2.上好第一节课,激发学习热情
1背景
数据结构与算法是计算机类专业的一门核心基础课程,是计算机、软件工程等电子信息类专业的必修课。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法;介绍了常用的多种查找和排序技术,并对其进行性能分析和比较,内容非常丰富[1-2]。本课程的教学目标是加强学生对数据逻辑关系的分析与认识,培养学生数据抽象的能力,通过理论分析与编程实践相结合,增强学生求解复杂问题的能力以及控制算法复杂性的能力。
在计算机科学中,数据结构不仅是程序设计的基础,而且是设计和实现编译程序、操作系统、数据库系统等系统程序和各种大型应用程序的重要基础[3]。数据结构与算法是计算机类专业部分专业课的先导课,如操作系统、编译原理和数据库原理等,因此它为后续的专业课程学习提供必要的知识和技能储备[4]。数据结构与算法课程一直以来都是本学科的核心专业基础课程,而且正逐渐发展成为众多理工科专业的热门选修课。只有学好了这门课,才能在今后的计算机专业课程的学习中游刃有余。因此,本课程在国内同类课程中有较明显的先进性和示范性。
根据新世纪对人才培养的要求,教学应重在学生能力、素质的培养,尤其是思维能力、实践能力、创新能力的培养。多年来我们致力于数据结构核心课程的建设,从完善课程体系、加强团队建设、深入教学改革和丰富教学资源等各个环节不断探索和实践。从提高学生的学习兴趣和加强实践环节教学方面入手,在教育教学方面持续、深入地改进教学方法,开展教学研究,提高教学质量。
2完善课程体系
首先,完善以“扎实基础,强化实践,引导创新”为培养目标的课程体系。计算机类专业核心基础课程体系主要由离散数学、面向对象的程序设计、数据结构与算法、操作系统、编译原理、计算机组成与结构、数据库原理7门课程组成,用于支撑计算机科学与技术、软件工程、网络工程、信息安全、数字媒体技术5个计算机科学相关专业的教学。
我们将课程群的理念引入计算机专业基础类课程教学,建立了以数据结构为核心的计算机类基础课程群,如图1所示。课程群以培养综合运用计算机基础知识能力为目标,打破课程间的壁垒,强化课程联系。本课程群以数据结构为核心,将数据结构的一些基本内容如链表、排序等渗透到“C/C++程序设计”课程中;将编译原理、数据库原理等需要使用数据结构内容的部分在数据结构课程中以应用的实例进行讲解,从而将相关课程的授课内容形成统一的整体。
在实践环节我们强化数据结构对程序设计语言的训练及解决相关课程问题的训练。除各门课程有单独的实践课程外,独立设置贯彻整个教学环节的实践课程,将数据结构课程群中各门课程较为关联的综合大作业进行归并整合。自身实验课程注重双基训练,但大实践课程要求对整个数据结构课程群教学经验丰富、能够精确把握该课程体系要点的教师进行授课,在教学中能够结合本学期相关课程设置大作业,在讲授中能够根据学生的具体情况进行诱导性教学,使学生通过完成大作业来更深刻地认识学科体系的全貌,强化学科综合素质的培养。
以数据结构课程为中心构建计算机类专业的核心基础课程体系,将与计算机科学相关专业的专业基础课程教学打通,在课程、课件、教材、师资队伍等多方面进行统一的规划和建设,以不同的着重点组织课程教学内容、进行大学生计算机实践能力和创新能力的培养。该体系打破了原有实验教学附属于理论课程的模式,理论教学与实验教学既相对独立、又相互联系,改变了单一的知识验证的实验模式,增强综合应用设计和创新实践内容,全面提高学生的实验实践技能。“扎实基础,强化实践,引导创新”培养目标体现了当前计算机类专业教育的发展趋势,走在国内高校的前面,在全国各类会议作专题报告近30次。
3加强团队建设
目前我院数据结构与算法教学团队共有5位主讲教师,其中教授2人,每50名学生配一名助教(博士或工学硕士)。该教学团队主要由30~40岁的年轻教师组成,尽管精力充沛,工作热情很高,但教学经验尚有欠缺。团队建设是本课程建设的重中之重,要把提高教师的综合素质和教学科研水平,强化教师的责任心放在首位。坚持教学与科研相结合,以国家自然科学基金项目为依托,为提高教学质量,不断提高科研水平和能力;以国家特色专业建设项目为依托,加强教学研究,以理论指导教学实践,吸取好的教学方法和经验,不断改进教学方法和手段,迅速促进教学团队成长。
在青年教师培养方面注重教学和科研能力的同步培养。要求青年教师在首次上课之前听课助课,培养基本教学能力;实行集中备课,统一课件,互相监督,保持教学一致性和教学内容一致性;定期召开教学研讨,及时总结教学经验方法,教授言传身教;以特色专业建设项目为依托,鼓励青年教师开展教学研究,以国家级项目为依托开展科研课题研究。青年教师成长迅速,已具备一定的科研能力,教学效果良好,学生满意超过90%;获得校教学质量优良奖,青年教师讲课竞赛二等奖,多媒体课件二等奖等多项奖励,已经成为学院的业务骨干。
4深化教学改革
4.1不断探索新的教学模式
1) 实践性教学。
实践是获得真知的根本源泉,主动探索真知是研究型人才的基本素质,我们在基础课中的创新能力培养主要体现在,让学生在自由的实验环境中积极实践、主动探索,自己发现新的知识和理论。如图2所示,在实践环节建设方面,建立书面作业,上机作业和课程设计3个层次的实践教学环节,以通过书面作业形式消化理解教学内容;通过上机作业培养动手能力,将课程单元知识转化为实际技能;通过课程设计培养解决实际问题的能力,融会贯通本课程的知识。
为了满足强化实践的教学要求,本课程团队经过多年实践,精选、整理了包括卡内基梅隆大学、斯坦福大学、麻省理工学院等国内外著名大学教授布置的实践作业,结合我们的教学要求,每学期给学生布置18道有一定创新性的上机题目。这些题目既反应了数据结构教学的基本知识,又来源于实际应用。达到了理论和实践的完美结合。本课程实践教学和理论教学环节的学时比例为1.5∶1。经我们多年实践,这个比例符合我国高等教育实际,达到了良好的能力锻炼目的,值得推广和借鉴。
2) 研究型教学。
在研究性理论教学方面,以教学大纲为主线,整理数据结构领域的经典论文,以提出问题为课堂教学的第一步骤,引导学生思考,将科学家的研究方法和研究思路融入课堂教学中。依托科学研究项目,提出本学科领域的最前沿课题,鼓励学生思考并解决。对有明显创造性的成果可以在教师指导下撰写学术论文。
将研究型教学融入数据结构实践教学课堂,鼓励学生从解决问题的角度研究如何设计数据结构与算法,在传授基础知识的同时注重创新性思维方式的培养,发现问题和解决问题能力的培养。
4.2全方位的课程改革
课程建设的核心是提高教学质量。为提高教学质量,我们从教学内容、教材、教学方法和手段、考试方法、实践教学等方向进行了全方位的改革。
1) 教学内容改革。
课程组参考国内外其他院校本课程的教学大纲和优秀教材,对数据结构课程的教学大纲进行了多次修订,逐步稳定了理论教学的教学内容、教学要求,细化了教学目标,明确了教学任务、教学内容、教学重点和难点、不同知识点的掌握程度。理论教学采用以共性化课堂教学为主,并利用辅导答疑和实践教学组织以学生为主的个性化教学,培养学生创新能力,辅助课堂教学。在教学过程中采用启发式教学方式,即注重学生基础理论知识的掌握,也注重学生分析问题、解决问题等基本能力的培养。
为了配合理论教学,我们也多次修订了实验大纲,使实践内容更加符合专业的发展和其他各方面的要求,并且与前序课程和后继课程很好地衔接。在实践环节中注重学生能力的培养和科学的开发方法的培养。实践教学内容采用梯度组织,具有不同的难易程度,方便学生巩固学习和拓展知识。
2) 教材选取。
目前本课程使用教材为高等教育出版社出版的《数据结构与算法》,许卓群、杨冬青等编著。该教材除了讲授基本数据结构外,突出作为面向对象程序设计的基础概念――抽象数据类型,强调算法与数据结构的密不可分性、封装性等;在处理知识面的宽度和知识点的深度上,既满足作为基础课的要求又达到一定的水平,完全适合本专业对人才培养的要求,是普通高等教育“十五”国家级规划教材。目前课程组已经开始着手准备根据我们自己的教学特点、专业要求等实际情况自主编制一套教材。
3) 教学方法改革。
(1) 启发式教学:学生的主动性是学习,我们在教学过程中注重启发学生的思维,采用循循善诱的方式引导学生自己发现问题,并逐步解决问题,培养学生思考问题、分析问题和解决问题的能力。这极大调动了学生的主观能动性,培养了学生分析和解决问题的能力。
(2) 共性化与个性化相结合教学:从教学形式上,我们积极探索新的教学方法,以便能够调动和发挥学生的主观能动性。具体有以教师为主体的课堂教学、习题课等共性化教学环节,也设置了答疑p质疑等教学环节,引导鼓励学生通过实践和自学获取知识。共性化与个性化相结合,既可以起到教师主导作用,也可以满足学生个性学习的需求。
(3) 理论与实验相结合:数据结构课程主要介绍数据的逻辑结构、物理结构以及算法。算法的思想需要通过一种程序设计语言加以描述并在计算机上实现。我们在重视理论教学的同时,也很注重实验课,注重学生灵活应用知识能力的培养。理论与实验相结合,可以使学生更好地理解“数据结构”的思想与概念。
5丰富教学资源
建立本课程网上课堂及在线智能教学系统。网上课堂设计的目的是能够给不同层次、不同需要的学生提供帮助,提高教学质量。根据网络教学环境的要求,
系统主要包括课程概况、师资队伍、教学资源、实验指导、教学录像、课程扩展、课程论坛等多个模块。系统主要具有以下特点:
1) 在线学习。
知识内容结构化,主体结构采用网页形式组织教学内容,以单元、章、节等知识点为中心组织教学,以关键词或标题为线索进行任意的查找。各知识点在整体上搭建框架式结构,思路明晰;在细节上环环相扣,前后关联紧密,便于学生更好地理解和掌握知识要点。
2) 动画演示。
以数据结构部分的讲授为例,这部分内容包含许多的算法,其描述大多数采用类高级语言的形式进行,有些算法无论是时间复杂性或是空间复杂性都比较高,采用动画的形式将算法的执行过程和思想呈现给学生,使学生很容易理解这一过程,再配上教师的解释做旁白,可产生与上机亲身实践和跟踪执行相似的效果。
3) 在线测试。
用数据库对练习题和模拟题进行有效的管理,在学生进入到考核子系统后,能交互式进行试题的选题与答题。当学生提交答卷后,系统又能对答分进行自动评判,并给出相应正确的答案和综合得分。
4) 课程扩展。
为更好地促进教学,本课程在巩固基础知识,提高实践能力的基础上,对学有余力的同学扩展了本课程的内容。引入了卡内基梅隆数据结构教学网站,这是一套全英文系统,上面提供了丰富的工程性题目训练,更加注重数据结构算法在实际中的应用,让学生开阔了思维和眼界;还为学生提供了ACM竞赛以及大连理工大学程序设计竞赛的模拟题库,通过这些略有难度又很新颖的题目进一步提高学生的学习兴趣,培养其解决实际问题的能力。
6结论
在近几年的课程建设实践中,我们的任课教师认真组织教学内容,与实际相结合,积极探索有效的教学方法,利用多媒体技术动态演示复杂数据结构的变化,并补充学生比较感兴趣的知识,拓宽学生的知识面。逐步完善和充实现有课件,做到内容充实,画面生动,具备声像效果,收到了很好的教学效果。作为计算机科学的核心内容,数据结构与算法的理论研究及应用研究一直在不断发展,在以后的工作中要注重研究型教学,鼓励学生从解决问题的角度研究如何设计数据结构与算法,并将学科领域经典研究成果和最新研究成果及时地反应在课程教学中,相信数据结构与算法这门课的教学效果和教学质量在我们持续深入的教学改革中会越来越好。
注:本文受教育部第二类特色专业建设项目――软件工程特色专业建设项目资助。
参考文献:
[1] 严蔚敏,吴伟民. 数据结构[M]. 北京:清华大学出版社,2002.
[2] 殷人昆. 数据结构(用面向对象和C++描述)[M]. 北京:清华大学出版社,2007.
[3] 殷人昆,邓俊辉. 清华大学“数据结构”精品课程建设[J]. 计算机教育,2006(5):20-22.
[4] 钱红兵,唐发根. “算法与数据结构”课程教学体系的建设[J]. 计算机教育,2009(17):65-66.
Development of the Data Structure and Algorithm Core Course
LIU Xinyue, ZHANG Xianchao, YU Hong
关键词: 公交;数据结构;算法;实现
Key words: bus;data structure;algorithm;implementation
中图分类号:TP301.6 文献标识码:A 文章编号:1006-4311(2014)19-0202-02
0 引言
目前,公共交通是人们出行最常用的一种方式,本文意在对公交数据结构算法与实现问题进行相关分析,使人们出行可享受便利的公交服务。基于对具体公交实际情况的研究,笔者对公交数据结构的算法进行了人性化的修改,使其实用程度大大提高,以不断满足大多数人的出行习惯和要求。
1 以GIS为基础的公交数据结构模型
GIS就是一种地理信息系统,它主要是用于搜集、模拟、加工、检索、分析以及表达地理空间数据的计算机数据信息系统。它以点、线、面三种不同的基底数据模型表达为主。因此,我们可以通过计算机建立起城市公交网络模型,利用GIS点模型来显示公交车站的具体数据信息,进而用这些数据结构来表示公交线路的路径信息。
经过比较,我们发现一个城市的公交网络要比其道路网络复杂许多,它不但包括公交站点与公交路线的数据结构,而且还有许多其他的数据信息。我们可以从图1公交网络模型的结构图来了解部分相关数据结构。
首先,公交站点数据。
这里的公交站点是指城市公交网络体系中的所有公交站点,在这里,我们可以借助于点模型来具体描述它们的地理位置,最后把它们站点名称等信息储存在属性数据之中。
其次,公交线路数据。
据调查,每一条公交线路都有自己对应的唯一编号。这一编号包含多种信息,主要有该公交线路的名称、起点、终点、上班、下班时间等具体信息,这些信息都记录在属性数据中。
其三,公交段数据。
公交段数据主要指城市公交线路的路径信息。我们可以利用线模型来描述其具体的地理位置。
其四,线路与站点关联数据。
各个线路与站点的辨别以及相关信息都是通过关联数据来体现的,这些数据都是按照顺序从始至终来记录的,清楚并相互对应的描述了公交线路的每个站点。
其五,站点与线路关联数据。
站点与线路关联数据是用来记录站点所经过的公交线路信息的,并以此来记录站点与线路的关联信息。
公交网络模型,它的数据结构不单单含有丰富的公交信息,还明确了每一个公交实体相互间的关系具体是怎样。在公交段表中所介绍的公交站点和公交段之间的空间拓扑关系,其实就是每个公交段记录一个前结点和后结点,实际上也是这个公交段的起始站点和终止站点的一个记录。其次,每张表中的数据前后要保持一致,比如:站点-线路关联中的线路ID必须跟公交线路的LineID保持一致,而它们之间的数据结构关联关系见图2具体表述。
2 公交数据结构算法与实现的思路
在实际的生活中,公交数据不是固定不变的,它往往受到多种因素的影响,因此在公交数据结构算法与实现的过程中我们要充分考虑这一问题,努力合理实现公交数据结构的计算和应用。
2.1 影响公交数据结构算法与实现的因素
影响公交数据结构算法与实现的因素有多个,主要有以下几个:首先,出行距离。这主要包括两种,即车上距离和车外距离。车外距离就是指乘车者为了乘坐公车而步行的那段距离;其次,换乘次数。这是指乘车者为到达目的地在乘车的过程中所换乘公交车的次数;其三,出行时间。这是指乘车者在一次出行过程中所需总的时间,这既包括在车上的时间也包括为乘车花费的车外时间;其四,出行费用。这是指乘车者在完成一次出行过程中所花的车费。由于不同的乘客对于这些因素的要求不一样,他们优先考虑的因素不同,这就导致公交数据及其结构的变化。本文笔者经过研究提出了全面的公交数据结构模型,并给出了对应的计算方法。
2.2 人性化的公交数据结构算法与实现
而公交数据结构算法与实现在实际的运用中要本着人性化的要求,因此在这一算法的过程中,我们要着实考虑多种不同的优先策略,例如尽量减少乘客的换乘次、费用最少化、时间和距离最短化、道路最优化等等。不同的人对公交乘坐路线的选择也是会有不同的,因此乘车方案要结合具体的实际情况进行考虑,有的人会把时间因素看的重要些,有的人会率先考虑费用问题,总而言之,其实就是对公交网络模型中的权值的衡量。
本文经过实践和调查提出了一种基于换乘次数最少的公交数据结构算法,这一计算方法相对其他方法来说比较符合人们出行时的心理状况。这一计算方法的思想我们可以描述如下:
根据大多数人的习惯我们可以得出,在出行选择路线时,2站之间首先考虑的是直达车,如果只有一条则选择该方案,若有多条则根据花费时间,花费费用等因素进行选择。如果没有直达车,则要考虑换乘,换乘时首先考虑经过2站的车辆是否有共同的站点,如果有,则可以在此站进行换乘,如果没有则要考虑进行2次换乘,即在2站之间选择2个站点,这2个站点的选择必须保证4个站点中有可直达的车,在中间的站点换乘2次,如果选择此出行方式还是没办法到达目的地,则我们就需要考虑进行3次或者更多次的换乘。综上所述,出行乘坐公交车时不仅仅有一种方案,这就需要我们综合花费时间,花费费用等多方面的因素优先选择。所以,这一算法是对不同情况进行综合考虑的结果,也就是用下面所述的权值来衡量最优的换乘方案:
σ=距离×权重%+费用×权重%+景观道路×权重%......
从以上公式我们可以看出,依据不同情况对每种因素所占的权重进行调整,来计算综合因素σ,最后通过比较σ来就可判定多种乘车方案中的哪个是最优方案,以选择最优的出行路线。
2.3 公交数据结构算法与实现的基本步骤
本文通过对最优公交途径的分析,并结合城市公交网络的具体基本特点提出了城市公交数据结构算法与实现的具体步骤:首先,依据城市公交网络建造公交数据结构模型;其次,结合城市公交网络的具体特点把直达矩阵引入公交网络数据的计算,并且可以根据这一直达矩阵把城市公交网络看成是一个“公交网络邻接图”。其三,采用最短路径算法的同时,结合城市公交抽象网络图进行计算,即可得出最少换乘次数以及可能换乘的公交站点。最后,在用建立起来的公交网络模型和所得换乘次数以及可能的换乘站点进行计算,得到了综合考虑最小换乘和最短路径的最佳路径。这样,就实现了人性化的公交乘坐计算方法,给人们的出行也带来了
便利。
3 公交数据结构算法与实现的意义
本文在以上分析的基础上,从乘客的出行心理出发,提出了“换乘次数最少”、“最短路径”等相结合的公交数据结构算法与实现的标准。这些算法在GIS地理信息系统中寻找接点的相邻接点,打破了邻接关心的束缚,使得换乘的搜索和计算成为可能,为乘客提供了起点与终点之间的适合的便利路线。这不但满足了人们“换剩次数最少”的出行心理需求与实现公交出行的科学性,也在一定程度上提高了人们公交出行的意识,对解决城市交通压力过大与交通堵塞等城市交通问题有极大帮助。
4 结束语
总而言之,论述以GIS为基础的城市公交数据结构模型,并且在此基础上提出了公交数据结构算法与实现的思路,这一思路是在分析实际的公交出行情况后得出的结论。文中笔者提到的具体公交数据结构算法其在具体的实用过程中有所提高。但是我们也应看到公交出行的实际情况要比我们看到的复杂的多,还有许多方面都需要进一步研究,相信在未来的公交数据结构算法与实现的过程中我们会取得更好的成绩,最终实现公交的便捷化、快速化、实用化。
参考文献:
1“数据结构”的教学现状
任何实际问题只有建立了数学模型才可以被计算机计算,而数据结构就是实际问题中元素的数学抽象,算法则是建立和解决数学模型的方法。
“数据结构”这个术语在整个计算机科学与技术领域得到广泛使用,它被用来反映一个数据的内部构成,即一个数据由哪些成分数据构成,以什么方式构成,呈什么样的结构等。数据结构是数据存在的形式,也是信息的一种组织方式,其目的是为了提高算法的效率,它通常与一组算法的集合相对应,通过这组算法集合可以对数据结构中的数据进行某种操作。
“数据结构”是计算机以及相关专业的一门核心课程,具有承上启下的地位和作用,“程序设计语言”(例如C或C++) 和“离散数学”是它的先导课程,“操作系统”、“数据库原理”、“软件工程”等则是它的后续课程。“数据结构”课程既有相当的理论抽象性,又有鲜明的应用特色,是专业基础课程中的一门有一定教与学难度的课程。
“数据结构”课程一向都有上机实验的要求,但主体通常还是课堂教学,无论是实验设计还是实验强度都远远不够,带有强烈的“验证性”色彩。但是鉴于以下原因:(1) 由于低年级程序设计语言教与学所存在的问题,学生普遍不能顺利地运用程序设计语言工具;(2)对于应用型院校以及许多专业的学生来说,学习数据结构与算法的主要目的应该是在理解的基础之上更好地从事计算机软件的设计与运用。因此,“数据结构”课程的教师必须决定其课程是集中于问题和理论,还是为学生提供一个能够对其进行充分实验的环境,让学生在实践的环节中增加感性认识,产生对相关理论知识的需求。
2教学内容的分层次设计
从1999年开始,经过几年的大规模扩张,人们对大面积扩招后形成的新的高等教育态势进行了重新认识,并把普通高等学校一般地分为研究型大学、教学科研型大学、教学型本科院校、高等专科院校和高等职业院校等几种办学类型。随着高等教育大众化、普及化时期的到来,初步形成了各类大学相对稳定的分层次办学的格局。
根据教育部计算机科学与技术专业教学指导分委员会的“中国计算机本科专业发展战略研究报告”,我们至少可以认为:所在院校的办学类型不同、培养目标不同、所在地及其周边地区社会需求的不同,这些计算机专业的教学内容应该有所不同。作为一门重要的计算机的专业基础课程,针对不同院校不同的教学目的,“数据结构”应该有不同的,分层次的教学设计。
我们认为:对于大多数计算机专业以及IT相关专业的学生,尤其是非研究性院校的学生,应该把数据结构的学习定位在理解、熟悉和能够灵活运用的基础上,而把那些“考研”所需要的更深层次理论性内容放在选修或者考研复习阶段来解决。从长远看,应该对各层次院校的计算机专业所开设的“数据结构”课程的教学内容进行研究,对其教学方法进行积极的探索。
数据结构与算法的应用面广,涉及技术领域宽泛,也被人们赋予了很高的期望值,对于计算机及其相关专业的一般学生和读者来说,肯定是需要掌握的重要专业基础知识之一。另一方面,虽然全部计算机应用技术都有实践性的要求,但数据结构与算法对于应用基础理论来指导开发实践却有着特别的需求,单凭课堂教学和一般作业,要真正领会数据结构与算法课程所介绍的概念、原理、方法和技巧等,是很困难的。因此,要让学生真正理解数据结构与算法的基本知识,具备将数据结构知识应用于社会实践的能力,积极加强数据结构课程的实验环节是至关重要的。
3教学改革、实验创新与成果
根据以上思考,我们在教学内容的安排、实验项目的选择、实验步骤的设计和实验文档的组织等诸方面都做了精心的考虑和安排,尝试为“数据结构与算法”课程编写了主要用于实验也可用于课堂教学的教材《数据结构与算法实验教程》。该教材依据课程教学大纲,充分理解课程的大多数主教材,遵循课程教学的规律和节奏,体现了实验的可操作性,帮助学生切实把握本课程的知识内涵和理论与实践的水平。
《数据结构与算法实验教程》采用C语言作为描述语言,通过一系列与课程单元知识密切相关的实验练习,把数据结构的概念、理论知识与技术融入到实际应用中,从而加深对本课程的认识和理解,逐步熟悉和掌握结构化程序设计方法,提高编程能力和综合分析能力,并为今后学习面向对象程序设计作一些铺垫。实验练习覆盖了“数据结构”课程教学的各个方面,内容涉及数据结构和算法分析基础、线性表、栈和队列、串、树和二叉树、图,以及查找与内部排序等,全书共16个实验练习、1个实验总结和1个附录实验,如表一所示。
实验1:数据结构和算法分析基础。包括数据结构和算法的计算环境、抽象数据类型的表示和实现、算法和算法分析等实验。通过实验来理解抽象数据类型的特点、定义方法和在C语言环境下实现的方法;掌握算法的主要特征和描述方法;尝试通过具体的算法结构,计算算法的时间复杂度和空间复杂度,并对算法进行定性或定量评价。
实验2:线性表。包括线性表的顺序表示和实现、线性表的链式表示和实现等实验。通过实验,掌握顺序表和链表的存储结构定义;实现基本操作算法的描述和分析;进一步理解实现复杂操作的C语言程序的结构,从而更深入理解结构化程序设计的方法;与此同时,加深理解C语言中函数和结构体的结构、语法和使用方法。
实验3:栈和队列。包括栈、队列和递归算法等实验。通过实验,掌握顺序栈和链式栈、顺序队列和链式队列的存储结构定义;掌握栈和队列基本操作的过程及实现的方法;理解递归算法的思路、使用条件以及设计方法,并且了解由递归算法到非递归算法的转换过程中栈的作用;通过实例,进一步加深对栈和队列特点的理解,并区别这两种结构在解决实际问题时的区别,从而更合理地选择适当的数据结构解决实际运用。
实验4:串。包括串的3种常见的存储结构定义、在具体的定义下串的基本操作和实现。通过这个实验,加深理解串这种常见的数据结构的特点和存储结构定义方法;掌握串的基本操作算法的描述,并根据算法的结构评价算法;理解串操作的实现方法,理解一个合理的存储结构定义对具体操作实现的重要性,并注重提高算法的健壮性,从而能更好理会一个好算法所需要的各种综合因素。
实验5:树和二叉树。包括二叉树及其基本操作、哈夫曼树和哈夫曼编码等实验。通过实验,掌握二叉树的不同存储结构定义,并理会在具体的应用中采用合理的存储结构的思路;理解二叉树的先序、中序及后序三种遍历的递归与非递归算法实现过程,加深理解递归算法的设计思路,体会栈在递归算法中的作用,以及在非递归算法中栈和队列的作用;理解哈夫曼树的特点和存储结构的定义思路、哈夫曼树建立的算法和实现,并在此基础上体验哈夫曼编码的特点和设计过程,弄清实现哈夫曼编码程序的结构,从而加深对C语言中字符串和指针的理解和灵活运用。
实验6:图。包括图的表示和实现、图的应用、贪心算法等实验。通过实验,掌握图的各种存储结构的定义方法,从而更进一步理解如何根据实际问题设计合理的数据结构;掌握图的两种遍历方法,即图的深度优先搜索和广度优先搜索,并根据这两种操作的实现过程确定算法中所需要采用的辅助数据结构;能根据实际问题选择图的类型,并采用合理的存储结构,理解解决最小生成树、拓扑排序、关键路径和最短路径等实际应用的算法描述,并能根据算法写出相应的程序代码。根据贪心算法的核心思想理解贪心算法的特点,并学会设计简单的贪心算法。
实验7:查找与内部排序。包括查找、内部排序等实验。通过实验,掌握查找表的特点,并能根据具体的查找方法定义合理的查找表的存储结构;掌握各种查找表的实现思路,能根据查找思路写出算法的描述,并对算法进行评价;掌握哈希查找的特点和影响哈希查找的因素,从而构造合理的哈希函数、采用适当的解决冲突的方法,加深理解C语言中指向函数的指针的具体应用。通过实验,熟悉各种排序方法的特点,并能根据具体的实现方法定义合理的待排序数据的存储结构;掌握各种排序方法的实现思路,能根据排序思路写出算法的描述,并对相应算法进行时间复杂度和空间复杂度计算;体会各种排序算法在最好情况下和最坏情况下的算法评价,并能根据待排序数据的实际分布,制订相应的排序方法。
实验8:数据结构与算法实验总结。全部实验完成后,要求学生回顾所有实验内容,进行一次系统的概括、评价和总结,以巩固通过实验所了解和掌握的数据结构与算法相关知识和技术。
附录:算法描述绘图工具Visio实验。学会在Visio环境下制作算法的程序流程图和N-S图等。
各个实验练习的难易程度不同,实验练习之间的难度不断增加,循序渐进,学生在实验中遇到困难,还可以搜索更早的实验来帮助解决问题。每个实验完成后,要求学生根据个人感受完成实验总结;师生通过“实验总结”和“教师评价”部分,交流对学科知识、实验内容的理解与体会。
数据结构与算法是计算机科学与技术专业的核心基础课程之一,同时,它也是算法分析与设计、操作系统、软件工程、数据库概论、编译技术、计算机图形学、人机交互等专业基础课和专业课的先行课程。本课程主要以抽象数据类型为主线,研究常用数据结构的逻辑结构、存储结构及其所支持的运算操作;研究能够解决实际问题的经典算法;学习基本的算法分析方法。它为学生后续课程的学习以及进行计算机软件的设计和开发打下良好的基础。
1教学过程中存在的问题
数据结构与算法课程是计算机专业教学的难点。在教学过程中,我们发现学生对这门课不仅感到入门困难,而且难于驾驭,其主要表现有以下几点。
1) 高职高专学生的先导知识学习储备不足。由于高职高专的教学以“理论够用”为教学原则,因此,学生掌握基础理论知识的程度无法与本科院校学生相比。例如,数据结构与算法需要学生具备结构体类型和指针的知识,甚至能够掌握内存模型的运行机制,而对于高职高专学生来说,其先导课程C语言程序设计属于非重点或选学内容。
2) 概念过多,不利于高职高专的学生掌握。本课程涉及的基本结构包括顺序表、树、图,以及查找、排序等算法内容。特别是树和图两项内容包含大量概念和理论,其中许多必须掌握的内容使学生产生畏难情绪。
3) 高职高专学生在实践课中没有养成阅读英文文档的习惯。学习编程的最好方法是阅读和查看MSDN,但高职高专的学生英语底子差,不太愿意阅读英文文档,这影响了实践课的教学效果。
从高职高专院校的教师角度来看,存在以下问题。
1) 高职高专院校的老师的教学模式过于单一,较少传授学生解决现实问题的方法。在数据结构教学过程中,高职教师一般将授课重点放在讲授数据的基本结构上,选择的案例只能用于数据结构算法的验证和说明[1]。这种教学模式对高职学生非常不利,因为,仅从基本结构这个单一的角度进行教学,只能使大多数学生在学习过程 “依葫芦画瓢”,一旦遇到问题就束手无策,乃至产生畏难和厌学情绪。很多学生常常觉得教科书的内容与具体的项目设计相距甚远,给人一种无从下手的感觉。在学完数据结构与算法课程后,学生既不能灵活运用所学知识,也难以实现从数据结构基础知识的掌握到实际应用的飞跃,这与高职院校“实用为主”的教学原则不符,也不利于应用型人才的培养。
2) 高职高专院校的老师的教学手段丰富,但是往往不涉及具体问题的分析,以及基于问题提出对应的解决方法,只是一味地追求直观效果。有些老师甚至根本不讲数据结构的抽象表示,在数据结构算法的处理上也不考虑应用场合,而是直接提供代码给学生。当然,这样做似乎对初学者有一定好处,但无助于学生培养正确的思考方法,另外,它让学生只注重实现程序,而不考虑如何进行算法设计以及怎样选择合适的数据结构来表达自己的算法思想。我们认为,在“够用为度”的教学原则下,教师只能在教学内容上进行适当的删减,而不能仅局限于“简单地教,简单地学”。
3) 对于高职高专院校而言,很多老师不具备完整的教学体系思想,不知道如何处理数据结构、算法和实现代码之间的联系和区别。有些老师对课程内容的理解不够深入,特别是没有把理论与实际应用问题联系起来。这势必造成学生不能理解学习数据结构课程的意义,不能形成对课程内容的整体概念,也不知道学习这门课程有什么用,不知道这门课程在专业体系中的位置。对于高职学生而言,数据结构为什么存在?在项目实践中如何灵活应用?这些问题如果不得到解决,那么在高职院校开设这门课程就变得毫无意义。
2教学改革中的几点建议
对于高职高专院校的学生来说,提高他们的学习兴趣至关重要。虽然高职生的基础知识薄弱、学习动力不足、自信心不强,自我管理以及自我约束力较差,但是,他们思想比较活跃,动手能力和社会适应性较强。因此,他们更需要老师耐心、正确的引导。对此,我们可以从以下几个方面进行改进。
2.1激发学生的学习兴趣
“兴趣是最好的老师”。培养学生的兴趣和维持前期的学习热情,并让学生在以后的项目实践中主动运用本门课程中学习到的知识,这是每个高职教师的责任和义务。我们知道,在这门课程中存在很多经典算法,而每一个经典算法的背后都有一个计算机界的传奇人物[2]。例如KMP算法中的D.E.Knuth,最短路径算法中的Dijkstra,等等,他们每个人都有一个传奇人生,上课时,教师可以通过讲述他们对计算机发展所作的突出贡献,鼓励学生,激发学生的学习热情。而在实践课程中,我们主要采用“换位思考法”,锻炼学生独立编程能力。梁肇新在《编程高手箴言》一书中提到:我就是程序,程序就是我。学生在上实践课时,很多程序细节问题都搞不清楚,这严重挫伤了学生的学习积极性。由于这些编程问题不可能在上课时被一一解答,所以,学生只能通过平时积累和应用,逐步提高自己的动手能力。上这门课时,教师要多鼓励学生把自己想象成“编译器”,不要只是简单地把它作为一个工具,而要把我们的编程工具“人性化”,编程过程只是我们在和一个“法官”聊天而已,而这个法官又无比“公正”。如果把自己想象成“编译器”,在学习语法时就可以很好地进行“换位”思考,知道自己需要什么,如何做才能编译和调试成功,学习兴趣也会随之提高。
2.2选取合适的教学内容
高职院校在开设数据结构与算法课程时,考虑到学校和学生的特殊性,总课时一般安排为64个课时,理论和实践各32个课时。内容多、课时少这对矛盾如何解决?如何在比较短的时间内培养学生独立解决问题的能力?这都是值得研究和探讨的问题[3]。
众所周知,本门课程包括表、树、图3种数据结构,而每一种数据结构又包括3个方面的内容――逻辑结构/存储结构/操作实现;还包括两类典型算法――查找/排序。这么多教学内容不可能在一个学期内完全教授给学生,所以,我们对教学内容进行了适当的删减,以便重点突出。在不影响高职院校教学原则的前提下,我们将教学重点放在线性表结构和通过时间复杂度分析选择合适的数据结构这两部分内容上(如图1所示)。对于非线性结构这部分内容,我们着重
讲解概念,具体用法可以留给学生作为课外作业。这种选择可以使学生养成良好的思维习惯和正确的学习方法,以求达到“运用之妙,存乎一心”。
2.3巩固先导课程的基础
在先导课程C语言程序设计中,学生没有系统地学习结构体和指针类型,也没有掌握动态内存分配的知识,所以,在本门课程教学中必须首先弥补以前的不足,但我们又面临新的问题,即系统学习与学时数不足的矛盾。对此,我们有如下建议:讲解在运行期时程序在内存中的分布区域,以及各个内存区的作用就足够学生理解本课程知识(如图2所示)。图2中模型[4]的讲解适合贯穿整个实践课程的教学过程,把这个模型讲深讲透,让学生彻底掌握,有利于高职学生独立思考和解决问题能力的培养。这个程序内存分布模型可以很好地满足高职院校的教学目标,让学生在具备较强编码和调试能力的同时,又具备解决实际问题的思想和技术。
2.4传统和现代教学手段相结合
高职院校一般硬件设施齐全,教学条件优越,给教师和学生提供了现代化的教学环境。不可否认,现代教学手段具有生动、直观和信息量大等特点,对于提高教学效果有促进作用,例如,多媒体教学课件(PPT课件和Flas等)和丰富的网络资源,等等。从本人多年的教学实践来看,现代媒体对提高某些课程的教学效果作用显著,但对于理论性很强的数据结构等课程而言,只能起到辅助作用。事实上,美国数据结构教学仍以讲授为主[5],所以,传统教育手段对本门课程不可或缺。在本门课程中,讲解三种数据结构的概念和性质时,可以多用PPT等现代教学手段;讲解算法的动态变化时,多用黑板+粉笔头的方式演示其动态变化过程[6-8]。
2.5问题驱动教学法
福州大学吴英杰等老师[9]在该校引入面向问题的教学模式,取得了良好的效果。在高职院校采用该教学模式,选择的问题必须具有代表意义,足够简单而且能够帮助学生快速入门。从图3可知,在传统的教学模式下,教师只是按照“逻辑结构存储结构编程实现”的流程讲解,学生并不能理解数据结构的意义。如果采用问题驱动的教学方法,教师必须按照“问题定义算法设计选择数据结构”的流程讲解,这种讲解方法可以帮助学生很快抓住数据结构的精髓,了解算法与数据结构之间的关系。在教学实践中,我们选择了3个典型问题:最大子序列和问题、二分搜索问题和快速排序问题。选择这3个问题的根本原因在于它们只需要用顺序表或数组就可以实现;第1个问题的引入在于其历史发展过程符合我们的思维习惯,就是一个不断深入理解问题,不断优化的过程;第2个问题的引入在于90%的计算机专家不能在2小时内写出完全正确的二分搜索算法;第3个问题的引入在于快速排序算法的实现只能选择顺序表或数组实现,而不能选择链表来实现。通过上面3个典型算法的实践课,高职学生能够很快地掌握验证和优化程序以及选择合适数据结构实现算法思想等能力。
2.6调整实践内容,提高学生能力
如果实践课只是使用枯燥的控制台程序界面,许多学生很快就会失去学习的兴趣和钻研的动力。实践课应该生动、活泼、有趣,因此,我们在实践课中引入简单游戏开发项目,例如走迷宫和5子棋等游戏。这些游戏都用到了顺序表等简单的数据结构和查找等算法知识,完全满足高职院校的教学要求。在教学实践中,我们一般提供游戏的整体框架代码,要求学生独立完成算法设计和代码实现。我们之所以这样做,一是因为实践课只有32个课时,没必要让学生设计软件的整体框架;二是因为不能让学生产生“程序=软件”的错误思想。
2.7改变考核方式
数据结构与算法课程一般采用最终卷面成绩的考核方式。根据高职院校的教学原则,应加大实践课在最终成绩的比重。通过实践,我们发现阶段性成果
的展示和分阶段打分在教学中有良好的教学效果,通过这种考核方法,在平时即对学生从严要求,高职学生的综合能力得到提高,潜力也能得到充分挖掘。
3结语
作为一所高职院校,我院在数据结构与算法教学改革与实践中取得了一系列丰硕的成果。我院ACM- ICPC代表队在2007、2008、2009年度亚洲区现场赛中曾获得优胜奖,2007、2008年四川省大学生程序设计大赛中曾获得二三等奖。同时,计算机科学与技术系的普通学生的出勤率和及格率得到提升,学习兴趣也有所提高。
数据结构与算法课程尽管难教难学,但如果采用正确有效的教学方法+生动活泼的学习方式+严格管理的考核方式,仍然可以取得良好的效果。
参考文献:
[1] 周泽辉. 浅谈高职学院数据结构课程的算法驱动教学[J]. 科教文汇(中旬刊),2009(3):121-122.
[2] 苏前敏. 计算机科学技术史的独特教育功能探讨[J]. 上海工程技术大学教育研究,2007(1):20-23.
[3] 卢洁,冯家勋. 理工科课程教学整体改革探索[J]. 高等工程教育研究,2009(2):137-139.
[4] 钱能. C++程序设计教程[M]. 2版. 北京:清华大学出版社,2005:145-149.
[5] 严莉,杨宗凯,刘三 . 关于高校教师与网络教学的研究综述[J]. 电化教育研究,2009(4):39-42.
[6] 蔡敏,郑尚志,梁宝华. 数据结构课程教学改革之我见[J]. 计算机教育,2009(4):50-51.
[7] 张桂芬,李海滨. 数据结构实验教学的改革与探索[J]. 高教论坛,2008(3):103-104.
[8] 周玉林,赖鑫生. 数据结构教改中的问题研究与探讨[J]. 上饶师范学院学报,2008(3):84-88.
[9] 吴英杰,王一蕾,王晓东. 面向问题求解的实践教学模式:算法与数据结构实践教学改革[J]. 计算机教育,2007(7):29-31.
Suggestions of Teaching and Learning Data Structures and Algorithms on the College
FAN Jun-qing1, CHEN Wen-fei2, XU Xue-feng3, YU Xin-qiao3, HOU Zong-hao3
(1. School of Computer, China University of Geosciences, Wuhan 430074, China; 2.Department of Computer Science, Wuhan
University, Wuhan 430072, China; 3.Department of Computer Science, Chengdu Neusoft Vocational Institute of Information
一、课程主要特色
哈尔滨工业大学“数据结构与算法”课程经过近30年的建设,逐步形成为一门具有一定特色的核心课程。
1.以抽象数据型为核心的课程体系
早在1989年我们就采用抽象数据型的概念组织教学内容,这在当时是没有的。实践表明,当前广泛流行的面向对象技术就是抽象数据型的丰富和发展。由于采用抽象数据型的概念来组织教学内容,算法的C++描述更为自然。为保持课程体系的先进性,我们还充分吸纳了美国ACM和IEEE/CS联合发表的计算学科课程体系CC2001以及后来我国发表的CCC2002体系新内容,使学生能够及时掌握“数据结构与算法”的最新研究成果。
2.以实践为重点的研究型教学
我们认为,教学不仅要传授给学生知识,更重要的是培养他们分析问题和解决问题的能力,实践教学是培养学生相关能力的重点。实践性教学环节在强化和巩固所学的课程基础理论和基本知识的同时,培养学生综合运用多种数据结构解决实际问题的能力。实现从理论到实践,再从实践到理论的升华。实践性教学的设计思想如下:
理性实践。注意引导学生在所学理论知识指导下进行实践(实验和课程设计),即理性实践,使学生在理论与实践的每次循环中体会到欣喜和成就感,以此提高学习兴趣、增强信心,达到巩固基础知识和知识综合运用能力不断提高的目的。
面向问题求解能力培养的实践教学。面向问题求解能力是学生创新能力培养的基础。我们在实践课程中增加了设计型实验和课程设计,锻炼学生综合运用所学理论知识解决复杂问题的实践能力。
实践教学与科研相结合。课程设计指导教师大都来自科研一线,学生课程设计题目选自指导教师研究方向与本课程有关的部分。使学生提前受到科学研究方法的熏陶,训练提高了学生查阅资料和文献的能力,也锻炼了学生科技论文写作的能力。
3.以网络和多媒体为基础的数字化教学
以多媒体和课程网站为中心构建立体式的现代化教学平台,利用现代化教学手段,通过多媒体和网络教学促进师生的交流,提高师生间的互动。其中,多媒体课件丰富了课堂内容,增强了动态演示效果;学习辅导网站,为学生提供全方位的学习辅导支持,包括教学大纲、学习指导、电子教案、在线测试、学生论坛等。在教学过程中,我们也始终注意对学生主动探索能力的激发,采用多种辅助教学手段,如在辅助教学网站上不断引入课程相关的新内容并以讨论的形式激发探索,制作算法演示系统以及网上习题库等。这些内容可以帮助学生形象地理解各种基本算法,帮助学生认识课程前沿内容。
另外,为提高实验效果,在授课过程中有意识地将教学内容和实验内容有机结合,并配有实验教学辅助网站,指导并监控学生完成整个实验过程。
4.以教学梯队为主线的师资队伍建设
我们建立了由课程负责人、主讲教师、辅导教师和实验指导教师组成的教学梯队。对青年教师的培养采取以老带新,由经验丰富的教师带新入门的年轻教师。有计划、有目的地培养中青年教师。通过教学实践、实验教学的训练以及定期组织教学研究讨论,使青年教师的教学态度、教学水平和教学方法得到提高。
二、课程建设具体实施办法
1.教学队伍的建设
建立了由课程负责人、主讲教师、辅导教师和实验指导教师组成的教学梯队。逐步形成一支以主讲教授负责、结构合理、人员稳定、教学水平高、教学效果好的教师梯队。
课程组还让年轻教师通过科研的实际锻炼提高自己的研究能力,扩充知识面。许多教学实例都来自于第一线的科研项目。科研和教学的有机结合,有利于提高授课内容的先进性,也有利于锻炼年轻教师的创造性和责任感。我们已建立起一支强有力的教学梯队,形成了以高素质教师为骨干力量的教师队伍。
2.教学内容的组织
在教学内容组织方面,我们根据学科发展迅速的特点,逐步地、有计划地对教学内容进行了调整,删减了必要性不大、陈旧过时的内容,逐步增加了反映学科发展趋势的新内容,保持了教学内容的先进性和科学性,同时还充分考虑了与其他课程的衔接问题。
3.教学方法与教学手段
在教学方法和手段改革上,我们以多媒体技术和网络技术为依托,采用现代教学方法和实现手段,制作了高质量的多媒体课件、算法动态演示系统和教学网站。
处理好传授知识和培养能力的关系。课程教学既强调基本理论、基本知识的传授,同时更注意加强学生的实践能力和创新能力的培养。
4.多元化考核方法
改革了“一次定论”的判分制度,考试以学生完成日常作业和实验环节为必要条件,期末考试采用笔试方式。成绩评定由三部分组成:期末考试占总成绩的70%;平时作业占总成绩的10%;实验能力占总成绩的20%。课程设计的考核形式采用答辩方式,锻炼了学生的表达能力和做学术报告能力。
5.实践教学
在实践环节教学方面,设置了验证型、设计型和综合型三个层次的实验内容,分别在课程实验和课程设计中进行。课程组的教师都在实践环节中亲临指导,通过实验室的环境与合理的实验题目引导学生积极主动地学习,锻炼学生的动手能力、创新能力和表达能力。成绩根据预习、表现、报告、答辩等方式综合打分。为加强对学生的个性化指导,我们为每15名学生配备一名辅导教师或实验指导教师。
6.教学管理
我们建立一套完善的教学质量监控体系,从课前、课中和课后等教学环节进行全方位的质量监控。课前,新任教师在开课前必须试讲,合格后方可上台授课。课程组组织定期和不定期的具体备课,研究教学内容和教学方法。在上课过程中,对每一位教师做到100%听课,并对教学过程中存在的具体问题及时进行纠正。我们还重点检查实验教学,保证指导到位;课后,重点监督答疑、作业批改等环节。根据各个教学环节,对教师进行教学质量的综合评定。每位教师的教学质量直接影响到他的工作量计算、岗位聘任以及下一轮的教学任务分配等关键问题。因此,在教学质量监控体系下,每位教师教学态度认真,教学水平不断提高。
1 引言
课程设计是课堂理论教学的延伸和补充。作为一门独立的课程,它应该完成如下基本目标:应能够完成理论与实践的结合,应能够锻炼学生的设计创新能力、分析和解决问题的能力。
数据结构与算法课程是计算机科学与技术专业以及相关专业的一门专业基础课程,同时它也是计算机科学与技术专业课程体系中的核心课程之一,它在计算机科学与技术专业的课程体系,特别是软件系列课程体系中处于承上启下、联系左右的中心地位。大量的实践表明,是否学好数据结构与算法课程对于能否学好计算机本科课程有着相当重要的作用,同时也对后续的工作和研究有着深远的影响。
现今,各大学的数据结构与算法课程和教材的内容都主要集中在“基本数据结构的阐述和分析、基本数据结构的应用、典型基本算法的适当渗透”这三个方面。其中,前两部分是重点,并占据了较多的篇幅,而这些内容的教与学离不开大量的实践,所以在数据结构与算法课程教学中经常会有大量的课程实验作为辅助。
通过进一步的深入分析可以看出,上述基本知识的学习并不是最终目标,而是为到达最终目标打下的基础。显然,从计算机科学与技术专业的知识体系可以看出:如图1所示,学习数据结构与算法更深层次的目标是能够针对实际问题来选择、扩展甚至是设计全新的数据结构,然后设计相应的存储结构并加以实现,从而最终完成问题的求解。可以看出,这一过程是一个融会贯通的过程,是不能通过课程实验完成的,也不可能在课堂教学中就可以建立完整意识的,所以在课程之后需要进行课程设计。
为此,数据结构与算法课程设计应能达到如下基本目标:培养学生应用数据结构基本知识来分析问题、解决问题的综合能力;帮助学生建立计算机问题求解的全局意识,主要是通过认识数据结构在问题求解中的地位来完成全局认识的建立(这一全局认识如图1所示);训练学生从系统的、规范的观点来进行计算机问题的分析、设计、编码、测试等。
上面分析得出的数据结构与算法的课程设计目标是符合一般的课程设计规律的。但数据结构与算法课程具有自身的、明显区别于其他课程的地方,再结合计算机专业的特点,就决定了还需要分析并建立适合数据结构与算法课程设计特点的教学模式。所以本文在第2节就数据结构与算法课程设计和其他课程的课程设计进行了对比分析,在第3节提出了一种基于问题驱动的教学模式,并就其中的关键部分给出了详细的描述。
2数据结构课程设计的特点分析
任何事物都是一般性和特殊性的统一,数据结构与算法课程设计也是一样的。和许多其他课程的课程设计一样,它有着课程设计的共性,也有自身的特性。经过和其他课程的课程设计的对比,作者认为数据结构与算法的课程设计主要具有如下特殊性。
2.1不具有明显的整体性
这是由数据结构与算法课程本身的特点决定的。由于该课程的核心内容主要集中于对各种数据结构的认识上,虽然各种数据结构之间总是存在许多内在的联系,但总的来说还是自成体系、较为独立的。
就这一点而言,数据结构与算法课程就和其他许多课程存在不同,也就使得数据结构与算法课程设计具有相应的特点。比如计算机组成原理的课程设计,可以通过做一个完整的、简化的计算机硬件系统(包括的简化的存储器、控制器、运算器等部件)来完成课程内容的全面训练,并让学生建立对计算机组成的整体认识。机械原理的课程设计可以是一个简单的机械系统的设计,完成对机械原理各部分内容的综合训练。而对于数据结构与算法的课程设计来说,几乎不可能构造一个题目把所有的数据结构都包含进去。实际上这样做是毫无意义的,因为数据结构本身就是不断扩展的,在学习、掌握基本数据结构的基础上能够对知识加以扩展并灵活运用才是真正重要的。
所以在数据结构与算法的课程设计中,应强调问题求解能力的培养,而不像其他课程的课程设计那样来强调综合设计能力。
2.2课程内容具有很强的可伸缩性
从发展状况来看,数据结构与算法的发展是极其迅速的,不断地有新的数据结构和新的算法出现,而且针对不同的问题,数据结构与算法可以做出非常灵活的调整。在这一点上它和许多其他课程不同,比如操作系统中可能会不断出现各种各样的调度算法,但都集中在进程管理中,并总归结于资源管理这一基本框架下,只要冯・诺伊曼体系结构不变,操作系统的资源管理框架就不会改变。而数据结构就不同,如就树结构而言,二元树虽然在概念上较为规整,但在实际问题中,大多都采用树结构的变形,如B树以及其他新型变形等,似乎两者都可成为教学的重点。
正是因为数据结构与算法的可收缩性,培养针对问题的数据结构设计能力才是最重要的。
2.3具有极其广泛的渗透性
计算机问题领域包括许多其他行业的问题,如经济领域问题,只要涉及到对数据的组织与处理,都能或多或少地找到数据结构的用武之地,所以培养依托数据结构完成各类问题求解的“嗅觉”是十分必要的。
总的来说,基于数据结构与算法课程的特点,建立起与之相匹配的课程设计教学模式,这样才能更好地完成教学。
3基于问题驱动的课程设计教学模式
在以上分析基础上,如图2所示,本文提出一种基于问题驱动的课程设计教学模式。
3.1问题来源
数据结构与算法课程设计的问题来源(即教学内容)主要包括:基本数据结构在解决实际问题中的应用;基本的算法策略在解决实际问题的应用;新兴数据结构的相关问题;新兴算法的相关问题及实践;经典问题的经典算法;典型系统的计算机模拟;需自行设计数据结构和算法来解决的实际问题。
3.2问题描述
在问题的描述上,侧重于用半自然语言进行描述。完全的形式化描述将减少问题分析能力的培养力度,完全的自然语言描述有包含太少的启发信息。
一般来说,要求问题的描述必须能够清晰地说明问题的含义和目标,并就采用的数据结构适当地给出启发,其中,也可以设计一些题目故意将问题的目标隐去,加强对学生问题定义能力的培养。
3.3问题求解的迭代性
问题求解是不能够一蹴而就的,一开始设计(选取)的数据结构与算法往往存在这样或那样的问题,建立逐步求精、多次迭代的问题求解思维是必要的。
为此,我们需要在学生的课程设计过程中,鼓励学生对其解决方案进行理论分析和实验分析,鼓励学生大胆提出优化方案,鼓励其积极主动的创新意识。
3.4结论形成
最终的结论(体现为课程设计报告)应以数据结构的描述为核心,并集中体现如何针对问题来完成数据结构的设计与优化。
其中,数据结构的描述应以抽象数据型(ADT)为基本手段,并在抽象数据型的基础上,引导学生深刻理解和掌握数据的逻辑结构、性质、特点、基本操作和存储结构的特点、实现和优化,并引导学生在实际应用中有意识地去为实际问题选择恰当的存储表示。
结果分析应采用理论分析和实验分析并重的方式,应适当加大实验分析的力度,使得学生能在分析结果的基础上形成总结并产生启发,最终能形成问题求解过程的全局意识。
3.5结果考核
鼓励学生选择需要设计新型数据结构(至少需要对已有数据结构作出修正)的题目,而不仅仅是实现一个定义明确的数据结构;鼓励优化方案的提出、分析和验证;鼓励学生扩展知识体系,并建立问题求解的修养;鼓励创新意识和主动学习意识的培养。
4 结束语
针对数据结构与算法课程设计的一般性和特殊性分析,本文在提出该课程设计的基本要求后,更提出了适合于数据结构与算法课程设计的“以问题求解为核心”的教学模式。近年来,经过对计算机科学与技术专业本科生的多次实践,可以看出,这一模式可以取得很好的教学效果。
参考文献
1 耿蕊,李敬有,邓文新.关于计算机基础课课程设计的研究.高师理科学刊,2005,5
中图分类号:TP312 文献标识码:A
教育部于2013年,提出一项重大的改革,即计划将大约600所地方性高等本科院校转型为应用型本科院校,2014年被列入教育部当年工作要点[1]。在高等院校向应用型本科转型的形势下,高校教学面临着新的机遇和挑战。商洛学院作为陕西省首批应用转型试点高校,实现毕业时与社会、企业零距离对接,完成高等学校为社会输送有用人才的最终目标[2]。
算法与数据结构课程是计算机相关专业的专业基础课程,是设计各种应用软件的重要基础,是我校电子信息科学与技术专业课程体系中的核心专业课程。本文主要针对当前教学过程的问题,进行探讨研究,提出一种新的教学模式,达到教与学的有机结合[3]。
一、课程教学改革的必要性与紧迫性
算法与数据结构课程主要涵盖数据结构的阐述分析、应用以及经典算法的应用,主体内容比较抽象,难以直观描述,掌握相对困难。此外,电子信息科学与技术专业的学生计算机基础知识薄弱,电子和计算机专业之间培养差异,导致电子信息科学与技术专业学生学习更加困难。随着互联网行业的迅猛发展,网络教学资源的日渐丰富以及算法与数据结构课程地位的愈加重要,传统教学模式中的问题日益突出[4]。
(一)数据结构课程自身特点
(1)高度抽象化,需要扎实的数理逻辑、图论、高等数学、拓扑几何、离散数学和数值分析等理论基础;(2)内容涵盖面广泛丰富。(3)隐含的技术方法丰富,各部分问题解决方式种类多样、没有固定解法、灵活性强。
(二)应用转型下发展算法与数据结构课程的教学目标
(1)重视算法与数据结构基础理论知识学习,理解数据逻辑、数据存储及数据运算等基本概念术语;(2)从实际问题出发,培养学生运用算法与数据结构的基本理论知识分析解决实际问题的能力;(3)重视学生实践动手能力和工程项目思想的培养。
二、传统教学过程中现存问题
根据长期从事算法与数据结构的教学过程,发现当前算法与数据结构教学中主要存在以下一些问题。
(一)难理解:本课程需要较高的逻辑思维和抽象思维能力,学生联系实际比较困难这一问题始终萦绕在整个教学过程中。
(二)难把控:电子信息科学与技术专业本科二年级学生,其计算机基础、建模能力、软件工程的思想薄弱。
(三)难实现:体现在遇到问题不知如何数据结构类型;面对具体算法不清楚如何进行优化;书本上的程序不能直接运行,学生自主学习有一定困难[5]。
(四)难应用:数据结构相关实验的课程设计主要采用高级程序语言(如C,C++)等来编写,我校电科专业学生对该程序语言的掌握程度直接影响到数据结构课程的实际应用情况。
三、教学模式改革与探索
针对现有传统教学中存在的问题,为了提高学生算法与数据结构应用能力,需完善并加强实践教学内容。
(一)调整课程体系
当前教学是依据传统的知识理论体系顺序授课:然而当前应用转型环境下这种模式已难以适应。根据学生学习认知一般规律及我校电子信息科学与技术专业自身特点,在传统教学基础上进一步优化课程培养体系,针对每一知识点配备相应实践项目,将理论与实践有机结合。
(二)优化教学手段
传统课堂教学主要以教师粉笔板书讲授为主,不能用动态直观的方式讲解抽象知识,难以激发学生学习热情,无法达到课题教学目的。
1.将微课引入教学中
借助微课这一新兴教学模式,将算法与数据结构课程重点、难点设计开发成网络视频资源,供学生课后自主学习。我们将算法与数据结构中每一个知识点的内容,制作成微教案、微视频、微练习、微点评、微互动等传至课程网络中心。
2.将案例驱动引入教学中
案例驱动的算法与数据结构教学方法,是将教学案例引入到课程教学过程中。教师通过一个完整案例的分析解决,借助板书、多媒体等手段与学生互动,达到培养学生发现问题、分析问题、解决问题的能力。
3.加强课外创新实践活动
算法与数据结构课程需要增加学生的课外创新实践活动。具体通过以下方式开展:(1)组建算法和数据结构学习创新小组,定期举行学习经验研讨交流活动,分享实际设计过程的困难、解决途径和最新成果;(2)定期组织以算法为核心竞赛活动,(3)鼓励学生申报研究学习与科技创新性实验项目,组织参加省市级或国家级各类学科竞赛。
3.改革课程考核模式
传统实验课的课程,实验动手部分只占10%,很多学生把重点放在报告书写上,为适应应用转型发展,加强学生实践能力,课程考核提出以下改革方案:(1)平时(考勤+开卷随堂测试+课堂表现),占学期总成绩的10%;(2)课程上机实验(源程序+实验报告)30%;(3)期末卷面成绩60%;(4)鼓钛生到相关优秀企业进行培训实习
四、结语
针对当前电子信息科学与技术专业算法与数据结构教学模式中培养目标及存在的主要问题,在转向应用型本科院校新形势下,为培养创新型、应用型人才,提高学生逻辑思维、编程运算等能力,本文主要从课程体系调整、教学手段优化、创新实践教学加强、考核模式改革共4个方面都出发,以提高算法和数据结构应用能力为教学目标,结合工程项目与市场实际需求,指导并加强实践教学。
参考文献:
[1]陶影,张斌.数据结构实验教学应重视算法设计与分析能力的培养[J].实验室研究与探索,2008,12:119-122.
[2]张铭,赵海燕,王腾蛟,宋国杰,高军.北京大学“数据结构与算法”教学设计[J].计算机教育,2008,20:5-11.
[3]唐剑梅,谭平.《数据结构与算法设计实训》课程教学研究[J].软件导刊,2016,01:193-194.
中图分类号:G642.0 文献标识码:A 文章编号:1002-4107(2014)12-0027-02
一、数据结构与算法教学存在的问题
倪光南院士指出,中国如果能发挥人才优势,不久就可成为仅次于美国的世界第二软件服务大国[1]。高素质的软件人才是我们成为软件大国的必要条件。目前国内软件设计相关专业毕业的工科生多数仅仅熟悉了一两项软件技术,存在专业基础不扎实、分析和解决问题的能力薄弱、动手能力不强等问题,导致了软件行业存在需求大于合格应聘者的尴尬现象。这一现象的根本原因在于学生在校期间没有夯实好专业“内功”,像数据结构与算法这样的专业基础课程没有取得良好学习效果。国内外相关专业在进行本课程教学中存在的主要问题如下。
(一)教学内容过于抽象
本课程涉及的知识面比较广,各章节的知识点有相互关联的逻辑关系,教学计划的制定多以理论知识点的讲解为主,选取的教材多数抽象难懂,缺少具体的实践案例的讲解,学生只能停留在理解层面,无法学以致用。
(二)教学模式僵化
老师课堂讲授侧重概念、理论,导致学生只能从理论上掌握基本的数据结构及其相关算法,但难以通过计算机编程语言(如:C/C++)实践相关理论,更不会用所学知识解决具体问题。很多学生在学习该课程的时候不知道在实际中如何应用各种数据结构和算法,仅仅学会一些“死”的理论来应对考试。
(三)实验教学环节薄弱
学生在实验的过程中,只停留在书本上,模仿书上的代码,存在理论脱离实际、实践环节薄弱问题,学生往往产生“学而无用”的思想。
(四)教学效果不佳
由于上述几个问题,学生只会机械地实践,没有领悟专业知识背后的思想,导致学生不清楚学习本课程的价值何在,分析问题、解决问题以及编程能力都没有从根本上得到培养,从而导致专业素质未得到提升。同时,学生的团队合作意识、良好的编码习惯等工程化思想未得到培养。
二、CDIO工程教育模式的特点
2000年10月,MIT联合瑞典的三所大学成立了以Edward Carwley教授为首的跨国高等工程教育改革研究组,创立了工程教育模型――CDIO(Conceive构思、Design设计、Implement实现、Operate运行),是“做中学”和“基于项目教育和学习”的集中体现[2]。
针对工程师的培养,CDIO提出的根本出发点就是为了设计造福于人类的软件产品,所以学生必须能发挥一个工程师的作用。表1显示了在企业/社会环境下,工程师“构思―设计―实施―运行”系统所必需的知识、技术及态度的组成模块。对于技术工作感兴趣的成熟的个体应具备个人和专业的技能,这是培养实践能力的核心。为了开发复杂的增值工程系统,学生应掌握最基本的技术知识和推理能力。为了在当今团队环境下工作,学生一定要发展团队合作和沟通的人际交往能力。最后,为了能够在企业/社会背景下创造和运行产品,一个工科生必须理解“构思―设计―实施―运行”系统的相关内容。
表1 工程师“构思―设计―实施―运行”系统所必需的能力模块
三、数据结构与算法课程教学改革的措施
教师培养学生实施软件项目都是围绕“构思―设计―实施―运行”这一背景进行的。表2显示了软件工程师参与工程设计的过程与CDIO之间是有对应关系的,可以看出,CDIO的理念是渗透在软件工程过程的每一个阶段。因此,基于CDIO的教育模式以及软件工程师进行“构思―设计―实施―运行”系统所必需的能力模块,提出了数据结构与算法教学改革的具体实施措施。
表2 软件工程师工程设计过程与CDIO之间的关系
(一)“构思”
教师授课时要明确培养“软件卓越工程师”的目标,而不是“软件外包程序员”,所以要强调数据结构与算法作为专业基础的重要性,可以让学生修炼以不变应对不断更新的软件技术的“内功”。在学习每个抽象的知识点前,一定要提出为什么要学习它,能解决什么问题。培养学生在软件工程设计过程中,能发现、分析和澄清一个问题的能力。
(二)“设计”
主要培养学生在工程设计过程中“提出―选择―实证”方案的能力,是软件工程师最重要的技能。课堂上多采用启发式教育方式,让学生自己提出解决问题的方案,如:拟采用的数据结构模型以及相对应的算法。然后通过算法的时间复杂度和空间复杂度进行事前比较分析,选择最优方案。最后,将要解决的问题通过“分而治之”的思想划分为子模块,并应用决定使用的方案,进行实证分析,看是否可以解决原问题。这个阶段也是培养学生逻辑推理和解决问题能力的阶段。
(三)“编码”
主要培养学生将分析设计的方案及相关抽象的理论知识用具体编程语言实现的能力。根据CDIO提出的“做中学”的工程教育理念,将授课中每一个抽象的理论知识渗透到具有实际意义的案例中,升华技术知识的运用。从而,使学生的学习更有效,能够学以致用,培养其实际运用的能力。除了专业知识和个人技能的培养,教师在案例教学和实践教学过程中,更要注重培养学生养成良好的编程习惯,形成良好的、符合软件设计规范的编程风格,从而使学生设计的数据结构与算法容易理解,具有较强的可读性,这也是一名优秀的软件工程师与人交流的“代码语言”,也是其人际交往能力的组成部分。
为了使学生通过本课程的学习,能够设计出时间上更高效、空间上更经济的程序,通过竞赛为载体进行教学,鼓励学生参加学院、学校组织的编程竞赛、ACM-ICPC省级大学生程序设计竞赛以及全国软件专业人才设计与开发大赛、软件大赛等。这些程序设计比赛解决问题的方式是“构思―设计―实施―运行”的模式,也需要学生具备工程师所必需的能力模块。通过这些竞赛平台,丰富了实践教学的形式,让学生拥有“学以致用”的平台,使学生的学习更有针对性,提高学生学习的主动性和参与性。通过“做中学”的方式有效地夯实专业基础的同时,提升其分析和解决问题的能力,实践动手能力也得到极大加强。
(四)“测试与维护”
培养学生在软件工程实践活动中创造、运行软件产品的能力。在教学中,将学生组成项目小组,并且根据学生的特点分配不同角色,各自经过“CDI”三个阶段,一起通过团队协作完成一个软件系统的开发。培养学生在设计、编写相关数据结构和算法的时候,本着“高内聚,低耦合”的思想,设计合理的接口,便于最终系统整合。同时,强调学生设计的程序要有通用性和灵活性,便于后期的修改和维护。
四、教学改革效果
哈尔滨理工大学软件学院将CDIO的工程教育理念应用到数据结构与算法的教学中,在教学的各个环节实施相应措施,培养学生“构思―设计―实施―运行”系统所必需的能力。图1显示了在数据结构与算法课程中实施CDIO教育模式两个年级学生期末考试成绩的对比。其中,平滑折线代表11级采用传统教学模式的数据结构与算法课程的成绩(67人,平均值=53.4),点划线代表12级实施CDIO教育模式后的数据结构与算法课程的成绩(65人,平均值=66.6)。可以看出采用CDIO模式后,学生整体成绩有明显幅度的提高。
由此,可以证明在数据结构与算法教学中实施CDIO工程教育模式是非常有效的。下一步将继续研究通过该模式的指导有效提高学生的工程实践能力,培养符合企业需求的软件人才。
图1 实施CDIO教育模式前后学生数据结构与算法课程成绩的对比
参考文献:
[1]靳晓燕.中国有望不久成第二软件大国[N].深圳特区
报,2013-11-17.
国内多数高校在数据结构与算法的教学中依然采用传统的教学模式,一般存在以下一些问题。
第一,师资方面。教师普遍具有高学历及较强的科研能力,所以课堂上的讲授以理论知识为基础,学科发展为导向,追求专业知识的完备性,不问软件行业的需求。
第二,讲授方法。教师在授课过程中容易只专专注于自顾自地讲解教材上的抽象的数据结构以及算法思想,不顾及学生的接受程度和融入课堂的积极性,更忽视学生课后学以致用的实践能力的培养,从而陷入“教师讲,学生被动接受”,甚至是“教师讲,学生睡”的填鸭式教学误区[1]。
第三,人才培养。缺乏与软件产业界的联系,依然把讲授理论放在首位,忽视工程实践性和应用环节,不利于学生对课程内容的掌握和工程实践能力的培养。
第四,教材内容。内容偏向理论,更新缓慢,由于内容较抽象,学生阅读后,通常只能停留在理解层面,难以付诸工程实践。
第五,实验环节。相对薄弱,通常实验的目的为验证书上的理论知识,缺乏创新能力和综合分析、解决问题能力的培养。
第六,素质培养。本门课程涉及的内容比较多,课上不可能涵盖所有知识点。学生由于惰性,多数只是掌握书本理论,机械地实践后,不再更多地领悟专业知识背后的思想。同时,缺乏团队合作意识,不能及时分享学习心得,导致专业素质提高的缓慢。
二CDIO工程教育模式在数据结构与算法中的实施方法
针对这样的情况,哈尔滨理工大学软件学院从2007年就开始研究CDIO教学模式的相关理论,在数据结构与算法的教学中取得了初步的研究成果。“CDIO”是构思(Conceive)、设计(Design)、实施(Implement)、运行(Operate)4个英文单词的首字母缩写,它是“做中学”原则和“基于项目的教育学习”的集中体现,是当今国际高等工程教育的一种创新模式[2]。我们学院CDIO工程化的教学理念的具体践行方法如下。
1建设具备高水平工程化素质的教师队伍
注重教师自身工程素质的提高,使其能够胜任CDIO课程体系的教育模式[3]。完善与国内外著名企业开展师资培训与交流合作的机制,一方面选派专职教师到企业研修,丰富专业教师的工程实践经历和经验,获取最新的技术信息,保证学生学以致用。另一方面建设由企业高级工程技术人员组成的兼职教师队伍,解决教师队伍工程实践经验薄弱的问题,提高工程教育教师队伍的整体素质。
2以培养软件卓越工程师为目标
基于CDIO的理念,我院提出“基于校企合作"2+1+1"模式软件卓越工程师教育培养的研究与实践”。面向软件行业,面向未来软件工程的需求和对未来软件工程师的素质要求,培养造就一大批能够适应和支撑软件产业发展、实践能力强、创新能力强、具有追求卓越的精神和态度、具有国际竞争力的高质量软件卓越工程师,建立社会主义市场经济条件下的现代高等工程教育体系。
3以学以致用为导向
学院每门专业课程的设置都是为了更好地培养软件卓越工程师。软件行业素有更新快的特点,而数据结构与算法这门课程是未来软件工程师以不变应对日新月异软件技术的内功。在教学中强调课程的重要性,在学习每一部分内容前,首先明确学习目标,告诉学生在什么地方应用,让同学们带着目的、本着学以致用的原则来汲取知识,减少学生学习中存在的迷茫,切实提高学生分析和解决实际问题的能力。
4以案例为中心的教学
为了切实提高学生专业学习的兴趣和解决实际问题的能力,依据CDIO工程化模式提出的“做中学”和“以案例为导向”的教学方法,数据结构与算法课程本身具有抽象难于理解的特点,结合应用相应理论的有实际意义的案例进行教学,使学生能够有目标地学习和实践,更好地掌握、完善和运用理论知识。数据结构与算法相关知识点及案例设置如下表1所示。
5以实战平台为驱动力实践教学
鼓励学生参加软件编程竞赛,激发学生的强烈的求知欲和自我学习兴趣。通过各种级别的比赛,丰富了实践教学的形式,让学生可以有针对性地学习,提高了学生的参与性和主动性。我们鼓励学生参加校、省级ACM比赛、全国软件专业人才设计与开发大赛软件大赛和全国大学生ITAT程序设计大赛等比赛。通过这些实战比赛,有效地提高了学生的工程实践能力,取得了很好的效果。本院学生在过去的三年里,在相关比赛中已经取得非常优异的成绩。通过比赛获得证书的同学,编程能力会有超出常人的进步,增加了他们就业的砝码,大赛获奖同学现在有的在百度、腾讯、华为等大公司工作,很好地适应了工作环境。我们学院这两年也组织了两届ACM程序设计大赛,通过大赛向广大同学宣传了软件设计比赛和相关数据结构与算法的知识,提高了他们学习这门课程的热情,更好地走上软件卓越工程师之路。在实验教学环节中,除了安排综合案例的设计之外,我们也从竞赛的试题中选择适合学生设计的题目,提高他们解决实际问题的能力,有效地夯实了他们的基本功。
6提高软件工程专业素质
首先,我们注重培养学生良好的软件开发习惯。在相关数据结构与算法的实施过程中,要养成加注释、“见名知意”、代码的可读性等良好习惯。其次,注重软件工程思想的培养,很重要的一个思想就是“分而治之”,问题定义、功能划分、数据结构选取、算法设计、编码和测试基本解决软件设计问题的工程化思想要时刻牢记。同时,还要培养学生的团队意识,让大家懂得分享知识的重要性,课下相互讨论,弥补思路上的盲点。我们为学生建立了网上的QQ群,如软件学院ACMer、哈理工大学软件设计群等。这些平台的搭建使学生更好地交流,培养了他们与人沟通的能力。最后,最重要的一点就是激发学生主动获取知识的求知欲,最重要的是我们用CDIO教育理念和培养软件卓越工程为目标完成教学之后,学生痴迷于键盘和鼠标,真正获取了能够捕食的“渔”和“猎枪”———工程实践的能力。
三教学效果
变被动学习为主动学习,提高了学生的参与度和主动性,明确了学习动机,学习效率大幅度提高。学生在课堂上积极主动地思考,课下能够主动找老师提出自己的设计方案,同老师讨论案例问题的优化思路。能够在老师的指导下,参与到实战性的程序竞赛中,把学到的数据结构与算法的知识应用到其中。通过2009和2010级两届学生的培养,使他们夯实了成为软件卓越工程师的基本功,为后续专业方向课程(如:J2EE、NET、嵌入式、物联网等)的开设打下坚实的基础,学生们也可以更快地在掌握相关方向,设计出相应软件。在CDIO工程化的教育理念下,学生的主观创新能力得到充分提高。在创新实验设计中有的同学将案例“旅游信息导航系统”拓展为“智能旅游一站式服务系统”,拓展了目前软件的功能,有很好的应用前景。
参考文献
中图分类号:G642文献标识码:B
1引言
实施网络教育精品课程建设对于促进优质网络教育资源的建设和共享,减少低层次重复开发,促进网络教学改革和创新,提升网络教育的社会地位等都具有十分重要的意义。2007年4月,教育部颁发了《关于2007年度国家精品课程申报工作的通知》(教高厅[2007]25 号),把网络教育精品课程纳入到国家精品课程建设体系。网络教育精品课程是具有一流的教师队伍、一流的教学内容、一流的教学方法、一流的资源和教材、一流的教学管理和支持服务的高水平网络课程。因此,网络精品课程的建设是“高等学校教学质量和教学改革工程”重要内容之一。本文针对网络教育的特殊性,从网络资源建设、师资队伍建设、教学和学习活动设计以及网络服务支持等几方面,介绍了国家级网络教育精品课程“数据结构与算法设计”的建设与实践。
2针对网络教育的特殊性,构建资源丰富的网络教学平台
网络教育是指远程网络教育。这种教育不同于一般的在校面授教育,其教育的对象不像全日制学生那样有大块的学习时间,而是利用零散的、业余的时间学习,而且学生的基础也不一样。他们更多的是为了学习实用的知识帮助他们解决工作中的问题。在学习的过程中还会有工作和学习的矛盾、家庭负担等影响因素。因此,远程教育课程教学设计的总体原则应该是,所教授知识有充分的实用价值和可实践性,适合于在职从业人员业余学习和终身学习,满足远程教育对象最紧迫的工作和应用需要。而在教学内容的选取上,则应采用教学与应用相结合的方式,将课程的基础性的理论与综合应用知识相结合,优化课程知识内容体系,达到应用型人才培养目标。
远程教育师生时空分离导致远程学习中学与教的时空分离,这是远程教育的重要特征之一。因此,要构建资源丰富的网络教学平台,将教学内容与学习资源整合起来,以实现远程教育。
北京理工大学现代远程教育学院成立于2000年,是经教育部2000年批准的15所现代远程教育试点高校之一。在发展和建设中,逐步形成了以人为本的教育理念。在实施远程教育过程中,加强对教学过程管理,并不断完善教育质量管理体系。“数据结构与算法设计”课程作为计算机基础教学基本要求的第三层次课程,2003年开始了网络教学和网络辅助教学。
“数据结构与算法设计”网络教学平台充分利用了多种媒体技术,构建了多种媒体资源优势互补的、支撑网络教学的立体化资源,风格独特,特色鲜明,实现了以“学生为中心,教师为主导”的教育思想。在选取教学内容和学习资源的建设时依据以下四个原则:第一,以学生为中心的原则,按照业余学习特点进行教学设计;第二,围绕网络教育应用型人才培养目标,选择适合远程教育对象学习的教学内容组织教学;第三,紧扣时代和学科最前沿,为学生提供多种形式的学习资源的原则;第四,紧扣网络教育特点和要求,选择适当课程授课方式。在学习资源建设方面,根据学生的学习条件和自身基础的差异性,采用多种媒体(文字、音频、视频、模拟、仿真、动画等)技术的应用呈现课程内容,为学生自主学习提供最大方便。我们编写并开发了该课程的教材、实验指导书、视频、电子教案、流媒体课件、Flas、实验案例、素材库、网络课件等,形成了丰富的立体化的教学资源,并将这些资源放在教学网站上供教师和学生浏览。在媒体设计上一体化,突出各自优势、形成优势互补。除具备课程所需的课件外,还设置了诸如实时交互、网上答疑、远程网站、自学导读、电子阅览等网络教育可以实现的现代教学形式。
课程的教学平台是立体化的,在设计上既体现了基于建构主义理论的教师主导型,引领型的价值理念,又给予学生自主选择、自主讨论、自我测试的平台空间,实现了教师主导引领和学生自主选择的统一。通过导学,学生可以快速掌握网络学习的方法,利用教学平台进行师生交互。同时,我们还创建了一个完整的教学支持服务体系,可以合理、有效地组织每个教学环节,注重教学过程和教学质量的跟踪管理,以确保应有的教学成效,培养了学生网络环境下的自主学习能力与实践能力,达到培养优秀应用型人才的目标。
3针对网络教育的特点,建设师资队伍
在网络教育中,师生分离的特征决定了师生之间的交流不方便、不及时,教师从学生身上获得的信息很少,相反也是如此。这就从客观上决定了网络教学中的师生需要建立更多同步或异步的交流途径,以弥补师生交互的缺失,而教师则需要投入大量的时间和精力与学生进行交流,如解答学生疑问,指导学习过程,组织网上教学活动等。
在现代远程教育中,教师通常由学校教师兼任,教师的学校教学和网络教学之间经常发生矛盾。为了解决这些问题,我们在师资队伍建设时注意了各种不同类型人员的配备,包括了主讲教师、教学辅导教师、班主任以及网络维护技术人员。其中,主讲教师主要负责课程的学术质量,包括:制定课程目标,设计教学大纲,组织教学内容,完成教学设计,录制课程讲解,设计考试试题等;辅导教师主要负责教学过程的指导与支持,包括:课程信息,组织教学活动,指导学习过程,答疑讨论,布置和批阅作业,批阅试卷等;班主任则负责学生的管理工作,随时在网上和学生沟通,一方面增加了学生的归属感,另一方面能及时把握学生各方面的动态,及时解决他们的问题,对促进学生持续、有效的学习,降低辍学率有很大的帮助。网络维护技术人员则全天候为学生提供技术支持服务,维护与建设网络教学资源,确保系统平台正常运行。
经过几年的建设,目前我们已经形成了一支稳定的教师队伍。在完善的网络教学制度管理下,促进了学生个性化的自主学习,规范学生个性化自主学习的行为,引导学生按照开放教育的要求学习,并保证学生个性化自主学习的质量。
4网络资源建设中的教学设计与学习活动设计
在网络教育中,网络教学资源是学生进行自主学习、获得知识和技能的基本途径。远程学习者与本科生在自身特征上存在很大不同,需要建立导学策略和组织学习活动,引导和督促其完成学业。通过网络教学资源,应该能为学生系统化呈现教学内容,促进学生对课程的理解,引导学生进行学习。因此,我们在课程的网络教学资源建设时,精心进行了教学设计,主要包括以下几个方面:
(1) 学习内容设计:选择适应应用型人才培养的课程内容;打破课程内容的线性章节结构,设计出适合学生自主学习的内容组织结构。
(2) 教学策略设计:设计教学内容的呈现方式和使用方式,如文字呈现、教师讲解、动画演示、效果对比、模拟操作等。
(3) 动机策略设计:设计富有激励性的学习环境,激发和维持学生的学习动机,如技术的新颖性、界面的艺术性、反馈语的归因导向、学习伙伴的伴学等。
(4) 学习指导设计:设计学习指导的内容和呈现策略,包括学习的重点、难点、学习方法的建议等。
(5) 学习评价设计:设计学生自我评价的内容和评价策略,如自测练习、模拟考试、学习游戏等。
(6) 学习资源设计:设计并提供与教学内容紧密相关的扩展学习资源。
同时为满足学习者的需要,学习活动则设计了以下一些模块:
(1)“课程概况”,包括“课程介绍”、“课程大纲”、“考试大纲”和“参考资源”等模块,为学生提供学习的准备性材料。
(2)“自学周历”模块为学生的学习时间和活动安排提供指导。
(3)“教学互动”中“主讲教师”、“课程论坛”、“小组论坛”、“语音答疑”、“留言信息”、“问题解答”等模块是学生与老师和同学进行交流讨论学习的平台。
(4)“教学互动”中“学习进度”、“在线作业”等模块,帮助学员把握自己的学习进度以完成学习任务。
(5) 每一章的学习中,给学生提供了“学前指导”、“内容讲解”、“总结评价”和“扩展学习”模块。“学前指导”为学生学习章的内容提供准备性的材料,使学生明确学习的目标、方法、重点难点等;“内容讲解”是学生学习的主要内容,由老师进行讲授;“总结评价”让学生及时地评价自己对内容的学习情况及效果;“扩展学习”为学生提供更多的学习资料,满足学生的个性化学习需求。
(6)“原理动画”模块将课程中比较难以掌握的学习知识点内容,以动画和具体操作的方式呈现,帮助学生更好地理解学习内容。
(7)“概念速查”为学生学习提供一些辅的工具。
(8)“参考资源”模块给学生以广博的辅助材料,拓展学生的理论视野,增强学生的学习兴趣和知识面。
上述的教学设计和学习活动设计,在课程的远程教学方面起到了重要的作用。
5网络支持服务
远程教育不仅要为学生提供教学内容和资源、组织学习活动,还要提供强大的学习支持服务。这不仅包括提供关于课程内容答疑、资源、实践等与学习有关的服务,而且包括提供与教学管理及其他相关的支持服务。
为了网络教育的顺利开展,在本课程在网络资源建设中,提供了包括授课、课程发送、学习辅导、学习资料提供、作业批改和意见反馈、考试实施和成绩管理,技术培训等支持服务内容。
授课过程中,注重培养学生的自主学习、协作学习和探究性学习的能力,包括对资料的收集、整理、分析、判断、评价、综合等能力。
通过在线课程基本信息和课程导学完成了“学习目标、学习要求、学习内容、学习模式、学习方法、考核方式、评价标准、评价内容”等课程发送功能。
在学习过程中提供“语音答疑”,使学生能跟老师实时地交流学习中问题;在“主讲教师”、“小组论坛”、“班级论坛”等教学互动的模块中,可以通过发帖提问、跟帖学习的方式,让师生共同参与,讨论学习中出现的问题,引导学生积极思考,逐步提高;另外,学生还可以通过“友情链接”进入到与课程相关的资源网站。
完成课程学习后通过“总结评价”、“自测习题”、“模拟试题”等模块,帮助学生总结所学的知识,并对学习效果进行评价;通过“扩展学习”、“参考资源”等模块,帮助学生拓宽学科的视野,把握学科前景。
提供的学习资源具体包括:静态资源和动态资源。教学视频、教学讲义、教学实验录像、参考书目、历年考卷、在线习题、案例讨论、在线答疑、网络课堂、课程论坛、优秀作业等等。
考试实施和成绩管理,具体包括“编制考卷、施测、评阅考卷、成绩查询”,考卷的编制,由教学办公室组织,任课教师具体完成。考试工作的开展,由学院统一组织,各教学点配合,统一按北京理工大学考试管理制度进行实施。教师阅卷后,在线登录成绩,学生可在线查询成绩。
专职技术人员全天候为学生提供技术支持服务。北京理工大学现代远程教育学院还设立了技术支持免费网络电话,用来提供关于网络学习、操作指南、常见问题的支持。
另外,北京理工大学远程教育学院坚持定期开展教学效果评价和实时跟踪评价。建立了包括教学内容、教学手段、教学过程、媒体应用、考试管理等方面的多种评价措施,对教学效果进行全面评估。
对学习过程的监控,则利用教学管理平台,统计学生网上资源使用情况和教师对学生开展支持学习服务的情况。
经过几年的建设,本课程的学习支持服务系统全部实现了网络化,极大提高了服务的效率和水平。
6结论
“数据结构与算法设计”网络教育精品课程的建设,主要是针对远程教育的特性进行的。通过对“一流的教师队伍、一流的教学内容、一流的教学方法、一流的资源和教材、一流的教学管理和支持服务”的建设,体现了一流网络教学的特点,体现应用型人才培养目标,符合科学性、先进性及网络教育规律和教学改革的方向,适合于在职从业人员和业余学习和终身学习。通过现代教育技术、方法和手段的运用,到位的学习支持服务,发挥着示范、辐射和共享的作用。“数据结构与算法设计”2008年被评为国家级网络教育精品课程。该课程所建设的网络教学资源始终开放,这些资源已经与北京理工大学该门课程的本科教学共享。课程资源网址为/2008/ public/。课程资源今后将会不断地更新维护,以保障该课程的可持续建设与发展。
参考文献:
[1] 教育部办公厅. 关于2007年度国家精品课程申报工作的通知(高教厅函[2007]25 号)[EB/OL]. jpkcnet. com/new/ zhengce/default.asp.
关键词:插值;K-D树;算法优化
Key words: interpolation;K-D tree;algorithm optimization
中图分类号:TP391.9 文献标识码:A 文章编号:1006-4311(2016)11-0199-02
0 引言
平面插值思想在现论研究、工程处理等方面有着重要的应用。由于现实条件的限制,无法采集到研究对象平面上任意坐标点的属性值。为了计算未采集到实际属性数据坐标点的信息,一般采用平面插值的方法,在已知点的基础上,对未知点进行插值计算。目前的数据插值处理多由计算机软件协助计算。当原始采样数据量较大的时候,常规算法耗时较长,本文讨论如何在常规插值算法中引入K-D树数据结构,提升插值算法的速度,并用实例加以实现验证。
1 插值概述和问题
插值是从一组以是离散点的形式存在的已知空间数据中找到一个函数关系式,使该关系式最好地逼近已知的空间数据,并能根据该函数关系式推求出区域范围内其它任意点或任意分区的值[1]。
插值的理论基础是空间位置上靠的越近的点,越可能具备相似的特征;而距离越远的点,其特征相似的可能性就越小。近些年的科学研究在此基础上,形成了最近距离插值法,距离加权反比插值法,泰森多边形插值以及克里格插值法等插值理论方法。实际研究中,人们一般根据已知数据的特征选用不同的插值方法。但是无论选用那种插值方法,都要事先确定一个距离插值点较近并且特征相似的已知点集合用于插值计算。这个插值点周边已知点集合的临界范围称为搜索范围。
传统的插值计算方法是在对每个插值点进行插值计算之前,先要得出一个参与该插值点插值计算的已知点集。计算点集合的方法是先对每一个已知点进行线性扫描,逐一得出已知点与待插值点的距离后,再与搜索范围比较,如果落在搜索范围内则将其加入参与插值计算点集合,否则就跳过该点。如果已知离散点分布范围较大,点数较多,这其中大量的无效的距离求值和比较计算次数都是随着插值点的个数成倍增加,这严重影响计算机软件的计算速度。
2 K-D树的介绍和实现
K-D树,是K-dimension tree(K-维树)的缩写,是一种对K维空间中的实例点进行存储以方便对齐进行快速检索的树形数据结构。
K-D树的设计思路是利用已知点的数据集本身蕴含的结构信息,建立一个索引,然后在此基础上搜索便可进行快速匹配,达到快速获取指定搜索结果的目的。
构造 K-D树首先构造根节点,使根节点对应于K维空间中包含所有实例点的超矩形区域。然后利用递归的思想,不断地对K维空间进行划分,生成子节点。在超矩形区域上选择一个坐标轴和在此坐标轴上的一个切分点,确定一个超平面,这个超平面通过选定的切分点并垂直于选定的坐标轴,将当前超矩形区域切分为左右两个子区域;这时,实例点被分到两个子区域。这个过程直到子区域内没有实例时终止,终止时的结点即为叶子结点。在此过程中,将实例保存到相应的结点上。
下面是一个6个二维数据点{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}构建K-D树的示例,利用上面的构造方法对平面进行分割如图1所示,构造好的K-D树如图2所示。
在以K-D树形式存放的数据结构上,利用KNN算法可以避免遍历全部数据而快速地获得确定范围内的数据点。利用K-D树的这一特性,将其引入到插值算法中,可以优化传统的遍历搜索插值算法,提升效率。
3 实例对比
实例样本为某地某金属元素含量采样离散点数据,100×100的坐标范围内得到的1000个随机分布的离散采样点,在此基础上采用搜索距离为20坐标单位的距离加权反比的加权方法,每隔1个坐标单位的步长进行插值,得到规则均匀分布的10000个插值点。
现分别采用传统的遍历搜索法和引入K-D树的搜索法进行插值,对比其效率。经多次测试,传统方法耗时一般需要900毫秒,而且引入K-D树数据结构后的耗时只需200毫秒。可见K-D树数据结构对插值算法优化效果显著。
4 总结与展望
本文是K-D树数据结构在K为2的二维空间环境下的应用,在K的取值较大的多维的环境下,K-D树的搜索效率会有一定程度的下降,需改进搜索方法,以获的理想的搜索效率。
在构造K-D树的过程中,选择一个恰当的根节点很重要,根节点的选择虽然不会影响构造正确的K-D树,但是会影响树的最大深度以及超平面空间的形状是否均衡,形状的均衡与否通常也会影响搜索效率,通常选定距离坐标轴上的中位数最近的离散点为切分点,这样得到的K-D 树是相对平衡的,其搜索效率也相对较高。
参考文献:
[1]黄杏元,马劲松,汤勤.地理信息系统概论[M].北京:高等教育出版社,2001:93-103.