“算法设计与分析”课程的STT教学模式探讨

郭丽清　郭一晶

摘  要： 为了提升“算法设计与分析”课程的教学质量，引入STT教学模式进行教学改革。针对教学过程中存在“弱”、“难”、“杂”的问题，提出“奖”、“例”、“享”的课堂互动教学方法。教学实践证明，该方法能有效激发学生学习兴趣，提升学生课程参与度，提高學生分析问题、解决问题的能力，取得较好的教学效果。

关键词： 算法; 弱难杂; STT; 奖例享

中图分类号：G421;TP312          文献标识码：A     文章编号：1006-8228（2020）06-73-03

Abstract： In order to improve the teaching quality of "Algorithm Design and Analysis" course， this paper introduces the STT teaching mode for teaching reform. To address the problems of "weak"， "difficult" and "miscellaneous" during teaching process， the interactive classroom teaching methods of "award"， "example" and "enjoyment” are proposed. It has been proved by practice that the methods can effectively stimulate students' interest in learning， vigorously enhance students' participation in courses， improve students' ability of analyzing and solving problems， and achieve better teaching results.

Key words： Algorithms; weak; difficult and miscellaneous; STT; award; example and enjoyment

0 引言

众所周知，程序=数据结构+算法。算法的本质是一个问题的解决方案。对于同一个问题，通常有多个解决方法。不同的方法，解决问题的效率差异很大。设计一个高效的程序不仅需要编程小技巧，更需要合理的数据组织和清晰高效的算法[1]。

“算法设计与分析”是计算机学科的核心课程，主要研究计算机及其相关领域中的一些常用算法。通过本课程的学习，学生对算法的基本概念、描述方法、设计过程以及计算机领域解决的问题类型等有一个全盘的了解;掌握蛮力法、分治法、减治法、贪心法、动态规划法、回溯法等算法设计技术，进而运用这些方法来解决一些常用的实际问题;同时，学生可学会分析算法、估计算法的时间复杂性和空间复杂性，以便理解并科学评估有关算法质量，从而提高程序设计的质量。该课程对学生将来从事计算机系统结构、系统软件和应用软件的研究与开发提供一个广泛扎实的计算机算法知识基础。算法设计与分析是计算机学科公认的最难课程之一，如何激发学生的学习热情，加深学生对算法设计策略的理解，进而提升教学质量和教学效果，一直是课程教学过程中的重点。本文从当前教学中存在的问题分析着手，探讨STT[2]教学模式在算法设计与分析课堂教学过程中的实际应用，以期给同类课程教师提供一些借鉴与启发。

1 当前教学中存在的问题

算法设计与分析是一门理论性与实践性兼顾的课程，在学习该课程的过程中需要注意理论与实践相结合，对理论性较强的部分，需通过多次练习加以巩固理解，需要充分地上机练习，结合应用实例在具体计算机环境中加深对理论知识的理解。

本课程主要采用探究研讨法、讲练结合等教学方式。每次讲授一种新算法，先介绍算法设计策略的基本思想，然后从解决计算机中的经典问题和生活中的实际问题入手，由简至繁、层层递进地讲解，通过对设计策略的反复应用，加深学生对算法设计思想的理解。此外，我们对某些经典问题甚至采用不同算法进行解决，对于熟悉的问题，学生可以更快地理解不同算法的核心思想和设计要点，同时也让学生更加深刻地体会到一个问题可以有不同的解决方案。即便这些都已考虑，还是由于课程难度、现实学情等一些因素，教学过程依然存在一些问题。

⑴ “弱”——理论学习的畏难心理，积极主动性较弱

算法是一门抽象性的学科，需要大量的理论基础知识，涉及不少数学知识和相关符号。在历年的教学过程中，了解到学生们普遍反映理论知识枯燥、算法很难学，并在学习过程中产生畏难情绪，影响了他们主动学习算法这门课程的积极主动性，进而影响了课程的教学质量和教学效果。

