应用型本科院校《算法设计与分析》课程实践教学改革研究

2016-10-10赵晓丽

长治学院学报 2016年2期

关键词：背包算法教学模式

赵晓丽

（长治学院计算机系,山西长治046011）

应用型本科院校《算法设计与分析》课程实践教学改革研究

赵晓丽

（长治学院计算机系,山西长治046011）

结合应用型人才培养的目标和理念，文章分析了《算法设计与分析》课程教学模式存在的弊端，提出了基于问题式实践教学改革方案，探讨了问题式实践教学模式在课程教学中的重要性。

问题式；实践教学；教学模式

引言

算法设计与分析是衡量软件性能优劣的一个核心指标，也是应用型本科院校中计算机专业本科生的一门必修的专业基础课程。课程通过对经典算法思想、特征与求解步骤进行学习，使学生能够掌握相关理论和使用技巧，培养学生正确分析算法的时空复杂性的能力和解决实际问题的算法设计能力，并从众多方案中择优求解，对已有算法进行分析改进，为编写出高效程序、开发优秀软件奠定坚实的理论基础。因此，算法设计的思维逻辑培养成为计算机专业人才培养的重要环节。在教学过程中为了增强学生的实践应用能力，就迫切需要进行实践教学的改革，从而构建符合应用型本科院校发展的教学模式，推动高校计算机专业教育的教学改革。

文章以“算法设计与分析”这门课程为研究对象，通过课堂教学模式多样化的尝试，针对课程在应用型本科院校教学中的教学内容、教学模式、实验项目训练验、综合应用四个方面问题，提出建立“问题+算法策略+实验”的实践教学模式。

1　教学现状

《算法设计与分析》作为计算机专业的课程，目的是为了让学生对算法的基本理论，培养学生对实际问题的算法设计思维[1]。课堂采用理论教学，尽管学生具备数据结构和编程语言的基础，但课堂教学之后，学生运用所学算法策略进行独立自主地求解实际问题的能力十分欠缺。针对这种情况，对长治学院计算机系2014级学生进行问卷调查，调查结果表明学生对课堂教学的接受情况不理想，具体情况如下所示：

人数所占比例接受程度56%30%～50% 25%>60% 9%10% 10%>80%

从结果看，有将近一半的学生只能接受知识的30%-50%，1/4的学生接受60%以上，只有1/10的学生能接受80%以上。由此可以看出学生接受情况并不是很好。课堂上虽然是多媒体ppt+板书讲解的教学模式，但教师讲解依然是中心，因此学生只能被动接受。

《算法设计与分析》课程的传统教学模式对课程教学效果不好，随着各种算法内容的加深学习，学生会感觉越来越力不从心。这样的教学模式太过于单调，只是一味的以枯燥的理论知识为主进行讲解，学生也只能被动的接受算法思想和强行记忆算法步骤，极大地降低了学生的学习兴趣和积极性。其次“算法”教学方法上仍侧重理论教学而忽视实践教学，在学习算法设计策略和分析算法的时候，互动缺乏，导致课堂教学质量低。在几乎没有实验课的课堂教学中，缺少综合应用算法的实践性应用项目，使得学生面对实际问题只能通过网络来寻求解决方法。这样的教学模式既不能培养学生的创造性思维，也不能提升解决实际问题的应用实践能力，根本不能完成教学目标，所以，对《算法设计与分析》课程的教学模式进行实践性教学改革是十分重要的。

2　教学改革方案

针对课程教学过程中存在的问题，通过引入问题式实践教学模式，激发了学生的学习热情，教学效果十分明显。因此，在教学中按照“问题提出、算法设计、实验实践”的教学模式进行实践性教学是非常有必要的。具体实施方案如下。

2.1优化教学内容

算法设计与分析这门课程，需要学生具备良好的抽象逻辑思维能力及程序设计技巧。尽管学生之前都学习过“数据结构”和“高级语言程序设计”这两门课程，起初学习起来也都有兴趣，但随着课程内容的深入学习，难度增大，导致学生学习困难。

因此，需要把课程中的各个算法思想的精华部分提取出来，对所讲的教学内容进行优化。每个算法都有各自的思想、步骤、基本特征要素,但彼此也有一定的关系。这样我们就可以在学习每个算法的时候与所掌握的算法进行对比,找出各自的相同点和不同点，不仅加深对算法的理解，使学生掌握算法基本特点、问题适用性及在具体例子中的灵活应用，也为设计出效率较高的算法、编制程序、分析和优化算法打好坚定的基础。

2.2问题式教学模式[4]

