算法设计与分析课程全方位实践教学改革探索

何克晶，张星明，郑运平

（华南理工大学 计算机科学与工程学院，广东 广州 510641）

算法设计与分析课程全方位实践教学改革探索

何克晶，张星明，郑运平

（华南理工大学 计算机科学与工程学院，广东 广州 510641）

针对算法设计与分析课程在培养学生实践能力、问题求解能力以及创新性方面的不足，研究国外计算机学科顶尖大学的算法设计与分析课程开设情况，分析课程目前的教学改革现状，提出算法设计与分析课程的全方位实践教学改革，从基于翻转课堂的研讨式教学结合的理论教学、ACM-ICPC竞赛和在线评测系统结合的实验教学、基于在线系统的课后作业管理、助教主导的课后讨论以及多样化的考核方式等方面阐述具体实施过程。

算法设计与分析；教学改革；研讨式教学；ACM-ICPC竞赛；考核方式多样化

0 引 言

随着社会对计算机技术需求的不断增加，用计算机解决实际问题的专业人才培养成为计算机相关学科教育的根本目的。算法设计与分析课程（以下简称“算法课程”）是计算机专业的专业基础课，在国内外各大学计算机专业课中处于核心地位。在国外计算机学科最负盛名的3所大学中，卡内基梅隆大学将“Algorithm Design and Analysis”列为必修课程[1]，斯坦福大学和麻省理工学院分别将“Design and Analysis of Algorithms”列为核心课程和先导课程[23]。算法设计与分析课程的主要目的是通过系统地学习算法设计的主要思想，培养算法设计和分析的能力，为学生利用算法解决计算机及其他学科实际问题奠定基础。

在进入算法课程学习之前，一般要求学生具有离散数学、高级语言程序设计（C++或Java）以及数据结构的相关知识。在高级语言程序设计和数据结构课程的学习过程中，学生所接触的是相对基础的概念和局部的知识点。算法课程要求学生利用之前学到的知识，用全局思想对实际问题进行分析，并进行具体的算法实现，真正解决实际问题。

1 传统算法课程教学的现状及问题

算法课程具有理论与实践紧密结合、相辅相成的特点，所以除了基础理论性的课程教学外，还要特别注重算法设计和实践环节。只有通过实践环节加深巩固课堂所学，才能通过此课程真正掌握解决实际问题的能力。

但传统的算法课程教学普遍存在实践教学不够深入全面的问题，具体体现在以下几方面。

（1）以理论为主，实践不足

学生课后很少做练习和深入思考，大学4年下来，学生的编程量少，写程序不熟练，碰到实际问题有种无从下手的感觉，问题分析和解决能力离社会的要求还有一定的差距。很多学生虽然考分高，但编程能力还比较弱，对于书上讲的知识也是一知半解。

（2）缺乏平时考核、测评

目前绝大多数课程的考核方式是平时成绩和实验占30%～40%，期末笔试成绩占60%～70%。课程的考核还是以笔试为主，操作性比较强的编程类题目所占比重比较少，这使得学生偏向于只掌握几个考试重点。这种状况实际上是过于强调结果而忽视过程，并非真正的素质教育。

在国外大学的算法课程中，平时的考核和测评往往多于期末考试成绩。以2016年春季课程为例，在所调研的3所顶尖大学中，期末考试成绩只占30%左右，课后作业和平时成绩对总成绩起主要作用（见表1）。

表1 国外顶尖大学计算机学科算法课程考核方式

（3）缺乏综合性的实践

平时的作业题多来自于课本上的课后习题，而课后习题往往能从课本上找到现成的答案。这种方式不利于考查学生解决实际问题的能力，因为课本的课后习题本身就不是“实际问题”，往往针对的是课程某个知识点，数据结构、图论、算法设计等综合知识没有得到很好的串联，而且题目与实际生活联系不紧密，导致学生觉得枯燥无味。

在现有少量的实验课中，缺少设计性和综合性实验，学生面对题目往往是上网或查书找答案，甚至有少部分学生会直接抄袭其他同学的答案，或者有些“精明”一点的同学会对程序中的变量名或者提示性的输出语句进行替换式的修改，完全缺少创造性思维的培养。最后导致实验变成打字和调试程序的过程，达不到预期的教学目标。

在上述国外3所大学中，均要求完成7个左右综合性的课后作业，配备了8～13名助教，并每周进行一次分组的课程讨论。

