【研究生精品课程】算法设计与分析:练好程序员的“内功”

文:何乔 张诗晗 学生记者团李湘叶 栾琦峰 图:软件学院 张诗晗 / 来源:新闻中心 / 2020-11-05 / 点击量:1325

编者按:为充分发挥精品课程的标杆示范作用,促进研究生课程质量进一步提升,研究生院自2018年启动了研究生精品课程建设工作,以公共基础课和各一级学科(类别)专业课为重点,充分结合国务院学位委员会学科评议组和全国专业学位研究生教育指导委员会编写的《研究生核心课程指南》,整体规划、分步实施,至2020年,经学院推荐、学校专家评审、研教指委审议通过,学校已立项了三批共146门“精品课程”。新闻中心特开设【研究生精品课程】栏目,分享这些“精品课程”基于“价值塑造、能力培养、知识传授”三位一体的教育理念,从课程目标与定位、课程内容、教学和考核方式、课程特色和成效等方面总结梳理其经验心得,与师生读者共享。本期介绍信息与软件工程学院刘瑶副教授在《算法设计与分析》课程中的教学探索。

  算法,是一个既熟悉又陌生的名词。我们从小学就开始接触算法,例如,做四则运算要先乘除后加减,从里往外脱括弧等等都是算法。而对计算机软件来说,做为灵魂的算法却要复杂得多,它涉及对数学知识的掌握,对计算机内部硬件结构的熟悉,对程序设计的学习……

  《算法设计与分析》对学生来说是一门相对较难的课程。从2017年开课以来,信息与软件工程学院刘瑶副教授精心设计课程内容,用耐心细致的讲解,以及自己独到的教学方法,引导学生掌握算法“思想”,为学生打下广泛扎实的算法知识基础。

微信图片_20201104164725.jpg

授人以渔:要掌握算法的“思想”

  在人工智能时代,人类的很多工作都可以依托计算机程序来实现。从电商平台的分类推荐,到医学成像分析,再到无人机的精准打击……计算机程序都展现出了其省时省力的优势。而对于一个程序而言,算法是其灵魂。好的算法不仅能缩短程序的运行时间,提高程序的响应效率,还能减少程序的硬件要求。大数据时代的到来,如何处理海量的数据成为了很多行业发展都需要面对的问题,这对算法也提出了更高的要求。刘瑶认为,学生将来要从事计算机系统结构、系统软件和应用软件等研究与开发工作,编程是“外功”,是具体的“招数”,而算法思维才是“内功”,是“武功心法”。

  刘瑶开设的《算法设计与分析》主要面向的是软件学院的同学,这学期还有一些医学院的同学也选修了这门课程。针对不同基础的学生,如何在40个学时内让他们掌握算法设计的主要方法,培养对算法复杂性正确分析的能力,进而为学生在接下来的学习和科研中独立设计和分析算法奠定坚实的理论基础,刘瑶深感时间紧、任务重。

  “授人以鱼,不如授人以渔”,掌握相关的问题,不如掌握求解问题的思想。刘瑶介绍说,算法主要包括:递归法、分治法、动态规划、贪心算法、回溯法、分支限界法、随机化算法、线性规划与网络流等相关算法。她在课程内容的设计中,根据课时的需要,删减了随机化算法以及线性规划与网络流两种经典算法,重点围绕其他6种算法讲解,并且每一种算法都会设计3~5个典型问题。结合具体的问题,从问题分析、算法的设计思想、到解决问题的思路以及编程过程,不放过任何一个细节。比如在讲到动态规划算法章节时,她会详细讲一个背包问题:N种物品和一个背包,每个物品的重量和价值都不一样,背包的总容量为15kg,如果每种物品只能放入背包一次,如何选择物品,才能使背包中物品的总价值最大?

QQ截图20201104165141.png

  而为了激发同学们的学习兴趣,她也会在上课过程中插入一些有趣的算法故事或者自己所在团队的一些科研成果。

  “随着时代的快速发展,算法的更新迭代也非常快。作为老师不可能交给学生所有的算法,而主要是让学生掌握经典的算法‘思想’,学会评估算法的优劣,以不变应万变。”刘瑶说。

