6月15日上午，应中国科学院研究生院数学科学学院邀请，堵丁柱教授在玉泉校区开设了深受广大研究生欢迎的夏季学期课程《近似算法的设计与分析》，课程为期一周。
《近似算法的设计与分析》课程主要由以下8部分组成：（1）算法的相关知识：由确定图灵机和非确定图灵机引出P、NP的概念，讲解了经典的NP完备问题中的背包问题。（2）贪婪策略：分别介绍了独立系统、次模势函数和非次模势函数的近似贪婪算法，分析了目前几乎所有的贪婪算法的理论分析中所隐含的次模势函数，并针对Steiner树中的iterated k-stein tree问题讲解了新的分析方法。（3）讲解了Steiner树和生成树、k-Steiner树、贪婪k-Steiner树等问题的近似算法。（4）针对划分问题主要讲解了移位、双层划分及双重划分。（5）针对断切问题详细演示了如何将一个复杂的问题分解为若干个计算复杂度为多项式时间的子问题。（6）对于松弛问题，主要讲解了单位圆盘图上连通控制集的相关问题，并且给出传感器网络中的实际应用。 (7)在线性规划部分，介绍了单纯形法、组合舍入、迭代舍入以及随机舍入等各种不同的方法，并讲解了原始对偶方案与局部比值法。
每次授课结束，同学们都报以热烈的掌声。短短的一周中，堵丁柱教授的课程让同学们了解了在算法设计的理论与应用方面的最新科研动态和发展，使同学们开阔了眼界，更好地把握了相关科研的方向，受益匪浅。
堵丁柱教授是世界著名数学家。现任美国Texas大学计算机系教授。曾任美国自然科学基金委计算机理论的项目主管。长期从事组合优化、计算机网络和计算理论、算法与复杂性研究。目前已经发表论文160多篇，编著出版了40本学术著作。他曾获国家自然科学二等奖、中国青年科学家奖、美国格雷汉姆奖和CSTS奖，是国际组合优化与复杂性研究的著名学者和带头人之一。他于1982年从中国科学院应用数学研究所取得硕士学位后赴美留学，1985年获美国加州大学数学专业博士学位，先后在加州大学、麻省理工学院、普林斯顿大学、明尼苏达大学等多所知名高校任职。 此外，堵丁柱教授为了推动我国与国际的数学界交往，开拓青年科学工作者的眼界。
作者：王慎娜
