工程教育专业认证下的“算法分析与设计”课程教学改革与实践

刘利敏，晏 轲

（湖北第二师范学院 计算机学院，武汉 430205）

1 引言

为了切实提高高等教育教学质量、实现工程教育国际互认，我国2016年正式加入了《华盛顿协议》。工程教育认证强调以学生为中心、以成果为导向（Outcomes-based Education，OBE）和持续改进的理念，面对毕业生制定了12条要求，包括工程知识、问题分析、设计/开发解决方案、个人和团队、终身学习等。[1]12条毕业要求可以概括为四个方面的能力：知识与技能、分析与设计、人文与素养、协作与学习。在工程教育专业背景下，教育目标围绕学生培养，教学设计聚焦学生能力的培养，师资与教育资源满足学生学习效果的达成；评价的焦点是对学习效果的评价。通过12条认证标准，对专业学生培养目标、质量、师资队伍、课程设置、实验设备、教学管理、各种教学文件及原始资料等方面进行规范化评估，最终实现“以人为本”、成果导向的教育目标及质量持续改进的培养机制。

湖北第二师范学院计算机科学与技术专业2017年开始筹备申报工程教育专业认证，并于2020年获批国家一流专业。在工程教育专业认证及专业人才培养的双重驱动下，为实现“以全体学生为中心”、能力提升及持续改进的教育理念，开展了“算法分析与设计”的教学改革与实践。制定了工程教育背景下的课程教学目标、教学内容，教学方法及评价指标体系，并进行目标达成计算，分析教学改革效果及教育质量评价。

2 课程特点及教学存在的问题

2.1 课程特点

“算法分析与设计”作为计算机科学与技术的核心专业课之一，先修课程包括：离散数学、高级程序设计语言、数据结构等。该课程总学时为40学时，其中理论24学时，实践16学时。课程涉及多种经典算法求解策略的学习及典型问题的应用求解，算法策略包括：蛮力法、递归分治、动态规划、贪心算法、回溯法及分支限界法等，典型问题包括：0/1背包问题、电路布线、TSP旅行商、多机调度、流水作业、装载问题、活动安排、硬币找零问题等，课程内容多、难度较大，需要学生具备较强的逻辑思维及动手实践能力。[2]其次，该课程对学生先修课程的掌握程度要求较高，很多算法思想及问题求解需要数据结构课程支撑，如分治算法中的快速排序、合并排序及二分查找，贪心算法中的哈夫曼编码、Dijkstra单源最短路径等问题都在数据结构课程中涉及，分支限界算法需要通过FIFO队列或优先队列实现，回溯法需要DFS深度优先搜索的知识基础。再次，算法学习的最终目的是应用及解决问题，因此该课程对学生动手实践能力要求较高，要求学生在充分理解需求的基础上，选择合适的数据结构及算法求解策略，通过方案设计、优化及编码实践输出结果，如果学生不具有扎实的编程基础，在进行算法实践方面也会存在一定的困难。

2.2 学生特点

学生普遍反映课程难度较大，通过调研分析发现：部分同学逻辑分析能力有限、无法建立算法思维，不能做到理论联系实际；部分同学难以深刻理解算法策略及思路，或对算法的理解和应用仅停留在对已知问题的处理及实现上，无法做到理论联系实际；部分同学编程基础薄弱，无法将算法思想进行工程实现；对于实际工程问题，无法通过比较、评价、优化，综合设计最优方案；部分同学反映经过大量实践训练，可有效增强对算法理论的理解及编码实践能力。对接受工程认证的计算机科学与技术专业近3年的学生课程结束后进行问卷调查，具体结果如表1。

表1 近3年计算机科学与技术专业学生调查问卷

2.3 课程教学问题

