• 2007-08-25

    [读书笔记]《离散数学及其应用Discrete Mathematics and its applications (Fifth Edition)》笔记-Chapter3&4 - [阅读]

    版权声明:转载时请以超链接形式标明文章原始出处和作者信息及本声明
    http://www.blogbus.com/sgzxy-logs/7928104.html

    Discrete Mathematics and its applications

    Written by (U.S.)Kenneth H. Rosen

     笔记-Chapter3&4 

     

        Chpater 3&4都是以前学过和比较熟悉的内容。3是介绍数学证明方法:演绎、归纳和递归,4则是讲授初步的排列组合知识。新内容不多,可以大量跳读。

     

    Chapter 3 Mathematical Reasoning, Induction, and Recursion

    思想1.有限递减法(Infinite Descent

    16世纪由费马提出的证明思想,在“Chapter2-原理1-原理[2]-*)证明”中已经体现。大致思想如下:

    欲证明命题P(n)对于一切正整数均不成立,则假设P(n)成立,根据使P(n)成立的n值的偏序关系性质,至少存在一个最小正整数s使P(s)成立。接下来要做的就是再找出一个s’<s,证明P(s’)也成立。则引出矛盾从而得证。其实也就是反证法的一种分支思想。

     定理1. 拉梅定理(Lame’s Theorem

    对于正整数a,ba>=b),利用Euclidean算法求gcd(a,b)时所需要进行的除法次数不超过b十进制位数的五倍。

     

    在计算复杂性分析中,它的证明是一个非常出色的范例。下面进行证明。

     Lemma:记f[n]为第n个菲波那契数(Fibonacci),则当n>=3时,f[n]>α^(n-2),其中α=( 1+sqrt(5) )/2

    //sqrt( )=开平方 square root

    证:利用数学归纳法,设引理命题为P(n)

        基础步骤:α<2=f[3],α^2=(3+ sqrt(5) )/2<3=f[4],所以P(3)P(4)为真。

        归纳步骤:假设P(k)为真。

                  注意到α是一元二次方程x^2-x-1=0的一个根,则有α^2=α+1。因此有

                  α^(k-1) = α^2*α^(k-3) = (α+1)α^(k-3) = α^(k-2) + α^(k-3)

              根据归纳前设,有f[k-1]>α^(k-3)f[k]>α^(k-2)

    那么对于n=k+1,根据Fibonacci数的定义,有

              f[k+1] = f[k]+f[k-1] > α^(k-2) + α^(k-3) = α^(k-1)

              所以P(k+1)也为真。

    证明完毕。

     

    Theorem证:设利用Euclidean算法计算gcd(a,b)需要n步除法,过程如下:(a=r[0] b=r[1]

                r[0] = r[1]*q[1] + r[2]         0<=r[2]<r[1]

                r[1] = r[2]*q[2] + r[3]         0<=r[3]<r[2]

               

                r[n-2] = r[n-1]*q[n-1] + r[n]   0<=r[n]<r[n-1]

                r[n-1]=r[n]*q[n]         //r[n]=gcd(a,b)

                

    可知r[n]>=1r[n-1]>r[n],故有

                r[n] >= 1 = f[2]

                r[n-1] >= 2*r[n] >= 2*f[2] = f[3]

                r[n-2] >= r[n-1] + r[n] >= f[3] + f[2] = f[4]

               

                r[2] >= r[3] + r[4] >=f[n-1] + f[n-2] = f[n]

                b= r[1] >= r[2] + r[3] >= f[n] + f[n-1] =f[n+1]

                则根据Lemma可知b = f[n+1] > α^(n-1),其中α=( 1+sqrt(5) )/2lg(α)~0.208>(1/5)

                则有lg(b) > (n-1)*lg(α) > (n-1)/5。证毕。

     

     Chapter 4 Counting

    概念1. 拉姆齐理论(Ramsey theory

    Ramsey theory研究抽屉原理(鸽巢原理)的推广形式,也即集合中元素在各子集中的分布问题。

    例子命题:一组六个人,两两之间有朋友或者敌人的关系,那么此六人组必存在一个三人组,这三人组中要么两两朋友,要么两两敌人。

    又可考察,若组中只有五人时,上述例子命题的结论不成立。则我们可把最终结论记为R(3,3)=6

    R(m,n)叫做拉姆齐数(Ramsey number),定义为满足“存在一个两两第一关系的m元组或者两两第二关系的n元组”的最小集合的元素数(此集合之间所有元素两两均有关系)。

    目前已知道R(4,4)=18,而大多数Ramsey number只是知道范围,如R(5,5)[43,49]

    (实际上我觉得,研究Ramsey number也是个图论问题,就像对边进行染色然后寻找边同色完全子图,这个貌似一个NP难度)

     

    定理1. 范德蒙恒等式(Vandermonde’s Identity

    m,n,r均为非负数,且r<=m,n,则有      m+n                    m        n

                                       (     ) = Sigma(r,k=0)(       )(     )

                                          r                     r-k      k

    注:括号表示“排列”

    (可以从逻辑上直接证明)

    分享到:

    评论

  • "..............

    定理1. 范德蒙恒等式(Vandermonde’s Identity)

    ..................



    (可以从逻辑上直接证明)"



    括号里的话不是很理解,是指组合论证吗?即:

    考虑从m个男秘书和n个女秘书中选r个秘书,

    然后用两种不同办法去算,分别得到等式两边的式子。



    回复mathchain说:
    呵呵对,就是这个意思。
    2007-08-29 19:19:57