2009年春季低年级讨论班介绍.docVIP

2009年春季低年级讨论班介绍 本次低年级讨论班将由姜明、马尽文、夏壁灿三位教授共同主持，分别讨论三个主题：莫尔现象的数学理论、基于数据的学习与挖掘、P vs NP 问题。 在讨论班的第一次课上，三位老师将分别简要介绍三个专题。然后，同学们可以按兴趣组成1-3人的学习小组，在老师指导下阅读文献并作讨论班报告。可以只做一个专题的阅读和报告，但应该参加每次课。最后按各专题的要求进行考查。 欢迎低年级同学报名参加。 一、莫尔现象的数学理论 莫尔一词来自法文的“moire”，其原来的含义是波动的，或起波纹的。在我国古代，人们就发现当两块薄的丝绸织物叠在一起时，可以看到一种不规则的花纹。后来人们将两组或者多组条纹叠加在一起所产生的图形称为莫尔条纹。在日常生活中，两块窗纱叠在一起时可以看到这种莫尔条纹。现在，莫尔现象已广泛用于科学研究和工程技术之中。莫尔条纹作为精密测量手段可用于测角、测长、测振等领域。从70年代开始，莫尔条纹又广泛用于三维物体的表面轮廓测量。在有的领域中，莫尔条纹又是需要避免和尽量消除的，例如对于半色调丝网印刷。下图是莫尔条纹的例子： Figure 1：取自(Amidror 2000)图3.3。 在讨论班中，我们将讨论莫尔现象的数学理论，主要参考资料是(Patorski 1993; Amidror 2000)。需要的先修知识是傅立叶级数理论。参加的同学按兴趣组成1-3人的学习小组，在老师指导下阅读文献并作讨论班报告。考查的基本要求：按学习小组提交读书报告、完成数种情形的莫尔现象的计算机模拟。参考文献： Amidror, I. (2000). The theory of the moiré phenomenon. Dordrecht, Kluwer Academic. Patorski, K. (1993). Handbook of the moiré fringe technique. Amsterdam; New York, Elsevier. 二、基于数据的学习与挖掘 本专题在讨论班中，我们将讨论。参加的同学按兴趣组成1-3人的学习小组，在老师指导下阅读文献并作讨论班报告。考查的基本要求：按学习小组提交读书报告、完成的计算机模拟。 三、P vs NP 问题 同学们一定知道“P vs NP”这个著名的问题。2000年5月，在新千年来临之际，美国的CMI（Clay Mathematics Institute）公布了七个悬赏百万美元的数学问题，“P vs NP”问题就是其中之一。 不同于其他动辄上百年历史的数学难题和猜想，“P vs NP”问题只有不到40年的历史，它源于计算机科学的复杂性理论。人们把可计算的问题按计算所需的时间和资源分类（称作复杂性类），P和NP就是其中最重要的两个时间复杂性类。“P vs NP”问题可简单地表述为：NPC问题（NP类中“最难”的问题）是否属于P类？ 与许多著名的数学难题一样，“P vs NP”问题陈述简单、易于理解，但解答却极其困难。简单地讲，“P vs NP”问题的实质就是：如果你能容易地验证某个问题的解，那么，你也能容易地求出这个问题的解吗？在当今这个日益计算机化的世界里，可以想象这个问题的解决会从理论到实际对人类产生多大的影响！自1971年 Stephen Cook 和 Leonid Levin 分别独立地提出“P vs NP”问题以来，人们进行了大量的探索和研究，正在帮助我们进一步理解“P vs NP”问题（主要是NPC问题）。 本专题拟采取老师和同学共同阅读和讲解的方式，主要探讨以下几个方面： 1. （主讲老师）问题介绍，包括计算理论（图灵机）、复杂性定义、3SAT问题（第一个NPC问题）； 2. （主讲老师）相关研究介绍，包括一些别的NPC问题、不完全算法、PCP理论、相变现象研究等； 3. （老师和同学）经典的NPC问题都来自逻辑、数论、图论等领域，经典的研究方法主要来自离散数学（当然，相变现象的研究使用统计物理的方法）。S. Smale 等人于八十年代末、九十年代初期推广了经典的图灵理论，建立了任意环上的计算模型，由此引入了大量新的NPC问题。这些问题多来自连续数学的各个领域，如代数几何、拓扑等。这为人们利用强大的连续数学的成果研究“P vs NP”问题提供了可能。我们拟仔细研读Smale 等人的专著“Complexity and Real Computation”。 考查方式：同学可以按兴趣组成1-3人的学习小组，分别研读和讲解相关文献，最后写读书报告。