上海交通大学计算机系陈翌佳教授为beat365手机中文官方网站卓越班同学作报告分享
发布时间:2021-05-19 浏览量:1916

       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手机中文官方网站的“卓越计划”为奠定学生的专业基础、扩宽知识面和前瞻性视野,培养其完整的人格,将不定期开展前瞻性的科学、文学、哲学等讲座,敬请期待。

 

华东师范大学beat365手机中文官方网站
学院地址:上海中山北路3663号理科大楼

                上海市浦东新区楠木路111号
院长信箱:yuanzhang@sei.ecnu.edu.cn | 办公邮箱:office@sei.ecnu.edu.cn | 院办电话:021-62232550
Copyright Software Engineering Institute


XML 地图