计算思维与实践编程能力培养并重的算法设计与分析教学

季晓慧 姚国清 张玉清 夏军宝 郑春梅

摘要：讨论了算法设计与分析教学过程中对学生计算思维能力培养的具体方法及将在线评测系统引入编程实践教学中的具体应用方法等。

关键词：算法设计与分析;计算思维;在线评测;考试

中图分类号：G642.

文献标识码：A

文章编号：1009-3044（2020）04-0070-02

收稿日期：2019-11-27

基金项目：2019年度中国地质大学（北京）一流课程建设项目

作者简介：季晓慧（1977-），女，黑龙江七台河人，副教授，博士，主要从事计算机教学和科研工作。

Cultivating the Computational Thinking and Practical Programming Abilities in Algorithm Design and Analysis Teaching

JI Xiao-hui，YAO Guo-qing，ZHANG Yu-qing，XIA Jun-bao，ZHENG Chun-mei

（School of Information Engineering，China University of Geosciences，Beijing 100083，China）

Abstract：This paper gave out the methods on cultivating the computational thinking ability in algorithm design and analysis teaching.Methods that uses online judge system in cultivating practical programming ability in algorithm design and analysis were also discussed.

Key words：Algorithm Design and Analysis;Computational Thinking;Online Judge;Examination

算法被誉为计算机学科的灵魂，是支撑计算机科学的核心和基石，是计算机科学研究的永恒主题[1]。因此算法设计与分析课程也处于计算机科学与技术学科的核心位置，是计算机学科最重要的专业基础课之一，在国内外各大高校计算机专业课中都处于核心地位。算法设计与分析课程讲授使用计算机解决实际问题时可以采用的经典方法，如递归与分治法、动态规划法、贪心法、回溯法、分支界限法等，并讲授各种算法的基本原理、复杂性分析、实现方法和应用实例等。通过该课程的学习，使学生掌握常用的算法设计分析、实现和比较方法以及计算复杂性分析理论和评价算法性能的标准，培养学生的问题抽象和建模能力以及能够针对具体实际问题设计出高效算法的实践能力。算法设计与分析课程既包含抽象的理论，又强调算法的实践，对于提升学生的逻辑思维能力和编程解决实际问题的能力有着非常重要的意义[2]，能为学生进一步分析和解决计算机科学与技术领域的复杂工程问题奠定良好基础。

算法设计与分析课程兼具理论性与实践性强的特点，实际教学中易出现要么过于强调理论而忽略编程实践要么过于强调编程实践而忽略算法背后的计算思维的情况;或者存在让学生编程实践过程中缺乏有代表性、趣味性强或者有实际意义的题目的情况，进而学生对课程没有兴趣;并且算法设计与分析课程对前序课程，比如《数据结构》《离散数学》《程序设计语言》等有依赖性，而这些前序课程本身也有一定难度，会存在学生基础不够牢固的情况，进而影响学生对课程的理解。针对上述问题，可以在教学过程中注重以下几个方面：

1 注重学生计算思维能力的培养

计算思维由美国卡内基·梅隆大学周以真（JeannetteM.Wing）教授于2006年第一次明确提出并将其解释为“‘运用计算的基础概念求解问题、设计系统和理解人类行为的一种方法”，并预见计算思维将成为像读、写、算一样，每个人必备的认知技能。有学者认为计算思维是计算机科学最具有基础性和长期性的思想，涉及逻辑地组织和分析数据、分解问题，算法设计、程序化的执行技巧，并且可以将问题解决过程拓展到社会和人文领域[3]。计算思维能力具体包括以下9个能力点：问题的符号表示、问题求解过程的符号表示、逻辑思维抽象思维、形式化证明、建立模型、实现类计算、实现模型计算、利用计算机技术[4]。而算法设计与分析解决问题的过程是：理解和把握问题背景及其相关知识，并用符号化的语言对所求解问题进行表示;设计解决问题的方法并用符号化的语言描述方法;分析所提方法的复杂度并进行适当改进;选择能够表达问题并与解决方法相适应的数据结构;编写代码;迭代调试;最终完成计算机的问题求解。可见算法设计与分析过程覆盖了计算思维所要求的能力点，是计算思维的具体体现。因此需要在具体的教学过程中强化上述思维过程，将计算思维的培养融入教学当中，以提高学生的计算思维能力。

