总结，提出了相应的教学实施方案。本方案的特点是：以素质和能力培养为目标，构建面向不同教学要求的模块化的知识框架，并注重理论联系实际，在软件系统建模和分析中强化应用。
关键词：算法设计与分析；软件工程；硕士研究生课程；教学改革；计算思维
北京大学软件与微电子学院是一所面向产业和领域需求，培养高层次、实用型、复合交叉型、国际化人才的学院。经过10年的探索与实践，提出一套“产学研用结合”的培养模式和“多层次、多方向、多领域、模块化、开放式”的课程体系[1]。在该课程体系中，“算法设计与分析”课程如何定位？面向工程硕士的算法课与本科生的算法课有什么区别？针对不同本科专业方向和基础的学生如何制订教学实施方案？这些都是需要探索的问题。
一、算法课程的定位和指导思想
教育部软件工程学科课程体系研究课题组在《中国软件工程学科教程》一书中提出了4种分别侧重于计算机科学、软件开发技术、系统认识和工程化理念的不同的本科生教学计划参考模式，其中“数据结构与算法”都是重要的核心课程之一[2]。软件工程是计算机科学与工程和管理学科的交叉学科，算法知识是计算学科的核心内容，是软件工程硕士必备的基础。特别对于从事软件工程的高层次、复合型人才，通过算法课程的学习有助于培养学生的计算思维与系统分析能力。
因此，在北京大学软件与微电子学院的课程体系中，“算法设计与分析”课程是面向全校硕士研究生的公共选修课，同时是软件开发、软件测试与质量保证专业与研发中心硕士研究生的必修课，总计3学分，48学时。
由于软件学院跨学科、多领域、产学研用相结合的培养模式，在制订算法课程的教学计划时遇到以下问题。
问题1：学习算法课的学生来自不同的专业方向，有着不同的培养目标和需求（见表1）。
表1给出了一个北京校区算法课脱产班212人专业方向分布的示例，其中必修学生156人，大约占3/4，剩下的是其他专业方向的选修生。不同专业方向、不同培养模式（脱产和在职班）的学生对算法课有着不同的需求。研究中心的学生由于要参与课题研究，需要较好的计算思维及更强的建模分析能力，其他学生更着重于软件工程实践及面向领域的应用，而在职班的学生则希望了解更多的应用背景。如何根据不同的培养目标确定算法课的教学内容？
问题2：算法课具有一定的难度，需要用到某些数据结构与离散数学的知识。而软件与微电子学院有部分学生本科专业不是计算机或相关专业，没有系统学过这些课程。
根据北京大学软件与微电子学院的特点，面向软件工程学科的硕士研究生算法课要在课程定位、教学目标、教学内容、教学设计等方面不断探索，制订出具有自己特色的教学实施方案。课程建设的指导思想是：
（1）突出能力培养。随着计算机的广泛应用，新的问题不断涌现，新的算法层出不穷，能力的培养尤为重要。与算法和问题求解相关的能力主要体现在以下4个方面：用适当的数学模型描述实际问题的建模能力，运用计算思维确定问题求解方法的算法设计能力，对给定算法做出性能评价的分析能力，对问题难度和复杂性的判定能力。针对软件工程专业硕士，在算法教学中应该着重于前3种能力的培养。
（2）构建统一的知识框架。该框架面向多个专业方向，适应于不同的本科基础，针对多样性的人才培养目标，采用层次化、模块化的结构，使得教师能够根据不同的教学需求制订相应的教学计划。
（3）进行科学的教学设计，不断更新教学内容，引入好的教学方法和教育技术。
（4）建设一系列配套的教学资源，包括教材、电子教案、教学辅导书、网上教学环境等。
（5）注重教师培养，建立老中青结合的教师队伍。
二、算法课程的教学目标与知识框架
针对软件工程专业硕士，算法课程的教学目标是：
（1）掌握计算机算法设计的基本技术——分治策略、动态规划、贪心算法、回溯与分支限界、随机算法等。
（2）掌握计算机算法分析的基本方法——了解评价算法的标准，能够对给定算法做出最坏与平均时间复杂度的估计，了解问题复杂度的界定方法。
（3）了解计算复杂性理论的基本框架和应用。
（4）培养针对实际问题进行建模并选择高效求解算法的能力，使得学生在计算思维、学科方法训练及专业素质方面得到提升。
根据软件工程的特点，算法课的核心内容以算法设计技术与分析方法为主，对于NP完全理论以及概率算法、近似算法等研究领域加以简要的介绍。算法课程的知识框架如下图所示。
在算法知识框架中，处于底层的是算法基础，有关知识可以在课程开始给予简要的介绍，也可以包含在其他基础课中。北大软件与微电子学院的做法是：把有关计算机组成、操作系统、程序设计、数据结构等计算机科学与技术的基础知识配置成A、B、C三种类型的基础课，以便不同专业的学生根据自己的情况选修。中间两层由核心知识单元构成，主要涉及算法的设计技术和分析方法，这部分内容是课程重点。第四层涉及计算复杂性理论，重点是NP完全理论。面对软件工程专业，只需要简单介绍相关的概念和理论框架，使学生了解什么是问题的难解性。最高层则结合学科进展介绍近似算法、随机算法等热点研究方向，同时联系学生科研实践对课程进行总结。整个教学安排按照48学时进行分配，其中基础知识、算法设计与分析部分可根据不同班次的教学要求分配32～42学时。
算法课程的知识框架图
三、围绕计算思维和能力培养进行教学设计
“计算思维”是美国科学基金会在2006年的研究报告中提出的新概念，也是近年来计算机教育所关注的热点问题。计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动[3]。计算思维是通过约简、嵌入、转化和仿真等方法，把一个困难的问题阐释为如何求解它的思维方法。是一种递归思维，是一种采用抽象和分解的方法来控制庞杂的任务或进行巨型复杂系统的设计，是一种选择合适的方式陈述一个问题，或对一个问题的相关方面建模使其易于处理的思维方法[4]。
作为高层次的软件工程研究和应用人才，应该受到良好的计算思维训练，而算法是计算思维训练的重要一环。算法课程的教学要求是：能够对所求解的问题加以抽象或约简，给出形式化的描述并找到正确高效的求解方法，其中涉及问题抽象、复杂问题的分解和递归处理、算法复杂度的定量分析与权衡等，这些都体现了计算思维。为了强化计算思维的训练，我们在教学设计中考虑的重点是：
1．教学内容，即“讲什么”的问题
大多数学校的本科算法课程主要讲算法的设计步骤，同时强调上机实现。而面向工程硕士的算法课要增加深度，讲出算法技术所隐含的学科思想。这不仅需要介绍具体的设计步骤，更应该讲清楚这样做的理论依据。所设计的算法是否正确？如何证明其正确性？它的优势在哪里？有什么局限性？改进算法的途径是什么？等等。应该通过学习达到举一反三，掌握算法所体现的思维逻辑和学科方法。有些学生在本科阶段修过算法课，分治策略、动态规划、贪心法、分支限界等设计技术都接触过，认为自己没必要再学了；但是，在期末课程总结中表示“算法课收获很大”，“许多在本科没搞清楚的问题都理解了，拿到实际问题有了更清晰的解决思路。”
需要说明的是，针对必修与选修、脱产与在职班的不同教学要求，教师可以在内容上加以调整。比如对于脱产班算法必修课，可以选择上图框架中的全部10个知识模块，教学安排如表2所示。而在职班和其他专业方向的选修课可以多讲一些应用实例，而适当减少模块6－10的内容。
2．教学方法，即“怎样讲”的问题
算法课中涉及较多的数学知识，比较抽象难懂，怎样激发学生的兴趣，做到启发式学习？我们的做法是：
（1）按照“提出问题－阐述方法－解决问题－总结规律－推广应用－讨论提高”的模式进行教学设计。每种设计技术和分析方法都精选了大量的应用实例，这些实例应该满足“建模简单，能够清晰地体现算法的设计思想，使用效果良好，有广泛的应用背景，与其他课程的教学内容有联系”。比如讲贪心法，先通过活动选择问题介绍贪心法的设计思想，举出3种贪心策略，其中1种能够得到最优解，而另外2种是错误的；接着总结了贪心法的设计步骤，指出设计的关键是正确性证明，这是讲授的重点，也是难点；然后通过3个典型的例子详细阐述数学归纳法和交换论证的证明方法；最后在推广应用中介绍了最优前缀码、最小生成树、单源最短路径等具有广泛应用背景的例子，并以找零钱问题为例讨论对某些可能得不到最优解的贪心法如何对输入做参数化分析。
（2）从研究课题和算法领域的新进展中收集典型的实例。学生曾经参与芯片设计、视频检索、资源配置、搜索引擎、安全协议设计等各种问题的研究，其中不少内容都涉及算法和复杂性理论。把学生参与研究的课题成果引入算法教学，学生非常感兴趣，进一步认识到提高算法设计与分析能力的重要性。
3．教学环节
课堂讲授是重要的，但不是全部，学生素质的训练和能力的培养依赖于教学环节的整体设计，比如考核方式、课后作业、课程实践等。
（1）与本科算法教学强调上机实现不同，研究生算法课的课后作业主要以对实际问题的建模、算法设计与分析的训练为主，有关练习主要取自教材[5]。
（2）为了突出能力培养的要求，算法课的考核不但考查学生对相关算法知识的理解，更应该检查是否具有相应的算法设计和分析能力，对问题求解是否有一个正确的思路。设计试卷时实际应用试题至少应该占50%。
（3）对于某些学生课后主动阅读资料、结合科研课题进行算法设计与分析的工作给予更多的关注和指导，并在学习评价上给予鼓励。
（4）课程成绩评定采用综合评定的方式，根据不同教学要求，平时成绩占40%～50%，期末笔试占50%～60%。
4．教学环境
利用现代化教学手段，建立网上教学环境，进行课件发布、课下答疑、视频讨论等，更好地与学生进行交流。
在北京大学软件与微电子学院的大力支持下，经过多年的课程建设，硕士研究生算法课的教学改革取得了显著的成果。形成了面向软件工程学科的知识体系和教学设计，出版了“十一五”规划教材，开发了电子教案，同时积累了较多的教学资源，建立了老中青相结合的师资队伍。广大学生对算法课的教学也给予了高度的评价。
参考文献：
[1] 北京大学软件与微电子学院课程体系研究组. 北京大学软件与微电子学院课程体系[M]. 北京：高等教育出版社，2011.
[2] 教育部软件工程学科课程体系研究课题组. 中国软件工程学科教程[M]. 北京：清华大学出版社，2005.
[3] Jeannette M. Wing. Computational Thinking[J]. Communications of the ACM， 2006， 49（3）.
[4] 陈国良，董荣胜. 计算思维与大学计算机基础教育[J]. 中国大学教学，2011（1）.
[5] 屈婉玲，刘田，张立昂等. 算法设计与分析[M]. 北京：清华大学出版社，2011.
[责任编辑：余大品]