通过一些应用性强的实例，激发学生自主学习的兴趣，帮助学生构建对经典算法知识的认知体系。如：分治算法、动态规划算法和贪心算法，可以根据之间的关联对比进行学习。把重点放在对算法的设计上，让学生学会如何对类似问题进行算法的选择、设计与实现[3]。

比如最优子结构性质，这个知识点就贯穿在这三个算法中。通过0-1背包问题和普通背包问题的算法应用，进行多方面的对比分析，把分治算法、动态规划算法和贪心算法的应用要点进行串联，使得学生对这三个算法策略有了非常清晰的认识。这种问题式启发教学可以让学生通过模仿，进行实际问题的分析与算法应用求解，从而使学生有自主独立学习的兴趣。

2.3建立开放实验项目训练

针对实践应用与理论教学严重脱节的弊端，笔者采用了开放式实验项目训练模式[2]，把学过的理论知识通过问题分析、算法分析、算法设计、算法实现这四大步加以实践。在这样的开放实验环境中，师生充分互动，不仅提高了教学质量，也大大加深了学生对知识点的理解与应用。

2.4增强经典算法的综合应用

除了以上方面，还可以在教学中选取一些经典问题,采用不同算法加以实现。对实现的各种算法的复杂度分析，并与实验结果进行比较，从而正确评价每个算法的优缺点。不仅如此，通过对这些经典问题的综合分析，可以对已有的条件进行改变，正确引导学生对问题的深层次思考,培养他们的思考能力、逻辑能力及动手能力,加强经典算法的综合应用。

3　问题式实践教学模式的案例设计

为了进一步说明上述教学模式，笔者通过一个教学案例《贪心算法—普通背包问题》来说明教学改革方案的执行，案例设计如下。

（1）问题的确定。

问题:在给定n种物品选择一种装包方案使得装入背包中物品的总价值最大?其中，物品的重量（Wi），价值（Pi），背包重量（M）。在动态规划算法中对《0-1背包问题》进行了动态规划步骤的求解。解是（X1,X2,…Xn）,Xi=0,1

在此基础上提出新的问题-普通背包问题，它与0-1背包问题类似，只是物品的装入状态0≤Xi≤1,直到背包装满为止。这2类问题都具有最优子结构性质，极为相似。但由于背包可以装入物品的一部分，那么普通背包问题还能否用动态规划算法求解呢？问题提出来，为引入新的算法打好基础，这就使得基于问题的教学模式很恰当。

（2）情境创设，提出问题

结合一个实际的例子，背包重量M=20，物品n=3,重量、价值分别为（w1，w2，w3）=（15,10,15）；

由教师直接抛出问题，采用穷举法求解。

（3）分析问题

根据问题的特点，按照生活实践经验，我们给出三种求解思路。

①以重量wi从小到大排列输入”为量度标准

②以“价值pi从大到小排列输入”为量度标准：

③以“单位重量价值pi/wi从大到小输入”为量度标准：

学生们分组讨论，分析各种实际情况的出现，最终给出解决问题的最优步骤，以“单位重量价值pi/wi从大到小输入”为量度标准得出的结果是装包价值最大的。

（4）解决问题，确定算法。

结合已学习的知识，依据刚刚得出的结论，找出解决步骤的主要性质—贪心选择性质和最优子结构性质。最终给出普通背包问题的算法步骤。①按照物品的单位重量的价值进行由高到低的排序；②依贪心选择策略，选择单位重量价值最高的物品尽可能多的进行装包；③若此时背包未满，继续选择单位重量价值次高的物品并尽可能多地装入背包；④重复第三个步骤，直到背包无法再装入物品为止。

（5）程序展示

根据算法步骤，给出程序代码实现。

（6）总结、概括。

总结解决问题的思路，概括算法设计的方法，引导学生们对实际问题的算法设计过程进行复述，将问题式思维过程用算法步骤描述出来。

4　结论

文章结合在教学中的一点教学实践摸索，对算法设计与分析的教学改革进行了探讨，提出了基于问题式的实践教学模式。通过该教学模式的改革方案的实施，较大程度的改善了此前的教学现状，不仅改变了学生被动学习的学习方式，提高了教学质量，也使得教学的互动过程更加和谐。这对于转变传统的教育观念和培养学生自主学习的能力起到了主要的作用。

［1］王晓东.算法设计与分析［M］.北京:清华大学出版社,2012.

［2］徐楠.基于项目驱动的Java课程教学改革研究教育与职业［J］.2011,5(14）：26-27.

［3］肖小克,陈莉.《算法设计与分析》实践教学探讨［J］.福建电脑,2009,5(10):210.

［4］袁宇翔,基于问题的教学模式的构建与应用探究［J］.教育与职业,2013.2.