通过分析课程和学生特点，可以发现课程教学过程中存在如下问题：第一，如何兼顾算法基础理论和学科前沿；第二，如何解决课时有限与课程难度大、内容多、学生实践创新不够充分的矛盾；第三，如何在学生深入理解算法理论的基础上，增强学生对算法思想及代码实践对应关系的理解，譬如掌握子集树的回溯法DFS搜索过程以及代码递归框架的对应；第四，如何引导学生把握算法课程整体体系，深入理解不同算法的求解策略及差异，掌握算法之间的逻辑关系及适用场景；第五，如何以学生为中心，针对具体的问题、激发学生主动思考，项目小组研讨、方案设计及代码实践，综合提升学生利用算法解决实际问题的能力。

3 基于能力提升及OBE理念的教学改革

工程教育专业背景下，课堂教学目标围绕学生培养，教学设计聚焦能力提升，课程评价围绕能力效果的评价，师资及教学以满足学习效果达成为要目的。结合课程及学生特点，通过深化课程教学改革，提高教学质量，达成培养目标。针对以上存在的问题，在能力素养提升及OBE理念驱动下，根据“算法分析与设计”课程的特点，通过专题探究、课程小组讨论及网络平台线上线下混合式教学方法，重构教学目标、重组教学内容、创新教学方法和改进评价指标体系等几个方面进行改革，并利用青软U+平台进行课程目标达成度分析。

3.1 工程教育背景下培养目标

为达成工程教育人才培养理念，制定算法分析与设计课程培养目标：培养学生系统掌握算法研究领域的基本概念与原理，理解和掌握常用算法的设计策略、算法差异、适用场景、算法的复杂度分析；增强学生的逻辑思维能力及终身学习能力；针对复杂工程问题，能够综合运用所学，独立地以计算机算法视角分析问题，通过比较、评价、优化，设计出最优算法解决方案，开发满足符合软件项目需求的系统模块或算法流程。具体可细化为3个目标，对应支撑毕业要求的1.4（工程知识，H支撑）、2.3（问题分析，H支撑）及3.2（设计/开发解决方案能力，M支撑）。同时引入思政元素，强化课程育人导向，坚持立德树人，综合运用启发式教学、讨论式教学、混合式教学、课外自学等教学模式，将与课程相关行业应用现状、行业法律案例、行业关注热点、社会文化趋势等融合到课程学习中，引导学生探讨相关问题，形成正确的人生观、价值观以及职业道德，培养学生严密的逻辑思维、吃苦耐劳的精神及终身学习的意识。

3.2 教学内容改革

当前大部分算法分析与设计的教材的教学内容，主要集中在三部分：一是算法基础理论及复杂度分析；二是经典算法求解策略以及典型问题的求解应用，包括分治递归、动态规划、贪心、回溯及分支限界等；三是困难问题的求解，包括随机算法、概率算法和近似算法、计算机NP复杂性理论等。但对当前学科的一些新型算法及研究热点鲜有涉及，但该部分对实际工程问题求解及科学研究而言都是非常重要的手段。

为培养创新人才，服务学生后期发展及能力提升，对课程教学内容进行改革。从学科特点出发，兼顾基础理论及学科前沿，在传统授课内容的基础上，引入一些学科研究热点及相关应用成果的介绍，引导学生关注学科领域前沿动态、拓宽科技视野，增强科学素养；同时融入思政元素，深化学生职业理想和职业道德教育，培养学生良好的职业品格并自觉实践和职业规范。当前人工智能在很多领域应用成效显著，如医疗、科技、金融、智能家居等，且已上升到国家战略；因此在传统算法基础及内容学习的基础上，引入关于机器学习、人工智能及深度学习理论及相关应用的内容，包括分类、聚类、回归、推荐等。同时为了培养学生主动学习的能力，布置学生查阅若干机器学习及人工智能应用项目案例，组织学生分组协作讨论、分享；在掌握学科基本理论的基础上，加深对学科前沿内容的理解。

3.3 教学模式改革

课程从培养学生计算机算法思维出发，培养学生解决复杂工程问题的能力，让学生能够综合运用所学，进行算法比较、评价、优化、设计，并编码实践开发解决问题的算法模块。注重以“学生为中心”，实现OBE理念的“成果导向”，设计了融合专题探究、课程小组讨论、项目驱动及混合式的教学模式，具体如下。

3.3.1 专题探究