2 现有的改革模式及其分析

为了解决测试及实验内容与实际操作能力脱钩的问题，并方便教师检查学生程序，包括华南理工大学在内的国内部分高校采用与ACMICPC（ACM 国际大学生程序设计竞赛）、OJ（在线评测）系统结合的方式来提升学生的编程能力，自动检验程序的正确性、算法效率和内存使用情况等[48]。ACM-ICPC是由ACM（美国计算机协会）主办的程序设计比赛，至2016年已举办40届，是全世界最具影响力的计算机竞赛，被誉为计算机界的“奥林匹克”。OJ系统可完成程序设计竞赛、课程实验、平时练习等多项任务。

ACM-ICPC采用团队参赛的形式，在不能联网查询资料的情况下，需要分析题目内容，设计算法并实现。ACM-ICPC的竞赛时间为5个小时，一般包含6～13道题目，程序运行不能超过允许的内存数量和执行时间。与传统竞赛相比，ACM-ICPC考查的是学生在限定的时间内团队合作解决问题的能力，是对学生编程能力、心理素质、团队协作能力的一个综合考验。根据往年经验，极少有团队能在限定的时间内完成所有题目。题目内容只是问题陈述，且学生得到的只是测试数据实例，无法获得裁判的检验数据和标准。而若提交的程序没有通过检验，则会受到加时惩罚。所以对问题进行难度分级、推断出要求、设计并实现算法就变得非常关键。面对实际的问题，能否在限定的时间内求解，进行针对性的算法设计和分析尤为重要，因为算法课程与ACM-ICPC的目标都是培养学生解决问题的实践能力，两者结合必然会取得双赢的结果。

通过分组的方式进行竞赛和教学的结合，学生之间能进行充分地合作交流并分享经验，有助于提高学生的团队协作精神和解决问题的能力。通过将算法课程与ACM-ICPC结合，能提高学生的编程水平和实践能力，同时为ACM-ICPC储备大量优秀的竞赛队员。在之前的教学改革中，华南理工大学已将竞赛模式运用到算法课程的教学过程中，提出了一种基于ACM-ICPC的算法课程教学改革模式。该模式培养了学生参加ACM-ICPC的兴趣，极大地提高了学生学习的主动性和积极性，加强了对团队合作精神和创新能力的培养[9]。但实际算法课程也有与ACMICPC不同之处，主要包括：①学生水平差别较大；②断网与不断网的选择；③如何在题库中创建众多新的题目。

在真正的竞赛中，每个题目允许的求解时间很短。但实际教学中，学生的水平相差较大，要充分考虑优秀学生和普通学生的不同需求[10]，且实际教学中的学生平均水平比ACM-ICPC队员的水平要弱一些。如果严格按照ACM-ICPC规定禁止使用网络，并限定时间，由于在线评测系统只检验最终结果，会造成众多学生许多题目都是零分，某种程度上会打击学生的积极性。如果允许学生使用网络，在互联网异常发达的情况下，大多数题库里的题目都能在互联网上找到答案。而且，如何防止学生之间互相抄袭和修改借鉴也就成了另一个不好解决的问题。2014年春季，我们在课程实验中加入了一个在网上找不到答案的题目，在允许使用网络，限定1个下午实验时间的情况下，正确完成的同学不到20%。2015年春季，第39届ACM-ICPC全球总决赛刚结束，我们马上将全球总决赛中较难的一道题（题目K）加入了实验。此题判定为较难的依据是因为在总决赛中此题一共只被提交了11次答案，最后只有2个队成功求解。同样允许使用网络，限定1个下午实验时间的情况下，结果没有同学能求解此题。所以在允许使用网络的情况下，某题目有多少同学能做出来很大程度上取决于网络上是否容易找到类似的解决方案。

所以，在充分考虑学生个体之间的巨大差异性、网络资源的丰富性、教学与竞赛的异同之后，如何结合ACM-ICPC进行较全面的算法课程实践教学改革就变成了一个值得深思的问题。

3 全方位实践教学改革

3.1 理论教学——课堂讲授与基于翻转课堂的研讨式教学结合

采用课堂讲授与研讨式课堂讨论结合的理论教学形式。教学内容以教材为基础，以具体的问题和应用为驱动，引导学生深入分析问题，并设计优秀的算法，培养学生的创新能力。

