具体数学论文

具体数学论文

有人要,就贴一下吧.
具体数学之我见
SA02011108 孙伟峰 研究方向；移动计算及网络
0． 序
本学期上了课程《具体数学》(－Graham and Knuth[1]）。虽说上课时候兢兢业业，课后完成习题，但是到目前为止还没有找到特别好的点进行深入的研究，诚惶诚恐，暂且写一些对该课程的感受及粗浅的想法，希望能够“蒙混过关”。
1． Graham and Knuth
对Ronald L.Graham并不是特别了解，但是对高纳德（Donald.E.Knuth）却是崇敬有加。TAOCP（）[2,3,4]的三卷，排版软件TeX，Metafont，KMP算法，36岁获得图灵奖，应该说是数学界和计算机界举足轻重的人物。有感于他的思维，是如此的发散跳跃，而且经常能够联系一些看似毫不相干的事情，一个小小的游戏，都会研究的特别深入，且善于从平常事件中找到自认为有意思的事情进行分析研究。比如说书中的整函数部分的轮盘赌问题，掷骰子问题，以及他最喜欢的ladders游戏问题[5]等。也许就是要幻想吧，科学都是想出来的，据说数理逻辑这门学科，就是一个哲学家在无所事事的时候，想出了这么一套谓词表示方法的离散数学的一个分支。拓展知识面，培养发散性思维，将一个领域中的解决方法应用到另外一个领域中，也许会取得意想不到的效果。比如说现在我们实验室的一个自然科学基金项目：市场经济模型的资源调度，就是要将经济学之中那些经过时间、社会考验的成熟的定律应用到网格的资源调度上面来。在基于角色的资源调度中，每个网格节点就是一个市场的实体，具有提供资源和请求资源的功能，而各个实体之间的行为、关系，则可通过经济学中的消费者和资源提供者之间的关系来进行操作，寻找网格资源当中的价值规律。在网络研究中，TCP的慢启动算法也广泛得到了应用，比如说QoS调度中寻找最大可获得服务质量的算法，在无线网络链路层中根据拥塞情况对发包进行调整的发包规则等。所以说，要有象Knuth一样的思维，兼容包并，从实际到理论，才也许会起到意想不到的效果。
2． 具体数学—计算机科学基础
2.1 什么是具体数学
在计算机系的学习当中，数学相关的课程我们学了很多。从大一时候的高等数学导论，到后面的离散数学系列，包括代数结构、图论、数理逻辑、概率论和数理统计、随机函数、组合数学，以及线形代数、数值分析、复变函数、数理方程等，都是从理论上去阐述数学的意义或者是数学和计算机的理论关系。当然，图论等课程中也涉及到一些具体算法的问题，如TSP问题、着色问题等。但是为博士生开设的具体数学课程，想要解决的是对于具体的问题，如何运用抽象的方法去解决，也就是理论如何应用于实际的问题。也有这样一种说法，即具体数学是计算机科学的基础，因为计算机学科就是从数学分支出来的Engineering。具体数学本身是对TAOCP第一部的扩展，比较注重在计算机科学领域内数学知识的应用，包括离散数学和连续数学都有涉及，这点在书的结构上就能看的出来。简单来说，具体数学这们课程就是讲数学在计算机学中如何应用，在计算机学中如何用数学来解决问题，是数学和计算机学的结合。
2.2 对本书的理解
从内容上来说，大部分还是熟悉的。递归、求和、整函数、数论、二项系数、离散概率都是在以前的课程中曾经涉及过的，特殊数在组合数学中有过组合意义上的解释，母函数也有一些接触，而渐进的一些概念，是算法课程中的复杂度分析要应用到的。但是从讲的形式来说，却是很不一样的。
2.2.1 递归
在对递归问题的解释没有从概念上讲什么是递归，也不是侧重写递归方程的方法，而是通过三个具体的问题汉诺塔、直线对平面的划分和Josephus三个问题来对递归进行感性的解释。
Josephus问题是个经典问题，在计算机中用程序解决这个问题的方法也有多种，但是该书中从两个角度教我们如何从理论上升华，并且对算法进行改进。从最简单的逢二杀一Josephus问题，对应到了2进制表示，并且发现这个问题的有趣的性质，从而对Josephus问题的求解只通过简单的二进制移位操作就可以实现。后来又将该问题扩展到不同进制Josephus方程类的一般形式。因为问题涉及到的域是整数域，在整函数部分，描述了编程解决Josephus问题，并对算法进行了简化，用比较简单的循环语句就较快的解决逢三杀一的Josephus问题。算法对逢二杀一的Josephus问题，应用移位操作，会更快的得到结果，这是具体编程的问题了。Josephus问题在数学上的解决，在计算机学科上涉及到了2进制和算法编写的问题。这对我们来说是一个工具，问题是如何构造具体问题使之对应于Josephus问题，Josephus的应用，书上并没有提到。
在令牌环网络中某些条件下的寻路是可以用到Josephus问题的：对令牌的分发问题，在N节点的令牌环网络中，若m个相邻的节点属于一组，我们所希望的是各个组轮流一个节点受到服务，这就演化为逢m杀一的Josephus问题。对有此种要求的网络，要设计一个令牌的分发算法，并对令牌进行修改。在令牌后附加计算Josephus数所需要的n值和N值，每一个节点在处理的时候要识别改造过后的令牌，并在受到服务后计算下一个n值和N值，保持Josephus数在一个计数器中，每经过一个节点，计数器减1，只有当计数器为0时，节点才能获得令牌。这样，保证了下一个能使用令牌的节点是Josephus问题中的解。另外，因为令牌要循环进行分发，在Josephus问题到了最后一个后，要对令牌附加消息中的n和N进行重新赋值。如果不用如此的处理方法，只在令牌上设置一个计数器，每隔m个节点服务一次，会出现有的节点获得不了服务的问题，要解决这个问题，就需要在节点上也设置一个计数器，受过一次服务，计数器加1。以初始值0为例，每个节点的计数器都为0，受过一次服务的节点中的计数器变为1，则该节点再收到令牌，则不接受这个令牌，把令牌传递给后继节点。这同样也有一个问题，即当所有节点都受到过一次服务，计数器都为1之后，如何让节点得知接受令牌，让计数器从1变为2。这个新的问题就又要求令牌进一步判断是不是所有的节点都服务到一次，有会增加复杂度。用Josephus数解决该问题的方法有如下缺点：扩展令牌，增大令牌的负荷；令牌环中的节点要进行计算（虽然计算量不大）；最大的缺点则是必须知道令牌环上所有节点的数目N。如果不知道N，而以一个大的数N’代替N，那么将出现什么结果呢？是不是能够找到一个大素数N’,使得用N’来代替N，同样能够遍历到所有的节点呢？现在的感觉是不行，因为对N’个节点，总可以有N’-N=m－1,这样，编号为1的节点在第二轮就又被重新编号，而这个节点，应该是已经被杀死过的。
在对等网络的P2P研究中，有一种叫Pastry网络，是根据对节点编号进行Hash形成一个环，是否用Josephus数会得到更好DHT呢？这种Hash方法，在对分组提供服务的情况下，可以快速的找到所要寻找的那一类资源，但是这种每类节点数目都大致相同的实际服务，好像还是太少了些。感觉Josephus数在实际网络应用中最大的问题，就是需要确切的知道初始N值。
2.2.2 和
本章新的知识是离散数域有限演算的部分，引入了新的算子，和实数域的有限演算对应起来，引入了差分算子对应微分算子，不定和算子来对应积分算子。为了对应有限域多项式求导的规律，还引入了下降阶乘幂和上升阶乘幂，并扩展到负数。对分部积分的规律也有所对应。可见整数域和实数域的运算是有对应的。要找到规律进行扩展，并创造新的一套对应规则，重要的是观察和寻找令人满意的特性。此部分中，为什么引入阶层幂、如何引入、以及阶层幂在负数上的扩展方式，给了我们很好的启发。
2.2.3 整函数和数论
关于整函数和模的介绍并不难，但是通过轮盘赌的实际例子，才让我知道如何实际应用区间、通过上整下整的范围转换来计算实际问题。以前确实并没有体会到这种“学以致用”。
数论部分中涉及到Stern-Brocot数，本身该数是构造有理数的一种手段，但是这种树的有趣之处是可以用LR两种操作的字符串来表示，L和R分别对应由单位矩阵经过一次简单运算的2×2矩阵，这同编译中的词法分析仿佛有着一定的联系。每一个字符串，经过词法分析（比如LR(0)分析），可以对应着一系列的LR操作，再将此串对应Stern-Brocot的LR序列，一个串就可以存储为一个数，这在压缩上是有用的。在串的匹配方面，也许也存在着特殊的形式。
在介绍莫比乌斯函数的时候，有一个反演定律，课堂上老师曾经说过可以对应于网络流量。感觉还不是很清楚，如果将节点的流入定义为1，流出定义为－1，没有流量定义为0，这样通过控制节点发送接受数据，可以得到莫比乌斯函数序列，并利用莫比乌斯函数的反演原理，也许可以观察到流量的某些特征。再比如在检测网络病毒时，如果知道病毒的特征码，并且这段特征码很长，如果能够通过反演找到较短的对应序列，也许会减轻测量检测的负担。同样是网络安全方面的问题，d作为密钥，将一段数据分成若干小部分加密，解密的时候就通过莫比乌斯函数进行解开，也许会增加可靠性。至于将反演定理中的g（m）用特殊函数进行研究，要看具体应用是否有对应某个具体函数。
2.2.4 二项系数和特殊数
二项系数是我们久已熟悉的东西，但是没有感觉到和计算机的紧密联系，倒是书中提到合流超几何级数在工程中有着重要的应用，也许是和计算相关的东西吧，不太明白，看来以后还要好好理解才是。
特殊数中有一些是组合数学中涉及到的，甚至Stirling数，Euler数就是从组合意义上得来的有趣的数列。调和数在物理上得到的特别广的应用，书上也举了一些例子。同样，Fibonacci数列也是特别有用的数列之一，课上老师也提到了广义Fibonacci数，这种Fibonacci数可以在组播算法中得到应用，对组播产生的包进行理论分析，得出组播中的包在网络中的分布及数目、对网络的影响，可以在组播的算法上给出指导。
2.2.5 母函数、离散概率和渐进
母函数，是解题的方法，是解题的一种工具。关键是如何找出对应的特殊序列。
和以前学过的离散概率不同，本书的离散概率侧重于用概率母函数解决问题，并用掷硬币的例子来详细说明。但是感觉和计算机相关最多的是式（8.73）的推导，书上却没有提到。如果时间充足，应该仔细讲一下，如何发现这么“有趣”的公式，而Knuth就在这方面有很强的能力，著名的KMP算法，就可以说明这一点。
渐进是算法分析中的重要部分，特别在分析时间复杂度和空间复杂度的时候。我们在写科技论文时，对提出模型的分析也是要用到渐进来简化的。在CMU博士的面试题中，经常会出现Back-of-EnvelopeCalculation的问题，也就是没有任何信息的情况下，进行数量级估算，也可以说是一种粗粒度的渐进。
3． 总结和建议
学过了具体数学的课程，知道了数学对计算机学科的指导意义，体会到了深层次研究的复杂，更是觉得前人们思想的深邃以及科学研究的从浅入深。本篇文章总结了一下自己对本课程的看法以及一些不成熟的想法，希望以后能发现新的研究点或完善上面的一些基本想法。
个人感觉，自己欠缺的是如何建模的问题，还有就是如何将这些数学公式应用到实际当中的问题。虽然书上有一些例子，但是感觉还是不够多，而用数学手段对数学公式的证明描述，对我们来说显得太多了。如果说以前没有接触到这些数学知识，这种组织会对数学和计算机水平都有提高。而作为面向博士生的课程，感觉还是应该多侧重于应用的例子，模型的建立方面，至少在我来说，我是想了解这些东西的。
文中的错误之处，请老师批评指正。
参考文献
[1] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik; Concrete Mathematics, Second Edition, 1994
[2] Donald E. Knuth, The Art of Computer Programming, Vol 1 : Fundamental Algorithms, Addison-Wesley, 1973
[3] Donald E. Knuth, The Art of Computer Programming, Vol 2 : Seminumerical Algorithms, Addison-Wesley, 1973
[4] Donald E. Knuth, The Art of Computer Programming, Vol 3 : Sorting and searching, Addison-Wesley, 1973
[5] Donald E. Knuth, The Stanford GraphBase : A Platform for Combinatorial Computing, Addison-Wesley, 1993

http://bbs.sjtu.edu.cn/bbsgcon?board=math&file=G.1039862049.A&num=214
<> 初读摘要
首先介绍一下这本书的作者，他们是听起来如雷贯耳般的 Ronald L. Graham 、Donald
E. Knuth、Oren Patashnik。

这本书是 Stanford 计算机系的教材（1970 年开始给研究生授课），附标题为 A FOUN
DATION FOR COMPUTER SCIENCE。Concrete 取名于Continus 和 Discrete 的前、后部分
，所以读起来跟普通的离散数学书有很大差别。全书共 9 章，每章后面附了不同层次的
练习题，给我的感觉是题目都很好，做了以后能对书中的内容起很好的巩固作用。

这里对每章做一个简单的记录：

第一章：Recurrent Problems
这章讲了三个递归函数的例子，都是很经典的，分别是：the Tower of Hanoi，Lines
in the Plane，the Josephus Problem。
前两个问题的解答都比较通俗易懂，而 Josephus 问题讲得很细，介绍了求解递归方程
的一些技巧，很多都是我以前搞数学竞赛的时候没有见过的方法。印象最深刻的是利用
数的进制表示来体现该问题解的一些性质。

第二章：Sums
该章以一句 "SUMS ARE EVERYWHERE" 开篇，接连介绍了 Sigma 符号、有穷无穷和式、
微积分跟与和式的联系。
其中 [Boolean Expression] 这钟记号是我第一次见到的，非常有趣。
对于无穷和式计算方法中一些常见错误求和方法给我深刻的印象。
微积分跟离散求和的关系更是让我看到了Concrete 的魔力。书中用了 7 钟方法来计算
{n^2} 的部分和，其中以积分法最为巧妙（还有就是 Harmonic Number 的近似表达式
）。

第三章：Integer Functions
Floor 、Ceiling、MOD 是这章的重点内容。其中以 Floor/Ceiling Sums 最为精彩。一
个相当有用的和 for k=0 to m-1 sum floor((x+kn)/m) = d*floor(x/d) + (m-1)*(n-
1)/2 + (d-1)/2 ， d=gcd(n,m) 让我记忆犹新（我高中的时候求过，但是怎么也求不出
来……）

第四章：Number Theory
这章介绍了初等数论方面的知识，跟一般的数论入门书讲的内容差不多，但是生动得多
。第 9 节 Phi and Mu 给出了一个非常有用的关系式。章末介绍了一个经典的组合计数
问题：Necklace 。书中对该问题的解法相当容易理解，比组合数学书中 Polya 原理和
Burside Lemma 给出的解答易懂太多了。另外，Relative Primality 里面的 Stern-B
rocot tree 和 Farey series 也很有趣。

第五章：Binomial Coefficients
最令我头大的就是这样,前面一般的内容我看起来都没有太大的问题，但是 Generatiin
g Functions 后面的 Hypergeometric Functions 开始就有点难啃了。那介绍的是一个
类似母函数的 "超几何分布函数" ，有很多很 amazing 的应用，但是我记得的却不多。
也许我以后要用到的时候会重新再读一边。

第六章：Special Numbers
这章介绍了 5 种数: Sirling Numbers 、Eulerian Numbers 、 Hamonic Numbers、Be
rnoulli Numbers、Fibonacci Numbers，给出了他们的一些性质（五花八门的和式……
）。 不少数并不只是讨论整数下标的，而是给出实数下标的表达式（多为积分表达式
）。

第七章：Generating Functions
母函数是讲计数内容的书里面不可缺少的一部分，这本书当然也不例外。一开始用一个
Domino 骨牌问题来介绍母函数，其中的表达方式相当有趣，非常适合初学该内容的人
看。

第八章：Discrete Probability
由于我以前没有学过概率，所以看起来非常新鲜，这章简单的介绍了这方面的一些理论
。看了第 5 节关于 Hashing 的例子对我来说非常有收获。

第九章：Asymptotics
全书的最后一章，讲渐近线表达式求法的。一开始介绍了计算机科学中常用的 O Notat
ion 。后面给出了一个非常强的 Euler‘s Summation Formula ，用于求一个函数 f(x)
类似于 g(x)+O(h(x)) 的表达式。

总的来说这本书对于提高数学修养非常有帮助.