改革视点

分享到微信 ×
打开微信“扫一扫”
即可将网页分享至朋友圈
【研究生精品课程】《算法设计与分析》:算法的精义是“无招胜有招”
文:王晓刚 学生记者团 陈心洁 苟灵 图:陈心洁 来源:新闻中心 研究生院、党委研究生工作部 时间:2020-04-23 11408

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

肖鸣宇 教授.jpg

  “如何利用有限的计算资源对计算问题进行求解?”这是计算机学院副院长肖鸣宇教授钻研科学问题的理念;“如何让学生掌握算法的精义,达到‘无招胜有招’的境界?”则是他针对研究生的培养和教学理念。

  在为研究生讲授的《算法设计与分析》课程中,怎么样让学生明白算法的奥秘,依然是肖鸣宇教学的初心和梦想。在讲课时,他会教给同学们具体的某种算法,但是,他并不希望学生只局限于具体的算法。

科教融合提升含金量,“算法”成为抢手课

  《算法设计与分析》是计算机科学与技术、网络空间安全专业的核心基础课,也是软件工程专业的专业选修课。从2014年开始,肖鸣宇就为研究生开设这门课程,很快就成了最受学生欢迎的课程之一,也是计算机专业最难选的课程之一。

  肖鸣宇十余年来一直从事算法与计算理论方向的研究,在精确算法、参数算法、核心化算法、近似算法、组合优化等方面取得了系列重要科研成果。他从计算问题解空间的结构出发,探索计算复杂度的上下界,提出了一系列新的算法分析与设计技巧,丰富了算法设计的理论体系,对进一步理解计算的本质做出了重要贡献。

  例如,在精确算法上,他为“最大独立集问题”设计了当前最快精确的算法,突破了30年无人能改进的时间运行界限;在参数算法上,为10余个基本NP难问题设计了当前最优的参数算法,其中两项结果被参数算法领域的会刊《参数计算快报》收录;在图优化分割方面,解决了一个10余年的公开难题,为“超图多块优化分割算法”提供了理论保证。

  这一系列基础算法的研究成果,不仅已经应用到了医学、生物计算、社会计算、网络、VLSI等领域中,解决了很多实际问题,而且也融汇到了他的课程内容当中,实现了“科教融合”,转化成为培养学生、启发学生、拓展学生思维、提升学生创新能力的“营养大餐”。

  肖鸣宇认为,计算机具有强大的编程功能,是与其他大机械学科(如汽车、航天等)存在差异的本质特点,而算法是编程的核心。但编程与算法并不完全相同,与编程相比,算法更强调思维的逻辑性、严谨性及计算的方法。

  因此,他对这门课程的定位是,“更多讲述算法思维的传授与练习,更有逻辑、更严谨地对计算机的优点进行有效利用”。开课6年以来,学生对这门课的反馈很不错,上课时出勤率高,毕业时在找工作、接受面试时,学生表现的包含较高逻辑性的算法思维,更容易受到用人单位的青睐。

肖鸣宇教授 02.jpg

