5月28日，美国计算机协会（ACM：the Association for Computing Machinery）的算法和计算机理论专业组（SIGACT：Special Interest Group on Algorithms and Computing Theory）宣布，滕尚华教授及其合作者荣获2008年哥德尔（Gödel）奖。
滕尚华是姚期智讲席教授组成员之一，美国波士顿大学计算机系教授，卡耐基梅隆大学博士。主要研究方向为计算几何、最优化、互联网算法等。他们此次的获奖工作是Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time。
哥德尔奖是理论计算机科学领域的最高奖项，由EATCS和ACM SIGACT共同评选。
(http://sigact.acm.org/prizes/godel/, for outstanding papers)，与美国工业与应用数学学会（SIAM)乔治·波利亚奖(George Polya Prize,http://www.siam.org/prizes/sponsored/polya.php, to recognize specific recentwork)和ACM SIGACT以算法设计大师克努特命名的克努特奖(Knuth Prize,http://sigact.acm.org/prizes/knuth/, for major research accomplishments andcontributions over an extended period of time)齐名。
滕尚华1985年获得上海交通大学计算机、电子双学位。他也是Akamai科技公司的高级研究人员，清华大学姚期智讲席教授组成员。他曾在麻省理工学院的数学系、明尼苏达大学和伊利诺大学香槟分校的计算机科学系任教。他和MIT的Dan Spielman一起，发展了以建模和分析实际算法为目标的平滑分析理论，并且示范了线性规划的单纯形算法具有多项式平滑复杂性。这项工作被国家科学基金会（FY’03）所支持。他的研究关注于高效算法设计和实现。
他的研究兴趣还包括光谱技术优化和信息处理、并行科学计算、计算几何、超大规模集成电路和线路模拟、组合优化和可能性分析、分布式计算和密码学。在编译器优化和因特网技术方面，他获得过7项美国专利。
算法的复杂度分析是软件系统设计与分析中的一个重要环节.为了分析算法的复杂度,我们常常对算法进行最坏情况复杂度分析.长期以来,人们一直为这样的现象所困惑,有很多算法按通常的(最坏情况)分析具有很坏的复杂度(通常是指数级的),但在实际应用中却很有效.这类算法的一个典型代表就是优化问题的单纯形算法.20世纪80年代初,人们用随机方法分析了单纯形算法,并证明了对输入参数的一系列分布,单纯形算法的期望执行时间收敛于多项式复杂度.但是,在随后20年里,很多人的研究指出,这种统计平均的多项式复杂度并不能很好地解释单纯形算法的实际有效性,因为它的输入参数的统计分布具有很特殊的性质,在实际应用中很罕见.另外,算法的平均复杂度与输入实例空间上的概率分布有关,不同的分布其相应的平均复杂度未必相同,而且输入实例空间上的概率分布一般不容易得知.
为了更合理地解释这样的现象,美国麻省理工学院的Daniel A.Spielman与波士顿大学的滕尚华提出了计算机算法的平滑复杂度(smoothed complexity)概念.Spielman和Teng在STOC 2001的论文[1]中提出了一种新的算法复杂度分析方法,即算法的平滑复杂度分析.
他们的思路是这样的,在分析一个算法时,对输入实例加上合理的微小幅度的随机"扰动",然后分析执行时间与输入规模及扰动的关系,由此得出的时间复杂度称为该算法的时间平滑复杂度.分析算法的平滑复杂度,其目的在于探测输入实例空间中是否含有最坏输入实例的稠密区域.Spielman和Teng在文献[1]中分析了"两阶段投影-顶点"单纯形算法的平滑复杂度,证明了"两阶段投影-顶点"单纯形算法在具有给定规模的所有可能的输入实例的局部随机邻域上,其最高平均时间复杂度是多项式的,更合理地解释了单纯形算法虽然具有很坏的最坏情况复杂度(时间复杂度为指数级),但在实际应用中却很有效之间的矛盾.自文献[1]发表以来,这一领域的研究在理论计算机界引起了极大的关注并取得了一系列的成果[2].
[1] Spielman DA, Teng SH. Smoothed analysis of algorithms: Why the simplexalgorithm usually takes polynomial time. In: SIGACT,ed. Proc. of the 33rdAnnual ACM Symp. on Theory of Computing. ACM Press, 2001. 296~305.http://www-math.mit.edu/~spielman/SmoothedAnalysis/papers.html
[2] Spielman DA, Teng SH. Smoothed analysis of algorithms. In: LI T, ed. Proc.of the 2002 Int'l Congress of Mathematicians,Abstracts of Plenary and InvitedLectures. Beijing: Higher Education Press, 2002. 144~145.http://www-math.mit.edu/~spielman/SmoothedAnalysis/papers.html
评论 (0)