基于立体化的算法设计与分析教学模式改革*

任建国 徐永红 李汉伦

（1.江苏师范大学智慧教育学院；2.江苏师范大学生命科学学院）

算法理论是计算机科学的重要研究内容，并且在计算机出现前的很长一段时间内，人们就已对算法有了深入的研究，并将其应用到实际生活中。根据算法的定义，它是执行不同功能所需的预定义的、独立且有限的指令序列，其规则可以追溯到公元前300 年，最早被发现刻在巴比伦的泥板上。最早和最基本的算法是古代人用来记录他们的谷物和牛的一系列标记方案，随之而来的是数字系统的出现，以及随后算盘、代数和变量的演变，产生了参与制定评估系统的符号和规则，后来算法在计算机程序和机械应用中找到了自己的位置。“算法”(algorithm)一词的起源被认为是由波斯天文学家和数学家穆罕默德·本·穆萨·阿尔·花 剌 子 模(Abu Abdulloh Muhammad ibn Muso al-Xorazmiy)(约公元850 年)提出，他的工作包括向西方世界介绍数字系统中的十进制位，以及有史以来第一个线性和二次方程的系统解。我们今天所知道的算法是随着机械工程和过程的出现和兴起才被应用的。在最初的形式中，算法为逻辑代数提供了基础，在计算中使用变量。最早的算法例子包括数论中最大公约数的欧几里得函数、阿基米德对π 的逼近以及厄拉多塞对素数的计算。第一个使用算法这个术语的最初形式的人是12 世纪的英国哲学家阿德拉德(Adelard of Bath)，他在翻译阿尔·花剌子模的阿拉伯作品时使用了算法这个术语。算法进化的一系列重大成就出现在19 世纪，其中第一项是由英国数学家乔治·布尔建立的，他还撰写了《思维定律》并建立了布尔代数。1847 年，布尔将逻辑与计算统一起来，形成了二进制代数，这是今天计算逻辑的基础。随着60 年代末个人电脑的出现，算法也有所改进。算法在我们日常生活中的每一个时刻都有应用，例如，在智能手机上，其相机拍摄的照片的色彩平衡由一组算法定义，这些算法根据场景识别颜色并平衡对比度。随着处理能力的提高，算法的复杂性和计算能力也在增长。

算法设计在各学科的夹缝中找到了立足之地，它是数学与工程技术糅合而成的怪异混合体。现在，为人类设计算法的工作也面临相同的境遇——找不到一个现成的归属学科。今天的算法设计不仅需要借助计算机科学、数学和工程技术，还需要得到统计学、运筹学等相关领域的帮助。此外，我们不仅需要考虑计算机算法设计与人类思维活动之间的关系，还需要认真研究认知学、心理学、经济学等学科。作为高校计算机专业的一门核心专业课程，教学目的是通过课程学习后能理解各种算法的思想，掌握算法复杂性的分析方法以及算法评判的准则。由于课程的实践性和应用性较强，学生需要根据具体实例设计出具有一定精度和效率的算法，并通过上机编程实现。不同类型的算法通常对应和解决一类特定的问题，并且都有各自的适用条件和局限性。[1]首先要深入理解算法的思想，就离不开高等数学、线性代数、离散数学和概率统计等数学知识。在理解递归、分治、动态规划和回溯等重要思想后，通过练习课后习题和竞赛试题提高问题分析能力、程序设计能力。基于课程的特殊性，传统的以课堂和教师为中心的教学模式难以满足教学要求，[2]因此，迫切需要改变教学方式，以实践运用为目的，以学生为中心，以培养创新意识为导向，以加强问题分析能力为主线，以算法设计策略为知识单元，结合高校教育工作的现状，追踪国际当前研究热点和技术水平，为学生的后续学习和深造打下坚实基础。

一、传统教学现状及存在问题

（一）教学模式单一

算法设计与分析课程传统的教学模式主要包括两个环节：课堂教学和期末考核。课堂教学以教师讲解为主，学生课堂参与度较低，独立思考不足。期末考核方式单一，以试卷形式为主，无法全面考核学生的实践应用能力和创新能力，[3-4]对于兼具理论性与实践性的算法分析与设计课程缺少多样化和立体化，难以有效发挥教学的作用。培养学生学习主动性是提高教学质量的关键，包括学生在学习过程中主动提出新问题、新算法。

（二）未考虑不同学生的基础

