1701018140
1701018141
（3）算法的选择。
1701018142
1701018143
如果研究的问题，其规模n是确定的，此时解题所需的时间主要与计算机的速度和选择的算法有关。
1701018144
1701018145
以fA （D，n）表示用算法A求解规模为n的问题所需的运算次数。要缩短运算时间或在一定时间内能解更大规模的问题，其主要办法为：提高计算机的速度和改进算法，减少运算次数。
1701018146
1701018147
首先考虑前者的影响。如果现有的计算机每小时解题的规模为n，则用了快100倍、1 000倍的新计算机后，一小时所能解决问题的规模会如何变化？请看表8.4.1。
1701018148
1701018149
表8.4.1 计算机速度与解题规模之间的关系
1701018150
1701018151
1701018152
1701018153
1701018154
从上述表格中，可以看出：算法复杂性为规模n的多项式时，计算机成倍提速后，相应地解题规模也成倍增长；对算法复杂性为指数函数的算法，例如当f A （D，n）=3n时，计算机提速1 000倍后，解题规模n只能增加6.29。所以，对指数函数的算法，单纯靠计算机提速来增加解题的规模n，收效甚微。因此转向算法的研究是必要的。
1701018155
1701018156
首先对算法进行分类：如果存在多项式P（n）和正整数n0，使得当n＞n0时，恒有fA （D，n）＜P（n），则称A为解决问题D的多项式算法，又称为有效算法，或好算法。如果fA （D，n）是n的指数函数，则称算法A为解决问题D的指数型算法，又称为“坏”算法或“无效”算法。例如，求解旅行售货员问题就是指数型算法。
1701018157
1701018158
对于一个算法复杂性为n80的问题，虽然是多项式算法，但实际上也是不可接受的。因为280≈1024是一个“天文”数字，在现实情况下几乎不可能算出结果。幸运的是，一个实际问题一旦找到多项式算法，经过一系列的改进，其算法复杂性一般会降到n的三次多项式，甚至更低。因此有理由相信，多项式算法总是有效的。
1701018159
1701018160
我们定义的算法复杂性是考虑所有可能情况下，算法的运算次数。而实际上，有些算法只是在“最坏的情况”下才呈现指数型的增长，在一般情况下则很有效，因此仍然被人们广泛采用。例如，求解线性规划通常使用单纯形法，在一般情况下的平均运算次数是规模n的多项式，速度很快，但已经证明它在“罕见”的情况下是一个指数型的算法。
1701018161
1701018162
大多数的指数型算法，只是穷举搜索法的变种。只有对问题的结构充分了解后，才有可能给出多项式算法。解决实际问题时，当然要寻求多项式算法。但如果一个问题已经被证明没有多项式算法，再寻找精力就白费了，因此有必要对实际问题进行分类。
1701018163
1701018164
P问题和NP问题 对于一个实际问题，如果其存在多项式算法，则称为P问题（polynomial problem）。对P问题研究的中心问题是如何改进现有的计算方法使运算次数更少。如果已经证明不存在多项式算法，则我们认为这一个问题是难问题。对于难问题，一般只能寻找可以接受的近似算法。
1701018165
1701018166
还有一类实际问题，称为判定问题；是能用“是”（有）或“不”（无）来回答的问题。例如，问用2 500元能够购置29英寸的彩色电视机吗？回答这个问题“能”时，不必知道当前市场上29英寸彩电的最低价，只需了解确有价格不超过2 500元的29英寸彩电出售即可。对于一个判定问题，如果对所有回答为“是”的实例，都存在多项式算法来验证它的正确性，则称此判定问题为NP问题（不确定多项式问题，non-deterministic polynomial problem）。显然P问题一定是NP问题。
1701018167
1701018168
1971年，美国计算机科学家库克（Stephen Cook，1939—）发表了一篇十分著名的论文《The Complexity of Theorem-Proving，Association of Computing Machinery》。他首先指出，NP问题中存在一类称为NPC问题（完备问题，non-deterministic polynomial complete problem）。这类问题有如下特性：
1701018169
1701018170
（1）类中每一个问题至今尚未找到多项式算法；
1701018171
1701018172
（2）如果类中任一个问题有多项式算法，那么该类中其他问题都有多项式算法（即这类中的任意两个问题都存在多项式算法相互转化）。
1701018173
1701018174
到目前为止，NPC问题已被扩充为近千个，其中包括旅行售货员问题。许多优秀的数学家、理论计算科学家在过去几十年来，试图寻找它们的多项式算法都没有成功。这越来越使人们相信，对它们也许根本不存在多项式算法。然而要证明这一猜想，既是有重大意义的，又是十分困难的。2000年5月24日Clay数学所宣布七个“千禧年数学难题”，每一个悬赏一百万美元征解，其中的第一个问题就是这个猜想。这个猜想的解决实属渺茫，有理由相信，不提出一套全新的数学理论和方法，这个问题的答案是不会出现的。
1701018175
1701018176
1701018177
1701018178
1701018179
数学文化教程 [:1701013764]
1701018180
数学文化教程 第五节 金融数学“华尔街革命”[2]
1701018181
1701018182
狭义的金融学是指金融市场的经济学。现代意义下的金融市场至少已有300年以上的历史，它从一开始就是经济学的研究对象。但人们通常认为现代金融学只有不到50年的历史。这50年也就是使金融学成为可用数学公理化方法架构的历史。
1701018183
1701018184
从瓦尔拉斯-阿罗-德布鲁的一般经济均衡体系的观点来看，现代金融学的第一篇文献是阿罗于1953年发表的论文《证券在风险承担的最优配置中的作用》。在这篇论文中，阿罗把证券理解为在不确定的不同状态下有不同价值的商品。这一思想后来又被德布鲁所发展，他把原来的一般经济均衡模型通过拓广商品空间的维数来处理金融市场，其中证券无非是不同时间、不同情况下有不同价值的商品。但是后来大家发现，把金融市场用这种方式混同于普通商品市场是不合适的。原因在于它掩盖了金融市场的不确定性本质。尤其是其中隐含着对每一种可能发生的状态都有相应的证券相对应，如同每一种可能有的金融风险都有保险那样，与现实相差太远。
1701018185
1701018186
这样，经济学家又为金融学寻求其他的数学架构。用新的数学来架构的现代金融学被认为是两次“华尔街革命”的产物。第一次“华尔街革命”是指1952年马科维茨的证券组合选择理论的问世。第二次“华尔街革命”是指1973年布莱克—肖尔斯期权定价公式的问世。这两次“革命”的特点之一都是避开了一般经济均衡的理论框架，以致在很长时期内都被传统的经济学家认为是“异端邪说”。但是它们又确实使以华尔街为代表的金融市场引起了“革命”，从而最终也使金融学发生根本改观。马科维茨因此荣获1990年诺贝尔经济学奖，肖尔斯（M.Scholes，1941—）则和对期权定价理论作出系统研究的默顿一起荣获1997年的诺贝尔经济学奖。布莱克（F.Black，1938—1995）不幸早逝，没有与他们一起领奖。
1701018187
1701018188
马科维茨研究的是这样一个问题：一个投资者同时在许多种证券上投资，那么应该如何选择各种证券的投资比例，使得投资收益最大，风险最小。马科维茨在观念上的最大贡献，在于他把收益与风险这两个原本有点含糊的概念明确为具体的数学概念。由于证券投资上的收益是不确定的，马科维茨首先把证券的收益率看作一个随机变量，而收益定义为这个随机变量的均值（数学期望），风险则定义为这个随机变量的标准差（这与人们通常把风险看作可能有的损失的思想相差甚远）。于是，如果把各证券的投资比例看作变量，问题就可归结为怎样使证券组合的收益最大、风险最小的数学规划。对每一固定收益都求出其最小风险，那么在风险-收益平面上，就可画出一条曲线，它称为组合前沿。
1701018189