辛勤耕耘,喜庆丰收——记计算几何算法专家周培德教授

时间:2010-09-25
  大家都知道,计算机科学的核心是算法。发现高效的算法是推动计算机科学技术发展的主要动力之一。无怪有“计算机界的诺贝尔奖”之称的图灵奖得主中有很多是算法专家。
  但是,研究算法是一件十分吃力、辛苦的工作;发现新算法更是谈何容易。因此许多人对算法望而生畏。在我国,称得上算法专家的寥寥可数。但在北京理工大学,有这样一位老师,几十年来在算法领域,尤其是在计算几何算法领域,辛勤耕耘,刻苦攻关,并取得了丰硕的成果。他就是周培德教授。
  周教授原是数学老师,20世纪70年代转入计算机的教学和科研,并选择诞生不久的计算几何这一难度较大、但应用很广的领域作为自己的主攻方向。计算几何研究些什么?有什么意义呢?举几个浅显的例子吧:

1. 皮革裁剪问题。给定一张形状不规则的牛皮,另外给定一双或几双拟投产的皮鞋鞋片,鞋片的形状也是极不规则的。要求估算这张牛皮能裁多少双这样的皮鞋,并给出具体的裁剪方案。如果牛皮上有小洞,裁剪时应避开这些小洞。许多行业都存在类似的问题,比如服装、家具、造船、印刷等。这个问题对节约原料、提高劳动生产率显然具有重要的意义。

2.任意多面体面上两点之间的最短路径。这里所说的多面体具有复杂表面,比如地球的表面,它有高山、丘陵、河流、山谷、平原等很不相同的地貌,要求最短路径紧贴地表,不能遇山挖洞、见水架桥。这个问题十分困难。但对公路、铁路建设,管道铺设等无疑非常重要。

3.多台数码相机从不同角度、不同距离拍摄同一目标,可以得到不同的图像。如何判断这些图像中的目标是同一个还是不同个?或者一台数码相机在不同时刻拍摄同一目标,图像也有所不同,不仅大小可能相差甚远,甚至形状都可能发生变化。怎么判断它们实际上是同一目标?这个问题在国防、军事、公安等许多领域都可以遇到。


  几十年来,据周教授自己统计,他独立的发明了大大小小228个算法,解决了或大或小的大约200个问题。这些问题分为两大类,即基础问题与应用问题。其中有不少问题是周教授在国内外首先提出并进行详细研究,获得结果的。有些问题前人虽然研究过,但周教授另辟途径,获得了复杂性远低于前人的更好结果。一些算法,如有关平面点集和平面点线集的三角剖分问题的算法,已在地质勘探和石油勘探中获得应用,取得了巨大的效益。

  周教授的研究成果结晶为一部厚厚的学术专著----《计算几何----算法设计与分析》(清华大学出版社)。第一版于2000年出版后,广获好评,2005、2008年先后出了第二版和第三版,第四版又即将出版,并成为“中国计算机学会学术著作丛书”中有较大影响的一部专著。它至今也是国内唯一一部有关计算几何方面的著作。同国内大部分算法设计与分析的著作中主要介绍国外的算法不同,周教授的这部书中绝大部分算法是作者自己提出来的算法,这一点使这本书特别与众不同和引人注目。
基于周教授在算法领域的丰硕成果和影响,《程序员》杂志在2006年4月推出“算法的力量”专刊的时候,专访了两个专家,其一是大名鼎鼎的李开复,另一位就是周教授。
  那么,周教授的这些算法的水平到底怎么样呢?2008年6月,在由教育部科技发展中心主持的鉴定会上,以著名算法专家卢开澄(清华)为主任,以院士汪顺亭和黄琳(北大)为副主任的鉴定委员会经过严格的资料审查、讨论和质疑,做出如下结论:“…成果具有重要的理论意义和实用价值,推动了计算几何理论、方法及应用的发展和完善,达到了国内领先、国际先进水平。”同年,周教授的研究成果获得了北京市科学技术一等奖,这是我校第一次获得该奖项的一等奖。
  周教授的工作也得到了国外同行的肯定。周教授根据自己在计算几何领域几十年研究的经验和体会,经过深入思考,提出了该领域15个有待解决的问题(爱因斯坦曾经说过,提出问题比解决问题还重要!)。对此,美国史密斯学院计算机系主任、世界闻名的计算几何专家欧洛克(Joseph O’Rourke,他是权威的Computational Geometry in C 一书的作者)在发给周教授的电子邮件中说:“你列出的15个问题说明你是天才,有创造力”(Your list of open problems shows you are talented and creative.)。
  认识周教授的人都知道,他身体单薄,是一个典型的文弱书生。是什么力量推动周教授忘我地工作,并且有如此成效?主要有两个原因。一个是兴趣,周教授对计算机算法情有独钟,长期研究它,不仅不厌倦,反而产生了浓厚的兴趣,一天不研究算法就觉得浑身难受,一个月不出成果就感到十分惭愧,就要检查自己的创新能力是否减退了。另一个是责任心,周教授看到目前国内出版的算法书籍中,几乎无一例外都是介绍外国人发明的算法,难以见到中国人自己的创造,感到这同中国这样一个大国的地位不相称,“中国人不应该只在运动会上拿金牌,应该在科学技术方面同样对人类做出贡献。”
  周教授说:“也许这就是付出吧,没有付出,哪有收获,所以要准备吃苦、吃大苦。在钻研紧张的时候我常常吃不下饭、睡不好觉,严重影响身体健康,甚至影响寿命。不过这是合算的,因为这些研究成果丰富了学科的内容,并为后人提供了较为有效的算法,同时本人也获得了成功之后的快乐,这种快乐与花钱买来的快乐是无法相比的。”
  周教授现在在业界已经出了名,登门拜访、请教的人不少,企业的技术人员,高校的教师、博士生…都纷至沓来,甚至科学院评选院士也请他审查材料。周教授对每一个来访者都热情接待,尽其所能的提供帮助(这些帮助常常是无偿的),并始终保持谦虚的态度。
我们祝周教授青春永驻,活力常存,在算法研究中取得更大的成果!