算法思维才是最核心,得其“意”而忘其“形”

  大部分算法教学,都将算法与技术相提并论,认为不管什么样的程序,只要能执行就可以,甚至可以机械地带入已知的算法解决问题。然而,肖鸣宇却认为,在教授《算法设计与分析》这门课程时,不应该把算法当作具体的技术向学生传授,而应当作一种艺术来让学生“心领神会”。他说,“要让学生学习算法时体会到艺术的美妙!”

  然而,难点在于,怎么样让学生站在更高的层面理解这种“艺术”呢?肖鸣宇认为,学习具体的算法就像在学习“武功”的“一招一式”,如果机械地学习算法,在“临阵对敌”时只能机械地生搬硬套,不能做到随心所欲、见招拆招。与武侠小说中的“武功心法”一样,只有实现了从“有形”到“无形”的转变,才能达到从“有限”到“无限”的境界。

  因此,在上课时,他不断提醒学生,算法不是一门技术,并不是学会了一种算法就可以解决很多问题,甚至在大多时候,学会一种算法只能解决一个问题。掌握了几种算法,可能只解决已知的几个问题,而我们要面对的却是更多的未知和挑战,尤其是层出不穷的新现象、新问题,这就需要我们忘记招式,理解算法的本质。

  肖鸣宇说,学生要转换观念,需要一个过程。很多学生起初并不习惯这样的教学方式,因为在传统的学习观念中,似乎只要把知识点背熟,把命令记熟练,就可以解决问题了。但是,他告诉学生:“即使把整本书背下来,考试时可能依然无法顺利解题!”

  比如学生在学习“贪心算法”((Greedy algorithm,又称“贪婪算法”)时,即使学习了四五个“贪心算法”,并且老师在出题考试时标明要使用“贪心算法”,学生也无法圆满解决。这是因为,“虽然这类算法都叫‘贪心算法’,但不同问题有不同的性质,需要用不同的策略解决问题。”

  因此,在教学过程中,肖鸣宇一方面从知识的角度,帮助学生掌握一些经典的算法,如“排序算法”、“最短路径”等知识点;另一方面从思维培养的角度,用严谨的数学推理,培养学生举一反三的思维能力。有的学生带着这种思维研读经典论文,甚至发现了其中的不足。

课堂教学需要下功夫,通俗易懂妙趣生

  在教学过程中,肖鸣宇基于国外经典教材,即美国康奈尔大学的《算法设计》教材,建立了教学主线。这部教材从算法思维出发,章节安排很有逻辑,是他多年来一直使用并觉得很不错的教材之一。

  在此基础上,他不断尝试教学改革,一方面使课程更多地与学术研究挂钩,让学生在研读论文时,领会如何把算法与自身的研究结合起来,在自己的研究中高效利用算法。另一方面,他从思维改变的角度,改变原来算法教学中抽象的部分,运用“可视化”的动画把一些算法流程呈现出来,让学生更容易理解。

  例如,在讲解经典问题“稳定匹配”时,他形象地把问题转化为“一个男孩挨个儿向女孩们求婚”的故事。这个问题描述的是:有N位男生和N位女生最后要组成稳定的婚姻家庭,求偶配对之前,男生和女生在各自的心目中都按照喜爱程度对N位异性有了各自的排序,然后开始选择对象,最终要达到所有配对稳定的情况。

“稳定匹配”问题 截图.png

通俗讲解“稳定匹配”问题

  在这里,肖鸣宇运用动画的形式,演示了算法如何在“稳定匹配”问题中实现了“非诚勿扰”的效果,使课程教学更具艺术性,妙趣横生,让学生看得津津有味。除此之外,他还用动画形式直观地展示了“冒泡排序”等算法问题。

  当然,除了讲课的方法之外,对学生的激励也十分重要。肖鸣宇在第一次课上,常以学生考研奋战的图片激励他们:“不要忘记自己考研时的激情!”另外,他还会介绍往年选修这门课的学生如何成长为大牛“学霸”,并列出详细的“光荣榜”刺激和鼓励学生,“要像他们那样追求优秀,你也可以这样优秀!”

记住曾经战斗过的地方.png

激励学生“不要忘记自己考研时的激情!”

  肖鸣宇以“立德树人”为根本,活跃在教学一线,取得了系列优秀的教学成果:每年坚持开研究生课程,年平均课时超过100个,每年研究生课程教学评价均为优秀。他积极探索新工科背景下的复合型人才培养和拔尖人才培养,主持教育部和四川省教改项目各1项,获得国家级实验教学示范中心一等奖;他培养的学生连续两年获得IEEE极限编程全球第2名、荣获ACM程序设计竞赛世界总决赛第13名。

  “肖老师把理论和实例结合起来,让我们掌握了算法的思想精髓。他还引导我们自主探索、合作交流,激发我们对算法的兴趣。”计算机学院2019级研究生胡珊同学表示,“通过这门课程,我学会了很多新知识,更重要的是,我学会了从不同角度思考问题!”



编辑:王晓刚  / 审核:王晓刚  / 发布:陈伟

分享到微信 ×
打开微信“扫一扫”
即可将网页分享至朋友圈