许晓云">许晓云博士报告中

 

    6月25日和26日下午, 来自美国亚利桑那州立大学工业工程系的 许晓云">许晓云博士在澳门太阳娱乐网站官网湍流实验室做了两场学术报告，题目分为为“An Introduction to Combinatorial Algorithms and Intractability”和“Algorithm and Analysis: From Recurrence to Asymptotic Notations”。两场报告均由工业工程系系主任 王龙">王龙教授主持，澳门太阳娱乐网站官网的部分师生出席了该报告会。

 

    许晓云">许晓云博士的首场报告对组合算法以及复杂性理论进行了简要介绍。　该报告通过引入多项式时间算法的概念，阐述了决策问题(decision problem) 和优化问题(optimization problem) 之间的区别和联系，并引入了解决算法相关问题的理想机器：图灵机。许博士简要介绍了确定性图灵机与非确定性图灵机的结构特征，从而引入了Class P和Class NP 的概念，进一步提出了Class P 与 Class NP 是否的相等的命题。该报告还介绍了Class NP 集合中的一个重要子集 NP-Complete, 以及它在复杂性理论以及计算机科学领域的重要意义，并简要介绍了证明一个问题属于NP-Complete的方法。

 

    许博士的第二场报告对算法，特别是算法在计算机领域的应用进行了综合介绍；对算法的定义，时间复杂性，空间复杂性分别进行了阐述。该报告还进一步介绍了算法复杂性的通用表达： Big O Notation 以及相应的表达式组，为描述算法增长率、比较算法速度以及复杂性理论的数学基础。许博士通过比较不同算法同样时间解决问题的个数，以及同样问题解决的时间来直观的指出算法复杂性的研究的重要性。此外，该报告还简要介绍了当算法用递归形式表现时其复杂性证明方法，包括substitution method, master method以及generating functions等。

 

    许博士的报告引起了参会师生的极大兴趣，大家在报告后进行了热烈的提问和讨论。

 

    许晓云">许晓云博士，1980年生，本科毕业于北京清华大学工业工程系，并在美国亚利桑那州立大学工业工程系取得了硕士和博士学位。主要从事复杂网络、计算机网络的服务的优化与保障、数据挖掘等方面的研究。现在2138cn太阳集团古天乐工业工程与管理系进行博士后研究。