西交《离散数学》第二章拓展资源1

欧阳老师

西交《离散数学》第二章 关系 拓展资源1
离散数学是计算机科学与技术专业的一门重要学科，它以研究离散量的结构和相互间的关系为主要目标，所涉及到的一些概念、理论和方法被大量地应用于其他学科中。例如，数理逻辑在应用于人工智能理论研究的同时，着重培养了学生的概括抽象能力、逻辑思维能力、归纳构造能力；图论和集合论不仅为数据结构和算法科学奠定了数学基础，同时也为软件工程和数据库提供了抽象和描述的重要方法。
然而，由于这门课程具有概念多、理论性强、高度抽象等特点，学生普遍反应难于理解掌握，同时由于学生知识面的局限又导致学生认为该门课程对专业知识无用，致使学生学习兴趣不高，教学效果不理想等现象。因此，激发学生的学习积极性和主动性，培养学生的创新意识和创新能力成了离散数学教学的当务之急。而在离散数学的教学过程中适当的引入一些实验设计，不仅是对离散数学的基本理论的很好验证，也锻炼了学生计算机语言的操作能力，同时也为其他课程的学习做了一个很好的铺垫。本文将以关系理论为基础，深入探讨离散数学实验设计的可行性。
2 关系理论的实验可行性
在离散数学中，关系理论是其一个重要的组成部分，它的知识点主要包括关系的性质、关系的复合、逆运算和闭包运算、关系的划分和覆盖，以及等价关系、相容关系、序关系几种特殊的关系，这些内容都可以建立在矩阵的基础上，因此本文以关系理论为基础，设计了一个系统的模型，在加深学生对理论理解掌握程度的同时，也有效地锻炼了学生的编程操作能力，激发了学生的学习兴趣。
3递归关系
递归关系可以很容易解决一些比较深奥的问题，将问题简化，但是由于递归算法将占用大量的资源。由于递归运算的资源消耗非常大，所以大家通常都禁忌使用递归。然而仍然有很的问题不可避免的要使用递归。在离散数学中，提出了一些简化递归关系的方法。
这里主要介绍迭代法与常系数齐次线性递归关系法。
★迭代法。
利用迭代法求解序列a0,a1,……递归关系时，先根据递归关系用an前面的a0,a1,……,an-1若干项表示an。然后反复利用递归关系a0,a1,……,an-1替换，直至an的显式公式。
例1．种群数目的增长。设n=0时刻Rustic County有1000头鹿，每过一个单位时间（从n-1到n），鹿的数目增长10%。给出鹿数目的递归关系和初始化条件，并用迭代法求解递归关系，得到n时刻鹿的数目表达式。
解：将n时刻鹿的数目记为dn，故初始化条件为d0=1000。
n-1到n时刻，鹿的数目增长dn-dn-1，为n-1时刻鹿数目的10%。可得递归关系dn-dn-1=0.1dn-1，即有dn=1.1dn-1。
利用迭代法求解递归关系dn=1.1dn-1=……=(1.1)nd0=1000(1.1)n。可见，这是一种指数增长关系。
例2．完成含有 个圆盘的Hanoi塔难题至少需要移动cn步，求序列{cn}的显式公式。
解：cn有其递归关系cn=2cn-1+1和初始条件c1=1。
将迭代法用于该递归关系，有
cn=2cn-1+1=2(2cn-2+1)+1=……=2n-1c1+2n-2+…+2+1=2n-1
★常系数齐次线性递归。
形如an=c1an-1+c2an-2+…+ckan-k,c<>0的递归关系称为常系数 阶齐次线性递归关系。
定理1．令an=c1an-1+c2an-2为常系数二阶齐次线性关系。若S和T为递归关系式的一个解，则U=bS+dT也为递归式的解。
若 为方程t2-c1t-c2=0的一个根，则序列rn(n=0,1,…)的递归关系式的一个解。
若a为式递归式定义的序列，a0=C0,a1=C1。且r1和r2为方程t2-c1t-c2=0的根，r1<>r2。则存在常数b和d，使得an=br1n+dr2n,n=0,1,…成立。
例3．种群数目增长。设在n=0时刻Rustic County有200头鹿，n=1时刻有220头鹿。n-1时刻到n时刻鹿增长的数目是n-2时刻到n-1时刻鹿增长数目的两倍。给出定义n时刻鹿数目的递归关系和初始条件，然后求解递归关系。
解：令dn表示n时刻鹿的数目。初始条件为d0=200,d1=220。
根据题目中的说明，可以得到一个递归关系式dn-dn-1=2(dn-1-dn-2)，即dn=3dn-1-2dn-2。
根据递归关系式，可得的二次方程t2-3t+2=0，该方程有两个根1和2。所以该递归序列可以表示成了dn=b*1n+c*2n。为满足初始条件，有方程组
200=d0=b+c
220=d1=b+2c
解该议程组，得b=180,c=20，则有dn=180+20*2n。
例4．Fibonacci序列的显式公式。
解：对于Fibonacci序列，有二阶齐次线性递归关系
fn-fn-1-fn-2=0,n>2
初始条件为f1=f2=1。
根据递归关系式，有方程t2-t-1=0，解方程得t1=(1+50.5)/2和t2=(1-50.5)/2。所以递归关系式可以表示为
fn=b((1+50.5)/2)n+c((1-50.5)/2)n
根据初始条件，有方程组
1=f1=b((1+50.5)/2)+c((1-50.5)/2)
1=f2=b((1+50.5)/2)2+c((1-50.5)/2)2
解方程组，得b=5-0.5,c=-5-0.5。所以Fibonacci序列的显式公式为
fn=5-0.5(((1+50.5)/2)n-((1-52)/2))
定理2．令an=c1an-1+c2an-2为常系数二阶齐次线性关系。令a0=C0,a1=C1。
方程t2-c1t-c2=0有两个相等的根r。则存在常数b和d，使得
an=brn+dnrn,n=0,1,…
成立。
例5．求解递归关系
dn=4(dn-1-dn-2)
初始条件为d0=d1=1。
解：根据递归关系式，得二次方程
t2-4t+4=0
解该二次方程得到根t1=t2=2。
根据定理可以确定，递归式可以表示为dn=a2n+bn2n,n=0,1,…。
由初始条件，可以得到方程组
1=d0=a
1=d1=2a+2b
解方程组，得a=1,b=-0.5，所以可以将递归关系式表示为
dn=2n-n2n-1
注：以上介绍的一种将递归关系式变换为非递归关系式的一种方法。这种方法只是针对一些特定的递归关系，对于不同的递归关系式，变换的方法各有不同。一般每一种递归关系，都可以使用非递归程序描述，不过这会使程序变得非常难以理解，而且程序的代码量也会成倍增加。因此，每每遇到递归，都是一个运算效率与代码的可读性的二选一的抉择。
不过，一定要相信问题总是会有解决的办法的，办法总比问题多嘛！
?
本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986