基于完全案例覆盖的专业硕士生算法教学方法

打开文本图片集

摘要：针对与计算机相关的专业硕士研究生算法理论基础相对薄弱和授课学时数较少的状况，在实践基础上，提出以大量案例多重覆盖知识点的算法设计与分析课程教学方法，同时介绍相应的教学案例库的构建和完善。

关键词：专业硕士；算法设计；算法分析；案例覆盖；案例库

0、引言

作为我国人才发展规划的重要组成部分和支撑手段，我国专业硕士学位正处于高速发展的机遇期。高校正在抓住机会，采取积极措施，大力促进硕士专业学位教育的全面发展。教育部在2010年要求进一步调整优化教育结构，积极稳妥地推动我国硕士研究生教育的战略转变，从以培养学术型人才为主，逐渐转变为以培养应用型人才为主。这意味着扩大全日制专业硕士研究生的培养规模成为研究生培养的一个趋势。

区别于侧重理论和研究的科学硕士学位，专业硕士学位教育主要培养满足特定职业需求和有特定职业背景的高级专门人才。专业学位教育具备专业性、综合性和开放性三大特点。

算法设计与分析是专业硕士研究生课程，是多个专业和方向的必修课程，这些专业包括计算机科学与技术、计算机应用、计算机软件与理论、软件工程等。该课程同时还是一门与计算机有关的非计算机专业的专业课程，包括管理科学与工程、系统工程、应用数学与计算数学等专业。本课程的前驱课程包括离散数学、程序设计基础、数据结构等，与计算方法和计算机图形学等课程关系紧密，既具有鲜明的理论体系，也具有很强的实践性。

专业硕士研究生的算法设计与分析课程的主要目标是通过讲授不同类型算法的基本原理、解决方法、实现技术等，分析不同算法的时间复杂度和空间复杂度，使学生通过该课程的学习，能够对系统软件和应用软件开发过程中的实际问题设计出高效、优化的算法，为开发出优秀的软件奠定基础。该课程涵盖的主要内容有常用数学工具、穷举法、贪心算法、分治法、减治法、动态规划、并查集、回溯法、分支限界法、计算几何、随机算法、NP理论等12个方面。

但是，在教学实践过程中，大部分的专业硕士研究生并不能很好地理解该课程的理论部分，对算法设计也只是机械地记忆法的步骤，而不能灵活地解决碰到的新问题。这些问题对教师提出了挑战：如何根据学生的知识基础，让他们以乐意接受的方式，在有限的课堂时间内掌握算法设计方法，以应对今后工作实践中无限变化的实际问题。

大量教学实践证实：纯粹的理论灌输会使学生很快失去学习课程的兴趣，不能坚持课堂学习，更没有意愿在课后的练习和实践环节投入时间和精力。

基于完全案例覆盖的教学方法因此提出，也就是让每个案例覆盖多个知识点，每个知识点有多个案例与之对应；让案例教学贯穿于理论讲授、算法设计讲授和编程技巧讲授的整个过程。该教学法涉及案例选取、案例库建设、案例授课技巧等内容，下面将分别阐述。

1、案例选取的原则

所谓的案例教学法，就是利用案例作为教学媒介和教学手段，以提高学生综合能力为目标的教学方法。案例的选取至关重要，因为案例是案例教学的核心，直接影响着学生的兴趣和对知识的接受程度，从而最终影响着案例教学法的实际效果。

根据所讲授算法分析与设计课程的实际，案例的选取要遵循两个原则：其一是多重覆盖原则，其二是难易平衡原则。

1.1 多重覆盖原则

科学硕士授课时间通常分为3个学期、一年半左右的时间，课时量充足，课程覆盖知识点全面而细致，传授知识的信息量更大。而专业硕士的课堂授课大多集中在前两个学期，用一年时间完成，相对科学硕士，课时量相对不足。就算法设计与分析这门课而言，科学硕士的授课学时数为48，而专业硕士授课32学时。较少的课时量对案例的选取提出了严格的要求。一个案例并不能只为一个知识点设计，而必须为多个知识点设计。只有这样，当所有的案例教学完成后，每个知识点可以从多个不同的角度进行讲解，学生也可以从多个角度对其进行学习和理解，完成了解→熟悉→巩固的学习过程。

例如，最大子段和问题就具有多重覆盖的性质。最大子段和问题可以描述为：给定n个整数（可以是0、可正、可负）组成的序列，求该序列能够取得最大连续子段的和。如果序列是{-2，6，-5，13，-5，4}，则满足要求的子段是{6，-5，13}，其元素和是14，这也是该问题的解。

