2021年5月8日,beat365手机中文官方网站邀请上海交通大学计算机系教授陈翌佳为学院2018、2019级卓越班同学作题为《参数复杂性》学术报告。陈翌佳长期从事计算复杂性方面的研究,特别是对于参数复杂性具有很高的造诣。
报告中,陈翌佳从城市监控摄像头的安装覆盖问题入手,引出了最小集合覆盖问题;从最简单的枚举算法、分治算法,到最后的并行算法,逐步提升算法的效率。在各种算法的介绍过程中,他普及了关于一阶逻辑的有限模型论、电路计算模型等相关知识,以及它们和算法设计之间的关系。会后,不少同学提出了各种问题,体现出浓厚的兴趣。
鉴于卓越班同学们的积极反响,5月12日,陈翌佳教授再次来到学院作关于《区块链、公钥密码学和计算复杂性》的报告。他通过区块链所涉及的技术,向大家科普了公钥密码学和计算复杂性的相关概念,并讨论了量子计算机的前景,以及量子计算机对公钥密码学的影响。
部分同学感想:
2018级卓越班柳潇然:
陈翌佳老师今天关于k-vertice-cover的报告,从最朴素的brute-force方法,到有简单优化的bounded-search-tree方法以及buss-kernelization优化,最后到基于AC0电路模型的深入优化。整个过程,举重若轻,干脆利落,既有关于color coding原理的简要叙述,也避开了大量枯燥的推导过程,使得整个报告深入浅出又不至于枯燥乏味,过渡顺畅又不拖泥带水。同时,陈老师激情的演讲风格以及形象的板书演示,又赋予这样抽象的理论以活力,让我听得饶有兴致,让我对这种模拟电路高效求解NP问题的思路有了大致的认识;此外,陈老师在最后提问环节的耐心解答,也让我们对k-vertice-cover问题以及NP问题的高效求解有了更加深入的体会。
2018级卓越班张子涵:
此次讲座中,陈翌佳教授提纲挚领地为我们介绍了k-vertex cover的相关算法。在讲座过程中,我们了解了针对k-vertex cover问题的两个朴素算法,基于AC0电路的高效并行算法以及其中用到的buss kernalization,color coding等技术。讲座的最后,陈翌佳教授还为我们介绍了color coding算法在k-path problem中的应用。在此次讲座中,我既了解了关于k-vertex cover问题的学术进展,同时,由于在k-vertex问题中多次运用到了算法设计以及数理逻辑中的一些知识,我也充分认识到了专业课的重要性,让我获益良多。”
beat365手机中文官方网站的“卓越计划”为奠定学生的专业基础、扩宽知识面和前瞻性视野,培养其完整的人格,将不定期开展前瞻性的科学、文学、哲学等讲座,敬请期待。