程序汇编语言、数据结构等课程是算法设计与分析课程的基础，[5]在设计算法解决实例问题的过程中，离不开数学，如问题规模、复杂性的分析等，更离不开数据结构，不同学生的基础可能差别较大，基础较薄弱的学生可能出现课上难以听懂或掌握某个算法后难以编程实现的情况。传统教学模式缺乏对不同基础学生的区分对待，未将学生作为教学主体，教学弹性和灵活性不足。

（三）课时短，课程本身难度大

课程的内容兼具深度和广度，对学生的抽象思维能力、逻辑思维能力、灵活运用算法解决问题的能力要求较高，且由于课程重在理解，死记硬背的学习方法难以奏效。课程的学习不仅要掌握算法设计的方法，还要能解决实际应用问题，这对学生的逻辑思维和数学有一定要求。[6]在课堂学习中，面对抽象的算法思想和枯燥的数学推导，基础不牢的学生无法跟上教师的进度，造成一知半解和学习兴趣的丧失。在课时普遍不足的情况下，课程教学很难涉及所有的算法思想和经典实例问题。

（四）互动少，反馈不及时

课下学生很少反馈学习情况，教师不能及时追踪学生的掌握情况。由于课时短以及学生基础参差不齐，对于某类算法，学生可能还未进行充分的实例编程练习就进入下一类算法类型的学习，从而无法充分消化，导致滚雪球情况的发生。师生的互动是保证教学质量的重要环节，教师应及时跟进和了解学生理论知识部分的掌握情况，同时关注学生在上机实践过程中遇到的问题和困难，及时引导、纠正错误。

（五）考核方式单一

传统的考核方式重理论轻实践，原因在于，平时的教学中在实践部分的投入不够，学生的编码训练不足，在最终考核时难以将算法理论和算法思想落实到实践运用中。因此应改革考核方式，加大实践比重，同时在教学过程中引导学生多阅读优秀代码和程序设计方法，从练习模仿别人的程序开始逐渐过渡到独立设计完整程序，以练促学。

二、算法设计与分析教学模式改革的必要性

与其他专业性课程相比，算法设计与分析课程需要构建一套系统性的教学体系，其中实践环节是关键，没有实践，学习毫无意义。每学完一个新算法或新题目，都应该把它运用起来，这将有助于长期的记忆和更深的理解。当学会一个新算法后，及时做几道相关练习题。练习应该分两个阶段进行。首先是当你第一次学习某个新算法的时候。在这个阶段，应该专注于真正理解所涉及的内容以及所用的算法为什么有效。第二阶段是在你对这些概念感到满意之后。在这一点上，你应该给自己计时，争取越来越快的解决时间。在课程开始的几天，根据问题的难度，可能要花费15-45 分钟内设计出有效算法解决一个问题。在课程开始后的几周后，这个时间应该开始减少。经过一两个月的持续练习(不仅仅是时间流逝)，学生应该能够按时解决相当数量的问题。在学习的前期，学生首先要阅读别人已实现的算法，这一过程应专注于理解它为什么以这样的方式实现，而不是试图记住确切的代码。

为保证每个环节的顺利进行，提高教学质量，迫切需要对传统单一、被动的教学模式进行改革，构建一套立体化的教学体系，充分发挥教师、网络、教材和算法竞赛的作用。该立体化教学模式的四阶段框架图如图1 所示。

在教学过程中，教师始终需要将“复杂问题简单化”的理念贯穿于教学的四个阶段，通过挖掘算法本质和列举通俗易懂的事例使学生深刻理解和掌握原理和概念。以动态规划为例，动态规划是一种通过将复杂问题分解成更简单的子问题来解决复杂问题的方法，思路是先解决子问题并记住它们的结果，利用子问题的结果来快速解决复杂的问题。比如，在一张纸上写下“1+1+1+1+1+1+1+1 =”，计算机结果为8，接着在左边写下另一个“1+”很快就得到9 这个答案，利用动态规划的思想，得到9 的过程不需要把之前的过程重新计算一遍，因此简单地说它是一种“记住结果以节省时间”的方式。以上是动态规划的直观理解，另一个重要的问题是理解该策略的适用场景，以及哪些情况不适用。如上所述，如果一个问题可以分解成子问题，这些子问题可以分解成小得多的子问题，并且其中一些子问题有重叠(即需要计算以前计算的值)，且问题的主要目标是通过存储子问题的结果来减少值的计算的重复，这时可以考虑动态规划。需要指出，动态规划不应与递归相混淆，递归是一种通过用函数的其他值直接或间接表示该函数的值来寻找解的方法，这种函数被称为递归函数，它遵循自上而下的方法。动态编程只不过是带有记忆的递归，即计算和存储值，这些值可以在以后访问以解决再次出现的子问题，从而使代码更快并降低时间复杂性，这里的基本思想是通过有效利用空间来节省时间。递归算法代码直观简洁，而动态规划使用空间来存储子问题的解供后续的计算使用，从而节省时间。

