《算法设计与分析》课程的问题驱动递进启发式教学方法探讨
来源:用户上传
作者:
摘 要：为了使计算机科学与技术专业的学生从本科阶段具有良好的算法设计思维和能力，本文提出了问题驱动的递进启发式教学方法。本文的撰写目的不是为了提供高大上的理论上的教学方法，而是给出一种具体的、可操作的教学方法，即，本文分别以分治法、动态规划和贪心算法为例，对该问题驱动递进启发式教学方法进行了描述。问题驱动递进启发式教学方法是通过直观的问题驱动，以递进的方式，对学生进行问题启发和算法启发，以提高学生的算法直观分析和设计能力。
关键词：算法设计与分析;问题驱动的递进启发式教学;分治法;动态规划;贪心算法
算法设计与分析是普通高校计算机科学与技术专业的核心基础课程，算法设计与分析课程一直是大多数本科生比较苦恼的一门专业课程。图灵奖得主Donald E.Knuth曾说：计算机科学就是算法研究[1]。事实上，计算机科学每个领域的发展都要靠有效的算法设计。作者在教学过程中一直选用的教材是王晓东教授编著的《计算机算法设计与分析》[2]，因此本文的很多描述都是以该教材作为基准。由于该课程需要较多的数学知识，因此有相当一部分学生对该课程有恐惧感，学习兴趣不高。另外，该课程是计算机科学与技术专业大学二年级的必修课，一般选课人数较多。为了提高学生们对该课程的学习兴趣和对课程中主要算法的掌握能力，本文提出了问题驱动的递进启发式教学方法。
问题驱动的启发式教学方法已在研究生评估类课程中得到了应用[3]。而本文的主要创新是，作者根据自己多年讲授本科生的《算法设计与分析》课程的教学经验，总结出了针对本科生《算法设计与分析》课程的问题驱动递进启发式教学方法。本文的撰写目的不是为了提供高大上的理论上的教学方法，而是给出一种具体的、可操作的教学方法。本文中的方法通过直观的问题驱动，以递进的方式，对学生进行问题启发和算法启发，以提高学生的算法直观分析和设计能力。具体地，下面，我们将分别以分治法、动态规划和贪心算法为例，对该问题驱动递进启发式教学方法进行了描述。
1 分治法的问题驱动递进启发式教学方法
在讲解分治法时，为了给学生一种直观的理解，需要通过一些具体化的例子来进行讲解。例如，可以先设置一个具体的背景，例如，警察要到一个单位去排查犯罪嫌疑人，已知该犯罪嫌疑人的身高是1.75米，然后让学生思考如何才能快速给出排查结果，也就是说警察如何做才能快速排查完？然后给学生讲解正式的折半查找算法。接下来抛出问题：对于给定的n个元素，如何实现快速排序？对于这个问题，网上有一个视频，该视频是通过跳舞的方式，实现快速排序。通过这个方式可以启发学生对分治法的兴趣。最后再详细讲解分治法思想和算法步骤。
在讲解分治法的算法步骤之后，还要对分治法的算法复杂度进行深入的讲解，通常学生们是记忆教材上给出的通用公式[2]。然而，这种死记硬背的方法，时间长了，却容易忘记。为了较好地让学生掌握分治法的复杂度，可以采用麻省理工学院教材上的方法，通过递归树的启发式讲解，来分析分治法的復杂度[4]，而且还比较容易得到教材上的算法复杂度公式。总之，分治法的问题驱动递进启发式教学方法是通过直观的问题驱动，以递进的方式，对学生进行问题启发和算法复杂度启发，以提高学生对分治法的算法直观分析和设计能力。
2 动态规划的问题驱动递进启发式教学方法
在讲解动态规划算法时，为了给学生一个直观的理解，我们可以先引入一个日常生活中的例子，例如，当我们和朋友坐在酒店聚餐的时候，面对一桌子菜的时候，我们是如何选择食物进餐的？事实上，我们日常进餐的时候，都是荤素搭配着吃饭，有些对饮食更讲究的人，还会考虑如何搭配更有营养。这种选择就是一种动态规划的思想。然后引入两个例子，一个是矩阵连乘积问题，另一个是最大字段和问题。在讲解矩阵连乘积时，本文建议先分析递归关系，让学生思考两个连乘积的矩阵序列的数乘次数和两个矩阵序列乘积之后得到的矩阵的数乘次数之间的关系，同时让学生思考两个矩阵序列各自的子序列是否也满足类似的性质，从而引出动态规划算法的基本要素之一“最优子结构”性质。最后，在讲解如何通过递归关系计算相应的最优值（最小数乘次数）。在讲解最大字段和的时候，本文建议尽量避免直接讲解规范化的数学描述，可以通过股民炒股需要计算一年当中哪个时间段的收益最高来讲解。这样做，可以让学生对最大字段和问题有一种“在身边”的感觉，从而让学生感觉该问题不至于那么深奥。
在给学生讲解动态规划的时候，还要通过分析0-1背包问题，直观分析和强调动态规划的重叠子问题性质。让学生真正对动态规划的最优子结构性质和重叠子问题性质有比较深刻的认识。总之，动态规划算法的问题驱动递进启发式教学方法是通过直观的问题驱动，以递进的方式，对学生进行问题启发和算法启发，以提高学生对动态规划算法的算法直观分析和设计能力。
3 贪心算法的问题驱动递进启发式教学方法
在讲解贪心算法时，为了给学生提供一种形象的解释，需要重点强调“贪心”。然而，为了避免学生为了“贪心”而贪心，需要引入一些中性或具有更加积极向上的例子。因此在讲解贪心算法的问题驱动递进启发式教学方法时，可以从如下两个层次展开教学：
（1）问题层次：首先通过“危难时刻”抛出问题：2018年7月19日，辽宁省锦州南火车站一位81岁老人突然倒地不起。候选答案之一是直接拨打120，等待医护人员到来。连一个候选答案是：现在有一位懂医学知识的女大学生见义勇为，同时拨打120。让学生思考如何选择处理方法更为合理：本实例可以起到间接鼓励学生“见义勇为”的效果。然后给出日常生活中的实例：其一是通过“饿汉进餐”，介绍“贪心选择”。进而通过“收银员找零”讲解收银员找零中的“贪心选择”做法。接下来是教材中的活动安排问题，并通过活动安排问题的数学模型，以及背包问题的数学模型，让学生由浅入深从问题层次上对“贪心算法”的适用范围有所了解。 （2）算法层次：针对上述三个不同层次的问题，开始讲解“贪心算法”。首先是从直观本能角度讲解贪心选择，事实上，从人性的本能做出的“见义勇为”的行为，属于贪心算法的贪心选择策略。因为在老人倒地的那一刻，能够做出的最优的选择是现场有懂医术的乘客，能够采取一些急救措施，例如掐人中穴或者人工呼吸等，同时拨打急救电话。而不是打急救电话，并干等救护车的到来，因为这样可能会错过一些抢救时机。接下来，从量化的角度讲解收银员找零问题的贪心算法：假设有面值为50元、20元、10元、5元，2元，1元的纸币，需要找给顾客85元现金，为使付出的纸币的数量最少，首先选出1张面值不超过85元的最大面值的纸币，即50元，再选出1张面值不超过35元的最大面值的纸币，即20元，依次选择下去，收银员总共付出4张纸币。这个例子可以让学生从量化的角度来理解收银员是如何做“贪心”选择的。最后，从规范的算法角度对活动安排问题的贪心算法进行讲解。此时，需要首先建立“活动安排问题”的规范的数学模型中，然后提炼出“贪心算法”，并分析算法的复杂度。
在讲解过活动安排问题的贪心算法之后，需要给学生强调：贪心算法在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。进一步，尽管贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。总之，贪心算法的问题驱动递进启发式教学方法是通过直观的问题驱动，以递进的方式，对学生进行问题启发和算法启发，以提高学生的算法直观分析和设计能力。
4 小结
本文针对计算机科学与技术专业本科生的《算法设计与分析》课程，提出了問题驱动的递进启发式教学方法。该教学方法主要分两个层次：问题层次和算法层次，并采用递进的方式进行教学，并分别以分治法、动态规划和贪心算法为例，对该问题驱动递进启发式教学方法进行了描述。问题驱动递进启发式教学方法是通过直观的问题驱动，以递进的方式，对学生进行问题启发和算法启发，以提高学生的算法直观分析和设计能力。
参考文献：
[1]M.H.Alsuwaiyel，Algorithms Design Techniques and Analysis.Publishing House of Electronics Industry，2013.
[2]王晓东.计算机算法设计与分析.北京：电子工业出版社，2018（第5版）.
[3]钱龙霞，王正新，张韧，洪梅，卢扬.基于问题驱动的启发式教学方法在研究生评估类课程中的应用研究.教育教学论坛，2016-3（11）：172-173.
[4]Thomas H.Corman，Charles E.Leiserson，Ronald L.Rivest，Clifford Stein，Introduction to Algorithms（3rd Ed.），The MIT Press，2012.
基金资助：河南省高等学校青年骨干教师培养计划（项目编号：2017GGJS065）
作者简介：董永生，男，副教授。
转载注明来源:https://www.xzbu.com/1/view-15114349.htm