具体在教学过程中应注意以下几点：（1）板书与多媒体教学相结合。即宜用板书一步一步地介绍算法求解某一问题的具体步骤，以让学生更好地掌握该算法求解问题的具体计算思维过程;（2）算法讲授过程中，学生上机实践前，不使用具体的编程语言。宜用伪代码、流程图等形式进行算法的讲述，使学生暂时不被具体的编程细节所累，而是专注于算法思想及其计算思维的理解;（3）强调算法复杂性分析及算法对比。算法讲授过程中注意对算法及其求解具体问题时的复杂性进行分析，培养学生对算法的分析能力，并注意引导学生对所学算法与已学过算法进行对比，以使学生养成评价算法的习惯;（4）注意对前序课程知识的巩固及后序知识的扩展。算法是计算机程序设计的灵魂，许多算法在前序课程的数据结构、程序设计基础等已经讲授，如快速排序、堆排序、最小生成树、单源最短路径算法等，需要在授课过程中进一步指明这些算法思想，使学生强化这些算法背后的计算思维，保持学习的连贯性及扎实性。许多算法，如回溯法、分支限界法等又是后续课程，如人工智能课程的重要知识点，授课过程中也应向学生进行扩展，以提高學生对课程的重视，为后续课程的学习打下良好基础。

2 注重学生实践编程能力的培养

计算机相关学科在算法设计与分析授课过程中除了注重计算思维的培养，也要注重对学生实践编程能力的培养，做到理论与实践并重、理论能够用于实践，使学生真正具备使用计算机解决实际应用问题的能力。在线评测系统是一套 能对程序源代码进行自动评判的计算机应用软件，其通过对学生用网页浏览器提交到服务器的源代码进行在线编译，生成可执行文件并产生输出，并将输出与服务器数据库中的测试数据中的输出文件进行逐字节的对比来判断学生提交程序的正确性，同时对耗时、耗费内存等方面进行评测，并将评测结果保存在数据库中且返回给用户。其除对源代码进行评判之外，还具有用户管理、题库管理、在线比赛及在线讨论等功能，已被众多高校用于计算机辅助教学[5]。在线评测系统具有严谨、通过对已求解题目数量的累积及所在排名的实时查看激发学生的上机实践自主性及实践编程兴趣、能形成学生之间的讨论和交流氛围等特点，因此十分适于算法设计与分析课程的实践教学。

在使用在线评测系统进行算法设计与分析的题库建设上可以采用以下几种方式：（1）将教材经典问题转化为适于进行在线评测的实践题目;（2）挖掘整理在线评测系统中的原有题目，将其中与算法设计与分析课程知识点结合紧密的题目用于课程实践;（3）鼓励优秀学生结合课程所学知识点为题库出新题，新题一旦被采用可以以加分作为鼓励。

在具体实践上，每次包含简单、中等难度及难题三类，以让不同层次的学生都能得到训练。并将每次实践完成情况按所通过题目的数量进行排序，折算后计人最终成绩，以加强学生对编程实践的重视。实践过程中，教师要以抽查等方式了解学生掌握情况，及时发现问题并予以纠正。在线评测系统还用于学完所有算法后的综合上机考试，题目覆盖所有知识点，要求在平时上机实践的两倍时间内完成指定题目。

算法设计与分析要求以时间复杂度尽量低的方法及程序解决实际问题，因此对同一问题的不同算法分析与对比尤为重要，需要学生在学完所有算法后对某一典型问题采用不同算法进行求解并予以分析比较并完成综合报告。学生的最终成绩由平时成绩（出勤、讨论及讲解、课后作业）20%+上机实践及报告55%+综合上机10%+综合报告15%=100%进行评定。

3结论

算法設计与分析课程兼具理论与实践性，教学过程中需要既注重计算思维能力的培养，又注重实践编程能力的培养。可以通过板书与多媒体教学相结合、算法讲授过程中，，学生上机实践前，不使用具体编程语言、强调算法复杂性分析及算法对比及注意对前序课程知识的巩固及后序知识的扩展等方式培养学生的计算思维能力;通过将在线评测系统应用到编程实践中，培养学生的实践编程能力。最终为学生以高性能的算法解决实际应用问题打下良好基础。

参考文献：

[1]王红梅，胡明.算法设计与分析（第2版）[M].北京：清华大学出版社，2013：7.

[2]张远平，邱丽娜在算法设计与分析课程教学中融入计算思维[J].价值工程，2016（8）：245-247.

[3]狄长艳，周庆国，李廉.新工科背景下对于计算思维的再认识[J]中国大学教学，2019（7）：47-53

[4]教育部高等学校计算机科学与技术教学指导委员会.高等学校计算机科学与技术专业人才专业能力构成与培养[M].北京：机械工业出版社，2010：25-36.

[5]季晓慧，张玉清.C程序设计教学中的在线评测系统应用[J].电脑知识与技术，2014，10（7）：1465-1466.

[通联编辑：王力]