专题教学是实现教材体系向教学体系转变。主流算法教材在内容组织主要以算法策略为逻辑单元，以王晓东编著的《计算机算法设计与分析》（第5版）为例，第一章算法概述、第二章递归与分治策略、第三章动态规划等。某些问题可以利用多种算法求解，所以在传统按照算法策略为逻辑单元的教学组织中，在不同算法章节中分别学习该问题的求解。如0/1背包问题，在动态规划法、回溯法以及分支限界法中，又分别进行了学习。但这样的授课方法，学生无法对该问题的多种不同的求解策略进行深入对比分析。而专题教学，可以突破按章节体系依序授课的局限，把相关教学内容进行整合、提炼、概括充实，形成独立专题，可以增强不同算法策略过程及复杂度的对比分析，加深学生对问题的理解。根据课程内容，在以算法策略为逻辑单元学习的基础上，增设部分专题，如：0/1背包多算法求解专题、复杂装载问题多算法求解专题、硬币找零问题多算法求解专题等。通过对比专题问题不同算法的求解思路、求解过程、求解结果及算法复杂度分析，加深学生对不同算法策略及适应情形的理解和掌握。

例如：0/1背包专题，分别利用动态规划、回溯法、分支限界法进行问题求解，分析算法策略及编码方法，并进行不同方法的对比及复杂度分析；同时讨论是否可以利用贪心算法进行求解，以及存在的问题。硬币找零问题：如现有硬币面值1元、3元、4元，需要找零6元，请问如何找零使得硬币个数最少？分别利用蛮力法、贪心算法、动态规划算法进行方案设计；可以发现贪心算法需要3枚硬币，dp算法需要2枚硬币，得最优解不同，对比分析不同算法求解差异及算法复杂度，得出哪些算法适合求解该问题的结论。

3.3.2 课程小组讨论及项目实践

为提高学生在课程教学中的参与度，构建“以学生为中心”的教学理念，教师根据班级人数划分课程学习小组，每组人数控制在6人左右。教师发布若干讨论主题及实际工程项目任务，各小组领取相关任务。通过组内讨论协作的方式，完成主题讨论、实际工程项目的实践及演示答辩。通过讨论及项目答辩演示环节，增强学生表达能力、团队合作能力及独立学习解决问题的能力。

3.3.3 项目驱动

表1调研结果表明，算法学习效果好的学生，在课下均进行了大量实践练习，实践也可进一步增进对算法理论理解。为增强学生算法应用及实践能力，课程利用“项目驱动”法，引入LeetCode 题库，根据课程学习专题，布置LeetCode 的相关题目作为课后项目实践。通过大量专题分类训练，增强学生对算法思想的理解，让学生建立起算法理论与代码之间的转换关系；在实践形成自己求解方案的同时，学会借鉴学习优秀解题思路，思考优化及改进策略，提升解决实际问题的能力。

3.3.4 混合式教学

为增强学生自主学习及分析问题的意识，通过混合式模式将传统课堂教学及在线学习平台相结合。[3]课前发布MOOC 视频学习任务、思考及讨论题；课上通过引入思考及组织讨论，重点介绍算法思想及问题求解思路，并针对线上学习难点进行答疑，通过“重点+难点”相结合的方法提升学生学习效果；课后布置作业任务，包括算法分析涉及类题目及LeetCode平台实践等。此外算法学习较为抽象，在教学过程中要注重理论联系实际，将抽象的问题转换成实际问题，一方面易于激发学生的学习兴趣，另一方面也易于理解。如最小生成树问题，可以通过如下案例：若干个城市修建高铁，城市之间修建成本已知，规划一个修建方案使得成本最低？单源最短路径问题，[4]可以如下案例说明：已知若干个城市之间的连同关系及交通成本，指定一个城市作为出发点分别去其他城市旅游，求解到其他城市各自的最短路径及线路。

3.4 评价指标与体系改革

工程教育认证强调学生能力提升及学习效果达成评价，考核要求针对全体学生可量化的能力评价，既包括过程性评价又包括综合性评价。针对如上要求，对该课程评价手段进行设计，主要包括四个方面，具体见表2。