最大子段和问题虽然描述简单，容易理解，但它有多种解法，涉及的知识点包括穷举法、分治法、动态规划、NP理论等，其计算复杂度涵盖了O（n3），O（n2），O（nlogn），O（n）等4个层次。因此，该问题是一个典型的多重覆盖的案例，在案例选取时可以优先选择。

1.2 难易平衡的原则

依照教育学理论，案例教学法要把实际教育过程中真实的情景加以典型化处理，引导学生思考和决断，使得相同或类似场景再现时，学生能够根据学习时处理案例的经验和技巧，有效处理新出现的情况和问题。因此，一方面，课堂上使用的案例要具有一定的难度和挑战性，使得学生有兴趣跟随教师的思路去思考解决方案；另一方面，案例的难度又不能超出学生的能力范围，否则学生会失去信心，与教学过程脱节。

最能体现案例选取的难易平衡原则的两个问题是多段图的最短路径问题和最长公共子列问题。前者描述的是一个图分为多个段，每个段有若干个节点，这些节点只与前一段的节点和后一段的节点之间有路径，要求找到起点到终点距离最短的路径。而最长公共子列问题描述的是在两个字符序列中找到共同的但又最长的那个子列。

虽然这两个问题都是动态规划的典型案例，但难度是不一样的。多段图的最短路径问题的求值过程和回溯求路径（求解）的过程形象而直观，因此可以作为动态规划算法的入门案例。最长公共子列问题虽然描述起来简单，但要建立递推公式比较困难，也比较难以理解的，因此，可以作为动态规划算法的提高案例。

但有些问题因为过难或过易不适合作为案例。楼层扔鸡蛋问题讲的是一个鸡蛋从n层楼上摔下来不破，但从n+1层楼上摔下来必摔破，对有限的楼层数和鸡蛋数，求最坏情况下至少要经过多少次实验才能把n求出来。这个问题虽然也可以用动态规划算法解决，但不易理解，因此由于受到学时数的限制，不适合作为专业硕士生算法教学案例。

2、案例库建设

在基于完全案例覆盖的算法教学法中，案例并不是孤立的、只服务于各章节和知识点的，相反，它们彼此间有紧密的关系，甚至可以说案例集合可以成为一个完整的体系。为了便于案例的选取和利用，需要把案例整理成库，并在教学过程中不断完善和发展。案例库并不是一个个案例的简单罗列，而是以数据库系统的形式组织起来，便于从难度、涉及知识点、彼此关系等方面查询，也便于添加、修改和删除。

2.1 案例来源

案例库中的案例有3个主要来源：经典问题、科研开发问题和公司面试题。

经典问题在案例库中占有大部分的比例。经过前人的总结和积累，算法设计与分析的各个知识点都有一个或多个的经典问题可以作为案例。经典问题作为案例具有多方面的优势。首先，这些问题已经被大多数学生熟悉，便于学生理解和掌握。例如汉诺塔问题，虽然学生尚不清楚案例涉及的分治和计算复杂度理论，但很容易被案例吸引，产生兴趣。其次，问题解决方法研究得比较透彻，且一般有多种解法。第三，学生更容易在课后找到相应的学习资料，对所学知识加深理解。

案例的第2个主要来源是学生在科研和开发中碰到的问题。这部分问题更具有前沿性和实践性，与实际联系紧密，更能使学生掌握解决实际问题的方法。例如，在教学过程中有学生提出其导师的课题中如何用GPS快速准确地测量林地面积的问题。如果用传统的林地分割法解决，不但数据收集困难，而且在计算中容易出现负面积和面积重复计算等严重的问题，但采用计算几何的手段可以解决这些问题，而且计算过程简单高效。因此，这个实际问题也成为计算几何知识点的主要案例之一。通过鼓励学生在课堂上通过提问和发电子邮件的形式获取这些问题，帮助他们解决问题，同时丰富案例库。

各大IT公司的面试题也是重要的案例来源。这些公司的研发部门为了招聘到具有发展潜力的研发人员，面试题目的重点已经不在程序的语法和具体的编程技巧上，而是把重点放在算法设计上，以考察所面试学生的算法水平和解决实际问题的能力。结课后1～3年的时间内，通过回访调查，可以获取这方面的案例，同时也可以掌握业界的研究动态和方向，以便在课程中有所涉及和倾向，为学生的就业奠定更好的基础。

2.2 部分案例总结和列表