⑵ “难”——基础水平参差不齐，课程内容设计难度大

算法是计算机相关专业学生的必修课程，一般开设在大二下学期。其先修课程包括程序设计基础（如：C、C++、Java之类）、离散数学、数据结构等。先修课程比较多，每个同学掌握程度略有差异，学生的水平参差不齐。

这样的学情/状况，给教学过程特别是课堂内容设计带来较大的难度。关注基础薄弱同学，基础较好接收能力较强的同学无法得到有效提高;拔高课程内容，容易导致基础较弱的同学跟不上，进一步产生厌学情绪，严重者甚至放弃该课程。为此，教师需要投入大量的时间，从海量的算法中挑选出合适的实例，构建阶梯式的学习题库。

⑶ “杂”——理解现有的算法，但无法应用于复杂的实际问题

高等教育重在培养应用型人才，学习算法的核心目的是为了让学生能够应用相关算法解决实际问题[3]。然而，从实际成效看，大部分学生即使已经学习并理解现有的算法，但是在遇到复杂的实际问题时，很难抽象出背后的算法模型。

比如某次上机测试实验，输油管道问题[4]，某公司计划建一条由东向西的主输油管道。该管道需穿过一个有n口油井的油田。从每口油井都有一条输油管道沿最短路经与主管道相连。若给定n口油井的坐标位置（x，y），主管道位置选择哪里可以使得各油井到主管道之间的输油管道长度总和最小的位置？该问题的本质是一个对n口油井y坐标的排序问题，进一步解析，问题可以转化为如何快速找到y坐标值的中位数，该位置即为总输油管道建立的最优选址位置。经过分析，我们采用快速排序[5]的原理在线性时间内即可实现，具体如图1所示。但是在有限的考核时间内，很多学生没有很好地完成。

2 STT教学模式探讨

TTT和STT起源于英语课堂教学，TTT（Teacher Talking Time）代表教师在教学中讲授中所占用的时间，STT（Student Talking Time）代表学生在课堂中发言中占用的时间。STT教学模式本质是一种经典的互动教学模式。在教师引导下，师生、同学之间采用对话、研讨和交流的方式，形成良好的互动教学氛围，充分调用学生的积极主动性，培养学生自学能力，开发学生的创造思维[6]。传统的英语课堂以TTT为主，近几年来不断增加课堂的STT部分。实践表明，适当增加教学中的STT，对英语教学质量的提高有明显的促进作用[2]。算法设计与分析课堂，教师为了构建知识理论体系，经常采用“灌输式”教学方法，即典型的TTT为主的教学模式。

我们在教学过程中，尝试引入STT教学模式，引导学生思考活跃学生思维，激发学生的学习热情，发挥学生积极主动性，进而更好地理解算法设计的本质思想。主要采用以下几个方法。

⑴ “奖”——建立合适的奖励机制，提升学生课堂参与度

学习的困难会降低学生的学习热情，进而影响教学质量。课堂激励可以有效提升学生的学习兴趣[8]。在课堂设计过程中，加大教学过程管控分值，提高学生课堂参与度。比如：对于参与专题分享的同学，平时分加3-5分。外在的激励一定程度上，提高了学生参与的积极性。激励理论包括外在激励和内在激励。内在激励往往具有更稳定、持久的驱动力。内在激励是指学习本身带来给人的激励，包括学习的兴趣、自信心、成就感等。对于课堂中积极互动的同学，不管怎样都先给予鼓励，愿意分享想法是一种勇气，也是一种进步。良好地课堂氛围，会促进学生学习的兴趣。思考越多，回答到点上的可能性就越大，学生的自信心、成就感也会随之提高。

⑵ “例”——生活实例入手，激发学生学习兴趣

兴趣是最好的老师。在课堂中，适当增加生活的实例，通过解决实际问题，激发学生的学习兴致。每次介绍新算法时，从生活的实例或历史典故入手，引出算法設计策略的基本思想。

