启发式思维驱动的研究生算法课程在线教学探索*

栗风永 毕忠勤

(上海电力大学计算机科学与技术学院，上海 201306)

0 引言

为应对新型冠状病毒肺炎疫情，教育部提出“停课不停教、停课不停学”指导意见[1]，国内各个高校纷纷开展在线教学。作为硕士研究生的主干专业基础课程，算法设计与分析(以下简称“算法课程”)不仅承载着算法基础理论和经典算法设计的教学内容，同时也是培养和提升研究生科研思维能力的平台[2]。

通过对算法课程的学习与研究，学生应具备以下两方面能力：①掌握算法设计的主要思想，能够对算法计算复杂性做出正确分析，同时结合经典的算法分析案例，理解算法的理论体系，并能够利用现代分析方法对算法进行优化。②培养学生提出问题、分析问题、解决问题的能力，并将其融入到后续的科研工作中。因此，算法课程不仅要培养学生利用基础算法理论解决实际问题的能力，同时要教学过程中进一步强化计算思维和创新意识，为后续科研工作奠定基础。

1 教学内容

1.1 课程特点及存在的问题

作为计算机专业研究生的一门专业基础课，算法课程在教学过程中需要注意以下几个问题。首先，学生需要具备良好的数学和程序设计基础，比如需要先修离散数学、程序设计基础、数据结构等课程，但部分学生的先修课程基础不同，因此一些内容还需要在教学过程中进行简单介绍，如离散数学中的逻辑分析和数据结构中的典型树形结构和链表等。其次，选修本门课程的研究生在本科阶段并非全部来自计算机专业，还包括其他如通信、自动化、数学等跨专业学生，如何组织教学内容使学生的整体接受度达到最大，其难度显而易见。最后，也是最重要的一点，受当前疫情影响，在线课程授课方式相比线下授课在师生互动方面有所减弱，而算法课程则需要学生结合典型算法的分析思想对部分算法实例进行实时互动反馈，如何在线上充分调动学生的互动积极性，这也是当前算法课程在线教学的一个难点。

1.2 应对在线教学的课程内容梳理

在综合分析了以上问题的基础上，笔者重新梳理了算法设计与分析课程的内容，并将其分为核心内容和拓展内容两部分，以适应不同基础的学生。相对于本科教学，研究生算法教学更侧重于复杂性分析，以及针对复杂性的优化过程[3]，因此核心内容主要涵盖了经典算法的设计思想和分析方法，如分治策略、动态规划、贪心算法、回溯法、分支限界法以及随机化算法等，这部分内容要求所有学生能够针对每一种典型算法描述出基本的设计思想，熟悉复杂度分析过程，写出复杂度递推方程，并进行推导证明。拓展内容则是在每一种经典算法基础上，针对不同算法案例进行实例分析，并提出可能改进的解决方案。由于每一种典型算法都包括了很多应用实例，每一种实例有不同的理解难度，笔者根据难易程度将众多应用实例分成难、中、易三个等级，学生根据自己的基础选择不同案例进行线下拓展学习，进一步完成相关的实验任务。整体的教学内容框架如图1所示。

图1 适应在线教学的课程内容梳理

1.3 课程采用的教材

受疫情影响，高校的大部分课程都采用在线教学形式。由于在线教学容易受到网络环境的影响，在考虑在线授课特点的基础上，结合算法课程的知识框架和教学内容，课程采用屈婉玲等编著的《算法设计与分析》(第2版)作为主讲教材[4]。该教材除了具备完备的课程教学体系外，在中国大学慕课(MOOC)平台上也发布了较为完善的线上教学视频供学生在线学习[5]。辅助教材采用王晓东编著的《计算机算法设计与分析》(第4版)[6]，该教材也属于国家精品课程教材。两部教材都较为全面地涉及了经典算法与对应的实例分析，同时涵盖了部分算法领域的热点研究内容，比较适合作为研究生课程的配套教材。

2 教学过程

2.1 教学平台