综上所述，在教学中应先以通俗易懂的例子介绍算法原理和要点，之后逐步引申，同时注意不同算法之间的联系和区别，逐渐设计出高效的算法。充分理解原理是灵活运用的前提，算法类型和数据对象可以千变万化，当遇到一个无法用现有算法和数据结构很好解决的新问题时，怎样构造有效的问题求解方法是学习过程中的重点问题，只有掌握了算法设计的思想，才能设计出解决问题的算法。

三、立体化教学模式的四个阶段

（一）课前阶段

课前阶段是课上阶段的必要准备，离散数学、数据结构或c++等相关课程知识不扎实的学生可以充分利用课前阶段及时进行相关内容的回顾和补漏，提高课上学习效率。此外，教师每次上课前提前几天下发本次课程的相关学习内容，给学生预留充分的时间明确学习方向和学习重点，学生在课前做好相关准备工作，提前熟悉教材和教学内容。同时，教师引导学生充分利用网络资源，对于难点问题通过查阅相关书籍和观看网络教学视频等方式解决。同时建立网络学习交流平台或群组，方便师生间的互动交流、及时反馈和跟踪学习情况。

（二）课上阶段

课上采用小组讨论方式，根据课前的相关准备，每次课多位同学轮流讲解一部分内容，讲解时可以配合ppt、演示视频和板书等，学生在讲解某类算法时可以结合其应用背景，把抽象的算法和现实问题相联系，加深对算法思想的理解和记忆。教师在讲解过程中或讲解结束后进行提问和补充，争取所有同学都能参与讨论。此外，教师和学生在讲解某类算法的思想或应用实例时可以前后对比，联系贯通，这样才能更深入理解各种算法的特点和对具体问题的适用性。比如具有最优子结构的0-1 背包问题，[7-8]动态规划是解这一类问题的常用方法，由于问题本身的性质，贪心算法却只能得到局部最优解而不能产生整体最优解。对于单船最优装载问题，利用重量最轻的货物先装船的贪心策略，最终可以产生最优解，且该方法比动态规划效率更高。

（三）课后阶段

课后学生通过上机对典型问题进行编程练习，题目选取从易到难，循序渐进，逐步培养算法分析和设计的方法和技巧，避免一开始产生畏难心理而失去兴趣。在逐渐熟悉算法原理后学生应尝试独立设计和编写完整代码，养成良好的程序设计习惯。对于学有余力的学生，教师鼓励其参加天池、挑战杯、百度之星等国内竞赛和ACM/ICPC、kaggle 等国际竞赛，旨在加深对算法的理解、加强学术交流、培养团队协作精神、逐步培养程序设计思维的同时将所学付诸实践。教师则以“教练”和“导师”的身份对学生开展指导，提供赛事上的建议和帮助。学生通过查看比赛排行榜还可以对自身水平有一个定位，明确努力方向。教师还应引导学生查阅算法设计领域的最新研究成果，了解最新的研究热点和动态。

（四）考核阶段

考核方式采用试卷与论文相结合的方式，试卷为辅，测查学生对基本理论知识的掌握，论文为主，检验学生的实践应用能力和创新能力。试卷以算法分析题为主，主要分析算法的性能和复杂性。学生首先应能根据问题特点把其归为某一类特定问题，并能找到对应的算法，如背包问题可以用动态规划、回溯法等，另外算法的适用性需要根据具体问题进行具体分析。论文的方向可以是对实际应用问题用算法进行实现或解决，并思考算法的改进和优化方法，这就要求对算法的原理有较深入的理解。此外，问题的解决最终还是要落实到代码上，因此充分的上机实操也是必不可少的环节。论文形式的考核方式虽然对学生来说有一定难度，但能很好地激发学生去主动思考、积极创新，对所学算法活学活用。

在目前的教学模式中，很多学习内容集中在课上完成，而要依靠有限的上课时间难以达成课程的教学要求。本文提出的立体化教学模式把学习内容分散到四个阶段，分别为课前阶段、课上阶段、课后阶段和考核阶段，每个阶段同等重要且均是不可缺失的学习环节。做好每个阶段相应的任务对切实掌握程序设计的方法和提高对实际问题的分析解决能力具有重要作用，是使学生在知识、方法、应用、创新四个方面能力全方位提高的必要途径。