除课堂讲授外，部分学时基于翻转课堂的模式进行研讨式教学。给学生提供主题、视频、在线课程及相关资料，让学生组成小组，根据具体的问题进行调研和讨论，教师进行启发式引导。通过让学生进行研讨汇报，实践能力得到提升，表达能力得到锻炼，思维更加缜密，同时团队协作精神得到加强。《国家中长期教育改革和发展规划纲要（2010—2020年）》对创新人才培养也要求注重学思结合，通过研讨式教学帮助学生掌握学习的能力[11]。通过在理论教学中推动学生课后的实践活动，可以与传统的讲授型教学模式进行良好互补。

3.2 实验教学——与ACM-ICPC和OJ系统结合

作为全方位实践教学体系的一部分，学科竞赛对提高学习兴趣、激发学生潜能发挥着重要作用。在竞赛和教学结合方面，将实验环节与ACM-ICPC和OJ系统结合，并鼓励学生参加其他相关竞赛，如数学建模及各大IT公司举办的学科竞赛。为了充分全面地考核不同层次的学生，题库中除了常规OJ系统频繁见到的题目之外，必须得有一定的新题。若新题能全面覆盖不同的知识点，且难易俱备，则能对学生进行更全面的锻炼和考核。通过与OJ系统结合，能减少教师批改编程题的工作量。

要真正培养学生的算法设计、分析和创新能力，只依靠课内学时是远远不够的。除了实验学时之外，鼓励学生课后参与ACM-ICPC训练或兴趣小组，或者利用空余时间到OJ系统上通过做题进行锻炼。还可利用技术讲座和学生项目实践，推动学生对技术前沿的掌握，学习前沿先进技术和创新理念，让学生了解实际问题，有重点地培养学生的创新意识。

3.3 课后作业——利用在线系统

算法课程的目的是锻炼学生的算法思维，并借助编程的手段，解决实际问题。现实中的问题很可能是未出现过的新问题，所以必须给予学生适当的思考时间，借助已有知识，循序渐进解决问题。因课时限制，无论是课堂教学还是实验，都没有条件锻炼学生解决实际复杂问题的能力。麻省理工学院的课后作业采用问题集（Problem Set）的形式，Erik Demaine教授谈到课后作业时表示：“在一个时间受限的测试中，很难期望学生具有创新性……所以我们用来测试的问题相对简单，学生只要一个简单的想法并且对相关的知识比较熟练，就可以较快地完成测试。而课后作业则更容易让学生发挥创新能力，学生能有更多的时间仔细思考这些问题。因为有些问题对某些学生而言可能相对容易，而对其他学生而言较难，所以学生有一周左右的时间进行思考。并且可以相互讨论，协作完成……2014年的时候，我们希望通过测试的方式来准确评价学生应用算法技术来设计一个新算法的创新能力，而2015年我们已经不再这样做，因为我们并不清楚这种评价方式的正确性……”[12]。

因此，课后作业或者问题集的形式，作为课堂以及实验教学的补充，可由易到难逐步培养学生解决复杂问题的能力。学生可以自愿选择在开放的实验室等地点完成作业。可根据作业的实际情况要求学生独立完成或组队完成。为减轻工作量，并综合考虑存档的需求，可利用智能化的评测系统，要求学生在规定的时间上传课后作业的电子文档或扫描件。课后作业也可与课后讨论结合。在时间和条件允许的情况下，要求学生在课堂研讨或课后讨论时，向任课教师或助教对作业完成过程进行阐述。

3.4 课后讨论——发挥助教的作用

因为课时限制，以及教学班的学生数目往往较多，一些学生在课堂上并没有机会充分地参与讨论和交流。因此可以将课后讨论作为补充，讨论分成小组形式。国外的算法课程往往安排了多个助教和多次课后讨论（见表1）。根据实际情况，建议助教组织、管理和安排一些课后讨论，讨论内容是对所学课堂知识的扩展。

3.5 考核方式——多样化，结合在线考试

大多数ACM-ICPC和OJ系统只能考查编程试题，并且存在结果错误即为零分的情况。而实际课程考试中，为了更全面考核学生的掌握程度，可能需要结合选择、填空、问答、计算及编程等题型，并且课程教学及考核与竞赛存在一定区别，单纯的结果错误即为零分的方式也值得商榷。结合高校实际情况，建立自动化的在线考试系统，有助于教学过程中对学生的掌握程度进行多次考核，且降低任课教师出题和改卷的工作量。考虑到实际情况，在线考试应对编程题、选择题、填空题、程序理解和改错题等均有较好的支持。