为了应对在线教学，算法设计与分析课程在疫情防控期间利用中国大学慕课(MOOC)平台开展在线教学。中国大学慕课平台提供三种课程授课方式：独立SPOC(Small Private Online Course，小规模限制性在线课程)、异步SPOC、同步SPOC。结合线上教学的教材资料及精品课程开放情况，笔者采用异步SPOC模式实施在线教学，它可以根据本校实际教学情况删改原有内容和新增补充内容，教学过程中的作业批改答疑等由任课教师提供，可以很好地构建师生的互动交流。同时，课程利用在线会议系统(如腾讯会议)组织算法课程的研讨式教学，开展实时在线研讨。

2.2 融入启发式思维的在线教学过程

作为一门计算机专业的研究生基础课程，算法设计与分析更多承担了培养学生计算思维能力的重任，同时还要让学生在算法教学过程中提升分析问题的能力。计算思维能力体现在针对具体问题的描述、建模、求解的科学思维方式，而分析问题的能力则主要体现在对问题深入思考的灵敏嗅觉。笔者通过总结线下课程教学经验，将启发式思维渗透到算法课堂教学中，在讲解算法的设计思想和算法分析过程中，注重利用启发式分析方法引导学生思考如何对模型进一步优化。针对一个具体问题，分析当前解决方案，考虑其中存在的问题，进一步思考如何解决该问题，最终找出应对方法。如此反复，直到学生掌握这种思考模式并能够将其熟练应用到其他问题分析中。以算法课程中分治策略的整数乘法为例，启发式的教学过程如表1所示。经过反复的启发式分析训练，学生的问题建模和分析能力得到较为明显的提升，具备了针对问题进一步优化的灵敏嗅觉。

2.3 围绕典型算法案例的研讨式在线教学

在教学过程中，笔者利用腾讯会议系统组织研讨式教学，进一步加深学生对典型算法案例的理解并提升团队协作能力。研讨内容以经典算法实例为主，通过实时在线讲解和程序演示，让学生就不同算法解决同一问题进行分析对比。小组研讨过程中注意区分不同程度的学生，根据学生的能力安排小组任务。以三人小组研讨0-1背包问题为例，让学生思考分别使用动态规划和回溯法得到不同的解决方案，同时分析不同方案的异同点。研讨过程中，学生A负责总体讲解问题模型、算法设计、核心代码以及复杂性分析。学生B负责算法的程序实现，并实际测试运行时间。学生C则围绕0-1背包问题检索近年相关的科研论文，并就该主题做研究进展综述。研讨式教学结构如表2所示。腾讯会议系统可支持多人同时在线讨论，相对于线下教学的小组研讨，线上小组研讨可以让小组的每一位成员实时参与互动，激发学生创新能力的同时也培养了学生的团队协作能力。

表2 0-1背包问题的小组研讨式在线教学案例

2.4 实验教学

在拓展教学内容的基础上，围绕每一个经典算法布置多个不同的算法实例，并将其分为难、中、易三个等级，实验教学要求学生根据自身能力自由选择不同难度的算法实例编程实现，并给出不同的参考和评价标准。实验过程主要是线下完成，以学生为主，教师在线辅助指导，并对程序设计过程中的问题做启发性提示，根据不同层次的实验内容对学生进行个性化培养。

3 课程考核

综合在线课程考核标准，算法课程的理论考核占总成绩的60%，研讨式教学过程小组表现占20%，在线答疑和讨论参与度占10%，实验教学占10%。由于线上教学难以全面掌握所有学生的课堂参与度，在未来的教学环节中将调整课堂参与度的分数占比，建立更加科学的考核体系。此外，小组研讨过程中每一位成员都有自己的任务，同时还需要相互配合完成小组的团队任务，且可以随时参与展示自己的想法和完成的内容，整体上这一环节更能体现个人能力和团队协作能力，因此考核分值占比较大。

4 结束语

结合在线教学特点，笔者对算法设计与分析课程教学模式进行了创新设计。针对不同程度学生的特点重新梳理了课程的重点内容和拓展内容，并对具体的教学方式进行设计，融入启发式教学模式，逐步引导学生形成提出问题、分析问题、解决问题的思维方式。同时将研讨式教学与线上教学有机融合，根据不同研究生的能力定制个性化教学任务目标，培养学生计算思维的同时，也显著提升了学生自主分析和解决实际问题的能力。