例如，百钱百鸡问题引入蛮力法的设计的思想，然后逐步引导学生对算法进行优化，加深对蛮力法的理解。又例如，学习动态规划算法时，通过货币找零问题，温习贪心算法的核心思想，引导学生思考如何解决不一定时最优解问题，导入动态规划的设计理念。对于涉及较多的数学符号、公式的经典问题，通过对实际例子的讲解，降低学生对理论学习的畏难情绪，结合课堂练习，加深学生对知识的理解和巩固。如：经典的TSP问题[5]，从小蜜蜂采蜜开始讲解，衍生到学生毕业旅行、城市的道路交通规划、快递送货、互联网中的CDN加速等应用。

这些尝试有效地提高了学生的学习兴趣，培养了学生分析问题、解决问题的能力。值得注意的是，在课堂中注重提问艺术，根据不同学生设置不同的问题，引导学生思考，让学生尽可能有的说，愿意说。

⑶ “享”——任务驱动专题分享，充分发挥学生主观能动性

采用类“翻转课堂”[7]教学模式，结合课堂上已经讲过的内容，提前2-3周布置相关主题并提供相关参考资料。自主组队报名为主，教师指定为辅参与模式。准备过程中，与学生保持交流互动，引导学生深入思考，学会归纳总结，分析算法的时间复杂度和空间复杂性以及这类算法生活中适用的场景。排序问题专题分享，加深了学生对一题多解思想的理解，巩固相关算法的设计思想。0-1背包专题分享，提供背包9讲相关资料，专题小组的“小老师们”从0-1背包入手，重点分享了完全背包、多重背包、树形背包。学生从小偷偷珠宝问题入手，逐层递进地分析问题，在算法优化过程，引入二进制思想，将问题“退化”为0-1背包问题的求解，树形背包延伸到学生如何实现最优总学分选课。这期分享异常精彩，收获良多。每个人思考问题的思维差异性很大，教师因为已经很熟悉，有时忘记当年是怎么理解这个问题。

通过“课堂翻转”，学生分享的模式，更好地了解了学生思考方式，为后续“以学生为中心”的课堂提供了借鉴。参与分享的学生也表示，通过参与主题分享加深了自己对算法的理解，同时锻炼了团队协作意识。此外，每次同学分享的内容，也拓展了本课程的学习题库。

3 总结

算法设计与分析是计算机学科的核心课程。本文深入剖析了该课程存在的一些问题，尝试引入STT教学模式，进行针对性的教学改革实践。通过应用算法解决生活实际问题、任务驱动学生专题分享、建立合适的奖励机制等方式有效地激发了学生学习兴趣，提升了学生分析问题解决问题的能力。特别是小组式的专题分享，锻炼了学生的表达能力，增强学生的团队合作意识。从期末考核结果看，学生成绩也有所提升。在后续的教学工作中，考虑与学校ACM竞赛结合，以赛促学，培养学生创新实践能力。

参考文献（References）：

[1] 孙俊，吴小俊，李岳阳.《计算机算法设计与分析》教学方法研究[J].科技信息，2013.23：173，217

[2] 张曼，李迎旭，李超.论英语课堂教学中的TTT和STT[J].课程教育研究，2013.10：81

[3] 张铭，耿国华，陈卫卫，胡学钢.数据结构与算法课程教学实施方案[J].中国大学教学，2011.3：56-60

[4]  洛谷.P1862输油管道问题[EB/OL].https：//www.luogu.org/problemnew/show/P1862

[5] 王红梅，胡明.《算法设计与分析》（第2版）[M].清华大学出版社，2016.

[6] 孙泽文.课堂互动教学研究[D].华中师范大学，2008.

[7] 何克晶，张星明，郑运平.算法设计与分析课程全方位实践教学改革探索[J].计算机教育，2017.2：45-49

[8] 严明贵.课堂激励是培养学习兴趣的推动力[J].教学与管理，2012：121-123