数学欣赏2011版课件

《数学欣赏2011版课件》由会员分享，可在线阅读，更多相关《数学欣赏2011版课件（65页珍藏版）》请在金锄头文库上搜索。

1、深圳大学数学与计算科学学院,数学欣赏,Mathematics Appreciation, ,第六节 七个千禧年数学难题,七个千禧年数学难题,（2000年5月24日：巴黎 ）,Clay Mathematics Institute,Riemann猜想,1,（Riemann假设）,1. 素数数的原子 素数：不能再真正分解的自然数。 算术基本定理：任何自然数都在一定意义下具有唯一的素数因子分解。 欧几里得：素数有无穷多个。（反证法） 问题：素数分布如何？是否有一定模式？,1. 素数数的原子,素数的间隔： 素数可以间隔很近！ 孪生素数（猜想）： ,；,；,；,； ,1. 素数数的原子,素数的间隔：,素数

2、可以间隔很远！ 任何自然数N： N!+2, N!+3, N!+(N-1), , N!+N, 连续N-1个数全是合数！,1. 素数数的原子,素数的间隔：,定量的结果： 对每个自然数，在 N 和 2N 之间一定有素数。 猜想：在 N2 和（N+1)2 之间一定有素数。,2.高斯的发现：素数定理 素数似乎越来越稀有！ 稀有到什么程度？ 素数密度： P(N):不超过 N 的素数个数。 D(N):前N个数中素数的密度，D(N)= P(N)/N,2.高斯的发现：素数定理,素数定理：D(N) 1/ln N, (N 时） 即 P(N) N/ln N, (N 时) 1791年，高斯（14岁）猜想， 1896年，

3、阿达玛、普桑证明。,2.高斯的发现：素数定理,两点启示： 1.素数虽然似乎是随机出现（就像掷硬币一样），但是它们逐渐趋少的方式是可以预见的！ 2.素数（离散量）分布的规律与对数函数（连续量）密切相关。,3. 欧拉的发现： 函数与素数的关系 富有哲理的思想： 数学的不同分支不是孤立无关的，而是相互联系的。数学犹如一块高低起伏的地域，它的许多地方被茂密的森林所覆盖，被浓厚的迷雾所笼罩。要看清其本来面目，需要选择适当的角度、适当的高度去观察。,3. 欧拉的发现： 函数与素数的关系,素数是数轴上的离散点，要看清素数可能不仅要站在数轴上（比如，用对数函数），可能更需要站在平面上。欧拉注意到，调和级数,是

4、发散的（无穷大）。,3. 欧拉的发现： 函数与素数的关系,但是，当 s 1 时,却是收敛的（有限数）。比如,3. 欧拉的发现： 函数与素数的关系,鉴于此，欧拉于1740年提出了函数,多项式函数有两种表示方法，即 P(x)= anxn + an-1xn-1 + + a1x + a0 和 P(x)= an (x-x1) (x-x2) (x-xn) 。 仿照多项式情形，欧拉把函数表示为无穷乘积的形式：,3. 欧拉的发现： 函数与素数的关系,3. 欧拉的发现： 函数与素数的关系,欧拉注意到，当 s 1 时，正项级数,的和与各项的顺序无关，而每一个自然数n都可以分解为若干个素数幂次之积。因此,为什么呢？

5、,3. 欧拉的发现： 函数与素数的关系,其中pj是不同的素数，而kj是自然数，且和式中每个这样的组合取且只取一次。,3. 欧拉的发现： 函数与素数的关系,考虑到,便得到,3. 欧拉的发现：函数与素数的关系,这表明：函数与素数具有密切关系,4. Riemann猜想（Riemann假设） 黎曼 (Bernhard Riemann,18261866)：高斯的学生。现代数学观念的起点。 关于数学本性的许多现代观念来自于黎曼。 最先认识非欧几何本质； 数学的本质是概念和联系（模式的科学）； 直觉与悟性。,黎曼G.F.B., (RiemannGeorg Friedrich Bernhard)1826 年9

6、 月17 日生于德国汉诺威的布雷斯塞伦茨 (Breselenz)；1866 年7 月20 日卒于意大利塞拉斯卡(Selasca)。,4. Riemann猜想（Riemann假设）,4. Riemann猜想（Riemann假设）,黎曼看到欧拉的函数中包含了所有素数的信息。如同多项式一样，这些信息应该完全由其零点所决定。但是，这个函数自身对于大于1的正实数，其值永远大于0. 这意味着，单在正实数上观察它是无法认清其面目的，因此，黎曼把它解析开拓到复平面上，叫黎曼函数，这成为了解析数论的起点。,4. Riemann猜想（Riemann假设）,正如多项式的情形一样，函数的信息大部分包含在其零点的信息当

7、中，因此，黎曼函数的零点就成为大家关心的头等大事。 可以知道，黎曼函数在负偶数 2, -4, -6 , 等处有零点，人们称这些为“平凡零点”。,4. Riemann猜想（Riemann假设）,1859年，黎曼提出猜想：素数不仅有无穷多个，而且这无穷多个素数以一种微妙和精确的模式出现。这种模式依赖于黎曼函数。 他指出，如果黎曼函数的所有非实数零点都满足虚部为1/2，那么他可以直接证明素数定理（尽管那时还没有素数定理，后来阿达玛证明时也没有用到这一猜想）,Riemann猜想是关于黎曼函数的非平凡零点的特征的，具体表达为：,Riemann猜想（1859年） 黎曼函数的所有非平凡零点的实部等于1/2，

8、即满足,5. Riemann是如何猜想的？,黎曼提出该猜想的一个可能的原因是，他发现了函数的下述性质：存在一个函数(s)，使对所有s1,这说明函数在s点处的值与在1-s处的值具有某种对称性，而对称轴就是Re s =1/2.,Poincare猜想,2,Poincare猜想 已经解决了,庞加莱(Poincare)猜想 任何单连通的三维流形（正如我们所在的宇宙空间）一定是一个三维球面。,P 对 NP 问题,3,这个问题与哲学上什么是可知的，什么是不可知的问题密切相关,属于计算复杂性理论。 问题的根源在于哥德尔不完备性定理。该定理认为： 在数学的任何包含初等算术的部分中，不论写出多少公理，总会有一些命

9、题不能通过这些公理得到证明。,1. 背景,从计算角度看，在任何公理系统下，总存在一些函数，它们在这个系统中是不可计算的。于是，他不得不建立一种关于“可计算函数”概念的形式理论。,1. 背景,一对重要的问题是：“验证答案”与“找到答案” 的难度问题。 通常，验证一个答案是容易的，而找到答案可能是极端困难的。,2. 验证答案与寻找答案,设想在一个盛大晚会上。你想知道这一大厅中是否有你已经认识的人。你的朋友向你提议说，你一定认识那位正在甜点盘附近角落的女士丹丹。不费一秒钟，你就能向那里扫视，并且发现你的朋友是正确的。 然而，如果没有这样的暗示，你就必须环顾整个大厅，一个个地审视每一个人，看是否有你认

10、识的人。生成问题的一个解通常比验证一个给定的解时间花费要多得多。,2. 验证答案与寻找答案,四则运算时间 我们知道，两个数进行四则运算，两个数的位数越多，运算时间（步骤）也就越长。 由于两个一位数相加或相乘可以由大脑的储存信息（记忆）直接给出答案，我们把这叫做一个基本步骤（时间）。于是，容易知道： 两个（不超过）n位数相加最多需要2n个基本步骤。,3. 多项式时间与指数时间,四则运算时间 对于乘法，两个n位数相乘则需要处理n2个乘法步骤以及由此产生的至多n2个进位加法步骤，还有n个至多n+1位数的求和步骤（不超过（n+1）2个），总数少于5n2个. 因此 两个（不超过） n位数相乘最多需要5n

11、2个基本步骤。,3. 多项式时间与指数时间,四则运算时间 类似的可以知道： 两个（不超过） n位数相减最多需要2n个基本步骤。 两个（不超过） n位数相除最多需要45n2个（包括试商过程）基本步骤。,3. 多项式时间与指数时间,四则运算时间 因此，两个（不超过） n位数相加减，所需基本步骤数与n具有线性（一次）关系；两个（不超过） n位数相乘除，所需基本步骤数与n具有二次关系。 一般，如果对某一类问题，其数据规模为n时，需要至多Cnk个基本步骤来处理，则称该类问题的解决需要“多项式时间过程”。,3. 多项式时间与指数时间,流动推销员问题与过程调度问题 流动推销员问题：一个推销员，他可能要负责几

12、个城市的商品推销，一个自然的问题是，如何设计行走路线，可以保证各个城市都走一遍的总路程最短？ 过程调度问题：在工厂产品生产过程中，往往需要多个工序，每一个工序需要一定的时间，而且可能还依赖于其它工序的完成。问：如何进行时间调度或分配，可以使效率最高？,3. 多项式时间与指数时间,流动推销员问题与过程调度问题 流动推销员问题：如果是3个城市A，B，C，那么可能的路线有 ABCA; ACBA; BACB; BCAB; CABC; CBAC。 共六种路线。分别计算其总里程再进行比较即可。,3. 多项式时间与指数时间,流动推销员问题与过程调度问题 流动推销员问题：如果是10个城市，容易知道可能的路线有

13、10! = 3628800种 如果每条线路总路程计算时间为1分钟，这十个城市的路线全算一遍需要一个人在正常工作时间内计算20年。如果再增加一个城市，则时间扩大11倍，要两百多年时间才能算出。,3. 多项式时间与指数时间,流动推销员问题与过程调度问题 流动推销员问题：一般地，如果是n个城市，容易知道可能的路线有n! 种，这随着n的增大将以极高的速度增大，它们跟n的关系不再是简单的n的若干次方的事情，而是，以指数形式（比如2n)、甚至高于指数形式（比如nn)增长. 当n达到一定程度后，即使用超级计算机也没有办法完成这个计算。这种情况称为“指数时间过程”。,3. 多项式时间与指数时间,对于流动推销员