随堂测试、讨论及作业环节。课程讨论、课堂测验，主要来源于课前预习或课堂授课环节。通过在线学习平台发布问题，引导学生思考参与讨论，构建开放式、问题式及对话式课堂环境；发布测验，考查学生对问题的理解及应用。课后作业，主要是课堂内容的延伸和深化，要求学生针对具体问题进行更为深入的思考、设计及对比分析，作业布置如案例1。学生测验、讨论及课后作业，可通过在线学习平台进行采集记录；该部分占总评分的10%。

课堂小组项目实践及演示，该部分主要考查学生的团队协作能力、问题分析及算法设计能力、算法分析及创新能力、代码编写实践能力以及演示答辩时PPT组织、演讲表达能力等；该部分占总评分的10%。

实验环节，共包括8个设计类实验，培养学生应用分治、动态规划、贪心、回溯及分支限界等算法思想解决实际问题并进行编程实践的能力，该部分考核主要通过实验验收答辩及实验报告。

期末考试，主要以闭卷形式考核学生利用所学算法理论、算法策略进行实际问题分析及方案设计的能力；题型以算法分析设计及程序分析设计题为主，客观题不超过15%。

以上四个环节的考核，从过程与结果两个层面对学生应用算法解决问题的能力进行考核，既包含了对算法知识理解、应用等初级认知学习的考核，也包括对问题进行分析、算法评价、优化及创新方面深层认知学习的考核，同时也涉及了对学生个人和团队、沟通、终身学习等非技术能力的考核。

4 课程目标达成计算

持续改进是推动课程教学质量持续提升的基础保障。教学效果评价聚焦课程目标的达成，通过达成度分析，发现当前教学存在的问题及不足，进行针对性持续改进。工程教育专业认证采用定量达成度评价授课对象对各课程目标的达成情况，[6]本课程4个考核环节对3个课程目标的支撑总评分及占比见表3。表3明确列出各课程目标的总评分M，以及4种考核对其支撑权重；如课程目标j，其总评得分为：

其中Ci为第i 种考核方式总评分，wij为第i 种考核方式对第j 种课程目标支撑权重。

表2 课程成绩评价组成

本文以2019级计科专业86名学生的各分项成绩，进行目标达成度计算。首先按照各考核环节相应的评分标准，评定每名学生的4种考核下的定量得分。利用表3中各考核指标对3个课程目标的支撑权重计算各课程目标达成得分，获取每名学生各个课程目标的达成度A，计算公式见式（2）。

表3 课程目标达成考核与评价方式及成绩评定对照表

其中：Aj表示课程目标j 的达成度，si表示第i 种考核的实际得分，wij表示第i 种考核方式对第j 种课程目标支撑权重。

全体学生平均课程目标达成度，si为全体学生的实际平均得分。通过定量评价，3个课程目标的达成度分别为：0.734、0.759、0.763。同时以散点图形式将每名同学3个课程目标的达成度进行可视化，以课程目标2为例，达成情况散点图如图1。从图1发现，大部分学生均能达成课程目标，但是其中一个学生未达成，该学生总评成绩也小于60分。

图1 全体学生课程目标2达成度

5 结语

工程教育认证以学生为中心、以能力提升为核心，以持续改进质量提升为目标。本文为落实工程认证人才培养内涵，针对“算法分析与设计”进行教学改革，通过制定工程认证背景下的教学目标、教学内容、教学模式、评价指标体系，并进行课程目标达成评价。结合课程特点及学生调查问卷，分析了学生特点及教学过程中存在的普遍问题；根据学生能力提升及OBE教学理念，制定了工程认证教育下的课程培养目标，设计了融合专题探究、课程小组讨论、项目驱动及“学生为中心”的混合式教学的新模式，构建了学生“产出导向”的评价指标及体系。通过改革实践，利用青软U+平台进行课程目标达成度分析，服务后期持续改进；结果表明：该教学改革可以达成课程目标、获得良好的教学效果；教学模式和改革方法，对其他接受工程认证的课程建设可提供借鉴和参考。