开展研讨:让学生当“老师”

  本着课堂解决深度问题,学生自己解决广度问题,刘瑶会精选一些开源项目,开源软件代码库或从著名的开源软件项目中查找适合学生阅读的程序代码。她先通过阅读、分析源代码和相关文档,从整体上把握开源软件实例的体系结构,然后结合课堂教学,从不同角度出发,给学生分配代码阅读任务。“由于课程时间有限,让同学通过学习这些成熟的项目,可以多思考、多规划,同时提升设计眼界。”刘瑶说。

  如何把“学”和“做”更好地结合?刘瑶认为,作为一门研究生课程,除了对学生知识的掌握有要求,还应该培养学生把理论应用到实际或者是自己科研中去的能力。而课堂研讨,可以为学生提供思考问题和讨论问题的机会,使学生围绕相关的算法,应用所学的知识解决相关的问题。

  在课程中,刘瑶会鼓励同学们自主报名,组成小组,进行算法讲座。学生可以结合自己在团队的科研工作来介绍使用过的算法,或分析一些当前算法领域的优秀开源算法。在这个讨论交流的过程中,同学们可以有更深入的思考,增进对算法的了解。

1.jpg

  由于来自不同的课题组甚至有不同的专业背景,同学们的选题也多种多样。比如这学期来自医学院的张莉做了题为《Boyer-Moore算法与病毒DNA序列检测》的分享:研究发现,人类的DNA有8%来自病毒。一些病毒如肝病、艾滋病病毒,侵入人体以后会首先进行逆转录,生成DNA,并且把这个DNA插入人类基因的片段中。如果在人的DNA中检测出某种病的病毒DNA序列,则认为此人曾经患过这种病。她向其他同学介绍了自己如何利用Boyer-Moore算法,检测除DNA序列中是否有该致病序列。这让大家感觉耳目一新,开阔了知识面。

  在刘瑶看来,开展研讨式教学是时代所需。“老师必须要在课堂中充分调动学生的积极性,培养学生的自主学习能力、创新能力、研究能力甚至是表达能力,这样才能真正培养出担当民族复兴大任的领军人才和核心骨干。”

加强互动:“线上+线下”打造智慧课堂

  新冠肺炎疫情期间,广大师生“停课不停教、停课不停学”,各种线上教学工具发挥了重要作用。在线上授课的过程中,刘瑶开始使用“雨课堂”。这是一种基于微信平台的互动式智慧教学模式,老师和学生通过关注微信公众号,扫描二维码,可以实现课前教学资源推送,课程中实时答题、弹幕交流互动及课后数据分析等功能。

微信图片_20201104164641.jpg

  这学期虽然同学们已经回到了课堂,但是“雨课堂”的使用刘瑶仍然保留了下来,作为课堂教学的辅助。上课前,她会把课程PPT发送到学生手机上,每页课件下方都设置有“收藏”和“不懂”按钮,同时学生可以通过手机提问或者反馈上课效果。在课间的时候,刘瑶会查看同学们点了“不懂”的页面和大家提出的问题,然后在下一节课上进行重点讲解和解答。同时,她也会在课件中插入一些互动的问题,比如“影响算法性能的主要因素是什么?为什么?”促进同学们思考。刘瑶认为,相对于同学们线下举手提问的互动方式,大家在线上发言更踊跃,互动效果更好。

  精心设计的课程内容,良好的课堂互动也让同学们对这门课评价颇高。在软件学院2019级研究生李佳洲看来,刘瑶老师的课堂从容不迫、条理清晰,“在面对复杂问题时,刘老师会通过图解的方法将问题层层分解,把解决方案娓娓道来。通过刘老师的指点,大家能够更熟练地掌握以前接触到的算法。”

  软件学院2018级研究生娄云对这门课也印象很深,“刘老师非常的耐心细致,真正培养了我们的算法思维,这对于我论文的阅读和研究的开展帮助都很大”。

  当然,刘瑶对课程的探索还在继续。她目前正在进行开源软件项目的收集与筛选,希望建设一个用于《算法设计与分析》课程教学的开源项目源码库,培养更多算法精英人才。


编辑:何乔  / 审核:何乔  / 发布者:陈伟