14、问题，刚才谈到的是穷举对比方法。这是比较幼稚的方法，因此会造成极端的复杂化。由于城市布局本身通常有某些特点，比如顺序、方向等因素，所以对于一批给定的城市，策略的方法是先考虑城市布局，把明显不合理的路线不予考虑，这样可以大大简化计算的数据量，从而就完成一个理论上不可能完成的计算。但其缺点是，换一批城市，哪怕是增加一个城市，就要从新考虑。,4.穷举对比与策略对比,对于一个“多项式时间过程”问题，随着数据量的增加，其运算量会增加，但是并不会大得惊人，用计算机去解决是完全可以的。这类问题我们称之为P问题。 而对于一个像流动推销员问题这样的指数时间过程问题，随着数据量的增加，其运算量会大得惊人，以致于用

15、超级计算机都无法去解决。,5. 多项式时间与非确定性多项式时间,指数时间过程问题之所以会从理论上产生用超级计算机都无法去解决的困难，其原因有两点：一是其计算量只是可能的计算量（可能性），二是计算机的计算方式是按照确定的规则以一种完全可以预期的方式去工作。但是有时候，如果计算机会进行某种逃避劣势、选择优势的决策性（具有不确定性或随机性）计算，则一个指数时间过程问题依然可以通过相关的决策在多项式时间过程内完成计算。,5. 多项式时间与非确定性多项式时间,一般地，如果一类问题，可以用一台能进行某种逃避劣势、选择优势的决策性计算机（具有不确定性，称之为非确定性计算机）在多项式时间过程内完成计算，则称这

16、类问题为“非确定性多项式时间过程”问题，简称NP问题。 显然，P问题都是NP问题。从直觉上看，NP问题介于P问题与指数时间问题之间。,5. 多项式时间与非确定性多项式时间,人们发现，在工业和管理中出现的大量指数时间问题都是NP问题。使得它们很难解决的原因并不是有关的计算很复杂，而是人们要对大量实质上相同的情况重复进行某些相对简单的计算。 问题：是不是这些问题本质上是P问题呢？也就是说，我们是否有一种算法可以让计算机按照指定的程序在多项式时间内完成这一问题的计算呢？ 所有的NP问题一定是P问题吗？,5. 多项式时间与非确定性多项式时间,判定一个答案是可以很快利用内部知识来验证，还是没有这样的提示而需要花费大量时间来求解，被看作逻辑和计算机科学中最突出的问题之一。它是斯蒂芬库克(StephenCook)于1971年陈述的。,5. 多项式时间与非确定性多项式时间,NP完全性问题 库克于1971年证明，存在一个NP问题，如果这个NP问题能用多项式时间过程解决，那么任何NP问题都能用多项式时间过程解决。这样的问题被称为是NP完全性问题。后来人们发现很多问题都是NP完全的，