图灵奖得主Robert Tarjan 做客海外名师讲堂主讲搜索树之谜

  清华新闻网4月13日电(通讯员 吕厦敏)4月12日,图灵奖得主、美国科学院院士、美国工程院院士、美国人文科学院院士、美国普林斯顿大学罗伯特·塔扬教授(Robert Tarjan)做客“清华海外名师讲堂”第119讲,在清华大学信息技术大楼多功能厅作《搜索树之谜》特邀报告。

图为Robert Tarjan教授作报告。

  清华大学交叉信息研究院院长姚期智教授为Robert Tarjan颁发“清华大学海外名师讲堂第119讲”纪念牌。

图为姚期智为Robert Tarjan颁发纪念牌。

  Robert Tarjan教授介绍,搜索树是古典数据结构,对于数据库和许多其他计算机应用而言至关重要。他详细论述了平衡二叉树(AVL树)的发展历史,带领同学们一同探索其中蕴含的巨大设计空间和奥秘。Tarjan教授结合自己最近的工作,描述了一种定义和分析平衡搜索树的新框架、一种具备特优性能的新型平衡树,以及一种通过插入而非删除方式来维护平衡的方式。

图为讲座现场。

  讲座结束后,Robert Tarjan教授与在座师生深入探讨交流了“搜索模型”、二叉查找树的“懒惰删除”(lazy deletion)等问题。

  清华大学交叉信息院师生近200人参加讲座。

  Robert Tarjan教授是世界知名计算机学家,因LCA、强连通分量等算法而闻名,研究领域主要包括图论,算法和数据结构设计。1986年Robert Tarjan教授与John Hopcroft因为在算法及数据结构的设计和分析中所取得的决定性成果而荣获图灵奖,提出了数据结构中著名的B树。Robert Tarjan教授是许多图论算法的发明者,比如著名的Tarjan's off-line least common ancestors algorithm;他于1982年获得首届奈望林纳奖,现为美国科学院院士、美国工程院院士、美国人文科学院院士、美国计算机协会(ACM)会士、美国哲学学会会士。

供稿:交叉信息研究院 编辑:范 丽

  

 

2012年04月13日 09:29:49  清华新闻网

更多 ›图说清华

最新更新