欢迎光临!
您现在所在的位置:首页 >> 通知公告 & 学术信息
公告 & 新闻
NEWS & NOTICES
著名数学家Mikhail Volkov教授做客数学科学学院 第二期“文俊讲坛”
2019-04-26 尚建辉

       为了深入落实学在交大,引领风气之先,积极培养学生学术志趣,营造学数学、爱数学的浓郁学术氛围,在迎来吴文俊学长诞辰100周年之际,数学科学学院特设立“文俊讲坛”。 “文俊讲坛”第二期学术报告于4月24日下午1:30在理科大楼6号楼7楼大会议室举行,俄罗斯著名数学家Mikhail Volkov教授受邀作题为“Smart search: a practical facet of theoretical mathematics”的学术报告。数学科学学院讲席教授Tudor Stefan Ratiu,学院访问教授Marc Troyanov、Nguyen Tien Zung,数学科学学院吴耀琨教授、麻志浩教授、李吉有副教授、学院党委副书记高传勇老师等师生近百人出席报告会。



       Mikhail Volkov教授从数学视角为大家分析如何从纷乱复杂的海量信息中搜索重要有用信息这一难题,学术报告从一个数学趣题开始。一个典狱长管理着100个囚犯(编号1-100)。他在一个房间里将100个盒子摆成一排。每个盒子里有一个不同的囚犯的编号。囚犯们依次进入房间,选择打开50个盒子。如果每个人都可以在其打开的盒子看到自己的编号,那么囚犯们就会被释放。囚犯们被允许在第一个囚犯进入房间前进行讨论,但之后不能进一步交流。特别地,一个囚犯离开房间后,盒子的状态会恢复成他进入之前的样子。如果所有囚犯采取随机的方式选择盒子,那么每个人成功的概率是1/2。那么,他们获得自由的概率是2^{-100}。这个机会几乎等于0。Mikhail Volkov教授展示了一个策略可以使得囚犯们释放的概率超过30%。这个策略是:编号为k的囚犯进入房间后,先打开左起第k个盒子,如果他看到的纸片上的编号是t_1,那么他接下来打开左起第t_1个盒子,不断重复上述过程。事实上,这也是最好的策略。这背后的数学原理是”2n个元素的置换中,大约有31%的置换不含有长度超过n的圈”。

       Mikhail Volkov教授接下来介绍了数据恢复的一个问题:我们有个一张巨大表格记录了m个人的名字和他们对应的性别。我们希望用一个数据结构存储这些信息使得我们只使用(1+e)m个比特(其中e是一个小常数),并且可以当有人问一个人的性别的时候,我们可以快速的回答(常数时间内)。Mikhail Volkov教授介绍了一个算法将这个问题化归为解一个线性方程组,在e > 0.09时,这个线性方程组有很大的概率有解;在e > 0.23时,这个线性方程组可以在O(m)的时间内被解出。


       报告会结束后,Mikhail Volkov教授与出席讲坛的老师和学生代表亲切合影。


        数学科学学院设立“文俊讲坛”,旨在深入落实学在交大,引领风气之先,积极培养学生学术志趣,营造学数学、爱数学的浓郁学术氛围。讲坛以“创新学术,开启未来”为宗旨,定期邀请海内外有影响力的数学家和学者为学生做前究领域学术报告,尤其注重为本科生提供通识性学术报告,播撒下热爱数学、追求学术的理想种子;鼓励青年学子潜心数学,在求知之路上勇于攀登;抓住学生成长的“灌浆期”,拓宽学生学术视野,启迪创新思维与研究智慧。
        Mikhail Volkov教授于1994年在圣彼得堡大学获得俄罗斯国家博士学位(Doctor of Science degree in Mathematics),他长期担任乌拉尔国立大学代数与理论计算机科学研究所所长,2016年首位当选俄罗斯教育部首届俄罗斯联邦数学讲席教授,2017年当选芬兰科学与文学院外籍院士,2019年被德国研究基金遴选为Mercator教授。他是几个著名的理论计算机年度会议永久执行委员,是Semigroup Forum执行主编和多份国际杂志编委。他是自动机理论,字上组合学,半群与形式语言等重要研究方向上的研究领袖,谷歌学术引用近2500次,相关工作多次入选理论计算机顶级会议,并曾两次在CIAA会议获得最佳论文奖。

供稿:祝隐峰、尚建辉