计算机教学论文：聚焦计算思维的算法分析与设计课程教学改革

计算机教学论文：聚焦计算思维的算法分析与设计课程教学改革0引言算法是计算机科学中最具方法论性质的核心概念，被誉为计算机学科的灵魂。图灵奖获得者NiklausWirth提出：算法+数据结构=程序，强调了算法在计算机领域的重要性。在现实生活中，算法、算据和算力组成了人工智能技术的三要素；算法的新颖性和性能决定了学术论文在高水平期刊或会议上发表的可能性；算法能力测试是研究生复试和求职面试等场合常见的环节。因此，学习并掌握好算法相关知识，对一名本科生的综合能力培养和职业发展来说非常重要。国内外各大高校计算机专业在培养方案中，普遍开设了算法分析与设计（以下简称算法）课程，该课程以高级程序设计和数据结构为先导课程，又为人工智能等专业课程提供算法支撑，是培养方案的重要枢纽之一。算法课程既包含抽象的理论，又强调算法的实践，对学生的逻辑思维和计算建模等能力有较高的要求，因此有必要聚焦计算思维，开展面向能力提升的课程教学改革。1课程教学和改革现状1.1共性问题目前，采取小班化策略开展算法课程教学已比较普遍；多数高校选用MIT经典书籍《IntroductiontoAlgorithms》作为教材；依托在线平台开展编程训练取得了良好的教学效果。但在教学过程中，还存在一些共性问题。（1）学生在理论学习时普遍存在畏难心理。算法要求学生不仅掌握算法的实施，更强调对算法原理的理解；一些关键的算法要进行证明，如主方法、最优前缀码等，这需要大量的理论知识，涉及不少数学符号，学生容易感到枯燥和抽象，降低了学习兴趣。（2）学生难以灵活运用算法解决实际问题。学生往往能够较好地掌握教材中的经典问题和相应的算法，并完成课后习题和部分在线训练题，但遇到复杂的现实问题或工程问题时，要么没有思路，要么依赖直觉，无法准确构建输入输出间的解析关系。（3）学生的基础水平和学习需求差异明显。修读课程的学生水平参差不齐，学习动力和学习方法也各不相同，因此处在两极的学生的学习需求通常难以得到精细满足；另外，创新实验活动和程序设计竞赛吸引了部分学有余力的学生，但课程教学和第二课堂缺乏深度结合。（4）课程思政的体现度较低。课程思政是从德智体美劳全面发展的目标出发，培养社会主义建设者和接班人的重要理念和实施路径。本课程作为一门典型的工科课程，课程思政的结合度不足，尚未充分做到课程思政与专业课程同向同行、协同育人。1.2已有研究针对算法课程，已有教师从计算思维、教学模式、课程思政等方面开展探究，显著提升了教学质量。（1）周以真教授于2006年首次提出了计算思维的概念，将其解释为“运用计算的基础概念求解问题、设计系统和理解人类行为的一种方法”；2010年进一步提出计算思维是与形式化问题及其解决方案相关的思维过程。文献中提出具有浓厚计算思维特色的3个核心内容，包括可行性、不精确性和交互性，强调了计算思维在新工科教育中的意义。（2）在教学模式方面，文献中建立“以赛励教、以赛督学”的教学模式，适应程序设计竞赛日益受到重视的现状，同时培养学生的合作和表达能力。针对学生在浅表学习时也普遍存在理解困难的情况，文献中提出了算法课程的翻转课堂教学模式，指出深入浅出地把知识点讲透是实施翻转课堂的关键。为了提升算法课程的教学质量，文献中引入STT教学模式，提出“奖、例、享”的课堂互动教学方法。（3）2016年12月，在全国高校思想政治工作会议上强调：“把思想政治工作贯穿教育教学全过程，开创我国高等教育事业发展新局面”。在计算机专业工程认证中，专业课程对社会、健康、安全、法律和文化等指标点的支撑严重不足，通过专业课程进行课程思政的教育迫在眉睫[7]。文献中提出教师必须挖掘算法背后的一般性规律，提炼算法所蕴含的人生哲理，在潜移默化中培养学生良好的品格和高度的社会责任感。文献中阐述了在融入STT模式的教学各环节开展课程思政的主要方法，并给出了具体案例。2课程教学改革整体架构算法课程的教学重点是面向问题求解，具体求解过程包括理解问题并用符号表达该问题，设计求解问题的算法并用合适的数据结构和程序语言转换成计算机处理任务，优化问题的求解方案并证明方法的正确性，综合运用已有的知识和经验解决更加复杂的问题，这个过程对应了计算思维的9个能力点。笔者将算法课程的计算思维能力归纳为4类：问题建模、算法实现、优化迁移和分析证明。针对教学过程中总结的问题，以计算思维培养为焦点，围绕“1个大纲、2个网站、3套资源库、4种能力”的主线开展教学改革，整体架构如图1所示。通过教学改革，课程能够实现知识传授、能力培养与价值引领的有机统一。3课程教学改革实践3.1以计算思维为导向，完善教学内容的设计计算思维能力可以归纳为4个方面：基础理论和基本方法的分析证明思维（分析证明）；典型问题的数学建模和抽象思维（问题建模）；实现解决方案并得到计算结果的思维（算法实现）；优化解决方案和在复杂情形或新场景下的迁移应用思维（优化迁移）。教学内容据此进行重新设计，不再按照教材上的章节顺序讲解（表1），教学时长包括36学时的理论课和18学时的上机实验。表1第2列中的章节信息是指MIT教材的章节；第3列是配套的实验题，来自ECNUOnlineJudge（以下简称EOJ）在线题库；第4列是与理论课内容对应的主要计算思维能力。3.2推行混合式教学，开发多元化计算思维训练资源线上线下混合式教学体现了信息技术与传统课堂教育的深度融合。特别是在疫情期间，“停课不停教、停课不停学”促使教师不断开发和完善在线教学方法。根据算法课程的特点，课程教学采用了2个网站并开发了3套教学资源以支持教学活动的开展。1）2个网站。EOJ平台和大夏学堂分别承担在线实训和在线教学管理的职责。①EOJ平台拥有大量的程序设计竞赛的题目，覆盖几乎所有的知识点。教师根据教学进度选择发布题目，并更新测试点；要求学生提交基于擅长语言所写的代码，运行程序并反馈各个测试点的通过情况；启用防作弊功能。②大夏学堂是学校教务处推行的一个教学管理平台，课程在此平台上发布教学资源、发布和批改作业、记录学生的在线学习过程等。两个平台辅以腾讯会议，保障了课程教学不受疫情的影响，得以顺利开展。2）3套教学资源。除了理论课的教材外，不断开发教学资源以拓展学生的知识面，增强其学习积极性和主动性。3套教学资源包括OJ训练题库、自主学习用的专题实训库和课程思政资源库。（1）OJ训练题库。教师从大量的习题中挑选出合适的实例，按难度构建阶梯式的学习题库。在实验课前1周，教师根据当前的教学内容，选取4道难度呈正态分布的题目发布在EOJ平台，由学生在线下独立完成。（2）专题实训库。教师根据理论课的11部分教学内容，挑选出一些代表性的程序设计竞赛题，详细写出破题策略、解题方法、解题过程、优化分析和代码示例。这部分资料示范了问题解决的全过程，主要供学生自学。同时，根据前沿热点或工程实际，教师精炼提取出一些综合性题目。这些题目有明确的应用背景，须综合运用课程的知识并进行一定的延展才有可能解决。这些习题会提前布置，学生小组在最后一次课上进行演示、探讨。（3）课程思政资源库。教师将工程教育认证涉及的社会、健康、安全、法律、文化和环境问题，与教材的内容相结合，从专业、行业、文化、历史、国内、国际等不同维度挖掘实例。如结合疫情防控网格化管理，讲述分治算法和健康理念；结合网络密码安全，讲述Huffman编码和国家安全；结合垃圾分类和回收，讲述动态规划和环境保护。3.3多措并举，全方位提高计算思维能力针对计算思维的4种能力，教学过程通过不同的渠道和方式进行训练和强化。1）问题建模。该思维能力体现了逻辑思维和抽象思维，是整个求解过程中最关键的能力。在教学过程中，主要采取3个措施，循序渐进地提升学生的建模抽象能力。（1）深度和形象化理解经典算法的原理。除了通过课件讲解算法的原理外，课程利用MERN架构来构建一个交互式在线程序，实现代表性算法的可视化。程序包括代码模块、图形化显示结果模块和交互操作模块，支持用户在交互操作模块设置问题的参数和控制算法的进程；随着代码的运行，用户可以看见该代码运行所对应的图形化结果，这样学生可以对算法的结构和运行的结果有非常直观的认识。如在单源最短路径中，设计基于Bellman-Ford算法的可视化，可以运行预设的有向无环图，也可以增加和修改结点。（2）教学中采取“先破后立”的案例教学。对每个案例以问题输出为导向，析取所有的变量及关键属性；继而建立变量间的次序、优先级、包含等关系，通过图示的方式增加理解的直观性。如糖果问题，在满足约束条件下对幼儿园的小朋友分配糖果，确定问题的变量主要是小朋友分配的糖果数，主要关系是每个小朋友都分到糖果，小朋友间分配的糖果数有5种差异，这样构建了一系列两变量间的不等式，很容易就转换到差分约束系统问题。（3）教学中采取“关联法”进行相似问题的建模探究。如在单源最短路径中，引入无权最长简单路径问题，说明最优子结构中子问题间无关的特征，以及其NP难的特征；接着讨论有向无环图最长简单路径，提供了基于拓扑排序的求解方法。2）算法实现。教学过程中，教师鼓励学生在建立了问题的解析模型后，“由粗到精”逐步实现。首先撰写算法的伪代码，并在小规模测试数据上手工验证问题的答案；然后根据伪代码，选择合适的数据结构，保证程序运行成功并通过部分测试点。在课程初期，教师就讲授并训练所有常见的排序算法，使学生之后学习的注意力放在特定的算法设计上。按照每2周4道题的强度，学生于实验课前1周在EOJ上自行编程练习；教师在实验课上分析每题的解题思路并回答学生的提问，从代码层面进行问题分析；学生在接下来的1周完成所有的上机实验，并撰写实验报告，实验报告中包含问题、思路、算法设计、复杂度分析、关键代码，使得自己的算法设计和分析更加严谨和完整。3）优化迁移。通常问题的输入都有较大范围，而算法的运行有时间的限制，因此算法实现后，要进一步分析算法的复杂度，逐步优化算法。如坑爹的售票机问题：一行n人要都买到票至少要取多少张纸币？这个问题可以用动态规划方法求解，算法复杂度为O（n*k）；当n为109时方法复杂度过高。通过进一步分析购票的性价比，可以分析大部分的船票应该为性价比最高的船票，这样转换成贪心策略，可以降低算法的复杂度，通过所有的测试点。遵循“言为心声”的道理，课程设计了算法的线下研讨和现场演讲环节。这个环节借鉴翻转课堂的模式，鼓励所有的学生开口说，表达自己对算法的理解和思考，学会倾听老师和同学的观点，让自己的思维更加全面和严谨；同时，课程开放了EOJ的测试数据点，学生可以分析算法不能顺利通过的测试数据点，针对性寻找优化方案。4）分析证明。算法的学习不仅要知其然，还要知其所以然。在教学过程中，课堂教学重视理论的证明，如主方法、最优前缀码、最大流最小割等。在课后作业中，主要布置偏证明类型的作业，如习题2-4逆序对、7.2-1代入法证明，通过这种方法引导学生复习课程内容并进行深度思考。在理论课时，教师安排时间进行作业讲解，针对性地分析证明的要点和常见的错误。4结语算法是理论与实践紧密结合的课程。