经过长时间的收集、整理和建设，案例库已初见规模，形成了经典案例、研发案例和面试案例共同构成的案例体系。表1展现了部分案例的来源以及它们与算法设计的各个知识点之间的覆盖关系。

2.3 完善案例相关的授课技巧

案例库中的所有案例都具有一个重要的属性：授课过程中使用该案例的技巧。这些技巧大致分为3类，分别是叙述故事、提出挑战、破解悬疑。

叙述故事的技巧适合于知识点的引入环节，目的是吸引学生的注意力，激发其兴趣。例如，在讲解最小生成树知识点时，可以讲述以下蜘蛛建网的故事。一只大蜘蛛要结网了！结网之前首先要拉龙骨。龙骨的作用很重要，要确保每个关键点之间都有一段或多段蛛丝连接。这样，可以保证一旦昆虫落入网络陷阱，蜘蛛能在第一时刻感受到。你的任务是：编写一个程序，对一组输入的固定点，能够输出一个方案，使得蛛丝的总长最小。通过这个故事，学生能够迅速理解最小生成树的定义，并饶有兴趣地思考如何解决这个问题。

对于那些貌似容易解决，但实际需要大量理论和算法设计技巧作为支撑的案例，可以采用提出挑战的方式授课，让学生乐意尝试。用GPS测算林地面积的问题就属于这个类型。通过问题介绍，学生根据自己的知识积累很快就能想出三角形分割法、梯形分割法和小矩形分割法等方法。但这些方法都存在着实际计算方面的缺陷，因此可以提出挑战：用所学过的计算几何的知识和手段解决面积测算问题。而挑战往往会带来思考和行动的动力，让学生在接受挑战的过程中掌握相关的知识和技巧。

破解悬疑是悬疑影片最引人人胜的设计，而案例授课过程可以把这种手法引入课堂，使学生长时间保持课堂注意力，并使问题解决的过程给学生留下深刻的印象，从而强化知识点，强化算法设计技巧的教学效果。二部图方面的婚配问题可以作为典型的破解悬疑的教学案例。在追求最大婚配数目标的过程中逐步讲解什么是二部图、什么是可增广链、如何发现可增广链、以及如何增加婚配数等，让每一步都有一个具体的目标，让学生围绕该具体目标进行思考和设计。

3、课堂效果

通过长期的探索和积累，基于完全案例覆盖的算法教学法取得了预期的效果。

（1）课堂出勤率有明显的好转。如果单纯讲解算法理论和算法技巧，课程开始阶段还有很多学生坚持上课，但到课程中后期，很多学生就会以各种理由缺课。究其根本原因，是这部分学生认为自己无法跟上课程节奏，没有课堂收获。但采用了案例教学后，绝大部分学生能够出勤，并且课程前期和中后期的出勤率大致相当。

（2）课堂气氛有了很大提升。为了解决案例中的问题，学生会积极思考，参与课堂讨论，能够始终保持课堂注意力。

（3）促进了部分学生的研究和开发。这是因为部分案例来自学生的科研和开发实践，案例在入库之前已经得到了充分讨论和有效解决。

（4）使学生在就业市场取得了一定的优势。由于部分案例来源于IT公司的面试题，这就让学生对就业有更充分的准备。而这些题目也是业界发展的风向标，因此对学生就业后的工作也有支持作用。事实上，在教学实践中，学生最感兴趣的案例就是公司面试题，这应该与越来越严峻的就业形势有关。

4、结语

专业硕士研究生的学制更改为两年，区别于科学硕士研究生的三年学制。为此，需要将专业硕士研究生的自主学习能力、实践动手能力和团队精神部分前移到课程教学中，以此弥补专业硕士研究生研究时间缩短、研究能力训练和综合素质培养不足的问题。如何在有限的学时内使专业硕士生既能快速理解算法的理论，又能让他们掌握算法的设计技巧，是摆在算法设计与分析课程教师面前的重要问题。

基于完全案例覆盖的算法教学法能够提升学生学习算法的兴趣，寓教于乐，通过示例实际问题的解决让学生理解和掌握相关的知识点和理论，起到了良好的教学效果。其中的教学手法在为科学硕士研究生授课的过程中也有借鉴意义。

但是，需要针对教学大纲要求、市场需求和学生的实际情况从案例库中优选相关教学案例，服务于专业硕士的算法教学活动。案例库的建设是一个长期积累、不断更新和发展变化的过程，需要大量的时间和精力的投人才能起到良好的效果。