为全面考核学生学习过程，结合学校和学院的相关政策，在条件允许的情况下，可选择综合考虑出勤情况、上课回答问题和讨论情况、课后讨论情况、课后作业情况、竞赛与教学结合的编程实验成绩、平时测评成绩和期末考试等方面，对学生进行全面考核。

通过以上全方位实践教学改革措施，可督促学生边实践边学习，达到“以用促学，以学致用，学用结合”的目的。教学过程能激发学生的学习兴趣，学生作为实际问题的解决者，对算法设计和分析不仅有较浓厚的兴趣，而且能提出更符合学生思维习惯的创新算法。注重实践性的算法课程能调动学生的主观能动性，通过在课程的实践教学环节中锻炼解决实际问题的动手能力，同时为学生未来的求职和科研打下基础。

4 结 语

经过一段时间的教学改革，目前已初见成效。通过在算法课程中全方位推进实践教学改革，学生解决实际问题的能力得到了培养，实践能力得到了提高。学生能从实际问题出发，根据理论知识，进行算法的设计分析并实现，学以致用。在课程教学中，让学生接受竞赛式的思维训练，培养了学生对算法设计和ACM-ICPC的兴趣。近年来，华南理工大学学生参加ACM-ICPC也取得了较好成绩，2013—2016年连续4年进入全球总决赛，但要全面持续地深入改革，仍然任重而道远，主要在于深入改革需要投入大量精力和资源。比如，国外的课后作业均为综合性的，在网上难以直接找到答案，且每年的课后作业都不同。课后讨论和题库建设同样需要教师和助教投入大量的时间。今后，将进一步深入贯彻算法课程的全方位实践教学模式，逐步培养学生的创新意识，提高其实践能力和团队协作能力。

[1] Carnegie Mellon University.15-451/651:Algorithms[EB/OL]. [2016-05-30]. http://www.cs.cmu.edu/～15451/.

[2] Stanford University. CS 161: Design and Analysis of Algorithms(Fall 2016) [EB/OL]. [2016-05-30].http://cs161.stanford.edu/.

[3] Massachusetts Institute of Technology. 6.046/18.410 Design and Analysis of Algorithms [EB/OL]. [2016-05-30].https://stellar.mit. edu/S/course/6/sp16/6.046/index.html.

[4] 郑运平.“算法设计与分析”的教学模式探索[J]. 华南高等工程教育研究, 2012(2): 21-25.

[5] 李华, 赵建平, 李奇, 等. 基于ACM-ICPC的算法设计与分析课程改革[J]. 计算机教育, 2013(7): 88-91.

[6] 刘晓璐. 基于ACM-ICPC模式的算法分析与设计课程的建设与实践[J]. 中国教育信息化, 2015(10): 65-67.

[7] 杨春明, 陈念年. 基于竞赛模式的“算法分析与设计”教学探索与实践[J]. 计算机教育, 2009(20): 146-147, 105.

[8] 吴英杰, 王一蕾, 傅仰耿, 等. 依托程序设计竞赛,推进“算法与数据结构”课程实践教学改革[J]. 计算机教育, 2010(4): 53-55.

[9] 张星明, 郑运平. 计算机创新人才培养模式的探索[J]. 计算机教育, 2013(18): 16-19, 40.

[10] 陈翔. 面向不同层次学生的算法设计与分析课程教学改革探索[J]. 计算机教育, 2014(18): 19-22, 26.

[11] 中华人民共和国教育部. 国家中长期教育改革和发展规划纲要（2010－2020年）[EB/OL]. [2016-05-30]. http://www.moe. edu.cn/publicfiles/business/htmlfiles/moe/moe_838/201008/93704.html.

[12] Massachusetts Institute of Technology. Design and Analysis of Algorithms[EB/OL].[2016-05-30]. http://ocw.mit.edu/courses/ electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/.

（编辑： 史志伟 ）

1672-5913(2017)02-0045-05

G642

广东省本科高校教学质量与教学改革工程（粤教高函〔2014〕97 号，粤教高函〔2015〕173 号）；2014年华南理工大学校级教研教改项目“网络工程专业实践教学的研究与探索”；2014年华南理工大学探索性实验教学项目“基于MPI/OpenMP混合编程的大规模多体问题仿真”。

何克晶，男，教授，研究方向为高性能计算、云计算与大数据，kjhe@scut.edu.cn。